第二章線性表王瑜本章內容提要1、理解線性表的邏輯結構及定義2、掌握線性表的順序存儲結構及操作實現3、掌握線性表的鏈式存儲結構及操作實現4、線性表結構應用舉例§2.1線性表的類型定義☆

線性表（linear_list）：N個數據元素的有限序列，數據元素之間具有線性關系。☆

線性關系：除第一個元素外，每個元素有且僅有一個前驅；除最后一個元素外，每個元素有且僅有一個后繼；☆

特點：數據元素之間的關系是它們在數據集合中的相對位置。一、線性表的定義☆

數據結構的描述：☆

術語：二、線性表上常見的運算1、初始化

Initiate(L):創建一個空的線性表L2、求長度

Length(L):返回表中元素個數n3、訪問一個元素

Get(L,i):返回線性表的第i個元素4、求前驅

Prior(L,elem):返回線性表中elem元素的前驅5、求后繼

Next(L,elem):返回線性表中elem元素的后繼6、查找(定位)

Locate(L,x):求x數據元素在線性表中的位置7、插入

Insert(L,i,b):將數據元素插入到線性表L的第I

個元素之前插入前a1a2…ai-1aiai+1…an

插入后a1a2…ai-1baiai+1…an8、刪除

Delete(L,i):刪除線性表的第i個元素

刪除前a1a2…ai-1aiai+1…an

刪除后a1a2…ai-1ai+1…an9、判斷是否為空

Empty(L):線性表空,則返回TRUE,

否則FALSE10、輸出線性表

Print(L):輸出線性表的各個元素11、其它操作

