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

1、第二章第二章線性表線性表2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)2.2 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)2.4 一元多項式的表示及相加一元多項式的表示及相加通過本章的學(xué)習(xí)，讀者應(yīng)能掌握線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及線性表的基本運算以及實現(xiàn)算法。 2.1線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)第二章 線性表線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼是一種最簡單的是一種最簡單的線

2、性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。接后繼。 可表示為：（可表示為：（a a1 1 , a, a2 2 , , a, , an n） 簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 的。的。特點特點 只有一個首結(jié)點和尾結(jié)點；只有一個首結(jié)點和尾結(jié)點；特點特點 除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。直接后繼。線

3、性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊列、字符串、數(shù)組線性表、堆棧、隊列、字符串、數(shù)組等，其中最典型、最常用的是等，其中最典型、最常用的是-一對一一對一 (1:1)2.1 線性表的基本概念線性表的基本概念、線性表、線性表它是一種最簡單的線性結(jié)構(gòu)。是一種可以在任它是一種最簡單的線性結(jié)構(gòu)。是一種可以在任意位置進行插入和刪除數(shù)據(jù)元素操作的，由意位置進行插入和刪除數(shù)據(jù)元素操作的，由n（n0)個相同類型數(shù)據(jù)元素個相同類型數(shù)據(jù)元素a0, a1, , an-1組成的線性組成的線性結(jié)構(gòu)。結(jié)構(gòu)。（a0, a1, ai-1，ai, ai1 ，, an-1）n=0時稱為時稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點線性起點ai

4、的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總為元素總個數(shù)，即表個數(shù)，即表長。長。空表空表線性終點線性終點 （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級012003010622陳建武陳建武男男 192003級電信級電信0301班班012003010704趙玉鳳趙玉鳳女女 182003級電信級電信0302班班012003010813王王 澤澤男男 192003級電信級電信0303班班012003010906薛薛 荃荃男男 192003級電信級電信0304班班0120030110

5、18王 春男 19 192003級電信級電信0305班班： ：例例2 分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：分析：數(shù)據(jù)元素都是同類型數(shù)據(jù)元素都是同類型（記錄記錄），元素間關(guān)系是線性的。），元素間關(guān)系是線性的。分析：分析： 數(shù)據(jù)元素都是同類型數(shù)據(jù)元素都是同類型（字母字母），）， 元素間關(guān)系是線性的元素間關(guān)系是線性的。例例1 分析分析26 個英文字母組成的英文表是什么結(jié)構(gòu)。個英文字母組成的英文表是什么結(jié)構(gòu)。 強調(diào)強調(diào) 本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計算機上實現(xiàn)，即如何在計算機上存儲數(shù)據(jù)結(jié)構(gòu)？如何在計算機上實現(xiàn)對數(shù)

6、據(jù)結(jié)構(gòu)的各種操作，為此，我們將用計算機語言來描述數(shù)據(jù)的存儲結(jié)構(gòu)，用計算機語言來描述這些操作的算法，本課程我們用類C語言做為描述語言。 線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。數(shù)據(jù)結(jié)構(gòu)有兩種存儲方式: 順序存儲，鏈式存儲， 線性表也可以用這兩種方法實現(xiàn)。在計算機內(nèi)，線性表有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。下面我們分別討論這兩種存儲結(jié)構(gòu)以及對應(yīng)存儲結(jié)構(gòu)下實現(xiàn)各操作的算法。線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu): :它是使用一片它是使用一片地址地址連續(xù)的有限內(nèi)存單連續(xù)的有限內(nèi)存單元空間存儲數(shù)據(jù)元素的一

