數據結構-第1章 緒論

數據結構

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

數據結構程序設計語言離散數學計算機原理面向對象程序設計操作系統(tǒng)數據庫編譯原理人工智能課程內容本課程的基本內容分為三個部分：第一部分：緒論第二部分：基本的數據結構包括：線性結構——線性表、棧和隊列、

串、數組和廣義表非線性結構——樹、圖第三部分：基本的數據處理技術包括：查找技術和排序技術

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

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

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

數據元素數據項4、數據結構(Datastructure)

相互之間存在一種或多種特定關系的數據元素的集合。例如:線性結構:

樹形結構:圖形結構:5．數據類型(DataType)

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

數據結構的內容邏輯結構存儲結構運算集合邏輯結構定義:數據之間邏輯關系描述.形式化描述:數據結構是一個二元組Data_Structure=(D,S)其中:D是數據元素的有限集,S是D上關系的有限集.

例如:DS2=(D2,R2)D2={a,b,c,d,e,f}R2={T}T={<a,b>,<a,c>,<a,d>,<d,e>,<e,f>}abcdef四種基本的邏輯結構集合、線性結構、樹形結構、圖形結構存儲結構定義:存儲結構(又稱物理結構)指邏輯結構在計算機中的存儲映像,是邏輯結構在計算機中的實現,包括數據的表示和關系的表示.分類:

順序存儲結構:借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系.

鏈式存儲結構:借助指示元素存儲地址的指針表示數據元素之間的邏輯關系.運算集合討論數據的目的是在計算機中實現操作,因此在數據結構上的運算集合是很重要的部分.數據結構就是研究一類數據的表示及其相關操作的集合.例如:工資表的查找,刪除和插入操作.1.3抽象數據類型的表示與實現數據類型

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

intcharfloatdoublevoid

整型字符型浮點型雙精度型無值抽象數據類型是指一個數學模型以及定義在此數學模型上的一組操作數據結構+定義在此數據結構上的一組操作=抽象數據類型例如：矩陣+（求轉置、加、乘、 求逆、求特征值） 構成一個矩陣的抽象數據類型抽象數據類型的描述抽象數據類型可用（D，S，P）三元組表示 其中，D是數據對象，S是D上的關系集，P是對D的基本操作集。

ADT抽象數據類型名{

數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

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

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

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

數據對象：

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

數據關系：

R1＝{<e1,e2>|e1是復數的實數部分

|e2

是復數的虛數部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結果：構造復數Z,其實部和虛部分別被賦以參數v1和v2的值。

DestroyComplex(&Z)操作結果：復數Z被銷毀。

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

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

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

找出與求解有關的數據元素之間的關系（建立結構關系）

確定在某一數據對象上所施加運算

考慮數據元素的存儲表示

選擇描述算法的語言

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

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

#define

TRUE

1

#define

FALSE

0

#define

OK

1

#define

ERROR

0#define

INFEASIBLE-1#define

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

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

函數的形式:

函數類型

函數名（[形式參數及說明]）{

//算法說明

語句序列}

//函數名類C語言簡要說明3．

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

（2）變量++;

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

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

條件選擇語句（1）

if（〈表達式〉）語句；（2）

if（〈表達式〉）語句1；

else

語句2；（3）

開關語句1switch

(<表達式>）{

case

值1:

語句組1；

break;

case

值2:

語句組2；

break;……

case

值n:

語句組n;

break;

[default:

語句組；]

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

開關語句2switch

{

case

條件1:

語句組1；

break;

case

條件2:

語句組2；

break;……

case

條件n:

語句組n;

break;

[default:

語句組；]

}類C語言簡要說明5．

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

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

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

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

}（3）

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

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

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