【正文】 93 2021/12/1 94 2021/12/1 95 2021/12/1 96 2021/12/1 97 2021/12/1 98 2021/12/1 99 2021/12/1 100 2021/12/1 101 2021/12/1 102 2021/12/1 103 2021/12/1 104 2021/12/1 105 2021/12/1 106 2021/12/1 107 2021/12/1 108 2021/12/1 109 2021/12/1 110 2021/12/1 111 2021/12/1 112 2021/12/1 113 2021/12/1 114 2021/12/1 115 2021/12/1 116 。 } int First ( )。 } lLink data rLink左鏈指針 右鏈指針 數(shù)據(jù) 2021/12/1 66 帶頭結(jié)點的雙向 循環(huán)鏈表 ： 空表 游標結(jié)點： * current 游標結(jié)點的前驅(qū)結(jié)點： * ( current lLink ) 游標結(jié)點的后繼結(jié)點： * ( current rLink ) e0 e1 en1 … current first first 2021/12/1 67 雙向循環(huán)鏈表的類定義： template class Type class DblList { public: DblList ( Type uniqueVal )。//將 current 指向后繼結(jié)點 Boolean Prior ( )。 int Length ( ) const。 //若存在后繼結(jié)點，則循環(huán)累加 return retvalue。 currentlink != NULL ) current=currentlink。amp。 // 使游標指向后繼結(jié)點 private: const ListType amp。 } return p。 } … … 結(jié)點 i1 結(jié)點 i 結(jié)點 i+1 p q (1) (2) 2021/12/1 55 template class Type ListNodeType *ListType::Find( int i ) { // 查找結(jié)點 i , 若找到，則返回該結(jié)點的指針，否則返回 NULL if ( i 1 ) return NULL。 // 查找結(jié)點 i1 if ( p==NULL || plink==NULL) return NULL。// 最后讓 last 指向頭結(jié)點，完成置空表操作 } first … (1) q=firstlink (2) firstlink=qlink (最后 ) last 頭結(jié)點 2021/12/1 53 template class Type int ListType::Insert(Type value,int i)。 //(1) if (link==NULL) return NULL。 item) //構(gòu)造函數(shù)，創(chuàng)建一個新結(jié)點，該結(jié)點的值為 item , 指針域為 NULL { data=item。//刪除所有元素結(jié)點，將鏈表置為空鏈表 int Length( ) const。 //將 *p 結(jié)點插入到當前結(jié)點之后 ListNode Type * GetNode (const Type amp。 設(shè)置頭結(jié)點的目的是為了簡化對空表的特殊處理， 使得算法更簡單、更有效。 If (s1==s2)… If (s1!=s2)… If (! s1)… Char c=s1[6]。 String s2 ( ― Hello World ‖ )。 operator += (const String amp。 int operator ==(const String amp。 } 2021/12/1 39 2。i++){ int j=rowStart[smArray[i].col]。iTerms。 SparseMatrixType b。 SparseMatrixType Multiply(SparseMatrixType b)。因此用二維數(shù)組來存儲稀疏矩陣的空間利用率較低，必須考慮對稀疏矩陣的壓縮存儲表示。 return C 。 a++ 。 if (c) NewTerm( c , termArray[a].exp ) 。 b = B . start； （ 4）當兩個指針都未超出相應(yīng)多項式的最末位置時，比較它們所 指示的對應(yīng)項的指數(shù)： 若指數(shù)相等，則對應(yīng)項系數(shù)相加，若相加結(jié)果不為零，則在 C 中加入一個新項 若指數(shù)不等，則把指數(shù)小者拷貝到 C 中 （ 5）當兩個指針中有一個超出了相應(yīng)多項式的最末位置，則將另 一個多項式的剩余部分拷貝到 C 中 2021/12/1 28 Polynomial Polynomial :: Add ( Polynomial B ) { Polynomial C。 // 多項式類的前視聲明 class term // 多項式中項（二元組）的類定義 { friend Polynomial。 int m = ( )。i=m1。 } return 0。 } } 2021/12/1 17 （ 4）順序表刪除操作 為了刪除第 i 個元素，必須把從 i＋ 1 到 last 的所有元素向前移動一個元素位置，把第 i 個元素覆蓋掉： 1 2 . . . 0 i1 i i+1 last1 last 1 . . . . . . . . . . . . . . . 2021/12/1 18 template class Type int SeqlistType::Remove(Type amp。 } 2021/12/1 15 （ 3）順序表插入操作 為了把新元素 x 插入到 i 處，必須把從 i 到 last 的所有元素成塊向后移動一個元素位置，以空出第 i 個位置供 x 插入： x 2 3 1 先移動后面元素 0 i1 i i+1 last . . . . . . . . . . . . . . . . . . 2021/12/1 16 template class Type int SeqlistType::Insert(Type amp。 // last+1=0 , 表明表中無元素，空表 data=new Type[Maxsize]。 Get( int i ) {return i 0 || i last ? NULL : data[i]。 x) const。通?？捎脠D形表示，圓圈表示數(shù)據(jù)元素，箭頭表示關(guān)系： ? 物理結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)在計算機中的具體表示和實現(xiàn)， 又稱存儲結(jié)構(gòu) E i E i+1 數(shù)據(jù)元素 數(shù)據(jù)元素 關(guān)系 2021/12/1 5 數(shù)據(jù)結(jié)構(gòu)的分類 ? 按邏輯結(jié)構(gòu)分類： 純集合型結(jié)構(gòu) :數(shù)據(jù)元素之間除了 “ 同屬于一個集合 ” 這一 關(guān)系外，別無其他關(guān)系 線性結(jié)構(gòu)： 數(shù)據(jù)元素之間存在 “ 一個跟著一個 ” 的序列關(guān)系 樹型結(jié)構(gòu)： 數(shù)據(jù)元素之間存在 “ 每個元素只能跟著一個元素 但可以有多個元素跟著它 ” 的層次關(guān)系 圖狀結(jié)構(gòu)： 任意兩個數(shù)據(jù)元素之間都可能存在關(guān)系 ? 按存儲結(jié)構(gòu)分類： 順序存儲結(jié)構(gòu) 鏈式存儲結(jié)構(gòu) 索引存貯結(jié)構(gòu) 2021/12/1 6 基本操作： 任一數(shù)據(jù)結(jié)構(gòu)均有一組相應(yīng)的基本操作， 有時操作不同，用途迥異（如棧和隊列） 常用的基本操作有插入、 刪除、查找、 更新、排序等 算 法： 算法是為了解決給定的問題而規(guī)定的一個 有限長的操作步驟序列，則重于解決問題 的方法和步驟。 數(shù)據(jù)項又稱域、字段 ? 關(guān) 鍵 碼： 能起唯一標識（數(shù)據(jù)元素）作用的數(shù)據(jù)項 ? 數(shù)據(jù)結(jié)構(gòu)： 一組同類的數(shù)據(jù)元素、其間的關(guān)系及其上的 一組操作所構(gòu)成的整體，稱為一個數(shù)據(jù)結(jié)構(gòu) 2021/12/1 4 數(shù)據(jù)結(jié)構(gòu)的描述方式 ? 邏輯結(jié)構(gòu)： 是對數(shù)據(jù)元素之間邏輯關(guān)系（拋開具體的關(guān)系含義以及存儲方式等）的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的幾個關(guān)系來表示。} int Find(Type amp。} Type amp。 last=1。 else return i。 return 1。 return 1。 for (int i=0。 LB) // 求順序表 LA 與 LB 的共同元素，結(jié)果在 LA 中 { int n = ( )。 } } 2021/12/1 22 多項式及其運算 A(x)=a0x + a1x +a2x +…+ an1x + anx = B(x)=b0x + b1x +b2x +…+ bn1x +bnx = A(x)+B(x)= 實際應(yīng)用中，上述一元多項式中的很多系數(shù)有可能為零， 即為稀疏多項式，如下式所示： Σ aix i=0 n i 0 1 2 n1 n 0 1 2 n1 n Σ bix i i=0 Σ (ai+bi)x n i=0 i P (x)=+ + 50 50 101 P(x)=Σci x i=0 n ei c0= e0=0 c1= e1=50 c2= e2=101 2021/12/1 23 多項式的表示 對于稀疏多項式，采用二元組表示法可以大大節(jié)省存儲 空間： （ 1）將稀疏多項式的每一項用二元組 ci , ei 表示 ——客體的表示方法 （ 2）用一順序表（一維數(shù)組）來存放上述的二元組 ——數(shù)據(jù)的組織方法 c0 c1 ci e0 e1 ei en 系數(shù) 指數(shù) .