數(shù)據(jù)結(jié)構(gòu)教程

數(shù)據(jù)結(jié)構(gòu)教程

第一課：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)

第二課：抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

第三課：算法及算法設(shè)計(jì)要求

第四課：算法效率的度量和存儲(chǔ)空間需求

第五課：線性表的類型定義

第六課：線性表的順序表示和實(shí)現(xiàn)

第七課：實(shí)驗(yàn)一線性表的順序存儲(chǔ)實(shí)驗(yàn)

第八課：線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)

第九課：循環(huán)鏈表與雙向鏈表

第十課：棧的表示與實(shí)現(xiàn)

第十一課：棧的應(yīng)用

第十二課：實(shí)驗(yàn)二循環(huán)鏈表實(shí)驗(yàn)

第十三課：隊(duì)列

第十四課：串的定義

第十五課：串的表示和實(shí)現(xiàn)

第十六課：串操作應(yīng)用舉例

第十七課：實(shí)驗(yàn)三：棧的表示與實(shí)現(xiàn)及棧的應(yīng)用

第十八課：數(shù)組的順序表示與實(shí)現(xiàn)

第十九課：實(shí)驗(yàn)四串的實(shí)現(xiàn)實(shí)驗(yàn)

第二十課：廣義表

第二十一課：樹(shù)、二叉樹(shù)定義及術(shù)語(yǔ)

第二十二課：實(shí)驗(yàn)五數(shù)組實(shí)驗(yàn)

第二十三課：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

第二十四課：遍歷二叉樹(shù)

第二十五課：?jiǎn)卧獪y(cè)驗(yàn)

第二十六課：圖的定義與術(shù)語(yǔ)

第二十七課：實(shí)驗(yàn)六二叉樹(shù)實(shí)驗(yàn)

第二十八課：圖的存儲(chǔ)結(jié)構(gòu)

第二十九課：靜態(tài)查找表（一）順序表的查找

第三十課：靜態(tài)查找表（二）有序表的查找

第三H''一課：動(dòng)態(tài)查找表

第三十二課：哈希表（一）

第三十三課：哈希表（二）

第三十四課：插入排序，快速排序

第三十五課：實(shí)驗(yàn)七查找

第三十六課：選擇排序，歸并排序

第三十七課：實(shí)驗(yàn)八排序?qū)嶒?yàn)

第三十八課：文件概念，順序文件

第三十九課：索引文件

第四十課：總復(fù)習(xí)

第一課

本課主題:數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)

教學(xué)目的:了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù)語(yǔ)

教學(xué)重點(diǎn):基本概念：數(shù)據(jù)與數(shù)據(jù)元素

教學(xué)難點(diǎn):數(shù)據(jù)元素間的四種結(jié)構(gòu)關(guān)系。

授課內(nèi)容:

一、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)的定義

1、數(shù)據(jù)的定義

定義一：數(shù)據(jù)是客觀事物的符號(hào)表示。

學(xué)號(hào)姓名語(yǔ)文數(shù)學(xué)C語(yǔ)言

6201001張三855492

6201002李四928464

6201003王五877473

6201004

???

例：張三的C語(yǔ)言考試成績(jī)?yōu)?2分，92就是該同學(xué)的成績(jī)數(shù)據(jù)。

定義二：能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

例：圖像、聲音等。

POWERBUILDER

總結(jié)：現(xiàn)實(shí)世界信息的分析、復(fù)制、傳播首先要符號(hào)化，這樣才便于處理，尤其

是便于計(jì)算機(jī)的處理。家長(zhǎng)、社會(huì)要了解一個(gè)學(xué)生的學(xué)習(xí)成績(jī)和能力，要看他的

學(xué)習(xí)檔案，而學(xué)習(xí)檔案即是說(shuō)明該學(xué)生學(xué)習(xí)情況的數(shù)據(jù)。

2、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它也可以再由不可分割的數(shù)據(jù)項(xiàng)組成。如圖示：

學(xué)號(hào)姓名，數(shù)學(xué)C語(yǔ)言

張二（

62娛UU1---------85_______15492

6201002李四------64

6201003王五87?-----_一個(gè)數(shù)據(jù)元素

6201004-------_

...、J一個(gè)數(shù)據(jù)項(xiàng)

翦繇翼翥顰整翻黔

3、數(shù)據(jù)對(duì)象

是性質(zhì)相同的數(shù)據(jù)元素的集合。如上例：一個(gè)班級(jí)的成績(jī)表可以看作一個(gè)數(shù)據(jù)對(duì)

象。

4、數(shù)據(jù)結(jié)構(gòu)

定義一、數(shù)據(jù)元素集合（也可稱數(shù)據(jù)對(duì)象）中各元素的關(guān)系。

定義二、相互之間存在特定關(guān)系的數(shù)據(jù)元素集合。

數(shù)據(jù)結(jié)構(gòu)的種類：

特征示例

同屬色彩集合

藍(lán)色

集合元素間為松散的關(guān)系

