計(jì)算機(jī)應(yīng)用基礎(chǔ)教學(xué)課件線性表

1、第 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)部排序ABCDEFG姓名 學(xué)號(hào) 成績(jī) 班級(jí) 李紅 9761059 95 機(jī)97.6 1065865 牛牛文庫(kù)文檔分享1.2 線性表1. 線性表的定義1) 定義：具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素組成的有限序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。 2) 表示: L=( a0，a2，a3，ai-1，ai ，ai+1，,.,an-1 ) 其中: n為線性表長(zhǎng)度(n=0稱為空表)，表中相鄰元素之間存在著順序關(guān)系。a0 ：表頭元素；an-1 ：表尾元素；ai-1稱為ai的直接前驅(qū)；a

2、i+1 稱為ai的直接后繼。 表頭表尾 牛牛文庫(kù)文檔分享1.2 線性表1. 線性表的定義1) 定義：具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素組成的有限序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。 2) 表示: L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 3) 線性結(jié)構(gòu)特點(diǎn):(1)有且只有一個(gè)根結(jié)點(diǎn)a0 ，無(wú)前驅(qū) 。(2)有且只有一個(gè)終端結(jié)點(diǎn)an-1 ，無(wú)后繼 。(3)其他結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 牛牛文庫(kù)文檔分享1.2 線性表1. 線性表的定義1) 定義：具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素組成的有限序列。是最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)。 2) 表示: 3) 線性

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ī)表.L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 牛牛文庫(kù)文檔分享學(xué)生健康情況登記表如下：姓 名學(xué) 號(hào)性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . . 牛牛文庫(kù)文檔分享1.順序表基本概念1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)1) 順序存儲(chǔ)結(jié)

4、構(gòu)： 用一組地址連續(xù)的存儲(chǔ)空間依次存放線性表的各元素 。順序表：采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表(一維數(shù)組) 表中的所有元素所占存儲(chǔ)空間連續(xù)表中各元素在存儲(chǔ)空間中按邏輯順序存放 順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)1.2 線性表 牛牛文庫(kù)文檔分享1.順序表基本概念4.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址4.2 線性表其中:m：每個(gè)元素占m個(gè)存儲(chǔ)單元Loc(a0)第一個(gè)元素地址(基址) 牛牛文庫(kù)文檔分享an1.ai.a1a0bb+mb+i*mb+n*m存儲(chǔ)地址存儲(chǔ)狀態(tài)空閑數(shù)據(jù)元素在線性表中的位序12n i 從存取方式看,線性表的順序存儲(chǔ)結(jié)構(gòu)是可以隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu). 牛牛文庫(kù)文檔

5、分享 1.順序表基本概念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)榭毡恚磩h除表中所有元素。 牛牛文庫(kù)文檔分享 1.順序表基本概念1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址1.2 線性表2.順序表的

6、基本運(yùn)算 插入和刪除1)順序表的插入運(yùn)算: 在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ai-1.a1a0an-1ai+1ai x ai-1. a1 a0 ai an an-1 ai+1 ai ai先移動(dòng)后插入 x 牛牛文庫(kù)文檔分享步驟：(1)將ai an順序向后移動(dòng),為新元素讓出位置(2)將x置入”空出”的第i個(gè)位置舉例：(在第4個(gè)和第5個(gè)元素之間插入元素91) 6741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 8212191 牛牛文庫(kù)文檔分享插

7、入程序舉例(在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; 牛牛文庫(kù)文檔分享在第i個(gè)位置上作插入x,則需將第i個(gè)至第n個(gè)元素移動(dòng)，即共需移動(dòng)(n-i+1)個(gè)元素。插入運(yùn)算時(shí)間性能分析：插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)移動(dòng)上。在長(zhǎng)度

8、為n的線性表中插入一個(gè)元素，則平均移動(dòng)元素次數(shù)(期望值)：pi：在第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前) 3 2 (插入到第2個(gè)數(shù)a1前) 23 (插入到第3個(gè)數(shù)a2前) 1 (插入到第3個(gè)數(shù)a2后) 0 牛牛文庫(kù)文檔分享 1.順序表基本概念1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)1) 順序存儲(chǔ)結(jié)構(gòu)： 2) 第i個(gè)元素地址1.2 線性表2.順序表的基本運(yùn)算 插入

9、和刪除2)順序表刪除運(yùn)算：定義：指將表中第i個(gè)元素從線性表中去掉。原表長(zhǎng)為n：( a0，a1，ai-1，ai ，ai+1， an-1 ) 新表長(zhǎng)為n-1：( a0，a1，ai-1，ai+1， ， an-1 ) 步驟：(1)將ai+1 an-1， 順序向前移動(dòng)(2)表長(zhǎng)減一 牛牛文庫(kù)文檔分享舉例：(刪除第五個(gè)元素21) 6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 8時(shí)間性能分析：時(shí)間消耗與插入運(yùn)算相同，平均移動(dòng)元素次數(shù)：qi:在第i個(gè)位置上作插入的概率。設(shè)qi=1/n 共需移動(dòng)(n-i)個(gè)元素。67 牛牛文庫(kù)文檔分享 i

