單鏈表鏈表的游標(biāo)類靜態(tài)鏈表循環(huán)鏈表多項(xiàng)式及其相加雙向鏈

1、。data linka0a1a2a3a4firstfree(a) 可利用存儲(chǔ)空間可利用存儲(chǔ)空間a0a2a1a3 freefirst(b) 經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu)經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu) class List; /鏈表類定義（復(fù)合方式） class ListNode /鏈表結(jié)點(diǎn)類 friend class List; /鏈表類為其友元類 private: int data; /結(jié)點(diǎn)數(shù)據(jù), ListNode * link; /結(jié)點(diǎn)指針 ; class List /鏈表類 private: ListNode *first , *current; /表頭指針;class List /鏈表類定義(

2、嵌套方式)private: class ListNode /嵌套鏈表結(jié)點(diǎn)類 public: int data; ListNode *link; ; ListNode *first , *current; /表頭指針public: /鏈表操作;鏈表類和鏈表結(jié)點(diǎn)類定義鏈表類和鏈表結(jié)點(diǎn)類定義( (繼承方式繼承方式) )class ListNode /鏈表結(jié)點(diǎn)類protected: int data; ListNode * link; ;class List : public class ListNode /鏈表類, 繼承鏈表結(jié)點(diǎn)類的數(shù)據(jù)和操作 private: ListNode *first , *

3、current; /表頭指針; 在在復(fù)合方式復(fù)合方式中，鏈表結(jié)點(diǎn)類中聲明鏈表中，鏈表結(jié)點(diǎn)類中聲明鏈表類是它的友元類，這樣可以類是它的友元類，這樣可以“奉獻(xiàn)奉獻(xiàn)”它它的私有成員給鏈表類。這種方式靈活。的私有成員給鏈表類。這種方式靈活。 在在嵌套方式嵌套方式中，鏈表結(jié)點(diǎn)類是鏈表類的中，鏈表結(jié)點(diǎn)類是鏈表類的私有成員，這樣限制了鏈表結(jié)點(diǎn)類的應(yīng)私有成員，這樣限制了鏈表結(jié)點(diǎn)類的應(yīng)用范圍。用范圍。 在在繼承方式繼承方式中，鏈表類聲明為鏈表結(jié)點(diǎn)中，鏈表類聲明為鏈表結(jié)點(diǎn)類的派生類，這在實(shí)現(xiàn)上是可行的。但類的派生類，這在實(shí)現(xiàn)上是可行的。但在邏輯上是有問題的，如在邏輯上是有問題的，如三角形三角形 is 多邊形（繼承

