數(shù)據(jù)結(jié)構(gòu)之線性表課件(參考版)
2024-09-04 09:01本頁面
【正文】 12. 試編寫一個在循環(huán)雙向鏈表中進(jìn)行刪除操作的算法，要求刪除的結(jié)點是指定結(jié)點 p的前趨結(jié)點。 10. 已知一個單循環(huán)鏈表，編寫一個函數(shù)，將所有箭頭方向取反。 8. 與上題相同的單鏈表，設(shè)計一個函數(shù)，將此單鏈表分成兩個單鏈表，要求其中一個仍以原表頭指針head1作表頭指針，表中順序包括原線性表的第一、三等奇數(shù)號結(jié)點；另一個鏈表以 head2為表頭指針，表中順序包括原單鏈表第二、四等號結(jié)點。 6. 已知一個單鏈表，編寫一個函數(shù)將此單鏈表復(fù)制一個拷貝。 4. 已知一個單鏈表，編寫一個函數(shù)從此單鏈表中刪除自第 i個元素起的 length個元素。 2. 設(shè)計一個函數(shù)，查找單鏈表中數(shù)值為 x的結(jié)點。 5. 寫出在單鏈表中的 p所指結(jié)點之前插入一個 s所指結(jié)點的操作。 2. 試分析單鏈表與雙鏈表的優(yōu)缺點。 } else printf(“未找到 !\n”)。 pnext=s。 } else { snext=pnext。 snext=NULL。 p=pnext。amp。 /*查找第 i個結(jié)點 ， 由 p指向 */ j=1。 head=s。 if(i==0) /*如 i=0,將 s所指結(jié)點插入到表頭后返回 */ { snext=head。 s=(dnode *)malloc(sizeof(dnode))。 例3.3算法 void insert(dnode *head,int i,x) { dnode *s,*p。 } 例 ?給出在雙鏈表中第 i個結(jié)點 (i≥0)之后插入一個元素為 x的結(jié)點的函數(shù)。 pnext=head2。 q=head2。 p=head1。 ?解：先找到兩個表的表尾，將 head2放入鏈表head1的表尾，然后將 head1放入原 head2鏈表的表尾。 head=p。 q=r。 qnext=p。 q=pnext。 例3.1算法 void invert(node *head) { node *p,*q,*r。 ?基本思想：從頭到尾遍歷單鏈表 L，并設(shè)置 3個附加指針 p、 q、 r, p指向當(dāng)前處理的結(jié)點， q指向 p的后繼， r指向 q的后繼， q、 r的作用是為了防止倒置指針時，下一個結(jié)點丟失而設(shè)置的。 A,B后移。 把多項式 B(x)加到 A(x)中。 Struct pnode *next。 4654)( 2345 ????? xxxxxAxxxxxB ???? 245 623)(結(jié)點的定義如下： typedef struct pnode { real coef。 設(shè)一個一元多項式為 4 0 6 1 5 4 0 1 2 3 4 5 6 4654)( 2345 ????? xxxxxA? 2. 用 單鏈表表 示一元多項式 將單鏈表的每個結(jié)點對應(yīng)著一元多項式中的一個非零項，它由三個域組成，分別表示非零項的系數(shù)、指數(shù)和指向下一個結(jié)點的指針。 p ① ② 4654)( 2345 ????? xxxxxAxxxxxB ???? 245 623)( 多項式的加法 運算規(guī)則 ? 將二個一元多項式中所有指數(shù)相同項的系數(shù)相加，相加后，若和不為零，則構(gòu)造 “和多項式”中的一項； ? 若和為零，則“和多項式”中無此項； ? 所有指數(shù)不相同的項均考貝到“和多項式”中。 (pnext) prior=pprior。 pprior=q。 qnext=p。 } Dblinklist。 struct dbnode *prior。 ?雙鏈表結(jié)構(gòu)是一種對稱結(jié)構(gòu)，設(shè)指針 p指向雙鏈表的某一結(jié)點，則雙鏈表的對稱性可用下式來表示： p=(pprior)next=(pnext)prior 即結(jié)點 *p的地址存放在其前趨結(jié)點 *(pprior)的后繼指針域中，又存放在它的后繼結(jié)點 *(pnext)的前趨指針域中。 pr i or da t a next ?如果循環(huán)鏈表的結(jié)點再采用雙向指針，就成為 雙向循環(huán)鏈表 。 r e a r r e a r 雙向鏈表 ?雙向鏈表中每個結(jié)點除了有向后指針外，還有指向其前一個結(jié)點的指針，這樣形成的鏈表中有兩條不同方向的鏈，因此從某一結(jié)點均可向兩個方向訪問。 delete_seqlist(josephus_seq, s1+1) } 2. 帶尾指針的循環(huán)鏈表 ?另一種方法是不設(shè)頭指針而改設(shè)尾指針，這樣無論是找頭結(jié)點還是尾結(jié)點都很方便。 w=josephus_seqdata[s1]。 i0。 ? Int josephus_seqlist( pseqlist josephus_sq,int s,m) { /*順序存儲在 josephus_sq中，從第 s個元素開始 s1=s1。 struct Jnode *next。 ?結(jié)點定義為： Typedef struct Jnode { int no。 首先給定一正整數(shù) m，從第 1個人開始(順時針），槍斃第 m個人，之后，以該人的密碼作為 m的新值，繼續(xù)下去 ,…… 基本思想： 首先建立一個帶頭結(jié)點，有 n個結(jié)點的循環(huán)鏈表，頭指針為 head。 ?例：約瑟夫（ Josephus）問題。 ?空表頭結(jié)點除指針以外的數(shù)據(jù)域是沒有用的，但為了將此結(jié)點與一般結(jié)點相區(qū)別，常常是將其賦以一個特別的數(shù)據(jù)，以與一般結(jié)點相區(qū)別。 head 1. 帶頭結(jié)點的循環(huán)鏈表 ?通常在循環(huán)鏈表的表頭結(jié)點前面再加一個空結(jié)點 ,也叫空表頭結(jié)點。 循環(huán)鏈表 ?循環(huán)鏈表（ circular linked list）是一種首尾相接的鏈表，將單鏈表表尾結(jié)點原來的空指針改為指向表頭結(jié)點，就成為循環(huán)鏈表。 ?例： L=（ a， b， c， d， e， f）， 0
法律信息相關(guān)推薦
鄂ICP備17016276號-1