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

1、有一個(gè)單鏈表L(至少有一個(gè)結(jié)點(diǎn))，其頭結(jié)點(diǎn)指針為head，編寫(xiě)一個(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á)到了本題的要求。 void invert( linklist head) linklist p, q, r; p=head; q

2、=p-next; while(q!=NULL) /*沒(méi)有后繼時(shí)停止*/ r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; typedef struct node datatype data; struct node *next;*linklist;堆棧的最簡(jiǎn)單的表示方法是采用一維數(shù)組，為形象起見(jiàn)，一般在圖中將堆棧畫(huà)成豎直的 。設(shè)數(shù)組名為data，其下標(biāo)的下界為0，上界為n。一般需用一個(gè)變量top記錄當(dāng)前棧頂?shù)南聵?biāo)值，top也叫做棧指針。topADCB3642105data本例中top=4 在C語(yǔ)言中通常用以下方式定義一個(gè)順序棧結(jié)構(gòu)體：#

3、define N 30Typedef struct stackdatatype data N ; Int top;sqstack;入棧push） 入棧的主要操作是先將棧頂指針加1；然后將入棧元素放到棧頂指針?biāo)甘鞠轮档奈恢蒙?。設(shè)用指針P表示堆棧，入棧的元素值為x，則可得到入棧函數(shù)如下：#define N 30Typedef struct stackdatatype data N ; Int top;sqstack;void push ( sqstack *p, datatype x) if (p-top=N-1) printf(“棧溢出!n”); /*顯示棧滿信息*/ else (p-top)

4、+; p-datap-top=x; #define N 30Typedef struct stackdatatype data N ; Int top;sqstack;void pop (sqstack *p) if (p-top= -1) printf(“空棧!n”); /*棧為空顯示相應(yīng)的信息*/ else x=p-datap-top; ( p- top)-; /*棧頂位置下移*/ return x; 2. 出棧Pop）出棧運(yùn)算時(shí)，先將棧頂?shù)脑刂蒂x給某個(gè)變量，以備后面的運(yùn)算應(yīng)用；然后棧頂指針減1，將棧頂位置下移。假設(shè)已指定的變量為x，則出棧的函數(shù)如下： 鏈堆棧是棧的鏈接存儲(chǔ)表示，它是只允

5、許在表頭進(jìn)行插入和刪除運(yùn)算的單鏈表。它與普通的單鏈表沒(méi)有什么不同，只是將頭指針head改稱為棧頂指針top。 top 在棧頂指針是top的鏈堆棧中插入一個(gè)值為x的結(jié)點(diǎn)的算法：void push (linklist top, datatype x) linklist s; s=new node ; /*建立一個(gè)結(jié)點(diǎn)指針*/ s-data=x; s-next=top; top=s; int pop(linklist top) int x; linklist p; if( top= = NULL) coutdata; p=top; top=top-next; delete p; return x;

6、循環(huán)鏈表circular linked list是一種首尾相接的鏈表，將單鏈表表尾結(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)。 head 有兩個(gè)循環(huán)單鏈表，頭指針?lè)譃閔ead1和head2，編寫(xiě)函數(shù)將鏈表head2鏈接到鏈表head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。解：先分別找到兩個(gè)鏈表的表尾，將head2放入鏈表head1的表尾，將兩個(gè)鏈表鏈接起來(lái)，然后將head1放入原h(huán)ead2鏈表的表尾，構(gòu)成新的循環(huán)鏈表。 head1 a1 an a2 head2

7、 b1 bn b2 link(linklist head1,head2) linklist p, 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; 通常在循環(huán)鏈表的表頭結(jié)點(diǎn)前面再加一個(gè)空結(jié)點(diǎn),也叫空表頭結(jié)點(diǎn)。表空時(shí)空表頭結(jié)點(diǎn)的指針指向其本身，如下面的圖所示為空循環(huán)鏈表。 空表頭結(jié)點(diǎn)除指針以外的數(shù)據(jù)域是沒(méi)有用的，但為了將此結(jié)點(diǎn)與一般結(jié)點(diǎn)相區(qū)別，常常是將其賦以一個(gè)特別的數(shù)據(jù)，以與一般結(jié)點(diǎn)相區(qū)別。 head 另一種方法是不設(shè)頭指針

8、而改設(shè)尾指針，這樣無(wú)論是找頭結(jié)點(diǎn)還是尾結(jié)點(diǎn)都很方便。因?yàn)槲步Y(jié)點(diǎn)由尾指針rear來(lái)指示，則頭結(jié)點(diǎn)的位置是rear-next-next。 rear rear 雙向鏈表中每個(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)。 prior data next 如果循環(huán)鏈表的結(jié)點(diǎn)再采用雙向指針，就成為雙向循環(huán)鏈表。 head 雙鏈表較單鏈表雖然要多占用一些存儲(chǔ)單元，但對(duì)其插入和刪除操作以及查找結(jié)點(diǎn)的前趨和后繼都非常方便。 雙鏈表結(jié)構(gòu)是一種對(duì)稱結(jié)

9、構(gòu)，設(shè)指針p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表的對(duì)稱性可用下式來(lái)表示： p=(p-prior)-next=(p-next)-prior 即結(jié)點(diǎn)*p的地址既存放在其前趨結(jié)點(diǎn) *(p-prior)的后繼指針域中，又存放在它的后繼結(jié)點(diǎn)*(p-next)的前趨指針域中。 設(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; p q 設(shè)p指向待刪除的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)步驟為：(p-prior) -next=p-next; (p-next) -prior=p-prior; 這兩個(gè)語(yǔ)句的執(zhí)行

10、順序可以顛倒，執(zhí)行這兩個(gè)語(yǔ)句之后，可調(diào)用delete p,將*p結(jié)點(diǎn)釋放。 p 前往在十字鏈表中，矩陣的每個(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)。 行號(hào) 列號(hào) 數(shù)值 向右指針 向下指針 將每行的非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，又將每列的非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，就構(gòu)成了十字形的鏈接結(jié)構(gòu)。對(duì)于每行、每列的循環(huán)鏈表都有一個(gè)空表頭結(jié)點(diǎn)，以利于元素的插入和刪除運(yùn)算。這些空表頭結(jié)點(diǎn)的行號(hào)、列號(hào)都標(biāo)成零，以便和其它結(jié)點(diǎn)相區(qū)別。整個(gè)十字鏈表有一個(gè)總的空表頭結(jié)點(diǎn)，在一般結(jié)點(diǎn)標(biāo)以行號(hào)、列號(hào)之處，此結(jié)點(diǎn)是標(biāo)出矩陣的行數(shù)m和列數(shù)n。有一個(gè)指針HM指向這個(gè)總的空表頭結(jié)點(diǎn)。 例：稀疏矩陣M及其對(duì)應(yīng)的十字鏈表如圖所示。60000570000403009008M H1 H2 H3 H4 H5 HM H5 H4 H3 H2 H1 5 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 8 1 4 9 0 0 0 0 2 3 -3 0 0 5 4 -6 0 0 3 1 4 4 2 7 4 3 -5