線性表完整版課件

1、1.2 線性表 線性結(jié)構(gòu)是最常用、最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。1.2 線性表1. 線性表（Linear List)的定義 具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素組成的有限 序列。 數(shù)據(jù)元素之間具有的邏輯關(guān)系為線性關(guān)系的數(shù)據(jù)元素集合稱為線性表。 n為線性表的長(zhǎng)度, 長(zhǎng)度為0的線性表稱為空表。1.2 線性表2. 線性表的表示L=( a1，a2，a3，ai-1，ai ，ai+1，,.,an ) 表頭表尾這里的數(shù)據(jù)元素ai(1in)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。3. 線性結(jié)構(gòu)特點(diǎn):(1)有且只有一個(gè)根結(jié)點(diǎn)a

2、1 ，無(wú)前驅(qū) 。(2)有且只有一個(gè)終端結(jié)點(diǎn)an ，無(wú)后繼 。(3)其他結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。1.2 線性表幾個(gè)線性表的例子： 數(shù)列： ( 25， 12， 78， 34， 100， 88)1a1 a2 a3 a4 a5 a6一個(gè)數(shù)據(jù)元素為一個(gè)整數(shù)2字母表： ( A， B， C， , Z)a1 a2 a3 a26一個(gè)數(shù)據(jù)元素為一個(gè)字母1.2 線性表簡(jiǎn)單線性表幾個(gè)線性表的例子：數(shù)據(jù)文件：399001張 華 女17 99002李 軍 男18 99003王 明 男17 99050劉 東 女19 學(xué)號(hào) 姓 名性別年齡其 他 一個(gè)數(shù)據(jù)元素為一個(gè)記錄a1a2a3 a50.1.2 線性表復(fù)雜線

3、性表 用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)數(shù)據(jù)元素的存儲(chǔ)位置直接反映。 ( a1，a2，a3， . . , an ) 所謂一個(gè)元素的 是指該元素占用的若干(連續(xù)的)存儲(chǔ)單元的第一個(gè)單元的地址。地址LOC(ai)a1a2a3an d1 d2 d3 dn 1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 若假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元，并且已知第一個(gè)元素的存儲(chǔ)位置LOC(a1)，則有 LOC(ai) = LOC(a1)+(i1)ka1a2a3an 結(jié)論：LOC(a1)=100 k=4 求LOC(a5)=?a1a2a3an a4a5100 104 108 112 116

4、 LOC(a5) = 100+(5 1)4=116事先分配給線性表的空間當(dāng)前已經(jīng)占用的空間尚未使用的空間#define M 100datatype AM;int n;C 語(yǔ)言1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址順序表的基本運(yùn)算 插入和刪除1)順序表的插入運(yùn)算: 在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ABCDEFGH空閑空間插隊(duì)前大哥，求求你？ABCDEFGH空閑空間插隊(duì)后大哥，謝謝你！1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址順序表的基本運(yùn)算 插入和刪除1)順序表的插入運(yùn)算: 在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ai-1.a2a1anai+1ai

5、 x ai-1. a2 a1 ai an an ai+1 ai ai x插入程序舉例(在8個(gè)數(shù)中任意位置插入一個(gè)數(shù))：#define N 8main() int aN+1=12,34,45,6,78,9,10,91, i,j,x; printf(“input the location to be inserted:”); scanf(“%d,%d”,&i,&x); ai-1=x; for(j=0;j=N;j+) printf(“%d,”,aj);for(j=i-1;j=i-1;j-) aj+1=aj;插入運(yùn)算時(shí)間性能分析：在第i個(gè)位置上作插入x,則需將第i個(gè)至第n個(gè)元素移動(dòng)，即共需移動(dòng)(n-i

