數(shù)據(jù)結(jié)構(gòu)chaer資料

數(shù)據(jù)結(jié)構(gòu)12十二月2023學(xué)時(shí)數(shù)：48學(xué)時(shí)教材：《數(shù)據(jù)結(jié)構(gòu)C語言版》嚴(yán)蔚敏、吳偉民-----清華大學(xué)出版社教學(xué)參考書：[1]殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社[2]《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社[3]丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社課程介紹2第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第9章查找

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

1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語

1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

1.4算法和算法分析第1章緒論4一、數(shù)據(jù)結(jié)構(gòu)課程的研究內(nèi)容電子計(jì)算機(jī)的主要用途：

早期：主要用于數(shù)值計(jì)算。

后來：

處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）數(shù)學(xué)模型→選擇計(jì)算機(jī)語言→編出程序→測試→最終解答數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述1.1什么是數(shù)據(jù)結(jié)構(gòu)5

非數(shù)值計(jì)算問題例1.1

電話號(hào)碼查詢問題。例1.2

田徑賽的時(shí)間安排問題：設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）。要求設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。1.1什么是數(shù)據(jù)結(jié)構(gòu)6（1）設(shè)用如下六個(gè)不同的編碼代表不同的項(xiàng)目：

跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米

AB CDE F姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一ABE馬二CD

張三CEF李四DFA王五BF（2）用頂點(diǎn)（圓圈）代表比賽項(xiàng)目

不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。AEBFDC比賽時(shí)間比賽項(xiàng)目1A，C2B，D3E4F1.1什么是數(shù)據(jù)結(jié)構(gòu)7因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。由此可見：對(duì)于解決非數(shù)值計(jì)算的問題首先要考慮對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？1.1什么是數(shù)據(jù)結(jié)構(gòu)81.許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，國防科技大學(xué)計(jì)算機(jī)研究所，1985年“按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲(chǔ)表示方式把它存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做一個(gè)數(shù)據(jù)結(jié)構(gòu)?！碧攸c(diǎn)：從三個(gè)方面來看數(shù)據(jù)結(jié)構(gòu)。2.李春葆，《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》，清華大學(xué)出版社，2000年“數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)又可以分為下述三個(gè)組成部分，它們分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。”特點(diǎn)：明確強(qiáng)調(diào)“關(guān)系”，且細(xì)分“關(guān)系”。1.1什么是數(shù)據(jù)結(jié)構(gòu)93.黃國瑜，葉乃菁，《數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社，2001年“在程序語言中，“數(shù)據(jù)類型”是指程序語言中變量所能表示并存儲(chǔ)的數(shù)據(jù)種類，“數(shù)據(jù)實(shí)體”則是指在一種數(shù)據(jù)類型中的所有可能元素的集合。而“數(shù)據(jù)結(jié)構(gòu)”，大致上說來，就是數(shù)據(jù)實(shí)體中元素之間的關(guān)系，包括數(shù)據(jù)的表示法和運(yùn)算。”特點(diǎn)：指出“關(guān)系”為表示法和運(yùn)算。4.陳慧南，《數(shù)據(jù)結(jié)構(gòu)——C語言描述》，西安電子科技大學(xué)出版社，2003年“從數(shù)學(xué)概念上講，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。研究數(shù)據(jù)結(jié)構(gòu)是為了解決應(yīng)用問題，所以討論數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的相關(guān)運(yùn)算及其算法才有意義?！碧攸c(diǎn)：從邏輯聯(lián)系入手，兼顧其它方面。1.1什么是數(shù)據(jù)結(jié)構(gòu)10計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算則要依靠數(shù)據(jù)結(jié)構(gòu)。同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有明顯的差異。程序設(shè)計(jì)實(shí)質(zhì)=好算法+好結(jié)構(gòu)二、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的用處1.1什么是數(shù)據(jù)結(jié)構(gòu)11是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程數(shù)學(xué)硬件軟件三、數(shù)據(jù)結(jié)構(gòu)課程的地位1.1什么是數(shù)據(jù)結(jié)構(gòu)12數(shù)據(jù)--是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有（Data）

