數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏-吳偉民主編課件第二章PPT

1、第二章 線性表線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個直接前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個直接后繼2.1 線性表的邏輯結(jié)構(gòu)定義：一個線性表是n個數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一個線性表例學(xué)號姓名年齡001張三18002李四19數(shù)據(jù)元素特征：v元素個數(shù)n表長度，n=0空表v1idata表示p指向結(jié)點的數(shù)據(jù)域(*p).linkp-link表示p指向結(jié)點的指針域生成一個JD型新結(jié)點：p=(JD *)malloc(size

2、of(JD);系統(tǒng)回收p結(jié)點：free(p)線性鏈表v定義：結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫頭結(jié)點指針域為空表示線性表為空ha1a2頭結(jié)點an .h空表v單鏈表的基本運算l查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULLu算法描述While循環(huán)中語句頻度為若找到結(jié)點X，為結(jié)點X在表中的序號否則，為n nOnTpabxsu算法評價l插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法評價u算法描述pabc 1OnTu算法評價l刪除：單鏈表中刪除

3、b，設(shè)p指向ap-link=p-link-link; nOnTl動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述u算法評價h頭結(jié)點an 0h頭結(jié)點an-10an a2.h頭結(jié)點an-10an ha1a2頭結(jié)點an .0Ch2_3.ch頭結(jié)點0v單鏈表特點l它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用l不需預(yù)先分配空間l指針占用額外存儲空間l不能隨機存取，查找速度慢循環(huán)鏈表(circular linked list)v循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀v特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率v操作與單鏈表基本一

4、致,循環(huán)條件不同l單鏈表p或p-link=NULLl循環(huán)鏈表p或p-link=Hhh空表雙向鏈表（double linked list）單鏈表具有單向性的缺點v結(jié)點定義typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表： LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);v

5、刪除l算法描述l算法評價：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法評價：T(n)=O(1)xSbaPv插入2.4 線性表的應(yīng)用舉例 一元多項式的表示及相加一元多項式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示20000100023

6、1)(xxxS但對S(x)這樣的多項式浪費空間一般emmnxPxPxPxPee2121)(其中為非零系數(shù)）（iPemee210用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示emPePePm，2121其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點定義typedef struct node int coef,exp; struct node *next;JD;coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元

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