【正文】 // 以 an為首q=head。例如：在線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) 的QIAN, SUN之間 插入新元素插入新元素 LIU， 可以這樣實(shí)現(xiàn)：S[7].next = S[3].next；；Step2:將 QIAN的游標(biāo)換為新元素 LIU的下標(biāo)：S[3].next = 7Step1:將 QIAN的游標(biāo)值存入 next的游標(biāo)中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi頭結(jié)點(diǎn)頭結(jié)點(diǎn)LIU 677本章小結(jié)1. 線性結(jié)構(gòu) (包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn) ：2. 僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。雙向循環(huán)鏈表空表非空表 a1 a2 … ... a n雙向鏈表的操作特點(diǎn)：“ 查詢 ” 和單鏈表相同。} O(n)7. 查找具有給定值的第一個(gè)元素 bool Find(LNode* HL, ElemTypeamp。 P = P next。 Lnext = p。for( i=1。 // 刪除位置不合理q = pnext。 // 插入return OK。 ++j。 // 指針域 } LNode, *LinkList。將所有位置的執(zhí)行時(shí)間相加，然后取平均。 L) {return (L. length ==0)。 ++p) *(p1) = *p。L, int i, ElemType amp。([])。 // i 的初值為第 1 元素的位序p = 。線性表的存儲(chǔ)結(jié)構(gòu)主要有如下兩類：(1)順序存儲(chǔ)結(jié)構(gòu) (2)鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu) 線性表類型的實(shí)現(xiàn) —— 順序映像 用一組 地址連續(xù) 的存儲(chǔ)單元 依次存放 線性表中的數(shù)據(jù)元素 （邏輯關(guān)系相鄰 , 物理位置相鄰。 i = Lb_len。 3． 若不存在，則插入之。（線性表置空）PutElem( amp。用 e 返回 L中第 i 個(gè)元素的值。銷毀線性表 L。 ” 但狐貍從早到晚進(jìn)進(jìn)出出了 1000次，仍沒有找到兔子。L )操作結(jié)果：構(gòu)造一個(gè)空的線性表 L。若 cur_e是 L的元素，但不是最后一個(gè)，則用 next_e返回它的后繼，否則操作失敗，next_e無定義。e) ClearList( amp。例 21 要求對(duì)線性表作如下操作：擴(kuò)大線性表 LA， 將 存在于線性表LB 中 而 不存在于線性表 LA 中 的數(shù)據(jù)元素 插入到線性表 LA 中 去。 } // union GetElem(Lb, i, e)。 // 取 Lb中第 i個(gè)數(shù)據(jù)元素賦給 eif (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e)。 = LIST_INIT_SIZEreturn OK。L, int i, ElemType e) { // 在順序表 L的第 i 個(gè)元素之前插入新的元素 e, // i 的合法范圍為 1≤i≤+1} // ListInsert_Sq 算法時(shí)間復(fù)雜度 為 :O( ListLength(L) )q = amp。 // 插入 ep線性表操作 ListDelete(amp。q = +。 清空操作 void ClearList(SqList amp。} //注意序號(hào)與下標(biāo)的不同 順序表操作的效率分析167。答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭 指針 的值為 空 時(shí)表示空表；^頭指針無頭結(jié)點(diǎn)^頭指針 頭 結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭 結(jié)點(diǎn) 的 指針域?yàn)榭?時(shí)表示空表。 // p指向第一個(gè)結(jié)點(diǎn)， j為計(jì)數(shù)器while (p amp。 // 生成新結(jié)點(diǎn)sdata = e。 j i1) { p = pnext。先挖 “ 坑 ”, 后種 “ 蘿卜 ” ！新手特別容易忘記?。L = (LinkList) malloc (sizeof (LNode))。 i) { p = (LinkList) malloc (sizeof (LNode))。{ P=HLnext。 while(P!=NULL) { coutHLdata 。 // 指向后繼的指針域} DuLNode, *DuLinkList。 //這是一維結(jié)構(gòu)型數(shù)組例 2：一 線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) ， 用靜態(tài)鏈表如何表示？data1ZHAO 3LI 5QIAN 6WU 0ZHOU 4SUN 2…… ……0123456……1000next 說明 1： 假設(shè) S為 SLinkList型變量，則S[MAXSIZE] 為一個(gè)靜態(tài)鏈表；S[0].next則表示第 1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。 //前驅(qū)變后繼 q=p。 q=p?！　?鏈?zhǔn)酱鎯?chǔ)時(shí)， 相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。 pnext = s。 while(p!=NULL) if (pdata==item) { return i。 exit(1)。 HL) { HL=NULL。 p=pnext； //讓指針變量 P指向后一個(gè)結(jié)點(diǎn)cinpdata。 free(q)。e)在鏈表中的實(shí)現(xiàn) :有序?qū)?ai1, ai 和 ai, ai+1 改變?yōu)? ai1, ai+1ai1 ai ai+1 在單鏈表中 刪除第 i 個(gè)結(jié)點(diǎn) 的 基本操作 為 :找到線性表中第 i1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。 // 取得第 i 個(gè)元素return OK。L, i, e) // 插入 數(shù)據(jù)元素ListDelete(amp。 （ n+1）＝n/2≈ O(n) 共有多少種插入形式 ?—— 連頭帶尾有 n+1種!同理可證 ： 順序表刪除一元素的時(shí)間效率為 :T（ n)=(n1)/2 ≈ O(n) 插入效率：刪除效率：教材 P25有對(duì)執(zhí)行效率的推導(dǎo)： （與課本略有區(qū)別）即插入、刪除算法的平均時(shí)間復(fù)雜度為 O(n)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表 順序存儲(chǔ)結(jié)構(gòu)特點(diǎn) ： 邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)： 可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)： 在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。} 若 L為空表，返回真，否則返回假167?！獭躺钲谌A為公司來某校招聘面試題解： void SortA(SeqList *L){ int i=0, zerosum =0。 ++p) *(p1) = *p。 // 插入位置及之后的 元素右移*q = e。 !(*pare)(*p++, e)) ++i。 // 俗稱 順序表define LIST_INIT_SIZE 80 // 線性表存儲(chǔ)空間的初始分配量define LISTINCREMENT 10 // 線性表存儲(chǔ)空間的分配增量ElemType *elem。試改變結(jié)構(gòu)，以 有序表 表示集合。 // La中不存在和 e 相同的數(shù)據(jù)元素，則插入之void union(List amp。L中第 i個(gè)元素賦值同 e的值。若這樣的元素不存在，則返回值為 0。next_e ) GetElem( L, i, amp。 → 可表示為：（ a1 , a2 , ……, an ） 特點(diǎn)：1．集合中必存在唯一的一個(gè) “第一元素 ”；2．集合中必存在唯一的一個(gè) “最后元素 ” ；3．除最后元素在外，均有 唯一的后繼 ；4．除第一元素之外，均有 唯一的前驅(qū) 。分析 ： 數(shù)據(jù)元素都是同類型（ 字母 ）， 元素間關(guān)系是線性的。若 cur_e是 L的元素，但不是第一個(gè)，則用 pre_e 返回它的前驅(qū)，否則操作失敗， pre_e無定義。e )ListInsert( amp。刪除 L的第 i個(gè)元素，并用e返回其值， L的長(zhǎng)度減 1。例 22集合 B 集合 A從集合 B 取出物件放入集合 A要求集合 A中 同樣物件不能有兩件以上因此， 算法的