計(jì)算機(jī)軟件技術(shù)編程基礎(chǔ) 線性表.ppt

1、線性表的定義：線性表L是由n個(gè)數(shù)據(jù)元素a1,a2, an組成的有限序列。L=（ a1,a2, ai , ai+1, , an） 其中n=0為表的長度 n=0時(shí)是空表，記為L=（ ）,特點(diǎn)： 唯一的起點(diǎn)：沒有前驅(qū)，有一個(gè)唯一的后繼 唯一的終點(diǎn)：有一個(gè)唯一的前驅(qū)而沒有后繼 內(nèi)部結(jié)點(diǎn)：有唯一的前驅(qū)，唯一的后繼 結(jié)點(diǎn)個(gè)數(shù)：線性表的長度 ,在同一表中，元素類型相同 例如： 字母表(A,B,C,D，Z)； 數(shù)字表（1，2，3， ，10)； 成績表,2 線性表的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)順序表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表,順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)： 1 存儲(chǔ)空間是連續(xù)的 2 各數(shù)據(jù)元素在存儲(chǔ)空間中按邏輯順序依次存放,內(nèi)存空間,

2、a1,a2,ai,an,存儲(chǔ)地址,Loc(a1),Loc(a1)+k,Loc(ai)+(i-1)k,Loc(an)+(n-1)k,插入運(yùn)算 在表中插入元素的條件是：順序表不滿 插入操作的步驟為,元素后移如何實(shí)現(xiàn)？,void insl(int m, int *n_point, int cp, int i, int b) int j; if(*n_point=m) if(i*n_point) for(j=*n_point;j=i;j-) ,coutoverflowendl; return;,i=*n_point+1;,cpj=cpj-1;,cpi-1=b;,*n_point=*n_point+1;

3、,插入位置,插入值,表,表容量,表長計(jì)數(shù),void insl(int m, int *n_point, int cp, int i, int b) int j; if(*n_point=m) cout*n_point) i=*n_point+1; for(j=*n_point;j=i;j-) cpj=cpj-1; cpi-1=b; *n_point=*n_point+1; ,插入位置,插入值,表,表容量,表長計(jì)數(shù),刪除運(yùn)算 條件是：存在指定序號(hào)元素,void desl(int *n_point,int *cp,int i) int j; if(*n_point=0)/空表 if(i*n_poi

4、nt)/輸入的序號(hào)不對(duì) coutnot this element in the listendl; return; for(j=i;j*n_point;j+) /i以后的各元素都向前移動(dòng)一個(gè)位置 /線性表的長度-1 ,coutunderflowendl; return;,cpj-1=cpj;,*n_point=*n_point-1;,刪除位置,表,表長計(jì)數(shù),void desl(int *n_point,int *cp,int i) int j; if(*n_point=0)/空表 cout*n_point)/輸入的序號(hào)不對(duì) coutnot this element in the listend

5、l; return; for(j=i;j*n_point;j+) cpj-1=cpj;/i以后的各元素都向前移動(dòng)一個(gè)位置 *n_point=*n_point-1;/線性表的長度-1 ,template T max(T x,T y) return (xy)? x:y; ,如果使用模板，數(shù)據(jù)類型本身就是一個(gè)參數(shù)：,類型作參數(shù),關(guān)鍵字template 表示正在聲明一個(gè)模板，數(shù)據(jù)類型參數(shù)T由模板參數(shù)給出。,該模板的含義為，無論模板參數(shù)T實(shí)例為int、float或任意其他類型，包括類類型時(shí)，函數(shù)max就為實(shí)例化了的類型的參數(shù)求最大值。,void main() int x=9,y=8,t1; t1=max

