鏈表、雙向鏈表、循環(huán)鏈表

計(jì)算機(jī)軟件技術(shù)基礎(chǔ)長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院基礎(chǔ)部孫爽滋順序表優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：邏輯上相鄰元素存儲(chǔ)位置也相鄰,無(wú)需增加額外存儲(chǔ)空間可方便隨機(jī)存取表中任一元素。缺點(diǎn)：插入和刪除運(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)不足的解決辦法鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn):1.2.3線性表的鏈?zhǔn)酱鎯?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)酱鎯?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)。101.分配內(nèi)存函數(shù)：malloc()——原型在stdlib.h中

1)調(diào)用方式

void*malloc(unsignedsize)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ù)11例：為1000個(gè)字符動(dòng)態(tài)分配內(nèi)存

char*base_ptr;base_ptr=(char*)malloc(1000);結(jié)合C語(yǔ)言：12structdata{intno;charname[10];intscore;};structdata*p;p=(structdata*)malloc(sizeof(structdata));

if(p==NULL){puts(“outofmemory\n”);exit(1);}結(jié)合C語(yǔ)言：13①(structdata*)返回結(jié)構(gòu)指針②sizeof(structdata)通知malloc分配足夠的內(nèi)存給structdata的每一個(gè)結(jié)構(gòu)成員③p接受返回的指針④如果內(nèi)存heap區(qū)已滿，則返回NULL⑤exit()函數(shù)被定義在process.h或者stdlib.h中

0:程序正常終止非0：程序非正常終止結(jié)合C語(yǔ)言：142.calloc()函數(shù)原型在stdlib.h中

1)調(diào)用方式

void*calloc(unsignedn,unsignedsize)2)功能分配n個(gè)具有size個(gè)字節(jié)的存儲(chǔ)空間，并返回一個(gè)指向被分配內(nèi)存起始地址的指針；如果沒(méi)有足夠的內(nèi)存滿足要求，則返回一個(gè)空指針結(jié)合C語(yǔ)言：153.free()函數(shù)原型在stdlib.h中

1)調(diào)用方式

voidfree(void*ptr)2)功能釋放由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)的單鏈表123∧head123∧head頭結(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)structNode{intdata;structNode*next;};structNode*head;head->next(head->next)->data起始結(jié)點(diǎn)的地址6鏈表的訪問(wèn)structNode*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)。*將當(dāng)前結(jié)點(diǎn)的元素值賦給xx=p->data;ListNode*p;intx;x6pListNode*p;intx;p*將x賦給當(dāng)前結(jié)點(diǎn)，修改當(dāng)前結(jié)點(diǎn)的元素值x=10;p->data=x;1021建立帶頭節(jié)點(diǎn)的單鏈表

尾插法建立單鏈表（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=(structnode*)malloc(sizeof(structnode));

head->next==NULL;tail=head;（3）生成新結(jié)點(diǎn)（p），輸入數(shù)據(jù)

p=(structnode*)malloc(sizeof(structnode));

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)22structnode{charname[10];intwage;structnode*next;};23定義頭指針、尾指針、新節(jié)點(diǎn)指針初始化（帶頭節(jié)點(diǎn)）開(kāi)辟新節(jié)點(diǎn)節(jié)點(diǎn)個(gè)數(shù)<nYN數(shù)據(jù)賦給新節(jié)點(diǎn)新節(jié)點(diǎn)鏈接到表尾重新置表尾建立帶頭結(jié)點(diǎn)鏈表的代碼(后插法)//建立n個(gè)結(jié)點(diǎn)單鏈表,返回頭指針//定義頭、

尾、p指針structnode*CreatList(intn){inti;stuctnode*head,tail,p;head=(structnode*)malloc(sizeof(structnode));head->next=NULL;tail=head;for(i=0;i<n;i++){p=(structnode*)malloc(sizeof(structnode));scanf(“%d”,&p->data);p->next=NULL;tail->next=p;tail=p;}returnL;}//建立頭結(jié)點(diǎn)//用tail標(biāo)記鏈表尾部//生成新結(jié)點(diǎn)//輸入結(jié)點(diǎn)的數(shù)據(jù)域//鏈接到表尾//更新尾指針//返回鏈表的頭指針structnode{charname[20];structnode*next;};structnode*head;typedefstructnode{charname[20];structnode*next;}LinkList;LinkList*head;新的類型名代換舊的類型名，也就是說(shuō)：LinkList等價(jià)與structnode3.單鏈表:

