數(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)，原來倒數(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á)到了本題的要求。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第1頁!voidinvert(linklisthead){linklistp,q,r;p=head;q=p->next;while(q!=NULL)/*沒有后繼時(shí)停止*/{r=q->next;q->next=p;p=q;q=r;}head->next=NULL;head=p;}typedefstructnode{datatypedata;structnode*next;}*linklist;數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第2頁!堆棧的最簡單的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的。設(shè)數(shù)組名為data，其下標(biāo)的下界為0，上界為n。一般需用一個(gè)變量top記錄當(dāng)前棧頂?shù)南聵?biāo)值，top也叫做棧指針。topADCB3642105data本例中top=4在C語言中通常用以下方式定義一個(gè)順序棧結(jié)構(gòu)體：#defineN30Typedefstructstack{datatypedata[N];Inttop;}sqstack;3.2鏈表應(yīng)用數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第3頁!#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ù)如下：數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第4頁!鏈堆棧的入棧算法在棧頂指針是top的鏈堆棧中插入一個(gè)值為x的結(jié)點(diǎn)的算法：voidpush(linklisttop,datatypex){linklists;s=newnode;/*建立一個(gè)結(jié)點(diǎn)指針*/s->data=x;s->next=top;top=s;}數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第5頁!3.3循環(huán)鏈表與雙向鏈表循環(huán)鏈表（circularlinkedlist）是一種首尾相接的鏈表，將單鏈表表尾結(jié)點(diǎn)原來的空指針改為指向表頭結(jié)點(diǎn)，就成為循環(huán)鏈表。循環(huán)鏈表并不多占存儲(chǔ)單元，但從循環(huán)鏈表的任一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問到此鏈表的每一個(gè)結(jié)點(diǎn)，因?yàn)楫?dāng)訪問到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。一、循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第6頁!例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;}數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第7頁!2.帶尾指針的循環(huán)鏈表另一種方法是不設(shè)頭指針而改設(shè)尾指針，這樣無論是找頭結(jié)點(diǎn)還是尾結(jié)點(diǎn)都很方便。因?yàn)槲步Y(jié)點(diǎn)由尾指針rear來指示，則頭結(jié)點(diǎn)的位置是rear->next->next。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第8頁!如果循環(huán)鏈表的結(jié)點(diǎn)再采用雙向指針，就成為雙向循環(huán)鏈表。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第9頁!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;數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第10頁!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)。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第11頁!例：稀疏矩陣M及其對(duì)應(yīng)的十字鏈表如圖所示。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第12頁!空表頭結(jié)點(diǎn)的結(jié)構(gòu)因各列、各行的空表頭結(jié)點(diǎn)中的行號(hào)和列號(hào)都是零，且每列空表頭結(jié)點(diǎn)只用到向下指針，每行空表頭結(jié)點(diǎn)只用到向右指針，故可將這組空表頭結(jié)點(diǎn)合用。由于數(shù)值域也沒有用，可將空表頭結(jié)點(diǎn)的數(shù)值域改為一個(gè)指針域，將各個(gè)空表頭結(jié)點(diǎn)也鏈接成一個(gè)循環(huán)鏈表。返回?cái)?shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第13頁!二、堆棧的運(yùn)算

入棧（push）入棧的主要操作是先將棧頂指針加1；然后將入棧元素放到棧頂指針?biāo)甘鞠轮档奈恢蒙?。設(shè)用指針P表示堆棧，入棧的元素值為x，則可得到入棧函數(shù)如下：#defineN30Typedefstructstack{datatypedata[N];Inttop;}sqstack;voidpush(sqstack*p,datatypex){if(p->top==N-1)printf(“棧溢出!\n”);/*顯示棧滿信息*/else {(p->top)++;p->data[p->top]=x;}}數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第14頁!鏈堆棧是棧的鏈接存儲(chǔ)表示，它是只允許在表頭進(jìn)行插入和刪除運(yùn)算的單鏈表。它與普通的單鏈表沒有什么不同，只是將頭指針head改稱為棧頂指針top。鏈堆棧數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第15頁!intpop(linklisttop){intx;linklistp;if(top==NULL)cout<<“棧為空!”;else{x=top->data;p=top;top=top->next;deletep;returnx;}}

鏈堆棧的出棧算法數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第16頁!例3.2有兩個(gè)循環(huán)單鏈表，頭指針分為head1和head2，編寫函數(shù)將鏈表head2鏈接到鏈表head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。解：先分別找到兩個(gè)鏈表的表尾，將head2放入鏈表head1的表尾，將兩個(gè)鏈表鏈接起來，然后將head1放入原h(huán)ead2鏈表的表尾，構(gòu)成新的循環(huán)鏈表。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第17頁!1.帶頭指針的循環(huán)鏈表通常在循環(huán)鏈表的表頭結(jié)點(diǎn)前面再加一個(gè)空結(jié)點(diǎn),也叫空表頭結(jié)點(diǎn)。表空時(shí)空表頭結(jié)點(diǎn)的指針指向其本身，如下面的圖所示為空循環(huán)鏈表。空表頭結(jié)點(diǎn)除指針以外的數(shù)據(jù)域是沒有用的，但為了將此結(jié)點(diǎn)與一般結(jié)點(diǎn)相區(qū)別，常常是將其賦以一個(gè)特別的數(shù)據(jù)，以與一般結(jié)點(diǎn)相區(qū)別。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第18頁!二、雙向鏈表雙向鏈表中每個(gè)結(jié)點(diǎn)除了有向后指針外，還有指向其前一個(gè)結(jié)點(diǎn)的指針，這樣形成的鏈表中有兩條不同方向的鏈，因此從某一結(jié)點(diǎn)均可向兩個(gè)方向訪問。雙鏈表的結(jié)點(diǎn)形式為：其中鏈域prior和next分別指向本結(jié)點(diǎn)的直接前趨和直接后繼結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第19頁!雙鏈表較單鏈表雖然要多占用一些存儲(chǔ)單元，但對(duì)其插入和刪除操作以及查找結(jié)點(diǎn)的前趨和后繼都非常方便。雙鏈表結(jié)構(gòu)是一種對(duì)稱結(jié)構(gòu)，設(shè)指針p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表的對(duì)稱性可用下式來表示：p=(p->prior)->next=(p->next)->prior即結(jié)點(diǎn)*p的地址既存放在其前趨結(jié)點(diǎn)*(p->prior)的后繼指針域中，又存放在它的后繼結(jié)點(diǎn)*(p->next)的前趨指針域中。數(shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第20頁!2.雙鏈表的刪除設(shè)p指向待刪除的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)步驟為：(p->prior)->next=p->next;(p->next)->prior=p->prior;這兩個(gè)語句的執(zhí)行順序可以顛倒，執(zhí)行這兩個(gè)語句之后，可調(diào)用deletep,將*p結(jié)點(diǎn)釋放。返回?cái)?shù)據(jù)結(jié)構(gòu)CC+循環(huán)鏈表共24頁，您現(xiàn)在瀏覽的是第21頁!將每行的非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，又將每列的非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，就構(gòu)成了十字形的鏈接結(jié)構(gòu)。對(duì)于每行、每列的循環(huán)鏈表都有一個(gè)空表頭結(jié)點(diǎn)