黃色

元素間為嚴(yán)格的一對(duì)

線性結(jié)構(gòu)如上面的成績(jī)表中各元素

一關(guān)系

一對(duì)多2祖

(父箕

元素間為嚴(yán)格的一對(duì)

樹(shù)形結(jié)構(gòu)

多關(guān)系/\/

攵攵炙子

多對(duì)多

圖狀結(jié)構(gòu)J京、

(或網(wǎng)狀結(jié)元素間為多對(duì)多關(guān)系合肥一連云港j上海

'南冬/

構(gòu))

公路交通網(wǎng)

數(shù)據(jù)結(jié)構(gòu)的形式定義:

數(shù)據(jù)結(jié)構(gòu)名稱=(D,S)

其中D為數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集

“數(shù)據(jù)結(jié)構(gòu)”定義中的“關(guān)系”指數(shù)據(jù)間的邏輯

邏輯結(jié)構(gòu)

關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)。又稱

存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)詳解：

計(jì)算機(jī)中存儲(chǔ)信息的最小單位：位，8位為一字節(jié)，兩個(gè)字節(jié)為一字，字節(jié)、字

或更多的二進(jìn)制位可稱為位串。在邏輯描述中，把位串稱為元素或結(jié)點(diǎn)。

當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域

(DataField)0

例：上述成績(jī)表數(shù)據(jù)用C語(yǔ)言的結(jié)構(gòu)體數(shù)組classonestu[50]來(lái)存儲(chǔ)：

structstu{

intstuno;/*數(shù)據(jù)項(xiàng)，也稱stu位串中的一個(gè)子位串，或叫做數(shù)據(jù)域*/

charname[20];

intmaths;

intlanguage;

intc_language;

}classonestu[50];

二、數(shù)據(jù)類型

1、定義：數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。

例：C語(yǔ)言中的整型，其內(nèi)涵為一定范圍的自然數(shù)集合，及定義在該集合上的加

減乘除及取模、比較大小操作。而實(shí)型則無(wú)取模操作。當(dāng)然整型也不需四舍五入。

2、數(shù)據(jù)類型的種類：

特征例

原子類型值在邏輯上不可分解intfloat

結(jié)構(gòu)類型值由若干成分按某種結(jié)構(gòu)組成structstu

數(shù)據(jù)類型封裝了數(shù)據(jù)存儲(chǔ)與操作的具體細(xì)節(jié)。

三、總結(jié)

數(shù)據(jù)-＞數(shù)據(jù)元素

具有特定關(guān)系的數(shù)據(jù)元素集合-＞數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的邏輯表示與物理存儲(chǔ)-＞邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

人們不僅關(guān)心數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，還關(guān)心數(shù)據(jù)的處理方法（算法）與處

理結(jié)果-＞數(shù)據(jù)類型

數(shù)據(jù)類型-＞分類

第二課

本課主題:抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

教學(xué)目的:了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法

教學(xué)重點(diǎn):抽象數(shù)據(jù)類型表示法、類C語(yǔ)言語(yǔ)法

教學(xué)難點(diǎn):抽象數(shù)據(jù)類型表示法

授課內(nèi)容:

一、抽象數(shù)據(jù)類型定義（ADT）

作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實(shí)世界。例：用線性表描述學(xué)生成

績(jī)表，用樹(shù)或圖描述遺傳關(guān)系。

定義：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。

關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲(chǔ)方式。定義它

的人同樣不必要關(guān)心它如何存儲(chǔ)。

例：線性表這樣的抽象數(shù)據(jù)類型，其數(shù)學(xué)模型是：數(shù)據(jù)元素的集合，該集合內(nèi)的

元素有這樣的關(guān)系：除第一個(gè)和最后一個(gè)外，每個(gè)元素有唯一的前趨和唯一的后

繼?？梢杂羞@樣一些操作：插入一個(gè)元素、刪除一個(gè)元素等。

抽象數(shù)據(jù)類型分類

原子類型值不可分解，如int

固定聚合類型值由確定數(shù)目的成分按某種結(jié)構(gòu)組成，如復(fù)數(shù)

可變聚合類型值的成分?jǐn)?shù)目不確定如學(xué)生基本情況

抽象數(shù)據(jù)類型表示法：

、

三元組表示：（D,S,P）

其中D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。

二、書(shū)中的定義格式：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義》

基本操作：〈基本操作的定義》

}ADT抽象數(shù)據(jù)類型名

例：線性表的表示

名稱線性表

