第2章線性表課件

關(guān)于結(jié)構(gòu)體類型與結(jié)構(gòu)體變量（1）結(jié)構(gòu)體類型與結(jié)構(gòu)體變量是兩個(gè)不同的概念，其區(qū)別如同int類型與int型變量的區(qū)別一樣。（2）結(jié)構(gòu)體類型中的成員名，可以與程序中的變量同名，它們代表不同的對(duì)象，互不干擾。1

如何訪問結(jié)構(gòu)體變量的成員?假設(shè)有結(jié)構(gòu)體變量var,指針變量pointer指向結(jié)構(gòu)變量var，則以下三種形式等價(jià)：

1）var.成員

2）pointer->成員

3）(*pointer).成員/*“*pointer”外面的括號(hào)不能?。?/注意：在格式（1）中，分量運(yùn)算符左側(cè)的運(yùn)算對(duì)象，只能是結(jié)構(gòu)體變量；而在格式（2）中，指向運(yùn)算符左側(cè)的運(yùn)算對(duì)象，只能是指向結(jié)構(gòu)體變量（或結(jié)構(gòu)體數(shù)組）的指針變量。2C語言動(dòng)態(tài)內(nèi)存分配(1)庫函數(shù)malloc()·用法：void*malloc(unsignedsize)·功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)分配１個(gè)長(zhǎng)度為

size的連續(xù)空間。·返回值：申請(qǐng)成功，則返回新分配內(nèi)存塊的起始地址；否則，返回NULL。·函數(shù)原型：malloc.h，stdlib.h。3malloc()函數(shù)的返回值是一個(gè)無類型指針，其特點(diǎn)是可以指向任何類型的數(shù)據(jù)。但在實(shí)際使用malloc()函數(shù)時(shí)，必須將其返回值強(qiáng)制轉(zhuǎn)換成被賦值指針變量的數(shù)據(jù)類型，以免出錯(cuò)。C語言動(dòng)態(tài)內(nèi)存分配4(2)運(yùn)算符sizeof·格式：sizeof(變量名／類型名)·功能：求變量／類型占用的內(nèi)存字節(jié)數(shù)（正整數(shù)）。例如，在IBM-PC機(jī)上，sizeof(int)=2。C語言動(dòng)態(tài)內(nèi)存分配5（3）庫函數(shù)free()·用法：voidfree(void*ptr)·功能：釋放由ptr指向的內(nèi)存塊（ptr是調(diào)用malloc()函數(shù)的返回值）?！し祷刂担簾o。·函數(shù)原型：stdlib.h，malloc.h。C語言動(dòng)態(tài)內(nèi)存分配6typedef語句typedef語句(類型說明語句)的功能是利用某個(gè)已有的數(shù)據(jù)類型定義一個(gè)新的數(shù)據(jù)類型。其格式為:

typedef數(shù)據(jù)類型名新數(shù)據(jù)類型名如：typedefintinteger;integeri,j;

7typedef語句例：typedefstruct

/*學(xué)生信息結(jié)構(gòu)體類型：由學(xué)號(hào)、姓名、性別和生日共4項(xiàng)組成*/{charno[7];charname[9];charsex[3];structdatebirthday;}

std_info;

其后的變量說明語句中可以省略結(jié)構(gòu)體類型說明符struct:std_infostudent;8線性結(jié)構(gòu)的定義：

若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。→可表示為：（a1,a2,……,an）

簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是

的。特點(diǎn)①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；特點(diǎn)②除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是------線性表一對(duì)一(1:1)9第2章線性表2.1線性表抽象數(shù)據(jù)類型2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)10（a0,a1,…ai-1，ai,ai＋1

，…,an-1）線性表的邏輯結(jié)構(gòu)：n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)。n≥0空表線性終點(diǎn)11

（A,B,C,D,……,Z）學(xué)號(hào)姓名性別年齡班級(jí)012019010622陳建武男192019級(jí)電信0301班012019010704趙玉鳳女182019級(jí)電信0302班012019010813王澤男192019級(jí)電信0303班012019010906薛荃男192019級(jí)電信0304班012019011018王春男192019級(jí)電信0305班：：：

