【正文】 都要改變 space[0].cur的值 scanf(amp。space， int amp。 為使算法清晰起見，我們先給出三個(gè)過程： 1)將整個(gè)數(shù)組空間初始化成一個(gè)鏈表； 2)從備用空間取得一個(gè)結(jié)點(diǎn)； 3)將空閑結(jié)點(diǎn)鏈結(jié)到備用鏈表上 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 37/58 void InitSpace_SL(SLinkList amp。pb) //若兩者均不為空 if(padata = pbdata) { pcnext = pa； pc = pa； pa = panext； } else { pcnext = pb； pc = pb； pb = pbnext。La， LinkList amp。 L ^ Lp a1^ a2p La1^ a2p . . . 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 33/58 用頭插法建立鏈表的算法描述如下： void CreateList_L(LinkList amp。 for(i = 0； i n； ++i) { p = (LinkList)malloc(sizeof(LNode))； scanf(amp。建立鏈表的方法有頭插法和尾插法，用尾插法建立鏈表的過程如下所示： La1a2…^anpre pre p p prenext = p。ji1) //尋找第 i個(gè)結(jié)點(diǎn)，及其前趨 p { p=pnext； ++j； } if( !(pnext) || ji1) exit(0)； //刪除位置不合理 q = pnext； pnext = qnext； //刪除并釋放結(jié)點(diǎn) e = qdata； free(q)； } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 30/58 ④ 建表：根據(jù)給定的元素值，建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。e) {//在帶頭結(jié)點(diǎn)的線性表 L中刪除第 i個(gè)結(jié)點(diǎn) p=L。 pnext=qnext。L, int i, ElemType e) {//在帶頭結(jié)點(diǎn)的線性表 L的第 i個(gè)結(jié)點(diǎn)之前插入新的元素 e p=L； j=0； while(pamp。 pdata != e) p = pnext； return p； } （ 4） 線性鏈表的基本操作 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 26/58 ② 插入：在以 L為頭結(jié)點(diǎn)的單鏈表中的第 i個(gè)元素前插入一個(gè)元素 e。 }LNode, *LinkList。 // 插入 Lb的剩余元素 }// MergeList_Sq 算法 MergeList的時(shí)間復(fù)雜度為 O(+) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 21/58 三、線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 線性鏈表 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 22/58 線性鏈表 順序存儲(chǔ)結(jié)構(gòu)弱點(diǎn) ：在作插入或刪除操作時(shí)需要移動(dòng)大量元素。 j ) // 歸并 if ( [i] = [j]) [k++] = [i++]。 ([j] != [i])) j++； if (j = ) [k++] = [i]； } = k； }//Union 算法 union的時(shí)間復(fù)雜度為 O( ) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 20/58 （ 5）兩個(gè)有序表的合并 void MergeList_Sq(SqList La， SqList Lb， SqList amp。 ?插入操作移動(dòng)元素次數(shù)的期望值 )1(11??? ???inpE ni iis?刪除操作移動(dòng)元素次數(shù)的期望值 )(1inqE ni idl?? ???等概率情況下 ( , ) 11?? npi nqi 1?111 ( 1 )12nisinE n in??? ? ? ?? ?111()2ndlinE n in ??? ? ??數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 19/58 （ 4）兩個(gè)順序表的合并 假設(shè)利用兩個(gè)線性表 LA和 LB分別表示兩個(gè)集合 A和 B(即：線性表中的數(shù)據(jù)元素即為集合中的成員 )，現(xiàn)要求一個(gè)新的集合 A=AUB。 for(j = i1。 //插入 e ++； //表長增 1 } ListInsert_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 16/58 （ 3）刪除：刪除線性表中的第 i個(gè)元素 分析 ：若要?jiǎng)h除線性表中的第 i個(gè)元素，除非 i=n，否則，須將第 i+1至第 n（共 ni）個(gè)元素依次往前移動(dòng)一個(gè)位置，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 刪除 24 12 13 21 28 30 42 77 1 2 3 4 5 6 7 序號(hào) 數(shù)據(jù)元素 表的長度減少 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 17/58 順序表的刪除 void ListDelete_Sq(SqList amp。L， int i， ElemType e) {//在順序表 L的第 i個(gè)元素之前插入新的元素 e if(i1||i+1) exit(0)； //插入位置不合法 if(=) //當(dāng)前存儲(chǔ)空間已滿，增加空間 { newbase=(ElemType*)realloc(， (+LISTINCREMENT)*sizeof(ElemType))； if(!newbase) exit(0)； //存儲(chǔ)分配失敗 =newbase； //新基址 +=LISTINCREMENT； //增加存儲(chǔ)容量 } for(j = 。 if ( ! ) exit (0)。 //當(dāng)前長度 int listsize。 存儲(chǔ)結(jié)構(gòu)示意圖 順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)： 所以：線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 1）線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）一致； 2）只要確定了存儲(chǔ)線性表的起始位臵，可以計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。 //歸并 La和 Lb得到新的線性表 Lc， Lc的數(shù)據(jù)元素也按值非遞減排列。 例如，設(shè) La=(3， 5， 8， 11) Lb=(2， 6， 8， 9， 11， 15， 20) 則 Lc=(2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20) 分析 ：從上述問題要求可知， LC中的數(shù)據(jù)元素或是 LA中的數(shù)據(jù)元素，或是 LB中的數(shù)據(jù)元素，只要先設(shè) LC為空表，然后將 LA和 LB中的元素按照順序逐個(gè)插入到 LC中即可。e) 求表 L中的第 i個(gè)元素，結(jié)果由 e返回； ListInsert(amp。當(dāng) n=0時(shí)，線性表為 空表 。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 2/58 基本內(nèi)容 一、線性表的定義 二、線性表的順序表示與實(shí)現(xiàn) 三、線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 四、一元多項(xiàng)式的表示及相加 五、本章小結(jié) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 3/58 線性結(jié)構(gòu)的特點(diǎn) ：在數(shù)據(jù)元素的非空有限集中 （ 1）存在惟一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素； （ 2）存在惟一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素； （ 3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)； （ 4）除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼。 一、線性表的定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 4/58 1. 線性表的定義 線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。 對(duì)于 ai，當(dāng) 1i≤n 時(shí)，它有一個(gè)直接前驅(qū) ai1；當(dāng) 1≤in 時(shí)，它有一個(gè)直接后繼 ai+1。L, i, x) 在線性表中第 i個(gè)元素之后 (或之前 )