數(shù)據(jù)對(duì)象D={aiai(-ElemSet,i=l,2,...,n,n>=0}任意數(shù)據(jù)元素的集合

除第一個(gè)和最后一個(gè)外，

數(shù)據(jù)關(guān)系Rl={〈aiT,ai>|3i-i,aiD,i=2,...,n)每個(gè)元素有唯一的直接

前趨和唯一的直接后繼

Listinsert(&L,i,e)L為線性表，i為位置，e

基本操作

ListDelete(&L,i,e)為數(shù)據(jù)元素。

二、類C語(yǔ)言語(yǔ)法

類C語(yǔ)言語(yǔ)法示例

^defineTRUE1

SdefineFALSE0

#defineOK1

1、預(yù)定

#defineERROR0

義常量

#defineINFEASIBLE-1

和類型

SdefineOVERFLOW-2

typedefinStatus;"Status是函數(shù)的類

型，其值是函數(shù)結(jié)果狀態(tài)代碼。

2、數(shù)據(jù)

結(jié)構(gòu)的

typedefElemTypefirst;

存儲(chǔ)結(jié)

構(gòu)

函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）｛

3、基本

〃算法說(shuō)明

操作的

語(yǔ)句序列

算法

"/函數(shù)名

簡(jiǎn)單賦值：變量名=表達(dá)式；

（變量名1,???,變量

名k）=（表達(dá)式1,...,

4、賦值表達(dá)式k）;

變量名1=變量名2=...=變量名成組

語(yǔ)句串聯(lián)賦值：結(jié)構(gòu)名=結(jié)構(gòu)名；

1<=表達(dá)式；賦

結(jié)構(gòu)名=（值1,

值：

值k);

變量名口=表達(dá)式；

變量名［起始下標(biāo)..終

止下標(biāo)］=變量名［起始

下標(biāo)..終止下標(biāo)］;

交換賦值：變量名<->變量名;

變量名=條件表達(dá)式？表達(dá)式?

條件賦值:

表達(dá)式T：表達(dá)式F

1、if（表達(dá)式）語(yǔ)句；

2、if（表達(dá)式）語(yǔ)句；

else語(yǔ)句；

3、switch（表達(dá)式）｛

case值1：語(yǔ)句序列1；break;

case值n：語(yǔ)句序列n；break;

5、選擇語(yǔ)句default:語(yǔ)句序列n+1；break;

）

4、switch（

case條件1：語(yǔ)句序列1；break;

case條件n：語(yǔ)句序列n；break;

default:語(yǔ)句序列n+1；break;

for（賦初值表達(dá)式；條件；修改表達(dá)式序列）

6、循環(huán)語(yǔ)句；

語(yǔ)句while（條件）語(yǔ)句;

do｛語(yǔ)句序列｝while（條件）；

return［表達(dá)式］；

7、結(jié)束

return;〃函數(shù)結(jié)束語(yǔ)句

語(yǔ)句

break;〃case結(jié)束語(yǔ)句

exit（異常代碼）；〃異常結(jié)束語(yǔ)句

8、輸入

和輸出scanf（［格式串］,變量1,變量n）；

語(yǔ)句

9、注釋〃文字序列

10、基max(表達(dá)式1,...,表達(dá)式n)

本函數(shù)min,abs,floor,ceil,eof,eoln

H、邏

&&與運(yùn)算;I或運(yùn)算

輯運(yùn)算

例：線性表的實(shí)現(xiàn):