6、(x,y); double x1=7., y1=12.,t2; t2=max(x1,y1); ,插入算法執(zhí)行時(shí)間: 元素總個(gè)數(shù)為n，各個(gè)位置插入的概率相等為p1/n,平均移動(dòng)元素次數(shù)為:,總時(shí)間開銷估計(jì)為:O(n),刪除算法時(shí)間代價(jià)與插入操作相似，O(n),順序表存取元素方便，時(shí)間代價(jià)為O(1) 插入、刪除操作則付出時(shí)間代價(jià)O(n),結(jié)論：當(dāng)n較大時(shí)，大量移動(dòng)元素，耗時(shí),解決辦法：不移動(dòng)元素的存儲(chǔ)方法,2.2.2棧的定義 棧是只能在表尾進(jìn)行插入和刪除元素的線性表,a1,an-1,an,入棧 push,出棧 pop,棧底bottom,棧頂top,特性：后進(jìn)先出 last in frist out

7、,棧的運(yùn)算,棧的初始化建立一個(gè)空棧 入棧運(yùn)算將元素放到棧頂 退棧運(yùn)算刪除當(dāng)前棧頂元素 讀棧頂元素,/入棧運(yùn)算 void push( int *cp, int m, int *p_top, int x) if(*p_top=m) ,coutstack overflowendl;,*p_top=*p_top+1;,cp*p_top-1=x;,棧頂指針,棧,插入元素,插入位置,/退棧運(yùn)算 void pop( int *cp, int m, int *p_top, int ,y=cp*p_top-1;,*p_top=*p_top-1;,棧頂指針,棧,刪除元素的值,刪除位置,void readtop(

8、int *cp, int m, int *p_top, int y=NULL; return;,y=cp*p_top-1;,/讀棧頂元素,隊(duì)列的定義：一端插入，另一端刪除元素的線性表,A,B,D,E,入隊(duì),出隊(duì),隊(duì)尾 rear,隊(duì)頭 front,特點(diǎn)：先進(jìn)先出，frist in frist out,C,插入一個(gè)元素,B,D,E,入隊(duì),出隊(duì),隊(duì)尾 rear,隊(duì)頭 front,C,F,刪除一個(gè)元素后的線性表,B,D,E,入隊(duì),出隊(duì),隊(duì)尾 rear,隊(duì)頭 front,C,最先插入的元素將最先被刪除,A,B,D,E,C,A,隊(duì)頭 front,循環(huán)隊(duì)列將隊(duì)首和隊(duì)尾連接起來形成一個(gè)環(huán)形表,rear,m,f

9、ront,1,2,m,1,2,m-1,入隊(duì)運(yùn)算：循環(huán)隊(duì)列的尾部加入一個(gè)新元素。,1 判斷循環(huán)隊(duì)列是否已滿。當(dāng)循環(huán)隊(duì)列非空(s=1)，且隊(duì)尾指針等于隊(duì)頭指針時(shí)，循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算上溢(隊(duì)尾指針趕上了隊(duì)頭指針）,標(biāo)志s=0,表示隊(duì)列空； s=1,表示隊(duì)列非空；,2 隊(duì)尾指針rear加一。當(dāng)隊(duì)尾指針rear=m+1時(shí)，則置rear=1,3新元素加入隊(duì)尾指針?biāo)肝恢?。置?duì)空標(biāo)志s=1,m,1,2,m-1,front,rear,i,void addcp( char *cp, int mm, int *rear, int *front, int /標(biāo)志隊(duì)列非空 ,隊(duì)列,隊(duì)尾指針,隊(duì)頭指針,入隊(duì)元素,隊(duì)列容量,退隊(duì)運(yùn)算：每進(jìn)行一次退隊(duì)運(yùn)算，隊(duì)頭指針front進(jìn)一。當(dāng)隊(duì)頭指針front=m+1時(shí)，則置front=1,退隊(duì)運(yùn)算： 1 判斷隊(duì)列是否為空(s=0)，空隊(duì)列不能進(jìn)行退隊(duì)運(yùn)算 2 將隊(duì)頭指針front 進(jìn)一(front= front+1)。當(dāng)隊(duì)頭指針front=m+1時(shí)，則置front=1 3將隊(duì)頭指針front 所指的元