清華大學(xué)計算機(jī)系列教材

清華大學(xué)計算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社嚴(yán)蔚敏吳偉民編著累計發(fā)行超100萬冊11.教學(xué)目的學(xué)會分析研究計算機(jī)加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)的算法。2.教學(xué)內(nèi)容3.教學(xué)要求初步掌握算法的時間分析、空間分析技巧。進(jìn)行復(fù)雜程序設(shè)計的訓(xùn)練。本書研究信息在計算機(jī)中的組織和表示方法。詳細(xì)介紹了線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹以及圖等幾種基本類型的數(shù)據(jù)結(jié)構(gòu)，以及在程序設(shè)計中經(jīng)常遇到的兩個問題——查找和排序。上課認(rèn)真聽課，課后按時獨(dú)立完成作業(yè)。理論、習(xí)題、上機(jī)緊密結(jié)合。2第一章緒論第二章線性表第三章棧和隊(duì)列第四章串第五章數(shù)組和廣義表第六章樹和二叉樹第七章圖第八章動態(tài)存儲管理第九章查找第十章內(nèi)部排序第十一章外部排序第十二章文件3※一元多項(xiàng)式相加※括號匹配的檢驗(yàn)※車廂調(diào)度問題※迷宮求解※表達(dá)式求值※哈夫曼編碼※最小生成樹※關(guān)鍵路徑※最短路徑※查找※排序各種數(shù)據(jù)結(jié)構(gòu)在實(shí)際中的應(yīng)用：42、北京大學(xué)>>信息科學(xué)技術(shù)學(xué)院>>計算機(jī)軟件與理論>>計算機(jī)軟件基礎(chǔ)（含操作系統(tǒng)、編譯原理、數(shù)據(jù)結(jié)構(gòu)）3、北京大學(xué)>>信息科學(xué)技術(shù)學(xué)院>>計算機(jī)系統(tǒng)結(jié)構(gòu)>>數(shù)據(jù)結(jié)構(gòu)4、北京大學(xué)>>信息科學(xué)技術(shù)學(xué)院>>計算機(jī)應(yīng)用技術(shù)>>數(shù)據(jù)結(jié)構(gòu)5、北京工業(yè)大學(xué)>>計算機(jī)學(xué)院>>計算機(jī)軟件與理論>>數(shù)據(jù)結(jié)構(gòu)與C++程序設(shè)計1、北京航空航天大學(xué)>>計算機(jī)學(xué)院>>計算機(jī)應(yīng)用技術(shù)>>數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研科目（考研共濟(jì)網(wǎng)）：7、廣西民族大學(xué)081203計算機(jī)應(yīng)用技術(shù)01智能計算技術(shù)及應(yīng)用02人工智能理論及應(yīng)用03模式識別與智能系統(tǒng)04數(shù)據(jù)挖掘與知識工程05數(shù)字圖像處理12

①101政治理論②201英語③301數(shù)學(xué)一④829c語言程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)6、廣西大學(xué)①101政治②201英語③301數(shù)學(xué)（一）④854專業(yè)基礎(chǔ)課1《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏等清華大學(xué)出版社《離散數(shù)學(xué)》耿素云等高等教育出版社5第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法的描述和算法分析61.1什么是數(shù)據(jù)結(jié)構(gòu)例子1：圖書館的書目檢索系統(tǒng)自動化問題。

001高等數(shù)學(xué)樊映川S01…002理論力學(xué)羅遠(yuǎn)祥L01…003高等數(shù)學(xué)華羅庚S01…004線性代數(shù)欒汝書S02………………高等數(shù)學(xué)001,003,…理論力學(xué)002，…線性代數(shù)004，……樊映川001，…華羅庚003，…欒汝書004，……L002,…S001,003,……計算機(jī)處理的對象之間存在著一種簡單的線性關(guān)系，稱為線性數(shù)據(jù)結(jié)構(gòu)。7例子2：計算機(jī)和人對奕問題?！痢?a)棋盤格局示例×××××××××××××××××(b)對奕樹的局部×××××××××××計算機(jī)處理的對象之間存在一種倒長“樹”的關(guān)系，稱為樹數(shù)據(jù)結(jié)構(gòu)。8例子3：多叉路口交通燈的管理問題。ABCDE路口有13條可行的通路：ABACADBABCBDDADBDCEAEBECEDABACADBABCBDDADBDCEAEBECEDABACADBABCBDDADBDCEAEBECED計算機(jī)處理的對象之間存在一種圖的關(guān)系，稱為圖數(shù)據(jù)結(jié)構(gòu)。演示91.2基本概念和術(shù)語數(shù)據(jù)——是對客觀事務(wù)的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。例子：數(shù)值數(shù)據(jù)。學(xué)號姓名語文數(shù)學(xué)C語言6201001張三8554926201002李四9284646201003王五8774736201004

