第一節(jié) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容

1．當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)
　　 所處理的數(shù)據(jù)量大且具有一定的關(guān)系；
　　 對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。
2．應(yīng)用舉例1--學(xué)籍檔案管理
假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。
學(xué)生基本情況

特點(diǎn)：
（1）每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格；
（2）表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說(shuō)的線性結(jié)構(gòu)；
（3）對(duì)它的操作通常是插入某個(gè)學(xué)生的信息，刪除某個(gè)學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。
3．應(yīng)用舉例2--輸出n個(gè)對(duì)象的全排列
輸出n個(gè)對(duì)象的全排列可以使用下圖所示的形式描述。

4．應(yīng)用舉例2--輸出n個(gè)對(duì)象的全排列

5．結(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ù)語(yǔ)

數(shù)據(jù)：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中其含義是指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)集合。
數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)實(shí)體，是計(jì)算機(jī)程序中加工處理的基本單位。
數(shù)據(jù)元素按其組成可分為簡(jiǎn)單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。簡(jiǎn)單型數(shù)據(jù)元素由一個(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)：簡(jiǎn)單地說(shuō)，就是相互之間存在一種或多種特定關(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)中所說(shuō)的"關(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)
(1)順序存儲(chǔ)結(jié)構(gòu)：特點(diǎn)是借助于數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)；
(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：特點(diǎn)是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。

第三節(jié) 算法

1．算法的概念
算法是解決某個(gè)特定問(wèn)題的一種方法或一個(gè)有限過(guò)程。
計(jì)算機(jī)對(duì)數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。
2．設(shè)計(jì)算法的基本過(guò)程
（1）通過(guò)對(duì)問(wèn)題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型；
（2）確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法；
（3）選用某種語(yǔ)言將算法轉(zhuǎn)換成程序；
（4）調(diào)試并運(yùn)行這些程序。
算法應(yīng)該具有下列五個(gè)特性
（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。
（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。
（3）動(dòng)態(tài)性：算法中描述的每一步操作都可以通過(guò)已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。
（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。
（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說(shuō)的輸出是指與輸入有某種特定關(guān)系的量。
舉例:
問(wèn)題：按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容。
算法：
（1）輸入x，y，z三個(gè)數(shù)值；
（2）從三個(gè)數(shù)值中挑選出最小者并換到x中；
（3）從y，z中挑選出較小者并換到y中；
（4）輸出排序后的結(jié)果。
3．算法的描述
3.1 選擇算法描述語(yǔ)言的準(zhǔn)則
（1）該語(yǔ)言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能；
（2）該語(yǔ)言應(yīng)該盡可能地簡(jiǎn)捷，以便于掌握、理解；
（3）使用該語(yǔ)言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計(jì)語(yǔ)言。
3.2 "類C"描述語(yǔ)言
"類C"描述語(yǔ)言是通過(guò)對(duì)C語(yǔ)言進(jìn)行精心篩選保留的一個(gè)核心子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語(yǔ)言的描述功能。(略介紹)
（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ù)表）
{
語(yǔ)句序列；
}
為了簡(jiǎn)化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說(shuō)明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說(shuō)明，必要時(shí)給出相應(yīng)的注釋即可。另外，在書寫算法時(shí)，應(yīng)該養(yǎng)成對(duì)重點(diǎn)語(yǔ)句段落添加注解的良好習(xí)慣。
（3）在算法描述中可以使用的賦值語(yǔ)句形式有：
簡(jiǎn)單賦值 變量名 = 表達(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）在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有：
條件語(yǔ)句1 if（表達(dá)式） 語(yǔ)句；
條件語(yǔ)句2 if（表達(dá)式） 語(yǔ)句；
else 語(yǔ)句；
開關(guān)語(yǔ)句1 switch（表達(dá)式）{
case 值1：語(yǔ)句序列1；break；
case 值2：語(yǔ)句序列2；break；
...
case 值n：語(yǔ)句序列n；break；
default：語(yǔ)句序列n+1；
}
開關(guān)語(yǔ)句2 switch{
case 條件1：語(yǔ)句序列1；break；
case 條件2：語(yǔ)句序列2；break；
...
case 條件n：語(yǔ)句序列n；break；
default：語(yǔ)句序列n+1；
}
（5）在算法描述中可以使用的循環(huán)結(jié)構(gòu)語(yǔ)句形式有：
for循環(huán)語(yǔ)句 for（表達(dá)式1；循環(huán)條件表達(dá)式；表達(dá)式2）語(yǔ)句；
while循環(huán)語(yǔ)句 while（循環(huán)條件表達(dá)式）語(yǔ)句；
do-while循環(huán)語(yǔ)句 do{
語(yǔ)句序列；
} while（循環(huán)條件表達(dá)式）；
（6）在描述算法中可以使用的結(jié)束語(yǔ)句形式有：
函數(shù)結(jié)束語(yǔ)句 return 表達(dá)式；
return;
case或循環(huán)結(jié)束語(yǔ)句 break;
異常結(jié)束語(yǔ)句 exit（異常代碼）；
（7）在算法描述中可以使用的輸入輸出語(yǔ)句形式有：
輸入語(yǔ)句 scanf([格式串]，變量名1，...，變量名n)；
輸出語(yǔ)句 printf([格式串]，表達(dá)式1，...，表達(dá)式n);
方括號(hào)（[ ]）中的內(nèi)容是可以省略的部分。
（8）在算法描述中使用的注釋格式為：
單行注釋 //文字序列
（9）在算法描述中可以使用的擴(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é)果中的最小值。
【舉例】用類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=*z;
if(*z<*y) *y=*z; //在y和z所指示存儲(chǔ)單元中挑選出較小者換到y中
}
4．算法的評(píng)價(jià)
算法的評(píng)價(jià)標(biāo)準(zhǔn)：
（1）正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。
（2）可讀性：為了便于理解、測(cè)試和修改算法，算法應(yīng)該具有良好的可讀性。
（3）健壯性：算法中擁有對(duì)輸入數(shù)據(jù)、打開文件、讀取文件記錄、分配內(nèi)存空間等操作的結(jié)果檢測(cè)，并通過(guò)與用戶對(duì)話的形式做出相應(yīng)的處理選擇。
（4）時(shí)間與空間效率：算法的時(shí)間與空間效率是指將算法變換為程序后，該程序在計(jì)算機(jī)上運(yùn)行時(shí)所花費(fèi)的時(shí)間及所占據(jù)空間的度量。
算法的時(shí)間效率：
算法的時(shí)間效率主要由兩個(gè)因素決定：
　　 ①所需處理問(wèn)題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費(fèi)的時(shí)間就多；
　　 ②在解決問(wèn)題的過(guò)程中，基本操作的執(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增長(zhǎng)的同時(shí)，函數(shù)T(n)的增長(zhǎng)速度比較緩慢。
空間效率的分析
一個(gè)算法的空間效率是指在算法的執(zhí)行過(guò)程中，所占據(jù)的輔助空間數(shù)量。輔助空間就是除算法代碼本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時(shí)開辟的存儲(chǔ)空間單元。在有些算法中，占據(jù)輔助空間的數(shù)量與所處理的數(shù)據(jù)量有關(guān)，而有些卻無(wú)關(guān)。后一種是較理想的情況。在設(shè)計(jì)算法時(shí)，應(yīng)該注意空間效率。