線性表完整版課件

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

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

3、性表 用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過數(shù)據(jù)元素的存儲位置直接反映。 ( a1，a2，a3， . . , an ) 所謂一個元素的 是指該元素占用的若干(連續(xù)的)存儲單元的第一個單元的地址。地址LOC(ai)a1a2a3an d1 d2 d3 dn 1.2.2 線性表的順序存儲結(jié)構(gòu) 若假設(shè)每個數(shù)據(jù)元素占用k個存儲單元，并且已知第一個元素的存儲位置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 語言1) 順序存儲結(jié)構(gòu)： 2) 第i個元素地址順序表的基本運(yùn)算 插入和刪除1)順序表的插入運(yùn)算: 在線性表的第i個元素之前插入一個新的元素，先移動，后插入。ABCDEFGH空閑空間插隊(duì)前大哥，求求你？ABCDEFGH空閑空間插隊(duì)后大哥，謝謝你！1) 順序存儲結(jié)構(gòu)： 2) 第i個元素地址順序表的基本運(yùn)算 插入和刪除1)順序表的插入運(yùn)算: 在線性表的第i個元素之前插入一個新的元素，先移動，后插入。ai-1.a2a1anai+1ai

5、 x ai-1. a2 a1 ai an an ai+1 ai ai x插入程序舉例(在8個數(shù)中任意位置插入一個數(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)算時間性能分析：在第i個位置上作插入x,則需將第i個至第n個元素移動，即共需移動(n-i

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

7、算：定義：指將表中第i個元素從線性表中去掉。原表長為n：( a1，a2，ai-1，ai ，ai+1， an ) 新表長為n-1：( a1，a2，ai-1，ai+1， ， an ) 步驟：(1)將ai+1 an， 順序向前移動(2)表長減一ABCDEFGH空閑空間逃離后ABCDEFGH空閑空間逃離前騙子，還我錢(刪除第五個元素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)算：時間性能分析：時間消耗與插入運(yùn)算相同，平均移動元素次數(shù)：qi:在第i個位置上作插入的概率。設(shè)qi=1/n

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

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

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

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

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

13、nsigned size) 2)功能 在內(nèi)存中分配size個字節(jié)的存儲空間，并返回指向分配存儲區(qū)起始地址的指針；如果不能獲得需要的存儲空間，將返回空指針。 注：在把返回值賦給具有一定數(shù)據(jù)類型的指針變量時，應(yīng)對返回值作強(qiáng)制類型轉(zhuǎn)換。結(jié)合C語言：跟鏈表相關(guān)的函數(shù)36例：為1000個字符動態(tài)分配內(nèi)存 char *p; p=(char *)malloc(1000); 結(jié)合C語言：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語言：exit()函數(shù):被定義在stdlib.h中 0: 程序正常終止 非0：程序非正常終止382. calloc()函數(shù) 原型在stdlib.h中 1)調(diào)用方式 void *calloc(unsigned n, unsigned size) 2)功能 分配n個具有size個字節(jié)的存儲空間，并返回一個指向被分配內(nèi)存起始地址的指針；如果沒有足夠的內(nèi)存滿足要求，則返回一個空指針結(jié)合C語言：393. free()函數(shù) 原型在stdlib.h中 1)調(diào)用方式 void free(void *ptr) 2)功能 釋