7、種計算機存儲數(shù)據(jù)方法。元空間存儲數(shù)據(jù)元素的一種計算機存儲數(shù)據(jù)方法。特點：特點：( (任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理位置任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理位置上也必然相鄰上也必然相鄰) )邏輯上相鄰的元素，物理上也相鄰。邏輯上相鄰的元素，物理上也相鄰。(2)(2)鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu): :它是把數(shù)據(jù)元素和指針定義成一個它是把數(shù)據(jù)元素和指針定義成一個存儲體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來存儲體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來的一種計算機存儲數(shù)據(jù)方法。的一種計算機存儲數(shù)據(jù)方法。特點：特點：任意兩個在任意兩個在邏輯上相鄰邏輯上相鄰的數(shù)據(jù)元素在的數(shù)據(jù)元素在物理上不物理上不一定相鄰

8、一定相鄰，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針鏈接實現(xiàn)的。鏈接實現(xiàn)的。2.2線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)2.2.1 順序表順序表2.2.2 順序表上實現(xiàn)的基本運算順序表上實現(xiàn)的基本運算2.2 線性表的順序存儲和實現(xiàn)如何在計算機中存儲線性表？如何在計算機中實現(xiàn)線性表的基本操作？2.2.1 順序表順序表一、一、 順序表的存儲結(jié)構(gòu)表示順序表的存儲結(jié)構(gòu)表示 1、順序表順序表：用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次存儲線的存儲單元依次存儲線性表的各個數(shù)據(jù)元素。即采用順序存儲結(jié)構(gòu)的線性性表的各個數(shù)據(jù)元素。即采用順序存儲結(jié)構(gòu)的線性表。它通常采用靜態(tài)數(shù)組實現(xiàn)數(shù)

9、據(jù)元素的存儲。表。它通常采用靜態(tài)數(shù)組實現(xiàn)數(shù)據(jù)元素的存儲?？梢岳每梢岳脭?shù)組數(shù)組VnVn來實現(xiàn)來實現(xiàn)注意：在注意：在C C語言中數(shù)組的下標(biāo)是從語言中數(shù)組的下標(biāo)是從0 0開始，即：開始，即： VnVn的有效范圍是從的有效范圍是從 V0V0Vn-1Vn-1(1) 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；(2) 若已知表中首元素在存儲器中的位置，則其他元若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。）。設(shè)首元素設(shè)首元素a0的存放地址為的存放地址為LOC(a0)（稱為稱為首地址首地址），），設(shè)

10、每個元素占用存儲空間（地址長度）為設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對上述公式的解釋如圖所示對上述公式的解釋如圖所示2 2、線性表順序存儲特點：、線性表順序存儲特點：a a0 0a a1 1a ai ia ai+1i+1a an-1n-1 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a0)b + + L Lb +i+iL Lb +(n-1)+(n-1)L Lb +(MaxSize-

11、1)+(MaxSize-1)L L3、線性表的順序存儲結(jié)構(gòu)示意圖、線性表的順序存儲結(jié)構(gòu)示意圖4 4、用、用C C語言描述語言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示數(shù)組的最大元素個數(shù)，list表示順序表的數(shù)組名，size表示順序表中當(dāng)前存儲的數(shù)據(jù)元素個數(shù)，它必須滿足size MaxSize，SeqList是該結(jié)構(gòu)體的名字。*/設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個數(shù)組元素用相鄰的每個數(shù)組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素按字節(jié)編址