6、+1)個(gè)元素。插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)移動(dòng)上。在長(zhǎng)度為n的線性表中插入一個(gè)元素，則平均移動(dòng)元素次數(shù)(期望值)：pi：在第i個(gè)位置上作插入的概率。等差數(shù)列求和公式: (首項(xiàng)+末項(xiàng))項(xiàng)數(shù))/2(n-i+1)MOVEi線性表(a0,a1,a2)平局移動(dòng)元素個(gè)數(shù):()*(3+2+1+0)=1.5在一線性表(a0,a1,a2)中插入任意一數(shù)i，求平局移動(dòng)元素次數(shù): i 移動(dòng)次數(shù)(n-i+1) 1(插入到第個(gè)數(shù)a0前) 3 2 (插入到第2個(gè)數(shù)a1前) 23 (插入到第3個(gè)數(shù)a2前) 1 (插入到第3個(gè)數(shù)a2后) 0 1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址順序表的基本運(yùn)算插入和刪除2)順序表刪除運(yùn)

7、算：定義：指將表中第i個(gè)元素從線性表中去掉。原表長(zhǎng)為n：( a1，a2，ai-1，ai ，ai+1， an ) 新表長(zhǎng)為n-1：( a1，a2，ai-1，ai+1， ， an ) 步驟：(1)將ai+1 an， 順序向前移動(dòng)(2)表長(zhǎng)減一ABCDEFGH空閑空間逃離后ABCDEFGH空閑空間逃離前騙子，還我錢(刪除第五個(gè)元素21) 6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 867順序表的基本運(yùn)算2)順序表刪除運(yùn)算：時(shí)間性能分析：時(shí)間消耗與插入運(yùn)算相同，平均移動(dòng)元素次數(shù)：qi:在第i個(gè)位置上作插入的概率。設(shè)qi=1/n

8、共需移動(dòng)(n-i)個(gè)元素。 i 移動(dòng)次數(shù)(n-i) 1(刪除第1個(gè)數(shù)a0) 22 (刪除第2個(gè)數(shù)a1) 13 (刪除第3個(gè)數(shù)a2) 0線性表(a0,a1,a2)平局移動(dòng)元素個(gè)數(shù):(1/3)*(2+1+0)=1在一線性表(a0,a1,a2)中刪除任意一數(shù)i，求平局移動(dòng)元素次數(shù):作業(yè)：有一數(shù)組，存儲(chǔ)十個(gè)數(shù)，編程序刪除其中任意一個(gè)數(shù)。重要結(jié)論在順序存儲(chǔ)表示的線性表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約需要移動(dòng)一半的元素 因此，順序存儲(chǔ)表示僅適用于不經(jīng)常進(jìn)行插入和刪除操作并且表中元素相對(duì)穩(wěn)定的表順序表優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：邏輯上相鄰元素存儲(chǔ)位置也相鄰,無(wú)需增加額外存儲(chǔ)空間可方便隨機(jī)存取表中任一元素。缺點(diǎn)：插入和刪

9、除運(yùn)算不方便,必須移動(dòng)大量結(jié)點(diǎn),效率較低不適合元素經(jīng)常變動(dòng)的大的線性表。對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用；容易造成存儲(chǔ)空間的“碎片”思路(鏈?zhǔn)酱鎯?chǔ)）：元素可以散落在任何位置，不必相鄰讓每個(gè)元素知道它的下一個(gè)元素在哪里我們只需要知道第一個(gè)元素的位置插入刪除不再需要移動(dòng)元素而是需要修改元素間的關(guān)系123456234561順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法 假定上圖為當(dāng)前內(nèi)存的使用情況，陰影部分為已用內(nèi)存，現(xiàn)有一線性表L=(A,B,C,D,E,F,G,H),假若采用順序存儲(chǔ)的話，則在當(dāng)前內(nèi)存中不能分配一塊長(zhǎng)度為8的連續(xù)的存儲(chǔ)空間。但實(shí)際上，系統(tǒng)的可用內(nèi)

10、存遠(yuǎn)大于該線性表所要求的內(nèi)存空間，應(yīng)采用其它的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)。當(dāng)前內(nèi)存的狀態(tài)建立一個(gè)含有8個(gè)元素的線性表 L=(a1,a2,a3, a4, a5, a6, a7, a8) 可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每一個(gè)數(shù)據(jù)元素占用兩個(gè)存儲(chǔ)單元，其中一個(gè)用來(lái)存放數(shù)據(jù)元素的值，另外一個(gè)存放下一個(gè)數(shù)據(jù)元素存儲(chǔ)單元的地址，這種結(jié)構(gòu)稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在這種結(jié)構(gòu)中，數(shù)據(jù)元素存放是不連續(xù)的。 a1Heada2a3 a4a5a6a7a8地址數(shù)據(jù)指針6462149594327901137991a24212743495990a1a3a7 a6a4a5a86499027594321Head鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn):1.2.3 線性表的鏈?zhǔn)?/p>

