《計(jì)算機(jī)應(yīng)用基礎(chǔ)課件》1.2線性表

《《計(jì)算機(jī)應(yīng)用基礎(chǔ)課件》1.2線性表》由會(huì)員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)應(yīng)用基礎(chǔ)課件》1.2線性表（63頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,第,1,章　 數(shù)據(jù)結(jié)構(gòu),1.1 基本數(shù)據(jù)結(jié)構(gòu)與算法,,,1.2 線性表,,1.3 棧和隊(duì)列,,1.4 樹和二叉樹,,,1.5 查找,,1.6 內(nèi)部排序,A,B,C,D,E,F,G,姓名 學(xué)號(hào) 成績(jī) 班級(jí),,,李紅 9761059 95 機(jī)97.6,,10,65,865,,1.2 線性表,1. 線性表的定義,,1) 定義：,具有,相同數(shù)據(jù)類型,的n(n≥0)個(gè)數(shù)據(jù)元素組成的,有限,序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。,,2) 表示:,,,L

2、=( a,0,，a,2,，a,3,，…a,i-1,，a,i,，a,i+1,，,...,a,n-1,),其中:,n為,線性表長(zhǎng)度,(,n=0稱為空表,)，表中相鄰元素之間存在著順序關(guān)系。a,0,：,表頭,元素；a,n-1,：,表尾,元素；a,i-1,稱為a,i,的直接,前驅(qū),；a,i+1,稱為a,i,的直接,后繼,。,,表頭,表尾,,1.2 線性表,1. 線性表的定義,,1) 定義：,具有,相同數(shù)據(jù)類型,的n(n≥0)個(gè)數(shù)據(jù)元素組成的,有限,序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。,,2) 表示:,,,L=( a,0,，a,2,，a,3,，…a,i-1,，a,i,，a,i+1,，...,a,n-1,)

3、,3) 線性結(jié)構(gòu)特點(diǎn):,(1)有且只有一個(gè)根結(jié)點(diǎn)a,0,,，無前驅(qū) 。,,(2)有且只有一個(gè)終端結(jié)點(diǎn)a,n-1,，無后繼 。,,(3)其他結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。,,,1.2 線性表,1. 線性表的定義,,1) 定義：,具有,相同數(shù)據(jù)類型,的n(n≥0)個(gè)數(shù)據(jù)元素組成的,有限,序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。,,2) 表示:,,,3) 線性結(jié)構(gòu)特點(diǎn):,4) 線性表的分類,,(1)簡(jiǎn)單線性表：,,,數(shù)據(jù)元素是簡(jiǎn)單項(xiàng)(數(shù)字、字母、季節(jié)名等)。,,如:(12,34,4,67,8),,(2)復(fù)雜線性表：,,,數(shù)據(jù)元素由,若干個(gè)數(shù)據(jù)項(xiàng),組成，此時(shí)數(shù)據(jù)元素稱為,記錄或結(jié)點(diǎn), 如學(xué)生成績(jī)表

4、.,L=( a,0,，a,2,，a,3,，…a,i-1,，a,i,，a,i+1,，...,a,n-1,),,學(xué)生健康情況登記表如下：,姓 名,學(xué) 號(hào),性 別,年齡,健康情況,王小林,790631,男,18,健康,陳 紅,790632,女,20,一般,劉建平,790633,男,21,健康,張立立,790634,男,17,神經(jīng)衰弱,……..,……..,…….,…….,…….,,1.順序表基本概念,,,,,,,,,1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1) 順序存儲(chǔ)結(jié)構(gòu)：,,,用一,組地址連續(xù)的存儲(chǔ)空間,依次存放線性表的各元素 。,順序表：,,采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表(一維數(shù)

5、組),,,表中的所有元素所占,存儲(chǔ)空間連續(xù),,表中各元素在存儲(chǔ)空間中按,邏輯順序存放,,順序存儲(chǔ)結(jié)構(gòu)特點(diǎn),1.2 線性表,,1.順序表基本概念,,,,,,,,,4.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1) 順序存儲(chǔ)結(jié)構(gòu)：,,,2) 第i個(gè)元素地址,4.2 線性表,其中:,,m,：每個(gè)元素占,m個(gè)存儲(chǔ)單元,,Loc(a,0,),第一個(gè)元素地址(基址),,,a,n－1,……..,a,i,……..,a,1,a,0,b,b+m,b+i*m,b+n*m,存儲(chǔ)地址,存儲(chǔ)狀態(tài),空閑,數(shù)據(jù)元素在線性表中的位序,1,,2,,,n,i,,,從存取方式看,線性表的順序存儲(chǔ)結(jié)構(gòu)是可以,隨機(jī)存儲(chǔ),的存儲(chǔ)結(jié)構(gòu).,,1.順序表基

