【文章內(nèi)容簡(jiǎn)介】 if ( first == NULL || i == 0 ) //插在表頭 { newnode→ link = first 。 first=current=newnode。 } else { //插在表中或末尾 newnode→ link = current→ link。 current → link = newnode。 current=newnode。 } 在鏈表第 i 個(gè)結(jié)點(diǎn)處插入新元素 x 單鏈表中的 刪除 （ 返回所刪的結(jié)點(diǎn)值 ） 在單鏈表中刪除第 i個(gè)位置（數(shù)據(jù) ai）的結(jié)點(diǎn) ?第一種情況 : 刪除表中第一個(gè)元素 ?第二種情況 : 刪除表中或表尾元素 int List::Remove ( int i ) { ListNode * q , *p =current。 //q用來暫存被刪結(jié)點(diǎn) current=frist。 int k = 0。 while ( current != NULL amp。amp。 k i1 ) { current =current→ link。 k++。 } //找 第 i1個(gè)結(jié)點(diǎn) if ( current == NULL || current→ link == NULL ) { cout ―無(wú)效的刪除位置 !\n‖。 current=p。 return 0。 } ?在鏈表中刪除第 i個(gè)結(jié)點(diǎn) if ( i == 0 ) { //刪除表中第 1個(gè)結(jié)點(diǎn) q = first。 current = first = first→ link。 } //q保存被刪結(jié)點(diǎn)地址 else { //刪除表中或表尾元素 q = current→ link。 current → link = q→ link。 //重新鏈接 current= current →link。 } int x = q→ data。 delete q。 //刪除 q return x。 //返回被刪結(jié)點(diǎn)值 } 表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。 設(shè)置表頭結(jié)點(diǎn)的 目的 是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。 非空表 空表 current=last 帶表頭結(jié)點(diǎn)的單鏈表 在帶表頭結(jié)點(diǎn)的單鏈表 第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn) newnode→ link = p→ link。 p→ link = newnode。 q = p→ link。 p→ link = q→ link。 delete q。 從帶表頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn) data link 數(shù)據(jù) 指向下一個(gè)結(jié)點(diǎn)的指針 數(shù)據(jù)成員： Type data。 ListNodeType * link。 成員函數(shù) : …… getNode(item,*next=NULL )——建立新結(jié)點(diǎn) getLink( )——取下一結(jié)點(diǎn)的地址 getData( )————取當(dāng)前結(jié)點(diǎn)數(shù)據(jù)。 setLink( * next )——修改當(dāng)前結(jié)點(diǎn)的指針 Link=next. setData( value )——修改當(dāng)前結(jié)點(diǎn)的數(shù)據(jù) data=value. ?結(jié)點(diǎn)類 ListNode： 單鏈表的模板類 a0 a1 an ^ …… first ?鏈表類 List 數(shù)據(jù)成員： ListNodeType * first。 頭指針 ListNodeType * current。當(dāng)前指針 成員函數(shù)： …… …… √ Find( value)——搜索含數(shù)據(jù) value的元素 Locate( i )——搜索第 i 位置的元素 (定位 ) √ Insert( value )——將 value插入在當(dāng)前位置之后 √ Remove( )——?jiǎng)h除當(dāng)前元素 Length( )——長(zhǎng)度 First ( )——把當(dāng)前指針定位于頭結(jié)點(diǎn) Next( )——把當(dāng)前指針移到下一個(gè)結(jié)點(diǎn)處 current 在單鏈表中 搜索 含數(shù)據(jù) value的結(jié)點(diǎn) template class TypeListType*ListType::Find( Type value ) { current=first → link。 while (current !=NULL amp。amp。 current → data !=value) current=current →link。 return current。 } ——搜索成功時(shí)返回結(jié)點(diǎn)地址，否則返回 NULL 將含 value的新元素 插入 到鏈表當(dāng)前結(jié)點(diǎn)之后位置 template class Type int ListType::Insert ( Type value ) { if ( current == NULL ) return 0。 ListNodeType *newnode =GetNode (value,current→ link)。 ① current→ link = newnode。 ② //重新鏈接 current=current →link。 ③ return 1。 } value current ① ② X current X ③ P53 從鏈表中 刪去 結(jié)點(diǎn) template class Type Type *ListType::Remove ( ) { if (current==first) return null。 ListNodeType *p =first。 while ( p→ link != current ) p=p →link。 ① p→ link =current→ link。 ② //重新鏈接 Type x =current → data。 //保存被刪數(shù)據(jù) delete current 。 ③ current=p→link。 ④ return amp。x。 } if (current = =null) current = first data p current ② ① ③ ④ current X 34 設(shè)有一個(gè)表頭指針為 h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針 h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。 【 解答 1】 templateclass Type void ListType :: Inverse ( ) { if ( h == NULL ) return。 ListNodeType *p = h→ link, *pr = NULL。 while ( p != NULL ) { h→ link = pr。 //逆轉(zhuǎn) h指針 pr = h。 h = p。 p = p→ link。 //指針前移 } h→ link = pr。 } 【 解答 2】 templateclass Type void ListType :: Inverse ( ) { ListNodeType *p, head=new ListNodeType ( )。 while (h != NULL ) { p = h。 h = h→ link。 //摘下 h鏈頭結(jié)點(diǎn) p→ link = head→ link。 head→ link = p。 //插入 head鏈前端 } h = head→ link。 delete head。 //重置 h } 雙向鏈表 P61 ?結(jié)點(diǎn)定義： lLink data rLink 指向前驅(qū)結(jié)點(diǎn) 數(shù)據(jù) 指向后繼結(jié)點(diǎn) /// …… first ?雙向鏈表 a0 a1 an 雙向鏈表 搜索 、 插入與刪除 算法 ?搜索 算法 P63 ?插入 算法 （ 插在當(dāng)前結(jié)點(diǎn)之后） 原表為空： current=new DblNodeType (value, first, first)。 first →rL ink=current。 q=current →rL ink。 ① p =new DblNodeType (value, current, q )。② current →rL ink=p。 ③ q →lL ink = p。 ④ current=p。 value current P q ② ③ ④ ① ?刪除 算法 (刪除 當(dāng)前結(jié)點(diǎn) ) P65 p=current。 ① current=current →rL ink。 ② current →lL ink = p →lLink 。 ③ p →lLink →rLink=current。 ④ delete p。 current current X p ① ② ③ ④ X X 刪除第 1個(gè)結(jié)點(diǎn)？ ——不用分情況 習(xí)題 P68： 3 3 36 習(xí)題： P41 習(xí)題： 23 、 2 2 214 返回 退出 第四章 棧與隊(duì)列 熟練掌握 ： ? 棧的定義、特性 ? 棧的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 （特別注意?？蘸蜅M的條件） ? 隊(duì)列的定義、特性 ? 隊(duì)列的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 （特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況） 掌握 ： ? 優(yōu)先隊(duì)列的定義、特性 ? 優(yōu)先隊(duì)列的的抽象數(shù)據(jù)類型 ? 優(yōu)先隊(duì)列的插入與刪除算法 了解：在表達(dá)式計(jì)算時(shí)棧的使用， 主要 是中綴表示改為后綴表示的方法思路 棧的定義及基本運(yùn)算 棧 (Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表， 通常稱插入、刪除的這一端為 棧頂 (Top)， 另一端為 棧底 (Bottom)。 當(dāng)表中沒有元素時(shí)稱為 空棧 。 棧 LIFO 進(jìn)棧： top+1。新元素插入 elements[top]位置 , 出棧： top1 假設(shè)棧 S=(a1， a2， a3， … an)， 則 a1稱為棧底元素， an為棧頂元素。 棧中元素按 a1， a2， a3， … an的次序進(jìn)棧，退棧按后進(jìn)先出的原則進(jìn)行的 ,因此 an …… a3 a2 a1的次序出棧。 棧的定義 P7172 ?類定義 數(shù)據(jù)成員： int top。 Type *elements。 int maxSize。 成員函數(shù)： GetTop( ) ——取棧頂元素 IsEmpty( )——判斷?？?(top==1)