ADTList{

數(shù)據(jù)對(duì)象：D={ai|ai(-ElemSet,i=l,2,...,n,n>=0}

數(shù)據(jù)關(guān)系：Rl={<ai-i,ai>|ai-i,as(-D,i=2,...,n)

基本操作：

InitList(&L)

DestroyList(&L)

Listinsert(&L,i,e)

ListDelete(&L,i,&e)

}ADTList

Listinsert(List&.L,inti,ElemTypee)

{if(i<l||i>L.length+)returnERROR;

q=&(L.elem[i-l]);

for(p=&(L.elem[L.length-1]);p>=q;―p)*(p+l)=*p;

*q=e;

++L.length;

returnOK;

）

下面是C語(yǔ)言編譯通過(guò)的示例:

#defineERROR0

#defineOK1

structSTU

{charname[20];

charstuno[10];

intage;intscore;

}stu[50];

structLIST

{structSTUstu[50];

intlength;

}L；

intprintlist(structLISTL)

(inti;

printf("namestunoagescore\n',);

for(i=0;i<L.length;i++)

printf("%s%s\t%d\t%d\n",L.stu[i].name,L.stu[i].stuno,

L.stu[i].age,L.stu[i].score);

printf("\n");

)

intlistinsert(structLIST*L,inti,structSTUe)

{structSTU*p,*q;

if(i<1||i>L->length+1)

returnERROR;

q=&(L->stu[i-1]);

for(p=&L->stu[L->length-1];p>=q;-p)

*(p+1)=*p;*q=e;++L->length;

returnOK;

}/*ListlnsertBeforei*/

main()

{structSTUe;

L.length=0;

strcpy(,"zmofun");

strcpy(e.stuno,"100001");

e.age=80;

e.score=1000;

listinsert(&L,1,e);

printlist(L);

printf("Listlengthnowis%d.\n\n",L.length);

strcpy(,"bobjin'^);

strcpy(e.stuno,"100002");

e.age=80;

e.score=1000;

listinsert(&L,1,e);

printlist(L);

printf("Listlengthnowis%d.\n\n",L.length);

}

E:\ZM\Zmdoc\datastru\class02Alistdemo

namestunoagescore

zmofun100001801000

Listlengthnowis1.

namestunoagescore

bobjin100002801000

zmofun100001801000

Listlengthnowis2.

抽象數(shù)據(jù)類型定義;

抽象數(shù)據(jù)類型實(shí)現(xiàn)方法：一、類C語(yǔ)言實(shí)現(xiàn)二、C語(yǔ)言實(shí)現(xiàn)

回目錄上一課下一課

第三課

本課主題:算法及算法設(shè)計(jì)要求

教學(xué)目的:掌握算法的定義及特性，算法設(shè)計(jì)的要求

教學(xué)重點(diǎn):算法的特性，算法設(shè)計(jì)要求

教學(xué)難點(diǎn):算法設(shè)計(jì)的要求

授課內(nèi)容:

一、算法的定義及特性

1、定義：

ispass(intnum[4][4])

{inti,j;

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

for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+l)/*一條指令,多個(gè)操作*/

return0;

return1;

}/*上面是一個(gè)類似華容道游戲中判斷游戲是否結(jié)束的算法*/

算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令

表示一個(gè)或多個(gè)操作；止匕外，一個(gè)算法還具有下列五個(gè)重要特性：

2、算法的五個(gè)特性：

一個(gè)算法必須總是(對(duì)任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，

有窮性

且每一步都可在有窮時(shí)間內(nèi)完成；

算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義

確定性性。有任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的

輸入只能得出相同的輸出。

一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的

可行性

基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。

一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對(duì)象的

輸入

集合。

一個(gè)算法有一個(gè)或多個(gè)的輸出。這些輸出是同輸入有著某些特定關(guān)

輸出

系的量。

例:

haha()

{Aonlyajoke,donothing.*/

)

main()

有窮性

{printf(〃請(qǐng)稍等...您將知道世界的未日???〃)；

while(1)

haha();

)

floataverage(int*a,intnum)

{inti;longsum=0;

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

sum+=*(a++);

returnsum/num;

確定性

)

main()

{intscore[10]={l,2,3,4,5,6,7,8,9,0);

printfaverage(score,10);

)

可行性

輸入

getsum(intnum)

(

inti,sum=0;

輸出

for(i=l;i<=num;i++)

sum+=i;

}/*無(wú)輸出的算法沒(méi)有任何意義，

二、算法設(shè)計(jì)的要求

1、正確性

算法正確性的四個(gè)層次

max(inta,intb,intc)

(

if(a>b)

程序不含語(yǔ)法錯(cuò)誤。{if(a>c)returnc;

elsereturna;

)

)

max(inta,intb,intc)

(

程序?qū)τ趲捉M輸入數(shù)據(jù)if(a>b)

能夠得出滿足規(guī)格說(shuō)明{if(a>c)returna;

要求的結(jié)果。elsereturnc;

)

}/*8,6,7*//*9,3,2*/

max(inta,intb,intc)

(

if(a>b)

程序?qū)τ诰倪x擇的典{if(a>c)returna;

型、苛刻而帶有刁難性elsereturnc;

的幾組輸入數(shù)據(jù)能夠得)

出滿足規(guī)格說(shuō)明要求的else

結(jié)果。{if(b>c)returnb;

elsereturnc;

)

)

程序?qū)τ谝磺泻戏ǖ妮?/p>

入數(shù)據(jù)都能產(chǎn)生滿足規(guī)

格說(shuō)明要求的結(jié)果。

2、可讀性

3、健壯性

4、效率與低存儲(chǔ)量需求

效率指的是算法執(zhí)行時(shí)間。對(duì)于解決同一問(wèn)題的多個(gè)算法，執(zhí)行時(shí)間短的算法效

率IWJ。

存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。

兩者都與問(wèn)題的規(guī)模有關(guān)。

算法一算法二

max(inta[3])

max(inta,int

{intc,inti;

b,intc)

c=a[0];

{if(a>b)

for(i=l;i<3;i++)

{if(a>c)returna;

if(a[i]>c)c=a[i];

elsereturnc;

在三個(gè)整數(shù)中求returnc;

1

最大者}

else

/*需要兩個(gè)額外的存儲(chǔ)空

{if(b>c)returnb;

間，兩次比較，至少一次賦

elsereturnc;

值*/

}/*無(wú)需額外存儲(chǔ)空

間，只需兩次比較*/

/*共需5個(gè)整型數(shù)空間*/

max(inta[100])

{intc,inti;

c=a[0];

求100個(gè)整數(shù)中同上的算法難寫(xiě)，難for(i=l;i<100;i++)

最大者讀if(a[i]>c)c=a[i];

returnc;

}

/*共需102個(gè)整型數(shù)空間*/

三、總結(jié)

1、算法的特性

2、算法設(shè)計(jì)要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。

回目錄上一課下一課

第四課

本課主題:算法效率的度量和存儲(chǔ)空間需求

教學(xué)目的:掌握算法的漸近時(shí)間復(fù)雜度和空間復(fù)雜度的意義與作用

教學(xué)重點(diǎn):漸近時(shí)間復(fù)雜度的意義與作用及計(jì)算方法

教學(xué)難點(diǎn):漸近時(shí)間復(fù)雜度的意義

授課內(nèi)容:

一、算法效率的度量

算法執(zhí)行的時(shí)間是算法優(yōu)劣和問(wèn)題規(guī)模的函數(shù)。評(píng)價(jià)一個(gè)算法的優(yōu)劣，可以在相

同的規(guī)模下，考察算法執(zhí)行時(shí)間的長(zhǎng)短來(lái)進(jìn)行判斷。而一個(gè)程序的執(zhí)行時(shí)間通常

有兩種方法：

1、事后統(tǒng)計(jì)的方法。

缺點(diǎn)：不利于較大范圍內(nèi)的算法比較。(異地，異時(shí)，異境)

2、事前分析估算的方法。

程序在計(jì)算機(jī)上運(yùn)行所需時(shí)間的影響因素

算法本身選用的策略

問(wèn)題的規(guī)模規(guī)模越大，消耗時(shí)間越多

書(shū)寫(xiě)程序的語(yǔ)言語(yǔ)言越高級(jí)，消耗時(shí)間越多

編譯產(chǎn)生的機(jī)器代碼質(zhì)量

機(jī)器執(zhí)行指令的速度

綜上所述，為便于比較算法本身的優(yōu)劣，應(yīng)排除其它影響算法效率的因素。

從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作重

復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。(原操作在所有該問(wèn)題的算法中都相同)

7(n)=0(f(n))

上示表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，

稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

sum(intnum[4][4])

{inti,j,r=0;

求4*4矩陣元素for(i=0;i<4;i++)

和，T(4)=0(f(4))for(j=0;j<4;j++)

f=n*n;r+=num[i][j];/*原操作*/

returnr;

}

ispass(intnum[4][4])

{inti,j;

最好情況：for(i=0;i<4;i++)

T(4)=0(0)for(j=0;j<4;j++)

最壞情況：if(num[i][j]!=i*4+j+l)

T(4)=0(n*n)return0;

return1;

}

原操作執(zhí)行次數(shù)和包含它的語(yǔ)句的頻度相同。語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行

的次數(shù)。

語(yǔ)句頻度時(shí)間復(fù)雜度

{++x;s=0;}10(1)

for(i=l;i<=n;++i)

n0(n)

{++x;s+=X；}

for(j=l;j<=n;++j)

for(k=l;k<=n;++k)n*n0(n*n)

{++x;s+=x;}

0(logn)

。的

基本操作的執(zhí)行次數(shù)不確定時(shí)的時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度依基本操作執(zhí)行次數(shù)概率計(jì)算平均

最壞情況下時(shí)間復(fù)雜度在最壞情況下基本操作執(zhí)行次數(shù)

二、算法的存儲(chǔ)空間需求

類似于算法的時(shí)間復(fù)雜度，空間復(fù)雜度可以作為算法所需存儲(chǔ)空間的量度。

記作：

S(n)=0(f(n))

若額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù),則稱此算法為原地工作。

如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來(lái)分析。

三、總結(jié)

漸近時(shí)間復(fù)雜度

空間復(fù)雜度

回目錄上一課下一課

第五課

本課主題:線性表的類型定義

教學(xué)目的:掌握線性表的概念和類型定義

教學(xué)重點(diǎn):線性表的類型定義

教學(xué)難點(diǎn):線性表的類型定義

授課內(nèi)容:

復(fù)習(xí)：數(shù)據(jù)結(jié)構(gòu)的種類

線性結(jié)構(gòu)的特點(diǎn)：

在數(shù)據(jù)元素的非空有限集中，

(1)存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；?

(2)存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；

(3)除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)

前驅(qū)；?

(4)除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)

后繼。?

一、線性表的定義

線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。

一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。

數(shù)據(jù)元素可以是一個(gè)數(shù)、一個(gè)符號(hào)、也可以是一幅圖、一頁(yè)書(shū)或更復(fù)雜的信息。

線性表例：

1、

1234567

2、

3、

學(xué)號(hào)姓名語(yǔ)文數(shù)學(xué)C語(yǔ)言

6201001張三855492

6201002李四928464

6201003王五877473

6201004

,.,

數(shù)據(jù)元素也可由若干個(gè)數(shù)據(jù)項(xiàng)組成（如上例3）。這時(shí)常把數(shù)據(jù)元素稱為記錄。

含有大量記錄的線性表又稱文件。

線性表中的數(shù)據(jù)元素類型多種多樣，但同一線性表中的元素必定具有相同特性,

即屬同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。

ai???a,i-iaiai+ian

ai是ai+1的直接前驅(qū)元素，ai+1是ai的直接后繼元素。

線性表中元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度，為0時(shí)稱為空表。在非空表中的每

個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置。ai是第i個(gè)元素，把i稱為數(shù)據(jù)元素ai在線

性中的位序。

二、線性表的類型定義

1、抽象數(shù)據(jù)類型線性表的定義如下：

ADTList{

數(shù)據(jù)對(duì)象：D={ai|ai(-ElemSet,i=l,2,...,n,n>=0}

數(shù)據(jù)關(guān)系：Rl={<ai-i,ai>|ai-i,ai(-D,i=2,...,n)

基本操作：

InitList(&L)

DestroyList(&L)

ClearList(&L)

ListEmpty(L)

ListLength(L)

GetElem(L,i,&e)

LocateElem(L,e,compare())

PriorElem(L,cur_e,&pre_e)

NextElem(L,cur_e,&next_e)

Listinsert(&L,i,e)

ListDelete(&L,i,&e)

ListTraverse(L,visit())

union(List&La,List&Lb)

}ADTList

2、部分操作的類C實(shí)現(xiàn)：

InitList(&L)

{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!Lelem)exit(OVERFLOW);

L.length=0;

L.listsize=LISTINITSIZE;

returnOK;

}//InitList

GetElem(L,i,&e)

{*e=L.lem[i]

}//GetElem

Listinsert(List&L,inti,ElemTypee)

{if(i<l,|i>L.length+)returnERROR;

q=&(L.elem[i-l]);

for(p=&(L.elem[L.length-1]);p>=q;一一p)*(p+l)=*p;

*q=e;

++L.length;

returnOK;

}//ListInsert

voidunion(List&La,List&Lb)

{La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=l;i<=Lb_len;i++){

GetElem(Lb,i,e);

if(!LocateElem(La,e,equal))

Listinsert(La,++La_len,e);

}//union

voidMergeList(ListLa,ListLb,List&Lc)

{InitList(Lc);

i=j=l;k=O;

La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<Lb_len)){

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){Listinsert(Lc,++k,ai);++i;}

else{Listinsert(Lc,++k,bj);++j;}

while(k<=Lalen){

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

while(j<=Lb_len){

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

)

}//MergeList

3、部分操作的C語(yǔ)言實(shí)現(xiàn),下面是程序運(yùn)行的結(jié)果:

----------------------ListDemoisrunning...

FirstisInsertListfunction.

namestunoagescore

stul100001801000

stu2100002801000

ListAlengthnowis2.

namestunoagescore

stul100001801000

stu2100002801000

stu3100003801000

ListAlengthnowis3.

namestunoagescore

zmofun100001801000

bobjin100002801000

stul100001801000

ListBlengthnowis3.

SecondisUnionListfunction.

NowunionListAandListB.....

namestunoagescore

stul100001801000

stu2100002801000

stu3100003801000

zmofun100001801000

bobjin100002801000

ListAlengthnowis5.

Welcometovisithttp://zmofun.heha.net!

三、總結(jié)

線性表的定義

線性表的類型定義

回目錄上一課下一課

第六課

本課主題:線性表的順序表示和實(shí)現(xiàn)

教學(xué)目的:掌握線性表的順序表示和實(shí)現(xiàn)方法

教學(xué)重點(diǎn):線性表的順序表示和實(shí)現(xiàn)方法

教學(xué)難點(diǎn):線性表的順序存儲(chǔ)的實(shí)現(xiàn)方法

授課內(nèi)容:

復(fù)習(xí)

1、存儲(chǔ)結(jié)構(gòu)

“數(shù)據(jù)結(jié)構(gòu)”定義中的“關(guān)系”指數(shù)據(jù)間的邏輯

邏輯結(jié)構(gòu)

關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)。又稱

