數(shù)據(jù)結(jié)構(gòu)CC++循環(huán)鏈表課件

例3.1有一個(gè)單鏈表L(至少有一個(gè)結(jié)點(diǎn))，其頭結(jié)點(diǎn)指針為head，編寫一個(gè)函數(shù)將L逆置，即最后一個(gè)結(jié)點(diǎn)變成第1個(gè)結(jié)點(diǎn)，原來(lái)倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn)……如此等等。解：本題采用的算法是，從頭到尾遍歷單鏈表L，并設(shè)置3個(gè)附加指針p、q、r,p指向當(dāng)前處理的結(jié)點(diǎn)，q指向p的下一個(gè)結(jié)點(diǎn)，r指向q的下一個(gè)結(jié)點(diǎn)，q、r的作用是為了防止倒置指針時(shí)，下一個(gè)結(jié)點(diǎn)的丟失而設(shè)置的，有了這三個(gè)指針，就可以方便地實(shí)現(xiàn)指針的倒置。最后將第一個(gè)結(jié)點(diǎn)的next域置為NULL，并將頭指針指向最后一個(gè)結(jié)點(diǎn)，這樣達(dá)到了本題的要求。voidinvert(linklisthead){linklistp,q,r;p=head;q=p->next;while(q!=NULL)/*沒(méi)有后繼時(shí)停止*/{r=q->next;q->next=p;p=q;q=r;}head->next=NULL;head=p;}typedefstructnode{datatypedata;structnode*next;}*linklist;堆棧的最簡(jiǎn)單的表示方法是采用一維數(shù)組，為形象起見(jiàn)，一般在圖中將堆棧畫成豎直的。設(shè)數(shù)組名為data，其下標(biāo)的下界為0，上界為n。一般需用一個(gè)變量top記錄當(dāng)前棧頂?shù)南聵?biāo)值，top也叫做棧指針。topADCB3642105data本例中top=4在C語(yǔ)言中通常用以下方式定義一個(gè)順序棧結(jié)構(gòu)體：#defineN30Typedefstructstack{datatypedata[N];Inttop;}sqstack;3.2鏈表應(yīng)用#defineN30Typedefstructstack{datatypedata[N];Inttop;}sqstack;voidpop(sqstack*p){if(p->top==-1)printf(“空棧!\n”);/*棧為空顯示相應(yīng)的信息*/else{x=p->data[p->top];(p->top)--;/*棧頂位置下移*/}returnx;}2.出棧（Pop）出棧運(yùn)算時(shí)，先將棧頂?shù)脑刂蒂x給某個(gè)變量，以備后面的運(yùn)算應(yīng)用；然后棧頂指針減1，將棧頂位置下移。假設(shè)已指定的變量為x，則出棧的函數(shù)如下：鏈堆棧是棧的鏈接存儲(chǔ)表示，它是只允許在表頭進(jìn)行插入和刪除運(yùn)算的單鏈表。它與普通的單鏈表沒(méi)有什么不同，只是將頭指針head改稱為棧頂指針top。鏈堆棧鏈堆棧的入棧算法在棧頂指針是top的鏈堆棧中插入一個(gè)值為x的結(jié)點(diǎn)的算法：voidpush(linklisttop,datatypex){linklists;s=newnode;/*建立一個(gè)結(jié)點(diǎn)指針*/s->data=x;s->next=top;top=s;}3.3循環(huán)鏈表與雙向鏈表循環(huán)鏈表（circularlinkedlist）是一種首尾相接的鏈表，將單鏈表表尾結(jié)點(diǎn)原來(lái)的空指針改為指向表頭結(jié)點(diǎn)，就成為循環(huán)鏈表。循環(huán)鏈表并不多占存儲(chǔ)單元，但從循環(huán)鏈表的任一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問(wèn)到此鏈表的每一個(gè)結(jié)點(diǎn)，因?yàn)楫?dāng)訪問(wèn)到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。一、循環(huán)鏈表例3.2有兩個(gè)循環(huán)單鏈表，頭指針?lè)譃閔ead1和head2，編寫函數(shù)將鏈表head2鏈接到鏈表head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。解：先分別找到兩個(gè)鏈表的表尾，將head2放入鏈表head1的表尾，將兩個(gè)鏈表鏈接起來(lái)，然后將head1放入原h(huán)ead2鏈表的表尾，構(gòu)成新的循環(huán)鏈表。例3.2算法link(linklisthead1,head2){linklistp,q;p=head1;while(p->next!=head1)p=p->next;q=head2;while(q->next!=head2)q=q->next;p->next=head2;q->next=head1;}2.帶尾指針的循環(huán)鏈表另一種方法是不設(shè)頭指針而改設(shè)尾指針，這樣無(wú)論是找頭結(jié)點(diǎn)還是尾結(jié)點(diǎn)都很方便。因?yàn)槲步Y(jié)點(diǎn)由尾指針rear來(lái)指示，則頭結(jié)點(diǎn)的位置是rear->next->next。二、雙向鏈表雙向鏈表中每個(gè)結(jié)點(diǎn)除了有向后指針外，還有指向其前一個(gè)結(jié)點(diǎn)的指針，這樣形成的鏈表中有兩條不同方向的鏈，因此從某一結(jié)點(diǎn)均可向兩個(gè)方向訪問(wèn)。雙鏈表的結(jié)點(diǎn)形式為：其中鏈域prior和next分別指向本結(jié)點(diǎn)的直接前趨和直接后繼結(jié)點(diǎn)。如果循環(huán)鏈表的結(jié)點(diǎn)再采用雙向指針，就成為雙向循環(huán)鏈表。1.雙鏈表的插入設(shè)要在p所指結(jié)點(diǎn)的前面插入一個(gè)新結(jié)點(diǎn)*q，則需要修改4個(gè)指針：q->prior=p->prior;q->next=p;(p->prior)->next=q;p->prior=q;2.雙鏈表的刪除設(shè)p指向待刪除的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)步驟為：(p->prior)->next=p->next;(p->next)->prior=p->prior;這兩個(gè)語(yǔ)句的執(zhí)行順序可以顛倒，執(zhí)行這兩個(gè)語(yǔ)句之后，可調(diào)用deletep,將*p結(jié)點(diǎn)釋放。返回3.4表示稀疏矩陣的十字鏈表在十字鏈表中，矩陣的每個(gè)非零元素對(duì)應(yīng)著一個(gè)含有五個(gè)域的結(jié)點(diǎn)，這五個(gè)域分別為該非零元素在稀疏矩陣中的行號(hào)、列號(hào)、元素的數(shù)值以及兩個(gè)指針，其中一個(gè)指針指向同一列的下一個(gè)非零元素的結(jié)點(diǎn)，另一個(gè)指針指向同一行的右邊一個(gè)非零元素的結(jié)點(diǎn)。例：稀疏矩陣M