線性表-數(shù)據(jù)結(jié)構(gòu).ppt

1、第二章 線性表,課前導(dǎo)學(xué),2.1 線性表的類型定義 2.2 線性表的順序表示與實(shí)現(xiàn) 2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 2.4 一元多項(xiàng)式的表示及相加,學(xué)習(xí)目標(biāo),1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系。 2. 熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 3. 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。 4. 結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。,重點(diǎn)和難點(diǎn),鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的

2、頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。,線性結(jié)構(gòu)的特點(diǎn),在數(shù)據(jù)元素的非空有限集中 存在唯一一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素； 存在唯一一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素； 除第一個(gè)數(shù)據(jù)元素之外，每個(gè)元素都只有一個(gè)前驅(qū)； 除最后一個(gè)數(shù)據(jù)元素之外，每個(gè)元素都只有一個(gè)后繼。,線性表的定義,一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。 除了第一個(gè)元素沒(méi)有直接前驅(qū)和最后一個(gè)元素沒(méi)有直接后繼之外，其余的每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。,線性表的特征,有窮性：由有限個(gè)元素組成，元素個(gè)數(shù)n表長(zhǎng)度，n=0空表。設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱

3、 i 為 ai 在線性表中的位序。 有序性：線性表元素之間存在序偶關(guān)系，1in時(shí) ai的直接前驅(qū)是ai-1，a1無(wú)直接前驅(qū) ai的直接后繼是ai+1，an無(wú)直接后繼 同一性：線性表屬于同類數(shù)據(jù)元素組成，每一個(gè)對(duì)象都屬于同一數(shù)據(jù)對(duì)象,抽象數(shù)據(jù)類型線性表的定義如下：,ADT List 數(shù)據(jù)對(duì)象：D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： （1）InitList（ GetElem(LB, i)e 依值在線性表LA中進(jìn)行查訪; LocateElem(LA, e, equal( ) 若不存在，則插入之。 ListI

4、nsert(LA, n+1, e) 算法的時(shí)間復(fù)雜度： O（ListLength(LA) ListLength(LB)）,思路：,實(shí)現(xiàn)：void union(List ,結(jié)構(gòu)體類型的使用,結(jié)構(gòu)體的定義方式： struct 結(jié)構(gòu)體名 成員列表 變量名稱； 例如： typedef struct student int num; /學(xué)號(hào) char name20; int age; stu; /定義一種學(xué)生結(jié)構(gòu)體類型，并將此類型重新定義名稱為stu類型,結(jié)構(gòu)體變量的引用：,結(jié)構(gòu)體變量名.成員名。student1.num=20; 指向結(jié)構(gòu)體變量的指針的使用 stu *p;/p為指向結(jié)構(gòu)體類型的指針 p=

5、 則*p代表的結(jié)構(gòu)體變量student1 通過(guò)p引用結(jié)構(gòu)體變量的成員為 p-num 或者（*p）.num。,2.2線性表的順序存儲(chǔ)結(jié)構(gòu),定義：線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素。 使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。 假設(shè)線性表中有n個(gè)元素，每個(gè)元素占L個(gè)單元，第一個(gè)元素的地址為loc(a1)，則可以通過(guò)如下公式計(jì)算出第i個(gè)元素的地址Loc(ai)： loc(ai+1) =loc(ai)+L loc(ai) =loc(a1)+(i-1)L (2-2) 其中l(wèi)oc(a1) 稱為基址。,線性表

6、的順序存儲(chǔ)結(jié)構(gòu)是一種隨即存取的存儲(chǔ)結(jié)構(gòu)，只要確定了起始位置，就可以訪問(wèn)表中的任何一個(gè)元素。,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的誤區(qū),只動(dòng)眼、耳，不動(dòng)手 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的有效方法是動(dòng)手，動(dòng)腦。 (2)有的同學(xué)認(rèn)為，數(shù)據(jù)結(jié)構(gòu)是C語(yǔ)言的延續(xù)，這是一種錯(cuò)誤的想法。 C語(yǔ)言僅僅是一個(gè)程序設(shè)計(jì)工具，而數(shù)據(jù)結(jié)構(gòu)則是程序設(shè)計(jì)的思想和靈魂，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過(guò)程中經(jīng)常會(huì)接觸到C語(yǔ)言的知識(shí)，這只不過(guò)是借用C語(yǔ)言這個(gè)工具來(lái)表達(dá)數(shù)據(jù)結(jié)構(gòu)的思想而已，我們也可以不選用C語(yǔ)言，而選擇其它語(yǔ)言，如PASCAL、JAVA等，所以，不應(yīng)該把數(shù)據(jù)結(jié)構(gòu)當(dāng)成C語(yǔ)言來(lái)學(xué)習(xí)。 死記硬背 分析每一種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方式和操作算法，養(yǎng)成提出問(wèn)題、分析問(wèn)題和解決問(wèn)

7、題的思維習(xí)慣，提升自己分析問(wèn)題和解決問(wèn)題的能力。,課程回顧,線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表的初始化 線性表插入操作,順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義,#define LIST_INT_SIZE 100 #define LISTINCREAMENT 10 typedef struct ElemType *elem； / 線性表占用的數(shù)組空間。 int length；/ 線性表的長(zhǎng)度 int listsize； /當(dāng)前分配的存儲(chǔ)容量 SeqList；,線性表的基本操作在順序表中的實(shí)現(xiàn),InitList( If (! L-elem) exit(OVERFLOW); /存儲(chǔ)分配失敗 L-length=0; /空

8、表長(zhǎng)度為0 L-listsize= LIST_INIT_SIZE; /初始存儲(chǔ)容量 return OK; /InitList_Sq,二、線性表的順序表插入操作 ListInsert( if (i L.length+1) return ERROR; / 插入位置不合法 if (L-length = L- listsize) . q = ,newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/ 當(dāng)前存儲(chǔ)空間已滿 L- elem=

9、newbase; L- list size+=LISTINCREMENT;,考慮移動(dòng)元素的平均情況:,假設(shè)在第 i 個(gè)元素之前插入的概率為 則在長(zhǎng)度為n 的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：,若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：,線性表操作 ListDelete( i elemi-1= L- elemi; / 被刪除元素之后的元素左移 -L- length; / 表長(zhǎng)減1 return OK;,*e= L-elemi-1; / 被刪除元素的值賦給 e k= L- length-1; / 表尾元素的位置,if (i L.length) re

10、turn ERROR; / 刪除位置不合法,考慮移動(dòng)元素的平均情況:,假設(shè)刪除第 i 個(gè)元素的概率為 , 則在長(zhǎng)度為n 的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：,若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：,int LocateElem_Sq(SqList L, ElemType e,) / 在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回 0 / LocateElem_Sq,if (i = L.length) return i; else return 0;,int i i= 1; / i 的初值為第 1 元素的位

11、序,while (i = L.length ,/找到滿足條件的元素,/ 沒(méi)有找到滿足條件的元素,時(shí)間復(fù)雜度為：0(L.length),線性表的查找操作,例如：順序表,e =,38,i,1,2,3,4,1,8,50,可見，基本操作是， 將順序表中的元素 逐個(gè)和給定值 e 相比較。,順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：,優(yōu)點(diǎn)： 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲(chǔ)空間使用緊湊 缺點(diǎn) 插入、刪除操作需要移動(dòng)大量的元素,順序表習(xí)題作業(yè)：,學(xué)號(hào)結(jié)尾為1，3，5的同學(xué)交作業(yè)，作業(yè)內(nèi)容：教材算法2.7，完整的c程序結(jié)構(gòu)。,線性表的合并問(wèn)題,例1、已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將LA和LB

12、歸并為一個(gè)新的鏈表LC，且LC中的數(shù)據(jù)元素仍按非值遞減有序排序。 例如：LA（3,5,8,11） LB（2,6,8,9,11,15,20） 則LC（2,3,5,6,8,8,9,11,11,15,20）,線性表的一般算法： Void MergeList（List La，List Lb，List Lc） InitList（Lc）； ij1；k0； La_lenListLength（La）；Lb_lenListLength(Lb)； While（(i=La_len) /Mergelist,順序表中的實(shí)現(xiàn) Void MergeList(SqList La, SqList Lb, SqList *Lc)

13、 int *pa,*pb,*pc,* pa_last,* pb_last; pa=La.elem;pb=La.elem; Lc-listsize=Lc.length=La.length+ Lb.length; pc=Lc-elem=(ElemType*)malloc(Lc-istsize*sizeof(ElemType); If(!Lc-elem) exit(overfiow); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last ,2.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn),特點(diǎn)： 用一組任意的存儲(chǔ)單元存儲(chǔ)

14、線性表的數(shù)據(jù)元素 利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 結(jié)點(diǎn):數(shù)據(jù)元素ai 的存儲(chǔ)映像。 數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲(chǔ)位置,例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,頭指針,2.3.1 單鏈表 (或線性鏈表),1. 定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表。 2. 特征 每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。 線性結(jié)構(gòu) 結(jié)點(diǎn)可以不連續(xù)存儲(chǔ) 表可擴(kuò)充,data next,3. 單鏈表的存儲(chǔ)映像,free,(a)

15、可利用存儲(chǔ)空間,a1,a3,a2,a4,free,first,(b) 經(jīng)過(guò)一段運(yùn)行后的單鏈表結(jié)構(gòu),以線性表中第一個(gè)數(shù)據(jù)元素 的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針,頭結(jié)點(diǎn),頭指針,頭指針,有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針,空指針,線性表為空表時(shí)， 頭結(jié)點(diǎn)的指針域?yàn)榭?4. 單鏈表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)用C語(yǔ)言中的“結(jié)構(gòu)指針”來(lái)描述,typedef struct LNode ElemType data; struct LNode *next; LNode ，*LinkList;,struct LNode ElemType data; stru

16、ct LNode *next; ; typedef LNode * LinkList;,單鏈表特點(diǎn): 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 不需預(yù)先分配空間 指針占用額外存儲(chǔ)空間 不能隨機(jī)存取，查找速度慢,生成一個(gè)LNode型新結(jié)點(diǎn)：p=(LinkList)malloc(sizeof(LNode); 系統(tǒng)回收p結(jié)點(diǎn)：free(p),線性表的操作 GetElem(L, i, j = 1; / p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器,while (p / 順指針向后查找，直到 p 指向第 i 個(gè)元素 / 或 p 為空,if ( !p | ji ) return ERROR; / 第 i 個(gè)元素不存在

17、 *e = p-data; / 取得第 i 個(gè)元素 return OK;,單鏈表中的插入與刪除,插入 第一種情況：在第一個(gè)結(jié)點(diǎn)前插入 s = (LinkList)malloc(sizeof(LNode);/ 生成新結(jié)點(diǎn) if ( s = null) return ERROR; s-data = e; s-next = first ; first = s;,（插入前） （插入后）,a1,a2,first,e,s,e,s,a1,first,a2,ai,e,(插入前) (插入后),第二種情況：在鏈表中間插入 s-next = p-next; p-next = s；,ai,ai-1,p,e,ai-1,

18、s,p,s,第三種情況：在鏈表末尾插入 s-next= p-next; p-next = s；,(插入前) (插入后),e,s,e,s,p,p,單鏈表的插入算法,int ListInsert_L ( LinkList L, int i, int e ) / 在帶頭結(jié)點(diǎn)的單鏈線性表L中第 i 個(gè)位置之前插入元素 e LNode *p,*s; int j; p = L; j = 0; while ( p ,刪除 第一種情況: 刪除表中第一個(gè)元素 第二種情況: 刪除表中或表尾元素,在單鏈表中刪除含ai的結(jié)點(diǎn),ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,刪除前,刪除后,p-next =

19、 q-next,單鏈表的刪除算法,int ListDelete_L ( LinkList L, int i, int *e ) / 在帶頭結(jié)點(diǎn)的單鏈線性表 L 中，刪除第 i 個(gè)元素，并由 e 返回其值 LNode *p,*q; int j; p = L; j = 0; while ( p-next / LinkDelete_L,T(n)=O(n),5. 動(dòng)態(tài)建立單鏈表算法：,動(dòng)畫2-3-2.swf演示,算法評(píng)價(jià),算法思路： （1）創(chuàng)建頭結(jié)點(diǎn) （2）逆序創(chuàng)建結(jié)點(diǎn)n，修改結(jié)點(diǎn)指針，再創(chuàng)建結(jié)點(diǎn)n-1,直到結(jié)點(diǎn)1,void CreateList_L ( LinkList *L, int n ) /

20、逆位序輸入 n 個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表 L LNode *p; int i; * L = ( LinkList ) malloc ( sizeof ( LNode ) ); (*L)-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表 for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新結(jié)點(diǎn) scanf (%d , / 修改單鏈表頭結(jié)點(diǎn)的指針域 ,/單鏈表的建立算法,void init_linklist(LinkList *l) /*對(duì)單鏈表進(jìn)行初始化*/ *l=(LinkLis

21、t)malloc(sizeof(Node); (*l)-next=NULL; void CreateList_L ( LinkList L, int n ) / 逆位序輸入 n 個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表 L LNode *p; int i; for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新結(jié)點(diǎn) scanf (%d , / 修改單鏈表頭結(jié)點(diǎn)的指針域 ,線性表的合并問(wèn)題,例1、已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將LA和LB歸并為一個(gè)新的鏈表LC，且LC中的數(shù)據(jù)元素仍

22、按非值遞減有序排序。 例如：LA（3,5,8,11） LB（2,6,8,9,11,15,20） 則LC（2,3,5,6,8,8,9,11,11,15,20）,線性表的一般算法： Void MergeList（List La，List Lb，List Lc） InitList（Lc）； ij1；k0； La_lenListLength（La）；Lb_lenListLength(Lb)； While（(i=La_len) /Mergelist,順序表中的實(shí)現(xiàn) Void MergeList(SqList La, SqList Lb, SqList *Lc) Pa=La.elem;pb=La.elem

23、; Lc-listsize=Lc.length=La.length+ Lb.length; Pc=Lc-elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); If(!Lc.elem) exit(overfiow); Pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; While(pa=pa_last ,例: 將兩個(gè)有序鏈表歸并為一個(gè)有序鏈表,void MergeList_L ( LinkList La, LinkList Lb, LinkList *Lc, ) / 歸并 La 和

24、 Lb 得到新的單鏈表 Lc ，Lc 的元素也按非遞減排列 Node *pa,*pb; pa = La-next; pb = Lb-next; *Lc = pc = La; / 用 La 的頭結(jié)點(diǎn)作為 Lc 的頭結(jié)點(diǎn) while ( pa / 釋放 Lb 的頭結(jié)點(diǎn) / MergeList_L,一、概念題 在順序表中要插入一個(gè)元素平均需要移動(dòng)_次元素，具體移動(dòng)元素的個(gè)數(shù)與_ _ _ _ _有關(guān)。,n/2,元素的具體位置, 單鏈表中，除頭節(jié)點(diǎn)外，任一節(jié)點(diǎn)的存儲(chǔ)位置由_確定。,其前驅(qū)節(jié)點(diǎn)指針域的值,頭結(jié)點(diǎn)、頭指針、和第一個(gè)結(jié)點(diǎn)的區(qū)別。,順序存儲(chǔ)結(jié)構(gòu)是通過(guò)（ ）表示元素之間的關(guān)系的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)

25、（ ）表示元素之間的關(guān)系的。（北京理工2001）。 在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是（ ）。（合肥工業(yè)大學(xué)1999）。 在單鏈表p所指結(jié)點(diǎn)之后插入s節(jié)點(diǎn)的基本操作是（ ）。（青島大學(xué)）。 對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空的條件是（ ）。 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）。（北京理工2006）. 對(duì)于一個(gè)線性表即要求能夠進(jìn)行較快速的插入和刪除操作，又要求存儲(chǔ)結(jié)構(gòu)能夠反映出來(lái)數(shù)據(jù)之間的邏輯關(guān)系，則應(yīng)該采用（ ）存儲(chǔ)結(jié)構(gòu)。（哈工大2005） 對(duì)于順序表，訪問(wèn)元素和增加、刪除元素的時(shí)間復(fù)雜度是分別是（ ）、（ ）。,畫出下列各語(yǔ)句執(zhí)行后各指針及鏈表的示意圖。,L(

26、LinkList)malloc(sizeof(LNode); P=L;,for(I=1；Inext= (LinkList)malloc(sizeof(LNode) P=P-next; P-data=I*2-1; ,P-next=NULL;,For(I=4;I=1;I+) ins_Linklist(L,I+1,I*2),For(I=1;I=3;I+) Del_Linklist(L,i);,有一個(gè)單鏈表，頭指針為head，編寫一個(gè)函數(shù)，計(jì)算數(shù)據(jù)域?yàn)閤的節(jié)點(diǎn)的個(gè)數(shù)。 設(shè)計(jì)思想： 遍歷鏈表，設(shè)立一個(gè)計(jì)數(shù)器，每當(dāng)遇到一個(gè)數(shù)據(jù)域?yàn)閄的節(jié)點(diǎn)，計(jì)數(shù)器加1。 自己動(dòng)手寫。,int count(Linklist

27、head,int x) node *head， node *p; int j=0; p=head; while(p!=NULL) if(p-data=x) j+; p=p-next; return (j); ,實(shí)現(xiàn)單鏈表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2,an）逆置為(an,an-1,a1)。 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。 編寫程序，刪除線性表a中第i個(gè)元素起的k個(gè)元素。,下面我們將看幾個(gè)在線性表中經(jīng)常會(huì)出現(xiàn)的算法和概念題。 練習(xí)1、把L中值為奇數(shù)的結(jié)點(diǎn)刪除，并用來(lái)生成新表L1。,算法思想： 生成一個(gè)新的節(jié)點(diǎn)，表示新的鏈表頭節(jié)

28、點(diǎn)。 從第一個(gè)節(jié)點(diǎn)開始，判斷其奇偶性。 若為奇數(shù)，則將其鏈到新的鏈表上，否則比較下一個(gè)。,status List_L(LinkList L) p = L; q = p-next; (p為前驅(qū)結(jié)點(diǎn)地址指針變量） s = (LinkList) malloc ( sizeof (Lnode); s-next = NULL; L1 = S ; while (q!= NULL) if （q -data mod 2 = 0） p = q ; q = q-next ; else p-next = q-next; q-next = s-next ;s-next = q ; q = p-next ; retur

29、n OK; ,8. 靜態(tài)鏈表,動(dòng)態(tài)鏈表 鏈表中的結(jié)點(diǎn)空間都是動(dòng)態(tài)申請(qǐng)和釋放的。 在有些高級(jí)語(yǔ)言（如BASIC）中，沒(méi)有提供指針類型，此時(shí)若仍想采用鏈表作為線性表存儲(chǔ)結(jié)構(gòu)? 則只能借助一維數(shù)組來(lái)模擬鏈表，,定義：用數(shù)組描述的鏈表叫靜態(tài)鏈表 存儲(chǔ)結(jié)構(gòu)： #define MAXSIZE = 100; /靜態(tài)鏈表的最大長(zhǎng)度 typedef struct ElemType data; int cur; /游標(biāo),代替指針指示結(jié)點(diǎn)在數(shù)組中的位置 component,SLinkListMAXSIZE; 目的是為了在不設(shè)指針類型的高級(jí)程序設(shè)計(jì)語(yǔ)言中使用鏈表結(jié)構(gòu)。樹的雙親表示法、圖的鄰接表表示法、表插入排序、等都

30、用到了靜態(tài)鏈表。,靜態(tài)鏈表結(jié)構(gòu)示例,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,插入shi,修改前的狀態(tài),修改后的狀態(tài),刪除zheng,S0.cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置,shi,9,5,5,8,游標(biāo)cur PK 指針next,1、指針next是個(gè)地址，游標(biāo)cur是？ int cur；指示后繼元素在數(shù)組中的相對(duì)位置 2、指針后移實(shí)現(xiàn)了，游標(biāo)cur后移呢？ p = p-next； 已知：SLinkList S； i = Si.cur;,一般情況下，對(duì)靜態(tài)鏈表S，如果Si.data=ak，則 ak+1= S?.data,Si.cur,靜態(tài)鏈表的

31、存儲(chǔ)結(jié)構(gòu),#define MAXSIZE = 100; /靜態(tài)鏈表的最大長(zhǎng)度 typedef struct ElemType data; int cur; /游標(biāo),代替指針指示結(jié)點(diǎn)在數(shù)組中的位置 component,SLinkListMAXSIZE;,在靜態(tài)鏈表中查找第1個(gè)具有給定值e的結(jié)點(diǎn),int LocateElem_SL ( SLinkList, S,ElemType e ) i = S 0.cur; /i 指向表第一個(gè)結(jié)點(diǎn),相當(dāng)于p=p-next while ( i /LocateElem_SL,2.3.2 循環(huán)鏈表 (Circular List),循環(huán)鏈表是單鏈表的變形。 循環(huán)鏈表最

32、后一個(gè)結(jié)點(diǎn)的 link 指針不 為NULL，而是指向了表的前端。 為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入頭結(jié)點(diǎn)。 循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。,循環(huán)鏈表的示例 帶頭結(jié)點(diǎn)的循環(huán)鏈表,a1,a2,a3,an,first,an,first,a2,a1,first,(空表),(非空表),搜索成功,搜索不成功,循環(huán)鏈表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,current,current,current,current,current,current,current,current,循環(huán)鏈表的操作和

33、單鏈表基本一致，差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。,帶尾指針的循環(huán)鏈表,rear,31,48,15,57,22,如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。 在表尾插入，時(shí)間復(fù)雜性 O(1) 在表尾刪除，時(shí)間復(fù)雜性 O(n) 在表頭插入，相當(dāng)于在表尾插入 在表頭刪除，時(shí)間復(fù)雜性 O(1),頭指針指向表尾的好處是既能立即找到鏈表的尾結(jié)點(diǎn)，也容易找到鏈表中的第一個(gè)結(jié)點(diǎn)。 P35頁(yè)圖2.13 鏈表A，B直接合并： trilA-next=trilB-next; trilB-next=trilA-next;,靜態(tài)鏈表 單循環(huán)鏈

34、表,2.3.3 雙向鏈表 (Doubly Linked List),雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。 雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域, 結(jié)構(gòu)如下： 雙向鏈表通常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表形式。,前驅(qū)方向 后繼方向,prior data next,雙向鏈表C語(yǔ)言的定義,typedef struct node ElemType data; struct node *prior,*next; JD;,空雙向循環(huán)鏈表：,非空雙向循環(huán)鏈表：,結(jié)點(diǎn)指向 p-prior-next = p = p-next-prior,p-prior,p-next,p,prior,next,雙向循環(huán)鏈表的搜

35、索算法,搜索成功,搜索不成功,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,雙向鏈表插入算法描述,void ins_dulist(JD* p,int x) JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; ,算法實(shí)現(xiàn),算法評(píng)價(jià)：T(n)=O(n),雙向鏈表的插入操作算法: Status ListInsert_DuL ( DuLinkList / ListInsert_DuL,算法評(píng)價(jià)：T(n)=O(n

36、),雙向鏈表刪除算法描述,void del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); ,算法實(shí)現(xiàn),p-prior-next=p-next;,p-next-prior=p-prior;,雙向鏈表的刪除操作算法: Status ListDelete_DuL ( DuLinkList / ListDelete_DuL,算法評(píng)價(jià)：T(n)=O(n),2.3.4 順序表與鏈表的比較,（1）基于空間的比較 存儲(chǔ)分配的方式 順序表的存儲(chǔ)空間是一次分配的 鏈表的元素的存儲(chǔ)空間是動(dòng)態(tài)分配的 存儲(chǔ)密度 = 結(jié)點(diǎn)數(shù)據(jù)本身所占的

37、存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量 順序表的存儲(chǔ)密度 = 1 鏈表的存儲(chǔ)密度 1,（2）基于時(shí)間的比較 存取方式 順序表可以隨機(jī)存取，也可以順序存取 鏈表是順序存取的 插入/刪除時(shí)移動(dòng)元素個(gè)數(shù) 順序表平均需要移動(dòng)近一半元素 鏈表不需要移動(dòng)元素，只需要修改指針 若插入/刪除僅發(fā)生在表的兩端，宜采用帶尾指針的循環(huán)鏈表,如何選擇存儲(chǔ)結(jié)構(gòu)呢？,若線性表的操作主要是進(jìn)行查找，很少做插入和刪除時(shí)，宜采用順序表做存儲(chǔ)結(jié)構(gòu)。 對(duì)于頻繁進(jìn)行插入和刪除的線性表， 宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。 在求長(zhǎng)度，查找元素時(shí)不如順序表。,用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)， 存在的問(wèn)題：,1單鏈表的表長(zhǎng)是一個(gè)隱含的值；,2在單鏈表的

38、最后一個(gè)元素之后插入元素時(shí)， 需遍歷整個(gè)鏈表；,3在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的 “位置”概念加強(qiáng)。,四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型,typedef struct LNode / 結(jié)點(diǎn)類型 ElemType data; struct LNode *next; *Link, *Position;,typedef struct / 鏈表類型 Link head, tail; / 分別指向頭結(jié)點(diǎn)和 最后一個(gè)結(jié)點(diǎn)的指針 int len; / 指示鏈表長(zhǎng)度 LinkList;,課程回顧,上機(jī)出現(xiàn)問(wèn)題 調(diào)試 鏈表和順序表的區(qū)別 循環(huán)鏈表 雙向鏈表,2.4 一元多項(xiàng)式的表示及相加,1. 一元多項(xiàng)式

39、的表示,n 階多項(xiàng)式 Pn(x) 有 n+1 項(xiàng)。 系數(shù) P0, P1, P2, , Pn 指數(shù) 0, 1, 2, , n。按升冪排列,若： 對(duì)S(x)這樣的多項(xiàng)式采用全部存儲(chǔ)的方式則浪費(fèi)空間。怎么辦？ 一般n次多項(xiàng)式可以寫成：,因此可以用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表來(lái)表示：,ADT Polynomial 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：,抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每個(gè)元素包含一個(gè) 表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) ,R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指數(shù)值ai中的指數(shù)值 ,CreatPolyn ( struct node *next; JD, *Polylist ;,（2） 通過(guò)鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，以輸入系數(shù)0為結(jié)束標(biāo)志，并約定建立多項(xiàng)式鏈表時(shí)，總是按指數(shù)從大到小的順序排列。 算法描述：從鍵盤接受輸入的系數(shù)和指數(shù)； 用尾插法建立一元多項(xiàng)式的鏈表。,Polylist polycreate() Polynode *head, *rear, *s; int c