...

例子：圖像、聲音等。10數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)——多個數(shù)據(jù)項(xiàng)可組成一個數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。例子：例子：一條書目信息、一個棋盤格局、一個圓圈一條書目包含登錄號、書名、作者名、…11數(shù)據(jù)對象——是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例子：整數(shù)數(shù)據(jù)對象N={0，+-1，+-2，…}

字母字符數(shù)據(jù)對象C={‘A’，‘B’，…’Z’}

全班學(xué)生的成績表G={（6201001，張三，85，54，92），（6201002，李四，92，84，64），

……}數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。四類基本結(jié)構(gòu)：（1）集合（2）線性結(jié)構(gòu)（3）樹形結(jié)構(gòu)（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)12集合線性樹圖數(shù)據(jù)結(jié)構(gòu)的形式定義：一個二元組：Data-Structure=(D,S)D：是數(shù)據(jù)元素的有限集。S：是D上關(guān)系的有限集。13例子1：在計算機(jī)科學(xué)中，復(fù)數(shù)數(shù)據(jù)結(jié)構(gòu)的定義：一個二元組：Complex=(C,R)C={c1,c2}R={〈C1，C2〉}；C1表示復(fù)數(shù)的實(shí)部，C2表示復(fù)數(shù)的虛部。例子2：一個課題小組由一位教師，一至三名研究生及一至六名本科生組成；成員之間的關(guān)系是教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至二名本科生。一個二元組：Group=(P,R)P={T，G1，…，Gn，S11，…，Snm|1≦n≦3，1≦m≦2}R={R1，R2}R1={〈T，Gi〉|1≦i≦n，1≦n≦3}R2={〈Gi

，Sij〉|1≦i≦n，1≦j≦m，1≦n≦n3，1≦m≦2}140300030103020303…………數(shù)據(jù)元素邏輯結(jié)構(gòu)：存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的二元組定義只是對操作對象的一種數(shù)學(xué)描述，反映的是數(shù)據(jù)元素之間的邏輯關(guān)系，所以稱為數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為物理結(jié)構(gòu)。又稱存儲結(jié)構(gòu)。數(shù)據(jù)元素的表示數(shù)據(jù)的結(jié)構(gòu)的表示結(jié)點(diǎn)數(shù)據(jù)域15順序映象——是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。例子：表示復(fù)數(shù)z1=3.0-2.3i和z2=-0.7+4.8i……0300030206320634…3.0-2.3-0.74.8非順序映象——是借助指針表示數(shù)據(jù)元素之間的邏輯關(guān)系?！?415061106133.00415-2.3算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)算法的實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)的表示:16數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)的描述——二元組（D，S）存儲結(jié)構(gòu)的描述——+操作高級語言中的“數(shù)據(jù)類型”17數(shù)據(jù)類型——是一個值的集合和定義在這個值上的一組操作的總稱。例子：整數(shù)類型值的集合：{-maxint,maxint}

定義在值上的操作：+-*/mod數(shù)據(jù)類型：（1）原子數(shù)據(jù)類型（2）結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型——是指數(shù)學(xué)模型以及定義在該模型上的一組操作。它可以通過固有的數(shù)據(jù)類型來表示和實(shí)現(xiàn)。抽象數(shù)據(jù)類型：（1）原子數(shù)據(jù)類型（2）固定聚合類型（3）可變聚合類型18數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)的描述——二元組（D，S）(存儲結(jié)構(gòu)+操作)的描述——高級語言中的“數(shù)據(jù)類型”抽象數(shù)據(jù)類型ADT定義——三元組（D，S，P）表示實(shí)現(xiàn)19抽象數(shù)據(jù)類型的形式定義-----三元組：（D,S,P）

D–數(shù)據(jù)對象;S–D上的關(guān)系;P–對D的基本操作集；ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：＜數(shù)據(jù)對象的定義＞

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

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

