1、. 線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)線性表的鏈?zhǔn)酱尜A結(jié)構(gòu) 線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈表。線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈表。 用一組任意的存貯單元用一組任意的存貯單元( (可連續(xù)，也可以不連續(xù)可連續(xù)，也可以不連續(xù)) )來存來存 放線性表的數(shù)據(jù)元素值及它在內(nèi)存的地址，放線性表的數(shù)據(jù)元素值及它在內(nèi)存的地址， 常用的鏈表常用的鏈表: : 單鏈表、單鏈表、循環(huán)鏈表、循環(huán)鏈表、雙向鏈表、雙向鏈表、多重鏈表等。多重鏈表等。 . 單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu) 只含有一個指針域來存放下一個元素地址，稱這只含有一個指針域來存放下一個元素地址，稱這 樣的鏈表為單鏈表或線性鏈表。樣的鏈表為單鏈表或線性鏈表。 線性鏈表中的結(jié)點(diǎn)結(jié)構(gòu)可描

2、述為線性鏈表中的結(jié)點(diǎn)結(jié)構(gòu)可描述為: : Data next next data 域：用來存放結(jié)點(diǎn)本身信息，類型由具體問題域：用來存放結(jié)點(diǎn)本身信息，類型由具體問題 而定，本書中將其設(shè)定為而定，本書中將其設(shè)定為elemtype類型，表示某一類型，表示某一 種具體的已知類型，種具體的已知類型， next域用來存放下一個元素地址。域用來存放下一個元素地址。 a2 180 a4 170 a6 NULL a1 110 a5 140 a3 130 150 地址 data 域 next 域 110 120 130 140 150 160 170 180 head 頭指針 圖 2-5 單鏈表示意圖 a1 a2

3、a3 a4 a5 a6 圖-6 單鏈表的邏輯表示 單鏈表可用單鏈表可用+描述為描述為: struct link elemtype data; /元素類型元素類型 link *next; /指針類型指針類型,存放下一個元素地址存放下一個元素地址 (a) 不帶頭結(jié)點(diǎn)的單鏈表 a1 head a2 an (b) 帶頭結(jié)點(diǎn)的單鏈表 head an 頭 a1 a2 圖 2-7 不帶頭結(jié)點(diǎn)和帶頭結(jié)點(diǎn)的單鏈表 232 單鏈表運(yùn)算單鏈表運(yùn)算 頭插法建立單鏈表頭插法建立單鏈表(如下圖所示如下圖所示) 執(zhí)行的語句組為:snextLnext；Lnexts； L (a) 建空表 c1 s s 指向新申請的結(jié)點(diǎn) sda

4、tac 1 (b) 申請新結(jié)點(diǎn)并賦值 L ci 1 s (c) 插入第一個結(jié)點(diǎn) Lc2c1 ci c1 s (d) 插入第i個元素 232 單鏈表運(yùn)算單鏈表運(yùn)算 頭插法建立單鏈表頭插法建立單鏈表(從左邊插入結(jié)點(diǎn)從左邊插入結(jié)點(diǎn)) link *hcreat( ) link *s,*p; int c1; /指針指針S，指針，指針P，變量，變量C1 cinc1; /輸入結(jié)點(diǎn)數(shù)值，為輸入結(jié)點(diǎn)數(shù)值，為0時算法結(jié)束時算法結(jié)束 p=NULL; /線性表為空表線性表為空表 while(c1) s=new link; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)S s-data=c1; /新結(jié)點(diǎn)新結(jié)點(diǎn)S的值為的值為C1 s-next=

5、p; /S的后繼結(jié)點(diǎn)的地址為的后繼結(jié)點(diǎn)的地址為P p=s; return p; /返回返回P結(jié)點(diǎn)的地址結(jié)點(diǎn)的地址 2 尾插法建立單鏈表尾插法建立單鏈表(如下圖所示如下圖所示) rs；r 始終指向單鏈表的表尾 L (a) 建空表 c1 s s 指向新申請的結(jié)點(diǎn)空間 sdatac 1 (b) 申請新結(jié)點(diǎn)并賦值 Lc1 s (c) 插入第一個結(jié)點(diǎn) Lc2c1 r r r nexts； (d) 插入第二個結(jié)點(diǎn) sr 2 尾插法建立單鏈表尾插法建立單鏈表(從右邊插入結(jié)點(diǎn)從右邊插入結(jié)點(diǎn)) link *rcreat( ) link *s,*r,*p; /指針類型指針類型 int c1; p=r=new li

6、nk; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) p，r p-next=NULL; /p結(jié)點(diǎn)的后繼結(jié)點(diǎn)為空結(jié)點(diǎn)的后繼結(jié)點(diǎn)為空 cinc1; while(c1) s=new link; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn) s s-data=c1; /s結(jié)點(diǎn)的數(shù)據(jù)值為結(jié)點(diǎn)的數(shù)據(jù)值為c1 r-next=s; /r結(jié)點(diǎn)的后繼結(jié)點(diǎn)為結(jié)點(diǎn)的后繼結(jié)點(diǎn)為s r=s; /s結(jié)點(diǎn)的地址傳給結(jié)點(diǎn)的地址傳給r結(jié)點(diǎn)結(jié)點(diǎn) cinc1; r-next=NULL; /r的后繼結(jié)點(diǎn)為空的后繼結(jié)點(diǎn)為空 return p; 3 單鏈表上的查找運(yùn)算單鏈表上的查找運(yùn)算 (1) 按值查找按值查找Locate(head,x) 在單鏈表在單鏈表head中，查找值為中，查

