第3章 線性表

1、第三章 線性表本章主要內(nèi)容3.1 線性表的定義和基本操作n線性表的定義n線性表是由n（n0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。nL=( a1, a2,.,ai-1,ai,ai+1,.,an)；其中：L為表名，習(xí)慣用大寫書寫；ai為該線性表的數(shù)據(jù)元素，習(xí)慣用小寫書寫；n線性表中數(shù)據(jù)元素的個(gè)數(shù)被稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空線性表。 線性表特點(diǎn)n特點(diǎn)n除第一個(gè)和最后一個(gè)元素外，其他元素都存在唯一的前驅(qū)、后繼關(guān)系n舉例 n La=（34，89，765，12，90，-34，22） 數(shù)據(jù)元素類型為int。n Ls=(Hello,World, China, Welcome) 數(shù)據(jù)元素類型為stri

2、ng。 n舉例n Lb=(book1,book2,.,book100) 數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型： struct bookinfo int No; /圖書編號(hào) char *name; /圖書名稱 char *auther; /作者名稱 .; 在現(xiàn)實(shí)中，這種類型的數(shù)據(jù)結(jié)構(gòu)很多很多，如學(xué)生檔案學(xué)籍系統(tǒng)、圖書管理系統(tǒng)、倉(cāng)庫(kù)管理系統(tǒng)、設(shè)備管理系統(tǒng)等線性表的基本操作n1. 初始化線性表L void InitList( ) n2. 求線性表的長(zhǎng)度：int Length()n3.取表元：DataType Get(int i)n4.按值查找：int Locate(DataType x)n5.插入操作：

3、int Insert(DataType x, int i)n6.刪除操作：int Deleted(int i) 返回2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)地址內(nèi)存單元.da1d+La2d+2La3.d+(i-1)Lai.d+(n-1)Lan.n順序存儲(chǔ)結(jié)構(gòu)n指用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的每個(gè)數(shù)據(jù)元素。如右圖所示：說(shuō)明：說(shuō)明：L為每個(gè)數(shù)據(jù)元素所占據(jù)的存儲(chǔ)單元數(shù)目。為每個(gè)數(shù)據(jù)元素所占據(jù)的存儲(chǔ)單元數(shù)目。順序表元素在內(nèi)存的存儲(chǔ)地址 n相鄰兩個(gè)數(shù)據(jù)元素的存儲(chǔ)位置計(jì)算公式 LOC(ai+1)=LOC(ai)+Ln線性表中任意一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置的計(jì)算 公式為：LOC(ai+1)=LOC(a1)+(i

4、-1)*L 順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)n邏輯與物理一致： 邏輯上相鄰，物理上也相鄰利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系n隨機(jī)存?。?可以利用上述給出的數(shù)學(xué)公式，快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址順序存儲(chǔ)結(jié)構(gòu)的類型定義n在C+中，線性表的順序存儲(chǔ)定義如下: #define MAXSIZE 100typedef int DataType;class SequenList public: void Initiate(); int Length(); int Insert(DataType x,int i); int Deleted(int i); int Locate(DataT

5、ype x); DataType Get(int i); private: DataType dataMAXSIZE; int len; 典型操作的算法實(shí)現(xiàn)1.順序表的初始化順序表的初始化即構(gòu)造一個(gè)數(shù)據(jù)元素個(gè)數(shù)為0的空表，算法如下:算法3-1 順序表的初始化void SequenList:Initiate() len=0;典型操作的算法實(shí)現(xiàn)2.插入運(yùn)算 插入運(yùn)算是指在順序表的第i個(gè)位置上插入一個(gè)值為x的新元素，插入后使原表為n的順序表（a1，a2，ai-1，ai，ai+1，an）變?yōu)楸黹L(zhǎng)為n+1的順序表 （a1，a2，ai-1，x，ai，ai+1，an ） 其中，i 的合理取值范圍為1in+1

6、。int SequenList:Insert(DataType x,int i) /在線性表的第i個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素x int j; if(len=MAXSIZE) coutoverflow!endl; /數(shù)據(jù)溢出 return 0; else if(ilen+1) /如果插入位置不合法 cout position is not correct!=i; j-) dataj=dataj-1; /元素后移 datai-1=x; /插入元素 len+; /表長(zhǎng)度增加1 return 1; 插入算法的時(shí)間性能分析： 時(shí)間主要消耗在數(shù)據(jù)元素的移動(dòng)上。在第i個(gè)位置上插入x，從第i個(gè)到第n個(gè)

