高等數(shù)據(jù)結(jié)構(gòu)與算法第一頁(yè)，共二十六頁(yè)，2022年，8月28日教材：數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)嚴(yán)蔚敏清華大學(xué)出版社參考書：數(shù)據(jù)結(jié)構(gòu)——使用C語(yǔ)言朱戰(zhàn)立西安交通大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)與算法齊德昱清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)與算法——C++版(第2版)AdamDrozdek清華大學(xué)出版社課程與考試安排：第8、11、12章不作要求有**號(hào)的小節(jié)不作要求期末成績(jī)和平時(shí)成績(jī)各占60％和40％第二頁(yè)，共二十六頁(yè)，2022年，8月28日第一章緒言1.1.1什么是數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)=數(shù)據(jù)模型+算法程序設(shè)計(jì)：為計(jì)算機(jī)處理問(wèn)題編制的一組指令集數(shù)據(jù)模型：現(xiàn)實(shí)問(wèn)題的抽象算法：處理問(wèn)題的策略數(shù)值計(jì)算問(wèn)題——數(shù)學(xué)模型是一組線性或非線性的代數(shù)方程組或微分方程組非數(shù)字計(jì)算問(wèn)題(包括管理、控制、數(shù)據(jù)處理等)——數(shù)學(xué)模型是數(shù)據(jù)結(jié)構(gòu)第三頁(yè)，共二十六頁(yè)，2022年，8月28日例1書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表第四頁(yè)，共二十六頁(yè)，2022年，8月28日例2人機(jī)對(duì)奕問(wèn)題樹……..……..…...…...…...…...第五頁(yè)，共二十六頁(yè)，2022年，8月28日多叉路口交通燈管理問(wèn)題CEDABABACADBABCBDDADBDCEAEBECED圖第六頁(yè)，共二十六頁(yè)，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)定義:是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科1.1.2為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的需要計(jì)算機(jī)專業(yè)基礎(chǔ)課編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)和大型應(yīng)用程序第七頁(yè)，共二十六頁(yè)，2022年，8月28日1.1.3學(xué)什么掌握各種類型的數(shù)據(jù)結(jié)構(gòu)掌握查找和排序操作學(xué)會(huì)用算法去處理問(wèn)題學(xué)會(huì)用C語(yǔ)言去實(shí)現(xiàn)算法1.1.4怎么學(xué)重視實(shí)踐環(huán)節(jié)，包括編程和上機(jī)第八頁(yè)，共二十六頁(yè)，2022年，8月28日1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)(data)——所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)，數(shù)據(jù)是信息的載體數(shù)據(jù)元素(dataelement)——數(shù)據(jù)的基本單位，數(shù)據(jù)中的一個(gè)“個(gè)體”數(shù)據(jù)項(xiàng)(dataitem)——數(shù)據(jù)的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的組合，有組合項(xiàng)和原子項(xiàng)之分?jǐn)?shù)據(jù)對(duì)象(dataobject)——性質(zhì)相同的數(shù)據(jù)元素的集合，如整數(shù)、所有書目信息等數(shù)據(jù)結(jié)構(gòu)(datastructure)——數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合，數(shù)據(jù)元素相同而關(guān)系不同的數(shù)據(jù)結(jié)構(gòu)是不同的數(shù)據(jù)結(jié)構(gòu)第九頁(yè)，共二十六頁(yè)，2022年，8月28日根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structures=(D,S)

其中：D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。第十頁(yè)，共二十六頁(yè)，2022年，8月28日數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)元素的實(shí)現(xiàn)數(shù)值"321"可用位串101000001表示，字母"A"可用位串001000001表示關(guān)系的實(shí)現(xiàn)第十一頁(yè)，共二十六頁(yè)，2022年，8月28日元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)第十二頁(yè)，共二十六頁(yè)，2022年，8月28日1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

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

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

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

h第十三頁(yè)，共二十六頁(yè)，2022年，8月28日不同的編程環(huán)境中，數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)可有不同的描述方法：以上用的是計(jì)算機(jī)的編碼及內(nèi)存來(lái)描述還可用高級(jí)程序語(yǔ)言提供的數(shù)據(jù)類型來(lái)描述關(guān)系順序存儲(chǔ)結(jié)構(gòu)

