1、1第二章第二章 線性表（線性表（linear list) 2.1 線性表的定義運算線性表的定義運算 1.線性表的定義：線性表的定義： 是由n(n=0)個數據元素（結點）a1,a2,a3, an組成的有限序列。 其中： n為數據元素的個數，也稱為表的長度表的長度。 當n=0 時，稱為空表空表。 非空的線性表非空的線性表(n0) 記作： （ a1,a2,a3, an）2 2.線性表（線性表（a1,a2,a3, an）的邏輯特征：）的邏輯特征： （1）有且僅有一個開始結點）有且僅有一個開始結點ai(無直接前無直接前趨）；趨）； （2）有且僅有一個終端結點）有且僅有一個終端結點an(無直接后無直接后繼

2、）；繼）； （3）其余的結點）其余的結點ai 都有且僅都有且僅有一個直接前趨有一個直接前趨ai-1和一個直接后繼和一個直接后繼ai+1。)2(ni （4） ai是屬于某個數據對象的元素，它是屬于某個數據對象的元素，它可以是一個數字、一個字母或一個記錄。可以是一個數字、一個字母或一個記錄。3 3.線性表的特性線性表的特性 （1）線性表中的所有數據元素的數據類）線性表中的所有數據元素的數據類型是一致的。型是一致的。 （2）數據元素）數據元素 在線性表中的位置只取決在線性表中的位置只取決于它的序號。于它的序號。 （3）結點間的邏輯關系是線性的。）結點間的邏輯關系是線性的。4 4. 線性表的運算線性表

3、的運算 數據的運算是定義在邏輯結構上的，而具體的實現則在存儲結構上進行。 （1）存取 （2）插入 （3）刪除 （4）查找 （5）合并 （6）分解 （7）排序 （8）求線性表的長度 基本運算5 線性表的順序存儲結構（順序表）線性表的順序存儲結構（順序表） 1.順序表的定義：順序表的定義： -用一組連續的存儲單元（地址連續）依次存放線性表的各個數據元素。 即：在順序表中邏輯結構上相鄰的數據即：在順序表中邏輯結構上相鄰的數據元素，其物理位置也是相鄰的元素，其物理位置也是相鄰的。6 存儲地址 內容元素序號12。I 。 n a 1 A 2 。 。A i 。 。LL + 1。L+（i - 1）。L+（n

4、- 1） a n 2.順序表中數據元素的存儲地址順序表中數據元素的存儲地址 若一個數據元素僅占一個存儲單元，則其存儲方式參見下圖。 從圖中可見，第i個數據元素的地址為：的地址為： LOC（a i）=loc(a 1)+(i-1)7 若每個數據元素占用m個存儲單元，則 第m個數據元素的存儲位置為： LOC（a i）=loc(a 1)+(i-1)*m loc(a 1)稱為基地址（第一個數據元素的存儲位置）。 顯然，數據元素在順序表中位置取決于數據元素在線性表中的位置。 順序表的特點 是：邏輯位置相鄰，其物理位置也相鄰。8 3.順序表的描述： 由于C語言中的一維數組也是采用順序存儲表示，故可以用數組類

5、型來描述順序表。又因為除了用數組來存儲線性表的元素之外，順序表還應該用一個變量來表示線性表的長度屬性，所以我們用結構類型來定義順序表類型。9可用C語言的一維數組實現：# define ListSize 100typedef int DataType;typedef struc DataType dataListSize; int length; Sqlist;10 4.順序表的幾種基本運算 （1）插入運算 -在第I（1=I=n+1)個元素之前插入一個新的數據元素x。使： 長度為n的線性表變為長度為n+1的線性表 （a1,a2,ai-1,ai,an） （a1,a2,ai-1,x,ai,an） 動

6、態演示11 插入算法的思想： 若i=n+1,則將x插入到表尾； 若表長度n0或插入位置不適當，則輸出錯誤信息，并返回-1； 當1=I=I-1;j-) L.dataj+1=L.dataj; L.dataI-1=x; L.length+;13插入算法分析：上述算法for循環語句的執行次數為n-I+1;若I=1,需移動全部n個結點（最壞：O(n)）若I=n+1（在表尾插入）,無需用移動結點，直接插入即可。（最好O(1)）移動結點的平均次數：)1(11inPEniII14 按等概率考慮： 可能的插入位置為I=1,2,n,n+1共n+1個，則pi=1/(n+1) 所以1111) 1(11) 1(nini

7、IIinninPE2)1(2)1)1()1111nnnnnn（ 順序表插入算法平均約需移動一半結點。15 （2）刪除算法 -將線性表的第I（1=I=n)個結點刪除，使： 長度為n的線性表變為長度為n-1的線性表。 （a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an） 動態演示16 刪除算法的思想： 若i=n,只需刪除終端結點，不用移動結點； 若表長度n=0或刪除位置不適當，則輸出錯誤信息，并返回-1； 當1=In時，則將表中結點ai+1,ai+2,an依次向前移動一個位置（共需移動n-I個數據元素。 最后將表長n減1，刪除成功，函數返回值為0。17刪除算法描述

