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

計算機(jī)軟件技術(shù)基礎(chǔ)長春理工大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院基礎(chǔ)部孫爽滋順序表優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：邏輯上相鄰元素存儲位置也相鄰,無需增加額外存儲空間可方便隨機(jī)存取表中任一元素。缺點(diǎn)：插入和刪除運(yùn)算不方便,必須移動大量結(jié)點(diǎn),效率較低不適合元素經(jīng)常變動的大的線性表。對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；容易造成存儲空間的“碎片”思路(鏈?zhǔn)酱鎯Γ涸乜梢陨⒙湓谌魏挝恢?，不必相鄰讓每個元素知道它的下一個元素在哪里我們只需要知道第一個元素的位置插入刪除不再需要移動元素而是需要修改元素間的關(guān)系123456234561順序存儲結(jié)構(gòu)不足的解決辦法鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn):1.2.3線性表的鏈?zhǔn)酱鎯Y(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)酱鎯Y(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)。101.分配內(nèi)存函數(shù)：malloc()——原型在stdlib.h中

1)調(diào)用方式

void*malloc(unsignedsize)2)功能在內(nèi)存中分配size個字節(jié)的存儲空間，并返回指向分配存儲區(qū)起始地址的指針；如果不能獲得需要的存儲空間，將返回空指針。

注：在把返回值賦給具有一定數(shù)據(jù)類型的指針變量時，應(yīng)對返回值作強(qiáng)制類型轉(zhuǎn)換。結(jié)合C語言：跟鏈表相關(guān)的函數(shù)11例：為1000個字符動態(tài)分配內(nèi)存

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

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

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

1)調(diào)用方式

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

1)調(diào)用方式

voidfree(void*ptr)2)功能釋放由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)的單鏈表123∧head123∧head頭結(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)structNode{intdata;structNode*next;};structNode*head;head->next(head->next)->data起始結(jié)點(diǎn)的地址6鏈表的訪問structNode*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)。*將當(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個節(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個節(jié)點(diǎn)為止。當(dāng)表空時，頭指針和尾指針同時指向頭節(jié)點(diǎn)22structnode{charname[10];intwage;structnode*next;};23定義頭指針、尾指針、新節(jié)點(diǎn)指針初始化（帶頭節(jié)點(diǎn)）開辟新節(jié)點(diǎn)節(jié)點(diǎn)個數(shù)<nYN數(shù)據(jù)賦給新節(jié)點(diǎn)新節(jié)點(diǎn)鏈接到表尾重新置表尾建立帶頭結(jié)點(diǎn)鏈表的代碼(后插法)//建立n個結(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;新的類型名代換舊的類型名，也就是說：LinkList等價與structnode3.單鏈表:

定義：由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)之后插入一個指針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:pnext＝s考慮上述兩步驟若顛倒會怎樣？插入步驟修改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)單鏈表刪除：不需要移動元素,僅修改指針鏈接刪除結(jié)點(diǎn)刪除p指向的結(jié)點(diǎn)只修改p(被刪除結(jié)點(diǎn))的前驅(qū)結(jié)點(diǎn)的指針域即可1.2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)刪除步驟修改q結(jié)點(diǎn)指針域qnext＝pnextCpBA刪除前刪除后qpCBAfree(p);先找到p的前驅(qū)結(jié)點(diǎn)qqnext＝qnextnext存儲分配方式

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

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

個結(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)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)酱鎯Y(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.線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是______。

A.順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B.隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(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)算的實現(xiàn)

B.使單鏈表至少有一個結(jié)點(diǎn)

C.標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

D.說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn)BA3用鏈表表示線性表的優(yōu)點(diǎn)是______。

A.便于插入和刪除操作

B.數(shù)據(jù)元素的物理順序與邏輯順序相同

C.花費(fèi)的存儲空間較順序存儲少

D.便于隨機(jī)存取4.某線性表采用順序存儲結(jié)構(gòu),每個元素占4個存儲單元,首地址為200,則第12個元素的存儲地址是_______.

A.248B.247C.246D.244AD5.下列對于線性鏈表的描述中正確的是______。(05.4月）A）存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的B）存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C）存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D）存儲空間必須連續(xù)，且各元素的存儲順序是任意的A6.線性表是（）

A.一個有限序列，可以為空B.一個有限序列，不能為空

C.一個無限序列，可以為空D.一個無限序列，不能為空7．在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為（）

A.（n+1）/2B.n/2C.nD.n+18.一個長度為n的順序存儲的線性表中，向第i個元素(1≤i≤n+1)

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

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

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

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

。

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