6、本概念,,,,,,,,,1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1) 順序存儲(chǔ)結(jié)構(gòu)：,,,2) 第i個(gè)元素地址,1.2 線性表,2.順序表的基本運(yùn)算,,,存取:,訪問線性表的第i個(gè)元素，使用或改變數(shù)據(jù)元素的值。,,查找:,在線性表中查找滿足某種條件的數(shù)據(jù)元素。,,插入:,在線性表的第i個(gè)元素之前，插入一個(gè)同類型的元素。,(***),,刪除:,刪除線性表中第i個(gè)元素。,(***),,求表長(zhǎng):,求出線性表中元素的個(gè)數(shù)。,,置空表:,建立一個(gè)空表。,,清除表:,將已有線性表變?yōu)榭毡?，即刪除表中所有元素。,,,1.順序表基本概念,,,,,,,,,1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1) 順序存儲(chǔ)結(jié)構(gòu)：,,,2

7、) 第i個(gè)元素地址,1.2 線性表,2.順序表的基本運(yùn)算,,,——插入和刪除,,1),順序表的插入運(yùn)算:,,在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。,a,i-1,…..,a,1,a,0,a,n-1,…,a,i+1,a,i,,x,a,i-1,…..,a,1,a,0,,a,i,,…,a,n,,a,n-1,,…,,…,a,i+1,,a,i,,,a,i,,先移動(dòng),,后插入,x,,步驟：,(1)將,a,i,,~,,a,n,順序向后移動(dòng),為新元素讓出位置,,(2)將x置入”,空出,”的第i個(gè)位置,舉例：,(,在第4個(gè)和第5個(gè)元素之間插入元素91,),,,,,67,41,26,21,4,8

8、,9,16,0 1 2 3 4 5 6 7 8,,,67,41,26,21,4,8,9,16,0 1 2 3 4 5 6 7 8,,,67,41,26,21,4,8,9,16,0 1 2 3 4 5 6 7 8,21,21,91,,插入程序舉例(在8個(gè)

9、數(shù)中任意位置插入一個(gè)數(shù))：,,#define N 8,,main(),,{ int a[N+1]={12,34,45,6,78,9,10,91}, i,j,x;,,printf(“input the location to be inserted:”);,,scanf(“%d,%d”,,,,,,a[i-1]=x;,,for(j=0;j<=N;j++),,printf(“%d,”,a[j]);,,},for(j=i-1;j<=,N-1,;j++),,a[j+1]=a[j];,for(j=,N-1,;j>=i-1;j--),,a[j+1]=a[j];,,在第i個(gè)位置上作插入x,則需將第i個(gè)至第n個(gè)

10、元素移動(dòng)，即共需移動(dòng),(n-i+1),個(gè)元素。,插入運(yùn)算時(shí)間性能分析：,插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)移動(dòng)上。在長(zhǎng)度為n的線性表中插入一個(gè)元素，則,平均移動(dòng)元素次數(shù),(,期望值,),：,p,i,：在第i個(gè)位置上作插入的概率。,等差數(shù)列求和公式: ((首項(xiàng)+末項(xiàng))×項(xiàng)數(shù))/2,(n-i+1),線性表(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前)

