s1 線性表-02級

1、實例線性表的邏輯結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)第一章 線性表線性表的應(yīng)用舉例順序表與鏈表比較返回目錄第一章 線性表1.0 實例書目自動檢索系統(tǒng)001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件書目文件1、各條書目信息之間存在一個對一個的線性關(guān)系、各條書目信息之間存在一個對一個的線性關(guān)系2、如何在計算機(jī)中存儲書目信息、如何在計算機(jī)中存儲書目信息3、數(shù)據(jù)操作：查找，插入，刪除，修改等、數(shù)據(jù)操作：查找，插入，刪除，修改等約瑟夫環(huán)問題35487216n=8 s=3 m=43548721644444444線性結(jié)構(gòu)特點：在數(shù)據(jù)元素

2、的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼1.1 線性表的邏輯結(jié)構(gòu)定義：一個線性表是n個數(shù)據(jù)元素的有限序列niaaaa,.,.,21如例例 英文字母表（英文字母表（A,B,C,.Z)是一個線性表是一個線性表例例學(xué)號姓名年齡001張三18002李四19數(shù)據(jù)元素數(shù)據(jù)元素特征：有限、序列、同構(gòu)v元素個數(shù)n表長度，n=0空表v1in時lai的直接前驅(qū)是ai-1，a1無直接前驅(qū)lai的直接后繼是ai+1，an無直接后繼v元素同構(gòu)，且不能出現(xiàn)缺項運算：存取 插

3、入 刪除 查找 合并 分解 排序 求長度1.2 順序存儲的線性表順序表：v定義：用一組地址連續(xù)的存儲單元存放一個線性表叫v元素地址計算方法：an.ai.a2a1LlLOC(ai)=LOC(a1)+(i-1)*L ( a1,a2, an)l( LOC(ai)=LOC(a0)+i*L (a0,a1, an-1) )lLOC(ai+1)=LOC(ai)+Ll其中：uL一個元素占用的存儲單元個數(shù)uLOC(ai)線性表第i個元素的地址v特點：l實現(xiàn)邏輯上相鄰物理地址相鄰l實現(xiàn)隨機(jī)存取v實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)a1a2an內(nèi)存內(nèi)存V數(shù)組下標(biāo)數(shù)組下標(biāo)12n元素序號元素序號01n-1M-1typedef

4、 int DATATYPE; #define M 1000DATATYPE dataM;例例 typedef struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 備用空間數(shù)據(jù)元素不是簡單類型時數(shù)據(jù)元素不是簡單類型時,可定義可定義結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組或或動態(tài)申請和釋放內(nèi)存動態(tài)申請和釋放內(nèi)存DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE);free(pData); 線性表插入v

5、定義：線性表的插入是指在第i（1i n+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表niiaaaaa,1,21 變成長度為n+1n+1的線性表niiaaxaaa,1,21 需將第i至第n共（n-i+1)n-i+1)個元素后移v算法判斷i值是否合法元素后移插入int sq-insert(int i,int x,int v,int *p) int j,n; n=*p; if(in+1) return (1); if(*p=M) return(2); else for(j=n;j=i;j-) vj+1=vj; vi=x; *p=+n; return (0); #define M 10ma

6、in() int aM=3,2,7,1,9; int i,x,n=5; scanf(%d,%d,&i,&x); sq-insert(i,x,a,&n); for(i=0;in;i+) printf(%d,ai); printf(nn=%dn,n);內(nèi)存內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)數(shù)組下標(biāo)n-1in12i元素序號元素序號i+1nn+1內(nèi)存內(nèi)存01i-1V數(shù)組下標(biāo)數(shù)組下標(biāo)n-1in12i元素序號元素序號i+1nn+1a1a2aiai+1anan-1xv算法時間復(fù)雜度T(n)l設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時