11、存儲(chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元（可以連續(xù)，也可以不連續(xù)）存儲(chǔ)線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲(chǔ)位置的信息。假設(shè)有一個(gè)線性表（a,b,c,d），可用下圖所示的形式存儲(chǔ)：線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致；在對(duì)線性表操作時(shí)，只能通過(guò)頭指針進(jìn)入鏈表，并通過(guò)每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會(huì)造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，具有這種特點(diǎn)的存取方式被稱為順序存取方式。 1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.線性鏈表:定義：線性表的鏈?zhǔn)酱?/p>

12、儲(chǔ)結(jié)構(gòu)稱為線性鏈表數(shù)據(jù)域: 一部分存放數(shù)據(jù)元素值 指針域: 存放指針,用于指向該結(jié)點(diǎn)的 前一個(gè)結(jié)點(diǎn)或后一個(gè)結(jié)點(diǎn) 線性鏈表中結(jié)點(diǎn)組成：1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)合C語(yǔ)言：鏈表就是一組組的數(shù)據(jù)用鏈將它連起來(lái)，如下圖所示。 數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)5數(shù)據(jù)3數(shù)據(jù)4數(shù)據(jù)鏈問(wèn)題是用什么來(lái)存放數(shù)據(jù)，用什么來(lái)作為鏈。解決辦法?數(shù)據(jù)1指針數(shù)據(jù)2指針數(shù)據(jù)3指針數(shù)據(jù)域指針域從上圖知，可以定義一個(gè)結(jié)構(gòu)，其中一部分存放數(shù)據(jù)，另一部分存放指向下一數(shù)據(jù)的指針。這就構(gòu)成了單鏈表。節(jié)點(diǎn)每組數(shù)據(jù)和指針?lè)Q為鏈表的一個(gè)節(jié)點(diǎn)。351.分配內(nèi)存函數(shù)： malloc() 原型在stdlib.h中 1)調(diào)用方式 void *malloc(u

13、nsigned size) 2)功能 在內(nèi)存中分配size個(gè)字節(jié)的存儲(chǔ)空間，并返回指向分配存儲(chǔ)區(qū)起始地址的指針；如果不能獲得需要的存儲(chǔ)空間，將返回空指針。 注：在把返回值賦給具有一定數(shù)據(jù)類型的指針變量時(shí)，應(yīng)對(duì)返回值作強(qiáng)制類型轉(zhuǎn)換。結(jié)合C語(yǔ)言：跟鏈表相關(guān)的函數(shù)36例：為1000個(gè)字符動(dòng)態(tài)分配內(nèi)存 char *p; p=(char *)malloc(1000); 結(jié)合C語(yǔ)言：37 struct data int no; char name10; int score; ; struct data *p; p=(struct data *)malloc(sizeof(struct data); if

14、(p=NULL) puts(“out of memoryn”); exit(1); 結(jié)合C語(yǔ)言：exit()函數(shù):被定義在stdlib.h中 0: 程序正常終止 非0：程序非正常終止382. calloc()函數(shù) 原型在stdlib.h中 1)調(diào)用方式 void *calloc(unsigned n, unsigned size) 2)功能 分配n個(gè)具有size個(gè)字節(jié)的存儲(chǔ)空間，并返回一個(gè)指向被分配內(nèi)存起始地址的指針；如果沒(méi)有足夠的內(nèi)存滿足要求，則返回一個(gè)空指針結(jié)合C語(yǔ)言：393. free()函數(shù) 原型在stdlib.h中 1)調(diào)用方式 void free(void *ptr) 2)功能 釋