7、元素都要向后移動(dòng)一個(gè)位置，共需要移動(dòng)n-(i-1)，即n-i1個(gè)數(shù)據(jù)元素。而i的取值范圍為1in+1，即有n1個(gè)位置可以插入。設(shè)在第i個(gè)位置上做插入操作的概率為Pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)為： 在等概率情況下，Pi=1/(n+1)，則1i1(1)niniEP ni 11111(1)(1)12nniniiinEP ninin 時(shí)間復(fù)雜度為O(n) 典型操作的算法實(shí)現(xiàn)3. 刪除運(yùn)算 線性表的刪除運(yùn)算是指將表中第i個(gè)元素從線性表中刪除，使原表長(zhǎng)為n的線性表（a1，a2，ai-1，ai，ai+1，an）變成表長(zhǎng)為n-1的線性表（a1，a2，ai-1，ai+1，an）i的取值范圍為1in。在順序表上完

8、成刪除運(yùn)算的步驟如下:（1）將數(shù)據(jù)元素ai+1an依次向前移動(dòng)一個(gè)位置。（2）修改len值，使之仍指向最后一個(gè)數(shù)據(jù)元素的下一個(gè)位置。 int SequenList:Deleted(int i) /刪除順序表的第i個(gè)數(shù)據(jù)元素 int j; if(ilen) /若刪除位置不合法 coutposition is not correct!endl; return 0; else for(j=i; jlen; j+) dataj-1=dataj; /元素前移 len-; /表長(zhǎng)度減1 return 1; 本算法應(yīng)注意以下問(wèn)題 （1）刪除第i個(gè)數(shù)據(jù)元素，i的取值為1in（即len），否則第i個(gè)元素不存在。

9、因此，要檢查刪除位置的有效性。（2）刪除ai之后，該數(shù)據(jù)不再存在；如果需要，可先取出ai，再做刪除。刪除算法的時(shí)間性能分析：n與插入運(yùn)算相同，其時(shí)間主要消耗在移動(dòng)表中元素上。刪除第i個(gè)元素時(shí)，其后面的元素ai+1an都要向前移動(dòng)一個(gè)位置，共移動(dòng)n-i個(gè)元素，所以平均移動(dòng)數(shù)據(jù)元素的次數(shù)為n在等概率情況下，Pi=1/n，則n這說(shuō)明，在順序表上做刪除運(yùn)算時(shí)大約需要移動(dòng)表中一半元素。顯然，該算法的時(shí)間復(fù)雜度為O(n)。1()ndeiiEP ni1111()()2nndeiiinEP ninin典型操作的算法實(shí)現(xiàn)4.按值查找 在線性表中查找與給定值相等的數(shù)據(jù)元素。方法是：從第一個(gè)元素a1起依次和比較，直

10、到找到值相等的數(shù)據(jù)元素，返回它在順序表中的位置值（下標(biāo)+1）；或者查遍整個(gè)表都沒(méi)有找到，返回0。 int SequenList:Locate(DataType x) /返回值為x的數(shù)據(jù)元素的位序值 int j=0; while(jlen)& (dataj!=x)j+; if(jlen)return j+1; else return 0; 算法主要運(yùn)算是比較。次數(shù)與 x在表中的位置有關(guān)，也與表長(zhǎng)有關(guān)。 當(dāng)a1=x時(shí)，比較一次成功；當(dāng)an=x時(shí)，比較n次成功。在查找成功的情況下，平均比較次數(shù)為（n+1）/2，時(shí)間復(fù)雜度為O(n)返回順序表查詢算法int Location_SeqList (

11、PSeqList PL, DataType x) /*順序表檢索，入口參數(shù)：為順序表指針，檢索元素，順序表檢索，入口參數(shù)：為順序表指針，檢索元素， 返回元素位置，返回元素位置，-1表示表不存在，表示表不存在，0表示查找失敗表示查找失敗*/ int i=0; if (!PL) printf(表不存在表不存在); return(-1); /*表不存在，不能檢索表不存在，不能檢索*/ while (i length & PL-datai!= x) i+; if (i=PL- length) return 0; else return (i +1); 典型操作的算法實(shí)現(xiàn)5. 順序表的插入運(yùn)算n

