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

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

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

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

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

5、18王 春男 19 192003級(jí)電信級(jí)電信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 個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。 強(qiáng)調(diào)強(qiáng)調(diào) 本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和基本操作，更重要的是要學(xué)習(xí)如何在計(jì)算機(jī)上實(shí)現(xiàn)，即如何在計(jì)算機(jī)上存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)？如何在計(jì)算機(jī)上實(shí)現(xiàn)對(duì)數(shù)

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

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

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

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

10、每個(gè)元素占用存儲(chǔ)空間（地址長度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對(duì)上述公式的解釋如圖所示對(duì)上述公式的解釋如圖所示2 2、線性表順序存儲(chǔ)特點(diǎn)：、線性表順序存儲(chǔ)特點(diǎn)：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、線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖、線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖4 4、用、用C C語言描述語言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示數(shù)組的最大元素個(gè)數(shù)，list表示順序表的數(shù)組名，size表示順序表中當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，它必須滿足size MaxSize，SeqList是該結(jié)構(gòu)體的名字。*/設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個(gè)數(shù)組元素用相鄰的每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素按字節(jié)編址

12、，設(shè)存儲(chǔ)數(shù)組元素 的第一個(gè)的第一個(gè)字節(jié)的地址是字節(jié)的地址是，則，則 的第一個(gè)字節(jié)的的第一個(gè)字節(jié)的地址是多少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址計(jì)算通式為：已知地址計(jì)算通式為：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個(gè)英文字母組成的線性表個(gè)英文字母組成的線性表（a，b，c，z）

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

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

15、212830304262514915213030425162刪除28后內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號(hào)i+1n-1nanai+2實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟：n將第將第i+1 至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置；n表長減表長減1。注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?刪除線性表的第刪除線性表的第i i個(gè)位置上的元素個(gè)位置上的元素for ( j=i+1; jdata=; p-next= ; 方式方式3： p指向結(jié)點(diǎn)首地

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

17、）：sizeof(x)計(jì)算變量計(jì)算變量x x的長度（字節(jié)數(shù)）；的長度（字節(jié)數(shù)）；malloc(m) 開辟開辟m m字節(jié)長度的地址空間，并返回這段空間字節(jié)長度的地址空間，并返回這段空間的首地址；的首地址；free(p) 釋放指針釋放指針p p所指變量的存儲(chǔ)空間，即徹底刪除所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。一個(gè)變量。sizeof(x)計(jì)算計(jì)算x x的長度的長度malloc(m) 開開m m字節(jié)字節(jié)空間空間free(p) 刪除一個(gè)變量刪除一個(gè)變量問問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 對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：對(duì)于指向結(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： 補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示

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

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

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

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

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

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

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

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

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

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

30、復(fù)雜度為 O(n)。在在n n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)* *P P，需找到它，需找到它的的 ，其時(shí)間復(fù)雜度為，其時(shí)間復(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) 是一個(gè)首尾相接的鏈表。 特點(diǎn)特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表 a1 a2 . an 2. 循環(huán)鏈表

31、循環(huán)鏈表 和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。循環(huán)鏈表(circular linked list)n循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀n特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率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é)點(diǎn)的中，訪問結(jié)點(diǎn)的特點(diǎn)特點(diǎn): :訪問后繼結(jié)點(diǎn)，只需要向后走一步，而訪問前驅(qū)結(jié)點(diǎn)，就需訪問后繼結(jié)點(diǎn)，

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

33、雙向鏈表中如何實(shí)現(xiàn)插入和刪除運(yùn)算？單鏈表中查找只能從前往后，而不能從后往前查。單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表，一個(gè)指針域，用來存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表，稱為稱為雙向鏈表。雙向鏈表。其其結(jié)點(diǎn)的結(jié)構(gòu)結(jié)點(diǎn)的結(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語言描述的雙鏈表，如下： 雙鏈表的定義和特點(diǎn)雙鏈表的定義和特點(diǎn)n雙（向）鏈表雙（向）鏈表（Double Linked List）：有兩種不同方向鏈的鏈表稱為雙向循環(huán)鏈表。 n雙鏈表特點(diǎn)：雙鏈表的每一個(gè)結(jié)點(diǎn)除含數(shù)據(jù)域外，還有兩個(gè)指針域，一個(gè)指針指向其前驅(qū)結(jié)點(diǎn)，另一個(gè)指針指向其后繼結(jié)點(diǎn)?？梢越o雙鏈表加一表頭結(jié)點(diǎn)。雙鏈表可以循環(huán)，也可以不循環(huán) n雙鏈表和單鏈表相比，每一個(gè)結(jié)點(diǎn)增加了一

35、個(gè)指針域，雙向鏈表雖然多占用了空間，但它給數(shù)據(jù)運(yùn)算帶來了方便 雙向鏈表（double linked list）單鏈表具有單向性的缺點(diǎn)n結(jié)點(diǎn)定義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刪除算法描述算法評(píng)價(jià)：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;算法描述算法評(píng)價(jià)：T(n)=O(1)xSbaPn插入雙向鏈表的操作特點(diǎn)：雙向鏈表的操作特點(diǎn)：“查詢查詢” ” 和單鏈表相同。和單鏈表相同?！安迦氩迦搿?” 和和“刪除刪除”時(shí)需要同時(shí)修時(shí)需要同時(shí)修改兩個(gè)方向上的指針。改兩個(gè)方向上的指針。上述兩個(gè)算法的

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

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

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

40、否合適？的多項(xiàng)式，上述表示方法是否合適？n但是對(duì)于形如S(x) = 1 + 3x10000 2x20000 的多項(xiàng)式，上述表示也就不恰當(dāng)了。因?yàn)橹挥腥齻€(gè)非零項(xiàng)，這樣一個(gè)一個(gè)的寫下去，非常浪費(fèi)內(nèi)存空間。因?yàn)槲覀冎幌氡硎痉橇沩?xiàng)，零項(xiàng)表示出來也沒什么用 一般情況下的一元稀疏多項(xiàng)式一元稀疏多項(xiàng)式可寫成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指數(shù)為ei 的項(xiàng)的非零系數(shù)， 0 e1 e2 exp與q-expp-exp exp: p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) p后移,q不動(dòng)p-exp q-exp: q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) 將q插在p之前,q后移,p不動(dòng)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上即可運(yùn)算規(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算法描述兩個(gè)兩個(gè)多項(xiàng)式相加算法實(shí)現(xiàn)void polyadd(Polylist polya;Polylist polyb) /* p和q分別指向polya和polyb鏈表中的當(dāng)前計(jì)算結(jié)點(diǎn)*/ /* pre指向和多項(xiàng)式鏈表中的尾結(jié)點(diǎn)*/ while p!=NULL & q!=NULL） if （p-expexp） /*將p結(jié)點(diǎn)加入到和多項(xiàng)式中*/ else if ( p-exp

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

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

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

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

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

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