數(shù)據(jù)結(jié)構(gòu)第2章線性表雙鏈表及循環(huán)應(yīng)用

第2章線性表BasicSortingAlgorithms22.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表2.3.2單鏈表2.3.3雙鏈表2.3.4循環(huán)鏈表（1）雙鏈表的表示和實(shí)現(xiàn)雙鏈表的表示和實(shí)現(xiàn)3對(duì)于雙鏈表。采用類似于單鏈表的結(jié)點(diǎn)類型定義。雙鏈表中每個(gè)結(jié)點(diǎn)類型DLinkList定義如下：publicclassDLinkList{publicstringdata;//存放數(shù)據(jù)元素publicDLinkListprior;//指向前一個(gè)結(jié)點(diǎn)的字段publicDLinkListnext;//指向下一個(gè)結(jié)點(diǎn)的字段};說明：在C#語言中沒有明確的指針類型，類對(duì)象屬于引用類型，如DLinkList類中prior字段和next字段都是引用類型，它相當(dāng)于C/C++語言中的指針，本書將其稱為指針。（1）雙鏈表的表示和實(shí)現(xiàn)4采用一個(gè)類DLinkList來定義雙鏈表的基本運(yùn)算方法，其中dhead為雙鏈表的頭結(jié)點(diǎn)指針（本小節(jié)的所有算法均包含在DLinkListClass類中）：classDLinkListClass{…publicDLinkListhead=newDLinkList();//雙鏈表頭結(jié)點(diǎn)指針//線性表的基本運(yùn)算算法}由于雙鏈表中的每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向其后繼結(jié)點(diǎn)，另一個(gè)指向其前驅(qū)結(jié)點(diǎn)。因此，與單鏈表相比，在雙鏈表中訪問一個(gè)結(jié)點(diǎn)的前、后結(jié)點(diǎn)更方便。（2）建立雙鏈表—頭插法5采用頭插法建立雙鏈表的過程和采用頭插法建立單鏈表的過程相似，其算法如下：publicvoidCreateListF(string[]split)//由含有n個(gè)元素的數(shù)組split創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表dhead{DLinkLists;inti;dhead.next=null;//將頭結(jié)點(diǎn)的next字段置為nullfor(i=0;i<split.Length;i++)//循環(huán)建立數(shù)據(jù)結(jié)點(diǎn){s=newDLinkList();s.data=split[i];//創(chuàng)建數(shù)據(jù)結(jié)點(diǎn)ss.next=dhead.next;//將s結(jié)點(diǎn)插入到開始結(jié)點(diǎn)之前，頭結(jié)點(diǎn)之后if(dhead.next!=null)dhead.next.prior=s;dhead.next=s;s.prior=dhead;}}（2）建立雙鏈表—尾插法6采用尾插法建立雙鏈表的過程和采用尾插法建立單鏈表的過程相似，其算法如下：publicvoidCreateListR(string[]split)//由含有n個(gè)元素的數(shù)組split創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表dhead{DLinkLists,r;inti;r=dhead;//r始終指向尾結(jié)點(diǎn)，開始時(shí)指向頭結(jié)點(diǎn)for(i=0;i<split.Length;i++)//循環(huán)建立數(shù)據(jù)結(jié)點(diǎn){s=newDLinkList();s.data=split[i];//創(chuàng)建數(shù)據(jù)結(jié)點(diǎn)sr.next=s;//將s結(jié)點(diǎn)插入r結(jié)點(diǎn)之后s.prior=r;r=s;}r.next=null;//將尾結(jié)點(diǎn)的next字段置為null}7（3）線性表基本運(yùn)算在雙鏈表的實(shí)現(xiàn)雙鏈表的插入雙鏈表的刪除s.next=p.next;p.next.prior=s;s.prior=p;p.next=s;操作語句描述:xSbaP1）雙鏈表的插入8假設(shè)在雙鏈表中p結(jié)點(diǎn)之后插入一個(gè)s結(jié)點(diǎn)，其指針的變化過程如下：9在雙鏈表dhead中第i個(gè)位置上插入值為e的結(jié)點(diǎn)，其算法如下：publicboolListInsert(inti,stringe){intj=0;DLinkLists,p=dhead;//p指向頭結(jié)點(diǎn)，j設(shè)置為0while(j<i-1&&p!=null)//查找第i-1個(gè)結(jié)點(diǎn){j++;p=p.next;}if(p==null)//未找到第i-1個(gè)結(jié)點(diǎn)，返回falsereturnfalse;else//找到第i-1個(gè)結(jié)點(diǎn)p，在其后插入新結(jié)點(diǎn)s{s=newDLinkList();s.data=e;//創(chuàng)建新結(jié)點(diǎn)ss.next=p.next;//在p之后插入s結(jié)點(diǎn)10if(p.next!=null)//若p結(jié)點(diǎn)存在后繼結(jié)點(diǎn)，修改其前驅(qū)字段p.next.prior=s;s.prior=p;p.next=s;returntrue;}本算法的時(shí)間復(fù)雜度為O(n)，其中n表示單鏈表中的數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。bcaqq.next.prior=p;p.next=q.next;操作語句描述p.next=q.next;q.next.prior=p;2）雙鏈表的刪除11p假設(shè)刪除雙鏈表dhead中p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，其指針的變化過程如下：12在雙鏈表dhead中刪除第i個(gè)結(jié)點(diǎn)的算法如下：publicboolListDelete(inti,refstringe){intj=0;DLinkListq,p=dhead;//p指向頭結(jié)點(diǎn)，j設(shè)置為0while(j<i-1&&p!=null)//查找第i-1個(gè)結(jié)點(diǎn){j++;p=p.next;}if(p==null)//未找到第i-1個(gè)結(jié)點(diǎn)，返回falsereturnfalse;else//找到第i-1個(gè)結(jié)點(diǎn)p{q=p.next;if(q==null)//q指向第i個(gè)結(jié)點(diǎn)returnfalse;//當(dāng)不存在第i個(gè)結(jié)點(diǎn)時(shí)，返回false13e=q.data;p.next=q.next;//從雙鏈表中刪除q結(jié)點(diǎn)if(p.next!=null)//若p結(jié)點(diǎn)存在后繼結(jié)點(diǎn)，修改其前驅(qū)字段p.next.prior=p;q=null;//釋放q結(jié)點(diǎn)returntrue;}本算法的時(shí)間復(fù)雜度為O(n)，其中n表示單鏈表中的數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。雙鏈表的統(tǒng)計(jì)例【2.7】設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)一個(gè)雙鏈表對(duì)象L中值為x的結(jié)點(diǎn)個(gè)數(shù)，并分析算法的時(shí)間復(fù)雜度。14解：用p遍歷雙鏈表對(duì)象L中所有數(shù)據(jù)結(jié)點(diǎn)，用n累計(jì)值為x的結(jié)點(diǎn)個(gè)數(shù)。對(duì)應(yīng)算法如下：publicintCount(DLinkListClassL,stringx){DLinkListp=L.head.next;intn=0;while(p!=null){if(p.data==x)n++;p=p.next;}returnn;}本算法的時(shí)間復(fù)雜度為O(n)，其中n為雙鏈表中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。雙鏈表的特定刪除例【2.8】設(shè)計(jì)一個(gè)算法，刪除雙鏈表對(duì)象L中第一個(gè)值為x的結(jié)點(diǎn)，并分析算法的時(shí)間復(fù)雜度。15解：用q遍歷雙鏈表對(duì)象L的數(shù)據(jù)結(jié)點(diǎn)并查找第一個(gè)值為x的結(jié)點(diǎn)，若沒有找到這樣的結(jié)點(diǎn)，返回false；若找到這樣的結(jié)點(diǎn)q，讓p指向其前驅(qū)結(jié)點(diǎn)，再刪除q結(jié)點(diǎn)，并返回true。對(duì)應(yīng)算法如下：publicboolDelnode(DLinkListClassL,stringx){DLinkListq=L.head.next,p;while(q!=null&&q.data!=x)q=q.next;if(q==null)//沒有值為x的結(jié)點(diǎn)時(shí)，返回falsereturnfalse;else//存在值為x的結(jié)點(diǎn)時(shí)，返回true{p=q.prior;//p指向q的前驅(qū)結(jié)點(diǎn)if(q.next!=null)q.next.prior=p;16p.next=q.next;q=null;returntrue;}本算法的時(shí)間復(fù)雜度為O(n)，其中n表示單鏈表中的數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。172.3.4循環(huán)鏈表循環(huán)單鏈表循環(huán)雙鏈表（1）循環(huán)單鏈表18循環(huán)單鏈表的定義帶頭結(jié)點(diǎn)head的循環(huán)單鏈表如圖所示，表中尾結(jié)點(diǎn)的指針域不再為空，而是指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。其特點(diǎn)是：從表中任一結(jié)點(diǎn)出發(fā)，均可找到鏈表中的其他結(jié)點(diǎn)。heada1an……循環(huán)鏈表示意圖：head尾結(jié)點(diǎn)開始結(jié)點(diǎn)頭結(jié)點(diǎn)19循環(huán)單鏈表的類型定義與非循環(huán)單鏈表相同，每個(gè)結(jié)點(diǎn)的類型仍為L(zhǎng)inkList。循環(huán)單鏈表的類定義如下（本小節(jié)的所有算法均包含在CLinkListClass類中）：classCLinkListClass{…publicLinkListhead=newLinkList();//循環(huán)單鏈表頭結(jié)點(diǎn)指針//線性表的基本運(yùn)算算法}循環(huán)單鏈表的基本運(yùn)算實(shí)現(xiàn)算法與非循環(huán)單鏈表的相似，只是對(duì)表尾的判斷有所改變。例如，在循環(huán)單鏈表head中，判斷表尾結(jié)點(diǎn)p的條件是p.next==head。循環(huán)單鏈表的表示和實(shí)現(xiàn)循環(huán)單鏈表的統(tǒng)計(jì)例【2.9】有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表對(duì)象L，設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)值為x的結(jié)點(diǎn)個(gè)數(shù)。20解：用p遍歷整個(gè)循環(huán)單鏈表對(duì)象L的結(jié)點(diǎn)，用n累計(jì)data域值為x的結(jié)點(diǎn)個(gè)數(shù)。對(duì)應(yīng)算法如下：publicintCount(CLinkListClassL,ElemTypex){LinkListp=L.head.next;//p指向第1個(gè)數(shù)據(jù)結(jié)點(diǎn)，n置為0intn=0;while(p!=L.head)//遍歷循環(huán)單鏈表{if(p.data==x)n++;//找到值為x的結(jié)點(diǎn)后n增1p=p.next;//p指向下一個(gè)結(jié)點(diǎn)}returnn;}例【2.10】設(shè)計(jì)一個(gè)算法，將一個(gè)非循環(huán)單鏈表對(duì)象L變?yōu)橐粋€(gè)循環(huán)單鏈表。21解：遍歷單鏈表對(duì)象L的所有結(jié)點(diǎn)，找到尾結(jié)點(diǎn)p(滿足p.next==null)，將p結(jié)點(diǎn)的next改為指向頭結(jié)點(diǎn)。對(duì)應(yīng)算法如下：publicvoidChange(LinkListClassL){LinkListp=L.head;while(p.next!=null)//查找尾結(jié)點(diǎn)p=p.next;p.next=L.head;//改為循環(huán)單鏈表}循環(huán)單鏈表的合并例【2.11】有兩個(gè)循環(huán)單鏈表對(duì)象L1和L2，其元素分別為(a1,a2,...,an)和(b1,b2,...,bm)，其中n、m均大于1。設(shè)計(jì)一個(gè)算法，將L2合并到L1之后，即L1變?yōu)?a1,a2,...,an,b1,b2,...,bm)，合并后L1仍為循環(huán)單鏈表，并分析算法的時(shí)間復(fù)雜度。22解：通過遍歷讓p指向L1的尾結(jié)點(diǎn)，q指向L2的尾結(jié)點(diǎn)，將p結(jié)點(diǎn)的后繼結(jié)點(diǎn)改為L(zhǎng)2的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，最后通過q結(jié)點(diǎn)將歸并后的鏈表改為循環(huán)單鏈表。對(duì)應(yīng)算法如下：23publicvoidCom(refLinkListClassL1,LinkListClassL2){LinkListp=L1.head,q=L2.head;while(p.next!=L1.head)//p指向L1的尾結(jié)點(diǎn)p=p.next;p.next=L2.head.next;while(q.next!=L2.head)//q指向L2的尾結(jié)點(diǎn)q=q.next;q.next=L1;L2.head=null;//釋放L2的頭結(jié)點(diǎn)}本算法的時(shí)間復(fù)雜度為O(n+m)。（1）循環(huán)雙鏈表24循環(huán)雙鏈表的定義帶頭結(jié)點(diǎn)dhead的循環(huán)雙鏈表如圖所示，尾結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的prior域指向尾結(jié)點(diǎn)。其特點(diǎn)是：整個(gè)鏈表形成兩個(gè)環(huán)。從此，從表中任意結(jié)點(diǎn)出發(fā)，均可找到鏈表中的其他結(jié)點(diǎn)。循環(huán)鏈表示意圖：頭結(jié)點(diǎn)開始結(jié)點(diǎn)尾結(jié)點(diǎn)dhead.......a1a2an25循環(huán)雙鏈表的類型定義與非循環(huán)雙鏈表相同，每個(gè)結(jié)點(diǎn)的類型仍為DLinkList。循環(huán)雙鏈表的類定義如下（本小節(jié)的所有算法均包含在CDLinkListClass類中）：classCDLinkListClass{…publicDLinkListhead=newDLinkList();//循環(huán)單鏈表頭結(jié)點(diǎn)指針//線性表的基本運(yùn)算算法}循環(huán)雙鏈表的基本運(yùn)算實(shí)現(xiàn)算法與非循環(huán)雙鏈表的相似，只是對(duì)表尾的判斷有所改變。例如，在循環(huán)雙鏈表dhead中，判斷表尾結(jié)點(diǎn)p的條件是p.next==dhead。另外，可以從頭結(jié)點(diǎn)直接跳到尾結(jié)點(diǎn)。循環(huán)雙鏈表的表示和實(shí)現(xiàn)循環(huán)雙鏈表的合并例【2.12】有兩個(gè)循環(huán)雙鏈表對(duì)象L1和L2，其元素分別為(a1,a2,...,an)和(b1,b2,...,bm)，其中n、m均大于1。設(shè)計(jì)一個(gè)算法，將L2合并到L1之后，即L1變?yōu)?a1,a2,...,an,b1,b2,...,bm)，合并后L1仍為循環(huán)雙鏈表，并分析算法的時(shí)間復(fù)雜度。26解：用p指向L1的尾結(jié)點(diǎn)，q指向L2的尾結(jié)點(diǎn)，將p結(jié)點(diǎn)的后繼結(jié)點(diǎn)改為L(zhǎng)2的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，最后通過q結(jié)點(diǎn)將歸并后的鏈表改為循環(huán)雙鏈表。對(duì)應(yīng)算法如下：27publicvoidCom(refCDLinkListClassL1,CDLinkListClassL2){DLinkListp=L1.head.prior;//p指向L1的尾結(jié)點(diǎn)DLinkListq=L2.head.prior;//q指向L2的尾結(jié)點(diǎn)p.next=L2.dhead.next;L2.dhead.next.prior=p;q.next=L1;L1.prior=q;L2.dhead=null;//釋放L2的頭結(jié)點(diǎn)}本算法的時(shí)間復(fù)雜度為O(1)。說明：將本例算法和例2.11的算法進(jìn)行比較，可以看出循環(huán)雙鏈表的優(yōu)點(diǎn)。循環(huán)雙鏈表的查找例【2.13】有一個(gè)含有n個(gè)不相同元素的循環(huán)雙鏈表對(duì)象L，其中所有元素遞增排列。設(shè)計(jì)一個(gè)盡可能高效的算法，查找值為x的結(jié)點(diǎn)，找到后返回true，否則返回false，并分析算法的時(shí)間復(fù)雜度。28解：用p、q分別指向L的開始結(jié)點(diǎn)和尾結(jié)點(diǎn)，根據(jù)數(shù)據(jù)元素的遞增性分別從前向后和從后向前進(jìn)行比較，由比較結(jié)果確定是返回false或true，還是繼續(xù)。對(duì)應(yīng)算法如下：publicboolFindx(CDLinkListClassL,stringx){LinkListp=L.dhead.next;LinkListq=L.dhead.prior;while(p!=q){if(p.data==x)returntrue;elseif(x>p.data)p=p.next;elsereturnfalse;}29if(q.data==x)returntrue;elsereturnfalse;}本算法的時(shí)間復(fù)雜度為O(n)。例2：一元多項(xiàng)式的計(jì)算

(參見教材P58–60)討論：一元多項(xiàng)式的數(shù)學(xué)通式？用抽象數(shù)據(jù)類型如何描述它的定義？用C語言如何描述它的定義？如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？2.4應(yīng)用舉例30但當(dāng)多項(xiàng)式的次數(shù)很高且零系數(shù)項(xiàng)很多時(shí)，更適于用鏈表存儲(chǔ)。1.一元多項(xiàng)式的數(shù)學(xué)通式？機(jī)內(nèi)存儲(chǔ)方式？一般用順序存儲(chǔ)——a0a1a2…am-2am-1鏈?zhǔn)酱鎯?chǔ)am-1

em-1am-2

em-2…a0e0^或0.0-1…am-1

em-1

^a0e0通常設(shè)計(jì)兩個(gè)數(shù)據(jù)域（系數(shù)項(xiàng)和指數(shù)項(xiàng)）和一個(gè)指針域頭結(jié)點(diǎn)只存系數(shù)項(xiàng)（但零系數(shù)項(xiàng)也不能遺漏）coefexponlinkP2000(x)=1+3x1000+5x2000312.如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？3142810a^814－310106b^例：運(yùn)算規(guī)則：兩多項(xiàng)式中指數(shù)相同的項(xiàng)對(duì)應(yīng)系數(shù)相加，若和不為0,則構(gòu)成多項(xiàng)式c(=a+b)中的一項(xiàng)；a和b中所有指數(shù)不相同的項(xiàng)均應(yīng)拷貝到c中。鏈表a:鏈表b：32實(shí)現(xiàn)思路：依次比較Pa和Pb所指結(jié)點(diǎn)中的指數(shù)項(xiàng)，依Pa->expon=、<或>Pb->expon等情況，再?zèng)Q定是將兩系數(shù)域的數(shù)值相加（并判其和是否為0），還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表c中。3142810^aPa814-310106^bPb1114-310281