：：例：分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：數(shù)據(jù)元素都是同類型（記錄），元素間關(guān)系是線性的。分析：數(shù)據(jù)元素都是同類型（字母），元素間關(guān)系是線性的。例：分析26個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。12線性表抽象數(shù)據(jù)類型

它包括兩個(gè)方面：數(shù)據(jù)集合：｛a0,a1,…,an-1｝ai的數(shù)據(jù)類型為DataType

操作集合：(1)ListInitiate(L)初始化線性表

(2)ListInsert(L,i,x)插入數(shù)據(jù)元素

(3)ListLength(L)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)

(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素

(5)ListGet(L,i,x)取數(shù)據(jù)元素13線性表的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu):它是使用一片地址連續(xù)的有限內(nèi)存單元空間存儲(chǔ)數(shù)據(jù)元素的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰。(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):它是把數(shù)據(jù)元素和指針定義成一個(gè)存儲(chǔ)體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針鏈接實(shí)現(xiàn)的。142.2線性表的順序表示和實(shí)現(xiàn)一、順序表的存儲(chǔ)結(jié)構(gòu)二、順序表的實(shí)現(xiàn)三、順序表的運(yùn)算效率分析152.2.1、順序表的存儲(chǔ)結(jié)構(gòu)表示

1、順序表：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。即采用順序存儲(chǔ)結(jié)構(gòu)的線性表。它通常采用靜態(tài)數(shù)組實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)?？梢岳脭?shù)組V[n]來實(shí)現(xiàn)注意：在C語言中數(shù)組的下標(biāo)是從0開始，即：

V[n]的有效范圍是從V[0]～V[n-1]16若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組V[n]的下標(biāo)）。設(shè)首元素a0的存放地址為L(zhǎng)OC(a0)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai

)=LOC(a0)+L*i對(duì)上述公式的解釋如圖所示2.2.1順序表的存儲(chǔ)結(jié)構(gòu)表示17a0a1……aiai+1……an-1

地址內(nèi)容元素在表中的位序0i1n-1空閑區(qū)i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖18設(shè)有一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是９８，則Ｍ[３]的第一個(gè)字節(jié)的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址計(jì)算通式為：LOC(ai)=LOC(a0)+L*i例:19用C語言描述：typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;

/*MaxSize表示數(shù)組的最大元素個(gè)數(shù)，list表示順序表的數(shù)組名，size表示順序表中當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，它必須滿足size≤MaxSize，SeqList是該結(jié)構(gòu)體的名字。*/2.2.2順序表的實(shí)現(xiàn)20順序表的操作(1)ListInitiate(L)初始化線性表

(2)ListInsert(L,i,x)插入數(shù)據(jù)元素

(3)ListLength(L)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)

(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素

(5)ListGet(L,i,x)取數(shù)據(jù)元素212.順序表操作的實(shí)現(xiàn)

（1）初始化ListInitiate(L)voidListInitiate(SeqList*L) {L->size=0; /*定義初始數(shù)據(jù)元素個(gè)數(shù)*/}

（2）求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)ListLength(L)intListLength(SeqListL) {returnL.size;}

22線性表操作

ListInsert(L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？23

(a0,…,ai-1,ai,…,an-1)改變?yōu)閍0a1

…ai-1ai

…an-1a0a1

…ai-1

…aiean-1<ai-1,ai><ai-1,e>,<e,ai>表的長(zhǎng)度增加(a0,…,ai-1,e,ai,…,an-1)24插入算法ListInsert(L,i,x)描述算法功能：在線性表（n個(gè)元素）的第i個(gè)位置前插入一個(gè)元素輸入：順序表輸出：插入元素后的順序表1.判斷表是否滿，如果滿則顯示提示信息2.判斷插入的位置i是否合法(n>i>=0)，如果不合法，則顯示錯(cuò)誤信息3.將第n-1至第i

位的元素向后移動(dòng)一個(gè)位置4.將要插入的元素寫到第i個(gè)位置；5.表長(zhǎng)加1。25（3）插入數(shù)據(jù)元素ListInsert(L,i,x)關(guān)鍵代碼

intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*依次后移*/

L->list[i]=x; /*插入x*/ L->size++; /*元素個(gè)數(shù)加1*/ return1;}26線性表操作

ListDelete(L,i,e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？27

(a0,…,ai-1,ai,ai+1,…,an-1)改變?yōu)閍i+1…an-1<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長(zhǎng)度減少a0a1

…ai-1ai

ai+1

…

an-1a0a1

…ai-1

(a0,…,ai-1,ai+1,…,an-1)28刪除算法ListDelete(L,i,x)描述算法功能：刪除線性表（n個(gè)元素）的第i個(gè)位置上的元素輸入：順序表輸出：刪除的元素1.判斷刪除的位置i是否合法(n-1>i>=0)，如果不合法，則顯示錯(cuò)誤信息2.將第i+1至第n-1位的元素向前移動(dòng)一個(gè)位置；3.表長(zhǎng)減1。29（4）刪除數(shù)據(jù)元素ListDelete(L,i,x)關(guān)鍵代碼intListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i];/*保存刪除的元素到x中*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];/*依次前移*/

L->size--; /*數(shù)據(jù)元素個(gè)數(shù)減1*/

return1;}30查找元素算法ListGet(L,i,x)描述算法功能：查找線性表（n個(gè)元素）的第i個(gè)位置上的元素輸入：順序表輸出：查找到的元素1.判斷查找的位置i是否合法(n-1>i>=0)，如果不合法，則顯示錯(cuò)誤信息2.直接取出第i個(gè)位置的元素31（5）取數(shù)據(jù)元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數(shù)i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}32例2-1：建立一個(gè)線性表，先依次輸入數(shù)據(jù)元素1，2，3，4，…，10，然后刪除５，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性的數(shù)據(jù)元素個(gè)數(shù)最壞情況下不會(huì)超過100個(gè)。

33實(shí)現(xiàn)方法：

1、采用直接編寫一個(gè)主函數(shù)實(shí)現(xiàn)。

2、利用已設(shè)計(jì)實(shí)現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h的文件中，通過#include“SeqList.h”

）程序設(shè)計(jì)如下：#include<stdio.h> #defineMaxSize100 typedefintDataType;#include"SeqList.h"

34voidmain(void){SeqListmyList;inti,x;

ListInitiate(&myList);for(i=0;i<10;i++)

ListInsert(&myList,i,i+1);

ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i++){ListGet(myList,i,&x);printf(“%d”,x);}}程序運(yùn)行結(jié)果：1234678910351.頭文件分為系統(tǒng)頭文件自定義頭文件2.頭文件的處理：先把被包含的文件內(nèi)容復(fù)制到引用頭文件的語句處，形成一個(gè)新的源程序，再編譯成一個(gè)目標(biāo)文件。C語言頭文件362.2.3順序表操作的效率分析算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度）

T(n)=O(移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。時(shí)間效率分析:37推導(dǎo)：假定在每個(gè)元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來計(jì)算平均執(zhí)行時(shí)間：將所有位置的執(zhí)行時(shí)間相加，然后取平均。若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移n次；若在a1后面插入，要后移n-1個(gè)元素，后移次數(shù)為n-1;……若在an-1后面插入，要后移1個(gè)元素；若在尾結(jié)點(diǎn)an之后插入，則后移0個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì)：0+1+…+n=n(n+1)/2

故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少種插入形式?——連頭帶尾有n+1種!38

順序表中的其余操作都和數(shù)據(jù)元素個(gè)數(shù)n無關(guān)，因此，在順序表中插入和刪除一個(gè)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(n),其余操作的時(shí)間復(fù)雜度都為O(1)主要優(yōu)點(diǎn)是算法簡(jiǎn)單，空間單元利用率高；主要缺點(diǎn)是需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。主要優(yōu)缺點(diǎn)39思考題P22頁，刪除算法的效率Edl是如何計(jì)算出來的？402.5算法設(shè)計(jì)舉例例2-4設(shè)計(jì)一個(gè)順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元素x刪除。算法思想：首先，找到要?jiǎng)h除元素的位置，然后，從這個(gè)位置到最后一個(gè)元素，逐個(gè)前移，最后，把元素個(gè)數(shù)減1。41intListDataDelete(SeqList*L,DataTypex){inti,j;for(i=0;i<L->size;i++) if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++) L->list[j]=L->list[j+1];