15、放由ptr指向的內(nèi)存空間，并將它返回給堆 注：free()只能由前面動(dòng)態(tài)內(nèi)存分配函數(shù)中所分配地址的那個(gè)指針來(lái)調(diào)用結(jié)合C語(yǔ)言：頭結(jié)點(diǎn)是在鏈表的起始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn).帶頭結(jié)點(diǎn)的單鏈表123head123head頭結(jié)點(diǎn)單鏈表帶頭結(jié)點(diǎn)的單鏈表head空表head 空表head-next=NULL頭結(jié)點(diǎn)有兩個(gè)優(yōu)點(diǎn)：由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，故在鏈表的第一個(gè)位置上的操作與表中其他位置上操作一致，無(wú)須進(jìn)行特殊處理。無(wú)論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針，故此空表和非空表的處理也統(tǒng)一了。起始結(jié)點(diǎn) struct Node int data; struct Node *next

16、; ;struct Node * head;head-next(head-next) -data起始結(jié)點(diǎn)的地址6鏈表的訪問(wèn)struct Node * p ; p=head-next;head63120pp=p-next;pp=p-next;pp-next=NULL 表明p到達(dá)表尾結(jié)點(diǎn)p=p-next;p=0 空指針 對(duì)于線性鏈表，可以從頭指針(head)開(kāi)始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。 typedef struct Node int data; struct Node *next; LinkList;LinkList * head;新的類型名代換舊的類型名，即：LinkList等價(jià)

17、與struct node struct Node int data; struct Node *next; ;struct Node * head;將當(dāng)前結(jié)點(diǎn)的元素值賦給xx=p-data;LinkList * p ; int x ; x6pLinkList * p ; int x ; p將x賦給當(dāng)前結(jié)點(diǎn)，修改當(dāng)前結(jié)點(diǎn)的元素值 x=10;p-data=x;10 尾插法建立單鏈表（n個(gè)節(jié)點(diǎn)）特點(diǎn)：頭指針固定不變，新產(chǎn)生的結(jié)點(diǎn)總是鏈接到鏈表的尾部。操作步驟：（1）進(jìn)行定義：head為頭指針，tail為尾指針，p為結(jié)點(diǎn)。 （2）建立頭節(jié)點(diǎn) head=(struct node *) malloc( s

18、izeof(struct node); head-next=NULL; tail=head; （3）生成新結(jié)點(diǎn)（p），輸入數(shù)據(jù) p=(struct node *) malloc( sizeof(struct node); scanf(“%d”,&p-data); p-next=NULL;（4）鏈接到表尾 tail-next=p; tail=p;（5）重復(fù)（3）（4），繼續(xù)建立新結(jié)點(diǎn)，直到n個(gè)節(jié)點(diǎn)為止。當(dāng)表空時(shí)，頭指針和尾指針同時(shí)指向頭節(jié)點(diǎn)47struct node char name10; int wage; struct node *next; ;48定義頭指針、尾指針、新節(jié)點(diǎn)指針初始化（帶

19、頭節(jié)點(diǎn)）開(kāi)辟新節(jié)點(diǎn)節(jié)點(diǎn)個(gè)數(shù)next=NULL; tail=head; for( i=0; idata); p-next=NULL; tail-next=p; tail=p; return head; / 建立頭結(jié)點(diǎn)/ 用tail標(biāo)記鏈表尾部/生成新結(jié)點(diǎn)/輸入結(jié)點(diǎn)的數(shù)據(jù)域/鏈接到表尾/ 更新尾指針/ 返回鏈表的頭指針3 .單鏈表: 定義：由n個(gè)結(jié)點(diǎn)鏈接，且每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表。 例：線性單鏈表( A, B, C, D, E, F )ABCDEhead F1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)3 .單鏈表: (1)單鏈表插入：增加新結(jié)點(diǎn),修改鏈接指針后插結(jié)點(diǎn)在指針p所指結(jié)點(diǎn)之

20、后插入一個(gè)指針s所指的結(jié)點(diǎn)修改p和s所指結(jié)點(diǎn)的指針域的指針即可 1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp B C Xs A修改p指針域, 使其指向新結(jié)點(diǎn)s: pnexts考慮上述兩步驟若顛倒會(huì)怎樣？插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp B C Xs A修改p指針域, 使其指向新結(jié)點(diǎn)s: pnexts后面的結(jié)點(diǎn)都將從鏈表中脫離它們占用著內(nèi)存空間，程序卻找不到它們了3 .單鏈表: (2)單鏈表刪除：不需要移動(dòng)元素,僅修改指針鏈接刪除結(jié)點(diǎn)刪除p指向的結(jié)點(diǎn)只修改p(被刪除結(jié)點(diǎn))的前驅(qū)結(jié)點(diǎn)的指針域即可 1

21、.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)刪除步驟修改q結(jié)點(diǎn)指針域 qnextpnextCpBA刪除前刪除后qpCBAfree(p);先找到p的前驅(qū)結(jié)點(diǎn)qqnextqnextnext1)存儲(chǔ)空間動(dòng)態(tài)分配，可以按需要使用；2)插入/刪除結(jié)點(diǎn)操作時(shí)，只需要修改指針，不必移動(dòng)數(shù)據(jù)元素優(yōu)點(diǎn)缺點(diǎn)1)每個(gè)結(jié)點(diǎn)需加一指針域，存儲(chǔ)密度降低；2)非隨機(jī)存儲(chǔ)結(jié)構(gòu)，查找定位操作需要從頭指針出發(fā)順著鏈表掃描。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)存儲(chǔ)分配方式順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素時(shí)間性能查找順序存儲(chǔ)結(jié)構(gòu)O(1)單鏈表O(n)插入和刪除順序存儲(chǔ)結(jié)構(gòu)需