能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(整數(shù)、實(shí)數(shù)、字符串、圖像、聲音等)。數(shù)據(jù)元素--是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義，（DataElement）在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理(又稱記錄、結(jié)點(diǎn)等)。數(shù)據(jù)項(xiàng)--一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，是數(shù)據(jù)的（DataItem）不可分割的最小單位(又稱字段等)。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：學(xué)生檔案>個(gè)人記錄>姓名、性別、籍貫…1.2基本概念和術(shù)語13數(shù)據(jù)對(duì)象（DataObject）--是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)（DataStructure）--是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

表示為：

Data_Structure=(D,S)元素有限集關(guān)系有限集例1：用數(shù)據(jù)結(jié)構(gòu)表示一周中的七天。Data_Structure=(D,S),其中，D={}S={}Mon,Tue,Wen,Thu,Fri,Sat,Sun<Mon,Tue>,<Tue,Wen>,<Wen,Thu>…1.2基本概念和術(shù)語14THANKYOUSUCCESS12/12/202315可編輯（1）Data_Structure=(D,S)，其中，

D={01，02，03，04，05}S={}（2）S=(D,R)D={a,b,c,d,e,f

}R={<a,e>,<

b,c>,<

c,a>,<

e,f>,<

f,d>}解:

上述表達(dá)式可用圖形表示為：aebcfd例2：將下述表達(dá)式用圖形的形式表示出來集合結(jié)構(gòu)線性結(jié)構(gòu)1.2基本概念和術(shù)語16（3）

Data_Structure=(D,S),其中，

D={01，02，03，04，05，06，07}S={(01,02)，(01,03)，(01,04)，(02,05)，(02,06)，(03,07)}（4）S=(D,R)

D={di|1≤i≤5,1≤j≤5}

R={<di,dj>,i<j}d1d2d3d4d501020304050607樹形結(jié)構(gòu)圖狀結(jié)構(gòu)1.2基本概念和術(shù)語17邏輯結(jié)構(gòu)--數(shù)據(jù)元素之間的邏輯關(guān)系，即結(jié)構(gòu)中定義的“關(guān)系”。邏輯結(jié)構(gòu)可細(xì)分為4類：集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)一對(duì)一關(guān)系一對(duì)多關(guān)系多對(duì)多關(guān)系非線性結(jié)構(gòu)1.2基本概念和術(shù)語1801000101物理結(jié)構(gòu)--也稱存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（映像）。順序映像非順序映像特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。特點(diǎn)是借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。例：復(fù)數(shù)3.0-2.3i的存儲(chǔ)形式3.0-20-2.3算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)----順序存儲(chǔ)結(jié)構(gòu)----鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.2基本概念和術(shù)語19數(shù)據(jù)類型--是一個(gè)值的集合和定義在這個(gè)值集上的一組操作

的總稱。抽象數(shù)據(jù)類型—由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型組成，并包含一組相關(guān)的操作。抽象數(shù)據(jù)類型可用ADT=（D，S，P）三元組表示數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉基本操作：〈基本操作的定義〉

}ADT抽象數(shù)據(jù)類型名ADT常用定義格式1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)20例：給出自然數(shù)（NaturalNumber）的抽象數(shù)據(jù)類型定義。IsZero(x):Booleanif(x==0)返回Trueelse返回FalseAdd(x,y):NaturalNumberif(x+y<=MaxInt)返回x+yelse返回MaxIntSubtract(x,y):NaturalNumberif(x<y)返回0else返回x-yEqual(x,y):Booleanif(x==y)返回Trueelse返回FalseADTNaturalNumber

{}NaturalNumber數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:數(shù)據(jù)操作:一個(gè)整數(shù)的有序子集合,它開始于0,結(jié)束于機(jī)器能表示的最大整數(shù)。1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)21一、算法：算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。二、算法的5個(gè)特性：

有窮性、確定性、可行性、輸入和輸出三、算法設(shè)計(jì)的要求：

正確性、可讀性、健壯性、效率與低存儲(chǔ)需求時(shí)間復(fù)雜度空間復(fù)雜度1.4算法和算法分析221.4算法和算法分析算法效率的度量方法事后統(tǒng)計(jì)方法事前分析估算算法采用的策略、方法編譯產(chǎn)生的代碼質(zhì)量問題的輸入規(guī)模機(jī)器執(zhí)行指令的速度時(shí)間復(fù)雜度：一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中語句的執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度，記為T(n)。算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作

T（n）=O（f（n））隨著問題規(guī)模的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，稱為算法的漸近時(shí)間復(fù)