存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2、線性表的類型定義

一、線性表的順序表示

用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。C語(yǔ)言中的數(shù)組即采用

順序存儲(chǔ)方式。

2000:000100000000000000011

2000:000300000000000000102

2000:000500000000000000113

2000:000700000000000001004

2000:000900000000000001015

2000:001100000000000001106

a[9]

2000:001300000000000001117

2000:001500000000000010008

2000:001700000000000010019

???

2000:1001

2000:1003

假設(shè)線性表的每個(gè)元素需占用/個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址

作為數(shù)據(jù)元素的存儲(chǔ)位置。則存在如下關(guān)系：

L0C(ai+i)=L0C(ai)+7

L0C(ai)=L0C(ai)+(y-i)*7

式中Loc(ai)是線性表的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，通常稱做線性表的起始位

置或基地址。常用，表示。

線性表的這種機(jī)內(nèi)表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象。

稱順序存儲(chǔ)結(jié)構(gòu)的線性表為順序表。順序表的特點(diǎn)是以元素在計(jì)算機(jī)內(nèi)物理位置

相鄰來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。

二、順序存儲(chǔ)結(jié)構(gòu)的線性表類c語(yǔ)言表示：

線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)

^defineLIST_INIT_SIZE100

WdefineLISTINCREMENT10

