【正文】 ； ++i ) { p = (LinkList)malloc(sizeof(LNode))； //生成新結(jié)點(diǎn) scanf(amp。 Lnext = p。pdata)； //輸入元素值 prenext = p； pre = p； //插入 } prenext = NULL； //修改尾指針 } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 32/58 用頭插法建立鏈表 ? 分析，尾插法使得每次插入的元素都是最后一個(gè)結(jié)點(diǎn)，而頭插法恰恰相反，每次插入的元素都是首元結(jié)點(diǎn)，而且這個(gè)鏈表帶有頭結(jié)點(diǎn)。L， int n) {//輸入 n個(gè)數(shù)據(jù)元素，利用尾插法建立帶頭結(jié)點(diǎn)的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； pre=L。 pre = p。即從 “ 空表 ” 的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。 分析 ：根據(jù)前面的插入操作可以看到，整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不需預(yù)先分配，而是可以由系統(tǒng)應(yīng)需求即時(shí)生成。amp。 j=0。L, int i, ElemType amp。 free(q)。 分析 ：在單鏈表中刪除結(jié)點(diǎn)其操作類似于插入操作，無(wú)需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語(yǔ)句描述即為： q=pnext。amp。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 27/58 算法描述如下： void ListInsert_L(LinkList amp。 分析 ：由于鏈表的特殊性，在某個(gè)元素前插入一個(gè)元素，無(wú)需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語(yǔ)句描述即為： snext = pnext。amp。 ^Lana1a2…L^( a ) 非 空 表( b ) 空 表帶 頭 結(jié) 點(diǎn) 的 單 鏈 表數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 25/58 ① 查找：在以 L為頭結(jié)點(diǎn)的單鏈表中查找值為 e的結(jié)點(diǎn)。 struct LNode *next。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn) ：邏輯上相鄰的元素在物理位臵上不一定相鄰 ,沒(méi)有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn) , 但也失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。 // 插入 La的剩余元素 while( j ) [k++] = [j++]。 else [k++] = [j++]。amp。Lc) {// 已知順序線性表 La和 Lb的元素按值非遞減排列， // 歸并 La和 Lb得到新的順序線性表 Lc， Lc的元素也按值非遞減排列 i = j = k = 0。amp。 void Union(SqList amp。 ； //表長(zhǎng)減 1 }// ListDelete_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 18/58 插入 /刪除操作時(shí)間復(fù)雜度分析 ?基本操作：移動(dòng)元素操作 ?順序表進(jìn)行插入及刪除操作的時(shí)間復(fù)雜度為 O(n)。 j。 //i值不合法 e=[i1]。L， int i， ElemType amp。 [i1] = e。 j=i1。 //初始存儲(chǔ)容量 }//InitList_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 14/58 （ 2）插入：在線性表的第 i個(gè)元素前插入一個(gè)元素 分析 ：若要在線性表的第 i個(gè)元素前插入一個(gè)元素，除非 i=n+1，否則，須將第 n至第 i（共 ni+1）個(gè)元素依次往后移動(dòng)一個(gè)位臵，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 插入 25 25 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 9 表的長(zhǎng)度增加 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 15/58 順序表的插入 void ListInsert_Sq(SqList amp。 //存儲(chǔ)分配失敗 = 0。L){ // 構(gòu)造一個(gè)空的線性表 L = (ElemType *) malloc (LIST_INIT_SIZE *sizeof(ElemType))。 //當(dāng)前分配存儲(chǔ)容量 }SqList。 //存儲(chǔ)空間基址 int length。 3）做插入或刪除操作時(shí)需移動(dòng)大量元素，效率不高，適合做查詢操作。(j=Lb_len)) {//La和 Lb均非空 GetElem(La， i， ai)； GetElem(Lb， j， bj)； if(ai=bj) { ListInsert(Lc， ++k， ai)； ++i； } else { Listlnsert(Lc， ++k， bj)； ++j； } } while(i=Lalen) { GetElem(La， i++， ai)； ListInsert(Lc， ++k， ai)； } while(j=Lb_len) { GetElem(Lb， j++， bj)； ListInsert(Lc， ++k， bj)； } }//MergeList 該算法的時(shí)間復(fù)雜度為： O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 9/58 二、線性表的順序表示與實(shí)現(xiàn) 線性表的順序表示描述 類型定義 基本操作 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 10/58 線性表順序表示 ：是指用一組 地址連續(xù) 的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。 InitList(Lc)； i=j=1； k=0； La_len=ListLength(La)； Lb_len=ListLength(Lb)； while((i=La_len)amp。Lc) {//已知線性表 La和 Lb中的數(shù)據(jù)元素按值非遞減排列。為使 LC中元素按值非遞減有序排列，可設(shè)兩個(gè)指針 i和 j分別指向 LA和 LB中某個(gè)元素，若設(shè) i當(dāng)前所指的元素為 a， j當(dāng)前所指的元素為 b，則當(dāng)前應(yīng)插入到 LC中的元素 c為： 顯然，指針 i和 j的初值均為 1，在所指元素插入 LC之后，在 LA或 LB中順序后移。e) 刪除線性表中的第 i個(gè)元素； … … }ADT List 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 6/58 利用上面的基本操作，還可以進(jìn)行一些更復(fù)雜的操作，例如： 已知線性表 La和 Lb中的元素按值非遞減有序排列，現(xiàn)要求將 La和 Lb歸并為一個(gè)新的線性表 Lc，且 Lc中的數(shù)據(jù)元素仍按值非遞減有序排列。L, i, x) 在線性表中第 i個(gè)元素之后 (或之前 ) 插入一個(gè)新元素 x； ListDelete(amp。L) 初始化線性表 L，設(shè)臵為空表； ListLength(L) 求線性表的長(zhǎng)度 ； GetElem(L, i, amp。 對(duì)于 ai，當(dāng) 1i≤n 時(shí)，它有一個(gè)直接前驅(qū) ai1；當(dāng) 1≤in 時(shí)，它有一個(gè)直接后繼 ai+1。 根據(jù)它們之間的關(guān)系可以排成一個(gè)線性序列，記作： (a1， a2， … ， an) 這里的 ai(1≤i≤n)屬于 同一數(shù)據(jù)對(duì)象 ， n代表線性表的 表長(zhǎng) ，即線性表中數(shù)據(jù)元素的個(gè)數(shù)。 一、線性表的定義 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 4/58 1. 線性表的定義 線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 1/58 第 2章 線性表 學(xué)習(xí)目的與要求： 1．了解線性表的邏輯結(jié)構(gòu)； 2．掌握順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法； 3．掌握線性表在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本操作：查找、插入和刪除的算法； 4．能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合； 5．理解靜態(tài)鏈表的定義及使用方法，并區(qū)分與單鏈表的不同。 數(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)