《數(shù)據(jù)結(jié)構(gòu)》課程課件第二章線性表

第二章線性表王瑜本章內(nèi)容提要1、理解線性表的邏輯結(jié)構(gòu)及定義2、掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3、掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)4、線性表結(jié)構(gòu)應(yīng)用舉例§2.1線性表的類型定義☆

線性表（linear_list）：N個(gè)數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間具有線性關(guān)系?！?/p>

線性關(guān)系：除第一個(gè)元素外，每個(gè)元素有且僅有一個(gè)前驅(qū)；除最后一個(gè)元素外，每個(gè)元素有且僅有一個(gè)后繼；☆

特點(diǎn)：數(shù)據(jù)元素之間的關(guān)系是它們?cè)跀?shù)據(jù)集合中的相對(duì)位置。一、線性表的定義☆

數(shù)據(jù)結(jié)構(gòu)的描述：☆

術(shù)語：二、線性表上常見的運(yùn)算1、初始化

Initiate(L):創(chuàng)建一個(gè)空的線性表L2、求長(zhǎng)度

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

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

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

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

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

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

個(gè)元素之前插入前a1a2…ai-1aiai+1…an

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

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

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

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

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

否則FALSE10、輸出線性表

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

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

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

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

☆存儲(chǔ)空間必須是連續(xù)的，預(yù)分配。

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

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

☆已知基地址，可以計(jì)算出任意元素的存儲(chǔ)地址：

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

第i個(gè)元素二、各個(gè)運(yùn)算在順序存儲(chǔ)下的虛擬實(shí)現(xiàn)7、定位//查找某個(gè)元素是否存在，存在給出其位置，否則為0；時(shí)間復(fù)雜性：找到找不到二、各個(gè)運(yùn)算在順序存儲(chǔ)下的虛擬實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)內(nèi)容的三個(gè)方面elemElemtype第i個(gè)元素elemElemtype第i個(gè)元素8、插入//在順序線性表L中第i個(gè)元素之前插入新元素e注意：還要考慮空間滿的情況8、插入9、刪除§2.2線性表的順序表示和實(shí)現(xiàn)§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、鏈?zhǔn)酱鎯?chǔ)方式：

用任意存儲(chǔ)空間單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的邏輯關(guān)系（線性），在存放每個(gè)元素的同時(shí)，也存放相關(guān)元素的信息（相關(guān)元素的存儲(chǔ)地址），即用指針來表示元素之間的邏輯關(guān)系。存放一個(gè)數(shù)據(jù)元素占用的空間為：存放數(shù)據(jù)元素存放相關(guān)元素的地址信息存儲(chǔ)一個(gè)元素占用的空間稱為一個(gè)結(jié)點(diǎn)§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、特點(diǎn)：☆

存儲(chǔ)空間不一定連續(xù)；☆

邏輯關(guān)系是由指針來實(shí)現(xiàn)的；☆

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

非隨機(jī)存?。樞虼嫒。丛L問任何一個(gè)元素的時(shí)間不同。三、分類（根據(jù)存儲(chǔ)相關(guān)元素的信息不同）：☆

單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：存放元素的同時(shí)，存放其后繼（或前驅(qū)）元素的信息；§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)☆

雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：存放元素的同時(shí)，存放其后繼和前驅(qū)元素的信息；☆

循環(huán)單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，由于最后一個(gè)元素沒有后繼，其結(jié)點(diǎn)的指針域?yàn)榭?，若在此記下第一個(gè)元素的存儲(chǔ)地址，則形成循環(huán)單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；§2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)☆

循環(huán)雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，最后一個(gè)元素結(jié)點(diǎn)的后繼指針指向第一個(gè)元素結(jié)點(diǎn)，第一個(gè)元素的前驅(qū)指針指向最后一個(gè)元素結(jié)點(diǎn)。§2.3.1線性鏈表一、單鏈?zhǔn)降拇鎯?chǔ)方式：用任意存儲(chǔ)空間單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的后繼邏輯關(guān)系，在存放每個(gè)元素的同時(shí)，也存放其后繼元素的信息（即后繼元素的存儲(chǔ)地址），即用指針來表示元素之間的后繼邏輯關(guān)系。存放一個(gè)數(shù)據(jù)元素占用的空間為：一、單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一、單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)☆

