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

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

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

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

4、素由一個(gè)數(shù)據(jù)項(xiàng)組成，所謂數(shù)據(jù)項(xiàng)就是數(shù)據(jù)中不可再分割的最小單位；復(fù)雜型數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念的多方面信息。數(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í)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）=（散列、索引）是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的具體實(shí)現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。常見的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：特點(diǎn)是借助于數(shù)

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

6、之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。 （3）動(dòng)態(tài)性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。舉例問題：按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容。算法：（1）輸入x，y，z三個(gè)數(shù)值；（2）從三個(gè)數(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è)計(jì)語言。 "類C"描述語言是通過對(duì)C語言進(jìn)行精心篩選保留的一個(gè)核心子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語言的描述功能。(略介紹)（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ù)中使用的局部變量可以不做變量說明，必要時(shí)給出相應(yīng)的注釋即可。另外，在書寫算法時(shí)，應(yīng)該養(yǎng)成對(duì)重點(diǎn)語句段落添加注解的良好習(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);方括號(hào)（ ）中的內(nèi)容是可以省略的部分。（8）在算法描述中使用的注釋格式為：單行注釋 /文字序列（9）在算法描述中可以

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

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