數(shù)據(jù)結(jié)構(gòu)-第1章 緒論

數(shù)據(jù)結(jié)構(gòu)

(DataStructure)使用教材指定教材：[1]嚴(yán)蔚敏等,《數(shù)據(jù)結(jié)構(gòu)(C語言版)》,清華大學(xué)出版社[2]嚴(yán)蔚敏等,《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》,清華大學(xué)出版社參考教材:[1]耿國華,《數(shù)據(jù)結(jié)構(gòu)》,高等教育出版社[2]楊秀金等,《數(shù)據(jù)結(jié)構(gòu)》,西安電子科技大學(xué)出版社[3]許卓群,《數(shù)據(jù)結(jié)構(gòu)》,高等教育出版社[4]唐策善等,《數(shù)據(jù)結(jié)構(gòu)》,高等教育出版社課程考核方式與要求本課程為考試課，滿分100分，分為平時(shí)成績和期末考試成績兩部分。平時(shí)成績：占30%。包括出勤、作業(yè)、課堂練習(xí)、上機(jī)、課堂紀(jì)律、回答問題、課間擦黑板等。期末考試：占70%，閉卷筆試，按各章知識(shí)點(diǎn)要求，突出重點(diǎn)，考核學(xué)生綜合應(yīng)用能力。特別提醒：上課時(shí)要帶好教材、筆、練習(xí)本!課程性質(zhì)及教學(xué)目的《數(shù)據(jù)結(jié)構(gòu)》是信息管理與信息系統(tǒng)專業(yè)本科生的一門專業(yè)基礎(chǔ)必修課。其教學(xué)目的就是要培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技巧,培養(yǎng)良好的程序設(shè)計(jì)技能。課程地位

數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)語言離散數(shù)學(xué)計(jì)算機(jī)原理面向?qū)ο蟪绦蛟O(shè)計(jì)操作系統(tǒng)數(shù)據(jù)庫編譯原理人工智能課程內(nèi)容本課程的基本內(nèi)容分為三個(gè)部分：第一部分：緒論第二部分：基本的數(shù)據(jù)結(jié)構(gòu)包括：線性結(jié)構(gòu)——線性表、棧和隊(duì)列、

串、數(shù)組和廣義表非線性結(jié)構(gòu)——樹、圖第三部分：基本的數(shù)據(jù)處理技術(shù)包括：查找技術(shù)和排序技術(shù)

1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)的主要應(yīng)用：程序=數(shù)據(jù)結(jié)構(gòu)+算法科學(xué)計(jì)算數(shù)據(jù)處理發(fā)展到計(jì)算機(jī)加工處理的對(duì)象：純數(shù)值發(fā)展到字符、表格和圖像等1968年，設(shè)立《數(shù)據(jù)結(jié)構(gòu)》課程計(jì)算機(jī)解決問題的步驟:具體問題設(shè)計(jì)編制分析抽象測試調(diào)整數(shù)學(xué)模型算法程序最終解答登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目信息書目文件按書名按作者名按分類號(hào)索引表線性表例1書目自動(dòng)檢索系統(tǒng)樹……..……..…...…...…...…...例2人機(jī)對(duì)奕問題CEDABABACADBABCBDDADBDCEAEBECED圖例3.多叉路口交通燈管理問題是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科《數(shù)據(jù)結(jié)構(gòu)》定義1.2基本概念和術(shù)語1、數(shù)據(jù)(Data)：一切能夠由計(jì)算機(jī)接受和處理的對(duì)象。

2、數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。

3、數(shù)據(jù)項(xiàng)(DataItem)：是數(shù)據(jù)的不可分割的最小單位，在有些場合下，數(shù)據(jù)項(xiàng)又稱為字段或域。

數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)4、數(shù)據(jù)結(jié)構(gòu)(Datastructure)

相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。例如:線性結(jié)構(gòu):