復制、分解、合并、分類等二、線性表上常見的運算三、線性表的ADT四、線性表的分類五、線性表ADT的應用舉例例1：已知有線性表L，要求刪除所有X的出現例2:已知有兩個分別有序的線性表（從小到大），要求合并兩個線性表，且合并后仍然有序。——歸并方法1:合并，再排序O((m+n)2)方法2：歸并，利用分別有序的特點O((m+n))五、線性表ADT的應用舉例五、線性表ADT的應用舉例Voidmergelist(listLa，listLb,list&Lc){//已知線性表La和Lb中的數據元素按值非遞減排列

//歸并La和Lb得到新的線性表Lc，Lc中的元素也按值非遞減排列例:

將兩個各有n個元素的有序表歸并成一個有序表，其最小的比較次數是（）。A、nB、2n-1C、2nD、n-1§2.2線性表的順序表示和實現一、順序存儲結構1、存儲方式：用一組地址連續的存儲單元依次存儲線性表的各個元素。具體地：假設存儲每個元素占用個存儲單元，并且以所占的第一個單元的地址作為該元素的存儲地址，于是：一、順序存儲結構...2、特點：

☆存儲空間必須是連續的，預分配。

☆邏輯順序與物理順序一致，用物理上的相鄰來表示邏輯上的線性關系。

☆任意相鄰元素之間無空閑空間，且相距為。

☆已知基地址，可以計算出任意元素的存儲地址：

LOC(ai)=base+(i-1)×一、順序存儲結構3、虛擬實現：在高級語言中，數組是采用順序存儲的，因而，我們可以用高級語言中的數組類型來說明上面的存儲方式。在對線性表進行虛擬實現時，我們要定義一個結構體類型，應在其中定義三個域分別用來表示：（1）存儲線性表所有元素的數組（2）存儲線性表元素的數組的長度（3）存儲線性表當前長度的變量一、順序存儲結構順序表的類型定義：#defineMaxsize<順序表的容量>typedefstruct{ElemTypedata[MaxSize];intlength;}Inode;一、順序存儲結構注意：上述兩種定義的區別在于前者能夠對線性表的數組空間采用動態分配，并且其數組長度能夠隨之改變。1、初始化二、各個運算在順序存儲下的虛擬實現2、清空表3、銷毀表4、求表長5、判斷空表6、取表中

第i個元素二、各個運算在順序存儲下的虛擬實現7、定位//查找某個元素是否存在，存在給出其位置，否則為0；時間復雜性：找到找不到二、各個運算在順序存儲下的虛擬實現數據結構內容的三個方面elemElemtype第i個元素elemElemtype第i個元素8、插入//在順序線性表L中第i個元素之前插入新元素e注意：還要考慮空間滿的情況8、插入9、刪除§2.2線性表的順序表示和實現§2.3線性表的鏈式表示和實現順序存儲結構的優點：順序存儲結構的缺點：§2.3線性表的鏈式表示和實現一、鏈式存儲方式：

用任意存儲空間單元來存放線性表的各個元素，為了能體現元素之間的邏輯關系（線性），在存放每個元素的同時，也存放相關元素的信息（相關元素的存儲地址），即用指針來表示元素之間的邏輯關系。存放一個數據元素占用的空間為：存放數據元素存放相關元素的地址信息存儲一個元素占用的空間稱為一個結點§2.3線性表的鏈式表示和實現二、特點：☆

存儲空間不一定連續；☆

邏輯關系是由指針來實現的；☆

邏輯上相鄰，物理上不一定相鄰；☆

非隨機存取（順序存取），即訪問任何一個元素的時間不同。三、分類（根據存儲相關元素的信息不同）：☆

單鏈式存儲結構：存放元素的同時，存放其后繼（或前驅）元素的信息；§2.3線性表的鏈式表示和實現☆

雙鏈式存儲結構：存放元素的同時，存放其后繼和前驅元素的信息；☆

循環單鏈式存儲結構：在單鏈式存儲結構中，由于最后一個元素沒有后繼，其結點的指針域為空，若在此記下第一個元素的存儲地址，則形成循環單鏈式存儲結構；§2.3線性表的鏈式表示和實現☆

循環雙鏈式存儲結構：在雙鏈式存儲結構中，最后一個元素結點的后繼指針指向第一個元素結點，第一個元素的前驅指針指向最后一個元素結點。§2.3.1線性鏈表一、單鏈式的存儲方式：用任意存儲空間單元來存放線性表的各個元素，為了能體現元素之間的后繼邏輯關系，在存放每個元素的同時，也存放其后繼元素的信息（即后繼元素的存儲地址），即用指針來表示元素之間的后繼邏輯關系。存放一個數據元素占用的空間為：一、單鏈式存儲結構一、單鏈式存儲結構☆

頭指針：第一個元素的存儲地址。☆

頭結點：有時為了方便，增加一個結點，其數據域不存放任何元素，其指針域存放第一個元素的存儲地址。☆

頭結點指針：指向頭結點的指針。頭結點二、單鏈式的存儲結構的特點§2.3.1線性鏈表三、單鏈式的存儲的虛擬實現利用高級語言中的動態存儲結構（即指針）來實現。§2.3.1線性鏈表四、在單鏈式存儲結構下的操作實現1、2、四、在單鏈式存儲結構下的操作實現3、訪問第i個元素4、在p所指結點之后插入某一元素插入前：Xqp插入后：Step1：申請空間Step2：數據域賦值Step3：插入（連接）(1)式和(2)式的順序顛倒，可以嗎？4、插入元素（在第i個元素之前插入元素e）p第i－1個元素第i個元素s新插入元素為什么時間復雜度不再是O(1)？5、刪除p所指元素的后繼元素刪除前：PP->nextP->next->next刪除：P->next＝P->next->next;5、刪除第i元素6、創建單鏈表——輸入線性元素，以單鏈存儲方式存儲方法1：從頭到尾，即從第一個元素結點逐個創建各個元素結點。每次都是鏈到當前鏈表的最后。創建頭結點：L＝(LinkList)malloc(sizeof(LNode));L->next=NULL;r=L;讀入一個元素，鏈入其中：p＝(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=NULL;r->next=p;r=r->next;prL頭結點a1這是一個正序建立重復n次6、創建單鏈表——輸入線性元素，以單鏈存儲方式存儲方法2：從尾到頭，即從最后一個元素結點逐個創建各個元素結點。每次都是鏈到當前鏈表的前面，即頭結點之后。創建頭結點：L＝(LinkList)malloc(sizeof(LNode));L->next=NULL;讀入一個元素，鏈入其中：p＝(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;重復n次panaipL6、創建單鏈表——輸入線性元素，以單鏈存儲方式存儲aiLpanp7、歸并——在兩個表上直接做，改變指針即可Laa1a2am。。。b1b2bn。。。Lb7、歸并7、歸并習題：假設有兩個按元素值遞增排列的線性表A和B，均已帶頭結點的單鏈表作為存儲結構，編寫算法將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表（A表或B表）的結點空間存放表C。8、刪除相同值的元素習題：設有頭結點的單鏈表L，編程實現對表中任一值只保留一個結點，刪除其余值相同的結點。8、刪除相同值的元素8、刪除相同值的元素9、逆轉習題：寫一算法，將一單鏈表逆轉。要求逆轉在原鏈表上進行，不允許重新構造一個鏈表。五、單鏈式存儲結構下的小結§2.3.2循環鏈表一、循環單鏈式存儲結構1、方式：與線性表的單鏈式存儲結構基本相同，只是：單鏈式存儲結構時最后一個元素沒有后繼，其后繼指針為空，現在把它變為指向第一個元素（或頭結點）的指針。

a1a2aiai+1……ana1a2aiai+1……an2、特點：☆

具有單鏈表的特點；☆

從任何一個元素都可以訪問整個線性表。3、虛擬實現：

同單鏈表的完全一樣一、循環單鏈式存儲結構二、線性表的各個運算在循環單鏈存儲結構下的虛擬實現基本與單鏈表存儲結構的相同，但是在處理最后一個元素結點時，要注意！§2.3.2循環鏈表§2.3.3雙向鏈表1、方式：用任意存儲空間單元來存放線性表的各個元素，為了能體現元素之間的前驅、后繼邏輯關系。在存放每個元素的同時，也存放其前驅、后繼元素的信息（即前驅和后繼元素的存儲地址），即用兩個指針來表示元素之間的前驅、后繼邏輯關系。存放一個數據元素占用的空間為：一、雙鏈式存儲結構（a1,a2,…ai,ai+1,…an）a1a2…an－1anla一、雙鏈式存儲結構記錄前驅的地址（指向前驅）記錄后繼的地址（指向后繼）一、雙鏈式存儲結構2、特點：☆

具有單鏈表的特點；☆

前驅操作簡單O（1）；☆

任何位置插入、刪除都簡單了。3、虛擬實現：二、線性表的各個運算在雙鏈存儲結構下的虛擬實現例題在雙向鏈表存儲結構中，刪除p所指的結點時需修改怎樣指針？1、p→next→prior=p→prior;p→prior→next=p→next;2、p→next=p→next→next;p→next→prior=p;3、p→prior→next=p;p→prior=p→prior→prior;4、p→prior=p→next→next;p→next=p→prior→prior;答案(1)§2.3.4線性表的循環雙鏈式存儲表示一、循環雙鏈式存儲結構1、方式：同雙鏈式存儲結構基本相同，但最后一個元素的后繼指針不空，而是指向第一個元素（或頭結點）；第一個元素的前驅指針不空，而是指向最后一個元素結點。（a1,a2,…ai,ai+1,…an）a1…an－1anla2、特點：☆

相當于兩個循環單鏈3、虛擬實現：

與雙鏈式完全相同二、線性表的各個運算在循環雙鏈存儲結構下的虛擬實現一、循環雙鏈式存儲結構例題1、在雙向循環鏈表中，在p指針所指的結點后插入一個指針q所指向的新結點，應該如何修改指針的操作？1.q→prior=p;2.q→next=p→next;3.p→next→prior=q;4.p→next=q;要點：（1）step1&step2首先要修改待插入結點q的前驅和后繼指針,可調換順序（2）step3&step4其次要修改p的后繼結點的前驅指針，再修改p后繼指針，可調換順序這兩個操作不能顛倒1.q→prior=p;2.p→next=q;3.p→next→prior=q;4.q→next=p→next;1.q→prior=p;2.p→next=q;3.q→next=p→next;4.p→next→prior=q;1.p→next=q;2.q→prior=p;3.q→next=p→next;4.p→next→prior=q;1.q→prior=p;2.p→next=q;3.p→next→prior=q;4.q→next=p→next;1.q→prior=p;2.p→next=q;3.q→next=p→next;4.p→next→prior=q;1.p→next=q;2.q→prior=p;3.q→next=p→next;4.p→next→prior=q;例題2、帶頭結點的雙向循環鏈表L為空的條件是：L==NULLb)L->next->prior==NULL

c)L->prior==NULL

d)L->prior==L&&L->next==L例題§2.4一元多項式的表示及相加一、問題的提出

符號處理是一類非數值性問題，一元多項式就是符號處理的一類實例。一個一元n次多項式的一般形式如下：其中

,,…為各項的系數，非零；

,,