【文章內(nèi)容簡(jiǎn)介】 0/11/23 32 從圖中可見，每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址存放在直接前驅(qū)的指針域中。所以要訪問鏈表中數(shù)據(jù)元素 C， 必須由頭指針 head得到第一個(gè)結(jié)點(diǎn)（數(shù)據(jù) A） 的地址，由該結(jié)點(diǎn)的指針域得到第二個(gè)結(jié)點(diǎn)（數(shù)據(jù) B）的地址，再由其指針域得到存儲(chǔ)數(shù)據(jù) C的結(jié)點(diǎn)地址，訪問該結(jié)點(diǎn)的數(shù)據(jù)域就可以處理數(shù)據(jù) C了。鏈表這種順著指針鏈依次訪問數(shù)據(jù)元素的特點(diǎn)，表明鏈表是一種 順序存儲(chǔ)結(jié)構(gòu) ，只能順序操作鏈表中元素。不能像順序表（數(shù)組）那樣可以按下標(biāo) 隨機(jī) 存取。 為了提高順序操作的速度，使操作更加靈活方便，對(duì)鏈表中的指針采用了不同的設(shè)置，構(gòu)成了不同的鏈表。如只設(shè)置一個(gè)指向后繼結(jié)點(diǎn)地址的指針域是單鏈表；將其首尾相接構(gòu)成一個(gè)環(huán)狀結(jié)構(gòu)，稱為循環(huán)鏈表；增加一個(gè)指向前驅(qū)的指針就構(gòu)成雙向鏈表。 在鏈表存儲(chǔ)結(jié)構(gòu)中，不要求存儲(chǔ)空間的連續(xù)性，數(shù)據(jù)元素之間的邏輯關(guān)系由指針來(lái)確定。由于鏈?zhǔn)酱鎯?chǔ)的靈活性，這種存儲(chǔ)方式既可用于表示線性結(jié)構(gòu)，也可以用來(lái)表示非線性結(jié)構(gòu)。 2020/11/23 33 單向鏈表 在圖 27所示的鏈表中，每個(gè)結(jié)點(diǎn)只有一個(gè)指向后繼的指針。也就是說(shuō)訪問數(shù)據(jù)元素只能由鏈表頭依次到鏈表尾，而不能做逆向訪問。稱這種鏈表為單向鏈表或線性鏈表。這是一種最簡(jiǎn)單的鏈表。 單鏈表分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種類型。 對(duì)于空鏈表，頭結(jié)點(diǎn)的指針域?yàn)榭?。圖 28是帶頭結(jié)點(diǎn)的鏈表示方式： 圖 28（ a） 為帶頭結(jié)點(diǎn)的空鏈 (b)為帶頭結(jié)點(diǎn)的單鏈表 headheada1a2a3∧(a) 空鏈表（b) 非空鏈表∧2020/11/23 34 由于鏈表是一種動(dòng)態(tài)管理的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)需動(dòng)態(tài)產(chǎn)生。 1． 初始化鏈表 initlist(L)的實(shí)現(xiàn) 建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表 。 所謂空鏈表就是指表長(zhǎng)為 0的表 。 在這種情況下 ， 鏈表中沒有元素結(jié)點(diǎn) 。 但應(yīng)有一個(gè)頭結(jié)點(diǎn) ， 其指針域?yàn)榭?。 void initlist(LinkList *L) { *L=(LNode *)malloc(sizeof(LNode))。 (*L)next=NULL。 } 在函數(shù)調(diào)用時(shí)，指針 L指向的內(nèi)容發(fā)生了變化，為使得調(diào)用函數(shù)中頭指針變量 head獲得頭結(jié)點(diǎn)地址，需傳遞頭指針變量的地址給 initlist()函數(shù)，而函數(shù)中定義二級(jí)指針變量 L接受該地址值，從而返回改變后的值。 2020/11/23 35 2． 求線性表長(zhǎng)度 Getlen(L)的實(shí)現(xiàn) 設(shè)計(jì)思路：設(shè)置一個(gè)初值為 0的計(jì)數(shù)器變量和一個(gè)跟蹤鏈表結(jié)點(diǎn)的指針 p。 初始時(shí) p指向鏈表中的第一個(gè)結(jié)點(diǎn) ， 然后順著 next域依次指向每個(gè)結(jié)點(diǎn) ， 每指向一個(gè)結(jié)點(diǎn)計(jì)數(shù)器變量加 1。 當(dāng) p為 0時(shí) ， 結(jié)束該過程 。 其時(shí)間復(fù)雜度為 O(n)。 int Getlen(LinkList L) { int num=0。 LNode *p。 p=Lnext。 while(p!=NULL) { num++。 p=pnext。 } return(num)。 } 2020/11/23 36 3． 按序號(hào)取元素 Getelem(L,i)的實(shí)現(xiàn) 根據(jù)前面的討論 ， 對(duì)單鏈表中的結(jié)點(diǎn)只能順序存取 ， 即訪問前一個(gè)結(jié)點(diǎn)后才能接著訪問后一個(gè)結(jié)點(diǎn) 。 所以要訪問單鏈表中第 i個(gè)元素值 ， 必須從頭指針開始遍歷鏈表 ， 依次訪問每個(gè)結(jié)點(diǎn) ， 直到訪問到第 i個(gè)結(jié)點(diǎn)為止 。 同順序表一樣 ， 也需注意存取的位置是否有效 。 LNode *Getelem(LinkList L,int i) { LNode *p。 int pos=1。 p=Lnext。 if(i1 || iGetlen(L)) exit(1)。 while(posi) { p=pnext。 pos++。 } return p。 } 2020/11/23 37 4． 查找運(yùn)算 locate(L,x)的實(shí)現(xiàn) 設(shè)計(jì)思路：設(shè)置一個(gè)跟蹤鏈表結(jié)點(diǎn)的指針 p， 初始時(shí) p指向鏈表中的第一個(gè)結(jié)點(diǎn) ， 然后順著 next域依次指向每個(gè)結(jié)點(diǎn) ， 每指向一個(gè)結(jié)點(diǎn)就判斷其值是否等于 x， 若是則返回該結(jié)點(diǎn)地址 。 否則繼續(xù)往后搜索 ， 直到 p為 0， 表示鏈表中無(wú)此元素 ， 返回 NULL。 其時(shí)間復(fù)雜度為 O(n)。 LNode *Locate(LinkList L,int x) { LNode *p。 p=Lnext。 while(p!=NULL amp。amp。 pdata!=x) p=pnext。 return p。 } 2020/11/23 38 5． 鏈表的插入算法 inselem(L,i,x)的實(shí)現(xiàn) 單鏈表結(jié)點(diǎn)的插入是利用修改結(jié)點(diǎn)指針域的值 ， 使其指向新的鏈接位置來(lái)完成的插入操作 ， 而無(wú)需移動(dòng)任何元素 。 假定在鏈表中值為 ai的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，要完成這種插入必須首先找到所插位置的前一個(gè)結(jié)點(diǎn)，再進(jìn)行插入。假設(shè)指針 q指向待插位置的前驅(qū)結(jié)點(diǎn)，指針 s指向新結(jié)點(diǎn)，則完成該操作的過程如圖 29所示。 2020/11/23 39 圖 29 p前插入 s結(jié)點(diǎn)過程示意圖 s=(LNode *)malloc(sizeof(LNode))；sdata=x；( b)申請(qǐng)新結(jié)點(diǎn)s，數(shù)據(jù)域置xxsheada1a2...ai1p...aian∧xsheada1a2...ai1p...aian∧②①(a)找到插入位置snext=qnextqnext=s(c)修改指針域，將新結(jié)點(diǎn)s插入關(guān)鍵語(yǔ)句：qq上述指針進(jìn)行相互賦值的語(yǔ)句順序不能顛倒。 2020/11/23 40 void Inselem(LinkList L,int i,int x) { LNode *p,*q,*s。 int pos=1。 p=L。 if(i1 || iGetlen(L)+1) exit(1)。 s=(LNode *)malloc(sizeof(LNode))。 sdata=x。 while(pos=i) { q=p。p=pnext。 pos++。 } snext=qnext。 qnext=s。 } 2020/11/23 41 若傳給函數(shù)的是待插入結(jié)點(diǎn)的地址 ， 可編寫如下的算法： void Insnode(LinkList L,int i,LNode *s) { LNode *p,*q。 int pos=1。 if(i1 || iGetlen(L)+1) exit(1)。 p=L。 while(pos=i) { q=p。p=pnext。 pos++。 } snext=qnext。 qnext=s。 } 2020/11/23 42 6． 鏈表的刪除運(yùn)算 delelem(L,i)的實(shí)現(xiàn) 要?jiǎng)h除鏈表中第 i個(gè)結(jié)點(diǎn) ， 首先在單鏈表中找到刪除位置前一個(gè)結(jié)點(diǎn) ， 并用指針 q指向它 ， 指針 p指向要?jiǎng)h除的結(jié)點(diǎn) 。 將 *q的指針域修改為待刪除結(jié)點(diǎn) *p的后繼結(jié)點(diǎn)的地址 。 刪除后的結(jié)點(diǎn)需動(dòng)態(tài)的釋放 。 如下圖 210所示 。 假定刪除的結(jié)點(diǎn)是值為 ai的結(jié)點(diǎn) 。 圖 210(c)中虛線表示刪除結(jié)點(diǎn) *p后的指針指向 。 具體算法描述為： { q=qnext。 pos++。 } p=qnext。 qnext=pnext。 free(p)。 } void Delelem(LinkList L,int i) { int pos=1。 LNode *q=L,*p。 if(i1 || iGetlen(L)) exit(1)。 while(posi) 2020/11/23 43 x=pdata；( b)返回被刪除結(jié)點(diǎn)數(shù)據(jù)xxpheada1a2...ai1q...aian∧(a)找到刪除位置pheada1...(c)修改指針域，將結(jié)點(diǎn)p刪除qai1pai...an∧ai+1①②關(guān)鍵語(yǔ)句： qnext=pnext；free(p)圖 210 線性鏈表的刪除過程示意圖 2020/11/23 44 在插入和刪除算法中 ， 都是先查詢確定操作位置 ， 然后再進(jìn)行插入和刪除操作 。 所以其時(shí)間復(fù)雜度均為 O(n)。 另外在算法中實(shí)行插入和刪除操作時(shí)沒有移動(dòng)元素的位置 ， 只是修改了指針的指向 ， 所以采用鏈表存儲(chǔ)方式要比順序存儲(chǔ)方式的效率高 。 7． 鏈表元素輸出運(yùn)算 displist(L)的實(shí)現(xiàn) 從第一個(gè)結(jié)點(diǎn)開始 ， 順著指針鏈依次訪問每一個(gè)結(jié)點(diǎn)并輸出 。 void displist(LinkList L) { LNode *p。 p=Lnext。 while(p!=NULL) { printf(%4d,pdata)。 p=pnext。 } printf(\n)。 } 2020/11/23 45 圖 211 單鏈表的倒置 heada1a2... ai1...aian∧headanan1... ai...ai1a1∧(a)倒置前(b)倒置后2020/11/23 46 【 例 24】 利用前面定義的基本運(yùn)算函數(shù) ， 編寫將一已知的單鏈表H倒置的程序 。 如圖 211的操作 。 (a)為倒置前 ， (b)為倒置后 。 【解】算法基本思路：不另外增加新結(jié)點(diǎn)，而只是修改原結(jié)點(diǎn)的指針。設(shè)置指針 p ， 令其指向 headnext， 并將 headnext置空，然后依次將 p所指鏈表的結(jié)點(diǎn)順序摘下，插入到 head之后即可。具體算法如下： void reverse(LinkList L) { LNode *p,*q。 if(Lnext!=NULL) //至少有兩個(gè)元素 { p=Lnext。 Lnext=NULL。 while(p!=NULL) 2020/11/23 47 { q=p。 p=pnext。 Insnode(L,1,q)。 } } } main() { LNode *head,*p。 int i,x。 initlist(amp。head)。 for(i=1。i=5。i++) { scanf(%d,amp。x)。 Inselem(head,i,x)。 } reverse(head)。 displist(head)。 } 該算法只是對(duì)鏈表順序掃描一遍即完成了倒置，所以時(shí)間復(fù)雜性為O(n)。 2020/11/23 48 循環(huán)鏈表 在單鏈表中 ， 最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?（ NULL） 。訪問單鏈表中任何數(shù)據(jù)只能從鏈表頭開始順序訪問 ， 而不能進(jìn)行任何位置的隨機(jī)查詢?cè)L問 。 如要查詢的結(jié)點(diǎn)在鏈表的尾部也需遍歷整