11、 3,,2 (插入到第2個(gè)數(shù)a1前) 2,,3 (插入到第3個(gè)數(shù)a2前) 1,,(插入到第3個(gè)數(shù)a2后) 0,,,1.順序表基本概念,,,,,,,,,1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1) 順序存儲(chǔ)結(jié)構(gòu)：,,,2) 第i個(gè)元素地址,1.2 線性表,2.順序表的基本運(yùn)算,,,——插入和刪除,,2)順序表刪除運(yùn)算：,定義：,指將表中第,i,個(gè)元素從線性表中去掉。,原表長(zhǎng)為n：,( a,0,，a,1,，…a,i-1,，,a,i,,，a,i+1,，,…,a,n-1,),,新表長(zhǎng)為n-1：,( a

12、,0,，a,1,，…a,i-1,，a,i+1,，,…，,a,n-1,),,,步驟：,(1)將,a,i+1,,~,a,n-1，,,順序向前移動(dòng),,(2)表長(zhǎng),減一,,舉例：,(,刪除第五個(gè)元素21,),,,,,67,41,26,21,4,8,9,16,0 1 2 3 4 5 6 7 8,,,,67,41,26,4,8,9,16,0 1 2 3 4 5 6 7 8,時(shí)間

13、性能分析：,時(shí)間消耗與插入運(yùn)算相同，,平均移動(dòng)元素次數(shù)：,q,i,:在第i個(gè)位置上作插入的概率。設(shè)q,i,=1/n,,共需移動(dòng)(n-i)個(gè)元素。,67,,i 移動(dòng)次數(shù)(n-i),,1(刪除第1個(gè)數(shù)a0) 2,,2 (刪除第2個(gè)數(shù)a1) 1,,3 (刪除第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è),：有

14、一數(shù)組，存儲(chǔ)十個(gè)數(shù)，,,編程序刪除其中任意一個(gè)數(shù)。,,1.順序表基本概念,,,,,,,,3.順序表優(yōu)點(diǎn)和缺點(diǎn),優(yōu)點(diǎn)：,,邏輯上相鄰元素,存儲(chǔ)位置也相鄰,,無需增加額外存儲(chǔ)空間可方便,隨機(jī)存取,表中任一元素。,缺點(diǎn)：,,插入和刪除運(yùn)算不方便,必須移動(dòng)大量結(jié)點(diǎn),效率較低不適合元素經(jīng)常變動(dòng)的大的線性表。,1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu),1.2 線性表,2.順序表的基本運(yùn)算,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),存儲(chǔ)空間可以,不連續(xù),。,,不要求邏輯上相鄰的元素在物理位置上也相鄰。,,數(shù)據(jù)元素間邏輯關(guān)系由,指針域,確定。,1.2 線性表,即,,鏈表存儲(chǔ)結(jié)構(gòu)是

15、一種,動(dòng)態(tài),數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是它包含的據(jù)對(duì)象的個(gè)數(shù)及其相互關(guān)系可以,按需要改變,，存儲(chǔ)空間是程序,根據(jù)需要,在程序運(yùn)行過程中,向系統(tǒng)申請(qǐng),獲得，鏈表也不要求邏輯上相鄰的元素在物理位置上也相鄰，它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)。,,zhang,,,335,,,3108＃,,2548#,,,,name,sum,next,結(jié)構(gòu)體元素,結(jié)構(gòu)體元素的地址,結(jié)構(gòu)體元素的成員是地址型數(shù)據(jù),struct student,,{ char name[10];,,int sum;,,,struct student *next,;,,};,p,struct student,*p,;,,,strcpy(p-

