計算機(jī)軟件及應(yīng)用數(shù)據(jù)結(jié)構(gòu)吳偉民編著PPT課件

1、第二章 線性表教學(xué)目的：（1）了解線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲實現(xiàn)方式；（2）熟練掌握順序表的定義與實現(xiàn)，包括查找、插入、刪除算法的實現(xiàn)；（3）熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表操作的基本方法，能在實際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。教學(xué)的重點和難點：鏈表。 第1頁/共51頁 2.1 線性表的定義及運算 1.線性表的定義： 是由n(n=0)個數(shù)據(jù)元素（結(jié)點）a1,a2,a3, an組成的有限序列。 其中： n為數(shù)據(jù)元素的個數(shù)，也稱為表的長度。 當(dāng)n=0 時，稱為空表。 非空的線性表(n0) 記作： （ a1,a2,a3, an）第2頁/共51頁 2.線性表的邏輯特征： （1）有且僅有一

2、個開始結(jié)點a1(無直接前趨）； （2）有且僅有一個終端結(jié)點an(無直接后繼）； （3）其余的結(jié)點ai 都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。)12(ni（4） ai是屬于某個數(shù)據(jù)對象的元素，它可以是一個數(shù)字、一個字母或一個記錄。第3頁/共51頁 3.線性表的特性 （1）線性表中的所有數(shù)據(jù)元素的數(shù)據(jù)類型是一致的。 （2）數(shù)據(jù)元素 在線性表中的位置只取決于它的序號。 （3）結(jié)點間的邏輯關(guān)系是線性的。 a1 a2 an 圖2-1 線性表邏輯結(jié)構(gòu)示意圖 線性表的形式化定義為：線性表的形式化定義為： linear_list=(D,R)其中其中 D=ai 1in,n0,aielemtype

3、 R= 1in-1第4頁/共51頁 例1、26個英文字母組成的字母表 （A，B，C、Z）例2、某校從1978年到1983年各種型號的計算機(jī)擁有量的變化情況。 （6，17，28，50，92，188）第5頁/共51頁例例3、學(xué)生健康情況登記表如下：、學(xué)生健康情況登記表如下：姓 名學(xué) 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .抽象數(shù)據(jù)類型的定義為：P19第6頁/共51頁 4. 線性表的運算 數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而具體的實現(xiàn)則在存儲結(jié)構(gòu)上進(jìn)行。 （1）存取 （

4、2）插入 （3）刪除 （4）查找 （5）合并 （6）分解 （7）排序 （8）求線性表的長度 基本運算第7頁/共51頁 2.2 線性表的順序存儲結(jié)構(gòu)（順序表） 1.順序表的定義： 用一組連續(xù)的存儲單元（地址連續(xù)）依次存放線性表的各個數(shù)據(jù)元素。 即：在順序表中邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位置也是相鄰的。第8頁/共51頁2.順序表中數(shù)據(jù)元素的存儲地址若一個數(shù)據(jù)元素占L個存儲單元，則其存儲方式參見下圖。a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + +

5、 L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L第9頁/共51頁 從圖中可以看出, LOC（a i+1）=LOC(a i)+l 一般地,有 第i個數(shù)據(jù)元素的存儲位置為： LOC（a i）=LOC(a 1)+(i-1)*l LOC(a 1)稱為基地址（第一個數(shù)據(jù)元素的存儲位置）。 顯然，數(shù)據(jù)元素在順序表中位置取決于數(shù)據(jù)元素在線性表中的位置。 順序表的特點 是：邏輯位置相鄰，其物理位置也相鄰。第10頁/共51頁一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的個個字節(jié)字節(jié)存儲。存

6、儲器按字節(jié)編址，設(shè)存儲數(shù)組元素存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是，則，則 的第一個字節(jié)的地址是的第一個字節(jié)的地址是 113例1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址計算通式為：地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）第11頁/共51頁 3.順序表的描述： 由于由于C C語言中的一維數(shù)組也是采用順序存儲語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之又因為除了用數(shù)組來存儲線性表的元素之

7、外，順序表還應(yīng)該用一個變量來表示線性外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。義順序表類型。 # define ListSize 100 typedef int ElemType; typedef struc ElemType dataListSize; int length; Sqlist;第12頁/共51頁4.順序表的幾種基本運算 在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是L.

8、datai-1。 以下主要討論線性表的插入和刪除兩種運算。 1、插入 線性表的插入運算是指在表的第i(1in+1)個位置上，插入一個新結(jié)點x，第13頁/共51頁使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，an) 插入算法的思想：1、將ai,ai+1,.,an依次后移一個位置，使第i位置留空2、將新元素x放在空出的位置上。3、線性表長度加1。演示第14頁/共51頁內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+

9、1an-1x第15頁/共51頁Void InsertList(Sqlist*L，ElemType x，int i) int j; if(iL-length+1) printf(“Position error”); return ERROR; if(L-length=ListSize) printf(“overflow”); exit(overflow); for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-length+; 第16頁/共51頁插入算法分析：上述算法for循環(huán)語句的執(zhí)行次數(shù)為n-i+1;若i=1,需移動全部n個

10、結(jié)點（最壞：O(n)）若i=n+1（在表尾插入）,無需用移動結(jié)點，直接插入即可。（最好O(1)）移動結(jié)點的平均次數(shù)：)1(11inPEniiI第17頁/共51頁按等概率考慮： 可能的插入位置為i=1,2,n,n+1共n+1個，則pi=1/(n+1) 所以1111) 1(11) 1(niniiIinninPE2)1(2)1)1()1111nnnnnn（順序表插入算法平均約需移動一半結(jié)點。第18頁/共51頁 2、刪除 線性表的刪除運算是指將表的第i(1in)結(jié)點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1，an)