12、定義： 順序表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的新元素，即在第i元素之前插入 x，使原表長(zhǎng)為n的表：(e1，e2，. ，ei-1，ei，ei+1，. ，en) 變?yōu)楸黹L(zhǎng)為 n+1 表：(e1，e2，.，ei-1，x，ei，ei+1，.，en) 。其中i：1in+1。 n(1)檢查待插入的表是否存在，若不存在退出；n(2)判斷順序表是否滿(即表長(zhǎng)length是否大于等于MAXSIZE)？若滿，退出；否則執(zhí)行(3)；n(3)檢查插入位置的合法性( i 滿足1=i length = MAXSIZE) printf(“表溢出表溢出”); return(-1); /*表空間已滿，不能插入表空間

13、已滿，不能插入*/ if (i PL- length +1) /*檢查插入位置的合法性檢查插入位置的合法性*/ printf(“插入位置不合法插入位置不合法”); return(0); for(j= PL - length -1; j=i-1; j-) PL -dataj+1= PL -dataj; /* 移動(dòng)元素移動(dòng)元素 */ PL-datai-1=x; /*新元素插入新元素插入*/ PL- length +; /*表長(zhǎng)加表長(zhǎng)加 1*/ return (1); /*插入成功，返回插入成功，返回*/ n設(shè)插入的位置為i ，則把ei到en元素向后移動(dòng)一個(gè)位置共需要移動(dòng) ni1個(gè)元素。n設(shè)在第i個(gè)

14、位置上作插入的概率為Pi，n由于 1 i n+1，共有 n1個(gè)位置可以插入，即在情況下pi=1/ (n+1)，則：n算法的時(shí)間復(fù)雜度為(n)11111E(1 )(1 )12nniniiinp n in in 順序表插入運(yùn)算的效率分析刪除的存儲(chǔ)示意如下頁(yè)所示典型操作的算法實(shí)現(xiàn)6. 順序表的刪除運(yùn)算是指將表中第 i 個(gè)元素從線性表中去掉 刪除前：表長(zhǎng)n (e1，e2，. ，ei-1，ei，ei+1，.，en) 刪除后：表長(zhǎng) n -1 (e1，e2，. ，ei-1， ei+1，. ，en) 其中i：1 i n。刪除前刪除后下頁(yè)給出刪除的算法刪除的操作步驟:n（1）檢查表是否存在，若不存在退出n（2）

15、檢查刪除位置的合法性（ i 是否為1ilength）若不滿足，退出n（3）將ei+1en 順序向上移動(dòng)一位，ei+1占據(jù)ei 位置，（注意數(shù)據(jù)的移動(dòng)方向）n（4）修改表長(zhǎng)下頁(yè)給出算法C語(yǔ)言描述順序表刪除算法int Delete_SeqList(PSeqList PL，int i) /*順序表刪除，入口參數(shù)：順序表指針，刪除元素位置，順序表刪除，入口參數(shù)：順序表指針，刪除元素位置，返回標(biāo)志返回標(biāo)志1表示成功，表示成功，0表示刪除位置不合法，表示刪除位置不合法，-1表示表不存在表示表不存在*/ int j; if (!PL) printf(表不存在表不存在); return(-1); /*表不存在

16、，不能刪除元素表不存在，不能刪除元素*/ if(i PL - length) /*檢查刪除位置的合法性檢查刪除位置的合法性*/ printf (刪除位置不合法刪除位置不合法); return(0); for(j=i; j length; j+) PL -dataj-1= PL-dataj; /*向上移動(dòng)向上移動(dòng)*/ PL- length -; return (1); /*刪除成功刪除成功*/ 刪除算法的效率分析n在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： n1idl21ni)(nn1E結(jié)論n順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)