樹形結(jié)構(gòu):圖形結(jié)構(gòu):5．?dāng)?shù)據(jù)類型(DataType)

數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。例如:C語言中的整型變量,其值集為某個(gè)區(qū)間上的整數(shù),定義在其上的操作為加,減,乘,除和取模等算術(shù)運(yùn)算。6. 抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型(簡稱ADT)定義了一個(gè)數(shù)據(jù)對(duì)象,數(shù)據(jù)對(duì)象中各元素間的結(jié)構(gòu)關(guān)系,以及一組處理數(shù)據(jù)的操作.抽象數(shù)據(jù)類型的最本質(zhì)特點(diǎn)是:數(shù)據(jù)抽象和信息隱蔽.抽象的本質(zhì)是抽取反映事物的本質(zhì)點(diǎn),忽略非本質(zhì)的細(xì)節(jié),從而使設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)更具一般性,可以解決一類問題.信息隱蔽就是對(duì)用戶隱藏?cái)?shù)據(jù)存儲(chǔ)和操作實(shí)現(xiàn)的細(xì)節(jié),使用者僅需了解操作或界面服務(wù),通過界面服務(wù)來訪問數(shù)據(jù).

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算集合邏輯結(jié)構(gòu)定義:數(shù)據(jù)之間邏輯關(guān)系描述.形式化描述:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure=(D,S)其中:D是數(shù)據(jù)元素的有限集,S是D上關(guān)系的有限集.

例如:DS2=(D2,R2)D2={a,b,c,d,e,f}R2={T}T={<a,b>,<a,c>,<a,d>,<d,e>,<e,f>}abcdef四種基本的邏輯結(jié)構(gòu)集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)定義:存儲(chǔ)結(jié)構(gòu)(又稱物理結(jié)構(gòu))指邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映像,是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn),包括數(shù)據(jù)的表示和關(guān)系的表示.分類:

順序存儲(chǔ)結(jié)構(gòu):借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系.

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系.運(yùn)算集合討論數(shù)據(jù)的目的是在計(jì)算機(jī)中實(shí)現(xiàn)操作,因此在數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算集合是很重要的部分.數(shù)據(jù)結(jié)構(gòu)就是研究一類數(shù)據(jù)的表示及其相關(guān)操作的集合.例如:工資表的查找,刪除和插入操作.1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)數(shù)據(jù)類型

定義：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。C語言中的基本數(shù)據(jù)類型

intcharfloatdoublevoid

整型字符型浮點(diǎn)型雙精度型無值抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作=抽象數(shù)據(jù)類型例如：矩陣+（求轉(zhuǎn)置、加、乘、 求逆、求特征值） 構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型可用（D，S，P）三元組表示 其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

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

基本操作：〈基本操作的定義〉 }ADT抽象數(shù)據(jù)類型名其中,數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型可以通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)抽象數(shù)據(jù)類型類class數(shù)據(jù)對(duì)象數(shù)據(jù)成員基本操作成員函數(shù)(方法)例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,z3)操作的結(jié)果z3=z1+z2即為用戶企求的結(jié)果1.4算法和算法分析算法(Algorithm)定義算法的特性算法設(shè)計(jì)的要求算法描述工具算法性能分析算法(Algorithm)定義解決某一特定問題的具體步驟的描述，是指令的有限、有序序列。算法的特性一算法設(shè)計(jì)的要求正確性可讀性健壯性(魯棒性)高效率與低存儲(chǔ)量正確性實(shí)例:例:求n個(gè)數(shù)的最大值max=0;for(i=1;i<=n;i++){scanf(“%f”,&x);if(x>max)max=x;}可讀性健壯性高效率與低存儲(chǔ)量算法描述工具1．算法、語言、程序的關(guān)系⑴算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。⑵描述算法的工具：（自然語言、框圖或高級(jí)程序設(shè)計(jì)語言）算法的描述可用自然語言、框圖或高級(jí)程序設(shè)計(jì)語言，自然語言簡單但易于產(chǎn)生二義?？驁D直觀但不擅長表達(dá)數(shù)據(jù)組織結(jié)構(gòu)，而其中以高級(jí)程序語言較為準(zhǔn)確但又比較嚴(yán)謹(jǐn)。⑶程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)（與所用計(jì)算機(jī)及所用語言有關(guān)）2．設(shè)計(jì)實(shí)現(xiàn)算法過程步驟：

