【正文】 value )。 target )。 //頭指針，游標(biāo)，尾指針 } 2021/12/1 64 作業(yè)： （ 1）比較單鏈表及其游標(biāo)類與循環(huán)鏈表類的定義的不同 （ 2）考察循環(huán)鏈表中游標(biāo)功能的實(shí)現(xiàn)方法 （ 3）模仿循環(huán)鏈表的類定義，重新定義單鏈表的類，使其具有游 標(biāo)功能，并設(shè)計(jì)新單鏈表的各成員函數(shù) 自學(xué)： 多項(xiàng)式及其相加 2021/12/1 65 雙向鏈表（ Doubly Linked List） 如果在一個(gè)應(yīng)用問題中經(jīng)常要求檢測指針向前驅(qū)和后繼方向移動(dòng)， 為保證移動(dòng)的時(shí)間復(fù)雜度達(dá)到最小，就必須采用雙向鏈表表示。//讀取游標(biāo)結(jié)點(diǎn)（ *current )的數(shù)據(jù)域 void Firster ( ) { current=first。 CircListNode Type * link。//定義一個(gè)單鏈表對象 l 及其游標(biāo)類對象 li ,并 //將游標(biāo)指向單鏈表的頭結(jié)點(diǎn)（由構(gòu)造函數(shù)實(shí)現(xiàn)） if ( ! ()) return 0。 // 否則置空游標(biāo) return current。 else return False。 // 檢查游標(biāo)結(jié)點(diǎn)（指針 current // 所指的結(jié)點(diǎn)）是否為不空 Boolean NextNotNull ( )。amp。 delete q。// 若結(jié)點(diǎn) i 不存在，則新結(jié)點(diǎn)將 // 是表尾結(jié)點(diǎn) plink=newnode。 first link=q link 。 } 2021/12/1 50 InsertAfter( ) 函數(shù) template class Type void ListNodeType:: InsertAfter(ListNodeType *p) {將 p 所指的結(jié)點(diǎn)（ *p）鏈接成為當(dāng)前結(jié)點(diǎn)（ *this）的后繼結(jié)點(diǎn) plink=link。 //刪除結(jié)點(diǎn) i Type Get(int i)。 } data link 2021/12/1 48 template class Type class List//單鏈表類的定義 { public: List( ) {last=first=new ListNodeType (value,NULL)。 item)。 2021/12/1 45 定義：用由指針連接起來的一串結(jié)點(diǎn)來存儲一個(gè)線性表 的存儲結(jié)構(gòu)稱為線性鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈表。 int len=()。 private: int curLen。 operator = (const String amp。 ~String() {delete [ ] ch。} } delete [] rowSize。i++) rowStart[i]=rowStart[i1]+rowSize[i1]。 iCols。 （ 3）數(shù)值計(jì)算與非數(shù)值計(jì)算的數(shù)據(jù)結(jié)構(gòu)中所定義的基 本操作有很大的不同 2021/12/1 36 稀疏矩陣的轉(zhuǎn)置操作 快速轉(zhuǎn)置算法思路： （ 1）引入兩個(gè)輔助數(shù)組 rowSize[ ] 和 rowStart[ ] rowSize [ i ]——表示稀疏矩陣第 i 列的非零元素個(gè)數(shù) rowStart[ i ]——表示稀疏矩陣第 i 列的第一個(gè)（行號最?。? 非零元素在轉(zhuǎn)置矩陣的三元組表中的位置。} SparseMatrixType Compression(smDataType)。 free ++ 。 b = 。 b++ 。 while ( a = finish amp。 //存放二元組的數(shù)組，存放多個(gè)多項(xiàng)式的共享空間 static int free 。 n。 } } } 2021/12/1 21 template class Type void Intersection( Seqlist Type amp。 { int n=()。j=last。j) data[j]=data[j1]。 data[i]!=x) i++。 由上可知：合理地設(shè)置數(shù)據(jù)成員可大大簡化算法的設(shè)計(jì)及提高算法的效率。 int IsEmpty( ) {return last = = 1。 ~SeqList( ) {delete [ ] data。 2021/12/1 3 基本術(shù)語 ? 數(shù) 據(jù)： 描述客觀事物的且能由計(jì)算機(jī)處理的數(shù) 值、字符等符號 ? 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常 作為一個(gè)整體進(jìn)行考慮和處理（記錄、 結(jié)點(diǎn)、表目、元素） ? 數(shù) 據(jù) 項(xiàng)： 數(shù)據(jù)元素的某一屬性。 1 線性表的邏輯結(jié)構(gòu) 定義 ： 由相同種類的數(shù)據(jù)元素組成的一個(gè)有窮序列稱為一個(gè)線性表。 x,int i)。 // 用數(shù)組存放線性表 ——順序存貯結(jié)構(gòu) int Maxsize。 x) const //查找 x 在表中位置，若查找成功，函數(shù)返回 x 的位置 //否則返回－ 1 { int i=0。 else { last++。若 x 在表中并成功刪除則返回 1， //否則返回 0 { int i=Find(x)。 2021/12/1 20 順序表應(yīng)用舉例 當(dāng)將兩個(gè)順序表作集合考慮時(shí)的 “ 并 ” 與 “ 交 ” 操作算法 template class Type void Union(Seqlist Type amp。 // 從順序表 LB 中取一元素 int k=(x)。 while ( i n ) { Type x = ( i )。 // 系數(shù) int exp。 int b =。 b++ 。 a = finish 。 return 。 Type value。 Trituple Type smArray[MaxTerms]。 = Rows。 rowStart[0]=0。 [j].col=smArray[i].row。)。} int operator !=(const String amp。 char amp。 String s3 ( ― 。 2021/12/1 42 文本編輯 計(jì)算機(jī)應(yīng)用中要涉及大量的文本文件，文本文件由大量的串 （行）組成，在某些文本文件（如源程序）中，串（行）長差異 很大，若每行都用等長的串來存貯，則會(huì)浪費(fèi)存貯空間 解決的辦法之一是建立一個(gè)很大的字符數(shù)組作為所有串的共享空間 ——串值共享空間，再為每個(gè)串建立一個(gè)描述子，用于描述該串的長度以及該串在串值共享空間中的位置等信息，并將這些描述子存入一順序表中，參見下圖： 2021/12/1 43 行表 (linelist) 串值共享空間（ space） MaxSize1 . . . . free 行號 0 1 2 3 行長 位置 行 2 行 3 行 0 行 1 . . . . . . . . . . . 自由空間起始地址 0 串值共享空間 ——String（串） 行表 ——Seqlist（順序表） 設(shè)計(jì)行內(nèi)字符插入、刪除操作算法 設(shè)計(jì)整行插入、刪除操作算法 2021/12/1 44 第三章 鏈表 順序表有下列缺點(diǎn)： （ 1）插入、刪除操作時(shí)需要移動(dòng)大量元素， 效率較低； （ 2）最大表長難以估計(jì)，太大了浪費(fèi)空間， 太小了容易溢出。 //單鏈表類的前視聲明 template class Type class ListNode{ //鏈表結(jié)點(diǎn)類的定義 friend class List Type。 //創(chuàng)建一個(gè)新結(jié)點(diǎn) ListNode Type * RemoveAfter ( )。 //查找值為 value 的結(jié)點(diǎn) ListNodeType *Find(int i)。 } template class Type ListNodeType * ListNodeType:: GetNode(const Type amp。 //(2) return tempptr。// 查找結(jié)點(diǎn) i1 if (p==NULL) return 0。 // (1) plink=qlink。// 結(jié)點(diǎn) –1 即為頭結(jié)點(diǎn) ListNodeType *p=firstlink。 單鏈表的位置概念： current 是結(jié)點(diǎn) i+1的位置 有了單鏈表結(jié)點(diǎn) i+1 的位置 current ，刪除結(jié)點(diǎn) i+1 或在 結(jié)點(diǎn) i+1 前插入新結(jié)點(diǎn)就會(huì)簡單得多，無需查找過程。 ListNodeType * current。 else return False。// 否則置空游標(biāo) return current。若單鏈表為空則返回 NULL， 否則返回最大結(jié)點(diǎn)的位置。 } Boolean Find ( const Type amp。 value )。 int Length ( ) const。 int Prior ( )。 } 2021/12/1 68 2021/12/1 69 2021/12/1 70 2021/12/1 71 2021/12/1 72 2021/12/1 73 2021/12/1 74 2021/12/1 75 2021/12/1 76 2021/12/1 77 2021/12/1 78 2021/12/1 79 2021/12/1 80 2021/12/1 81 2021/12/1 82 2021/12/1 83 2021/12/1 84 2021/12/1 85 2021/12/1 86 2021/12/1 87 2021/12/1 88 2021/12/1 89 2021/12/1 90 2021/12/1 91 2021/12/1 92 2021/12/1