17、據(jù)元素n當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插入或刪除操作時(shí)，消耗的時(shí)間代價(jià)較大返回返回2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)n線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：n邏輯上相鄰、物理上相鄰，結(jié)構(gòu)簡(jiǎn)單n可以根據(jù)元素的下標(biāo)存取，速度便捷 n線性表順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：n在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)n對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用n線性表的容量難以擴(kuò)充為此我們引入線性表的鏈?zhǔn)酱鎯?chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)n邏輯上相鄰的元素之間的物理位置是通過(guò)指針的指向來(lái)實(shí)現(xiàn)的，這種指向一般是通過(guò)的動(dòng)態(tài)的地址指針來(lái)實(shí)現(xiàn)的（也可以通過(guò)靜態(tài)的偽地址指針來(lái)實(shí)現(xiàn)）n每個(gè)

18、數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲(chǔ)位置的信息下頁(yè)給出鏈?zhǔn)酱鎯?chǔ)的內(nèi)存示意圖：下頁(yè)給出鏈?zhǔn)酱鎯?chǔ)的內(nèi)存示意圖：headd cba存儲(chǔ)地址內(nèi)容直接后繼存儲(chǔ)地址100b120.120c160.144a100.160dNULL.首元素位置線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖鏈?zhǔn)酱鎯?chǔ)n表示每個(gè)數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點(diǎn), 其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域data；表示直接后繼元素存儲(chǔ)地址的部分被稱為指針或指針域next n單鏈表中最后一個(gè)結(jié)點(diǎn)沒(méi)有直接后繼結(jié)點(diǎn)，它的指針域放入一個(gè)特殊的值NULLn為了簡(jiǎn)化對(duì)鏈表的操作，人們經(jīng)常在鏈表的第一個(gè)結(jié)點(diǎn)

19、之前附加一個(gè)結(jié)點(diǎn)，并稱為頭結(jié)點(diǎn)headd cba帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)示意圖帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)示意圖n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)n線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致n通過(guò)頭指針進(jìn)入鏈表，通過(guò)結(jié)點(diǎn)的指針域訪問(wèn)后繼結(jié)點(diǎn)，尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，存取方式被為順序存取方式對(duì)比順序存儲(chǔ)為對(duì)比順序存儲(chǔ)為隨即存取方式隨即存取方式鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)的幾種形式n單鏈表n循環(huán)鏈表n雙向鏈表typedef int DataType;class Item public: DataType data; Item * next; Item()next=NULL;單鏈表的定義cla

20、ss Link public: Item *head; Link()head=NULL; Link()DeleteAll(); void Initiate(); void DeleteAll(); void HeadCreate(int n); void TailCreate(int n); void HeadCreateWithHead(int n); void TailCreateWithHead(int n); int Length(); Item *Locatex(DataType x); Item *Locatei(int i); DataType Get(int i); bool

