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

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

2、a1,a2,ai,an,存儲地址,Loc(a1),Loc(a1)+k,Loc(ai)+(i-1)k,Loc(an)+(n-1)k,插入運算 在表中插入元素的條件是：順序表不滿 插入操作的步驟為,元素后移如何實現(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、,插入位置,插入值,表,表容量,表長計數(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; ,插入位置,插入值,表,表容量,表長計數(shù),刪除運算 條件是：存在指定序號元素,void desl(int *n_point,int *cp,int i) int j; if(*n_point=0)/空表 if(i*n_poi

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

5、l; return; for(j=i;j*n_point;j+) cpj-1=cpj;/i以后的各元素都向前移動一個位置 *n_point=*n_point-1;/線性表的長度-1 ,template T max(T x,T y) return (xy)? x:y; ,如果使用模板，數(shù)據(jù)類型本身就是一個參數(shù)：,類型作參數(shù),關(guān)鍵字template 表示正在聲明一個模板，數(shù)據(jù)類型參數(shù)T由模板參數(shù)給出。,該模板的含義為，無論模板參數(shù)T實例為int、float或任意其他類型，包括類類型時，函數(shù)max就為實例化了的類型的參數(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ù)為n，各個位置插入的概率相等為p1/n,平均移動元素次數(shù)為:,總時間開銷估計為:O(n),刪除算法時間代價與插入操作相似，O(n),順序表存取元素方便，時間代價為O(1) 插入、刪除操作則付出時間代價O(n),結(jié)論：當(dāng)n較大時，大量移動元素，耗時,解決辦法：不移動元素的存儲方法,2.2.2棧的定義 棧是只能在表尾進(jìn)行插入和刪除元素的線性表,a1,an-1,an,入棧 push,出棧 pop,棧底bottom,棧頂top,特性：后進(jìn)先出 last in frist out

7、,棧的運算,棧的初始化建立一個空棧 入棧運算將元素放到棧頂 退棧運算刪除當(dāng)前棧頂元素 讀棧頂元素,/入棧運算 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;,棧頂指針,棧,插入元素,插入位置,/退棧運算 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;,/讀棧頂元素,隊列的定義：一端插入，另一端刪除元素的線性表,A,B,D,E,入隊,出隊,隊尾 rear,隊頭 front,特點：先進(jìn)先出，frist in frist out,C,插入一個元素,B,D,E,入隊,出隊,隊尾 rear,隊頭 front,C,F,刪除一個元素后的線性表,B,D,E,入隊,出隊,隊尾 rear,隊頭 front,C,最先插入的元素將最先被刪除,A,B,D,E,C,A,隊頭 front,循環(huán)隊列將隊首和隊尾連接起來形成一個環(huán)形表,rear,m,f

9、ront,1,2,m,1,2,m-1,入隊運算：循環(huán)隊列的尾部加入一個新元素。,1 判斷循環(huán)隊列是否已滿。當(dāng)循環(huán)隊列非空(s=1)，且隊尾指針等于隊頭指針時，循環(huán)隊列已滿，不能進(jìn)行入隊運算上溢(隊尾指針趕上了隊頭指針）,標(biāo)志s=0,表示隊列空； s=1,表示隊列非空；,2 隊尾指針rear加一。當(dāng)隊尾指針rear=m+1時，則置rear=1,3新元素加入隊尾指針?biāo)肝恢?。置隊空?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)志隊列非空 ,隊列,隊尾指針,隊頭指針,入隊元素,隊列容量,退隊運算：每進(jìn)行一次退隊運算，隊頭指針front進(jìn)一。當(dāng)隊頭指針front=m+1時，則置front=1,退隊運算： 1 判斷隊列是否為空(s=0)，空隊列不能進(jìn)行退隊運算 2 將隊頭指針front 進(jìn)一(front= front+1)。當(dāng)隊頭指針front=m+1時，則置front=1 3將隊頭指針front 所指的元