22、要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間為O(n)單鏈表在找出某位置的指針后，插入和刪除的時(shí)間僅為O(1)空間性能順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了，浪費(fèi)，分小了，易發(fā)生溢出單鏈表不需要預(yù)分配一整塊存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)也不受限制鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)的比對(duì)：假設(shè)我們的校園只有單行道保安沿這條路線巡邏，需要查遍所有地點(diǎn)。有一天，保安先從主教出發(fā)，想把以上地點(diǎn)走一遍，此時(shí)主管告訴他，不行，你必須從主校門開(kāi)始走。主校門辦公樓圖書館體育館機(jī)電樓主教逸夫樓北門事實(shí)上，把主校門和北門連接起來(lái)，形成一個(gè)環(huán)路，就解決了這個(gè)問(wèn)題。單鏈表的尷尬4.循環(huán)鏈表特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，

23、整個(gè)鏈表首尾相連形成一個(gè)環(huán)。 帶頭結(jié)點(diǎn)的循環(huán)鏈表1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。對(duì)帶頭結(jié)點(diǎn)的單循環(huán)鏈表head為空的判定條件是 head-next=head帶頭結(jié)點(diǎn)的空循環(huán)鏈表例：假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，p指向該鏈表中某一結(jié)點(diǎn)，編寫一個(gè)算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。單鏈表只能從頭結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表，而循環(huán)單鏈表則可以從表中任意結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表。.a1a2an-1a0ps=p;while(s-next-next!=p) s=s-next;如何尋找前驅(qū)結(jié)點(diǎn)？s指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)ss-next=p;刪除該結(jié)點(diǎn)的前

24、驅(qū)結(jié)點(diǎn)思考：對(duì)于單鏈表而言，連接兩個(gè)單鏈表應(yīng)該如何實(shí)現(xiàn)？.a0head1a1an-1.b0head2b1bn-1currentcurrent-next=head2-next對(duì)于循環(huán)單鏈表呢？.a0head1a1an-1.b0head2b1bn-1pp=head1-next;head1-next=head2-next-next;Head2-next=p;.a0head1a1an-1.b0head2b1bn-1p主校門辦公樓圖書館體育館機(jī)電樓主教逸夫樓北門終于有一天，保安在感嘆：如果我們有雙行道該多好啊！雙向鏈表（double linked list）是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)

