【文章內(nèi)容簡介】 // ListDelete_Sq for (++p。 p = q。 ++p) *(p1) = *p。 // 被刪除元素之后的元素左移 。 // 表長減 1 return OK。 算法時間復雜度 為 : O( ListLength(L)) p = ([i1])。 // p 為被刪除元素的位置 e = *p。 // 被刪除元素的值賦給 e q = +。 // 表尾元素的位置 if ((i 1) || (i )) return ERROR。 // 刪除位置不合法 元素左移數(shù)據(jù)結(jié)構(gòu) * 36 考慮移動元素的平均情況 : 假設刪除第 i 個元素的概率為 , 則在長度為 n 的線性表中 刪除一個元素 所需移動元素次數(shù)的期望值 為： iq? ???niidl inqE1)(? ???nidl inn1)(12 1?? n若假定在線性表中任何一個位置上進行刪除的 概率 都是 相等 的，則 移動元素的期望值 為 ： 數(shù)據(jù)結(jié)構(gòu) * 37 p 21 18 30 75 42 56 87 21 18 30 75 0 p p q 87 56 p = ([i1])。 q = +。 for (++p。 p = q。 ++p) *(p1) = *p。 例如： ListDelete_Sq(L, 5, e) p 數(shù)據(jù)結(jié)構(gòu) * 38 int LocateElem_Sq(SqList L, ElemType e, Status (*pare)(ElemType, ElemType)) { // 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， // 若存在，則返回它的位序，否則返回 0 } // LocateElem_Sq O( ListLength(L) ) 算法的 時間復雜度 為： i = 1。 // i 的初值為第 1 元素的位序 p = 。 // p 的初值為第 1 元素的存儲位置 while (i = !(*pare)(*p++, e)) ++i。 if (i = ) return i。 else return 0。 ompare)(*p++, e) 利用順序表類實現(xiàn)線性表的其它操作 數(shù)據(jù)結(jié)構(gòu) * 39 例如：順序表 23 75 41 38 54 62 17 = 7 e = 38 p p p p p i 1 234850 可見，基本操作是， 將順序表中的元素 逐個和給定值 e 相比較。 數(shù)據(jù)結(jié)構(gòu) * 40 集合歸并： include include ?? SqList merge(Sqlist a, SqList b) { ElemType *ai, *bj。 int m = ( )。 int n = ( )。 SqList c(m+n)。 int i = 1。 int j = 1。 int k = ( )。 while ((i=m) (j=n)) { ai = (i)。 bj = (j)。 switch (pare(*ai, *bj)) { case –1: case 0: (++k, ai)。 i++。 break。 case 1: (++k, bj)。 j++。 break。 default:。 } // switch } // while 利用順序表類實現(xiàn)線性表的其它操作 數(shù)據(jù)結(jié)構(gòu) * 41 while (i=m) { ai = (i++)。 (++k, ai)。 } while (j=n) { bj = (j++)。 (++k, bj)。 } return c。 } // merge 數(shù)據(jù)結(jié)構(gòu) * 42 線性表的鏈式存儲 鏈接存儲的線性表（鏈表）的定義 鏈表的引入 ?數(shù)組結(jié)構(gòu)的缺點 : ?（ 1）在插入、刪除時要移動大量的結(jié)點 ?（ 2）表的大小固定。 預先在申明數(shù)組時指定，無法更改 ?原因： ?存放的連續(xù)性 ?突破 ?離散存放 ?用指針來表示元素之間的關(guān)系 。 數(shù)據(jù)結(jié)構(gòu) * 43 線性表的鏈式存儲 用鏈表實現(xiàn)線性表（非連續(xù)存儲） 線性表元素： a a a a4.... 鏈表鏈點 線性關(guān)系： a1 a2 a3 a4 指針域，指針關(guān)系 數(shù)據(jù)結(jié)構(gòu) * 44 鏈表的定義 1 鏈表的定義 結(jié)點 data link 元素域 指針域 元素域（數(shù)據(jù)元素域）：存放一個數(shù)據(jù)元素。 指針域（關(guān)系域）：存放指向下一個元素的指針 —— 元素間的關(guān)系。 元素域 + 指針域 = 結(jié)點（鏈點） 數(shù)據(jù)結(jié)構(gòu) * 45 用一組 地址任意 的存儲單元 存放 線性表中的數(shù)據(jù)元素。 以 元素 (數(shù)據(jù)元素的映象 ) + 指針 (指示后繼元素存儲位置 ) = 結(jié)點 (表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象 ) 以“ 結(jié)點的序列 ”表示線性表 ?? 稱作 鏈表 一、單鏈表 數(shù)據(jù)結(jié)構(gòu) * 46 頭指針 以線性表中第一個數(shù)據(jù)元素 的 存儲地址作為線性表的地址，稱作線性表的 頭指針 1a頭結(jié)點 a1 a2 … ... a n ^ 頭指針 有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以 指向頭結(jié)點的指針 為鏈表的頭指針 空指針 線性表為空表時， 頭結(jié)點的指針域為空 ? 數(shù)據(jù)結(jié)構(gòu) * 47 Typedef struct LNode { ElemType data。 // 數(shù)據(jù)域 struct Lnode *next。 // 指針域 } LNode, *LinkList。 LinkList L； // L 為單鏈表的頭指針 二、結(jié)點和單鏈表的描述 數(shù)據(jù)結(jié)構(gòu) * 48 class Node { protected: ElemType data。 // 數(shù)據(jù)域 Node *next。 // 指針域 public: // constructor Node(const ElemType item, Node *ptr = NULL) 。 // destructor ~ Node(void) { } // access method Node *nextNode(void) const。 { return next 。} // 返回結(jié)點的后繼 ElemType* info(void) const。 { return data 。} // 返回結(jié)點數(shù)據(jù)域的值 // modification method void insertAfter(Node *p)。 // 插入后繼結(jié)點 Node* deleteAfter(void)。 // 刪除并返回后繼結(jié)點 }。 // Node類的實現(xiàn) Node::Node(const ElemType item, Node *ptr = NULL) { data = item。 next = ptr。 } void Node::insertAfter(Node *p) { // 插入后繼結(jié)點 p ? next = next。 next = p。 } Node* Node:: deleteAfter(void) { // 刪除并返回后繼結(jié)點 Node *s = next。 next = s ? next。 return s。 } L 線性表的操作 GetElem(L, i, e) 在單鏈表中的實現(xiàn) : 21 18 30 75 42 56 ∧ p p p j 1 23 因此，查找第 i 個數(shù)據(jù)元素的基本操作為： 移動指針，比較 j 和 i 單鏈表是一種順序存取的結(jié)構(gòu)，為找第 i 個數(shù)據(jù)元素，必須先找到第 i1 個數(shù)據(jù)元素。 令指針 p 始終 指向 線性表中第 j 個數(shù)據(jù)元素 Status GetElem_L(LinkList L, int i, ElemType e) { // L是帶頭結(jié)點的鏈表的頭指針，以 e 返回第 i 個元素 } // GetElem_L 算法 時間復雜度 為 : O(ListLength(L)) p = Lnext。 j = 1。 // p指向第一個結(jié)點， j為計數(shù)器 while (p ji) { p = pnext。 ++j。 } // 順指針向后查找，直到 p 指向第 i 個元素 // 或 p 為空 if ( !p || ji ) return ERROR。 // 第 i 個元素不存在 e = pdata。 // 取得第 i 個元素 return OK。 ai1 線性表的操作 ListInsert(L, i, e) 在單鏈表中的實現(xiàn) ： 有序?qū)? ai1, ai 改變?yōu)? ai1, e 和 e, ai e ai 因此，在單鏈表中第 i 個結(jié)點之前進行插入的基本操作為 : 找到線性表中第 i1個結(jié)點，然后修改其指向后繼的指針。 可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第 i 個結(jié)點之前插入元素，修改的是第 i1 個結(jié)點的指針。 Status ListInsert_L(LinkList L, int i, ElemType e) { // L 為帶頭結(jié)點的單鏈表的頭指針，本算法 // 在鏈表中第 i 個結(jié)點之前插入新的元素 e } // LinstInsert_L 算法的 時間復雜度 為 : O(ListLength(L)) …… p = L。 j = 0。 while (p j i1) { p = pnext。 ++j。 } // 尋找第 i1 個結(jié)點 if (!p || j i1) return ERROR。 // i 大于表長或者小于 1 s = new LNode。 // 生成新結(jié)點 sdata = e。 snext = pnext。 pnext = s。 // 插入 return OK。 e ai1 ai s p 線性表 的操作 ListDelete (L, i, e)在鏈表中的實現(xiàn) : 有序?qū)?ai1, ai 和 ai, ai+1 改變?yōu)? ai1, ai+1 ai1 ai ai+1 在單鏈表中 刪除 第 i 個結(jié)點 的 基本操作 為 :找到線性表中第 i1個結(jié)點，修改其指向后繼的指針。 ai1 ai ai+1 q = pnext。 pnext = qnext。 e = qdata。 free(q)。 p q Status ListDelete_L(LinkList L, int i, ElemType e