4、關(guān)系）多邊形（繼承關(guān)系） 鏈表鏈表 is 鏈表結(jié)點(diǎn)（顯然概念有誤）鏈表結(jié)點(diǎn)（顯然概念有誤） newnode-link = first ; first = newnode; firstnewnodenewnodefirst newnode-link = current-link; current-link = newnode；newnodecurrentnewnodecurrent newnode-link = current-link; current-link = newnode；newnodenewnodecurrentcurrent int List : Insert ( int x,

5、int i ) /在鏈表第 i ( 0) 號(hào)結(jié)點(diǎn)處插入新元素 x ListNode * p = current; current = first; for ( k = 0; k link; if ( current = NULL & first != NULL ) cout link = first; first = current = newnode; else /插在表中或末尾 newnode-link = current-link; current = current-link = newnode; return 1; 在單鏈表中刪除含在單鏈表中刪除含 的結(jié)點(diǎn)的結(jié)點(diǎn)ai-1ai-1aia

6、iai+1ai+1pq刪除前刪除后int List : Remove ( Type& x, int i ) /在鏈表中刪除第 i 號(hào)結(jié)點(diǎn), 通過x返回其值 ListNode *p, *q; if ( i = 0 ) /刪除表中第 0 號(hào)號(hào)結(jié)點(diǎn) q = first; current = first = first-link; else p = current; current = first; int k = 0; /找第 i- -1號(hào)結(jié)點(diǎn) while ( current != NULL & k link; k+; if ( current = NULL | current-link = NUL

7、L ) cout link; /重新鏈接 current = current-link = q-link; x = q-data; delete q; /刪除q return 1; 0an-1a0firstfirst0 newnode-link = p-link; p-link = newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp q = p-link; p-link = q-link; delete q; ( (非空表）非空表）( (空表）空表）firstfirstfirst0first0pqpq templ

8、ate class List;template class ListNode friend class List; Type data; /結(jié)點(diǎn)數(shù)據(jù) ListNode *link; /結(jié)點(diǎn)鏈接指針public: ListNode ( ) : link (NULL) /構(gòu)造函數(shù) ListNode ( Type item ) : data (item), link (NULL) ListNode (Type item, ListNode *next) : data (item), link (next) /以item和next建立一個(gè)新結(jié)點(diǎn) ListNode * getLink( ) return

9、 link; /取得結(jié)點(diǎn)的下一結(jié)點(diǎn)地址 Type getData ( ) return data; /取得結(jié)點(diǎn)中的數(shù)據(jù) void setLink ( ListNode * next ) link = next; /修改結(jié)點(diǎn)的link指針 void setData ( Type value ) data = value; /修改結(jié)點(diǎn)的data值;template class List /鏈表類private: ListNode *first, *current;/鏈表的表頭指針和當(dāng)前元素指針public: List ( Type value ) current = first = new Lis

10、tNode ( value ); List ( List& RL ); /復(fù)制構(gòu)造函數(shù) List ( ) MakeEmpty ( ); delete first; /析構(gòu)函數(shù) void MakeEmpty ( ); /將鏈表置為空表 int Length ( ) const; /計(jì)算鏈表的長(zhǎng)度 ListNode * Find ( Type value ); /搜索含數(shù)據(jù)value的元素并成為當(dāng)前元素 ListNode * Locate( int i ); /搜索第 i 號(hào)元素的地址并置為當(dāng)前元素 int GetData ( Type& value ); /取出表中當(dāng)前元素的值 int Inse

11、rt ( Type value ); /將value插在表中當(dāng)前元素后 int Remove (Type& value ); /將鏈表當(dāng)前元素刪去, 填補(bǔ)者為當(dāng)前元素 ListNode * Firster ( ) current = first; return first; /當(dāng)前指針置于表頭, 返回表頭結(jié)點(diǎn)地址 ListNode * First ( ) current = first-link; return current; /第一個(gè)結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn) ListNode * Next ( ); /下一個(gè)結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn) int NotNull ( ) return current != NULL

12、; int NextNotNull ( ) return current != NULL & current-link != NULL; ;template void List : MakeEmpty ( ) /刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn) ListNode *q; while ( first-link != NULL ) q = first-link; first-link = q-link;/將表頭結(jié)點(diǎn)后第一號(hào)結(jié)點(diǎn)從鏈中摘下 delete q; /釋放它 current = first; /當(dāng)前指針置于表頭結(jié)點(diǎn)firstqfirstfirstqqfirsta0a1a1a2a2a2c

13、urrenttemplate int List : Length ( ) const /求單鏈表的長(zhǎng)度 ListNode *p = first-link; /檢測(cè)指針 p 指示第一號(hào)結(jié)點(diǎn) int count = 0; while ( p != NULL ) /逐個(gè)結(jié)點(diǎn)檢測(cè) p = p-link; count+; return count;firstpa0a1a2c = 0firstpa0a1a2c = 1firstpa0a1a2c = 2firstpa0a1a2c = 3template ListNode * List : Find ( Type value ) /在鏈表中從頭搜索其數(shù)據(jù)值為v

14、alue的結(jié)點(diǎn) current = first-link; /當(dāng)前指針 current 指示第一號(hào)結(jié)點(diǎn) while ( current != NULL ) if ( current-data = value ) break; else current = current-link; return current; /搜索失敗時(shí)current = NULLtemplate ListNode *List : Locate ( int i ) /定位函數(shù)：返回表中第 i 號(hào)元素的地址, /i = 0為尋找表頭結(jié)點(diǎn)的地址 if ( i 0 ) return NULL; / i 值不合理 current

15、 = first; int k = 0; while ( current != NULL & k link; k+; /找第 i 號(hào)結(jié)點(diǎn) return current; /返回第 i 號(hào)結(jié)點(diǎn)地址或NULL /定位定位失敗時(shí)current = NULLtemplate int List : GetData ( Type& value ) /取出鏈表中當(dāng)前元素的值 if ( current = NULL | current = first ) return 0; else value = current-data; return 1; template int List : Insert ( Ty

16、pe value ) /將新元素value插入在鏈表中當(dāng)前結(jié)點(diǎn)后 if ( current = NULL ) return 0; ListNode *newnode = /創(chuàng)建結(jié)點(diǎn) new ListNode (value); newnode-link = current-link; current-link = newnode; current = newnode; return 1; /插入成功，函數(shù)返回1template int List : Remove ( Type& value) /將鏈表當(dāng)前元素刪去, 函數(shù)返回該元素 if ( current = first | current =

17、 NULL ) return 0; ListNode * p = first; /找前一結(jié)點(diǎn) while ( p-link != current ) p = p-link; p-link = current-link; /摘下被刪結(jié)點(diǎn) value = current-data; delete current; current = p-link; return 1;firstnewnodefirstnewnode00template void List : createListF(Type endTag) Type val; ListNode *node; first = new ListNod

18、e; /表頭結(jié)點(diǎn) cin val; while ( val != endTag ) node = new ListNode(val); node-link = first-link; first-link = node; /插入到表前端 cin val; current = first; last00newnodefirstnewnode00rrrrtemplate void List : createListR(Type endTag) Type val; ListNode *node, *last; first = new ListNode; /表頭結(jié)點(diǎn) cin val; current

19、= last = first; while ( val != endTag ) /last指向表尾 node = new ListNode(val); last-link = node; last = node; cin val; /插入到表末端 last-link = NULL; /表收尾 enum Boolean False, True ;template class List;template class ListIterator;template class ListNode /表結(jié)點(diǎn)表結(jié)點(diǎn)friend class List ;friend class ListIterator ;pu

20、blic: private: Type data; ListNode *link; template class List /鏈表類public: private: ListNode *first, *last;template class ListIterator private: const List & list; /引用已有鏈表 ListNode *current; /當(dāng)前結(jié)點(diǎn)指針public: ListIterator ( const List & l ) : list ( l ), current ( l.first ) /構(gòu)造函數(shù): 引用鏈表 ListNode * Firster

21、 ( ) current = first; return first; /當(dāng)前指針置于表頭, 返回表頭結(jié)點(diǎn)地址 Boolean NotNull ( ); /檢查當(dāng)前指針空否 Boolean NextNotNull ( ); /檢查鏈表中下一結(jié)點(diǎn)是否非空 ListNode *First ( ); /返回第一個(gè)結(jié)點(diǎn) ListNode *Next ( ); /返回鏈表當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址template Boolean ListIterator : NotNull ( ) /檢查鏈表中當(dāng)前元素是否非空 if ( current != NULL ) return True; else retur

22、n False;currentcurrent情況情況 1 返回返回True 情況情況 2 返回返回Falsetemplate Boolean ListIterator : NextNotNull ( ) /檢查鏈表中下一元素是否非空 if ( current != NULL & current-link != NULL ) return True; else return False; currentcurrent情況情況 1 返回返回True 情況情況 2 返回返回Falsetemplate ListNode* ListIterator : First ( ) /返回鏈表中第一個(gè)結(jié)點(diǎn)的地址

23、if ( list.first-link != NULL ) current = list.first-link; return ¤t-data; else current = NULL; return NULL; list.firstcurrent 約定鏈表中約定鏈表中沒有表頭結(jié)點(diǎn)沒有表頭結(jié)點(diǎn)template ListNode* ListIterator : Next ( ) /返回鏈表中當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址 if ( current != NULL & current-link != NULL ) current = current-link; return & curr

24、ent-data; else current = NULL; return NULL; currentcurrentint sum ( const List &L ) ListIterator li (L); /定義游標(biāo)對(duì)象, current 指向 li.first if ( ! li.NotNull ( ) ) return 0; /鏈表為空時(shí)返回0 int retval = li.First( )-data; /第一個(gè)元素 while ( li.nextNotNull ( ) ) /鏈表未掃描完 retval += li.Next( )-data; /累加 return retval;fi

25、rstfirstfirstconst int MaxSize = 100; /靜態(tài)鏈表大小template class StaticList;template class SListNode friend class StaticList; Type data; /結(jié)點(diǎn)數(shù)據(jù) int link; /結(jié)點(diǎn)鏈接指針template class StaticList SListNode elemMaxSize; int avil; /當(dāng)前可分配空間首地址template void StaticList : InitList ( ) elem0.link = -1; avil = 1; /當(dāng)前可分配空間

26、從 1 開始建 /立帶表頭結(jié)點(diǎn)的空鏈表 for ( int i = 1; i MaxSize-1; i+ ) elemi.link = i+1; /構(gòu)成空閑鏈接表 elemMaxSize-1.link = -1; /鏈表收尾template int StaticList : Find ( Type x ) int p = elem0.link; /指針 p 指向鏈表第一個(gè)結(jié)點(diǎn) while ( p != -1 ) if ( elemp.data = x) break; else p = elemp.link; /逐個(gè)結(jié)點(diǎn)檢測(cè)查找具有給定值的結(jié)點(diǎn) return p;template int Sta

27、ticList : Append ( Type x ) if ( avil = -1 ) return 0; /追加失敗 int q = avil; /分配結(jié)點(diǎn) avil = elemavil.link; elemq.data = x; elemq.link = -1; int p = 0; /查找表尾 while (elemp.link != -1) p = elemp.link; elemp.link = q; /追加 return 1; template int StaticList : Locate ( int i ) if ( i 0 ) return -1; /參數(shù)不合理 if (

28、 i = 0 ) return 0; int j = 0, p = elem0.link; while ( p != -1 & j i ) p = elemp.link; j+; /循鏈查找第 i 號(hào)結(jié)點(diǎn) return p; template int StaticList : Insert ( int i, Type x ) int p = Locate (i-1); if ( p = -1 ) return 0; /找不到結(jié)點(diǎn) int q = avil; /分配結(jié)點(diǎn) avil = elemavil.link; elemq.data = x; elemq.link = elemp.link;

29、/鏈入 elemp.link = q; return 1;template int StaticList : Remove ( int i ) int p = Locate (i-1); if ( p = -1 ) return 0; /找不到結(jié)點(diǎn) int q = elemp.link; /第 i 號(hào)結(jié)點(diǎn) elemp.link = elemq.link; elemq.link = avil; /釋放 avil = q; return 1; a0a1a2an-1firstan-1firsta1a0first( (空表空表) )( (非空表非空表) )template class CircList

30、;template class CircListNode friend class CircList ;public: CircListNode ( Type d = 0, CircListNode *next = NULL ) : data ( d ), link ( next ) /構(gòu)造函數(shù)private: Type data; /結(jié)點(diǎn)數(shù)據(jù) CircListNode *link; /鏈接指針 template class CircList private: CircListNode *first, *current, *last; /鏈表的表頭指針、當(dāng)前指針和表尾指針public: Cir

31、cList ( Type value ); CircList ( ); int Length ( ) const; int IsEmpty ( ) return first-link = first; CircListNode * Find ( Type value ); int getData ( Type& value ); CircListNode * Firster ( ) current = first; return current; CircListNode * First ( ) current = first-link; return current; CircListNod

32、e * Next ( ) current = current-link; return current; CircListNode * Prior ( ); int Insert ( Type value ); int Remove ( Type& value );搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 current current currentcurrent current current currentcurrenttemplate CircListNode * CircList : Find ( Type v

33、alue ) /在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn) current = first-link; while ( current != first & current-data != value ) current = current-link; return current;if ( first != NULL ) CircListNode *second = first-link; first-link = av; av = second; first = NULL;firstavfirstav回收前回收前回收后回收后secondif ( av = NULL ) newnode =

34、new CircListNode;else newnode = av; av = av-link; avnewnodeavrear3148155722rear1520253010first60657055rear1520253010p60657055first #include #include “CircList.h”Template void Josephus (CircList& Js, int n, int m) CircListNode * p = Js.Firster ( ); Type s; for ( int i = 0; i n-1; i+ ) /執(zhí)行執(zhí)行n- -1次次 fo

35、r ( int j = 0; j m-1; j+ ) p = Js.Next ( ); Js.getData (s); /數(shù)數(shù)m- -1個(gè)人個(gè)人 cout “出列的人是” s endl; Js.Remove (s); /刪去刪去 void main ( ) CircList clist; int n, m; cout n m; /形成約瑟夫環(huán) for ( int i = 1; i = n; i+ ) clist.insert (i); clist.Josephus (n, m); /解決約瑟夫問題in0iinn2210nxc xc xcxcc(x)PPn(x) 。u u coef exp li

36、nk Data Termstruct Term /多項(xiàng)式結(jié)點(diǎn)定義 float coef; /系數(shù) int exp; /指數(shù) Term ( float c, int e ) coef = c; exp = e; ; class Polynomial /多項(xiàng)式類的定義 List poly; /構(gòu)造函數(shù) friend Polynomial operator + ( Polynomial &, Polynomial &); /加法;AH = 1 - 3x6 + 7x12BH = - x4 + 3x6 - 9x10 + 8x14AH.firstBH.first CH.first 1 01 0-1 4-1

37、 4-3 63 6-9 10-9 107 127 128 148 14AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14pappc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 1

38、07 127 128 148 14pappc-9 10pb0AH.first CH.first 1 01 0-1 4-1 40 6-9 107 127 128 148 14pappc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pbAH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa = pc-9 10pb AH.fir

39、st CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa = pc-9 10pb Polynomial operator + ( Polynomial& ah, Polynomial& bh ) /兩個(gè)帶頭結(jié)點(diǎn)的按升冪排列的多項(xiàng)式相加，/返回結(jié)果多項(xiàng)式鏈表的表頭指針，結(jié)果不/另外占用存儲(chǔ), 覆蓋ah和bh鏈表 ListNode *pa, *pb, *pc, *p; Term a, b; pc = ah.poly.Firster ( ); /結(jié)果存放指針 p = bh.poly.Firster ( ); pa = ah.poly.First( ); /多

40、項(xiàng)式檢測(cè)指針 pb = bh.poly.First( ); /多項(xiàng)式檢測(cè)指針 delete p; /刪去bh的表頭結(jié)點(diǎn) while ( pa != NULL & pb != NULL ) a = pa-data; b = pb-data; switch ( compare ( a.exp, b.exp ) ) case = :/pa-exp = pb-exp a.coef = a.coef + b.coef; /系數(shù)相加 p = pb; pb = pb-link; delete p;/刪去原pb所指結(jié)點(diǎn) if ( abs(a.coef ) link; delete p; /相加為零, 該項(xiàng)不要

41、 else /相加不為零, 加入ch鏈 pa-data = a; pc-link = pa; pc = pa; pa = pa-link; break; case : /pa-exp pb-exp pc-link = pb; pc = pb; pb = pb-link; break; case exp exp pc-link = pa; pc = pa; pa = pa-link; if ( pa != NULL ) pc-link = pa; else pc-link = pb; /剩余部分鏈入ch鏈 return ah; p-lLinkp-rLinkplLinkrLinkfirstfirs

42、ttemplate class DblList;template class DblNode friend class DblList;private: Type data; /數(shù)據(jù) DblNode * lLink, * rLink; /指針public: DblNode (Type value, DblNode * left, DblNode * right ) : data (value), lLink (left), rLink (right) DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) DblNod

43、e ( ) : data(0), lLink(NULL), rLink(NULL) DblNode * getLeftLink ( ) return llink; /取得左鏈指針值 DblNode * getRightLink ( ) return rlink; /取得右鏈指針值 Type getData ( ) return data; void setLeftLink ( DblNode*Left ) llink = Left; /修改左鏈指針值 void setRightLink ( DblNode*Right ) rlink = Right; /修改右鏈指針值 void setData

44、 ( Type value ) data = value; ;template class DblList private: DblNode * first, * current;public: DblList ( Type uniqueVal ); /構(gòu)造函數(shù) DblList ( DblList& RL ); /復(fù)制構(gòu)造函數(shù) DblList ( ); /析構(gòu)函數(shù) int Length ( ) const; /計(jì)算長(zhǎng)度 int IsEmpty ( ) /判鏈表空否 return first-rlink = first; DblListNode * Find ( Type value ); /搜

45、索鏈表中含value的結(jié)點(diǎn) DblListNode * Firster ( ) current = first; return current;/當(dāng)前指針置于表頭結(jié)點(diǎn) DblListNode * First ( );/當(dāng)前指針置于第一個(gè)結(jié)點(diǎn) DblListNode * Next ( );/當(dāng)前指針置于后繼結(jié)點(diǎn) DblListNode * Prior ( );/當(dāng)前指針置于前驅(qū)結(jié)點(diǎn) int Insert ( Type value );/插入一個(gè)包含有值value的新結(jié)點(diǎn) int Remove ( Type& value ); /刪除當(dāng)前結(jié)點(diǎn);template DblList : DblLIst

46、( Type uniqueVal ) /構(gòu)造函數(shù): 建立雙向循環(huán)鏈表的表頭結(jié)點(diǎn) first = current = new DblNode ( uniqueVal ); if (first = NULL ) cerr rLink = first-lLink = first;template int DblList : Length ( ) const /計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長(zhǎng)度 DblNode * p = first-rLink; int count = 0; while ( p != first ) p = p-rLink; count+; return count;/按前驅(qū)方向計(jì)

47、算只需左、右互換即可 搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 template DblListNode * DblList :Find ( Type value ) /在雙向循環(huán)鏈表中搜索含value的結(jié)點(diǎn), 若/找到, 則返回1, 同時(shí)current指針指向該結(jié)點(diǎn), /否則函數(shù)返回0。 current = first-rLink; while ( current != first & current-data != value ) current = current-rLink; return current;fir

48、stfirst31481525currentcurrent31482515newnode-lLink = current;newnode-rLink = current-rLink;current-rLink = newnode;current = current-rLink;current-rLink-lLink = current;first25currentcurrent25newnode-lLink = current;newnode-rLink = current-rLink; ( = first )current-rLink = newnode;current = current-

49、rLink;current-rLink-lLink = current; ( first -lLink = current ) firsttemplate int DblList : Insert ( Type value ) if ( first-rlink = first ) /空表情形 current = first-rLink = new DblNode ( value, first, first ); else /非空表情形 current-rLink = new DblNode ( value, current, current-rLink );current = current-

50、rLink; current-rLink-lLink = current; return 1;template DblList : DblLIst ( DblList& RL ) /復(fù)制構(gòu)造函數(shù): 用已有鏈表RL初始化 first = new DblNode ( RL-data ); if ( first = NULL ) cerr lLink = first-rLink = first; if ( RL-current = RL-first ) current = first; ListNode *p = RL-first-rLink; ListNode *last = first; whi

51、le ( p != RL-first ) /逐個(gè)結(jié)點(diǎn)復(fù)制 last-rLink = new DblNode ( p-data, last, last-rLink ); if ( last-rLink = NULL ) /分配新結(jié)點(diǎn) cerr rLink; last-rLink-lLink = last; /鏈結(jié)完成 if ( RL-current = p ) current = last; p = p-rLink; firstfirst314815current3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink

52、 = current-rLink;firstfirst31currentcurrentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;template int DblList : Remove ( Type& value) if ( current != first ) DblNode *temp = current; /被刪結(jié)點(diǎn) current = current-rLink; current-lLink = temp-lLink; /摘下 temp-lLink-rLink = current;

53、 value = temp-data; delete temp; /刪去 return 1; return 0;template DbistNode * DblList : First ( ) if ( first-rLink = first ) current = first; else current = first-rLink; return current; template DbistNode * DblList : Next ( ) if ( current-rLink = first ) /最后結(jié)點(diǎn) current = first -rLink; else current = current-rLink; return current;template DbistNode * DblList : Prior ( ) if ( current-lLink = first ) /第一個(gè)結(jié)點(diǎn) current = first-lLink; else current = current-lLink; return current;headdownnextright(a) 表頭結(jié)點(diǎn)表頭結(jié)點(diǎn) (b) 非零元素結(jié)點(diǎn)非零元素結(jié)點(diǎn)rightvaluedownrowcolaijFalseij(c) 建立建立aij結(jié)點(diǎn)結(jié)點(diǎn) headenum Boolean