數(shù)據(jù)結(jié)構(gòu)與算法 線性表

1、第2章 線性表,2.1 線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.4 線性表的應(yīng)用示例,線性結(jié)構(gòu)是最簡(jiǎn)單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。包括線性表、棧、隊(duì)列、串。 線性結(jié)構(gòu)具有下列特點(diǎn)： 存在一個(gè)唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素。 存在一個(gè)唯一的沒有后繼的（尾）數(shù)據(jù)元素。 此外，每一個(gè)數(shù)據(jù)元素均有一個(gè)直接前驅(qū)和一個(gè)直接后繼數(shù)據(jù)元素。,線性結(jié)構(gòu),2.1 線性表的類型定義,線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。 數(shù)據(jù)元素在不同的具體情況下，可以有不同的含義。 在一些復(fù)雜的線性表中，每一個(gè)數(shù)據(jù)元素又可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，在這種情況下，通常將數(shù)據(jù)元素稱為記錄（re

2、cord）。,例如，職工工資表,每一個(gè)職工的工資是一個(gè)記錄（數(shù)據(jù)元素）。,每個(gè)記錄包含八個(gè)數(shù)據(jù)項(xiàng)。,如果n0，則除a0和an-1外，有且僅有一個(gè)直接前趨和一個(gè)直接后繼數(shù)據(jù)元素。 如果n=0，則為一個(gè)空表，表示無數(shù)據(jù)元素。,一個(gè)線性表是n （n0 ）個(gè)數(shù)據(jù)元素a0，a1，a2，an-1的有限序列。,綜上所述：,LinearList=(D,R) 其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1 R=| ai-1，aiD, i=1,2, ，n-1 Elemset為某一數(shù)據(jù)對(duì)象集；n為線性表的長(zhǎng)度。,抽象數(shù)據(jù)類型線性表的定義如下：,ADT List 數(shù)據(jù)對(duì)象：D= ai| ai