typedefstruct{

ElemType*elem;〃存儲(chǔ)空間基址

intlength;〃當(dāng)前長(zhǎng)度

intlistsize;〃當(dāng)前分配的存儲(chǔ)容量以一數(shù)據(jù)元素存儲(chǔ)長(zhǎng)度為單位

}SqList;

三、順序存儲(chǔ)結(jié)構(gòu)的線性表操作及c語(yǔ)言實(shí)現(xiàn):

順序表的插入與刪除操作：

數(shù)據(jù)元

序號(hào)數(shù)據(jù)元素序號(hào)序號(hào)數(shù)據(jù)元素序號(hào)數(shù)據(jù)元素

素

112112112112

I

2弱213213213

—-->24

321321321321

----Hi(-25

424424424428

5525528530

630628630642

742730742777

8778428778

997799

插入前n=8;插入后n=9;刪除前n=8;刪除后n=7;

順序表的插入算法

statusListinsert(List*L,inti,ElemTypee){

structSTU*p,*q;

if(i<l||i>L->length+l)returnERROR;

q=&(L->elem[i-l]);

for(p=&L->elem[L->1ength-1];p>=q;-p)

*(p+l)=*p;

*q=e;

++L->length;

returnOK;

}/*ListInsertBeforei*/

順序表的合并算法

voidMergeList(List*La,List*Lb,List*Lc){

ElemType*pa,*pb,*pc,*pa_last,*pb_last;

pa=La->elem;pb=Lb->elem;

Lc->listsize=Lc->length=La->length+Lb->length;

pc=Lc->elem=

(ElemType*)malloc(Lc->listsize*sizeof(ElemType));

if(!Lc->elem)exit(OVERFLOW);

pa_last=La->elem+La->length-1;

pb_last=Lb->elem+Lb->length-1;

while(pa<=pa__last&&pb<=pb_last){

if(Less_EqualList(pa,pb))*pc-H-=*pa++;

else*pc++=*pb++;

)

while(pa<=pa_last)*pc++=*pa++;

while(pb<=pb_last)*pc-H■=*pb++;

)

順序表的查找算法

intLocateElem(List*La,ElemTypee,inttype){

inti;

switch(type){

caseEQUAL:

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

if(EqualList(&La->elem[i],&e))

return1;

break;

default:

break;

}

return0;

)

順序表的聯(lián)合算法

voidUnionList(List*La,List*Lb){

intLa_len,Lb_len;inti;ElemTypee;

La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=0;i<Lb_len;i++){

GetElem(*Lb,i,&e);

if(!LocateElem(La,e,EQUAL))

Listinsert(La,++La_len,e);

}

)