L->size--; return1;}}

42算法練習(xí)題1.編寫算法實(shí)現(xiàn)順序表的逆置，要求把順序表A中的數(shù)據(jù)元素序列（a0,a1,a2,…..an-1）逆置為（an-1,…..a2,a1,a0），并存儲(chǔ)到順序表B中。43算法練習(xí)題2.編寫算法實(shí)現(xiàn)順序表的就地逆置，把數(shù)據(jù)元素序列（a0,a1,a2,…..an-1）逆置為（an-1,…..a2,a1,a0）。442.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、單鏈表的存儲(chǔ)結(jié)構(gòu)二、單鏈表的操作實(shí)現(xiàn)三、鏈表的運(yùn)算效率分析45１、單鏈?zhǔn)郊氨硎痉椒?1)單鏈表:構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針。其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針域數(shù)據(jù)域nextdata或樣式：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率一、單鏈表的存儲(chǔ)結(jié)構(gòu)46例：請(qǐng)畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和

。討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由

指示。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)47

線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下圖所示。其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例：481）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……循環(huán)鏈表示意圖：head(2)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：494）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a０的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。示意圖如下：50答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長(zhǎng)度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；^頭指針無頭結(jié)點(diǎn)^頭指針頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！51一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31２、帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較例：52上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！53對(duì)比帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程和不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程，可以得知：

●若設(shè)計(jì)的單鏈表帶頭結(jié)點(diǎn)，則無論是在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入都不會(huì)改變頭指針的數(shù)值。

●若設(shè)計(jì)的單鏈表不帶頭結(jié)點(diǎn)，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入其算法的處理方法不同。

●在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。

因此，單鏈表一般構(gòu)造成帶頭結(jié)點(diǎn)的單鏈表。54討論:鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型指針型設(shè)每個(gè)結(jié)點(diǎn)用變量node表示，其指針用p表示，兩個(gè)分量分別用data和*next表示，以下兩個(gè)分量賦值方法是否正確？p*nextdatanode方式1：直接表示為

node.data＝'a'；node.next=q方式2：p指向結(jié)點(diǎn)首地址，然后p->data='a';p->next=q;方式3：p指向結(jié)點(diǎn)首地址，然后(*p).data='a'；(*p).next＝q‘a(chǎn)’‘b’qp55sizeof(x)——計(jì)算x的長(zhǎng)度malloc(m)—開m字節(jié)空間free(p)——?jiǎng)h除一個(gè)變量問1：自定義結(jié)構(gòu)類型變量node的長(zhǎng)度m是多少？問2：結(jié)構(gòu)變量node的首地址(指針p）是多少？問3：怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長(zhǎng)度為m字節(jié)pm＝sizeof(node)//單位是字節(jié)p＝(node*)malloc(m)free(p)//只能借助node的指針刪除！56②對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：

SLNode*p,*q;//或用

structNode*p,*q;//注：上面已經(jīng)定義了SLNode為用戶自定義的Node類型。①類型定義可以寫為：typedefstructNode//Node是自定義結(jié)構(gòu)類型名稱{DataTypedata;//定義數(shù)據(jù)域的變量名及其類型

structNode*next;//定義指針域的變量名及其類型}SLNode，*p;//SLNode是Node結(jié)構(gòu)類型的類型替代,

*p是指針型的Node結(jié)構(gòu)類型的替代

此結(jié)構(gòu)數(shù)據(jù)類型的C表示法57單鏈表基本操作1.初始化2.求單鏈表中元素個(gè)數(shù)3.插入元素4.刪除元素5.取數(shù)據(jù)元素6.撤消單鏈表二、單鏈表的操作實(shí)現(xiàn)58１、初始化voidListInitiate(SLNode**head)／*初始化*/{ /*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/

*head=(SLNode)malloc(sizeof(SLNode));(*head)->next=NULL; }59２、求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)

intListLength(SLNode*head)

{

SLNode*p=head;

/*p指向頭結(jié)點(diǎn)*/

intsize=0;

/*size初始為0*/

while(p->next!=NULL)/*循環(huán)計(jì)數(shù)*/

{

p=p->next;

size++;

}

returnsize;

}60在鏈表中插入一個(gè)元素X的示意圖如下：Xqabp鏈表插入的核心語句：Step1：q->next=p->next;Step2：p->next=q；p->nextq->next思考：Step1和2能互換么？X結(jié)點(diǎn)的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向單鏈表中插入一個(gè)元素61intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q; intj; p=head; j=-1;(1)while(p->next!=NULL&&j<i-1){ p=p->next;j++; }

if(j!=i-1){ printf("插入位置參數(shù)錯(cuò)！"); return0;}(2)

q=(SLNode*)malloc(sizeof(SLNode)); q->data=x;q->next=p->next;

p->next=q;(4) return1;}

