數(shù)據(jù)結(jié)構(gòu)c語言版

1、第一章 緒論,1.3 算法和算法的描述,1.1 什么是數(shù)據(jù)結(jié)構(gòu),1.2 基本概念和術(shù)語,1.1 什么是數(shù)據(jù)結(jié)構(gòu),當(dāng)今計算機應(yīng)用的特點：l計算機應(yīng)用領(lǐng)域從科學(xué)計算到非數(shù)值計算,更多地是需要對其進(jìn)行組織、管理和檢索; l所處理的數(shù)據(jù)量大且具有一定的關(guān)系.,下面舉幾個非數(shù)值計算的例子,例1 學(xué)生檔案管理系統(tǒng),假設(shè)一個學(xué)生檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息,特點：,l每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排

2、列構(gòu)成一張表格； l表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； l對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。,例2 人機對奕問題,,,,,,,,,,例3 制定教學(xué)計劃,在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機專業(yè)課程的開設(shè)情況如下表

3、所示：,課程先后關(guān)系的圖形描形式：,特點： 課程之間的先后關(guān)系用圖結(jié)構(gòu)描述； 通過實施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點進(jìn)行線性排序。,結(jié)論 計算機的操作對象的關(guān)系復(fù)雜，操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理，我們將此稱為非數(shù)值性處理。要使計算機能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些數(shù)據(jù)之間的關(guān)系，在計算機中的存儲方式以及各個操作的具體實現(xiàn)。,數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為：

4、 研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。,課程目的能夠分析研究計算機加工的對象的特性，獲得其邏輯結(jié)構(gòu)，根據(jù)需求，選擇合適存貯結(jié)構(gòu)及其相應(yīng)的算法；學(xué)習(xí)一些常用的算法；復(fù)雜程序設(shè)計的訓(xùn)練過程，要求編寫的程序結(jié)構(gòu)清楚和正確易讀；初步掌握算法的時間分析和空間分析技術(shù)。,1.2 基本概念和術(shù)語,一、基本概念,二、數(shù)據(jù)類型,三、抽象數(shù)據(jù)類型,數(shù)據(jù):所有能被輸入到計算機中，且能被計算機

5、處理的符號的集合。不僅包括數(shù)字、字符串，還包括圖形、圖像、聲音、動畫、視頻等數(shù)據(jù)形式。數(shù)據(jù)元素:數(shù)據(jù)的基本單位，也稱結(jié)點（node）或記錄（record） 。數(shù)據(jù)項:是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。,,,數(shù)據(jù)元素,,,數(shù)據(jù)項,一、基本概念,三者之間的關(guān)系：數(shù)據(jù) > 數(shù)據(jù)元素 > 數(shù)據(jù)項,例：學(xué)生表 > 個人記錄 > 學(xué)號、姓名……,4. 數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集

6、合，是數(shù)據(jù)的一個子集。,整數(shù)數(shù)據(jù)對象 N = { 0, ?1, ?2, … }學(xué)生數(shù)據(jù)對象 學(xué)生記錄的集合,5、數(shù)據(jù)結(jié)構(gòu)（Data Structure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。,數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。,6 邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中所說的“關(guān)系”實際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。,集合數(shù)據(jù)元素間

7、除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu) 一對一的關(guān)系， 如線性表、棧、隊列樹型結(jié)構(gòu) 一對多的關(guān)系，如樹圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 多對多的關(guān)系，如圖。,,數(shù)據(jù)之間的關(guān)系分為四類：,7.存儲結(jié)構(gòu)（物理結(jié)構(gòu)） ：數(shù)據(jù)在計算機中的存儲表示。,鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。 (可以占用不連續(xù)的存儲單元）,,分為兩種：,順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示 數(shù)據(jù)元素間的邏輯關(guān)

8、系。(占用連續(xù)的存儲單元）,順序存儲結(jié)構(gòu),鏈?zhǔn)酱鎯Y(jié)構(gòu),邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同, 但運算不同, 則數(shù)據(jù)結(jié)構(gòu)不同. 例如, 棧與隊列對于一種數(shù)據(jù)結(jié)構(gòu), 常見的運算插入刪除修改查找排序,數(shù)據(jù)的運算,,,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的運算：插入、刪除、修改、查找、排序,,,,,線性結(jié)構(gòu),非線性結(jié)構(gòu),順序存儲,鏈?zhǔn)酱鎯?線性表,棧、隊列,串、數(shù)組,樹形結(jié)構(gòu),圖形結(jié)構(gòu),邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴

9、于存儲結(jié)構(gòu),,二、數(shù)據(jù)類型,數(shù)據(jù)類型 是一個值的集合和定義在此集合上的一組操作的總稱。,在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進(jìn)行的運算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)計中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。,C語言：　基本數(shù)據(jù)類型： char int float double void　構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、文件,三、抽象數(shù)據(jù)類型 (Abstract D

10、ata Type 簡稱ADT),是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。,抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組操作。,ADT 有兩個重要特征:,數(shù)據(jù)抽象,用ADT描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。,數(shù)據(jù)封裝,將實體的外部特性和其內(nèi)部實現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細(xì)節(jié)。,抽象數(shù)據(jù)類型可以用以

11、下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象 D上的關(guān)系集 D上的操作集,ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作 ： } ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,,,,抽象數(shù)據(jù)類型的描述方法,例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：,數(shù)據(jù)對象： D＝{e1,e2｜e

12、1,e2∈RealSet } 數(shù)據(jù)關(guān)系： R1＝{ | e1是復(fù)數(shù)的實數(shù)部分 | e2 是復(fù)數(shù)的虛數(shù)部分 },ADT Complex {,基本操作：,AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實部和虛部 分別被賦以參數(shù) v1 和 v2 的值。,DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z

13、被銷毀。,GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實部值。,GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。,Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1, z2 的和值。,} ADT Complex,假設(shè):z1

14、和z2是上述定義的復(fù)數(shù),則 Add(z1, z2, z3) 操作的結(jié)果,z3 = z1 + z2,即為用戶企求的結(jié)果,抽象數(shù)據(jù)類型的表示與實現(xiàn),抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。,教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具,但上機時要用具體語言實現(xiàn)，如C或C++等,例如，對前面定義的復(fù)數(shù)。,typedef struct { float realpart； float

15、 imagpart；}complex；,// -----存儲結(jié)構(gòu)的定義,// -----基本操作的實現(xiàn),void add( complex z1, complex z2, complex &sum ) { // 以 sum 返回兩個復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart;

16、 sum.imagpart = z1.imagpart + z2.imagpart;},{ 其它省略 },,1.3 算法和算法的衡量,一、算法,二、算法設(shè)計的原則,三、算法效率的衡量方法和準(zhǔn)則,四、算法的描述,算法是對特定問題求解步驟的一種描述，是指令的有限序列。,一、算法,計算機對數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。,設(shè)計算

17、法的基本過程,通過對問題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型；確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計對此數(shù)據(jù)結(jié)構(gòu)實施各種操作的算法；選用某種語言將算法轉(zhuǎn)換成程序；調(diào)試并運行這些程序。例如：復(fù)數(shù)運算的實現(xiàn),一個算法必須滿足以下五個重要特性：,1．有窮性: 一個算法必須總是在執(zhí)行有窮步之后結(jié)束， 且每一步都在有窮時間內(nèi)完成。2．確定性：算法的每一步必須是確切定義的， 不能產(chǎn)生二義性 3

18、．可行性：算法是能夠?qū)崿F(xiàn)的.即算法描述的操作都是可以 通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。4．有輸入：一個算法有零個或多個輸入 5．有輸出：一個算法有零個或多個輸出,二、算法設(shè)計的原則,設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：,1．正確性:,2. 可讀性:,3．健壯性:,4．高效率與低存儲量需求,效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。,標(biāo)準(zhǔn)：通常對于精心選擇的典型、苛刻而