三、c語(yǔ)言源程序范例

四、總結(jié)

線性表的順序表示

順序表的插入算法

順序表的合并算法

回目錄上一課下一課

第七課

本課主題:實(shí)驗(yàn)一線性表的順序存儲(chǔ)實(shí)驗(yàn)

教學(xué)目的:掌握順序表的定義及操作的C語(yǔ)言實(shí)現(xiàn)方法

教學(xué)重點(diǎn):順序表的操作的C語(yǔ)言實(shí)現(xiàn)方法

教學(xué)難點(diǎn):順序表的操作的c語(yǔ)言實(shí)現(xiàn)方法

實(shí)驗(yàn)內(nèi)容:

利用順序表完成一個(gè)班級(jí)的一個(gè)學(xué)期的所有課程的管理：能夠增加、刪除、修改

學(xué)生的成績(jī)記錄。

實(shí)驗(yàn)要求:

在上機(jī)前寫(xiě)出全部源程序。

回目錄上一課下一課

第八課

本課主題:線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)

教學(xué)目的:掌握線性鏈表、單鏈表、靜態(tài)鏈表的概念、表示及實(shí)現(xiàn)方法

教學(xué)重點(diǎn):線性鏈表之單鏈表的表示及實(shí)現(xiàn)方法。

教學(xué)難點(diǎn):線性鏈表的概念。

授課內(nèi)容:

一、復(fù)習(xí)順序表的定義。

二、線性鏈表的概念：

以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表稱之為線性鏈表。

特點(diǎn)是該線性表中的數(shù)據(jù)元素可以用任意的存儲(chǔ)單元來(lái)存儲(chǔ)。線性表中邏輯相鄰

的兩元素的存儲(chǔ)空間可以是不連續(xù)的。為表示邏輯上的順序關(guān)系，對(duì)表的每個(gè)數(shù)

據(jù)元素除存儲(chǔ)本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接衙繼的信息。這兩部分

信息組成數(shù)據(jù)元素的存儲(chǔ)映象，稱為結(jié)點(diǎn)。

2000:1000頭指針2000:10062000:1030

2000:1010a32000:1040

2000:1020a6NULL

2000:1030al2000:1060〈-數(shù)據(jù)域+指針域

2000:1040a42000:1050

