第一章 數(shù)據(jù)結(jié)構(gòu)概論

1、第一章 數(shù)據(jù)結(jié)構(gòu)概論教學(xué)目的要求：了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計；時間和空間復(fù)雜度。教學(xué)內(nèi)容及學(xué)時分配： 1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 2、數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念 3、算法的概念、描述方法以及評價標(biāo)準(zhǔn)課時分配： 兩個學(xué)時 教學(xué)重點：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。教學(xué)難點：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復(fù)雜度及其計算第一節(jié) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當(dāng)今計算機應(yīng)用的特點： 所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 對其操作不再是單純的數(shù)值計算，而更多地是需要對其進(jìn)行組織、管理和檢索。應(yīng)用舉例1-學(xué)籍檔案管理假

2、設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。學(xué)生基本情況學(xué) 號姓 名性 別出生年月.99070101李 軍男80.12.99070102王顏霞女81.2.99070103孫 濤男80.9.99070104單曉宏男81.3.     特點： 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； 表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； 對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。應(yīng)用舉例2-輸出n個對象的全排列輸出n個對象的

3、全排列可以使用下圖所示的形式描述。結(jié)論計算機的操作對象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理，我們將此稱為非數(shù)值性處理。要使計算機能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點，在計算機中的表示方式以及各個操作的具體實現(xiàn)手段。這些就是數(shù)據(jù)結(jié)構(gòu)這門課程研究的主要內(nèi)容。第二節(jié) 基本概念和術(shù)語數(shù)據(jù) 是對客觀事物的符號表示。在計算機科學(xué)中其含義是指所有能夠輸入到計算機中并被計算機程序處理的符號集合。數(shù)據(jù)元素 是數(shù)據(jù)集合中的一個實體，是計算機程序中加工處理的基本單位。數(shù)據(jù)元素按其組成可分為簡單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。簡單型數(shù)據(jù)元

4、素由一個數(shù)據(jù)項組成，所謂數(shù)據(jù)項就是數(shù)據(jù)中不可再分割的最小單位；復(fù)雜型數(shù)據(jù)元素由多個數(shù)據(jù)項組成，它通常攜帶著一個概念的多方面信息。數(shù)據(jù)結(jié)構(gòu) 簡單地說，就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。=（集合關(guān)系）邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中所說的"關(guān)系"實際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）=（散列、索引）是指數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的具體實現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。常見的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：特點是借助于數(shù)

5、據(jù)元素的相對存儲位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)：特點是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。第三節(jié) 算法算法的概念算法是解決某個特定問題的一種方法或一個有限過程。 計算機對數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。設(shè)計算法的基本過程 通過對問題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型； 確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計對此數(shù)據(jù)結(jié)構(gòu)實施各種操作的算法； 選用某種語言將算法轉(zhuǎn)換成程序； 調(diào)試并運行這些程序。 算法應(yīng)該具有下列五個特性（1）有窮性：一個算法必須在執(zhí)行有窮步

6、之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產(chǎn)生二義性。 （3）動態(tài)性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實現(xiàn)。（4）輸入：一個算法應(yīng)該有零個或多個輸入。（5）輸出：一個算法應(yīng)該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。舉例問題：按從小到大的順序重新排列x，y，z三個數(shù)值的內(nèi)容。算法：（1）輸入x，y，z三個數(shù)值；（2）從三個數(shù)值中挑選出最小者并換到x中；（3）從y，z中挑選出較小者并換到y(tǒng)中；（4）輸出排序后的結(jié)果。算法的描述選擇算法描述語言的準(zhǔn)則（1）該語言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能；（2）該語言應(yīng)該盡可能地

7、簡捷，以便于掌握、理解；（3）使用該語言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計語言。 "類C"描述語言是通過對C語言進(jìn)行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴展修改，從而，增強了語言的描述功能。(略介紹)（1）預(yù)定義常量及類型(略介紹)#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1數(shù)據(jù)元素被約定為Elemtype 類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。（2）算法描述為以下的函數(shù)形式：函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）語句序列；為了簡化函

