雙向鏈表也叫雙鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。一、循環(huán)鏈表循環(huán)鏈表是與單鏈表一樣，是一種鏈?zhǔn)降拇鎯Y(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個結(jié)點的指針是指向該循環(huán)鏈表的第一個結(jié)點或者表頭結(jié)點，從而構(gòu)成一個環(huán)形的鏈。循環(huán)鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點：1、在建立一個循環(huán)鏈表時，必須使其最后一個結(jié)點的指針指向表頭結(jié)點，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個結(jié)點后插入一個新的結(jié)點。2、在判斷是否到表尾時，是判斷該結(jié)點鏈域的值是否是表頭結(jié)點，當(dāng)鏈域值等于表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。二、雙向鏈表雙向鏈表其實是單鏈表的改進(jìn)。當(dāng)我們對單鏈表進(jìn)行操作時，有時你要對某個結(jié)點的直接前驅(qū)進(jìn)行操作時，又必須從表頭開始查找。這是由單鏈表結(jié)點的結(jié)構(gòu)所限制的。因為單鏈表每個結(jié)點只有一個存儲直接后繼結(jié)點地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點地址的鏈域，又有存儲直接前驅(qū)結(jié)點地址的鏈域的這樣一個雙鏈域結(jié)點結(jié)構(gòu)呢？這就是雙向鏈表。在雙向鏈表中，結(jié)點除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結(jié)點地址，一般稱之為左鏈域。在c語言中雙向鏈表結(jié)點類型可以定義為：typedefstructnode{intdata;/*數(shù)據(jù)域*/structnode*llink,*rlink;/*鏈域，*llink是左鏈域指針，*rlink是右鏈域指針*/}JD;當(dāng)然，也可以把一個雙向鏈表構(gòu)建成一個雙向循環(huán)鏈表。雙向鏈表與單向鏈表一樣，也有三種基本運算：查找、插入和刪除。雙向鏈表的基本運算：1、查找假若我們要在一個帶表頭的雙向循環(huán)鏈表中查找數(shù)據(jù)域為一特定值的某個結(jié)點時，我們同樣從表頭結(jié)點往后依次比較各結(jié)點數(shù)據(jù)域的值，若正是該特定值，則返回指向結(jié)點的指針，否則繼續(xù)往后查，直到表尾。下例就是應(yīng)用雙向循環(huán)鏈表查找算法的一個程序。

searchpoint二search(head,studname);printfC你所要查找的人的姓名是:％s",*&searchpoint->name);}/*線性表的雙向鏈表存儲結(jié)構(gòu)*/typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;/*帶頭結(jié)點的雙向循環(huán)鏈表的基本操作(14個)*/voidInitList(DuLinkList*L){/*產(chǎn)生空的雙向循環(huán)鏈表L*/*L=(DuLinkList)malloc(sizeof(DuLNode));(*L)->next=(*L)->prior=*L;elseexit(OVERFLOW);}voidDestroyList(DuLinkList*L){/*操作結(jié)果：銷毀雙向循環(huán)鏈表L*/DuLinkListq,p=(*L)->next;/*p指向第一個結(jié)點*/while(p!=*L)/*p沒到表頭*/{q=p->next;free(p);p=q;

*L=NULL;voidClearList(DuLinkListL)/*不改變L*/{/*初始條件：L已存在。操作結(jié)果：將L重置為空表*/DuLinkListq,p=L->next;/*p指向第一個結(jié)點*/while(p!=L)/*p沒到表頭*/1q=“free(p);P=q；L->next二L->prior二L;/*頭結(jié)點的兩個指針域均指向自身*/}StatusListEmpty(DuLinkListL){/*初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE*/訐(L->next==L&&L->prior==L)returnTRUE;elsereturnFALSE;}intListLength(DuLinkListL){/*初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)*/inti=0;DuLinkListp=L->next;/*p指向第一個結(jié)點*/while(p!二L)/*p沒到表頭*/{i++；p=p->next;}returni;}StatusGetElem(DuLinkListL,inti,ElemType*e){/*當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK,否則返回ERROR*/intj=1;/*j為計數(shù)器*/DuLinkListp=L->next;/*p指向第一個結(jié)點*/while(p!=L&&jnext;j++;}if(p二二L||j>i)/*第i個元素不存在*/returnERROR;*e=p->data;/*取第i個元素*/returnOK;}intLocateElem(DuLinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始條件：L已存在，compare。是數(shù)據(jù)元素判定函數(shù)*//*操作結(jié)果：返回L中第1個與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。*//* 若這樣的數(shù)據(jù)元素不存在，則返回值為0*/inti=0;DuLinkListp=L->next;/*p指向第1個元素*/while(p!二L){i++；訐(compare(p->data,e))/*找到這樣的數(shù)據(jù)元素*/returni;p=p->next;}return0;}StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType*pre_e){/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，*//* 否則操作失敗，pre_e無定義*/DuLinkListp=L->next->next;/*p指向第2個元素*while(p!=L)/*p沒到表頭*/訐(p->data==cur_e){*pre_e=p->prior->data;returnTRUE;}p=p->next;}returnFALSE;

StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType*next_e){/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，*//* 否則操作失敗，next_e無定義*/DuLinkListp=L->next->next;/*p指向第2個元素*/while(p!=L)/*p沒到表頭*/{訐(p->prior->data二二cur_e){*next_e=p->data;returnTRUE;}p=p->next;returnFALSE;DuLinkListGetElemP(DuLinkListL,inti)/*另加*/{/*在雙向鏈表L中返回第i個元素的地址。i為0,返回頭結(jié)點的地址。若第i個元素不存在，*//*返回NULL*/intj;DuLinkListp=L;/*p指向頭結(jié)點*/if(i<0||i>ListLength(L))/*i值不合法*/returnNULL;for(j=1;j<二i;j++)p=p->next;returnp;StatusListlnsert(DuLinkListL,inti,ElemTypee){/*在帶頭結(jié)點的雙鏈循環(huán)線性表L中第i個位置之前插入元素e,i的合法值為1<i<表長+1*//*改進(jìn)算法2.18，否則無法在第表長+1個結(jié)點之前插入元素*/DuLinkListp,s;if(i<1||i>ListLength(L)+1)/*i值不合法*/returnERROR;p=GetElemP(L,i-1);/*在L中確定第i個元素前驅(qū)的位置指針p*/if(!p)/*p二NULL,即第i個元素的前驅(qū)不存在(設(shè)頭結(jié)點為第1個元素的前驅(qū))*/returnERROR;s=(DuLinkList)malloc(sizeof(DuLNode));if(!s)

returnOVERFLOW;s->data=e;s->prior二p;/*在第i-1個元素之后插入*/s->next二p->next;p->next->prior=s;p->next=s;returnOK;}StatusListDelete(DuLinkListL,inti,ElemType*e){/*刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素，i的合法值為1<i<表長*/DuLinkListp;if(i<1)/*i值不合法*/returnERROR;p二GetElemP(L,i);/*在L中確定第i個元素的位置指針p*/if(!p)/*p二NULL,即第i個元素不存在*/returnERROR;*e=p->data;p->prior->next二p->next;p->next->prior二p->prior;free(p);returnOK;}voidListTraverse(DuLinkListL,void(*visit)(ElemType)){/*由雙鏈循環(huán)線性表L的頭結(jié)點出發(fā)，正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit()*/DuLinkListp二L->next;/*p指向頭結(jié)點*/while(p!二L){visit(p->data