19、帶有刁難性的幾組輸入數(shù)據(jù)程序能夠得出滿足規(guī)格說明要求的結(jié)果。,算法應(yīng)易于閱讀和理解，以便于調(diào)試和修改。,算法應(yīng)具有容錯處理。當(dāng)輸入數(shù)據(jù)非法時，算法能做出適當(dāng)?shù)姆磻?yīng)和進(jìn)行特殊處理，而不是產(chǎn)年莫名其妙的輸出結(jié)果。,三、算法效率的衡量方法和準(zhǔn)則,通常有兩種衡量算法效率的方法:,事后統(tǒng)計法：,事前分析估算法,1.事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分,缺點：?必須先運行依據(jù)算法編制的程序?所得時間

20、統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣,2.事前分析估計：一個高級語言程序在計算機上運行所消耗的時間取決于： ?依據(jù)的算法選用何種策略 ?問題的規(guī)模 ?程序語言 ?編譯程序產(chǎn)生機器代碼質(zhì)量 ?機器執(zhí)行指令速度,同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———使用絕對時間單位衡量算法效率不合適,算法 = 控制結(jié)構(gòu) + 基本操作,算法的執(zhí)行時間

21、 =基本操作(i)的執(zhí)行次數(shù)×基本操作(i)的執(zhí)行時間,算法的執(zhí)行時間 與 基本操作執(zhí)行次數(shù)之和 成正比,如何估算算法的時間復(fù)雜度？,從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運行時間的衡量準(zhǔn)則。,算法中基本操作（循環(huán)）重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),它是一個算法運行時間的相對量度,算法的時間量度記作： T(n)

22、=O(f(n)),時間復(fù)雜度的漸進(jìn)表示法,它表示隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同，T(n) 稱作算法的(漸近)時間復(fù)雜度。,例1：,{++x;s=0;},1,O(1),for(i=1;i<=n;++i){++x;s+=x;},n,O(n),for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;},n*n,O(n2),例2：,例3：,頻度,時