3、ElemSet, i=1,2, ，n n0 數(shù)據(jù)關(guān)系：R=| ai-1，aiD, i=2, ，n 基本操作： InitList( 順序表存儲(chǔ)空間的總分配量 #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 順序存儲(chǔ)類型 typedef struct ElemType dataMAXSIZE; /*存放線性表的數(shù)組*/ int length; /* length是順序表的長(zhǎng)度*/ SeqList;,1. 求順序表長(zhǎng)度,int ListLength(SeqList L) return(L.length); ,2. 檢查順序表是否為空,int Li

4、stEmpty(SeqList L) if(L.length) return(FALSE); else return(TRUE); ,3. 遍歷順序表,void ListTraverse(SeqList L) int i; if(L.length=0) printf(順序表為空n); else printf(當(dāng)前順序表中的元素為:n); for(i=0;i=L.length-1;i+) printf(%d ,L.datai); printf(n); ,4. 從順序表中查找元素,ElemType GetElem(SeqList L , int i) ElemType e; e=L.datai-1

5、; /第i個(gè)元素 return(e); ,5. 查找定位,/* 從順序表中查找與給定元素值相同的元素在順序表中的位置 */ int LocateElem(SeqList L, ElemType e) int i=0; while(iL.length ,6. 求順序表中元素的前驅(qū),ElemType PriorElem(SeqList L, ElemType e) int i=0; while(inext=NULL; return L; ,(只是建立一個(gè)空表，即一個(gè)頭結(jié)點(diǎn)),（2）清空單鏈表,void LinkedListClear(LinkedList L) L-next=NULL; print

6、f(鏈表已經(jīng)清空n); ,（3）檢查單鏈表是否為空,int LinkedListEmpty(LinkedList L) if(L-next=NULL) return TRUE; else return FALSE; ,（4）遍歷單鏈表,void LinkedListTraverse(LinkedList L) LinkedList p; p=L-next; if(p=NULL) printf(單鏈表為空表n); else printf(鏈表中的元素為:n); while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); ,（5）求單鏈表長(zhǎng)度,i

7、nt LinkedListLength (LinkedList L) LinkedList p; int j; p=L-next; j=0; while(p!=NULL) j+;p=p-next; return j; ,（6）從鏈表中查找元素,LinkedList LinkedListGet(LinkedList L, int i) LinkedList p; int j; p=L-next; j=1; while (p!=NULL ,（7）從鏈表查找與給定元素值相同元素的位置,int LinkedListLocate ( LinkedList L, ElemType e) LinkedLis

8、t p; int j; p=L-next; j=1; while ( p!=NULL ,（8）向鏈表中插入元素,p=L; j=0; while(p ,算法：,算法演示： DSDemoWDSDemoW.exe,(9) 從鏈表中刪除元素,(a)尋找第i個(gè)結(jié)點(diǎn),P指向其前驅(qū),(b)刪除并釋放第i個(gè)結(jié)點(diǎn),p=L; j=0; while(p-next ,q=p-next; p-next=q-next; free(q);,算法演示： DSDemoWDSDemoW.exe,從線性鏈表的插入與刪除算法中，可以看到要取鏈表中某個(gè)結(jié)點(diǎn)，必須從鏈表的頭結(jié)點(diǎn)開始一個(gè)一個(gè)地向后查找，即不能直接存取線性鏈表中的某個(gè)結(jié)點(diǎn)。

9、 這是因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是隨機(jī)存儲(chǔ)結(jié)構(gòu)。 雖然在線性鏈表中插入或刪除結(jié)點(diǎn)不需要移動(dòng)別的數(shù)據(jù)元素，但算法尋找第i-1個(gè)或第i個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。,比較插入算法與刪除算法,循環(huán)單鏈表(Circular Linked List)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。,2.3.2 循環(huán)單鏈表,（a）為帶頭結(jié)點(diǎn)的循環(huán)單鏈表的空表形式， （b）為帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式。,2.3.3 雙向鏈表,1雙向鏈表 在單鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指示后繼的指針域，因此從任何一個(gè)結(jié)點(diǎn)都能通過指針域

10、找到它的后繼結(jié)點(diǎn)； 若需找出該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則需從表頭出發(fā)重新查找。 換句話說，在單鏈表中，查找某結(jié)點(diǎn)的后繼結(jié)點(diǎn)的執(zhí)行時(shí)間為O(1)，而查找其前驅(qū)結(jié)點(diǎn)的執(zhí)行時(shí)間為O(n)。 可用雙向鏈表來克服單鏈表的這種缺點(diǎn)，在雙向鏈表中，每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域，一個(gè)指針（next）指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（prior）指向它的前驅(qū)結(jié)點(diǎn)。 雙向鏈表的結(jié)構(gòu)可定義如下：,typedef struct node Elemtype data; struct node *prior, *next; dlnodetype;,和單鏈的循環(huán)表類似，雙向鏈表也可以有循環(huán)表，讓頭結(jié)點(diǎn)的前驅(qū)指針指向鏈表

11、的最后的一個(gè)結(jié)點(diǎn)，讓最后一個(gè)結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn)。,若p為指向雙向鏈表中的某一個(gè)結(jié)點(diǎn)ai的指針，則顯然有： p-next-prior=p-prior-next=p,p,（1）在雙向鏈表中插入一個(gè)結(jié)點(diǎn) 在雙向鏈表的第i個(gè)元素前插入一個(gè)結(jié)點(diǎn)時(shí)，可用指針p指該結(jié)點(diǎn)（稱p結(jié)點(diǎn)）。 將新結(jié)點(diǎn)的prior指向p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)， 將p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)， 將新結(jié)點(diǎn)的next指向p結(jié)點(diǎn)， 將p結(jié)點(diǎn)的prior指向新結(jié)點(diǎn)。,2雙向鏈表的基本操作,在雙向鏈表中，有些操作如：求長(zhǎng)度、取元素、定位等，因僅需涉及一個(gè)方向的指針，故它們的算法與線性鏈表的操作相同； 在插入、刪除時(shí)，需同時(shí)修改兩個(gè)方

12、向上的指針，兩者的操作的時(shí)間復(fù)雜度均為O(n)。,【算法2.18 雙向鏈表的插入】 int insert_dl(dlnodetype *head, I nt i, Elemtype e) /*在帶頭結(jié)點(diǎn)的雙向鏈表中第i個(gè)位置之前插入元素e*/ dlnodetype *p,*s; int j; j=0; p=head; while (p!=NULL ,在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)，可用指針p指向該結(jié)點(diǎn)（稱p結(jié)點(diǎn)）。 將p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next指向p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)， 將p的下一個(gè)結(jié)點(diǎn)的prior指向p的上一個(gè)結(jié)點(diǎn)。,（2）在雙向鏈表中刪除一個(gè)結(jié)點(diǎn),int Delete_dl(dlnodetyp

13、e *head, int i, ElemType ,【算法2.19 雙向鏈表的刪除】,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)： （1）結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放； （2）數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，不需要移動(dòng)數(shù)據(jù)元素。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)： （1）每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間。 （2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。,2.4 線性表的應(yīng)用示例,（一）一元多項(xiàng)式的表示和相加,在數(shù)學(xué)上，一個(gè)一元n次多項(xiàng)式可表示為 Pn(x)=p0+p1x+p2x2+pnxn 它由(n+1)個(gè)系數(shù)序列p0、p1、pn 唯一地確定。因此，在計(jì)算機(jī)中，它可用一個(gè)線性表P來表示： P=(p0, p1, ,pn) 其中，p

14、i代表Pn(x)中的i次項(xiàng)系數(shù)。 在這種表示法中，系數(shù)所對(duì)應(yīng)的指數(shù)隱含在系數(shù)的序號(hào)中，所以值為0的系數(shù)也要列出。 現(xiàn)考慮兩多項(xiàng)式進(jìn)行符號(hào)相加的問題。 設(shè)Qm(x)是另一個(gè)一元m次多項(xiàng)式，它的線性表表示為 Q=(q0, q1, , qm),為解決0系數(shù)問題，可以不存貯0值元素。但這樣就不能利用位置關(guān)系隱含指出系數(shù)對(duì)應(yīng)的指數(shù)了，而必須顯式地給出指數(shù)。 對(duì)任一個(gè)一元n次多項(xiàng)式，若不寫出系數(shù)為0的項(xiàng)，則可表示為 pn(x) = p1xe1+p2xe2+ +pnxen 這里，p1, p2, , pn均非0，e1e2 =0 TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) 數(shù)據(jù)關(guān)系：R1=

15、|ai-1,ai D,且ai-1中的指數(shù)值 ai中的指數(shù)值 基本操作： CreatPolyn( int expn; typedef LinkList polynomial; /用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式 void CreatPolyn(polynomail ,多項(xiàng)式相加示例,void AddPolyn(polynomial /switch, /while if(!ListEmpty(Pb) Append(Pa,qb); FreeNode(hb); /AddPolyn,作業(yè)： 1、假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A、B，同一個(gè)表中的元素值各不相同，現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表C，其元素為A和B中元素的交集，且表C中的元素也依值遞增有序排列。試對(duì)順序表編寫求C的算法。 2、設(shè)線性表中數(shù)據(jù)元素的總數(shù)基本不變，并很少進(jìn)行插入或刪除工作，若要以最快的速度存取線性表中的數(shù)據(jù)元素，應(yīng)選擇線性表的何種存儲(chǔ)結(jié)構(gòu)？為什么? 3、順序表和鏈表在進(jìn)行插入操作時(shí)，有什么不同？ 4、寫出在