intLong_int[3];[鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

int

*Long_int[3];數(shù)據(jù)元素Long_int[0]=4234;第十四頁(yè)，共二十六頁(yè)，2022年，8月28日1.3抽象數(shù)據(jù)類型數(shù)據(jù)類型(datatype)——一個(gè)值的集合和定義在此集合上的一組操作的總稱抽象數(shù)據(jù)類型(abstractdatatype,ADT)——一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作抽象不同語(yǔ)言不同處理器相同的數(shù)學(xué)特征（即已定義的數(shù)據(jù)類型）設(shè)計(jì)軟件時(shí)自定義的數(shù)據(jù)類型ADT有兩個(gè)重要特征：數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)特征和外界使用它的方法數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)第十五頁(yè)，共二十六頁(yè)，2022年，8月28日抽象數(shù)據(jù)類型包含定義、表示和實(shí)現(xiàn)三部分。抽象數(shù)據(jù)類型的形式描述為：

ADT=(D，S，P)

其中：D是數(shù)據(jù)對(duì)象，

S是D上的關(guān)系集，

P是D的基本操作集。typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;第十六頁(yè)，共二十六頁(yè)，2022年，8月28日1.抽象數(shù)據(jù)類型的定義ADT形式定義為：

ADT

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

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

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

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

}

ADT

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

其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為

基本操作名

（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。

"初始條件"描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則可省略之。

"操作結(jié)果"說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。第十七頁(yè)，共二十六頁(yè)，2022年，8月28日例：抽象數(shù)據(jù)類型"復(fù)數(shù)"的定義為：ADTComplex{

數(shù)據(jù)對(duì)象：D={e1,e2|e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：R1={<e1,e2>|e1是復(fù)數(shù)的實(shí)部，e2是復(fù)數(shù)的虛部}

基本操作：

InitComplex(&Z,v1,v2)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z，其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)

初始條件：復(fù)數(shù)已存在。

操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)

初始條件：復(fù)數(shù)已存在。

操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)

初始條件：復(fù)數(shù)已存在。

操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)

初始條件：z1，z2是復(fù)數(shù)。

操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1，z2的和值。

}ADTComplex第十八頁(yè)，共二十六頁(yè)，2022年，8月28日2.抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過(guò)高級(jí)編程語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型（通常稱之謂固有數(shù)據(jù)類型）來(lái)實(shí)現(xiàn)。第十九頁(yè)，共二十六頁(yè)，2022年，8月28日例：利用C語(yǔ)言實(shí)現(xiàn)的"復(fù)數(shù)"類型如下描述：

//

存儲(chǔ)結(jié)構(gòu)的定義

typedefstruct{

floatrealpart;

floatimagpart;

}complex;

//

基本操作的函數(shù)原型說(shuō)明

voidAssign(complex&Z,floatrealval,floatimagval);

//

構(gòu)造復(fù)數(shù)Z，其實(shí)部和虛部分別被賦以參數(shù)realval和imagval的值

voidadd(complexz1,complexz2,complex&sum);

//

以sum返回兩個(gè)復(fù)數(shù)z1，z2的和

//

基本操作的實(shí)現(xiàn)

…………

voidadd(complexz1,complexz2,complex&sum)

{//

以sum返回兩個(gè)復(fù)數(shù)z1，z2的和

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;

}

…………第二十頁(yè)，共二十六頁(yè)，2022年，8月28日1.4算法的描述和算法分析簡(jiǎn)介算法（algorithm）—解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列算法特性—算法的描述—采用類C語(yǔ)言算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲(chǔ)量第二十一頁(yè)，共二十六頁(yè)，2022年，8月28日算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)度量

1.事后統(tǒng)計(jì)——利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

2.事前分析估計(jì)——一個(gè)高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：依據(jù)的算法選用何種策略問(wèn)題的規(guī)模程序語(yǔ)言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———所以使用絕對(duì)時(shí)間單位衡量算法效率不合適第二十二頁(yè)，共二十六頁(yè)，2022年，8月28日時(shí)間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù)T(n)=O(f(n))，表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同例1：NXN矩陣相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0; for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];} 語(yǔ)句的頻度：該語(yǔ)句重復(fù)執(zhí)行的次數(shù)第二十三頁(yè)，共二十六頁(yè)，2022年，8月28日除特別指明，若算法的執(zhí)行時(shí)間依賴于特定的輸入，則按最壞情況考慮對(duì)時(shí)間復(fù)雜度而言，只需要取最高項(xiàng)，并忽略常數(shù)系數(shù)

voidbubble_sort(inta[],intn)

{//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

for(i=n-1,change=TRUE;i>1&&change;--i){

change=FALSE;

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

if(a[j]>a[j+1])

{w=a[j];a[j]=a[j+1];a[j+1]=w;change=TRUE}

}

}//bubble_sort

算法執(zhí)行次數(shù)隨輸入數(shù)據(jù)不同而不同，概率相等時(shí)考慮平均值，概率不明時(shí)考慮最壞情況。#include<stdio.h>main(){inta[11],i,j,t;pr