21、Insert(DataType x,int i); bool Deleted(int i); void Print(); ;單鏈表的邏輯結(jié)構(gòu)示意圖單鏈表的幾種形態(tài)單鏈表的基本操作1.初始化 void Link:Initiate() DeleteAll(); head=NULL;2.建立單鏈表 （1）從表尾到表頭建立單鏈表（不帶有空白頭結(jié)點(diǎn)） void Link:HeadCreate(int n) DeleteAll(); Item *s,*p; int i; p=NULL; for(i=1; is-data; s-next=p; p=s; head=p;（2）從表頭到表尾建立單鏈表（不帶有空白

22、頭結(jié)點(diǎn)） 頭void Link:TailCreate(int n) Item *s,*r,*p; int i; DeleteAll(); p=NULL; for(i=1; is-data; s-next=NULL; if(p=NULL)p=r=s; else r-next=s; r=s; head = p;（3）從表尾到表頭建立單鏈表（帶有空白頭結(jié)點(diǎn)） void Link:HeadCreateWithHead(int n) Item *s,*p; int i; DeleteAll(); p=new Item(); p-next=NULL; for(i=1; is-data; s-next=p-

23、next; p-next=s; head= p;（4）從表頭到表尾建立單鏈表（帶有空白頭結(jié)點(diǎn)）void Link:TailCreateWithHead(int n) Item *s,*r,*p; int i; DeleteAll(); p=new Item(); p-next=NULL; r=p; for(i=1; is-data; r-next=s; r=s; r-next=NULL; head= p;3求表長(zhǎng) 設(shè)定一個(gè)移動(dòng)指針p和計(jì)數(shù)器j，初始化后，p所指結(jié)點(diǎn)后面若還有結(jié)點(diǎn)，p向后移動(dòng)，計(jì)數(shù)器加1。 int Link:Length() int j; Item *p; j=1; p=head

24、-next; while(p!=NULL) j+; p=p-next; return -j;4查找操作 （1）按序號(hào)查找 從單鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第i個(gè)，若是，則返回該結(jié)點(diǎn)的指針；否則繼續(xù)下一個(gè)結(jié)點(diǎn)的查找，直到表結(jié)束為止。若沒(méi)有第i個(gè)結(jié)點(diǎn)，則返回空；如果i=0；則返回頭指針。 Item * Link:Locatei(int i) int j=1; Item *p; if(i=0)return head; p=head-next; while(p!=NULL)& (jnext; j+; if(j=i)return p; else coutposition is no

25、t correct!next; while(p!=NULL)& (p-data!=x)p=p-next; if(p) return p; else coutx is not exist!next; while(jnext; if(p=NULL)| (ji) coutposition is not correct!data;5插入(前插) 設(shè)p指向鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入*p的前面插入算法 找到第i-1個(gè)結(jié)點(diǎn)；若存在，繼續(xù)步驟，否則結(jié)束。 申請(qǐng)新結(jié)點(diǎn)，將數(shù)據(jù)填入新結(jié)點(diǎn)的數(shù)據(jù)域。 將新結(jié)點(diǎn)插入。 bool Link:Insert(DataType x,int

26、i) Item *p,*s; p=Locatei(i-1); if(p=NULL) coutposition is not correct!data=x; s-next=p-next; p-next=s; return true;返回 循環(huán)鏈表循環(huán)鏈表為循環(huán)鏈表為空的情形空的情形特點(diǎn)：特點(diǎn)： 1.可以通過(guò)鏈表中任意節(jié)點(diǎn)遍歷整個(gè)鏈表 2.可以通過(guò)尾指針訪問(wèn)到頭節(jié)點(diǎn) 3.循環(huán)鏈表的操作基本上和單鏈表相同 返回雙向鏈表如何定義雙向鏈表的節(jié)點(diǎn)，請(qǐng)看下頁(yè)雙向鏈表的節(jié)點(diǎn)定義typedef int DataType;class DualItem public: DataType data; DualItem

27、 *next; DualItem *prior; DualItem()next=NULL; prior=NULL;在此定義基礎(chǔ)之上，雙向鏈表的插入、刪除運(yùn)算是如何實(shí)現(xiàn)的呢？雙向鏈表的節(jié)點(diǎn)插入n設(shè)p指向雙向鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，n步驟如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;雙向鏈表的節(jié)點(diǎn)刪除n設(shè)p指向雙向鏈表中某結(jié)點(diǎn)，刪除*p。n操作示意圖如圖2-17所示。n操作步驟如下：p-prior-next=p-next;p-next-prior=p-prior; free(p) 1、2的順序可

28、以調(diào)換返回 2.3 線性表的應(yīng)用舉例 1. 要求在時(shí)間復(fù)雜度為O(n)的條件下將順序表（a1，a2,an）重新排列為以a1為界的兩部分：a1前面的值都比a1小，a1后面的值都比a1大 定義i、j分別指向第一個(gè)元素和最后一個(gè)元素，從最后一個(gè)元素aj開(kāi)始逐一向前掃描每一個(gè)數(shù)據(jù)元素 （1）條件ij：若當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)元素aj比a大，表明它已經(jīng)在a的后面，不必改變它的位置，繼續(xù)比較aj前一個(gè)數(shù)據(jù)元素；若當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)元素aj比a小，說(shuō)明它應(yīng)該在a的前面，將aj保存到ai所在位置。（2）條件ij：若當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)元素ai比a小，說(shuō)明它已經(jīng)在a的前面，不必改變它的位置，繼續(xù)比較ai后一個(gè)數(shù)據(jù)元素；若當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)元素ai比a大，說(shuō)明它應(yīng)該在a的后面，將ai保存到aj所在位置，重新執(zhí)行步驟（1）。 #define MAXSIZE 100typedef int DataType;class SequenList public: friend void Part(Seque