數(shù)據(jù)結(jié)構(gòu)線性表

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)1第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4應(yīng)用舉例

作業(yè)2上堂課要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或1:1存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除3.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快O(1)缺點(diǎn)：插入、刪除慢O(n)32.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析本節(jié)小結(jié)作業(yè)42.3.1鏈表的表示鏈?zhǔn)酱鎯?chǔ)特點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)補(bǔ)充：結(jié)構(gòu)數(shù)據(jù)類型及其C語(yǔ)言表示法5用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素，即邏輯上相鄰，物理上不一定相鄰鏈?zhǔn)酱鎯?chǔ)特點(diǎn)如何表示ai與ai+1之間的邏輯關(guān)系？通過(guò)指針來(lái)實(shí)現(xiàn)結(jié)點(diǎn)：鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：數(shù)據(jù)域(data)指針域(link)數(shù)據(jù)元素的映象以“結(jié)點(diǎn)的序列”表示線性表

稱作鏈表。指示后繼元素存儲(chǔ)位置6鏈表示意圖：討論1：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和

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

指示。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)鏈?zhǔn)酱鎯?chǔ)特點(diǎn)（續(xù)）頭結(jié)點(diǎn)

a1a2…...an^例2-3-1畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）72.與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)1）結(jié)點(diǎn)2）鏈表3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)a1heada2an……循環(huán)鏈表示意圖：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。8何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)頭結(jié)點(diǎn)頭指針表尾空指針

a1a2…...an^頭指針是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。

是指鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。單鏈表可由一個(gè)頭指針唯一確定。有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)前加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;9一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例2-3-2答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是3110鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無(wú)頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)例2-3-2（續(xù)）11答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。^頭指針無(wú)頭結(jié)點(diǎn)^頭指針頭結(jié)點(diǎn)有頭結(jié)點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)（續(xù)）12與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)（續(xù)）頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。答：討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書寫表達(dá)？

——補(bǔ)充C語(yǔ)言內(nèi)容

H頭結(jié)點(diǎn)的數(shù)據(jù)域討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？133.補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型及其C語(yǔ)言表示法①類型定義和變量說(shuō)明可以合寫為：typedef

structNode{//Node是自定義結(jié)構(gòu)類型名稱chardata;//定義數(shù)據(jù)域的變量名及其類型structNode*next;//定義指針域的變量名及其類型}LNode,*LinkList;//LNode是結(jié)構(gòu)類型的類型名,

//LinkList是指向LNode結(jié)構(gòu)類型的指針類型的類型名以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型指針型假設(shè)每個(gè)結(jié)點(diǎn)用變量lNode表示，其中兩個(gè)分量分別用data和*next表示，則：*nextdatalNode14補(bǔ)充：結(jié)構(gòu)類型的C語(yǔ)言表示法②用LNode或LinkList類型聲明指向結(jié)點(diǎn)的指針變量：

LNode*p,*q;或LinkListp，q；

③每個(gè)結(jié)點(diǎn)的分量如何表示？*nextdatalnodep方式1：直接用

lnode.data＝'a'；lnode.next=q方式2：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：

p->data='a';p->next=q;方式3：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：

(*p).data='a'；(*p).next＝q15設(shè)p為指向鏈表的第i個(gè)元素的指針,則第i個(gè)元素的數(shù)據(jù)域?qū)憺?/p>

，指針域?qū)憺?/p>

。p->dataai的值p->nextai+1的地址練習(xí)16補(bǔ)充：結(jié)構(gòu)類型的C語(yǔ)言表示法（續(xù)）④介紹三個(gè)有用的庫(kù)函數(shù)（都在<stdlib.h>中）：sizeof(x)——計(jì)算變量x的長(zhǎng)度；malloc(m)—開辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；

