【數(shù)據(jù)結(jié)構(gòu)與算法】概述

《【數(shù)據(jù)結(jié)構(gòu)與算法】概述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)及算法課程名稱：數(shù)據(jù)結(jié)構(gòu)及算法預(yù)修課程:C語言,高等數(shù)學(xué)教材：1.《數(shù)據(jù)結(jié)構(gòu)》(C語言版)清華大學(xué)出版社19972.《數(shù)據(jù)結(jié)構(gòu)題集》(C語言版)清華大學(xué)出版社1999教師：徐鏡春xjcsj01@dlc.zju.edu.cn關(guān)于習(xí)題與實驗題教材中習(xí)題放在每章結(jié)束,但學(xué)生在每周都應(yīng)該完成與上課內(nèi)容相應(yīng)的部分小題有精力的同學(xué)應(yīng)該思考《數(shù)據(jù)結(jié)構(gòu)題集》中未列為必做的練習(xí),這會有助于理解課程內(nèi)容習(xí)題包括理論習(xí)題和上機實驗題實驗題要求用C語言編寫,并在計算機上調(diào)試通過實驗報告至少應(yīng)包括題目算法步驟源程序(不太多時寫在作業(yè)本上)運算結(jié)果及分析調(diào)試過程與體會第一章緒論1．1什么

2、是數(shù)據(jù)結(jié)構(gòu)1．2基本概念和術(shù)語1．3抽象數(shù)據(jù)類型的表示與實現(xiàn)1．4算法和算法分析1．4．1算法1．4．2算法設(shè)計的要求1．4．3算法效率的度量1．4．4算法的存儲空間需求1.1什么是數(shù)據(jù)結(jié)構(gòu)計算機解決問題的步驟實際問題---數(shù)學(xué)模型---算法---程序---結(jié)果工程師數(shù)學(xué)家程序員計算機的用途科學(xué)計算(數(shù)值運算):解方程(組),函數(shù)求值,概率統(tǒng)計等非數(shù)值運算:字符,表格,圖象,聲音等計算機的用途---數(shù)值運算水庫大壩的應(yīng)力計算預(yù)報人口增長天氣預(yù)報計算機的用途---非數(shù)值運算書目檢索系統(tǒng)多叉路口的交通燈管理問題有連線的節(jié)點用不同的顏色標(biāo)記,表示不能同時通行.要求使用的顏色

3、數(shù)盡可能少,以使減少等待時間.圖論中的四色問題.多叉路口的交通燈管理問題不能同時通行的通路用連線把它們連起來,它們有:A->B通路:CA,BD,BCA->D通路:CB,BCB->C通路:AB,ADB->D通路:AB,CBC->A通路:ABC->B通路:BD,AD計算機的用途---非數(shù)值運算計算機與人對奕問題數(shù)據(jù)結(jié)構(gòu)的定義描述非數(shù)值計算問題的模型是---如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是---研究計算機的操作對象(數(shù)據(jù))以及它們之間的關(guān)系和操作等的學(xué)科.學(xué)科《數(shù)據(jù)結(jié)構(gòu)》在計算機科學(xué)中所處的地位綜合性的專業(yè)基礎(chǔ)課1.2基本概念和術(shù)語數(shù)據(jù)：計算機程序處理的符號的總稱。數(shù)據(jù)

4、元素：數(shù)據(jù)的基本單位。通常作為一個整體進(jìn)行處理。數(shù)據(jù)項：數(shù)據(jù)的不可分割的最小單位。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項構(gòu)成。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：相互間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素相互關(guān)系-----稱為“結(jié)構(gòu)”四類基本結(jié)構(gòu)集合線性結(jié)構(gòu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)定義數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structure=(D,S)D–數(shù)據(jù)元素的有限集合S–定義在D上的關(guān)系的有限集合例如Complex=(C,R)C={(c1,c2)

5、c1,c2是實數(shù)}R={P

6、P是定義在C上的關(guān)系，表示c1是實部,c2是虛部}邏

7、輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu):數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)在計算機中的表示,又稱存儲結(jié)構(gòu)算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)數(shù)據(jù)類型與抽象的數(shù)據(jù)類型數(shù)據(jù)類型（DataType）：值的集合以及定義在這個集合上的一組操作。例如:C語言中的整數(shù)類型抽象數(shù)據(jù)類型(ADT)數(shù)學(xué)模型以及定義在該模型上的一組操作。與其在計算機中的表示和實現(xiàn)無關(guān)。ADT可用三元組表示：（D,S,P）D–數(shù)據(jù)對象;S–D上的關(guān)系;P–對D的基本操作集抽象數(shù)據(jù)類型的定義格式：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：＜數(shù)據(jù)對象的定義＞數(shù)據(jù)關(guān)系：＜數(shù)據(jù)關(guān)系的定義＞基本操作：＜基本操

8、作的定義＞｝ADT抽象的數(shù)據(jù)類型名基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：＜初始條件描述＞操作結(jié)果：＜操作結(jié)果描述＞抽象數(shù)據(jù)類型三元組的定義ADTTriplet{數(shù)據(jù)對象：D={e1,e2,e3

9、e1,e2,e3屬于Elemset(定義了關(guān)系的某個集合)}數(shù)據(jù)關(guān)系：R1={＜e1,e2＞

10、＜e2,e3＞}基本操作：InitTriplet(&T,v1,v2,v3)初始條件:操作結(jié)果:構(gòu)造三元組T,元素e1,e2和e3分別被賦予參數(shù)v1,v2和v3的值。抽象數(shù)據(jù)類型三元組的定義(2)DestroyTriplet(&T)初始條件:三元組T已經(jīng)存在。操作結(jié)果:

11、銷毀三元組T。Get(T,i,&e)初始條件:三元組T已經(jīng)存在,1<=i<=3。操作結(jié)果:用e返回三元組T的第i個元素。Put(&T,i,e)初始條件:三元組T已經(jīng)存在,1<=i<=3。操作結(jié)果:用e值取代三元組T的第i個元素。抽象數(shù)據(jù)類型三元組的定義(3)IsAscending(T)初始條件:三元組T已經(jīng)存在。操作結(jié)果:如果三元組T的三個元素按升序排列,則返回TRUE;否則返回FALSE。IsDescending(T)初始條件:三元組T已經(jīng)存在。操作結(jié)果:如果三元組T的三個元素按降序排列,則返回TRUE;否則返回FALSE。抽象數(shù)據(jù)類型三元組的定義