線性結(jié)構(gòu)-雙鏈表和循環(huán)鏈表

線性結(jié)構(gòu)-雙鏈表雙鏈表的引出

單鏈表的不足

每個(gè)結(jié)點(diǎn)的指針域只放了一個(gè)指針，該指針指向該結(jié)點(diǎn)的直接后繼。因此，每查找一個(gè)數(shù)據(jù)元素，都必須從頭結(jié)點(diǎn)開(kāi)始，由前向后單方向搜索。datanextdatanextprior指向直接前趨數(shù)據(jù)域指向直接后繼C語(yǔ)言描述：

structnode{

elemtypedata;

structnode*next;}

structnode{

elemtypedata;

structnode*prior,*next;}邏輯示意圖若P是指向表中某一結(jié)點(diǎn)（頭結(jié)點(diǎn)除外）的指針，明顯有如下關(guān)系：

P->next->prior=PP->prior->next=Pa1a2an

空雙鏈表的建立（初始化）插入結(jié)點(diǎn)刪除結(jié)點(diǎn)雙鏈表的基本操作空雙鏈表的建立操作描述：建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表

算法：1、分配一個(gè)結(jié)點(diǎn)的內(nèi)存空間C語(yǔ)言描述：

voidinitiate_list(node**h){

*h=(node*)mallcoc(sizeof(node));(*h)->prior=NULL;(*h)->next=NULL;}2、使鏈表指針指向該頭結(jié)點(diǎn)插入結(jié)點(diǎn)操作描述：在第i個(gè)元素后插入新元素anew，構(gòu)成一個(gè)新的雙鏈表。算法分析：同單向鏈表一樣，先打開(kāi)ai和ai＋1之間的鏈，插入anew后，重建鏈接關(guān)系。aiNPai＋1NPanewNP.3、anew->next=ai＋11、ai->next=anew2、anew->previous=ai4、ai＋1->previous=anewppnewC語(yǔ)言描述voidinsert1(node*p,elemtype

anew){node*pnew;

pnew=(node*)malloc(sizeof(node));

pnew->data=anew;}

p->next->prior-=pnew;

pnew->next=p->next;

pnew->prior=p;

p->next=pnew

;voidinsert2(node*h,int

i,elemtype

anew){node*p,*pnew;

int

j;//定位，使p指向第i個(gè)結(jié)點(diǎn)

p=h;

for(j=0;j<i;j++){

p=p->next;

if(p==NULL)return;

}

pnew=(node*)malloc(sizeof(node));……}刪除結(jié)點(diǎn)操作描述：刪除雙向鏈表的第i個(gè)元素。算法分析：相對(duì)雙向鏈表的插入操作而言，刪除比較簡(jiǎn)單，只需要重新建立元素ai-1和元素ai+1之間的鏈接，并釋放元素ai的空間就可以了。ai-1NPaiNPai＋1NPpaiNPVoiddelete(node*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}雙向鏈表的性能分析優(yōu)點(diǎn)：可以從任一節(jié)點(diǎn)開(kāi)始，訪問(wèn)表中的任一節(jié)點(diǎn)。訪問(wèn)順序自由。缺點(diǎn)：占用空間增多，內(nèi)存利用率減低。根據(jù)實(shí)際需要，選擇使用單向鏈表還是雙向鏈表。線性結(jié)構(gòu)-循環(huán)鏈表循環(huán)鏈表

循環(huán)鏈表是一種首尾相接的鏈表。在不增加存儲(chǔ)空間的前提下，實(shí)現(xiàn)了雙向鏈表的操作特點(diǎn)，即可以從任一節(jié)點(diǎn)開(kāi)始訪問(wèn)所有節(jié)點(diǎn)。a1a2anha1a2anhhhhh尾指針a1a2anr循環(huán)單鏈表更常用尾指針來(lái)命名。hr優(yōu)點(diǎn)：查找鏈表開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，其存儲(chǔ)位置分別為r->next->next和r。合并兩個(gè)循環(huán)鏈表將兩個(gè)線性表（a1，a2，……，an

）和（b1，b2，……，bn

）鏈接成一個(gè)線性表（a1，a2，……，an

，b1，b2，……，bn

）。頭指針表示的單鏈表或循環(huán)單鏈表：必需遍歷第一個(gè)鏈表.尾指針表示的循環(huán)單鏈表：只需要修改一些指針域.a1a2anhabababrarbababa1a2anrb1b2bnra1a2anb1b2bnrvoidconnect_r(node*ra,node*rb){p=rb->next;

rb->next=ra->next;

ra->next=p>next;

free(p);}

voidconnect_h(node*ha,node*hb){node*p