2000:1050a52000:1020

2000:1060a22000:1010

???數(shù)據(jù)域指針域

2000:4000

例：下圖是若干抽屜，每個(gè)抽屜中放一個(gè)數(shù)據(jù)元素和一個(gè)指向后繼元素的指針，

一號(hào)抽屜中放線性表的第一個(gè)元素，它的下一個(gè)即第二個(gè)元素的位置標(biāo)為5,即

放在第5個(gè)抽屜中，而第三個(gè)放在2號(hào)抽屜中。第三個(gè)元素即為最后一個(gè)，它的

下一個(gè)元素的指針標(biāo)為空，用0表示。

1234567

IIi------1czzzii?i

891011121314

i:?]11?i??

15161718192021

????i?????

502

第1七第2Z-：b.

用線性鏈表表示線性表時(shí),數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的

二、線性鏈表的存儲(chǔ)實(shí)現(xiàn)

structLNODE{

ElemTypedata;

structLNODE*next;

）；

typedefstructLNODELNode;

typedefstructLNODE*LinkList;

頭指針與頭結(jié)點(diǎn)的區(qū)別：

頭指針只相當(dāng)于結(jié)點(diǎn)的指針域，頭結(jié)點(diǎn)即整個(gè)線性鏈表的第一個(gè)結(jié)點(diǎn)，它的數(shù)據(jù)

域可以放數(shù)據(jù)元素，也可以放線性表的長(zhǎng)度等附加信息，也可以不存儲(chǔ)任何信息。

三、線性表的操作實(shí)現(xiàn)(類C語(yǔ)言)

1初始化操作

StatusInit_L(LinkListL){

if(L=(LinkList*)malloc(sizeof(LNode)))

{L->next=NULL;return1;}

elsereturn0;

)

2插入操作

StatusListInsert_L(LinkList&L,inti,ElemTypee){

P=L,j=0;

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

if(!p||j>i-l)returnERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;s->next=p->next;

p->next=s;

returnOK;

}//ListInsert_L

在第3個(gè)位置前插入元索8L=3

P

L

IL今區(qū)［+匚口3乂二江不匚百今…今［1二囚

」二0%dQT為真

2L今，//書(shū)廠1I書(shū)121Al3I+>…制QI八1

產(chǎn)1P融UGT為真

3L■M777T:H~TT:P?rrFbnTzb…方巨因

j=2PMja-i為假

$―rm-

p

qL—I//7I-PCT1用2I+>13I?+?…-9I川

3刪除操作

StatusListDelete_L(LinkList&L,inti,ElemType&e){

P=L,j=0;

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

if(!p->next||j>i-l)returnERROR;

q=p->next;p->next=q->next;

e=q->data;free(q);

returnOK;

}//ListDelete_L

刪除第撲位置的元素：

P

]L)fl1I-12I4I3I-H4-4I書(shū)..今IB1A]

」;oPft&jC-l為真

If-

2L~K//I+H1?+?廠￡?+?i$I為一“引gw

>1尸獨(dú)ja-i為真

￡

3LvPTTFbnr^rrFhrrnhrrnkL<j_id

j=2P幽jC-l為假

J金Q=P->next

gL?M777T=H"n'zN"^T=br3T=hrn'=b…HZH3

QP=Q->next

5LT-//I+nr^nTH今國(guó)3

PQfrEB（O）

vJ

5L今區(qū)［于匚二工ALT卬.rTT^今匚口四

IT

4取某序號(hào)元素的操作

StatusGetElem_L(LinkList&L,inti,ElemType&e){

p=L->next,j=l;

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

if(!pI|j>i)returnERROR;

e=p->data;

returnOK;

}//GetElem_L

5歸并兩個(gè)單鏈表的算法

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

〃已知單鏈線性表La和Lb的元素按值非遞減排列

〃歸并后得到新的單鏈線性表Lc,元素也按值非遞減排列

pa=La->next;pb=Lb->next;

Lc二pc=La;

while(pa&&pb){

if(pa->data<=pb->data){

pc->next=pa;pc=pa;pa=pa->next;

}else{pc->next=pb;pc=pb;pb=pb->next;}

pc->next=pa?pa:pb;

free(Lb);

}//MergeList_L

C語(yǔ)言實(shí)現(xiàn)的例子。

四、總結(jié)

1、線性鏈表的概念。

2、線性鏈表的存儲(chǔ)

3、線性鏈表的操作

回目錄上一課下一課

第九課

本課主題:循環(huán)鏈表與雙向鏈表

教學(xué)目的:掌握循環(huán)鏈表的概念，掌握雙向鏈表的的表示與實(shí)現(xiàn)

教學(xué)重點(diǎn):雙向鏈表的表示與實(shí)現(xiàn)

教學(xué)難點(diǎn):雙向鏈表的存儲(chǔ)表示

授課內(nèi)容:

一、復(fù)習(xí)線性鏈表的存儲(chǔ)結(jié)構(gòu)

In