25、點(diǎn)的指針域。07/08/2022645.雙向鏈表定義：在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，next 指向后繼結(jié)點(diǎn)，prior指向前趨結(jié)點(diǎn)。 datapriornext結(jié)點(diǎn)構(gòu)成：1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)作用：可以方便地沿向前或向后兩個(gè)方向查找。克服單鏈表中每個(gè)結(jié)點(diǎn)只能找到它的后繼結(jié)點(diǎn)，不能找到前驅(qū)結(jié)點(diǎn)。若要找前驅(qū)結(jié)點(diǎn)，必須從頭指針開(kāi)始重新查找的不足。head.ana2a1nextprior對(duì)指向雙向鏈表任一結(jié)點(diǎn)的指針p，有下面的關(guān)系：p-next-prious=p-prious-next=ppnextpriouspriousnext設(shè)對(duì)象引用p表示雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則p.next表

26、示第 個(gè)結(jié)點(diǎn)，p.next.prior表示第 個(gè)結(jié)點(diǎn)，即p.next.prior = p；同樣地，p.prior表示第 個(gè)結(jié)點(diǎn)，p.prior.next仍表示第 個(gè)結(jié)點(diǎn)，即p.prior.next = p。雙向鏈表的關(guān)系i+1ii-1i5.雙向鏈表(1)插入結(jié)點(diǎn)：在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)q，只需要修改p,q結(jié)點(diǎn)的prior和next域即可。p插入前cbax待插入的結(jié)點(diǎn):q1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)cbaxqpp結(jié)點(diǎn)作為q結(jié)點(diǎn)的前驅(qū):q-prior=p；p結(jié)點(diǎn)的后繼作為q結(jié)點(diǎn)的后繼:q -next=p-next；q結(jié)點(diǎn)作為p 結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn):p-next-prior=qq

27、結(jié)點(diǎn)作為p結(jié)點(diǎn)的后繼:p-next=q； (p的后繼指向新結(jié)點(diǎn)q)確定新結(jié)點(diǎn)q的前驅(qū)和后繼5.雙向鏈表p刪除前cba(2)刪除結(jié)點(diǎn)：刪除P指針?biāo)附Y(jié)點(diǎn)，只需修改P指針的前驅(qū)和后繼結(jié)點(diǎn)的next，prior域即可。1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)p p的后繼結(jié)點(diǎn)作為p結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的后繼 (a c) p的前驅(qū)結(jié)點(diǎn)作為p結(jié)點(diǎn)后繼結(jié)點(diǎn)的前驅(qū) ( a c) p-prior-next = p-next；p-next-prior= p-prior；free(p)；cba習(xí)題講解1. 線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是_。 A. 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) B. 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、

28、順序存取的存儲(chǔ)結(jié)構(gòu) C. 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) D. 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)2. 在單鏈表中，增加頭結(jié)點(diǎn)的目的是_。 A. 方便運(yùn)算的實(shí)現(xiàn) B. 使單鏈表至少有一個(gè)結(jié)點(diǎn) C. 標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D. 說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)BA3 用鏈表表示線性表的優(yōu)點(diǎn)是_。 A. 便于插入和刪除操作 B. 數(shù)據(jù)元素的物理順序與邏輯順序相同 C. 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 D. 便于隨機(jī)存取4.某線性表采用順序存儲(chǔ)結(jié)構(gòu),每個(gè)元素占4個(gè)存儲(chǔ)單元,首地址為200,則第12個(gè)元素的存儲(chǔ)地址是_. A. 248 B. 247 C. 246 D. 244AD5. 下列

