課件參考-1第9章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

能夠?yàn)閿?shù)據(jù)對(duì)象動(dòng)態(tài)分配和釋放內(nèi)存能夠用指針、自引用結(jié)構(gòu)構(gòu)造鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)能夠建立和操作鏈表理解鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的應(yīng)用第九章

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

能夠?yàn)閿?shù)據(jù)對(duì)象動(dòng)態(tài)分配和釋放內(nèi)存能夠用指針、自引用結(jié)構(gòu)構(gòu)造鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)能夠建立和操作鏈表理解鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的應(yīng)用第九章

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2022/12/133數(shù)據(jù)結(jié)構(gòu)的基本概念

程序=數(shù)據(jù)結(jié)構(gòu)+算法（著名的計(jì)算機(jī)科學(xué)家wirth(沃思）提出的表達(dá)程序設(shè)計(jì)實(shí)質(zhì)的公式）2022/12/134例1:

英文26個(gè)字母表的數(shù)據(jù)結(jié)構(gòu)是一個(gè)線形表，可表示為:B={D,R}D={a,b,c,·······

，x,y,z}R={(a,b),(b,c),……，(y,z)}

此例數(shù)據(jù)元素是簡單項(xiàng)。學(xué)號(hào)姓名成績9861109張卓1009861107劉忠賞959861103胡孝臣86例2:

學(xué)生成績表（復(fù)雜的線性表）數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成，如每個(gè)學(xué)生的情況，稱為記錄（Record）；由多個(gè)記錄組成的線性表稱為文件（File).2022/12/135樹形結(jié)構(gòu)例子——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGAHGFECDBA例2計(jì)算機(jī)中的目錄結(jié)構(gòu)問題樹2022/12/1361423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

圖形結(jié)構(gòu)例子——結(jié)點(diǎn)間的連結(jié)是任意的例3

交通、道路問題的數(shù)學(xué)模型圖通過上述例子可以看出：描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和操作的學(xué)科。2022/12/137提示：在計(jì)算機(jī)專業(yè)的后續(xù)課程中，數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，請(qǐng)參看“數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC＋＋語言描述）（殷人昆主編）”2022/12/138數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)問題（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)之間的邏輯關(guān)系。三種基本結(jié)構(gòu):線性結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在著線性(一對(duì)一)的關(guān)系.樹形結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在著層次(一對(duì)多)的關(guān)系.圖形結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在著任意(多對(duì)多)的關(guān)系.（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方式。

（3）數(shù)據(jù)的操作：數(shù)據(jù)的操作即是對(duì)數(shù)據(jù)進(jìn)行的處理。

2022/12/1391.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3.數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面反映數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)部的組織方式一種邏輯結(jié)構(gòu)可以采取不同的存儲(chǔ)方式，但必須都反映出要求的邏輯關(guān)系。2022/12/1310元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)把線性表中數(shù)據(jù)元素依次存放到一組連續(xù)的存儲(chǔ)單元中。2022/12/13111536元素21400元素11346元素3∧元素41345存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h2022/12/1312線性表（Linear_List)1線性表的定義

線性表是n個(gè)元素的有限序列，是最常用最簡單的數(shù)據(jù)結(jié)構(gòu)，長度可增長或縮短。它們之間的關(guān)系可以排成一個(gè)線性序列：

a1，a2，...，ai，...，an線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼在線性表上常用的運(yùn)算有：初始化、求長度、取元素、定位、插入及刪除等。線性表中的數(shù)據(jù)元素是各種各樣的，同一線性表中的元素必定具有相同的特性，即屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。2022/12/13132線性表的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算1）線性表的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：把線性表中數(shù)據(jù)元素依次存放到一組連續(xù)的存儲(chǔ)單元中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)存儲(chǔ)單元。線性表中數(shù)據(jù)元素類型一致，占用相同大小的存儲(chǔ)單元。存儲(chǔ)空間利用率高。做插入、刪除時(shí)需移動(dòng)大量元素。空間估計(jì)不明時(shí)，按最大空間分配。2022/12/1314元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址內(nèi)存狀態(tài)Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)結(jié)構(gòu)示意圖：2022/12/1315元素1元素2……..元素i……..01i