8、Void deleteList(Sqlist*L，int I) int j; for(j=i;jdata-表示由p所指向結點的數據域。 (*p).next或或p-next-表示由p所指向結點的指針域。Data next 單鏈表的描述：單鏈表的描述：27P=(JD*)malloc(sizeof(JD)-對指針p賦值使其指向某一結點（按需生成一個JD結點類型的新結點）。其中： (JD*)-進行類型轉換。Sizeof(JD)-求結點需用占用的字節數。Malloc(size)-在內存中分配size個連續可用字節的空間。Free(p)-系統回收p結點。（動態） 單鏈表的描述：單鏈表的描述：28 單鏈表的

9、基本運算單鏈表的基本運算 （1）建立單鏈表之）建立單鏈表之 -頭插法建表： 思想：思想：從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放在新結點的數據域 中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。 B A C D HeadHead S注：頭插法生成的鏈表中結點的次序和輸入的順序相反。29 頭插法建表頭插法建表:（逆序） 動畫void Createlist_L(LinkList &L,int n)L=(LinkList) malloc (sizeof(LNode);L-next = NULL;for(i=n;i0;-i)p=(LinkList) malloc

10、(sizeof(LNode);scanf(&p-data);p-next = L-next;L-next = p;30 算法思想：算法思想：將新結點插入到當前鏈表的表尾上，可增加一個尾指針r，使其始終指向鏈表的尾結點。 pA D C B 單鏈表的基本運算單鏈表的基本運算 （1）建立單鏈表之）建立單鏈表之 -尾插建表法：head r S 尾插建表可使生成的結點次序和輸入的順序相同31頭、尾插法建表分析：頭、尾插法建表分析： 上述頭、尾插法建表由于沒有生成（附上述頭、尾插法建表由于沒有生成（附 加）頭結點，因此開始結點和其它結點 的插入處理并不一樣，原因是開始結點 的位置存放在頭指針中，而

11、其余結點的 位置是在其前趨結點的指針域 。 尾插法建表的改進算法尾插法建表的改進算法 思想：思想： 設頭結點，設頭結點，使第一個結點和其余結點的插入操作一致。32（表）頭結點（表）頭結點（在第一個結點之前附設）-其指針域 存貯指向第一個結點的指針（即第一個結點的存貯位置）。 頭結點的數據域：頭結點的數據域：可有可無 頭結點的指針域：頭結點的指針域：指向第一個結點的指針。單鏈表的基本運算之單鏈表的基本運算之-改進的尾插法建表算法改進的尾插法建表算法33帶頭結點的單鏈表帶頭結點的單鏈表 空表空表heada1 an 頭結點開始結點 非空表非空表無論鏈表是否為空，其頭指針是指向頭結點的非空指針，所以表

12、的第一個結點和其它結點的操作一致。34按序號查找按序號查找 設單鏈表的長度為n，要查找表中第I個結點，算法思想如下：算法思想如下： 從頭結點開始順鏈掃描，用指針p指向當前掃描到的結點，用j作統計已掃描結點數的計數器，當p掃描下一個結點時，j自動加1。 P的初值指向頭結點，j的初值為0。 當j=I時，指針p所指的結點就是第I個結點。 單鏈表的基本運算之單鏈表的基本運算之 （2）查找運算）查找運算35訪問單鏈表的第i個元素 動畫status GetElem_L(LinkList L,int i,ElemType &e)p = L-next; j = 1;while(p & jnex

13、t; +j;if(!p | ji) return ERROR;e = p-data;return OK;36按按值查找：按按值查找： 在鏈表中，查找是否有結點等于給定值key的結點，若有的話，則返回首次找到的值勤為key的結點的存儲位置；否則返回null. 算法思想：算法思想： 從開始結點出發，順鏈逐個結點的值和給予定值key作比較。 算法描述（略）算法描述（略）37 設指針p指向單鏈表的某一結點，指針s指向等到插入的、其值為x的新結點。實現方法（兩種）：實現方法（兩種）： 后插后插-將新結點*s插入結點*p之后。 前插前插-將新結點*s插入結點*p之前。 單鏈表的基本運算之單鏈表的基本運算之

14、（3）插入運算）插入運算38 算法思想：算法思想：取一新結點，將其數據域置為新結點，再修改有關結點的鏈域： 把原p結點的直接后繼結點作為s結點的直接后繼，s結點作為p結點的直接后繼。 X 單鏈表的基本運算單鏈表的基本運算（3）插入運算之）插入運算之 后插操作后插操作 S P39INSERTAFTER（P，X）/*將值為X的新結點插入*P之后*/JD *p;datatype x; s=（JD *）malloc(sizeof(JD); /生成新結點*/s-data=x;s-next=p-next;p-next=s;/*將*s插入*p之后*/ /*INSERTAFTER */ 單鏈表的基本運算單鏈表的基本運算（3）插入運算之）插入運算之 后插算法：后插算法：后插算法的時間復雜度：O（1）40 先找到p結點的前趨結點（單鏈表無前趨指針），然后修改其鏈域，使其指向待插入的s結點，而將s結點指向p結點。 X 單鏈表的基本運算單鏈表的基本運算 （3）插入運算之）