8、數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說明，必要時給出相應(yīng)的注釋即可。另外，在書寫算法時，應(yīng)該養(yǎng)成對重點語句段落添加注解的良好習(xí)慣。（3）在算法描述中可以使用的賦值語句形式有：簡單賦值 變量名 = 表達(dá)式；串聯(lián)賦值 變量名1 = 變量名2 = . = 變量名n = 表達(dá)式；成組賦值 （變量名1，.，變量名n）=（表達(dá)式1，.，表達(dá)式n）；結(jié)構(gòu)賦值 結(jié)構(gòu)名1 = 結(jié)構(gòu)名2；結(jié)構(gòu)名 =（值1，值2，.，值n）；條件賦值 變量名 = 條件表達(dá)式 ? 表達(dá)式1：表達(dá)式2；交換賦值 變量名1 " 變量名2；（4）在算法描

9、述中可以使用的選擇結(jié)構(gòu)語句形式有：條件語句1 if （表達(dá)式） 語句；條件語句2 if （表達(dá)式） 語句；else 語句；開關(guān)語句1 switch （表達(dá)式） case 值1：語句序列1；break；case 值2：語句序列2；break；.case 值n：語句序列n；break；default：語句序列n+1；開關(guān)語句2 switch case 條件1：語句序列1；break；case 條件2：語句序列2；break；.case 條件n：語句序列n；break；default：語句序列n+1；（5）在算法描述中可以使用的循環(huán)結(jié)構(gòu)語句形式有：for循環(huán)語句 for （表達(dá)式1；循環(huán)條件表達(dá)式；

10、表達(dá)式2） 語句；while循環(huán)語句 while （循環(huán)條件表達(dá)式） 語句；do-while循環(huán)語句 do 語句序列； while （循環(huán)條件表達(dá)式）；（6）在描述算法中可以使用的結(jié)束語句形式有：函數(shù)結(jié)束語句 return 表達(dá)式；return;case或循環(huán)結(jié)束語句 break;異常結(jié)束語句 exit（異常代碼）；（7）在算法描述中可以使用的輸入輸出語句形式有：輸入語句 scanf( 格式串，變量名1，.，變量名n)；輸出語句 printf( 格式串，表達(dá)式1，.，表達(dá)式n);方括號（ ）中的內(nèi)容是可以省略的部分。（8）在算法描述中使用的注釋格式為：單行注釋 /文字序列（9）在算法描述中可以

11、使用的擴展函數(shù)有： 求最大值 max（表達(dá)式1，.，表達(dá)式n）；這個函數(shù)返回參數(shù)表中n個表達(dá)式計算結(jié)果中的最大值。求最小值 min（表達(dá)式1，.，表達(dá)式n）；這個函數(shù)返回參數(shù)表中n個表達(dá)式計算結(jié)果中的最小值?！九e例1-4】用類C描述將三個數(shù)值排序的算法。viod Three_Sort( int *x,int *y,int *z)/將x,y,z三個指針?biāo)甘镜膬?nèi)容按從小到大的順序重新排列if (*y<*x&&*y<*z) *x"*y; /挑選出最小的數(shù)值并換到x指針?biāo)傅拇鎯卧衑lse if (*z<*x&&*z<*y) *x

12、"*z;if (*z<*y) *y"*z; /在y和z所指示的存儲單元中挑選出較小者換到y(tǒng)中算法的評價算法的評價標(biāo)準(zhǔn)（1） 正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。（2）可讀性：為了便于理解、測試和修改算法，算法應(yīng)該具有良好的可讀性。（3）健壯性：算法中擁有對輸入數(shù)據(jù)、打開文件、讀取文件記錄、分配內(nèi)存空間等操作的結(jié)果檢測，并通過與用戶對話的形式做出相應(yīng)的處理選擇。 （4）時間與空間效率：算法的時間與空間效率是指將算法變換為程序后，該程序在計算機上運行時所花費的時間及所占據(jù)空間的度量。算法的時間效率算法的時間效率主要由兩個因素決定： 所需處理問題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費的時間就多； 在解決問題的過程中，基本操作的執(zhí)行次數(shù)。時間特性的分析如果我們將一個算法所花費的時間設(shè)計成一個以數(shù)據(jù)量n為自變量的函數(shù)T(n)，這個函數(shù)在正整數(shù)定義域范圍內(nèi)一定是單調(diào)遞增的。好的算法應(yīng)該能夠在數(shù)據(jù)量n增長的同時，函數(shù)T(n)的增長速度比較緩慢?？臻g效率的分析一個算法的空間效率是指在算法的執(zhí)行過程中，所占據(jù)的輔助空間數(shù)量。輔助空間就是除算法代碼本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法