11、刪除算法的思想：1、將ai+1,.,an依次前移一個位置2、線性表長度減1。演示第19頁/共51頁內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號i+1n-1nanai+2第20頁/共51頁 Void deleteList(Sqlist*L，int i) int j; if(iL-length) printf(“Position error”); return ERROR; for( j=i;jlength-1;j+) L-data j-1=L-data j; L-length-; 第21

12、頁/共51頁刪除算法分析： 上述算法for循環(huán)語句的執(zhí)行次數(shù)為n-i; 若i=1,最壞：O(n) 若i=n,無需用移動結(jié)點，直接刪除即可。（最好O(1)） 移動結(jié)點的平均次數(shù)：)(1inPEniid第22頁/共51頁按等概率考慮： 可能的刪除位置為i=1,2,n共n個，則pi=1/n 所以順序表插入算法平均約需移動一半結(jié)點。小結(jié)：順序表插入、刪除算法平均約需移動一半結(jié)點，當(dāng)n很大時，算法的效率較低。niniiIinninPE11)(1)(212)()11nnnnnn（第23頁/共51頁順序表存儲空間的動態(tài)分配 若將前面線性表的順序存儲結(jié)構(gòu)類型中的數(shù)組形式改為指針形式，則得到動態(tài)分配形式如下：

13、typedef int ElemType; typedef struct ElemType *elem; int length; int listsize; Sqlist;第24頁/共51頁順序存儲結(jié)構(gòu)的優(yōu)缺點 優(yōu)點 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲空間使用緊湊 缺點 插入、刪除操作需要移動大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充第25頁/共51頁 2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲方式 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素 利用指針實現(xiàn)用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點:數(shù)據(jù)ai的

14、鏈?zhǔn)酱鎯τ诚? 數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲位置數(shù)據(jù)域 指針域結(jié)點鏈?zhǔn)酱鎯Y(jié)構(gòu):n個結(jié)點鏈結(jié)成的一個鏈表第26頁/共51頁 單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故設(shè)頭指針head指向開始結(jié)點。同時，由于終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即null（圖示中也可用表示)。一、線性鏈表結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的單鏈表示意圖如下第27頁/共51頁ZHAOQIANSUNLIZHOUWUZHENGWANGH43131NULL3771925數(shù)