頭指針：第一個(gè)元素的存儲(chǔ)地址。☆

頭結(jié)點(diǎn)：有時(shí)為了方便，增加一個(gè)結(jié)點(diǎn)，其數(shù)據(jù)域不存放任何元素，其指針域存放第一個(gè)元素的存儲(chǔ)地址?！?/p>

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

a1a2aiai+1……ana1a2aiai+1……an2、特點(diǎn)：☆

具有單鏈表的特點(diǎn)；☆

從任何一個(gè)元素都可以訪問整個(gè)線性表。3、虛擬實(shí)現(xiàn)：

同單鏈表的完全一樣一、循環(huán)單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二、線性表的各個(gè)運(yùn)算在循環(huán)單鏈存儲(chǔ)結(jié)構(gòu)下的虛擬實(shí)現(xiàn)基本與單鏈表存儲(chǔ)結(jié)構(gòu)的相同，但是在處理最后一個(gè)元素結(jié)點(diǎn)時(shí)，要注意！§2.3.2循環(huán)鏈表§2.3.3雙向鏈表1、方式：用任意存儲(chǔ)空間單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的前驅(qū)、后繼邏輯關(guān)系。在存放每個(gè)元素的同時(shí)，也存放其前驅(qū)、后繼元素的信息（即前驅(qū)和后繼元素的存儲(chǔ)地址），即用兩個(gè)指針來表示元素之間的前驅(qū)、后繼邏輯關(guān)系。存放一個(gè)數(shù)據(jù)元素占用的空間為：一、雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（a1,a2,…ai,ai+1,…an）a1a2…an－1anla一、雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)記錄前驅(qū)的地址（指向前驅(qū)）記錄后繼的地址（指向后繼）一、雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2、特點(diǎn)：☆

具有單鏈表的特點(diǎn)；☆

前驅(qū)操作簡(jiǎn)單O（1）；☆

任何位置插入、刪除都簡(jiǎn)單了。3、虛擬實(shí)現(xiàn)：二、線性表的各個(gè)運(yùn)算在雙鏈存儲(chǔ)結(jié)構(gòu)下的虛擬實(shí)現(xiàn)例題在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改怎樣指針？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線性表的循環(huán)雙鏈?zhǔn)酱鎯?chǔ)表示一、循環(huán)雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1、方式：同雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)基本相同，但最后一個(gè)元素的后繼指針不空，而是指向第一個(gè)元素（或頭結(jié)點(diǎn)）；第一個(gè)元素的前驅(qū)指針不空，而是指向最后一個(gè)元素結(jié)點(diǎn)。（a1,a2,…ai,ai+1,…an）a1…an－1anla2、特點(diǎn)：☆

相當(dāng)于兩個(gè)循環(huán)單鏈3、虛擬實(shí)現(xiàn)：

與雙鏈?zhǔn)酵耆嗤?、線性表的各個(gè)運(yùn)算在循環(huán)雙鏈存儲(chǔ)結(jié)構(gòu)下的虛擬實(shí)現(xiàn)一、循環(huán)雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例題1、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，應(yīng)該如何修改指針的操作？1.q→prior=p;2.q→next=p→next;3.p→next→prior=q;4.p→next=q;要點(diǎn)：（1）step1&step2首先要修改待插入結(jié)點(diǎn)q的前驅(qū)和后繼指針,可調(diào)換順序（2）step3&step4其次要修改p的后繼結(jié)點(diǎn)的前驅(qū)指針，再修改p后繼指針，可調(diào)換順序這兩個(gè)操作不能顛倒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、帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空的條件是：L==NULLb)L->next->prior==NULL

c)L->prior==NULL

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

符號(hào)處理是一類非數(shù)值性問題，一元多項(xiàng)式就是符號(hào)處理的一類實(shí)例。一個(gè)一元n次多項(xiàng)式的一般形式如下：其中

,,…為各項(xiàng)的系數(shù)，非零；

,,