找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系（建立結(jié)構(gòu)關(guān)系）

確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算

考慮數(shù)據(jù)元素的存儲(chǔ)表示

選擇描述算法的語言

設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。算法描述工具高級(jí)語言描述算法，具有嚴(yán)格準(zhǔn)確的優(yōu)點(diǎn)，但用于描述算法，也有語言細(xì)節(jié)過多的弱點(diǎn)，為此采用類語言形式本課程算法采用類C語言作為描述工具.類C語言簡要說明1．

預(yù)定義常量和類型本書中用到以下常量符號(hào)，如True、False、MAXSIZE等，約定用如下宏定義預(yù)先定義：

#define

TRUE

1

#define

FALSE

0

#define

OK

1

#define

ERROR

0#define

INFEASIBLE-1#define

OVERFLOW-2//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼

typeintStatus;類C語言簡要說明2.本書中所有的算法都以如下所示函數(shù)的形式加以表示，其中的結(jié)構(gòu)類型使用前面已有的定義。

函數(shù)的形式:

函數(shù)類型

函數(shù)名（[形式參數(shù)及說明]）{

//算法說明

語句序列}

//函數(shù)名類C語言簡要說明3．

賦值語句簡單賦值：（1）變量名=表達(dá)式;

（2）變量++;

（3）變量--；串聯(lián)賦值：變量1=變量2=變量3=…=變量k=表達(dá)式；成組賦值：（變量1，變量2，變量3，…變量k=（表達(dá)式1，表達(dá)式2，表達(dá)式3，…表達(dá)式k）；結(jié)構(gòu)名=結(jié)構(gòu)名;結(jié)構(gòu)名=(值1,……，值k);變量名[]=表達(dá)式；

變量名[起始下標(biāo)..終止下標(biāo)]=變量名[起始下標(biāo)..終止下標(biāo)];交換賦值:變量名←→變量名條件賦值:變量名=條件表達(dá)式？表達(dá)式1:表達(dá)式2；類C語言簡要說明4．

條件選擇語句（1）

if（〈表達(dá)式〉）語句；（2）

if（〈表達(dá)式〉）語句1；

else

語句2；（3）

開關(guān)語句1switch

(<表達(dá)式>）{

case

值1:

語句組1；

break;

case

值2:

語句組2；

break;……

case

值n:

語句組n;

break;

[default:

語句組；]

}類C語言簡要說明（4）

開關(guān)語句2switch

{

case

條件1:

語句組1；

break;

case

條件2:

語句組2；

break;……

case

條件n:

語句組n;

break;

[default:

語句組；]

}類C語言簡要說明5．

循環(huán)語句（1）

for語句for(<表達(dá)式1>；<表達(dá)式2>；<表達(dá)式3>）{循環(huán)體語句；}（2）

while語句while(<條件表達(dá)式>）

{循環(huán)體語句；

}（3）

do-while語句do{循環(huán)體語句}while(<條件表達(dá)式>）類C語言簡要說明6．

結(jié)束語句函數(shù)結(jié)束語句return表達(dá)式;return;switch結(jié)束語句break;異常結(jié)束語句exit(異常代碼);類C語言簡要說明7．

輸入和輸出語句輸入語句scanf([格式串],變量1,變量2,……，變量n);輸出語句printf(([格式串],表達(dá)式1，表達(dá)式2，……表達(dá)式n);switch結(jié)