15、放由ptr指向的內(nèi)存空間，并將它返回給堆 注：free()只能由前面動態(tài)內(nèi)存分配函數(shù)中所分配地址的那個指針來調(diào)用結(jié)合C語言：頭結(jié)點(diǎn)是在鏈表的起始結(jié)點(diǎn)之前附加的一個結(jié)點(diǎn).帶頭結(jié)點(diǎn)的單鏈表123head123head頭結(jié)點(diǎn)單鏈表帶頭結(jié)點(diǎn)的單鏈表head空表head 空表head-next=NULL頭結(jié)點(diǎn)有兩個優(yōu)點(diǎn)：由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，故在鏈表的第一個位置上的操作與表中其他位置上操作一致，無須進(jìn)行特殊處理。無論鏈表是否為空，其頭指針都是指向頭結(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鏈表的訪問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 空指針 對于線性鏈表，可以從頭指針(head)開始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。 typedef struct Node int data; struct Node *next; LinkList;LinkList * head;新的類型名代換舊的類型名，即：LinkList等價

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個節(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個節(jié)點(diǎn)為止。當(dāng)表空時，頭指針和尾指針同時指向頭節(jié)點(diǎn)47struct node char name10; int wage; struct node *next; ;48定義頭指針、尾指針、新節(jié)點(diǎn)指針初始化（帶

19、頭節(jié)點(diǎn)）開辟新節(jié)點(diǎn)節(jié)點(diǎn)個數(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個結(jié)點(diǎn)鏈接，且每個結(jié)點(diǎn)中只包含一個指針域的鏈表。 例：線性單鏈表( A, B, C, D, E, F )ABCDEhead F1.2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)3 .單鏈表: (1)單鏈表插入：增加新結(jié)點(diǎn),修改鏈接指針后插結(jié)點(diǎn)在指針p所指結(jié)點(diǎn)之

20、后插入一個指針s所指的結(jié)點(diǎn)修改p和s所指結(jié)點(diǎn)的指針域的指針即可 1.2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp B C Xs A修改p指針域, 使其指向新結(jié)點(diǎn)s: pnexts考慮上述兩步驟若顛倒會怎樣？插入步驟修改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)單鏈表刪除：不需要移動元素,僅修改指針鏈接刪除結(jié)點(diǎn)刪除p指向的結(jié)點(diǎn)只修改p(被刪除結(jié)點(diǎn))的前驅(qū)結(jié)點(diǎn)的指針域即可 1

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

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

23、整個鏈表首尾相連形成一個環(huán)。 帶頭結(jié)點(diǎn)的循環(huán)鏈表1.2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。對帶頭結(jié)點(diǎn)的單循環(huán)鏈表head為空的判定條件是 head-next=head帶頭結(jié)點(diǎn)的空循環(huán)鏈表例：假設(shè)長度大于1的循環(huán)單鏈表中，既無頭結(jié)點(diǎn)也無頭指針，p指向該鏈表中某一結(jié)點(diǎn)，編寫一個算法刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。單鏈表只能從頭結(jié)點(diǎn)開始遍歷整個鏈表，而循環(huán)單鏈表則可以從表中任意結(jié)點(diǎn)開始遍歷整個鏈表。.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)思考：對于單鏈表而言，連接兩個單鏈表應(yīng)該如何實(shí)現(xiàn)？.a0head1a1an-1.b0head2b1bn-1currentcurrent-next=head2-next對于循環(huán)單鏈表呢？.a0head1a1an-1.b0head2b1bn-1pp=head1-next;head1-next=head2-next-next;Head2-next=p;.a0head1a1an-1.b0head2b1bn-1p主校門辦公樓圖書館體育館機(jī)電樓主教逸夫樓北門終于有一天，保安在感嘆：如果我們有雙行道該多好??！雙向鏈表（double linked list）是在單鏈表的每個結(jié)點(diǎn)中，再設(shè)置一個指向其前驅(qū)結(jié)

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

26、示第 個結(jié)點(diǎn)，p.next.prior表示第 個結(jié)點(diǎn)，即p.next.prior = p；同樣地，p.prior表示第 個結(jié)點(diǎn)，p.prior.next仍表示第 個結(jié)點(diǎn)，即p.prior.next = p。雙向鏈表的關(guān)系i+1ii-1i5.雙向鏈表(1)插入結(jié)點(diǎn)：在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個結(jié)點(diǎn)q，只需要修改p,q結(jié)點(diǎn)的prior和next域即可。p插入前cbax待插入的結(jié)點(diǎn):q1.2.3 線性表的鏈?zhǔn)酱鎯Y(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)酱鎯Y(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. 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是_。 A. 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B. 隨機(jī)存取的存儲結(jié)構(gòu)、

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

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

30、in+1) 位置插入一個新元素時，需要從后面向前依次后移（ ）個元 素。 A. n-i B. n-i+1 C. n-i-1 D. iACB9.設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai,若要刪除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插在鏈表中兩個數(shù)據(jù)元素ai和ai+1之間時，只要先 修改 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.在一個單鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個新結(jié) 點(diǎn)，則需要相繼修改（）個指針域的值。 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.在一個帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)

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

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

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

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