10、移動(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ù)。 牛牛文庫(kù)文檔分享 1.順序表基本概念3.順序表優(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)的大的線性表。1.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)1.2 線性表2.順序表的基本運(yùn)算 牛牛文

11、庫(kù)文檔分享鏈?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)是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是它包含的據(jù)對(duì)象的個(gè)數(shù)及其相互關(guān)系可以按需要改變，存儲(chǔ)空間是程序根據(jù)需要在程序運(yùn)行過(guò)程中向系統(tǒng)申請(qǐng)獲得，鏈表也不要求邏輯上相鄰的元素在物理位置上也相鄰，它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)。 牛牛文庫(kù)文檔分享zhang33531082548#namesumnext結(jié)構(gòu)體元素結(jié)構(gòu)體元素的地址結(jié)構(gòu)體元素的成員是地址型數(shù)據(jù)struct student char name10; int sum; st

12、ruct student *next; ;pstruct student *p; strcpy(p-name,”zhang”)；p-sum=335;p-next=? 牛牛文庫(kù)文檔分享zhang33531082548#bai32831483108#zhao35231883148#wu34703188#headp1p2p3有四個(gè)結(jié)構(gòu)體元素： 牛牛文庫(kù)文檔分享zhang33531082548#bai32831483108#zhao35231883148#wu34703188#head有四個(gè)結(jié)構(gòu)體元素： 牛牛文庫(kù)文檔分享head（3）尾結(jié)點(diǎn)的指針域置為“NULL（空）”，作為鏈表結(jié)束的標(biāo)志（1）頭指針

13、變量head指向鏈表的首結(jié)點(diǎn)。（2）每個(gè)結(jié)點(diǎn)由2個(gè)域組成： 1）數(shù)據(jù)域存儲(chǔ)結(jié)點(diǎn)本身的信息。 2）指針域指向后繼結(jié)點(diǎn)的指針。zhang33531082548#bai32831483108#zhao35231883148#wu347NULL3188#struct student char name10; int sum; struct student *next; ; 牛牛文庫(kù)文檔分享鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn):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)組成：

14、分類：?jiǎn)捂湵?、循環(huán)單鏈表、雙向鏈表 1.2 線性表 牛牛文庫(kù)文檔分享其單鏈表示意圖如下：有一線性表: (bat，cat，eat，fat，hat，jat，lat，mat)hat200.cat135eat170.matNullbat130fat110jat205lat160 110 130 135 160頭指針 head 165 170 200 205 165簡(jiǎn)化為：鏈尾略 牛牛文庫(kù)文檔分享bat cat eat mat 單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例如：若頭指針名是head，則把鏈表稱為表head。head用C語(yǔ)言描述的單鏈表如下： struct node cha

15、r name20; struct node *next;struct node *head; typedef struct node char name20; struct node *next;LinkList;LinkList *head;新的類型名代換舊的類型名，也就是說(shuō)：LinkList等價(jià)與struct node 牛牛文庫(kù)文檔分享鏈?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) ABCDEhead F其中: head稱

16、為單鏈表的頭指針,指向表中的第一個(gè)結(jié)點(diǎn) 牛牛文庫(kù)文檔分享物理狀態(tài) E7FNULLB25A13C31D1頭指針 存儲(chǔ)地址 數(shù)據(jù)域 指針域 19 1713192531單鏈表存取:必須從頭指針開始進(jìn)行，依次順著指針向鏈尾方向掃描。找到各個(gè)元素,因此說(shuō)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)。ABCDEhead F 牛牛文庫(kù)文檔分享ABCDEhead FABCDEhead F帶頭節(jié)點(diǎn)的單鏈表編程：創(chuàng)建帶頭節(jié)點(diǎn)的單鏈表。程序算法：（1）定義三個(gè)結(jié)構(gòu)體類型的指針變量head, p, s（2）利用malloc函數(shù)開辟頭結(jié)點(diǎn)，由head, p共同來(lái)指向（3）再利用malloc函數(shù)開辟相應(yīng)的內(nèi)存空間，由s來(lái)

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

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