29、對(duì)于線性鏈表的描述中正確的是_。(05.4月 ）A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的A6. 線性表是（） A. 一個(gè)有限序列，可以為空 B. 一個(gè)有限序列，不能為空 C. 一個(gè)無(wú)限序列，可以為空 D. 一個(gè)無(wú)限序列，不能為空7在一個(gè)長(zhǎng)度為n的線性表中，刪除值為x的元素時(shí)需要比較元 素和移動(dòng)元素的總次數(shù)為（） A. （n+1）/2 B.n/2 C. n D.n+18. 一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1

30、in+1) 位置插入一個(gè)新元素時(shí)，需要從后面向前依次后移（ ）個(gè)元 素。 A. n-i B. n-i+1 C. n-i-1 D. iACB9.設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai,若要?jiǎng)h除ai之后的結(jié)點(diǎn)（若存 在），則需修改指針的操作為（）。A. p-next= p-next-next B. p=p-next C. p=p-next-next D. next=p10.設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai,指針q指向?qū)⒁迦氲男陆Y(jié)點(diǎn) x，則當(dāng)x插在鏈表中兩個(gè)數(shù)據(jù)元素ai和ai+1之間時(shí)，只要先 修改 q-next=p-next，后修改（）即可。A. p-next= q B. p-next= p-next-nex

31、t C. p-next=q-next D. q-next=null 11.在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié) 點(diǎn)，則需要相繼修改（）個(gè)指針域的值。 A. 1 B. 2 C. 3 D.4AAB12.不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（）。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL13帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（）。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL14.在一個(gè)帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)

32、之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（）個(gè)指針域的值。A. 2 B. 3 C. 4 D.6ABC15.在一個(gè)帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)q指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對(duì)q-next賦值為（）A. p-prior B. p-next C. p-next-next D. p-prior -prior16.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）A. 必須是連續(xù)的B. 一定是不連續(xù)的C. 部分地址必須是連續(xù)的D. 連續(xù)與否均可以BD17. 下列敘述中正確的是：(2010年9月國(guó)二） A）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的B）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空

33、間一般要多于順序存儲(chǔ)結(jié)構(gòu)C）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)D）上述三種說(shuō)法都不對(duì) B1.在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行一下操作： q=p-next; p-data= p-next-data; p-next=_； free(q);p-next-nextpqABBC2. 在一個(gè)單鏈表中指針p所指向結(jié)點(diǎn)的后面插入一個(gè)指針q所指向的結(jié)點(diǎn)時(shí)，首先把_ _ 的值賦給q-next，然后把_的值賦給p-next。p-nextq3.假定指向單鏈表中第一個(gè)結(jié)點(diǎn)的表頭指針為head，則向該單鏈表的表頭插入指針p所指向的新結(jié)點(diǎn)時(shí)，首先執(zhí)行_ _賦值操作，然后執(zhí)行_ _ 賦值操

34、作。 p-next=headhead=pheadp4. 在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把_的值賦給p-next指針域。p-next-next5. 在_鏈表中，既可以通過(guò)設(shè)定一個(gè)頭指針也可 以通過(guò)設(shè)定一個(gè)尾指針來(lái)確定它，即通過(guò)頭指針或 尾指針可以訪問(wèn)到該鏈表中的每個(gè)結(jié)點(diǎn)。 循環(huán)6. 在一個(gè)帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p所指向的結(jié) 點(diǎn)之前插入一個(gè)指針s所指向結(jié)點(diǎn)時(shí),可執(zhí)行如下操作：(1) s -prior=_；(2) p-prior-next=s;(3) s-next=_;(4) p-prior=_;p-priorpsps7. 線性表的長(zhǎng)度是指_。 線性表中包含數(shù)據(jù)元素的個(gè)數(shù)

35、 8.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_(kāi)和_。 單鏈表、雙鏈表 9. 循環(huán)單鏈表與非循環(huán)單鏈表的主要不同是循環(huán)單鏈表的尾結(jié) 點(diǎn)指針_，而非循環(huán)單鏈表的尾結(jié)點(diǎn)指針_。 指向鏈表頭節(jié)點(diǎn) 指向空 10.訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著_依次進(jìn)行。 指針域 11. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_， 另一個(gè)指向_。前驅(qū)節(jié)點(diǎn) 后續(xù)節(jié)點(diǎn) 12. 在一個(gè)雙向鏈表中刪除指針p所指向的結(jié)點(diǎn)時(shí)，需要對(duì) p-next-prior指針域賦值為_(kāi)。 p-prior 13.設(shè)head為單循環(huán)鏈表L的頭結(jié)點(diǎn)，則L為空表的條件是_。 head-next=head 14. 在一個(gè)長(zhǎng)度為n的順序表