注：此單鏈表是帶頭結(jié)點(diǎn)的62在鏈表中刪除某元素b的示意圖如下：cabp刪除動(dòng)作的核心語句（可以借助輔助指針變量s）：s=p->next;//首先保存b的指針，靠它才能找到c；p->next=s->next;

//將a、c兩結(jié)點(diǎn)相連，淘汰b結(jié)點(diǎn)；free(s)；//徹底釋放b結(jié)點(diǎn)空間p->next思考：省略free(s)語句行不行？(p->next)->next××s４、從單鏈表中刪除一個(gè)元素63intListDelete(SLNode*head,inti,DataType*x)

{ SLNode*p,*s; intj;(1)p=head;

j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)

{

p=p->next; j++; }

if(j!=i-1) {

printf(“插入位置參數(shù)錯(cuò)！”);

return0; }(2)

s=p->next;*x=s->data;(3)

p->next=s->next;

free(s);

return1;

} 645.取數(shù)據(jù)元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;

p=head;j=-1;

while(p->next!=NULL&&j<i){p=p->next; j++; }

if(j!=i){printf(“取元素位置參數(shù)錯(cuò)！”); return0;}

*x=p->data;return1;}

65（6）撤消單鏈表Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}66三、單鏈表的操作效率分析（1）查找

因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為

O(n)。時(shí)間效率分析（2）插入和刪除

因線性鏈表不需要移動(dòng)元素，只要修改指針，僅就插入或刪除而言，時(shí)間復(fù)雜度為

O(1)。但是，如果要在單鏈表中進(jìn)行在某結(jié)點(diǎn)前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所以一般情況下，單鏈表插入和刪除操作的時(shí)間復(fù)雜度是O(n)（同順序表）。67單鏈表操作的效率分析（P34頁）單鏈表的插入和刪除操作不需移動(dòng)數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個(gè)數(shù)操作的時(shí)間復(fù)雜度為O(n)。68和順序表相比主要優(yōu)點(diǎn)是不需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除操作不需要移動(dòng)數(shù)據(jù)元素；主要缺點(diǎn)是查找數(shù)據(jù)元素時(shí)需要順序進(jìn)行，不能像順序表那樣隨機(jī)查找任意一個(gè)數(shù)據(jù)元素。另外，每個(gè)結(jié)點(diǎn)中要有一個(gè)指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復(fù)雜。單鏈表和順序表相比，單鏈表的優(yōu)點(diǎn)和缺點(diǎn)正好相反。69四、應(yīng)用舉例例2-3編程實(shí)現(xiàn)：建立一個(gè)單鏈表，首先依次輸入數(shù)據(jù)元素１,２,…,10，然后刪除數(shù)據(jù)元素５，最后依次顯示當(dāng)前表中的數(shù)據(jù)元素。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintDataType; #include"LinList.h"重點(diǎn)是鏈表70

voidmain(void){SLNode*head;inti,x;

ListInitiate(&head);

for(i=0;i<10;i++)

ListInsert(head,i,i+1);

ListDelete(head,4,&x);

for(i=0;i<ListLength(head);i++){ListGet(head,i,&x); printf(“%d”,x); }

Destroy(&head);}程序運(yùn)行結(jié)果：123467891071

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表a1a2…...an1.循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。五、其它形式的鏈表72