7、找值為x的結(jié)點(diǎn)，若找到，返回它的結(jié)點(diǎn)，若找到，返回它 的地址，否則返回的地址，否則返回NULL。 (2) 按序號查找按序號查找get(head,i) 在單鏈表在單鏈表head中查找第中查找第i個位置上的元素，若找到，個位置上的元素，若找到， 則返回它的地址，否則返回則返回它的地址，否則返回NULL。 按值查找：按值查找： Link *Locate(link *head,elemtype x) link *p; p=head-next; while(p!=NULL) return p; 算法的時間復(fù)雜度都為算法的時間復(fù)雜度都為(n)。 按序號查找：按序號查找： Link *get(link *h

8、ead,int i) int j; link *p; j=1; p=head-next; while(jnext; return p; 算法的時間復(fù)雜度都為算法的時間復(fù)雜度都為(n)。 4 單鏈表上的插入運(yùn)算單鏈表上的插入運(yùn)算 若將若將x插入插入a和和b 之間，插入結(jié)點(diǎn)的指針變化如圖之間，插入結(jié)點(diǎn)的指針變化如圖-8 所示。所示。 s a b x p 圖 2-8 插入結(jié)點(diǎn)時的指針修改 void insert(link *head,elemtype x,elemtype y) /頭指針頭指針head所指單鏈表中所指單鏈表中,在值為在值為y的結(jié)點(diǎn)之后插入值為的結(jié)點(diǎn)之后插入值為x的結(jié)點(diǎn)的結(jié)點(diǎn) link

9、 *p,*s; s=new link; s-data=x; if(head-next=NULL) /鏈表為空鏈表為空 head-next=s; s-next=NULL; p=Locate(head,y) /調(diào)用查找算法調(diào)用查找算法 if(p=NULL) coutnext=p-next; p-next=s; 單鏈表上的刪除運(yùn)算單鏈表上的刪除運(yùn)算 若將若將x刪除，刪除結(jié)點(diǎn)的指針變化如圖刪除，刪除結(jié)點(diǎn)的指針變化如圖2-9所示。所示。 p q a1 x a2 圖 2-9 刪除結(jié)點(diǎn)的指針修改 void delete(link *head,elemtype x) /在在head為頭指針的單鏈表中為頭指針的

10、單鏈表中,刪除值為刪除值為x的結(jié)點(diǎn)的結(jié)點(diǎn) link *p,*q; q=head; p=head-next; while(p!=NULL) p=p-next; if(p=NULL) coutnext=p-next; delete(p); 輸出單鏈表輸出單鏈表 若需將單鏈表按邏輯順序輸出若需將單鏈表按邏輯順序輸出(見圖見圖-10)，則必須從頭，則必須從頭 到尾訪問單鏈表中每一個結(jié)點(diǎn)，到尾訪問單鏈表中每一個結(jié)點(diǎn)， an 頭 a1 head a2 ( a )單鏈表示意圖 a1 a2 an (b )單鏈表輸出結(jié)果示意圖 圖 2-10 單鏈表按邏輯結(jié)構(gòu)輸出示意圖 void print(link *head

11、) link *p; p=head-next; while(p-next!=NULL) coutdata”; /輸出表中非最后一個元素輸出表中非最后一個元素 p=p-next; coutdata; /輸出表中最后一個元素輸出表中最后一個元素 coutprior-next = p = p-next-prior 雙向循環(huán)鏈表（見下圖所示）雙向循環(huán)鏈表（見下圖所示） 頭 a1 a2 an 尾 head rear (a) 雙向鏈表示意圖 雙向循環(huán)鏈表（見下圖所示）雙向循環(huán)鏈表（見下圖所示） L a1a2a3 L (a) 空的雙向循環(huán)鏈表 (b) 非空的雙向循環(huán)鏈表 雙向循環(huán)鏈表示意圖雙向循環(huán)鏈表示意圖

12、 雙向鏈表可用雙向鏈表可用C+描述如下：描述如下： struct dulink elemtype data; /結(jié)點(diǎn)的數(shù)據(jù)域結(jié)點(diǎn)的數(shù)據(jù)域,類型設(shè)定為類型設(shè)定為elemtype dulink * next, *prior; /定義指向直接后繼和直接定義指向直接后繼和直接 前驅(qū)的指針前驅(qū)的指針 2 2雙向鏈表插入運(yùn)算雙向鏈表插入運(yùn)算 duinsert (head,x,y) (head,x,y) 在雙向鏈表中，在值為在雙向鏈表中，在值為a a的結(jié)點(diǎn)之后的結(jié)點(diǎn)之后,b,b的結(jié)點(diǎn)之間的結(jié)點(diǎn)之間 插入值為插入值為c c的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化見下圖的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化見下圖 所示所示 ab s p c 雙向鏈表插入操作圖雙向鏈表插入操作圖 插入算法描述為：插入算法描述為： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 3 。雙向鏈表的刪除運(yùn)算。雙向鏈表的刪除運(yùn)算 dudelete(head ,x) 在以在以head為頭的雙向鏈表中刪除值為為頭的雙向鏈表中刪除值為x的結(jié)點(diǎn)，刪的結(jié)點(diǎn)，刪 除算法的指針變化見圖除算法的指針變化見圖2-17。 p a x b 圖 2-17 刪除 P 指針