19、5）p-next=s;（6）p=s;（7）回到第（3）步;sp對(duì)帶頭結(jié)點(diǎn)的復(fù)雜鏈表的基本操作創(chuàng)建AsheadpB 牛牛文庫(kù)文檔分享ABCDEhead FABCDEhead F帶頭節(jié)點(diǎn)的單鏈表 typedef struct nodechar 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=(Linkl

20、ist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 編程：創(chuàng)建帶頭節(jié)點(diǎn)的單鏈表。 牛牛文庫(kù)文檔分享帶頭節(jié)點(diǎn)的單鏈表 typedef struct nodechar 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

21、()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 2000Bdatanext 牛牛文庫(kù)文檔分享 struct nodechar 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()

22、!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Aheadp用戶輸入為：ABCsptypedef 牛牛文庫(kù)文檔分享 struct nodechar 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=

23、getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Ahead用戶輸入為：ABCspsBptypedef 牛牛文庫(kù)文檔分享 struct nodechar 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

24、; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Ahead用戶輸入為：ABCsBpsCpNULLtypedef 牛牛文庫(kù)文檔分享鏈?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)的指針域的指針即可 牛牛文庫(kù)文檔分享插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp

25、 B C Xs A修改p指針域, 使其指向新結(jié)點(diǎn)s: pnexts考慮上述兩步驟若顛倒會(huì)怎樣？ 牛牛文庫(kù)文檔分享插入步驟修改s指針域,使其指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn):snext=pnextp B C Xs A修改p指針域, 使其指向新結(jié)點(diǎn)s: pnexts考慮上述兩步驟若顛倒會(huì)怎樣？后面的結(jié)點(diǎn)都將從鏈表中脫離它們占用著內(nèi)存空間，程序卻找不到它們了 牛牛文庫(kù)文檔分享鏈?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)的指針域即可 牛牛文庫(kù)文檔分享刪除步驟修改

26、q結(jié)點(diǎn)指針域 qnextpnextCpBA刪除前刪除后qpCBAfree(p);先找到p的前驅(qū)結(jié)點(diǎn)qqnextqnextnext 牛牛文庫(kù)文檔分享鏈?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)鏈表 牛牛文庫(kù)文檔分享優(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)鏈表 牛牛文庫(kù)文檔分享鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn):2.線性鏈表:1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.2 線性表3

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

28、.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插入前cbax待插入的結(jié)點(diǎn):q 牛牛文庫(kù)文檔分享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結(jié)點(diǎn)作為p結(jié)點(diǎn)的后繼:p-next=q； (p的后繼指向新結(jié)點(diǎn)q)確定新結(jié)點(diǎn)q的前驅(qū)和后繼 牛牛文庫(kù)文檔分享鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn):2.線性鏈表:1.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.2 線性表3 .單鏈表: 4.循環(huán)

29、鏈表5.雙向鏈表p刪除前cba(2)刪除結(jié)點(diǎn)：刪除P指針?biāo)附Y(jié)點(diǎn)，只需修改P指針的前驅(qū)和后繼結(jié)點(diǎn)的next，prior域即可。 牛牛文庫(kù)文檔分享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 牛牛文庫(kù)文檔分享習(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. 任意存取的

30、存儲(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) 牛牛文庫(kù)文檔分享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 牛牛文庫(kù)文檔分享5. 下列對(duì)于線性鏈表的描述中正確的是_。(05.4月 ）A）存

31、儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的B）存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C）存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D）存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的 牛牛文庫(kù)文檔分享6. 線性表是（） 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+1詳見計(jì)算機(jī)基礎(chǔ)綜合實(shí)訓(xùn)教程P1758. 一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1in

32、+1) 位置插入一個(gè)新元素時(shí)，需要從后面向前依次后移（ ）個(gè)元 素。 A. n-i B. n-i+1 C. n-i-1 D. i 牛牛文庫(kù)文檔分享9.設(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

33、-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 牛牛文庫(kù)文檔分享12.不帶頭結(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)鏈表中，

34、若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（）個(gè)指針域的值。A. 2 B. 3 C. 4 D.615.在一個(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ù)與否均可以 牛牛文庫(kù)文檔分享2.在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行一下操作： q=p-next; p-data= p-next-data; p

35、-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-nextpqABBC 牛牛文庫(kù)文檔分享3. 在一個(gè)單鏈表中指針p所指向結(jié)點(diǎn)的后面插入一個(gè)指針q所指向的結(jié)點(diǎn)時(shí)，首先把_ _的值賦給q-next，然后把_的值賦給p-next。p-nextq4.假定指向單鏈表中第一個(gè)結(jié)點(diǎn)的表頭指針為head，則向該單鏈 表的表頭插入指針p所指向的新結(jié)點(diǎn)時(shí)，首先執(zhí)行_賦值操 作，然后執(zhí)行_賦值操作。 p-next=headhead=pheadp 牛牛文庫(kù)文檔分享5. 在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把_的值賦給p-next指針域。p-next-next6. 在_鏈表中，既可以通過(guò)設(shè)定一個(gè)頭指針也可 以通過(guò)設(shè)定一個(gè)尾指針來(lái)確定它，即通過(guò)頭指針或 尾指針可以訪問到該鏈表中的每個(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