【文章內(nèi)容簡(jiǎn)介】 窮的。 ：線性表中數(shù)據(jù)元素的類型是同一的。 ：線性表中相鄰的數(shù)據(jù)元素 ai1和 ai之間存在序偶關(guān)系 (ai1, ai)，即 ai1是 ai的前驅(qū)， ai是 ai1的后繼；a1 無(wú)前驅(qū)， an無(wú)后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表的抽象數(shù)據(jù)類型定義 ADT List Data 線性表中的數(shù)據(jù)元素具有相同類型， 相鄰元素具有前驅(qū)和后繼關(guān)系 Operation InitList 前置條件 ：表不存在 輸入 ：無(wú) 功能 ：表的初始化 輸出 ： 無(wú) 后置條件 ：建一個(gè)空表 線性表的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 DestroyList 前置條件 ：表已存在 輸入 ：無(wú) 功能 ：銷毀表 輸出 ：無(wú) 后置條件 ：釋放表所占用的存儲(chǔ)空間 Length 前置條件 ：表已存在 輸入 ：無(wú) 功能 ：求表的長(zhǎng)度 輸出 ：表中數(shù)據(jù)元素的個(gè)數(shù) 后置條件 ：表不變 線性表的邏輯結(jié)構(gòu) 線性表的抽象數(shù)據(jù)類型定義 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 Get 前置條件 ：表已存在 輸入 ：元素的序號(hào) i 功能 ：在表中取序號(hào)為 i的數(shù)據(jù)元素 輸出 ：若 i合法，返回序號(hào)為 i的元素值，否則拋出異常 后置條件 ：表不變 Locate 前置條件 ：表已存在 輸入 ：數(shù)據(jù)元素 x 功能 ：在線性表中查找值等于 x的元素 輸出 ：若查找成功 ， 返回 x在表中的序號(hào) ， 否則返回 0 后置條件 ：表不變 線性表的邏輯結(jié)構(gòu) 線性表的抽象數(shù)據(jù)類型定義 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 Insert 前置條件 ：表已存在 輸入 ：插入 i； 待插 x 功能 ：在表的第 i個(gè)位置處插入一個(gè)新元素 x 輸出 ：若插入不成功 ， 拋出異常 后置條件 ：若插入成功 ， 表中增加一個(gè)新元素 Delete 前置條件 ：表已存在 輸入 ：刪除位置 i 功能 ：刪除表中的第 i個(gè)元素 輸出 ：若刪除成功，返回被刪元素，否則拋出異常 后置條件 ：若刪除成功 ， 表中減少一個(gè)元素 線性表的邏輯結(jié)構(gòu) 線性表的抽象數(shù)據(jù)類型定義 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 Empty 前置條件 ：表已存在 輸入 ：無(wú) 功能 ：判斷表是否為空 輸出 ：若是空表 ， 返回 1， 否則返回 0 后置條件 ：表不變 ADT 進(jìn)一步說(shuō)明 : （ 1）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定； （ 2）復(fù)雜的操作可以通過(guò)基本操作的組合來(lái)實(shí)現(xiàn)； （ 3） 對(duì)不同的應(yīng)用，操作的接口可能不同。 線性表的邏輯結(jié)構(gòu) 線性表的抽象數(shù)據(jù)類型定義 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 ——線性表的順序存儲(chǔ)結(jié)構(gòu) 例： （ 34, 23, 67, 43） 34 23 67 43 4 存儲(chǔ)要點(diǎn) 用一段地址 連續(xù) 的存儲(chǔ)單元 依次 存儲(chǔ)線性表中的數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 ——線性表的順序存儲(chǔ)結(jié)構(gòu) 例： （ 34, 23, 67, 43） 34 23 67 43 ?存儲(chǔ)空間的起始位置 4 用什么屬性來(lái)描述順序表？ ?順序表的容量（最大長(zhǎng)度） ?順序表的當(dāng)前長(zhǎng)度 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 ——線性表的順序存儲(chǔ)結(jié)構(gòu) 例： （ 34, 23, 67, 43） 34 23 67 43 4 如何實(shí)現(xiàn)順序表的內(nèi)存分配？ 順序表 一維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 如何求得任意元素的存儲(chǔ)地址？ 0 … i2 i1 … n1 Max1 a1 … ai1 ai … an 空閑 長(zhǎng)度 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 一般情況下， (a1， a2， …, ai1， ai , … , an)的順序存儲(chǔ)： c Loc(ai) Loc(a1) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 0 … i2 i1 … n1 Max1 a1 … ai1 ai … an 空閑 長(zhǎng)度 Loc(ai)=Loc(a1) + (i 1) c 隨機(jī)存取 ： 在 O(1)時(shí)間內(nèi)存取數(shù)據(jù)元素 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 一般情況下， (a1， a2， …, ai1， ai , … , an)的順序存儲(chǔ)： c Loc(ai) Loc(a1) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示； 存取結(jié)構(gòu)是在一個(gè)數(shù)據(jù)結(jié)構(gòu)上對(duì)查找操作的時(shí)間性能的一種描述。 存儲(chǔ)結(jié)構(gòu)和存取結(jié)構(gòu) “順序表是一種 隨機(jī)存取 的 存儲(chǔ) 結(jié)構(gòu)”的含義為：在順序表這種存儲(chǔ)結(jié)構(gòu)上進(jìn)行的查找操作，其時(shí)間性能為 O(1)。 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 順序表類的聲明 const int MaxSize=100。 template class T //模板類 class SeqList { public: SeqList( ) 。 //構(gòu)造函數(shù) SeqList(T a[ ], int n)。 ~SeqList( ) 。 //析構(gòu)函數(shù) int Length( )。 T Get(int i)。 int Locate(T x )。 void Insert(int i, T x)。 T Delete(int i)。 private: T data[MaxSize]。 int length。 }。 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 操作接口： SeqList( ) 算法描述： SeqList::SeqList( ) { length=0。 } 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) ——無(wú)參構(gòu)造函數(shù) data length 0 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 操作接口： SeqList(T a[ ], int n) 順序表的實(shí)現(xiàn) —— 有參構(gòu)造函數(shù) 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表 數(shù)組 a 35 12 24 33 42 5 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 template class T SeqList::SeqList(T a[ ], int n) { if (nMaxSize) throw 參數(shù)非法 。 for (i=0。 in。 i+ +) data[i]=a[i]。 length=n。 } 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) ——有參構(gòu)造函數(shù) 算法描述： 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 操作接口： void Insert(int i, T x) 插入前： (a1, … , ai1, ai, … , an) 插入后： (a1, … , ai1, x , ai, … , an) 順序表的實(shí)現(xiàn) —— 插入 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) ai1和 ai之間的邏輯關(guān)系發(fā)生了變化 順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系 存儲(chǔ)位置要反映這個(gè)變化 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 33 例： （ 35， 12， 24， 42）， 在 i=2的位置上插入 33。 表滿： length=MaxSize 合理的插入位置： 1≤i≤length+1（ i指的是元素的序號(hào)） 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) ——插入 4 35 12 24 42 a1 a2 a3 a4 0 1 2 3 4 42 241233 5 什么時(shí)候不能插入 ？ 注意邊界條件 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 1. 如果表滿了，則拋出 上溢 異常 。 2. 如果元素的插入位置不合理 ， 則拋出 位置 異常 。 3. 將最后一個(gè)元素至第 i個(gè)元素分別向后移動(dòng)一個(gè)位置； 4. 將元素 x填入位置 i處； 5. 表長(zhǎng)加 1； 算法描述 —— 偽代碼 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) —— 插入 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 template class T void SeqList::Insert(int i, T x) { if (length=MaxSize) throw 上溢 。 if (i1 | | ilength+1) throw 位置 。 for (j=length。 j=i。 j) data[j]=data[j1]。 data[i1]=x。 length++。 } 算法描述 —— C++描述 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) ——插入 基本語(yǔ)句 ？ 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 最好 情況（ i=n+1）： 基本語(yǔ)句執(zhí)行 0次，時(shí)間復(fù)雜度為 O(1)。 最壞 情況（ i=1）： 基本語(yǔ)句執(zhí)行 n+1次，時(shí)間復(fù)雜度為 O(n)。 平均 情況（ 1≤i≤n+1）： 時(shí)間復(fù)雜度為 O(n)。 時(shí)間性能分析 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) ——插入 ? + + = 1 1 )= 1 ( n i i i n p ? + + + = 1 1 )= 1 ( 1 1 n i i n n 2 n =O(n) 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 操作接口： T Delete(int i) 刪除前： (a1, …, ai1,ai,ai+1,… ,an) 刪除后： (a1,… ,ai1,ai+1, … ,an) 順序表的實(shí)現(xiàn) —— 刪 除 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) ai1和 ai之間的邏輯關(guān)系發(fā)生了變化 順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系 存儲(chǔ)位置要反映這個(gè)變化 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 例：（ 35, 33, 12, 24, 42）， 刪除 i=2的數(shù)據(jù)元素。 仿照順序表的插入操作，完成： 1. 分析邊界條件； 2. 分別給出偽代碼和 C++描述的算法； 3. 分析時(shí)間復(fù)雜度。 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序表的實(shí)現(xiàn) —— 刪 除 5 35 a1 a2 a3 a4 0 1 2 3 4 42 24 12 33 4 a5 12 24 42數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 順序表的實(shí)現(xiàn) —— 按位查找 操作接口： T Get(int i) 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 … i2 i1 … n1 Max1 a1 … ai1 ai … an 空閑 n 算法描述： template class T T SeqList::Get( int i ) { if (i=1 amp。amp。 i=length) return i1。 } 時(shí)間復(fù)雜度 ？ 數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） 清華大學(xué)出版社 順序表的實(shí)現(xiàn) —— 按值查找 操作接口： int Locate(T x ) 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 5 35