12、，設(shè)存儲數(shù)組元素 的第一個的第一個字節(jié)的地址是字節(jié)的地址是，則，則 的第一個字節(jié)的的第一個字節(jié)的地址是多少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址計算通式為：已知地址計算通式為：LOC(ai) = LOC(a0) + L *i例例1 1 char V30;void build() /*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心語句：核心語句：例例2用數(shù)組用數(shù)組V來存放來存放26個英文字母組成的線性表個英文字母組成的線性表（a，b，c，z）

13、，寫出在順序結(jié)構(gòu)上），寫出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語言程序。語言程序。void main(void) /*主函數(shù)主函數(shù)，字母線性表的，字母線性表的生成和輸出生成和輸出*/ n=26; /* n n是表長，是數(shù)據(jù)元素的個數(shù)，而不是是表長，是數(shù)據(jù)元素的個數(shù)，而不是V V的的 實際下標(biāo)實際下標(biāo)*/build( );display( );void display( ) /*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/ int i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一個位置元素后移一個位置/ / 插入插入

14、x x / / 表長加表長加1 1 核核心心語語句：句：2)2)插入插入在線性表的第在線性表的第i i個位置前插入一個元素的示意圖如下：個位置前插入一個元素的示意圖如下：1213212428304277121321242830427712345678123456789插入插入在一個順序表中第i個元素之前插入一個元素x的函數(shù)： 順序表的刪除：順序表的刪除：n刪除操作分為相應(yīng)兩個階段，只是順序與前者相反：第一階段先執(zhí)行數(shù)據(jù)元素的刪除，第二階段再移動數(shù)據(jù)將空擋填上。刪除算法示意：將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個元素刪除。 序號123456781094915

15、212830304262514915213030425162刪除28后內(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實現(xiàn)步驟：實現(xiàn)步驟：n將第將第i+1 至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置；n表長減表長減1。注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?刪除線性表的第刪除線性表的第i i個位置上的元素個位置上的元素for ( j=i+1; jdata=; p-next= ; 方式方式3： p指向結(jié)點首地

16、址，然后指向結(jié)點首地址，然后 (*p).data=； (*p).nextb線性鏈表31LI43QIAN13SUN1WU37WANGNULLZHAO7ZHENG19ZHOU2517133719253143頭指針heada1a2a3an-1an ppdata等于a2 pnextdata等于a3 設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個元素的指針個元素的指針, ,則第則第i i個元素的個元素的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺椋羔樣驅(qū)憺?。練習(xí)：練習(xí)：p-dataai的值的值p-nextai+1的地址的地址附附1：介紹介紹C的三個有用的庫函數(shù)的三個有用的庫函數(shù)/算符（都在算符（都在 中）：中

17、）：sizeof(x)計算變量計算變量x x的長度（字節(jié)數(shù)）；的長度（字節(jié)數(shù)）；malloc(m) 開辟開辟m m字節(jié)長度的地址空間，并返回這段空間字節(jié)長度的地址空間，并返回這段空間的首地址；的首地址；free(p) 釋放指針釋放指針p p所指變量的存儲空間，即徹底刪除所指變量的存儲空間，即徹底刪除一個變量。一個變量。sizeof(x)計算計算x x的長度的長度malloc(m) 開開m m字節(jié)字節(jié)空間空間free(p) 刪除一個變量刪除一個變量問問1：自定義結(jié)構(gòu)類型變量自定義結(jié)構(gòu)類型變量node的長度的長度m是多少？是多少？問問2：結(jié)構(gòu)變量結(jié)構(gòu)變量node的首地址的首地址(指針指針p）是多少

18、？）是多少？問問3：怎樣刪除結(jié)構(gòu)變量怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長度為長度為m字節(jié)字節(jié)pmsizeof(node) /單位是字節(jié)單位是字節(jié)p(node*)malloc(m)free(p) /只能借助只能借助node的指針刪除！的指針刪除！P-data=a; p-P-data=a; p-next=qnext=q 對于指向結(jié)構(gòu)類型的指針變量，可說明為：對于指向結(jié)構(gòu)類型的指針變量，可說明為： *p, *q; /或用或用 struct *p , *q; /注：上面已經(jīng)定義了注：上面已經(jīng)定義了node為用戶自定義的為用戶自定義的liuyuliuyu類型。類型。 類型定義和變量說

19、明可以合寫為：類型定義和變量說明可以合寫為： liuyu /liuyu/liuyu是自定義結(jié)構(gòu)類型名稱是自定義結(jié)構(gòu)類型名稱 char data; /定義數(shù)據(jù)域的變量名及其類型定義數(shù)據(jù)域的變量名及其類型 liuyu *next; /定義指針域的變量名及其類型定義指針域的變量名及其類型node，*pointer; /node/node是是liuyuliuyu結(jié)構(gòu)類型的類型替代結(jié)構(gòu)類型的類型替代, , * *pointerpointer是指針型的是指針型的liuyuliuyu結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型* */ /附附2： 補充結(jié)構(gòu)數(shù)據(jù)類型的補充結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示