free(p)——釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。問(wèn)1：LNode結(jié)構(gòu)類型變量的長(zhǎng)度m是多少？問(wèn)2：結(jié)構(gòu)變量lnode的首地址(指針p）是多少？問(wèn)3：怎樣刪除結(jié)構(gòu)變量lnode？只能借助其指針刪除！m＝sizeof(LNode)；p＝(LNode*)malloc(m)；或p＝(LinkList)malloc(m)；free(p)；172.3.2鏈表的實(shí)現(xiàn)1.單鏈表的建立和輸出2.單鏈表的修改3.單鏈表的插入4.單鏈表的刪除5.應(yīng)用舉例6.其它鏈表形式181.單鏈表的建立和輸出實(shí)例：用單鏈表結(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，…，z），請(qǐng)寫出C語(yǔ)言程序。難點(diǎn)分析：每個(gè)數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)數(shù)據(jù)元素開辟存儲(chǔ)空間并賦值，并及時(shí)將地址送給前面的指針。19逆位序輸入數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表操作步驟：1）建立一個(gè)“空表”；2）輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；3）輸入數(shù)據(jù)元素an-1，

建立結(jié)點(diǎn)并插入；ananan-14）依次類推，直至輸入a1為止。20順序輸入數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表操作步驟：1）建立一個(gè)“空表”；2）輸入數(shù)據(jù)元素a1，建立結(jié)點(diǎn)并插入；3）輸入數(shù)據(jù)元素a2，

建立結(jié)點(diǎn)并插入；a1a1a24）依次類推，直至輸入an為止。LLp↑L↑pfpf↑pf↑pf↑↑pfp↑21結(jié)點(diǎn)的結(jié)構(gòu)體類型定義#include<stdio.h>#include<stdlib.h>typedef

struct

LNode{chardata;

struct

LNode*next;}LNode，*LinkList;22鏈表的生成（順序輸入數(shù)據(jù)元素的值）{inti=26;

LinkListpf,p;

intm=sizeof(LNode);//求每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間

head=(LinkList)malloc(m);//為頭結(jié)點(diǎn)申請(qǐng)空間

head->next=NULL;pf=head;while(i){p=(LNode*)malloc(m);//為新結(jié)點(diǎn)開新空間！

p->data=26-i+‘a(chǎn)’;//第一個(gè)結(jié)點(diǎn)值為字符ap->next=pf->next;pf->next=p;//插入到表尾

pf=p；//移動(dòng)pf指針到下一位置

i--;}}voidbuild(LinkList&head)23鏈表的輸出voiddisplay(LinkListhead){LinkListp;p=head->next;//p指向首元結(jié)點(diǎn)while(p){

printf("%c",p->data);p=p->next;}}討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？sum++;intsum=0;printf("元素個(gè)數(shù)：%d\n",sum);24voidmain(){

LinkListhead;//頭指針head

build(&head);//建立字母鏈表

display(head);//輸出字母鏈表}252.單鏈表的修改(或讀?。㎜211830754256∧pppj123取元素操作

GetElem(L,i,&e)

（取單鏈表L的第i個(gè)元素給變量e）*e=p->.data難點(diǎn)：?jiǎn)捂湵碇邢肴〉玫趇個(gè)元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機(jī)存取。在單鏈表中的實(shí)現(xiàn)為:(例如，i=3)26因此，查找第i個(gè)元素的基本操作為：

移動(dòng)指針，比較j和i

。

指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素，其中j為指針移動(dòng)的次數(shù)計(jì)數(shù)器。

指針p所指示的結(jié)點(diǎn)，有時(shí)也稱為p結(jié)點(diǎn)。程序?qū)崿F(xiàn)如下：?jiǎn)捂湵淼淖x取（續(xù)）27

StatusGetElem_L(LinkListL,inti,ElemType&e){

//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素

}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;j為指針移動(dòng)的次數(shù)計(jì)數(shù)器順指針向后查，直到p指向第i個(gè)元素或p為空判斷第i個(gè)元素是否存在獲取第i個(gè)元素單鏈表的讀?。ㄋ惴▽?shí)現(xiàn)）LinkListp=L;int