16、>name,”zhang”)；,,p->sum=335;,,p->next=?,,,,zhang,,,335,,,3108＃,,2548#,bai,,,328,,,3148＃,,3108#,zhao,,,352,,,3188＃,,3148#,wu,,,347,,,0＃,,3188#,head,p1,p2,p3,有四個(gè)結(jié)構(gòu)體元素：,,zhang,,,335,,,3108＃,,2548#,bai,,,328,,,3148＃,,3108#,zhao,,,352,,,3188＃,,3148#,wu,,,347,,,0＃,,3188#,head,有四個(gè)結(jié)構(gòu)體元素：,,head,,（3）,尾結(jié)點(diǎn),的指針域

17、置為“NULL（空）”，作為鏈表結(jié)束的標(biāo)志,（1）,頭指針,變量head──指向鏈表的首結(jié)點(diǎn)。,（2）每個(gè),結(jié)點(diǎn),由2個(gè)域組成：,,1）數(shù)據(jù)域──存儲(chǔ)結(jié)點(diǎn)本身的信息。,,2）指針域──指向后繼結(jié)點(diǎn)的指針。,zhang,,,335,,,3108＃,,2548#,bai,,,328,,,3148＃,,3108#,zhao,,,352,,,3188＃,,3148#,wu,,,347,,,NULL,,3188#,struct student,,{ char name[10];,,int sum;,,,struct student *next,;,,};,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,

18、,,,,2.線性鏈表:,,定義：,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),數(shù)據(jù)域:,一部分存放數(shù)據(jù)元素值,,,指針域:,,存放指針,用于指向該結(jié)點(diǎn)的,,前一個(gè)結(jié)點(diǎn)或后一個(gè)結(jié)點(diǎn),線性鏈表中,,結(jié)點(diǎn)組成：,分類：,單鏈表、循環(huán)單鏈表、雙向鏈表,1.2 線性表,,其單鏈表示意圖如下：,有一線性表:,,(bat，cat，eat，fat，hat，jat，lat，mat),………,……,hat,200,…….,……,cat,135,eat,170,….,……,mat,Null,bat,130,fat,110,……,……,jat,205,lat,160,……,……,……,,11

19、0,,……,,130,,135,,……,,160,,頭指針 head 165,,170,,……,,200,,205,,……,165,簡(jiǎn)化為,：,鏈尾,略,,bat,cat,eat,mat ^,…,單鏈表是由表頭唯一確定，因此單鏈表可以用頭,指針的名字來命名。,例如：若頭指針名是head，則把鏈表稱為表head。,head,用C語言描述的單鏈表如下：,struct node,,{ char name[20];,,struct node *next;,,};,,struct node,*head;,typedef,struct node,,{ char name[

20、20];,,struct node *next;,,},LinkList;,,LinkList,*head;,新,的類型名代換,舊,的類型名，,,也就是說：LinkList等價(jià)與struct node,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,定義：,由n個(gè)結(jié)點(diǎn)鏈接，且每個(gè)結(jié)點(diǎn)中只,包含一個(gè)指針域,的鏈表。,例：,線性單鏈表( A, B, C, D, E, F ),邏輯狀態(tài),,,A,,B,,C,,D,,E,head,,,F,其中: head稱為單鏈表的頭指針,指向表中的第一個(gè)結(jié)點(diǎn),,物理狀態(tài),,E,

21、7,F,NULL,B,25,A,13,C,31,D,1,頭指針 存儲(chǔ)地址 數(shù)據(jù)域 指針域,19,,1,,7,,13,,19,,25,,31,單鏈表存取:,必須從頭指針開始進(jìn)行，依次順著指針向鏈尾方向掃描。找到各個(gè)元素,因此說線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種,順序存儲(chǔ),的存儲(chǔ)結(jié)構(gòu),。,,A,,B,,C,,D,,E,head,,,F,,,A,,B,,C,,D,,E,head,,,F,,A,,B,,C,,D,,E,head,,,F,,,帶,頭節(jié)點(diǎn),的單鏈表,編程：創(chuàng)建帶頭節(jié)點(diǎn)的單鏈表。,程序算法：,,（1）定義三個(gè),結(jié)構(gòu)體類型,的,指針變量,head, p, s,,