7、，所需移動的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認(rèn)為刪除v定義：線性表的刪除是指將第i（1 i n）個元素刪除，使長度為n的線性表niiaaaaa,1,21 變成長度為n-1n-1的線性表niiaaaaa,11,21 需將第i+1至第n共（n-i)n-i)個元素前移v算法判斷i值是否合法元素前移int sq-delete(int i,int v,int *p) int j,n; n=*p; if(in) return (1); else for(j=i;jdata表示表示p指向結(jié)點的數(shù)據(jù)域指向結(jié)點的數(shù)據(jù)域(*p).link

8、p-link表示表示p指向結(jié)點的指針域指向結(jié)點的指針域生成一個生成一個NODE型型新結(jié)點：新結(jié)點： p=(NODE*)malloc(sizeof(NODE);系統(tǒng)回收系統(tǒng)回收p結(jié)點：結(jié)點：free(p)單鏈表v定義：結(jié)點中只含一個指針域的鏈表叫，也叫線性鏈表頭結(jié)點頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫頭結(jié)點指針域為空表示線性表為空頭結(jié)點指針域為空表示線性表為空ha1a2頭結(jié)點頭結(jié)點an .h空表空表v1.4.2 單鏈表的基本運算l查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULLu算法描述NODE *dlbcz(NODE *h

9、,int x)NODE *p; p=h;while(p!=NULL & p-data!=x)p=p-link;return (p);ppp頭指針頭指針ha1a2a3anWhile循環(huán)中語句頻度為循環(huán)中語句頻度為若找到結(jié)點若找到結(jié)點X，為結(jié)點為結(jié)點X在表中的序號在表中的序號否則，為否則，為n nOnTu算法評價l查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULLu算法描述NODE *dlbcz(NOde *h,int x)NODE *p; p=h;while(p!=NULL & p-data!=x)p=p-link;return (p);pabxsl插

10、入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法評價void dlbcr(NODE *p,int x) NODE *s; s=(NODE*)malloc(sizeof(NODE); s-data=x; s-link=p-link; p-link=s;u算法描述pabc 1OnTu算法評價l刪除：單鏈表中刪除b，設(shè)p指向ap-link=p-link-link;void dlbsc(NODE *p) NODE *q; if(p-link!=NULL) q=p-link; p-link=q-link; free(q);l動態(tài)

11、建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0san頭插法NODE* dlbjl(int a,int n) NODE *s,*h; int i; h=(NODE*)malloc(sizeof(NODE); h-data=0;/初始化初始化 h-link=NULL; for(i=n+1;i0;i-) s=(NODE*)malloc(sizeof(NODE); s-data=ai-1; s-link=h-link; h-link=s; return (h);生成頭結(jié)點循環(huán)插入l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈

12、表，h為頭指針u算法描述算法描述san-1h頭結(jié)點頭結(jié)點an 0NODE* dlbjl(int a,int n) NODE *s,*h; int i; h=(NODE*)malloc(sizeof(NODE); h-data=0; h-link=NULL; for(i=n+1;i0;i-) s=(NODE*)malloc(sizeof(NODE); s-data=ai-1; s-link=h-link; h-link=s; return (h);l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述算法描述san-2h頭結(jié)點頭結(jié)點0an-1an NODE*

13、 dlbjl(int a,int n) NODE *s,*h; int i; h=(NODE*)malloc(sizeof(NODE); h-data=0; h-link=NULL; for(i=n;i0;i-) s=(NODE*)malloc(sizeof(NODE); s-data=ai-1; s-link=h-link; h-link=s; return (h);l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述算法描述ha1a2頭結(jié)點頭結(jié)點an .0 nOnTu算法評價算法評價NODE* dlbjl(int a,int n)NODE *s,*h

14、; int i; h=(NODE*)malloc(sizeof(NODE); h-data=0; h-link=NULL; for(i=n;i0;i-) s=(NODE*)malloc(sizeof(NODE); s-data=ai-1; s-link=h-link; h-link=s; return (h);l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0sa1尾插法l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0sa2尾插法a1l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放

15、在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0尾插法a1a2sa3l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0尾插法a1a2an-1san l動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述h頭結(jié)點頭結(jié)點0尾插法a1a2an-1an-1課堂小測驗：編寫算法實現(xiàn)尾插法建立單鏈表函數(shù)原型：NODE* dlbjl(int a,int n)；NODE* dlbjl(int a,int n)NODE *s,*h,*p;int i;h=(NODE*)malloc(sizeof(NOD

16、E);h-data=0;h-link=NULL;p=h;for(i=1;idata=ai-1; s-link=NULL; p-link=s; p=s;return (h);v單鏈表特點l它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用l不需預(yù)先分配空間l指針占用額外存儲空間l不能隨機(jī)存取，查找速度慢1.4.3 用線性鏈表表示多項式 線性表的應(yīng)用舉例 一元多項式的表示及相加一元多項式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表可用線性表P P表示表示200001000231)(xxxS但對但對S(x)S(x)這樣的多項式浪費空間這樣的多項式浪費空間一般一般emmnx

17、PxPxPxPee2121)(其中其中為非零系數(shù)）（iPemee210用用數(shù)據(jù)域含兩個數(shù)據(jù)項數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示的線性表表示emPePePm，2121其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點定義typedef struct node int coef,exp; struct node *next;NODE;coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1A7 0 11 1

18、22 7 5 17 一元多項式相加pqpqpqpqpqNULL設(shè)設(shè)p,q分別指向分別指向A,B中某一結(jié)點，中某一結(jié)點，p,q初值初值是第一結(jié)點是第一結(jié)點比較比較p-exp與與q-expp-exp exp:p-exp q-exp:p-exp = =q-exp:0： 0：直到直到p或或q為為NULL 若若q=NULL，結(jié)束結(jié)束若若p=NULL，將將B中剩余部分連到中剩余部分連到A上即可上即可運算規(guī)則運算規(guī)則p結(jié)點是和多項式中的一項結(jié)點是和多項式中的一項p后移后移,q不動不動q結(jié)點是和多項式中的一項結(jié)點是和多項式中的一項將將q插在插在p之前之前,q后移后移,p不動不動系數(shù)相加系數(shù)相加從從A表中刪去表

19、中刪去p,釋放釋放p,q，p,q后移后移修改修改p系數(shù)域系數(shù)域,釋放釋放q，p,q后移后移算法描述void add_poly(NODE *pa,NODE *pb) NODE *p,*q,*u,*pre; int x; p=pa-next; q=pb-next; pre=pa; while(p!=NULL) &( q!=NULL) if(p-expexp) pre=p; p=p-next; else if(p-exp=q-exp) else u=q-next; q-next=p; pre-next=q; pre=q; q=u; if(q!=NULL) pre-next=q; free(p

20、b); x=p-coef+q-coef;if(x!=0) p-coef=x; pre=p; else pre-next=p-next; free(p); p=pre-next;u=q;q=q-next;free(u);賦初值q-1pa-1pb7 0 3 1 9 8 5 17 8 1 22 7 -9 8 ppre算法描述pre=p; p=p-next;p結(jié)點是和多項式中的一項結(jié)點是和多項式中的一項p后移后移,q不動不動p-exp exp:q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre算法描述 0：修改修改p系數(shù)域系數(shù)域, 釋放釋放q，p,q后移后移系數(shù)相

21、加系數(shù)相加x=p-coef+q-coef;if(x!=0) p-coef=x; pre=p; p=pre-next;u=q;q=q-next;free(u);q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre算法描述p-exp q-exp:q結(jié)點是和多項式中的一項結(jié)點是和多項式中的一項將將q插在插在p之前之前,q后移后移,p不動不動u=q-next;q-next=p;pre-next=q;pre=q; q=u;q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre算法描述=0：從從A表中刪去表中刪去p, 釋放釋放p,q

22、，p,q后移后移系數(shù)相加系數(shù)相加x=p-coef+q-coef;if(x=0)pre-next=p-next; free(p);p=pre-next;u=q;q=q-next;free(u);q=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre算法描述q=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述算法評價：設(shè)A和B多項式分別有m、n項 最壞情況下：T(n)=O(m+n)1.4.4 幾種變形的線性鏈表p頭指針頭指針ha1a2a3an1.4.4 循環(huán)鏈表(circular linked list)v循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀h空表空表v特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率v操作與單鏈表基本一致,循環(huán)條件不同l單鏈表p或或p-link=NULLl循環(huán)鏈表p或或p-link=ha1a2a3anh1.4.5雙向鏈表（double linked list）單鏈表具有單向性的缺點v結(jié)點定義typedef struct node datat