j=0;

可以嗎？自己上機(jī)試試（當(dāng)i=0時(shí)）結(jié)果對(duì)嗎？28單鏈表的讀取（算法實(shí)現(xiàn)）voidmain(){LinkListhead;//頭指針headchare='1';inti;

build(&head);//建立字母鏈表

display(head);//輸出字母鏈表

printf(“\n輸入要讀取第幾個(gè)數(shù)據(jù)元素:");

scanf("%d",&i);

while(i<1){

printf(“\nI的值必須大于0,請(qǐng)重新輸入:");

scanf("%d",&i);}

if(GetElem_L(head,i,&e))

printf("第%d個(gè)元素是：%c\n",i,e);else

printf("\n%dislargerthanthelistlength\n",i);}293.單鏈表的插入在鏈表中插入一個(gè)元素的示意圖如下：xsbapabpp->nexts->next在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入新元素的基本操作為:

找到線性表中第i-1個(gè)結(jié)點(diǎn)；生成要插入的新元素結(jié)點(diǎn);

修改新結(jié)點(diǎn)及第i-1個(gè)結(jié)點(diǎn)的指針。ii-1ii-1i+130StatusListInsert_L(LinkListL,inti,ElemTypee){LinkLists,p=L;intj=0;

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

if(!p||j>i)returnERROR;s=(LinkList)malloc(m);s->data=e;

s->next=p->next;p->next=s；

returnOK;}單鏈表的插入（算法實(shí)現(xiàn)）能互換么？要先找到第i-1個(gè)元素i大于表長(zhǎng)或者小于1生成新結(jié)點(diǎn)LinkList

s,p=L->next;intj=1;思考：可以這樣做嗎？為什么？不可以，因?yàn)楫?dāng)i=1時(shí)，插入的新元素放在了原來(lái)首元素后面314.單鏈表的刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語(yǔ)句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點(diǎn)相連free(q)；

//刪除b結(jié)點(diǎn)，徹底釋放p->next思考：省略free(q)語(yǔ)句行不行？(q->next)××基本操作為：找到第i-1個(gè)存在直接后繼的結(jié)點(diǎn)修改其指向后繼的指針，釋放被刪元素的空間。q32單鏈表的刪除（算法實(shí)現(xiàn)）

StatusListDelete_L(LinkListL,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i-1個(gè)結(jié)點(diǎn)，并令p指向它if(!(p->next)||j>i-1)returnERROR;

//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結(jié)點(diǎn)e=q->data;

free(q);returnOK;335.應(yīng)用舉例：兩個(gè)鏈表的歸并（教材P31）算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列。要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表LC存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測(cè)：合并后C=（2,3,5,6,8,8,9,11，11）34兩個(gè)鏈表的歸并（續(xù)）

3

511^

8

La頭結(jié)點(diǎn)

2

3

6

5

Lc

815

18^

2

611

8

Lb

915

18^用鏈表可表示為：35兩個(gè)鏈表的歸并（算法分析）算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。36PbPcPaLa3

5

8

11^

Lb2

6

8

119

PaPbPa、Pb用于搜索La和Lb，Pc指向新鏈表當(dāng)前結(jié)點(diǎn)，新鏈表不開辟新的存儲(chǔ)空間LcPc2

PcPaPbPcPcPcPcPaPcPbPcPbPa3

5

8

6

8

9

15

11

18^11

15

18^Pa->data>Pb->data:Pc->next=Pb;Pb=Pb->next;Pa->data<=Pb->data:Pc->next=Pa;Pa=Pa->next;Pc=Pb;Pa=NULL:Pc=Pa;Pc->next=Pb;若Pb=NULL:Pc->next=?Pa37VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//按值排序的單鏈表LA,LB，歸并為L(zhǎng)C后也按值排序

free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa?pa:pb;//插入剩余段

while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入C中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb