【正文】 Llast+2) ) /*首先判斷插入位置是否合法 */ { printf(“插入位置 i值不合法 ” )； return(ERROR)。 2022/8/26 15 插入 算法示意圖 已知： 線性表 (4,9,15,28,30,30,42,51,62)，需在第 4個(gè)元素之前插入一個(gè)元素 “ 21”。 /*若沒找到 ， 則返回空序號(hào) */ } 2022/8/26 14 插入操作 線性表的插入運(yùn)算是指在表的第 i (1≤i≤n+1)個(gè)位置，插入一個(gè)新元素 e，使長(zhǎng)度為 n的線性表 (e1， … ， ei1， ei， … ， en) 變成長(zhǎng)度為 n+1的線性表（ e1， … ,ei1， e， ei， … ， en）。 /*順序掃描表 ， 直到找到值為 key的元素 ,或掃描到表尾而沒找到 */ if (i=) return(i)。amp。 線性表的查找運(yùn)算算法 描述為： 2022/8/26 13 線性表的查找運(yùn)算 int Locate(SeqList L， ElemType e) { i=0 。 2022/8/26 11 線性表順序存儲(chǔ)結(jié)構(gòu)的基本運(yùn)算 ? 線性表的基本運(yùn)算 ： 1. 查找操作 2. 插入操作 3. 刪除操作 4. 順序表 合并算法 ? 線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)分析 2022/8/26 12 查找操作 線性表的兩種基本查找運(yùn)算 1. 按序號(hào)查找 GetData(L,i)： 要求查找線性表 L中第 i個(gè)數(shù)據(jù)元素，其結(jié)果是 [i1]或 Lelem[i1]。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為 順序表 。 操作結(jié)果：將表 L置為空表。 操作結(jié)果：將 L銷毀。 操作結(jié)果：將 L初始化為空表。 ?有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系 ai,ai+1。 線性表的邏輯結(jié)構(gòu)圖為： 2022/8/26 5 線性表的特點(diǎn) ?同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè) ai必須屬于同一數(shù)據(jù)對(duì)象。 2022/8/26 2 第 2章 線性表 ? 線性表的概念及運(yùn)算 ? 線性表的順序存儲(chǔ) ? 線性表的鏈?zhǔn)酱鎯?chǔ) ? 一元多項(xiàng)式的表示及相加 2022/8/26 3 線性表的概念及運(yùn)算 ? 線性表的邏輯結(jié)構(gòu) ? 線性表的抽象數(shù)據(jù)類型定義 2022/8/26 4 線性表的定義 線性表 (Linear List)是由 n (n≥ 0)個(gè)類型相同的數(shù)據(jù)元素 a1,a2,… ， an組成的有限序列 ， 記做（ a1,a2,… ， ai1， ai， ai+1， … ， an） 。2022/8/26 1 數(shù)據(jù)結(jié)構(gòu)課件 西北大學(xué)計(jì)算機(jī)系 本演示文稿可能包含觀眾討論和即席反應(yīng)。使用 PowerPoint 可以跟蹤演示時(shí)的即席反應(yīng)， ? 在幻燈片放映中，右鍵單擊鼠標(biāo) ? 請(qǐng)選擇“會(huì)議記錄” ? 選擇“即席反應(yīng)”選項(xiàng)卡 ? 必要時(shí)輸入即席反應(yīng) ? 單擊“確定”撤消此框 此動(dòng)作將自動(dòng)在演示文稿末尾創(chuàng)建一張即席反應(yīng)幻燈片，包括您的觀點(diǎn)。 數(shù)據(jù)元素之間是一對(duì)一的關(guān)系 ， 即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼 。 ?有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長(zhǎng)度就是表中數(shù)據(jù)元素的個(gè)數(shù)。 2022/8/26 6 線性表的抽象數(shù)據(jù)類型定義 ? 抽象數(shù)據(jù)類型定義 ： ADT LinearList{ 數(shù)據(jù)元素 ： D={ai| ai∈ D0, i=1,2,… ， n n≥0 ， D0為某一數(shù)據(jù)對(duì)象 } 關(guān)系 ：Ｓ＝｛ ai,ai+1 | ai, ai+1∈ D0， i=1,2, … ,n1｝ 基本操作 ： （ 1） InitList（ L） 操作前提： L為未初始化線性表。 （ 2） DestroyList(L) 操作前提：線性表 L已存在。 （ 3） ClearList(L) 操作前提：線性表 L已存在 。 ……… }ADT LinearList 2022/8/26 7 線性表的順序存儲(chǔ) ? 線性表的順序存儲(chǔ)結(jié)構(gòu) ? 線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算 2022/8/26 8 順序存儲(chǔ)結(jié)構(gòu)的定義 線性表的順序存儲(chǔ) 是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。 假設(shè)線性表中每個(gè)元素占 k個(gè)單元，第一個(gè)元素的地址為 loc(a1)，則第 k個(gè)元素的地址為： loc(ai) =loc(a1)+(i1) k 2022/8/26 9 順序存儲(chǔ)結(jié)構(gòu)示意圖 存儲(chǔ)地址 內(nèi)存空間狀態(tài) 邏輯地址 Loc(a1) a1 1 Loc(a1)+(21)k a2 2 … … … loc(a1)+(i1)k ai i … … … loc(a1)+(n1)k an n ... loc(a1)+(maxlen1)k 空閑 2022/8/26 10 順序存儲(chǔ)結(jié)構(gòu)的 C語言定義 define maxsize=線性表可能達(dá)到的最大長(zhǎng)度； typedef struct { ElemType elem[maxsize]； /* 線性表占用的數(shù)組空間 */ int last； /*記錄線性表中最后一個(gè)元素在數(shù)組 elem[ ] 中的位置 （ 下標(biāo)值 ） ， 空表置為 1*/ } SeqList； 注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo) ， 如 a1的序號(hào)為 1， 而其對(duì)應(yīng)的數(shù)組下標(biāo)為 0。 2. 按內(nèi)容查找 Locate（ L,e） : 要求查找線性表 L中與給定值 e相等的數(shù)據(jù)元素，其結(jié)果是：若在表 L中找到與 e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè) “ 空序號(hào) ” ，如 1。 /*i為掃描計(jì)數(shù)器 ， 初值為 0， 即從第一個(gè)元素開始比較 */ while ((i=)amp。([i]!=e) ) i++。 /*若找到值為 e的元素 ， 則返回其序號(hào) */ else return(1)。 線性表的插入運(yùn)算算法 。則需要將第 9個(gè)位置到第 4個(gè)位置的元素依次后移一個(gè)位置，然后將 “ 21”插入到第 4個(gè)位置， 序號(hào) 移動(dòng)元素 插入元素 1 2 3 4 5 6 7 8 10 9 4 9 15 28 30 30 42 51 62 4 9 15 28 30 30 42 62 51 4 9 15 21 28 30 30 42 62 51 2022/8/26 16 插入運(yùn)算 int InsList(SeqList *L,int i,ElemType e) { int k。 } if(Llast=maxsize1) { printf(“表已滿無法插入 ” )； return(ERROR)。k=i1。 Lelem[i1]=e。 return(OK)。 2022/8/26 17 刪除操作 線性表的刪除運(yùn)算是指將表的第 i(1≤ i≤ n)個(gè)元素刪去，使長(zhǎng)度為 n的線性表 (e1， … ,ei1， ei，ei+1， … ， en)，變成長(zhǎng)度為 n1的線性表(e1， … ,ei1， ei+1， … ， en)。 序號(hào) 1 2 3 4 5 6 7 8 10 9 4 9 15 21 28 30 30 42 62 51 4 9 15 21 30 30 42 51 62 刪除 28后 2022/8/26 19 刪除 算法 int DelList(SeqList *L,int i,ElemType *e) /*在順序表 L中刪除第 i個(gè)數(shù)據(jù)元素 ， 并用指針參數(shù) e返回其值 */ { int k。 /* 將刪除的元素存放到 e所指向的變量中 */ for(k=i。k++) Lelem[k1]= Lelem[k]。 return(OK)。 ? 算法思想 ： 設(shè)表 LC是一個(gè)空表，為使 LC也是非遞減有序排列，可設(shè)兩個(gè)指針 i、 j分別指向表 LA和 LB中的元素，若[i][j]，則當(dāng)前先將 [j]插入到表 LC中，若[i]≤ [j] ，當(dāng)前先將 [i]插入到表 LC中，如此進(jìn)行下去，直到其中一個(gè)表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表 LC中。j=0。 while(i=LAlastamp。j=LBlast) if(LAelem[i]=LBelem[j]) { LCelem[k]= LAelem[i]。 k++。 j++。 } while(i=LAlast) /*當(dāng)表 LA長(zhǎng)則將表 LA余下的元素賦給表 LC*/ { LCelem[k]= LAelem[i]。 k++。 j++。 } LClast=LAlast+LBlast。 缺點(diǎn)： ，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低； ，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。 2022/8/26 23