｝ADT抽象的數(shù)據(jù)類型名基本操作的定義格式為：

基本操作名（參數(shù)表）

初始條件：＜初始條件描述＞

操作結(jié)果：＜操作結(jié)果描述＞

用偽碼表示20例子：抽象數(shù)據(jù)類型復(fù)數(shù)的定義。數(shù)據(jù)對象：C＝{C1，C2|C1∈R，C2∈R}數(shù)據(jù)關(guān)系：R＝{<C1,C2>}基本操作：

create(&z,x,y)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z，實(shí)部值為x，虛部值為yadd(z1,z2,&sum)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1與z2的和，用sum返回值

subtract(z1,z2,&difference)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1與z2的差，用difference返回值

ADTComplex{21multiply(z1,z2,&product)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1和z2的乘積，用product返回值

get-realpart(z，&x)

初始條件：復(fù)數(shù)z已存在操作結(jié)果：求復(fù)數(shù)z的實(shí)部，用x返回值get-imagpart(z，&y)

初始條件：復(fù)數(shù)z已存在操作結(jié)果：求復(fù)數(shù)z的虛部，用y返回值}ADTComplex22例子：抽象數(shù)據(jù)類型三元組triplet的定義：ADTTriplet{數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3∈Elemset}數(shù)據(jù)關(guān)系：R1={＜e1,e2＞，＜e2,e3＞}基本操作：

InitTriplet(&T,v1,v2,v3)

初始條件:

操作結(jié)果:構(gòu)造三元組T,元素e1,e2和e3分別被賦予參數(shù)v1,v2和v3的值。DestroyTriplet(&T)

初始條件:三元組T已經(jīng)存在。操作結(jié)果:銷毀三元組T。23

Get(T,i,&e)

初始條件:三元組T已經(jīng)存在,1<=i<=3。

操作結(jié)果:用e返回三元組T的第i個元素。Put(&T,i,e)

初始條件:三元組T已經(jīng)存在,1<=i<=3。操作結(jié)果:用e值取代三元組T的第i個元素。IsAscending(T)

初始條件:三元組T已經(jīng)存在。操作結(jié)果:如果三元組T的三個元素按升序排列,則返回TRUE;否則返回FALSE。24Max(T,&e)

初始條件:三元組T已經(jīng)存在,。操作結(jié)果:用e返回三元組T的最大值。Min(T,&e)

初始條件:三元組T已經(jīng)存在,。操作結(jié)果:用e返回三元組T的最小值。

｝ADTTripletIsDescending(T)

初始條件:三元組T已經(jīng)存在。操作結(jié)果:如果三元組T的三個元素按降序排列,則返回TRUE;否則返回FALSE。25數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)的描述——二元組（D，S）存儲結(jié)構(gòu)的描述——高級語言中的“數(shù)據(jù)類型”抽象數(shù)據(jù)類型ADT形式定義——三元組（D，S，P）表示和實(shí)現(xiàn)——用已有的數(shù)據(jù)類型定義新的結(jié)構(gòu)，用已實(shí)現(xiàn)的操作組合新的操作261.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)類C語言（作了擴(kuò)充和修改）的表示如：預(yù)定義常量和類型＃defineTRUE1

＃defineFALSE0

＃defineOK1

＃defineERROR0

＃defineINFEASIBLE-1

＃defineOVERFLOW-2

typedef

intStatus

27（2）（3）（4）。。。。。。（11）P11～1228例：抽象數(shù)據(jù)類型三元組triplet的表示和實(shí)現(xiàn)：Typedef

Elemtype*triplet;StatusInitTriplet(triplet&T,Elemtypev1,

Elemtypev2,Elemtypev3);//操作結(jié)果：……StatusDestroyTriplet(triplet&T);……StatusMin(tripletT,Elemtype&e);StatusInitTriplet(triplet&T,Elemtypev1,

Elemtypev2,Elemtypev3){}StatusDestroyTriplet(triplet&T){}…….StatusMin(tripletT,Elemtype&e){}存儲結(jié)構(gòu)函數(shù)的原型說明函數(shù)的實(shí)現(xiàn)表示實(shí)現(xiàn)29課堂作業(yè)：寫出抽象數(shù)據(jù)類型復(fù)數(shù)的定義、表示和實(shí)現(xiàn)。數(shù)據(jù)對象：C＝{C1，C2|C1∈R，C2∈R}數(shù)據(jù)關(guān)系：R＝{<C1,C2>}基本操作：