22、（2）利用,malloc,函數(shù)開辟,頭結(jié)點(diǎn),，由head, p共同來指向,,（3）再利用,malloc,函數(shù)開辟相應(yīng)的內(nèi)存空間，由s來指向,,（4）由鍵盤輸入數(shù)據(jù)，賦給s所指向的內(nèi)存空間,,（5）,p->next=s;,,（6）,p=s;,,（7）回到第（3）步,;,,程序算法：,,（1）定義三個(gè),結(jié)構(gòu)體類型,的,指針變量,head, p, s,,（2）利用,malloc,函數(shù)開辟,頭結(jié)點(diǎn),，由head, p共同來指向,,（3）再利用,malloc,函數(shù)開辟相應(yīng)的內(nèi)存空間，由s來指向,,（4）由鍵盤輸入數(shù)據(jù)，賦給s所指向的內(nèi)存空間,,（5）,p->next=s;,,（6）,p=s;,,（7）回

23、到第（3）步,;,head=p=(strutc node*) malloc(sizeof(struct node));,head,,p,對(duì)帶頭結(jié)點(diǎn)的復(fù)雜鏈表的基本操作,——,創(chuàng)建,,,程序算法：,,（1）定義三個(gè),結(jié)構(gòu)體類型,的,指針變量,head, p, s,,（2）利用,malloc,函數(shù)開辟,頭結(jié)點(diǎn),，由head, p共同來指向,,（3）再利用,malloc,函數(shù)開辟相應(yīng)的內(nèi)存空間，由s來指向,,（4）由鍵盤輸入數(shù)據(jù)，賦給s所指向的內(nèi)存空間,,（5）,p->next=s;,,（6）,p=s;,,（7）回到第（3）步,;,,,A,s->data=getchar();,s,p,對(duì)帶頭結(jié)點(diǎn)的復(fù)

24、雜鏈表的基本操作,——,創(chuàng)建,head,,p,,,程序算法：,,（1）定義三個(gè),結(jié)構(gòu)體類型,的,指針變量,head, p, s,,（2）利用,malloc,函數(shù)開辟,頭結(jié)點(diǎn),，由head, p共同來指向,,（3）再利用,malloc,函數(shù)開辟相應(yīng)的內(nèi)存空間，由s來指向,,（4）由鍵盤輸入數(shù)據(jù)，賦給s所指向的內(nèi)存空間,,（5）,p->next=s;,,（6）,p=s;,,（7）回到第（3）步,;,s,p,對(duì)帶頭結(jié)點(diǎn)的復(fù)雜鏈表的基本操作,——,創(chuàng)建,,,A,s,head,,p,,,B,,,A,,B,,C,,D,,E,head,,,F,,A,,B,,C,,D,,E,head,,,F,,,帶,頭節(jié)點(diǎn),

25、的單鏈表,,typedef,struct node,,{char data;,,struct node *next;,,},Linklist,;,,,Linklist,*head,*p,*s; char ch;,,head=(Linklist *)malloc(sizeof(Linklist));,,printf("input letters to create a list:\n");,,,while((ch=getchar())!='\n'),,{s=(Linklist *)malloc(sizeof(Linklist));,,s->data=ch;,,p->next=s;,,p=s;

26、,,},,p->next=NULL;,,},編程：創(chuàng)建帶頭節(jié)點(diǎn)的單鏈表。,,帶,頭節(jié)點(diǎn),的單鏈表,,typedef,,struct node,,{char data;,,struct node *next;,,},Linklist,;,,,Linklist,*head,*p,*s; char ch;,,head=(,Linklist *),malloc(,sizeof,(Linklist));,,printf("input letters to create a list:\n");,,p=head;,,while((ch=getchar())!='\n'),,{s=(,Linklist,

27、*),malloc,(,sizeof,(Linklist));,,s->data=ch;,,p->next=s;,,p=s;,,},,p->next=NULL;,,···············,2000,B,data,next,,struct node,,{char data;,,struct node *next;,,} Linklist;,,Linklist *head,*p,*s; char ch;,,head=(,Linklist *),malloc(,sizeof,(Linklist));,,printf("input letters to create a list:\n")