線性表的順序存儲(chǔ)結(jié)構(gòu)——可用C語言中的一維數(shù)組來描述.#defineM100/*定義M為常數(shù)100，M的值作為數(shù)組的最大容量*/。

intV[M];/*V是數(shù)組的名字，假設(shè)數(shù)組中的元素是整型類型*/第i個(gè)元素的ai存儲(chǔ)地址：Loc(ai)=Loc(a1)+(i-1)*mV[０]V[１]V[i]V[m-1]2022/12/1316…..a2a1an…..ai+1ai01i-1in-1

（1）順序表的插入運(yùn)算

在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ai-1…..a2a1alength…ai+1aixai-1…..a2a1

aiai+1…alength

alength……ai+1aix2022/12/1317

順序表的插入算法：intinsq(inti，intx,intV[],intM,int*p）{/*在線性表V中第i個(gè)元素之前插入x，i的合法值為1in*/intn,j;n=*p;/*獲取表長*/if（n==M)/*M是存儲(chǔ)空間的大小，p是指向存儲(chǔ)表長的指針變量*/{printf("overflow\n");return(0);}if((i<1)||(i>n+1)){printf("iiserror\n");return(0);}/*i值不合法*/else{for(j=n;j>=i;j--)V[j]=V[j-1];/*插入位置后的元素依次右移*/V[j]=x;/*插入x*/p=++n;/*表長加1,由p返回到函數(shù)調(diào)用處*/return(1);}}2022/12/1318voidmain(){intM=10,n=4;/*M是數(shù)組的大小,n是表中元素個(gè)數(shù),即表長*/intresult,k;staticintV[10]={3,5,7,10};/*數(shù)組賦初值*/result=insq(2,4,V,M,&n);/*執(zhí)行函數(shù)調(diào)用,在第2個(gè)元素前插入4*/if(result==1){printf("success!\n");for(k=0;k<n;k++)printf("%d",V[k]);}elseprintf("failure!");}

運(yùn)行結(jié)果:success!3457102022/12/1319（2）順序表的刪除運(yùn)算intdelsq(inti,intV[],int*p）{/*在線性表V中刪除第i個(gè)元素*/intn,j;n=*p;if（i<1||i>n）

{printf("Thiselementisnotinthelist\n");return(0);}else{for(j=i;j<n;j++)V[j-1]=V[j];/*被刪除元素之后的元素左移*/*p=--n;/*表長減1*/return(1);}}算法評(píng)價(jià)：在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低。T(n)=O(n)2）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)－－鏈表（1）自引用結(jié)構(gòu)：typedefstructLNode{intdata;structLNode*link;}NODE;NODE*p;datalinkP(*p)

表示p所指向的結(jié)點(diǎn)(*p).data

p->data

表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).link

p->link

表示p指向結(jié)點(diǎn)的指針域（2）動(dòng)態(tài)內(nèi)存分配：使用函數(shù)： malloc free sizeof（1）生成一個(gè)NODE型新結(jié)點(diǎn)： p=(NODE*)malloc(sizeof(NODE));注意：在使用mallo時(shí)，最好測試返回值是否是NULL指針，如果沒有分配到所請(qǐng)求的內(nèi)存時(shí)，打印出錯(cuò)誤信息。（2）系統(tǒng)回收p結(jié)點(diǎn)： free(p)2022/12/1322（3）鏈表結(jié)構(gòu)定義：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。結(jié)點(diǎn)

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭仗攸c(diǎn)：插入、刪除靈活方便，不需要移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。適合于線性表是動(dòng)態(tài)變化的,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時(shí)使用。

鏈表的查找只能從頭指針開始順序查找。（4）鏈表的基本運(yùn)算a)建立鏈表

