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

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

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

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

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

指示。其直接前驅(qū)結(jié)點的鏈域的值指針域(鏈域)鏈式存儲特點（續(xù)）頭結(jié)點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

建立結(jié)點并插入；a1a1a24）依次類推，直至輸入an為止。LLp↑L↑pfpf↑pf↑pf↑↑pfp↑21結(jié)點的結(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);//求每個結(jié)點占用的存儲空間

head=(LinkList)malloc(m);//為頭結(jié)點申請空間

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

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

pf=p；//移動pf指針到下一位置

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

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

LinkListhead;//頭指針head

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

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

GetElem(L,i,&e)

（取單鏈表L的第i個元素給變量e）*e=p->.data難點：單鏈表中想取得第i個元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機存取。在單鏈表中的實現(xiàn)為:(例如，i=3)26因此，查找第i個元素的基本操作為：

移動指針，比較j和i

。

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

指針p所指示的結(jié)點，有時也稱為p結(jié)點。程序?qū)崿F(xiàn)如下：單鏈表的讀?。ɡm(xù)）27

StatusGetElem_L(LinkListL,inti,ElemType&e){

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

}//GetElem_L算法時間復雜度為: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為指針移動的次數(shù)計數(shù)器順指針向后查，直到p指向第i個元素或p為空判斷第i個元素是否存在獲取第i個元素單鏈表的讀?。ㄋ惴▽崿F(xiàn)）LinkListp=L;int

j=0;

可以嗎？自己上機試試（當i=0時）結(jié)果對嗎？28單鏈表的讀?。ㄋ惴▽崿F(xiàn)）voidmain(){LinkListhead;//頭指針headchare='1';inti;

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

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

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

scanf("%d",&i);

while(i<1){

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

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

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

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

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

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

修改新結(jié)點及第i-1個結(jié)點的指針。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;}單鏈表的插入（算法實現(xiàn)）能互換么？要先找到第i-1個元素i大于表長或者小于1生成新結(jié)點LinkList

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

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

StatusListDelete_L(LinkListL,inti,ElemType&e){

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

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

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

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

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

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

3

511^

8

La頭結(jié)點

2

3

6

5

Lc

815

18^

2

611

8

Lb

915

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

5

8

11^

Lb2

6

8

119

PaPbPa、Pb用于搜索La和Lb，Pc指向新鏈表當前結(jié)點，新鏈表不開辟新的存儲空間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，歸并為LC后也按值排序

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

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

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

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