【正文】 i++。 Llast=Llast1。k=Llast。 while(iLlast) {j=i+1。 {int i,j,k。 為此 ， 算法中需設(shè)兩重循環(huán) ， 外層控制清除的趟數(shù) ， 內(nèi)層控制每趟的檢查范圍 。 舉例 —?jiǎng)h除順序表中的重復(fù)元素 ?一個(gè)順序表中可能含有一些值相同的重復(fù)元素 ， 題目要求對(duì)于值相同的重復(fù)元素只保留位序最小的一個(gè)而刪除其它多余的元素 。 ?當(dāng) i=n時(shí)最好不需移動(dòng) ， 當(dāng) i=1時(shí)最壞需移動(dòng) n1次 ，在等概率的情況下需平均移動(dòng)元素 (n1)/2次 。 } }/*delete*/ 刪除運(yùn)算算法的時(shí)間復(fù)雜度 ?由刪除過(guò)程可以看出 ， 通過(guò)元素 ai+1到 an的依次前移就達(dá)到了刪除 ai的目的 。j++) Ldata[j1]=Ldata[j]。 else {for(j=i+1。 {int j。 在順序表中刪除第 i個(gè)元素過(guò)程 刪除運(yùn)算的算法描述 void delete(L,i) sequenlist *L。 delete(L,i) ?刪除運(yùn)算是把順序表中第 i個(gè)元素刪掉 ， 使順序表的長(zhǎng)度由 n變?yōu)?n1， 其部分元素的邏輯關(guān)系和存儲(chǔ)位置也發(fā)生相應(yīng)變化 ， 即 由 （ a1,a2,… ,ai1,ai,ai+1,… ,an） 變成為 （ a1,a2,… ,ai1,ai+1,… ,an） 。 當(dāng) i=n+1時(shí)不需移動(dòng)元素是最好情況 ， 當(dāng) i=1時(shí)需移動(dòng)元素 n次是最壞情況 ， 在插入位置等概率分布時(shí)的平均移動(dòng)次數(shù)為 n/2。 } }/*insert*/ 插入運(yùn)算算法的時(shí)間復(fù)雜度 ?算法中的數(shù)據(jù)元素移動(dòng)是從第 n個(gè)元素到第 i個(gè)元素依次后移的 。 Ldata[i]=x。j=i。 else if(Llast=MAXSIZE) printf(“表已滿(mǎn) ， 發(fā)生上溢 \n”)。 {int j。 elemtype x。 ?除非 i=n+1， 否則必須將位序?yàn)?i,i+1,…… ,n的數(shù)據(jù)元素向后移動(dòng)一個(gè)元素位置 ， 空出第 i個(gè)位置插入新元素 x；在 i=n+1時(shí)直接將新元素 x插入表尾 。 插入的結(jié)果使 x 在順序表中第 i個(gè)元素位置上 ， 使順序表的長(zhǎng)度由 n變?yōu)?n+1。 所以算法的時(shí)間復(fù)雜度為 O(n)。 /*找到值為 x的元素返回它的位序 i*/ } /*locate*/ ?該算法的主要時(shí)間花費(fèi)在于查找比較的循環(huán) 。 定位序 （續(xù)） if(iLlast) return 0。amp。 {int i=1。 ?其算法描述如下： int locate(L,x) sequenlist *L。 1. 定位序 locate(L,x) ?定位序即按值查找 ， 確定元素 x在順序表 L中的位置 。 例如： ?置空表就是使表長(zhǎng)為 0， 即 (*L).last=0； ?求表長(zhǎng)就是讀出 last域的值 ， 即 (*L).last； ?取元素就是按位序取出 data 域中相應(yīng)元素 ， 即(*L).data[i]；取前趨就是將元素 x的位序前一個(gè)元素取出 ，即 (*L).data[locate(L,x)1]； ?取后繼即取出 (*L).data[locate(L,x)+1]的值等 。 順序表 線(xiàn)性表的基本概念 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) ——順序表 順序表上的基本運(yùn)算 順序表上的基本運(yùn)算 ?在定義了線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)之后 ， 就可以討論各種基本運(yùn)算的實(shí)現(xiàn)問(wèn)題了 。 ?即把順序表類(lèi)型 sequenlist描述為一個(gè)結(jié)構(gòu)體 ， 域data數(shù)組存放表中的數(shù)據(jù)元素 ， 域 last存放表長(zhǎng) ，data[last]存放表中最后一個(gè)元素 。 int last。 ?為了討論方便 ， 我們假定元素是從數(shù)組下標(biāo)為 1的位置開(kāi)始存放 ， 即 last=0時(shí)為空表 。 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 順序表的順序存儲(chǔ)結(jié)構(gòu)（續(xù)） ?由于在高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組 （ 或向量 ）在計(jì)算機(jī)內(nèi)分配的是一片連續(xù)的存儲(chǔ)單元 ， 所以可借助一維數(shù)組為順序表開(kāi)辟存儲(chǔ)空間存儲(chǔ)表中的數(shù)據(jù)元素 。 線(xiàn)性表的存儲(chǔ)地址計(jì)算公式 ?由于線(xiàn)性表中的數(shù)據(jù)元素具有相同的類(lèi)型 ， 所以可以很容易地確定順序表中每個(gè)數(shù)據(jù)元素在存儲(chǔ)空間中與起始單元的相對(duì)位置； ?假定線(xiàn)性表中每個(gè)數(shù)據(jù)元素需要占用 c個(gè)存儲(chǔ)單元 ，loc(a1)是第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址 （ 也稱(chēng)作基地址 ） ， 則第 i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址可由下式確定： loc(ai)=loc(a1)+(i1)*c ?其中： 1≤i≤length(L)+ 1。 ?這組地址連續(xù)的存儲(chǔ)空間的大小依線(xiàn)性表中的數(shù)據(jù)元素個(gè)數(shù)而定 ， 線(xiàn)性表中第一個(gè)元素存放在這組空間的開(kāi)始處 ， 第二個(gè)元素緊跟著存放在第一個(gè)元素之后 ， …… ， 余類(lèi)推 。 ?這里所給出的運(yùn)算是定義在邏輯結(jié)構(gòu)上的抽象運(yùn)算 ， 而運(yùn)算的實(shí)現(xiàn)要依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu) 。 ?利用這些基本運(yùn)算 ， 可以實(shí)現(xiàn)線(xiàn)性表的其它較復(fù)雜運(yùn)算 ，如線(xiàn)性表的分拆 、 合并 、 逆置等 。 線(xiàn)性表的基本運(yùn)算（續(xù)） ?插入 insert(L,x,i)：在線(xiàn)性表 L中第 i個(gè)位置上插入值為 x的新元素 ， 使表長(zhǎng)增 1；要求 1≤i≤length(L)+1。 ?取后繼 next(L,x)：取出線(xiàn)性表 L中值為 x的元素的后繼元素；要求 x的位序小于 length(L)。 ?取元素 get(L,i)：取出線(xiàn)性表 L中第 i個(gè)數(shù)據(jù)元素；要求 i≤length(L)。 線(xiàn)性表的基本運(yùn)算 ?置空表 setnull(L)：將線(xiàn)性表 L置為空表 。 線(xiàn)性表的形式化定義 ?線(xiàn)性表的形式化定義如下： Linear List=(D,R) ?其中： D={ai|ai∈ Do， i=1， 2， …… ， n， n≥ 0}；R={ai1， ai|ai1,ai∈ Do， i=2， 3， …… ， n}；Do為某個(gè)數(shù)據(jù)對(duì)象 。 線(xiàn)性表的例子 ?線(xiàn)性表中的數(shù)據(jù)元素 （ 結(jié)點(diǎn) ） 可以是一個(gè)數(shù) 、 一個(gè)符號(hào) 、一頁(yè)書(shū) 、 一個(gè)記錄等 。 表中有且僅有一個(gè)第一個(gè)結(jié)點(diǎn) ， 它沒(méi)有前趨而只有一個(gè)后繼；有且僅有一個(gè)最后一個(gè)結(jié)點(diǎn) ， 它沒(méi)有后繼而只有一個(gè)前趨；其余結(jié)點(diǎn)都只有一個(gè)前趨和一個(gè)后繼 。 第 3章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu) 順序表 鏈表 棧 隊(duì)列 廣義表 順序表 線(xiàn)性表的基本概念 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) ——順序表 順序表上的基本運(yùn)算 線(xiàn)性表的基本概念 ?線(xiàn)性表 （ Linear List） 是一種最簡(jiǎn)單最常用的數(shù)據(jù)結(jié)構(gòu) 。算法與數(shù)據(jù)結(jié)構(gòu) 第 3章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu) ?簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu) ， 包括順序表 、 鏈表 、 棧 、 隊(duì)列和廣義表 ， 它們和上一章介紹過(guò)的數(shù)組和串一起都同屬于 線(xiàn)性結(jié)構(gòu) 。 ?在線(xiàn)性結(jié)構(gòu)中 ， 數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的次序關(guān)系 ， 其邏輯特征為： ?存在一個(gè)惟一地被稱(chēng)作 “ 第一個(gè) ” 的數(shù)據(jù)元素； ?存在一個(gè)惟一地被稱(chēng)作 “ 最后一個(gè) ” 的數(shù)據(jù)元素； ?除第一個(gè)之外 ， 每個(gè)數(shù)據(jù)元素都只有一個(gè)前趨； ?除最后一個(gè)之外 ， 每個(gè)數(shù)據(jù)元素都只有一個(gè)后繼 。 ?一個(gè)線(xiàn)性表是由 n（ n≥0） 個(gè)相同類(lèi)型數(shù)據(jù)元素 （ 結(jié)點(diǎn) ） 組成的 有限序列 。 ?根據(jù)結(jié)點(diǎn)之間的關(guān)系可以排成一個(gè)線(xiàn)性序列： （ a1， a2， a3， a4， …… ， an） ?其中： a1為第一個(gè)結(jié)點(diǎn) ， an為最后一個(gè)結(jié)點(diǎn)；對(duì)于i=2… n， ai1是 ai的前趨 ， ai是 ai1的后繼； n稱(chēng)作線(xiàn)性表的長(zhǎng)度 ， n為 0時(shí)稱(chēng)作 空表 。 下面給出線(xiàn)性表的幾個(gè)例子： ?（ “ A”， “ B”， …… ， “ Z”） 是一個(gè)線(xiàn)性表 ， 稱(chēng)作字母表 ， 表中的數(shù)據(jù)元素都是單個(gè)大寫(xiě)字母字符； ?（ 3， 7， 9， 12， 66， 87） 是一個(gè)線(xiàn)性表 ， 表中的每個(gè)數(shù)據(jù)元素都是一個(gè)整數(shù)； ?學(xué)生成績(jī)表也是一個(gè)線(xiàn)性表 ， 表中的數(shù)據(jù)元素為描述一個(gè)學(xué)生高考情況的一個(gè)記錄 ， 它由姓名 、 準(zhǔn)考證號(hào) 、 數(shù)學(xué) 、 語(yǔ)文 、 英語(yǔ) 、理綜 、 總分七個(gè)數(shù)據(jù)項(xiàng)組成 。 ?線(xiàn)性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu) ， 其長(zhǎng)度可根據(jù)需要增減 ， 即對(duì)數(shù)據(jù)元素不僅可以訪(fǎng)問(wèn) ， 還可進(jìn)行插入和刪除 。 ?求長(zhǎng)度 length(L)：計(jì)算線(xiàn)性表 L中數(shù)據(jù)元素的個(gè)數(shù) 。 ?取前趨 prior(L,x)：取出線(xiàn)性表 L中值為 x的元素的前趨元素；要求 x的位序大于 1。 ?定位序 locate(L,x)：確定元素 x在線(xiàn)性表 L中的位置 ，并給出位置序號(hào)；若 L中無(wú) x返回 0。 ?刪除 delete(L,i)：刪除線(xiàn)性表 L中的第 i個(gè)元素 ， 使表長(zhǎng)減 1；要求 1≤i≤length(L)。 ?在實(shí)際應(yīng)用中 ， 當(dāng)線(xiàn)性表作為一個(gè)運(yùn)算對(duì)象時(shí) ， 所需的運(yùn)算種類(lèi)不一定相同 ， 不同的運(yùn)算將構(gòu)成不同的抽象數(shù)據(jù)類(lèi)型 。 順序表 線(xiàn)性表的基本概念 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) ——順序表 順序表上的基本運(yùn)算 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) —順序表 ?順序表 （ sequential list） 是用一組 地址連續(xù) 的存儲(chǔ)單元依次存放線(xiàn)性表中的各個(gè)數(shù)據(jù)元素 ， 是一種最簡(jiǎn)單最自然的線(xiàn)性表存儲(chǔ)方法 。 ?顯然 ， 順序表中相鄰的數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的存儲(chǔ)位置也相鄰； ?換句話(huà)說(shuō) ， 順序表以數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的 物理位置相鄰 來(lái)表示數(shù)據(jù)元素在線(xiàn)性表中的邏輯相鄰關(guān)系 。 ?顯然 ， 順序表是一種可隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu) 。 ?考慮到線(xiàn)性表因插入 、 刪除運(yùn)算長(zhǎng)度可變 ， 數(shù)組的容量要足夠大 （ 可設(shè)為 MAXSIZE， 其值依實(shí)際問(wèn)題而定 ） ， 并設(shè)一指示器變量 last指向表中的最后一個(gè)元素位置 。 順序表的類(lèi)型描述 define MAXSIZE 500 typedef struct {elemtyPe data[MAXSIZE]。 }sequenlist。 ?elemtype為表中數(shù)據(jù)元素的類(lèi)型 ， 對(duì)于不同的實(shí)際問(wèn)題可以為不同的具體類(lèi)型 ， 如整型 int、 實(shí)型 float、字符型 char、 雙精度實(shí)型 double、 或其它結(jié)構(gòu)類(lèi)型等 。 ?順序表上的許多運(yùn)算是很容易實(shí)現(xiàn)的 。 ?這里只討論定位序 、 插入和刪除運(yùn)算的實(shí)現(xiàn)算法 。最簡(jiǎn)單的方法是從第一個(gè)元素起和 x比較 ， 直到找到一個(gè)值為 x的數(shù)據(jù)元素返回它的位置序號(hào) （ 即數(shù)組下標(biāo) ） ， 或者找遍表中所有元素均無(wú)值為 x的元素時(shí)返回 0。 elemtyPe x。 while((iLlast)amp。(Ldata[i]!=x)) i++。 /*未找到值為 x的元素返回 0*/ else return i。 當(dāng)a1=x時(shí)一次比較成功 ， 當(dāng) an=x時(shí) n次比較成功 ， 在 x 分布位置等概率的情況下平均比較次數(shù)為 (n+1)/2；查找不成功時(shí)的比較次數(shù)為 n+1。 2. 插入 insert(L,x,i) ?插入運(yùn)算 是指在順序表 L的第 i個(gè)元素之前加入一個(gè)新元素 x。 ?插入新元素 x后 ， 部分?jǐn)?shù)據(jù)元素間的邏輯關(guān)系發(fā)生了改變 ， 要求物理存儲(chǔ)位置也要相應(yīng)變化 。 在順序表中插入新元素 x的過(guò)程 插入運(yùn)算的算法描述 void insert(L,x,i) sequenlist *L。 int i。 if((i1)||i(Llast+1)) printf(“插入位置不正確 \n”)。 else {for(j=Llast。j) Ldata[j+1]=Ldata[j]。 Llast=Llast+1。 ?算法中的主要時(shí)間開(kāi)銷(xiāo)在于后移元素的 for循環(huán) ，循環(huán)執(zhí)行 ni+1次 。 ?所以算法最好情況下的時(shí)間復(fù)雜度為 O(1)， 在最壞情況下的時(shí)間復(fù)雜度為 O(n)， 在平均情況下的時(shí)間復(fù)雜度也是 O(n)。 ?除非 i=n時(shí)直接刪除 ， 否則需要從第 i+1元素到第 n元素依次前移一個(gè)元素位置 。 int i。 if((i1)||(iLlast)) printf(“刪除位置不正確 \n”)。j=Llast。 Llast=Llast1。 ?該算法的時(shí)間開(kāi)銷(xiāo)也主要是在元素的移動(dòng) 。 其時(shí)間復(fù)雜度在最好