定義：由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)之后插入一個(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:pnext＝s考慮上述兩步驟若顛倒會(huì)怎樣？插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp

B

C

Xs

A修改p指針域,使其指向新結(jié)點(diǎn)s:pnext＝s后面的結(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.2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)刪除步驟修改q結(jié)點(diǎn)指針域qnext＝pnextCpBA刪除前刪除后qpCBAfree(p);先找到p的前驅(qū)結(jié)點(diǎn)qqnext＝qnextnext存儲(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)需要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間為O(n)單鏈表在找出某位置的指針后，插入和刪除的時(shí)間僅為O(1)空間性能順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了，浪費(fèi)，分小了，易發(fā)生溢出單鏈表不需要預(yù)分配一整塊存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)也不受限制單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)的比對(duì)：假設(shè)我們的校園只有單行道保安沿這條路線巡邏，需要查遍所有地點(diǎn)。有一天，保安先從主教出發(fā)，想把以上地點(diǎn)走一遍，此時(shí)主管告訴他，不行，你必須從主校門開(kāi)始走。。。主校門辦公樓圖書(shū)館體育館機(jī)電樓主教逸夫樓北門事實(shí)上，把主校門和北門連接起來(lái)，形成一個(gè)環(huán)路，就解決了這個(gè)問(wèn)題。單鏈表的尷尬4.循環(huán)鏈表特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(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)，編寫(xiě)一個(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)的前驅(qū)結(jié)點(diǎn)思考：對(duì)于單鏈表而言，連接兩個(gè)單鏈表應(yīng)該如何實(shí)現(xiàn)？...a0head1a1an-1^...b0head2b1bn-1^currentcurrent.next=head2.next對(duì)于循環(huán)單鏈表呢？...a0head1a1an-1...b0head2b1bn-1pp=head1.next;head1.next=head2.next.next;head2.next=p;...a0head1a1an-1...b0head2b1bn-1p主校門辦公樓圖書(shū)館體育館機(jī)電樓主教逸夫樓北門終于有一天，保安在感嘆：如果我們有雙行道該多好??！雙向鏈表（doublelinkedlist）是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。01/02/2023395.雙向鏈表定義：在雙向鏈表中，每個(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->priou=p->priou->next=ppnextpriouspriousnext

設(shè)對(duì)象引用p表示雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則p.next表示第

個(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)cbaxqp①p結(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=q④q結(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)的后繼(ac)

②

p的前驅(qū)結(jié)點(diǎn)作為p結(jié)點(diǎn)后繼結(jié)點(diǎn)的前驅(qū)(ac)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)、順序存取的存儲(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.248B.247C.246D.244AD5.下列對(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）/2B.n/2C.nD.n+18.一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1≤i≤n+1)

位置插入一個(gè)新元素時(shí)，需要從后面向前依次后移（）個(gè)元素。A.n-iB.n-i+1C.n-i-1D.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->next C.p->next=q->nextD.q->next=null11.在一個(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)之前插入一個(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ǔ)空間一般要多于順序存儲(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í)行__

___賦值操作。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ù)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->prior13.設(shè)head為單循環(huán)鏈表L的頭結(jié)點(diǎn)，則L為空表的條件是______。head->next=head14.在一個(gè)長(zhǎng)度為n的順序表中的刪除第i個(gè)元素（0≤i≤n-1），需要向前移動(dòng)______個(gè)元素。n-i15.線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是

。(n-1)/216.一含N個(gè)元素的順序表，若在第i個(gè)元素之前插入一個(gè)元素，需移動(dòng)

個(gè)元素。n-i+117.從鏈表種刪除q結(jié)點(diǎn)之后的p結(jié)點(diǎn)，語(yǔ)句為：q->next=

。

p->next18.鏈表中每個(gè)結(jié)點(diǎn)包含兩部分內(nèi)容，一部分為