28、;,,p=head;,,while((ch=getchar())!='\n'),,{s=(,Linklist,*),malloc,(,sizeof,(Linklist));,,s->data=ch;,,p->next=s;,,p=s;,,},,p->next=NULL;,,···············,A,head,p,用戶輸入為：ABC,s,p,typedef,,struct node,,{char data;,,struct node *next;,,} Linklist;,,Linklist *head,*p,*s; char ch;,,head=(,Linklist *),mal

29、loc(,sizeof,(Linklist));,,printf("input letters to create a list:\n");,,p=head;,,while((ch=getchar())!='\n'),,{s=(,Linklist,*),malloc,(,sizeof,(Linklist));,,s->data=ch;,,p->next=s;,,p=s;,,},,p->next=NULL;,,···············,A,head,用戶輸入為：ABC,s,p,s,B,p,typedef,,struct node,,{char data;,,struct node *nex

30、t;,,} Linklist;,,Linklist *head,*p,*s; char ch;,,head=(,Linklist *),malloc(,sizeof,(Linklist));,,printf("input letters to create a list:\n");,,p=head;,,while((ch=getchar())!='\n'),,{s=(,Linklist,*),malloc,(,sizeof,(Linklist));,,s->data=ch;,,p->next=s;,,p=s;,,},,p->next=NULL;,,···············,A,hea

31、d,用戶輸入為：ABC,s,B,p,,s,C,p,NULL,typedef,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,,(1)單鏈表插入：,增加新結(jié)點(diǎn),修改鏈接指針,后插結(jié)點(diǎn),,在指針p所指結(jié)點(diǎn)之后插入一個(gè)指針s所指的結(jié)點(diǎn),,修改p和s所指結(jié)點(diǎn)的指針域的指針即可,,插入步驟,,修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):,s,?,next=p,?,next,p,,B,,C,X,s,,A,修改p指針域, 使其指向新結(jié)點(diǎn)s:,p,?,next＝s,考慮上述兩步驟若顛倒會(huì)怎樣？,,插入步驟,,修改s指針域,使其指向

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

33、除前,刪除后,q,p,,C,,B,,A,free(p);,先,找到p,的前驅(qū)結(jié)點(diǎn)q,q,?,next＝q,?,next,?,next,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,,4.循環(huán)鏈表,特點(diǎn)：,表中,最后一個(gè)結(jié)點(diǎn),的指針域指向,頭結(jié)點(diǎn),，整個(gè)鏈表首尾相連形成一個(gè)環(huán)。,,帶頭節(jié)點(diǎn)的循環(huán)鏈表,,優(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)鏈表,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表

34、:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,,4.循環(huán)鏈表,5.雙向鏈表,定義：,在雙向鏈表中，每個(gè)結(jié)點(diǎn)有,兩個(gè)指針域,，next,,指向后繼結(jié)點(diǎn)，prior指向前趨結(jié)點(diǎn)。,,,data,prior,next,結(jié)點(diǎn)構(gòu)成：,,作用：,可以方便地沿向前或向后兩個(gè)方向查找。克服單鏈表中每個(gè)結(jié)點(diǎn)只能找到它的后繼結(jié)點(diǎn)，不能找到前驅(qū)結(jié)點(diǎn)。若要找前驅(qū)結(jié)點(diǎn)，必須從頭指針開始重新查找的不足。,head,,,,,...,...,a,n,a,2,a,1,next,prior,對(duì)指向雙向鏈表任一結(jié)點(diǎn)的指針p，有下面的關(guān)系：,,p->next->priou=p->priou->next=

35、p,p,next,prious,prious,next,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,,4.循環(huán)鏈表,5.雙向鏈表,(1)插入結(jié)點(diǎn)：,在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)q，只需要修改p,q結(jié)點(diǎn)的prior和next域即可。,p,插入前,,,,c,b,a,,x,待插入的結(jié)點(diǎn),:,q,,,,,c,b,a,,x,q,p,①,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->

36、prior=q,④,q結(jié)點(diǎn)作為p結(jié)點(diǎn)的后繼:p->next=q； (p的后繼指向新結(jié)點(diǎn)q),②,③,④,①,確定新結(jié)點(diǎn)q的前驅(qū)和后繼,,,,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn),:,,,,,,,,,,2.線性鏈表:,,1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 線性表,3 .單鏈表:,,,4.循環(huán)鏈表,5.雙向鏈表,p,刪除前,,,,c,b,a,(2)刪除結(jié)點(diǎn)：,刪除P指針?biāo)附Y(jié)點(diǎn)，只需修改P指針的前驅(qū)和后繼結(jié)點(diǎn)的next，prior域即可。,,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->

37、prior->next = p->next；,p->next->prior= p->prior；,free(p)；,,,,c,b,a,,習(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. 說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

38、實(shí)現(xiàn),,,,3 用鏈表表示線性表的優(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. 244,,,,5. 下列對(duì)于線性鏈表的描述中正確的是______。(05.4月 ）,,A）存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的,,B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

39、,,C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面,,D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的,,,,6. 線性表是（）,,A. 一個(gè)有限序列，可以為空 B. 一個(gè)有限序列，不能為空,,C. 一個(gè)無限序列，可以為空 D. 一個(gè)無限序列，不能為空,7．在一個(gè)長(zhǎng)度為n的線性表中，刪除值為x的元素時(shí)需要比較元,,素和移動(dòng)元素的總次數(shù)為（）,,A. （n+1）/2 B.n/2 C. n D.n+1,——詳見《計(jì)算機(jī)基礎(chǔ)綜合實(shí)訓(xùn)教程》P175,8. 一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1≤i≤n+1),,位置插入一個(gè)新元素時(shí)，需要從后面,向

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

41、xt，后修改（）即可。,,A. p->next= q B. p->next= p->next->next,,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.4,,,12.不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（）。,,A. L= = NULL B. L->next = = NULL,,C. L->next = = L D. L! = NULL,,13．帶頭

42、結(jié)點(diǎn)的單鏈表L為空的判定條件是（）。,,A. L= = NULL B. L->next = = NULL,,C. L->next = = L D. L! = NULL,,14.在一個(gè)帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（）個(gè)指針域的值。,,A. 2 B. 3 C. 4 D.6,,15.在一個(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->ne

43、xt->next D. p->prior ->prior,,16.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）,,A. 必須是連續(xù)的 B. 一定是不連續(xù)的,,C. 部分地址必須是連續(xù)的 D. 連續(xù)與否均可以,,2.在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行一下操作：,,q=p->next;,,p->data= p->next->data;,,p->next=_____；,,free(q);,填空題,,1.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬,,于 ———— 結(jié)構(gòu)。（05.9月）,存儲(chǔ)結(jié)構(gòu),p->next->next,p,q,A,B,B,C,,3. 在一個(gè)單鏈表中指針p所指向結(jié)點(diǎn)的

44、后面插入一個(gè)指針q所指向的結(jié)點(diǎn)時(shí)，首先把,___ __,的值賦給q->next，然后把_____的值賦給p->next。,p->next,q,4.假定指向單鏈表中第一個(gè)結(jié)點(diǎn)的表頭指針為head，則向該單鏈,,表的表頭插入指針p所指向的新結(jié)點(diǎn)時(shí)，首先執(zhí)行_____賦值操,,作，然后執(zhí)行_____賦值操作。,p->next=head,head=p,head,p,,5. 在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把_____的值賦給p->next指針域。,p->next->next,6. 在_____鏈表中，既可以通過設(shè)定一個(gè)頭指針也可,,以通過設(shè)定一個(gè)尾指針來確定它，即通過頭指針或

45、,,尾指針可以訪問到該鏈表中的每個(gè)結(jié)點(diǎn)。,循環(huán),7. 在一個(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->prior,p,s,p,s,,8. 線性表的長(zhǎng)度是指_______。,線性表中包含數(shù)據(jù)元素的個(gè)數(shù),,9.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_______和_______。,單鏈表、雙鏈表,,10. 循環(huán)單鏈表與非循環(huán)單鏈表的主要

46、不同是循環(huán)單鏈表的尾結(jié),,點(diǎn)指針______，而非循環(huán)單鏈表的尾結(jié)點(diǎn)指針______。,指向鏈表頭節(jié)點(diǎn),,指向空,,11.訪問單鏈表中的結(jié)點(diǎn)，必須沿著______依次進(jìn)行。,指針域,,12. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向______，,,另一個(gè)指向______。,前驅(qū)節(jié)點(diǎn),,后續(xù)節(jié)點(diǎn),,13. 在一個(gè)雙向鏈表中刪除指針p所指向的結(jié)點(diǎn)時(shí)，需要對(duì),,p->next->prior指針域賦值為______。,p->prior,,,14.設(shè)head為單循環(huán)鏈表L的頭結(jié)點(diǎn)，則L為空表的條件是______。,head->next=head,,15.假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入

47、序列a, b, c ,d,,,e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列是,,______。,bceda,,16. 在一個(gè)長(zhǎng)度為n的順序表中的刪除第i個(gè)元素（0≤i≤n-1），需,,要向前移動(dòng)______個(gè)元素。,n-i,17. 線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的,,概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是,,。,(n-1)/2,18.一含N個(gè)元素的順序表，若在第i個(gè)元素之前插入一個(gè)元素，需移動(dòng),,個(gè)元素。,n-i+1,,19.從鏈表種刪除q結(jié)點(diǎn)之后的p結(jié)點(diǎn)，語句為：q->next=,。,,p->next,,20.鏈表中每個(gè)結(jié)點(diǎn)包含兩部

48、分內(nèi)容，一部分為數(shù)據(jù)域，另一部,,分為,,域。,指針,,21. 在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的,,_______。,前驅(qū),,,假定建立了以下鏈表結(jié)構(gòu)，指針,p,、,q,分別指向如圖所示的結(jié)點(diǎn)，則以下可以將,q,所指結(jié)點(diǎn)從鏈表中刪除并釋放該結(jié)點(diǎn)的語句組是,,,,A) free(q); p->next=q->next;,,B) (*p).next=(*q).next; free(q);,,C) q=(*q).next; (*p).next=q; free(q);,,D) q=q->next;p->next=q;p=p->next; free(p);,,,,,head,,8,,4

49、,,3,,p,,q,,date,,next,,練1,,練2,head,,,,E,,F \0,,p,,date next,,G,,s,,若已建立如下圖所示的單向鏈表結(jié)構(gòu),在該鏈表結(jié)構(gòu)中，指針p、s分別指向圖中所示結(jié)點(diǎn)，則不能將s所指的結(jié)點(diǎn)插入到鏈表末尾仍構(gòu)成單向鏈表的語句組是,A) p =p->next; s->next=p; p->next=s;B) p =p->next; s->next=p->next; p->next=s;C) s->next=NULL; p=p->next; p->next=s;D) p=(*p).next; (*s).next=(*p).next; (*p).next=s,;,,,