線性表(C)循環(huán)鏈?zhǔn)酱鎯φn件

2.5線性表的其它存儲方法循環(huán)鏈表La1ai-1an∧aip將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針改為指向頭結(jié)點(diǎn)，構(gòu)成單循環(huán)鏈表，簡稱循環(huán)鏈表。2.5線性表的其它存儲方法循環(huán)鏈表L空循環(huán)鏈表La1ai-1anai非空循環(huán)鏈表循環(huán)鏈表是否為空的條件是：L->next==L單鏈表是否為空的條件是：L->next==NULLL->next==L為真L->next!=L為真La1ai-1anai2.5線性表的其它存儲方法循環(huán)鏈表——插入xspxspxsp循環(huán)鏈表的插入操作與單鏈表的插入操作相同La1ai-1ai+1ai2.5線性表的其它存儲方法循環(huán)鏈表——刪除p循環(huán)鏈表的刪除操作與單鏈表的刪除操作相同anqvoidxhDelete(LinkListL,inti,ElemType&x){/*讓p指向第i-1個(gè)結(jié)點(diǎn)*/p=L;j=0;while(p->next->next!=L&&j<i-1){p=p->next;j++;}

if(p->next->next==L&&j<i-1||j>i-1)

printf(“位置異?！?;else{q=p->next;x=q->data;p->next=q->next;deleteq;}}2.5線性表的其它存儲方法循環(huán)鏈表——刪除與單鏈表的刪除操作相比，差別是什么？i的取值范圍[1,n]i>n或i<1如何查找開始結(jié)點(diǎn)和尾結(jié)點(diǎn)？2.5線性表的其它存儲方法循環(huán)鏈表La1ai-1anai開始結(jié)點(diǎn)：L->next尾結(jié)點(diǎn)：將單鏈表掃描一遍，時(shí)間為O(n)有沒有更簡單的方法？reara1ai-1anai開始結(jié)點(diǎn)：rear->next->next終端結(jié)點(diǎn)：rear2.5線性表的其它存儲方法循環(huán)鏈表帶尾指針的循環(huán)鏈表一個(gè)存儲結(jié)構(gòu)設(shè)計(jì)得是否合理，取決于基于該存儲結(jié)構(gòu)的運(yùn)算是否方便，時(shí)間性能是否提高。既方便找頭又方便找尾雙鏈表2.5線性表的其它存儲方法如何求結(jié)點(diǎn)p的直接前驅(qū)，時(shí)間性能？La1ai-1anaip為什么可以快速求得結(jié)點(diǎn)p的后繼？如何快速求得結(jié)點(diǎn)p的前驅(qū)？雙鏈表：在單鏈表的每個(gè)結(jié)點(diǎn)中再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。雙鏈表結(jié)點(diǎn)結(jié)構(gòu)：priordatanextdata：數(shù)據(jù)域，存儲數(shù)據(jù)元素；prior：指針域，存儲該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)地址；next：指針域，存儲該結(jié)點(diǎn)的后繼結(jié)點(diǎn)地址。2.5線性表的其它存儲方法typedefstructDulNode{ElemTypedata;structDulNode*prior,*next;}DulNode,*DuLinkList;

2.5線性表的其它存儲方法雙鏈表啟示？時(shí)空權(quán)衡——空間換取時(shí)間priordatanext定義結(jié)點(diǎn)結(jié)構(gòu)：雙向鏈表的初始化/*初始化函數(shù)*/intinitDLinkList(DuLinkList&L){ L=newDulNode;//申請頭結(jié)點(diǎn)

if(L==NULL){ printf("申請空間失??！\n"); exit(0); } L->next=L->prior=L; return1;}空表L雙鏈表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;2.5線性表的其它存儲方法ai-1ai操作接口：

voidduInsert(DuLinkListL,inti,ElemTypex);

pxs注意指針修改的相對順序intinsDLinkList(DuLinkListL,inti,ElemTypex){ DuLinkListp=L;//工作指針指向頭結(jié)點(diǎn)

DuLinkListnewp;//用于指向新結(jié)點(diǎn)

intj=0;//計(jì)數(shù)器置0 //尋找插入位置，使得工作指針p指向第i-1個(gè)結(jié)點(diǎn)

while(p->next!=L&&j<i-1){p=p->next;j++;}

if(p->next==L&&j<i-1||j>i-1){ printf("位置不合理！\n"); return0; }//接后

按后繼方向，尋找插入位置//插入

newp=newDulNode; newp->data=x;newp->next=p->next;newp->prior=p; p->next->prior=newp; p->next=newp; return1;}按后繼方向?qū)ふ乙獎h除的結(jié)點(diǎn)intdelDLinkList(DuLinkListL,inti,ElemType&x){DuLinkListp=L;//工作指針指向頭結(jié)點(diǎn)

DuLinkListq;//指向被刪除的結(jié)點(diǎn)

intj=0;//計(jì)數(shù)器置0 //尋找刪除位置，使得工作指針p指向第i-1個(gè)結(jié)點(diǎn)

while(p->next->next!=L&&j<i-1){p=p->next;j++;}

if(p->next->next==L&&j<i-1||j>i-1){ printf("位置不合