動(dòng)態(tài)建立如下鏈表的思想:2022/12/1323ha1a2頭結(jié)點(diǎn)an^…...0尾插法創(chuàng)建鏈表創(chuàng)建頭結(jié)點(diǎn)，讓頭指針head和尾指針tail都指向該結(jié)點(diǎn)，設(shè)置該結(jié)點(diǎn)的指針域?yàn)镹ULL；head=(NODE*)malloc(sizeof(NODE));head->next=NULL;tail=head；②為實(shí)際數(shù)據(jù)創(chuàng)建一個(gè)結(jié)點(diǎn)，用指針pnew指向它，并將實(shí)際數(shù)據(jù)放在該結(jié)點(diǎn)的數(shù)據(jù)域，其指針域初始置為NULL；pnew=(NODE*)malloc(sizeof(NODE));pnew->score=score;pnew->next=NULL;③將pnew結(jié)點(diǎn)連接到tail所指向結(jié)點(diǎn)的后面：tail->next=pnew;④移動(dòng)tail使其指向pnew所指結(jié)點(diǎn)：tail=pnew;⑤重復(fù)②③④直至創(chuàng)建符合結(jié)束要求。⑥返回頭指針:

return(head);2022/12/1325示例1：建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表,新產(chǎn)生的結(jié)點(diǎn)總是插在鏈表的末尾,單向鏈表的頭指針作為函數(shù)值返回。2022/12/1326b)線性鏈表的查找操作建立鏈表如下：∧anaia1a2ai-1xL……2022/12/1327c)單鏈表的插入運(yùn)算（按排序順序插入到鏈表中）2022/12/1328d)單鏈表的刪除運(yùn)算ai-1a1aiai+1Lpq2022/12/1329e)單鏈表的遍歷和打印運(yùn)算2022/12/1330f)單鏈表的判空操作示例1：鍵盤輸入字符，并按順序創(chuàng)建字符鏈表。教材P374。2022/12/1332棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。a1a2….an進(jìn)棧出棧棧頂棧底1棧(Stack)1）

棧的定義定義：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表。特點(diǎn)：后進(jìn)先出(LIFO/先進(jìn)后出（FILO)。設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素，其原理示意圖為:棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。2022/12/13332）棧的運(yùn)算：設(shè)置一個(gè)空棧；插入一個(gè)新的棧頂元素；刪除棧頂元素；讀取棧頂元素。凡是對(duì)數(shù)據(jù)處理具有“后進(jìn)先出”的特點(diǎn)，都可以用棧來操作。2022/12/1334

順序棧：用順序存儲(chǔ)結(jié)構(gòu)表示的棧。

順序棧用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個(gè)簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向棧頂?shù)奈恢谩?/p>

例：

進(jìn)棧算法

彈棧算法a1a2a1a2top棧的上溢：棧滿時(shí)(top=stacksize-1)，還有元素要進(jìn)棧。棧的下溢：?？諘r(shí)（top=-1)，還有元素要出棧。2022/12/1335例：設(shè)數(shù)組S是一個(gè)順序棧，棧的最大容量stacksize=4，初始狀態(tài)top=-1

10S[4]231010進(jìn)棧:

top=top+1;s[top]=10top

10

25

30S[4]2310top30出棧:

y=s[top];top=top-1S[4]2310棧空:

top=-1top棧滿:top=stacksize-1

10

25

30

40S[4]2310top2022/12/13363）

棧的應(yīng)用

(1)

子程序的嵌套調(diào)用r主程序srrrs子程序1rst子程序2rst子程序32022/12/1337longFact(intn){longs;if(n==1)s=1;elses=n*Fact(n-1);return(s);}

計(jì)算N階乘的遞歸函數(shù)

(2)

遞歸算法：

1(n=0,1)n!=n(n-1)！(n>1)2022/12/1338遞歸調(diào)用執(zhí)行情況如下：主程序(1)輸出f(4);

……4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)2(2)3(1)4tops=4*3*2*1(1)4top返回(3)2(2)3(1)4top(4)1結(jié)束輸出24隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；2022/12/13393隊(duì)列1）

隊(duì)列的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。特點(diǎn)：此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。隊(duì)尾a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭先進(jìn)先出FIFO2022/12/13