15、據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針第28頁/共51頁listnode *h,*p;datanextp結(jié)點（*p）(*p)表示p所指向的結(jié)點(*p).datap-data表示p指向結(jié)點的數(shù)據(jù)域(*p).nextp-next表示p指向結(jié)點的指針域生成一個listnode型新結(jié)點：p=(listnode *)malloc(sizeof(listnode);系統(tǒng)回收p結(jié)點：free(p)Typedef char Elemtype;Typedef struct node Elemtype data; struct node

16、*next;listnode;用C語言描述的單鏈表如下：第29頁/共51頁頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一 個結(jié)點叫頭結(jié)點指針域為空表示線性表為空ha1a2頭結(jié)點an .h空表 不帶頭結(jié)點的單鏈 表 a1 head a2 an 第30頁/共51頁 單鏈表上的查找運算(1) 按序號查找get(L,i)在單鏈表L中查找第i個位置上的元素，若找到，則返回它的地址，否則返回NULL。算法思想如下： 從頭結(jié)點開始順鏈掃描，用指針p指向當(dāng)前掃描到的結(jié)點，用j作統(tǒng)計已掃描結(jié)點數(shù)的計數(shù)器，當(dāng)p掃描下一個結(jié)點時，j自動加1。 P的初值指向頭結(jié)點，j的初值為0。 當(dāng)j=i時，指針p所指的結(jié)點就是第i個結(jié)點。第3

17、1頁/共51頁listnode *get(listnode *L,int i) int j; listnode *p; j=1; p=L-next; while(jnext; return p; 算法的時間復(fù)雜度都為(n)。 第32頁/共51頁(2) 按值查找Locate(L,x)在單鏈表L中，查找值為x的結(jié)點，若找到，返回它的地址，否則返回NULL。算法思想如下： 從開始結(jié)點出發(fā)，順鏈逐個結(jié)點的值和給定值key作比較。listnode *Locate(listnode *head,elemtype x) listnode *p; p=head-next; while(p!=NULL)&(p-

18、data!=x) p=p-next; return p; 算法的時間復(fù)雜度都為算法的時間復(fù)雜度都為(n)。 第33頁/共51頁單鏈表上的插入運算 若將x插入a和b 之間，插入結(jié)點的指針變化如圖所示。 算法思想： (1)先求出第i-1個結(jié)點 (2)然后在第i-1個結(jié)點之后插入結(jié)點x。pabxss-next=p-next;p-next=s;第34頁/共51頁 INSERT（ listnode *L, elemtype x, int i) listnode *p,*s; int j; p=L;j=0; while(p & jnext;+j; if (p=null) printf(“找不到插入點n“）

19、 else s=(listnode*) malloc(sizeof(listnode); s-data=x;s-next=p-next; p-next=s; /*end*/第35頁/共51頁 單鏈表上的刪除運算若將x刪除，刪除結(jié)點的指針變化所示。 p q a1 x a2 圖 刪除結(jié)點的指針修改 思想：先找到被刪結(jié)點（第i個）的前趨結(jié)點，即第i-1個結(jié)點*p,然后刪除*p的后繼。第36頁/共51頁DELETE(listnode *L,int i) listnode *p,*q; int j; p=L;j=0; while(p-next & jnext;+j; if (P-next!=null)

20、q=p-next;p-next=q-next; free(q); else printf(“errorn”) /*end*/思考：如何實現(xiàn)刪除線性表head中數(shù)據(jù)域為a的結(jié)點。第37頁/共51頁建立單鏈表-頭插法建表：思想：從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 h頭結(jié)點an 0h頭結(jié)點an-10an a2.h頭結(jié)點an-10an ha1a2頭結(jié)點an .0h頭結(jié)點0第38頁/共51頁Listnode * creatlist(int n) listnode *p,*L; int i; L=(list

21、node *)malloc(sizeof(listnode); L-next=NULL; for(i=n;i0;i-) p=(listnode*)malloc(sizeof(listnode); scanf(&p-data); p-next=L-next; L-next=p; return L; 第39頁/共51頁單鏈表特點 它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用 不需預(yù)先分配空間 指針占用額外存儲空間 不能隨機(jī)存取，查找速度慢第40頁/共51頁二、循環(huán)鏈表(circular linked list) 循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀 特點：從表中任一結(jié)點出發(fā)均

22、可找到表中其他結(jié)點，提高查找效率 操作與單鏈表基本一致,循環(huán)條件不同 單鏈表p或p-next=NULL 循環(huán)鏈表p或p-next=Hhh空表第41頁/共51頁在有些情況下，在循環(huán)鏈表中設(shè)立尾指針而不設(shè)頭指針，可使某些操作簡化。例如將兩個線性鏈表合并成一個表時，只需將一個表的表尾與另一個表的表頭相接。第42頁/共51頁例:在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個線性表的運算。 linklist connect(linklist *heada,linklist *headb) linklist p=heada-next; heada-next=(he

23、adb-next)-next free(headb-next); headb-next=p; return(headb); 第43頁/共51頁三、雙向鏈表（double linked list）單鏈表具有單向性的缺點 結(jié)點定義typedef struct node elemtype data; struct node *prior,*next;JD;priordatanextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp-prior-next= p= p-next-proir;第44頁/共51頁bcaPvoid del_dulist(listnode *p)p-prior-next=p-

24、next; p-next-prior=p-prior; free(p);v刪除l 算法描述p-prior-next=p-next;p-next-prior=p-prior;第45頁/共51頁void ins_dulist(listnode* p,int x)listnode *s; s=(listnode*)malloc(sizeof(listnode); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l 算法描述xSbaPv插入第46頁/共51頁2.4 線性表的應(yīng)用舉例 一元多項式的表示及相加 一元多項式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示200001000231)(xxxS但對S(x)這樣的多項式浪費空間一般emmnxPxPxPxPee2121)(其中為非零系數(shù)）（iPemee210用數(shù)據(jù)域含兩個數(shù)據(jù)項的線