23、間復(fù)雜度,程序,,,,,,,,時間復(fù)雜度的計算：,例4：,void mult(int a[], int b[], int& c[] ) { // 以二維數(shù)組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i,j] = 0; for (k=1; k<=n; ++k)

24、 c[i,j] += a[i,k]*b[k,j];//語句的頻度: 重復(fù)執(zhí)行的次數(shù)：n3; } //for} //mult,基本操作: 乘法操作,時間復(fù)雜度: O(n3),T( n ) = O ( n 3)即：矩陣乘法的運算量和問題的規(guī)模n的立方是同一個量級,,,,,x = 0; y = 0;for ( int k = 0; k < n; k ++ ) x ++;for ( in

25、t i = 0; i < n; i++ ) for ( int j = 0; j < n; j++ ) y ++;,T1(n) = O(1),T2(n) = O(n),T3(n) = O(n2),T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2),例5：,void exam ( float x[ ][ ], int m, int n

26、 ) { float sum [ ]; for ( int i = 0; i < m; i++ ) { //x中各行數(shù)據(jù)累加 sum[i] = 0.0; for ( int j = 0; j < n; j++ ) sum[i] += x[i][j]; //關(guān)鍵操作 } for ( i = 0

27、; i < m; i++ ) //打印各行數(shù)據(jù)和 cout << i << “ : ” <<sum [i] << endl; //關(guān)鍵操作 },漸進(jìn)時間復(fù)雜度為 O(max (m*n, m)),算法的時間復(fù)雜度是由嵌套最深層語句的頻度決定的,例6：,for( i=1; i<=n; i++) for (j=1; j<=i; j++)

28、 for (k=1; k<=j; k++)　　　　x=x+1;,語句頻度 =,例7：,例8：分析以下程序段的時間復(fù)雜度,i=1; ①while(i<=n) i=i*2; ②,即f(n)≤log2n，取最大值f(n)=log2n,所以該程序段的時間復(fù)雜度T(n) =O( log2n),【例9】

29、順序查找，在數(shù)組a[i]中查找值等于e的元素，返回其所在位置。 for (i=0;i< n;i++) if (a[i]==e) return i+1; return 0;,有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同,最好情況：1次 最壞情況：n平均時間復(fù)雜度為:O(n),時間復(fù)雜度T(n)按數(shù)量級遞增順序為：,,復(fù)雜度高,復(fù)雜度低,指數(shù)時間的關(guān)系為： O(2

30、n)<O(n!)<O(nn),當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊,空間復(fù)雜度:算法所需存儲空間的度量，記作: S(n)=O(g(n)) 其中n為問題的規(guī)模(或大小),算法要占據(jù)的空間算法本身要占據(jù)的空間輸入數(shù)據(jù)所占空間算法要使用的輔助空間若輸入數(shù)據(jù)所占空間和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。,漸進(jìn)空間復(fù)雜度,一個算法可以用自然語

31、言、數(shù)字語言或約定的符號來描述，也可以用計算機高級程序語言來描述，如Pascal語言、C語言或偽代碼等。,本書選用C語言作為描述算法的工具。,四、算法的描述,1．預(yù)定義常量和類型：,簡單說明C語言的語法結(jié)構(gòu)：,typedef int ElemType;typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode,*LinkList;,//函數(shù)結(jié)果狀態(tài)代碼#defi

32、ne OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 // Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。 typedef int Status;,函數(shù)類型 函數(shù)名(參數(shù)表){ //算法說明 語句組 }/*函數(shù)名*/,2．函數(shù)的形式,簡單賦值：〈變量名〉=〈表達(dá)式〉，它表示將表達(dá)式的值賦給左邊的變量；

33、 〈變量〉++，它表示變量加1后賦值給變量； 〈變量〉--，它表示變量減1后賦值給變量；,3．賦值語句,成組賦值：1.（, ，…,）= （，，…,）；2.[下標(biāo)1…下標(biāo)2]=[下標(biāo)1…下標(biāo)2],串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉= 〈表達(dá)式〉；條件賦值：〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉：〈表達(dá)式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變

34、量2互換；,情況語句: switch （表達(dá)式） { case 值1；語句組1；break； case 值2；語句組2；break； …… case 值n；語句組n； break； [default：語句組；break；] },4．條件選擇語句,if （〈表達(dá)式〉） 語句；,if （〈表達(dá)式〉）語句1；else 語句2；,⑴ for語句

35、 for（表達(dá)式1；表達(dá)式2；表達(dá)式3） { 循環(huán)體語句；},5．循環(huán)語句,⑵ while語句,while （條件表達(dá)式） { 循環(huán)體語句；},⑶ do-while語句,do { 循環(huán)體語句 } while（條件表達(dá)式）,輸入語句：用函數(shù)scanf實現(xiàn)，當(dāng)數(shù)據(jù)為字符時，用getchar函數(shù)實現(xiàn)。輸出語句：用printf函數(shù)實現(xiàn)，當(dāng)要輸出字符數(shù)據(jù)時，用putchar函數(shù)實現(xiàn)。,6．輸入、輸出語句,

36、（1）return表達(dá)式或return：用于函數(shù)結(jié)束。（2）break語句：可用在循環(huán)語句或case語句中結(jié)束循環(huán)過程或跳出情況語句。（3）exit語句：表示出現(xiàn)異常情況時，控制退出語句。8．注釋形式 可用 /*字符串*/ 單行注釋 或 //文字序列。,7．其他一些語句,如： max函數(shù)，用于求一個或幾個表達(dá)式中的最大值； min函數(shù)，用于求一個或幾個表達(dá)式中的最小值； abs函數(shù)，用于求表