【文章內(nèi)容簡(jiǎn)介】 else { for (int i = 0。 i k。 i++) cout b[top – i] “ ” 。 top = top k。 return 1。 } } Bagfloat f。 BagCircle c。 于是， Bag對(duì)象 f存放浮點(diǎn)數(shù)， c存放圓。 JYP 58 效率與權(quán)衡 ? 時(shí)間和空間的權(quán)衡； ? 通用性和效率的權(quán)衡； ? 開發(fā)效率與運(yùn)行效率的權(quán)衡； ? 等等。 JYP 59 第 2章 線性表 本章學(xué)習(xí)最簡(jiǎn)單同時(shí)又最常用的數(shù)據(jù)結(jié)構(gòu) —線性表。 JYP 60 線性表與數(shù)組 線性表 L定義為： ( a0, a1, …, a n1)， n≥1 L = ( )， n = 0 線性表由 n個(gè)元素構(gòu)成。當(dāng) n = 0時(shí)， ( ) 表示空線性表。當(dāng) n 1時(shí)，表中第一個(gè)元素有唯一的后繼，最后一個(gè)元素有唯一的前驅(qū)，其余元素有唯一的后繼和前驅(qū)，因而呈現(xiàn) 線性關(guān)系 。 JYP 61 線性表的操作主要包括： （ 1）計(jì)算表的長(zhǎng)度 n。 （ 2）從左到右（或從右到左）遍歷表的元素。 （ 3）訪問第 i個(gè)元素， 0≤i n。 （ 4）將新值賦予第 i個(gè)元素， 0≤i n。 （ 5）將新元素插入第 i個(gè)位置， 0≤i n，使原來的第 i， i+1， … ， n–1個(gè)元素變?yōu)榈?i+1， i+2， … ，n個(gè)元素。 （ 6）刪除第 i個(gè)元素， 0≤i n，使原來的第 i+1，i+2， … ， n–1個(gè)元素變?yōu)榈?i， i+1， … ， n–2個(gè)元素。 JYP 62 假設(shè)線性表的元素類型是浮點(diǎn)數(shù)，其 ADT定義為： class LinearList { // 對(duì)象 : L = ( a0, a1, …, a n1) 或 ( ), ai?浮點(diǎn)數(shù) , 0≤i n public: LinearList ( )。 // 構(gòu)造函數(shù)，創(chuàng)建一個(gè)空表 int Length( )。 // 返回該實(shí)例的長(zhǎng)度 void LeftToRight( )。 // 從左到右遍歷全部元素 float Retrieve( int i )。 // 返回第 i個(gè)元素的值 void Store( int i, float v )。 // 將 v的值賦予第 i個(gè)元素 void Insert( int i, float v )。 // 將 v作為第 i個(gè)元素插入 float Delete( int i )。 // 刪除第 i個(gè)元素并返回其值 }。 JYP 63 如何表示線性表的結(jié)構(gòu)，從而高效實(shí)現(xiàn)這些操作？ 最通常的方法是用程序設(shè)計(jì)語言提供的數(shù)組，即用數(shù)組的第 i個(gè)單元表示線性表的 ai元素。 數(shù)組第 i個(gè)單元與第 i+1個(gè)單元在物理上是連續(xù)存放的，因此稱上述方法為 順序映射 （ sequential mapping）。 順序映射使隨機(jī)存取表中的任何元素的時(shí)間是O(1)，但插入和刪除第 i個(gè)元素將導(dǎo)致其后續(xù)元素的遷移。 作業(yè)： P62—2 JYP 64 多項(xiàng)式 數(shù)學(xué)上，多項(xiàng)式 P(x)定義為： 其中非零項(xiàng)的最大指數(shù)稱為 階 。 多項(xiàng)式的 ADT定義如下： class Polynomial { // 對(duì)象：一個(gè)有序?qū)?ei, ai的集合 , 其中， ai 是系數(shù)， ei 是指 // 數(shù)，且指數(shù)是 ≥ 0的整數(shù)。 public: Polynomial ( )。 // 返回多項(xiàng)式 p(x) = 0 JYP 65 int operator ! ( )。 // 若 *this 是零多項(xiàng)式返回 1，否則返回 0 float Coef (int e)。 // 返回 *this 中指數(shù)為 e 的項(xiàng)的系數(shù) int LeadExp ( )。 // 返回 *this 中最大指數(shù) void AddTerm (int e, float c)。 // 將 e, c 加入 *this Polynomial Add (Polynomial poly)。 // 返回多項(xiàng)式 *this 與 // poly之和 Polynomial Mult (Polynomial poly)。 // 返回多項(xiàng)式 *this 與 // poly之積 float Eval ( float f)。 // 計(jì)算并返回 x = f時(shí) *this 多項(xiàng)式的值 }。 JYP 66 多項(xiàng)式的表示 規(guī)定 :多項(xiàng)式中的項(xiàng)按指數(shù)遞減順序排列。 方法 1 定義一個(gè)有 MaxDegree+1個(gè)元素的數(shù)組表示系數(shù)，數(shù)組下標(biāo)表示相應(yīng)的指數(shù)： private: int degree。 // 當(dāng)前多項(xiàng)式的階 float coef[MaxDegree+1]。 // MaxDegree是多項(xiàng)式的最高階 若 p是類 Polynomial的一個(gè)對(duì)象，則： = n [i] = ani， 0≤i≤n 這種表示法使多項(xiàng)式的許多操作實(shí)現(xiàn)非常簡(jiǎn)單。 JYP 67 方法 2 當(dāng) MaxDegree時(shí)，方法 1很浪費(fèi)空間，可動(dòng)態(tài)定義 coef數(shù)組的元素個(gè)數(shù)： private: int degree。 float *coef。 構(gòu)造函數(shù)為： Polynomial::Polynomial( int d) { degree = d。 coef = new float [degree+1]。 // 動(dòng)態(tài)申請(qǐng)數(shù)組空間 } JYP 68 方法 3 對(duì)于有很多零項(xiàng)的稀疏多項(xiàng)式，方法 2仍然很浪費(fèi)空間。例如 x800+3僅有 2個(gè)非零項(xiàng)，其余 799項(xiàng)都是零項(xiàng)。這時(shí)，只存儲(chǔ)非零項(xiàng)更為有效。由此將多項(xiàng)式表示為另一種形式： 其中， bi?0， ( 0≤i≤m )， em em1 …e 0 ≥0。 為此，不僅需要顯式存儲(chǔ)系數(shù)，而且需要顯式存儲(chǔ)指數(shù)。同時(shí)，為了充分利用存儲(chǔ)資源，所有Polynomial類的多項(xiàng)式都用一個(gè)元素類型為 term的數(shù)組 termArray表示： JYP 69 term定義如下： class Polynomial。 // 向前聲明 class term { friend Polynomial。 private: float coef。 // 系數(shù) int exp。 // 指數(shù) }。 JYP 70 Polynomial的私有成員定義如下： private: static term termArray[MaxTerms]。 // 靜態(tài)成員聲明 static int free。 // 靜態(tài)成員聲明 int Start, Finish。 // 多項(xiàng)式的起、始位置 其中， MaxTerms是常數(shù)。由于類中的靜態(tài)成員聲明不構(gòu)成其定義，還必須在類定義之外定義靜態(tài)成員如下： term Polynomial::termArray[MaxTerms]。 int Polynomial::free = 0。 // 指示 termArray中的下一個(gè)可用單元 JYP 71 例如 ， A(x) = 2x800+3x3+1和 B(x) = 7x5+x3+5x+2 一個(gè)多項(xiàng)式 p(x)的項(xiàng)數(shù)為 –+1。 當(dāng)多項(xiàng)式的零項(xiàng)很多時(shí) ， 方法 3明顯好于方法 2。但當(dāng)絕大多數(shù)都是非零項(xiàng)時(shí) ， 方法 3所用空間大約是方法 2的兩倍 。 JYP 72 多項(xiàng)式相加 用方法 3表示多項(xiàng)式 A和 B。 由于多項(xiàng)式的項(xiàng)是按指數(shù)遞減順序排列的 ， 因而通過對(duì) A和 B逐項(xiàng)掃描 ，比較指數(shù) ， 很容易實(shí)現(xiàn) C=A+B。 用函數(shù) NewTerm將新的屬于 C的項(xiàng)存入 free所指的 termArray可用單元 。 1 Polynomial Polynomial::Add(Polynomial B) { 2 Polynomial C。int a=Start。int b=。=free。 float c。 3 while (a = Finish amp。amp。 b = ) 4 switch (pare(termArray[a].exp, termArray[b].exp)) { 5 case ?=?: c=termArray[a].coef + termArray[b].coef。 6 if (c) NewTerm(c, termArray[a].exp)。 7 a++。 b++。 8 break。 JYP 73 9 case ?39。: NewTerm(termArray[b].coef, termArray[b].exp)。 10 b++。 11 break。 12 case ?39。: NewTerm(termArray[a].coef, termArray[a].exp)。 13 a++。 14 } 15 for (。a=Finish。a++) NewTerm(termArray[a].coef, termArray[a].exp)。//加入 A(x)的剩余項(xiàng) 16 for (。b=。b++) NewTerm(termArray[b].coef, termArray[b].exp)。//加入 B(x)的剩余項(xiàng) 17 =free–1。 18 return C。 19} JYP 74 void Polynomial::NewTerm(float c, int e) { //將新項(xiàng)加入 C(x)中 if (free = MaxTerms) { cout ―空間不夠！? endl。 return。 } termArray[free].coef = c。 termArray[free].exp = e。 free++。 } // NewTerm結(jié)束 JYP 75 分析： ? 設(shè) m和 n分別是 A和 B的非零項(xiàng)個(gè)數(shù) 。 ? 第 2行 ——O(1)。 ? 第 3行的循環(huán)內(nèi)執(zhí)行一次 ， a或 b或 a和 b增加 1， 循環(huán)次數(shù)最多是 m+n–1。 ? 第 15和 16行的循環(huán)的總次數(shù)不超過 m+n。 整個(gè)算法的時(shí)間復(fù)雜性是 O(m+n)。 free超過 MaxTerms時(shí)的處理很麻煩 。 作業(yè)： P62—4， 5 JYP 76 稀疏矩陣 矩陣是常用的數(shù)學(xué)對(duì)象，由 m行、 n列元素構(gòu)成，也稱為 m ? n矩陣。當(dāng) m = n時(shí)，稱該矩陣為方陣。 例子： JYP 77 表示： ? 用二維數(shù)組，如 A[m][n]，表示矩陣十分自然。但對(duì)于大型稀疏矩陣，非零項(xiàng)只占所需空間的很小部分。 ? 較好的辦法是只存儲(chǔ)非零項(xiàng)，而將零元素作為缺省值。 JYP 78 稀疏矩陣抽象數(shù)據(jù)類型 class SparseMatrix { // 對(duì)象 : 三元組 行 , 列 , 值 的集合，行、列、值都是整型 public: SparseMatrix ( int Rows, int Cols )。 SparseMatrix Transpose ( )。 // 返回 (*this)矩陣的轉(zhuǎn)置矩陣 SparseMatrix Add ( SparseMatrix b)。 SparseMatrix Multiply ( SparseMatrix b)。 }。 JYP 79 稀疏矩陣的表示 ? 用三元組 row, col, value唯一表示矩陣元素 ? 用一個(gè)由此三元組構(gòu)成的數(shù)組表示整個(gè)稀疏矩陣 ? 所有三元組按行號(hào)遞增順序排序，同一行內(nèi)的三元組按列號(hào)遞增順序排序 ? 存儲(chǔ)稀疏矩陣的行數(shù)、列數(shù)和非零項(xiàng)的個(gè)數(shù) JYP 80 class SparseMatrix。 // 向前聲明 class MatrixTerm { fri