create(&z,x,y)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z，實(shí)部值為x，虛部值為yadd(z1,z2,&sum)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1與z2的和，用sum返回值

subtract(z1,z2,&difference)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1與z2的差，用difference返回值

ADTComplex{multiply(z1,z2,&product)

初始條件：復(fù)數(shù)z1,z2已存在操作結(jié)果：求復(fù)數(shù)z1和z2的乘積，用product返回值

get-realpart(z，&x)

初始條件：復(fù)數(shù)z已存在操作結(jié)果：求復(fù)數(shù)z的實(shí)部，用x返回值get-imagpart(z，&y)

初始條件：復(fù)數(shù)z已存在操作結(jié)果：求復(fù)數(shù)z的虛部，用y返回值}ADTComplexTypedef

Elemtype*Complex;Statuscreate(Complex&z,Elemtypex,

Elemtypey);//操作結(jié)果：……Statusadd(Complexz1,Complexz2,Complex&sum)……Statusget-imagpart(Complex

z,Elemtype&y)Statuscreate(Complex&z,Elemtypex,

Elemtypey);{…}Statusadd(Complexz1,Complexz2,Complex&sum)……Statusget-imagpart(Complex

z,Elemtype&y){…}301.4算法和算法分析算法的描述（1）自然語言（2）專用工具（3）程序設(shè)計語言流程圖表格偽代碼算法——是對特定問題求解步驟的一種描述。算法的五個特性：（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出類C語言31算法設(shè)計的要求：（1）正確性

a.程序不含語法錯誤

b.程序?qū)捉M輸入有正確輸出

c.程序?qū)捉M典型、苛刻的輸入有正確輸出

d.程序?qū)σ磺泻戏ㄝ斎胗姓_輸出

（2）可讀性（3）健壯性（4）高效率與低存儲量需求321.4.3算法效率的度量一個程序的執(zhí)行時間通常有兩種方法：(1)事后統(tǒng)計的方法。缺點(diǎn)：不利于較大范圍內(nèi)的算法比較。（異地，異時，異境）(2)事前分析估算的方法。一個程序的執(zhí)行時間取決于以下因素：（1）算法的策略（2）問題的規(guī)模（3）書寫程序的語言（4）編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量（5）機(jī)器執(zhí)行指令的速度33算法的時間量度：從算法中選取一種原操作（對于所研究的問題來說是基本運(yùn)算），以該基本操作重復(fù)執(zhí)行的次數(shù)

(執(zhí)行頻度）作為算法的時間量度。例子1：兩個N×N矩陣相乘的算法。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]+=a[i][k]*b[k][j];}基本運(yùn)算：基本運(yùn)算的執(zhí)行頻度：乘法n*n*n34T(n)=O(f(n))上示表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同。T（n）=O（）算法的漸近時間復(fù)雜度(時間復(fù)雜度):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]+=a[i][k]*b[k][j];}基本運(yùn)算：基本運(yùn)算的執(zhí)行頻度：乘法n*n*n時間復(fù)雜度：35例子4：for(i=2;i<=n;++i)for(j=2;j<=i-1;++j)++x;基本運(yùn)算：基本運(yùn)算的執(zhí)行頻度：X增1i=20i=31i=42…i=nn-2

1+2+3+…+(n-2)=(n-1)(n-2)/2T（n）=O（）例子2：++x;T（n）=O（1）例子3：for(i=1;i<=n;++i)++x;T（n）=O（n）時間復(fù)雜度：T(n)=O((n*n-3n+2)/2)基本運(yùn)算：基本運(yùn)算的執(zhí)行頻度：時間復(fù)雜度：1X增1基本運(yùn)算：基本運(yùn)算的執(zhí)行頻度：時間復(fù)雜度：X增1n36常見的時間復(fù)雜度：P16圖1.737例子5：For(i=1;i<=n;++i)for(j=1;j<=i;++j)for(k=1;k<=j;++k)++x;基本運(yùn)算：++x;基本運(yùn)算執(zhí)行頻度：算法的時間復(fù)雜度：38例子6：時間復(fù)雜度與輸入數(shù)據(jù)集有關(guān)的一個算法。Voidbubble-sort(int

a[],intn){for(i=n-1,change=true;i>=1&&change;--i){change=false;for(j=0;j<i;++j)if