20、法2.3.1 單鏈表單鏈表n實現(xiàn)typedef struct node datatype data; struct node *link;JD;JD *h,*p;datalinkp結(jié)點（*p）(*p)表示p所指向的結(jié)點(*p).datap-data表示p指向結(jié)點的數(shù)據(jù)域(*p).linkp-link表示p指向結(jié)點的指針域生成一個JD型新結(jié)點：p=(JD *)malloc(sizeof(JD);系統(tǒng)回收p結(jié)點：free(p)總結(jié)線性鏈表n定義：結(jié)點中只含一個指針域的鏈表叫，也叫單鏈表n 鏈式存儲結(jié)構(gòu)的特點（1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時，

21、只能通過頭指針進入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，具有這種特點的存取方式被稱為順序存取方式。n在C語言中，實現(xiàn)線性表的鏈式存儲結(jié)構(gòu)的類型定義typedef strcut node /結(jié)點類型定義 EntryType item; /結(jié)點的數(shù)據(jù)域 struct node *next; /結(jié)點的指針域NODE;typedef struct /鏈表類型 NODE *head;LINK_LIST;請注意：請注意：TypedefTypedef不可能創(chuàng)造不可能創(chuàng)造任何新的數(shù)據(jù)類型，而僅僅是任何新的數(shù)據(jù)類型，而僅僅是在原有的數(shù)據(jù)類型中

22、命名一個在原有的數(shù)據(jù)類型中命名一個新名字，其目的是使你的程序新名字，其目的是使你的程序更易閱讀和移植。更易閱讀和移植。2.3.2單鏈表上的基本運算單鏈表上的基本運算2.3.2 單鏈表上的基本運算單鏈表上的基本運算n線性表的基本運算：建立單鏈表 單鏈表查找 單鏈表插入操作 1.單鏈表刪除 （1） 單鏈表的建立和輸出單鏈表的建立和輸出例：用例：用單鏈表單鏈表結(jié)構(gòu)來存放結(jié)構(gòu)來存放26個英文字母組成的線個英文字母組成的線性表（性表（a，b，c，z）,請寫出請寫出C語言程序。語言程序。實現(xiàn)思路：實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲空間并及時賦值，后繼

23、結(jié)點的地址要空間并及時賦值，后繼結(jié)點的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿卜卜”！typedef struct nodechar data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3個指針變量個指針變量int n ; / / 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類型定義好之后，每個變量結(jié)構(gòu)類型定義好之后，每個變量的長度就固定了，的長度就固定了，m m求一次即可求一次即可* */ /將全局變量及函數(shù)提前說明：將全局變量及函數(shù)提前說明：新

24、手特別容易忘記！新手特別容易忘記！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一個結(jié)點值為字符第一個結(jié)點值為字符ap-next=(node*)malloc(m); /為后繼結(jié)點為后繼結(jié)點“挖坑挖坑”！p=p-next； /讓指針變量讓指針變量P指向后一個結(jié)點指向后一個結(jié)點p-data=i+a-1; /最后一個元素要單獨處理最后一個元素要單獨處理p-next=NULL ; / /單鏈表尾結(jié)點的指針域要置空！單鏈表尾結(jié)點的指針域要置空！void build( ) /

25、字母鏈表的生成字母鏈表的生成。要一個個慢慢鏈入要一個個慢慢鏈入p=head;while (p) /當(dāng)指針不空時循環(huán)，僅限于當(dāng)指針不空時循環(huán)，僅限于無頭結(jié)點無頭結(jié)點的情況的情況 printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” sum+;sum+;sum=0;sum=0;void display() /*字母鏈表的輸出字母鏈表的輸出*/n單鏈表的基本運算查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULL 算法描述While循環(huán)中語句頻度為若找到結(jié)點X，為結(jié)點X在表中的序號否則，為n nOnTpabxs 算法評價插入：

26、在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnT 算法描述 算法評價在鏈表中插入一個元素在鏈表中插入一個元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX X 結(jié)點的生成方式：結(jié)點的生成方式：s=(node*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 單鏈表的插入單鏈表的插入 算法描述pabc 1OnT 算法評價刪除：單鏈表中刪除b，設(shè)p指向ap-link=p-link-link;在鏈表中刪除某元素在鏈表中刪除某元素b b的示意

27、圖如下：的示意圖如下：c a bp刪除動作的核心語句刪除動作的核心語句（要借助輔助指針變量（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存b b的指針，靠它才能找到的指針，靠它才能找到c c；p-next=q-next; /將將a a、c c兩結(jié)點相連，淘汰兩結(jié)點相連，淘汰b b結(jié)點；結(jié)點；free(q) ； /徹底釋放徹底釋放b b結(jié)點空間結(jié)點空間p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除 nOnT動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為

28、頭指針 算法描述 算法評價h頭結(jié)點an 0h頭結(jié)點an-10an a2.h頭結(jié)點an-10an ha1a2頭結(jié)點an .0Ch2_3.ch頭結(jié)點0n單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢 在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。鏈表的運算效率分析鏈表的運算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，因線性鏈表只能順序存取，即在查找時要從頭

29、指針找起，查找的時間復(fù)雜度為查找的時間復(fù)雜度為 O(n)。時間效率分析時間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進行但是，如果要在單鏈表中進行前前插或刪除操作，因為要插或刪除操作，因為要從頭查找前驅(qū)從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是結(jié)點，所耗時間復(fù)雜度將是 O(n)?？臻g效率分析空間效率分析鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總共增鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總共增加了加了n 個整型變量，空間復(fù)雜度為個整型變量，空間

30、復(fù)雜度為 O(n)。在在n n個結(jié)點的單鏈表中要刪除已知結(jié)點個結(jié)點的單鏈表中要刪除已知結(jié)點* *P P，需找到它，需找到它的的 ，其時間復(fù)雜度為，其時間復(fù)雜度為 。 O(n)O(n)練習(xí)：練習(xí)：2.3.3 循環(huán)鏈表循環(huán)鏈表2.3.3 循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表(Circular Linked List) 是一個首尾相接的鏈表。 特點特點：將單鏈表最后一個結(jié)點的指針域由NULL改為指向頭結(jié)點或線性表中的第一個結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。 最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表 a1 a2 . an 2. 循環(huán)鏈表

31、循環(huán)鏈表 和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。循環(huán)鏈表(circular linked list)n循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀n特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率n操作與單鏈表基本一致,循環(huán)條件不同，只是判斷鏈表結(jié)束的條件有所不同。單鏈表p或p-link=NULL循環(huán)鏈表p或p-link=Hhh空表2.3.4 雙鏈表雙鏈表2.3.3 雙向循環(huán)鏈表n 在在循環(huán)鏈表循環(huán)鏈表中，訪問結(jié)點的中，訪問結(jié)點的特點特點: :訪問后繼結(jié)點，只需要向后走一步，而訪問前驅(qū)結(jié)點，就需訪問后繼結(jié)點，

32、只需要向后走一步，而訪問前驅(qū)結(jié)點，就需要轉(zhuǎn)一圈。要轉(zhuǎn)一圈。n結(jié)論結(jié)論：循環(huán)鏈表并不適用于經(jīng)常訪問前驅(qū)結(jié)點的情況。：循環(huán)鏈表并不適用于經(jīng)常訪問前驅(qū)結(jié)點的情況。n解決方法解決方法：在需要頻繁地同時訪問前驅(qū)和后繼結(jié)點的時：在需要頻繁地同時訪問前驅(qū)和后繼結(jié)點的時候，使用雙向鏈表。候，使用雙向鏈表。n所謂所謂雙向鏈表雙向鏈表：雙向鏈表就是每個結(jié)點有兩個指針域。一個指向后繼結(jié)點，雙向鏈表就是每個結(jié)點有兩個指針域。一個指向后繼結(jié)點，另一個指向前驅(qū)結(jié)點。另一個指向前驅(qū)結(jié)點。雙鏈表的結(jié)構(gòu)定義n雙鏈表的結(jié)點結(jié)構(gòu) 后繼指針域prior data next前驅(qū)指針域數(shù)據(jù)域例：在雙向鏈表中如何實現(xiàn)插入和刪除運算？例：在

33、雙向鏈表中如何實現(xiàn)插入和刪除運算？單鏈表中查找只能從前往后，而不能從后往前查。單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點上增加為了查找方便，提高查找速度，可以在結(jié)點上增加一個指針域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表，一個指針域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表，稱為稱為雙向鏈表。雙向鏈表。其其結(jié)點的結(jié)構(gòu)結(jié)點的結(jié)構(gòu)為：為：prior data nexttypedef struct DuLNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct DuLNode *prior; /前驅(qū)指針域前驅(qū)指針域 struct DuLNode *next; /

34、后繼指針域后繼指針域 DuLNode , *DuLinkList ; 雙向鏈表類型的定義如下：雙向鏈表類型的定義如下：雙向循環(huán)鏈表雙向循環(huán)鏈表空表空表非空表非空表 a1 a2 . an雙鏈表的定義：雙鏈表的定義：n采用C語言描述的雙鏈表，如下： 雙鏈表的定義和特點雙鏈表的定義和特點n雙（向）鏈表雙（向）鏈表（Double Linked List）：有兩種不同方向鏈的鏈表稱為雙向循環(huán)鏈表。 n雙鏈表特點：雙鏈表的每一個結(jié)點除含數(shù)據(jù)域外，還有兩個指針域，一個指針指向其前驅(qū)結(jié)點，另一個指針指向其后繼結(jié)點?？梢越o雙鏈表加一表頭結(jié)點。雙鏈表可以循環(huán)，也可以不循環(huán) n雙鏈表和單鏈表相比，每一個結(jié)點增加了一

35、個指針域，雙向鏈表雖然多占用了空間，但它給數(shù)據(jù)運算帶來了方便 雙向鏈表（double linked list）單鏈表具有單向性的缺點n結(jié)點定義typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表： LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);n刪除算法描述算法評價：T(

36、n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;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;算法描述算法評價：T(n)=O(1)xSbaPn插入雙向鏈表的操作特點：雙向鏈表的操作特點：“查詢查詢” ” 和單鏈表相同。和單鏈表相同?！安迦氩迦搿?” 和和“刪除刪除”時需要同時修時需要同時修改兩個方向上的指針。改兩個方向上的指針。上述兩個算法的

37、時間復(fù)雜度均為O(1)。雙向鏈表雙向鏈表 （加一個指向前驅(qū)的指針）（加一個指向前驅(qū)的指針）n每個結(jié)點的后繼的前驅(qū)就是他本身，前驅(qū)的后繼也是他本身。n優(yōu)點：找當(dāng)前指針的前驅(qū)找當(dāng)前指針的前驅(qū)這個基本操作就是常量級的，而不是線性級的了。所以如果在線性表的使用中，不但找后繼還要找前驅(qū)的情況下就可用雙向鏈表來實現(xiàn)。n插入刪除時，不但要修改后繼修改后繼，還要修改前驅(qū)修改前驅(qū)。 鏈式存儲結(jié)構(gòu)的優(yōu)點和缺點n鏈式存儲結(jié)構(gòu)克服了順序存儲結(jié)構(gòu)的缺點：它的結(jié)點空間可以動態(tài)申請和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，不需要移動數(shù)據(jù)元素。n但是鏈式存儲結(jié)構(gòu)也有不足之處：（1）每個結(jié)點中的指針域需額外占用存儲空間

38、。當(dāng)每個結(jié)點的數(shù)據(jù)域所占字節(jié)不多時，指針域所占存儲空間的比重就顯得很大。（2）鏈式存儲結(jié)構(gòu)是一種非隨機存儲結(jié)構(gòu)。對任一結(jié)點的操作都要從頭指針依指針鏈查找到該結(jié)點，這增加了算法的復(fù)雜度。2.3.5順序表和鏈表的比較順序表和鏈表的比較2.3.5 順序表和鏈表的比較順序表和鏈表的比較 n1基于空間的考慮 n2基于時間的考慮 順序表和鏈表的比較n基于空間的考慮基于空間的考慮 當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。 當(dāng)線性表的長度變化不大，易于事先確定其大小，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。 存儲密度存儲密度（Storage Density）：是指結(jié)點

39、數(shù)據(jù)本身所占的存儲量和整個結(jié)點結(jié)構(gòu)所占的存儲量之比。 基于時間的考慮基于時間的考慮 若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜。 對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。 nnnxpxpxppxp.)(2210在計算機中，可以用一個線性表來表示在計算機中，可以用一個線性表來表示: P = (p0, p1, ，pn)每一項的指數(shù)I隱含在他系數(shù)pi的序號中一元多項式一元多項式但是對于形如但是對于形如 S(x) = 1 + 3x10000 2x20000的多項式，上述表示方法是

40、否合適？的多項式，上述表示方法是否合適？n但是對于形如S(x) = 1 + 3x10000 2x20000 的多項式，上述表示也就不恰當(dāng)了。因為只有三個非零項，這樣一個一個的寫下去，非常浪費內(nèi)存空間。因為我們只想表示非零項，零項表示出來也沒什么用 一般情況下的一元稀疏多項式一元稀疏多項式可寫成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指數(shù)為ei 的項的非零系數(shù)， 0 e1 e2 exp與q-expp-exp exp: p結(jié)點是和多項式中的一項 p后移,q不動p-exp q-exp: q結(jié)點是和多項式中的一項 將q插在p之前,q后移,p不動p-exp =

41、q-exp: 系數(shù)相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數(shù)域, 釋放q，p,q后移直到p或q為NULL 若q=NULL，結(jié)束 若p=NULL，將B中剩余部分連到A上即可運算規(guī)則q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8

42、 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Ch2_7.c算法描述兩個兩個多項式相加算法實現(xiàn)void polyadd(Polylist polya;Polylist polyb) /* p和q分別指向polya和polyb鏈表中的當(dāng)前計算結(jié)點*/ /* pre指向和多項式鏈表中的尾結(jié)點*/ while p!=NULL & q!=NULL） if （p-expexp） /*將p結(jié)點加入到和多項式中*/ else if ( p-exp

43、= =q-exp） /*若指數(shù)相等，則相應(yīng)的系數(shù)相加。若系數(shù)為0則刪除p，q節(jié)點*/ else /*將q結(jié)點加入到和多項式中*/ ./*將多項式polya或polyb中剩余的結(jié)點加入到和多項式中*/本章小結(jié)本章小結(jié)線性結(jié)構(gòu)線性結(jié)構(gòu)( (包括表、棧、隊、數(shù)組）的定義和特點：包括表、棧、隊、數(shù)組）的定義和特點：僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和一個僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和一個直接后繼。直接后繼。2. 2. 線性表線性表邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：“一對一一對一” ” 或或 “ “1:1”1:1”存儲結(jié)構(gòu)存儲結(jié)構(gòu)：順序、鏈式順序、鏈式運運 算：算：修改、插入、刪除修改、插入、刪除3.

44、3.順序存儲順序存儲特征特征：邏輯上相鄰，物理上也相鄰；邏輯上相鄰，物理上也相鄰；優(yōu)點優(yōu)點：隨機查找修改快隨機查找修改快 O(1)O(1)缺點缺點：插入、刪除慢插入、刪除慢 O(n)O(n)改進方案：改進方案：循環(huán)鏈表的特點：循環(huán)鏈表的特點：雙向鏈表的特點：雙向鏈表的特點：可方便可方便靜態(tài)鏈表的特點：靜態(tài)鏈表的特點：不用指針也能實現(xiàn)鏈式存儲和運算不用指針也能實現(xiàn)鏈式存儲和運算4.4.鏈式存儲鏈式存儲特征特征：邏輯上相鄰，物理上未必相鄰；邏輯上相鄰，物理上未必相鄰；優(yōu)點優(yōu)點：插入、刪除快插入、刪除快 O(1)O(1)缺點：缺點：隨機查找修改慢隨機查找修改慢 O(n)O(n)5.5.幾種特殊鏈表的

45、特點：幾種特殊鏈表的特點：討論討論1 1： 順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲時，順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。缺點是插入或刪除元素時不方便。鏈式存儲時，鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈式存儲的優(yōu)

46、點是插入或刪除元素時很方便，關(guān)系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。使用靈活。缺點是存儲密度小，存儲空間利用率低。順序表順序表適宜于做適宜于做查找查找這樣的靜態(tài)操作；這樣的靜態(tài)操作；鏈表鏈表宜于做宜于做插插入、刪除入、刪除這樣的動態(tài)操作。若這樣的動態(tài)操作。若線性表的長度變化不大線性表的長度變化不大，且，且其主要操作是查找，則采用順序表；若其主要操作是查找，則采用順序表；若線性表的長度變化線性表的長度變化較大較大，且其主要操作是插入、刪除操作，則采用鏈表。，且其主要操作是插入、刪除操作，則采用鏈表。本章小結(jié)本章小結(jié) 本章主要介紹了如下一些

47、基本概念： 線性表線性表：一個線性表是n0個數(shù)據(jù)元素a0，a1，a2，an-1的 有限序列。線性表的線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)線性表的線性表的鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)：線性表的鏈式存儲結(jié)構(gòu)就是用一組任意的存儲單元結(jié)點（可以是不連續(xù)的）存儲線性表的數(shù)據(jù)元素。表中每一個數(shù)據(jù)元素，都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅(qū)或直接后繼結(jié)點的地址（指針）的指針域組成。 循環(huán)鏈表循環(huán)鏈表：循環(huán)鏈表(Circular Linked List)是將單鏈表的表中最后一個結(jié)點指針指向鏈表的表頭結(jié)點，整個鏈表形成一個環(huán)，從

48、表中任一結(jié)點出發(fā)都可找到表中其他的結(jié)點。 雙向鏈表雙向鏈表：雙向鏈表中，在每一個結(jié)點除了數(shù)據(jù)域外，還包含兩個指針域，一個指針（next）指向該結(jié)點的后繼結(jié)點，另一個指針（prior）指向它的前驅(qū)結(jié)點。 除上述基本概念以外，學(xué)生還應(yīng)該了解： 線性表的基本操作（建立、插入、刪除、查找） 線性表的順序存儲結(jié)構(gòu)的表示、 線性表的鏈式存儲結(jié)構(gòu)的表示、 一元多項式Pn(x)， 掌握順序存儲結(jié)構(gòu)（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）。 第二章 線性表小結(jié) 本章學(xué)習(xí)了線性表的本章學(xué)習(xí)了線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序表順序表，鏈式存鏈式存儲結(jié)構(gòu)儲結(jié)構(gòu)線性鏈表線性鏈表、循環(huán)鏈表循環(huán)鏈表、 雙向鏈表雙向鏈表，以及在這兩種，以及在這兩種存儲結(jié)構(gòu)下如何實現(xiàn)線性表的存儲結(jié)構(gòu)下如何實現(xiàn)線性表的基本操作基本操作。這里再一次需要強。這里再一次需要強調(diào)：本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏調(diào)：本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計算機上實現(xiàn)，輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計算機上實現(xiàn)，即如何在計算機上存儲線性表，