2.雙向鏈表a1a2…...an^^73雙向循環(huán)鏈表空表非空表a1a2…...an74（１）雙向循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu)雙向循環(huán)鏈表：鏈表中每個(gè)結(jié)點(diǎn)除后繼指針域和數(shù)據(jù)域外還有一個(gè)前驅(qū)指針域。其結(jié)點(diǎn)的結(jié)構(gòu)為：雙向鏈表結(jié)點(diǎn)的結(jié)構(gòu)體定義如下：

typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;priordatanext75（2）雙向鏈表的操作實(shí)現(xiàn)(1)前插設(shè)p已指向第i元素，請(qǐng)?jiān)诘趇元素前插入元素xx

sai-1

ai

p指針域的變化：①ai-1的后繼從ai(指針是p)變?yōu)閤（指針是s):s->next=p;

p->prior->next=s;

②ai的前驅(qū)從ai-1(指針是p->prior)變?yōu)閤(指針是s);

s->prior=p->prior;p->prior=s;76

p指針域的變化：

后繼方向：ai-1的后繼由ai(指針p)變?yōu)閍i+1(指針p->next

);p->prior->next

=

p->next;

前驅(qū)方向：ai+1的前驅(qū)由ai(指針p)變?yōu)閍i-1(指針p->prior);p->next->prior

=p->prior;(2)雙向鏈表的刪除操作設(shè)p指向第i個(gè)元素，刪除第i個(gè)元素ai-1

ai

ai+1

772.4靜態(tài)鏈表靜態(tài)鏈表：在數(shù)組中增加一個(gè)（或兩個(gè)）指針域，這些指針域用來存放下一個(gè)（或上一個(gè)）數(shù)據(jù)元素在數(shù)組中的下標(biāo)，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表（或雙鏈表）。靜態(tài)鏈表中的指針又稱仿真指針。78例：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur說明1：假設(shè)S為SLinkList型變量，則S[MAXSIZE]

為一個(gè)靜態(tài)鏈表；S[0].next則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。說明2：如果數(shù)組的第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則：S[i].data表示第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；S[i].next

表示第k+1個(gè)結(jié)點(diǎn)(即k的直接后繼)的位置。i頭結(jié)點(diǎn)79例2-6設(shè)頭指針為head，并設(shè)帶頭結(jié)點(diǎn)單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點(diǎn)單鏈表的適當(dāng)位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。算法思想：從鏈表的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)開始，逐個(gè)比較每個(gè)結(jié)點(diǎn)的data域值和x的值，當(dāng)data小于等于x時(shí)，進(jìn)行下一個(gè)結(jié)點(diǎn)的比較；否則就找到了插入結(jié)點(diǎn)的合適位置，此時(shí)申請(qǐng)新結(jié)點(diǎn)把x存入，然后把新結(jié)點(diǎn)插入；當(dāng)比較到最后一個(gè)結(jié)點(diǎn)仍有data小于等于x時(shí)，則把新結(jié)點(diǎn)插入單鏈表尾。2.5算法設(shè)計(jì)舉例80voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;

curr=head->next;pre=head;

while(curr!=NULL&&curr->data<=x){pre=curr; curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;

q->next=pre->next;pre->next=q;}81算法設(shè)計(jì)說明：（1）在循環(huán)定位插入位置時(shí)，循環(huán)條件必須首先是curr!=NULL，然后是curr->data<=x。如果次序顛倒，則當(dāng)curr為空（即等于鏈表結(jié)束標(biāo)記NULL）時(shí),將因?yàn)閏urr->data不存在而出錯(cuò)；次序不顛倒時(shí)，當(dāng)curr等于NULL時(shí)將退出循環(huán)，不會(huì)進(jìn)行后邊條件curr->data<=x的比較。（2）當(dāng)比較到最后一個(gè)結(jié)點(diǎn)仍有data小于等于x時(shí)，此時(shí)有pre指向最后一個(gè)結(jié)點(diǎn)，curr等于NULL，則上述算法把新結(jié)點(diǎn)插入