數(shù)據(jù)結(jié)構(gòu)1緒論課件

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

付細楚

2011年2月1數(shù)據(jù)結(jié)構(gòu)付細楚1聯(lián)系方式電子郵件：xichuf@163.com歡迎同學(xué)們共同交流和探討。2聯(lián)系方式電子郵件：xichuf@163.com2課程的性質(zhì)綜合性的專業(yè)基礎(chǔ)課程軟件專業(yè)課程體系中的核心課程先修課:C++程序設(shè)計語言,離散數(shù)學(xué)后續(xù)課:幾乎所有的軟件方面課程,如:操作系統(tǒng),編譯原理,算法分析與設(shè)計,應(yīng)用系統(tǒng)開發(fā)等.

3課程的性質(zhì)綜合性的專業(yè)基礎(chǔ)課程3課程安排教學(xué)安排:

教學(xué)總學(xué)時數(shù)56學(xué)時（其中講授:40課時,實驗16課時）數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計（2周）10軟件4、5、6、7、8班

4課程安排教學(xué)安排:4研究對象主要是研究：非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作

5研究對象主要是研究：5學(xué)習(xí)目的了解計算機處理對象的特性，將現(xiàn)實世界中實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。與此同時，通過算法訓(xùn)練提高計算機思維的能力，通過程序設(shè)計的技能訓(xùn)練來促進綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。6學(xué)習(xí)目的了解計算機處理對象的特性，將現(xiàn)實世界中實際問題中所涉教材[1]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）,北京：清華大學(xué)出版社，1997年[2]李根強數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及實訓(xùn)指導(dǎo)北京：中國水利出版社，2009年7教材[1]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）,7參考資料[1]殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描）,北京：清華大學(xué)出版社，1999年[2]BrunoR.Preiss，數(shù)據(jù)結(jié)構(gòu)與算法——面向?qū)ο蟮腃++設(shè)計模式，北京：電子工業(yè)出版社，2003年[3]李春葆．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言版第二版）．北京：清華大學(xué)出版社，2004年[4]陳元春等編，用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，中國鐵道出版社2003年8參考資料[1]殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+第一章緒論介紹數(shù)據(jù)結(jié)構(gòu)的基本概念1.什么是數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)基本概念3.抽象數(shù)據(jù)類型表示與實現(xiàn)4.算法及算法分析9第一章緒論介紹數(shù)據(jù)結(jié)構(gòu)的基本概念91.1什么是數(shù)據(jù)結(jié)構(gòu)信息管理、人工智能、文字處理加工對象：數(shù)值字符、表格、圖像或其他具有一定結(jié)構(gòu)的數(shù)據(jù)應(yīng)用領(lǐng)域：科學(xué)計算101.1什么是數(shù)據(jù)結(jié)構(gòu)信息管理、人工智能、加工對象：字符、計算機解決問題的步驟用計算機解決具體實際問題時,一般過程如下:從具體問題抽象出適當(dāng)?shù)臄?shù)據(jù)模型,設(shè)計求解數(shù)據(jù)模型的算法編寫程序,運行并調(diào)試程序,直到解決實際問題.

舉例:求水仙花數(shù)問題.尋求數(shù)據(jù)模型實質(zhì)是:分析問題,從中提取操作的對象,并找出這些操作對象之間的關(guān)系,然后用數(shù)學(xué)語言加以描述.11計算機解決問題的步驟用計算機解決具體實際問題時,一般過程如下例1.1圖書信息檢索登錄號,書名,作者,出版社,出版日期等構(gòu)成一張表.

每本書一個登錄號.要求按書名,作者,分類號等進行查找,

建立分別按書名,作者名,分類號的順序排列的索引表.書目表,書名,作者名,分類號索引表構(gòu)成數(shù)學(xué)模型.12例1.1圖書信息檢索登錄號,書名,作者,出版社,出版圖書信息表

000001高等數(shù)學(xué)樊映川S01。。。000002理論力學(xué)羅遠祥

L01。。。000003高等數(shù)學(xué)華羅庚

S01。。。000004線性代數(shù)陽正宏

S02。。。。。。。。。。。。。。。。。。。13圖書信息表000001高等數(shù)學(xué)樊映川S01。。。000例1.2八皇后問題N皇后問題是要求一個N×N的棋盤上放置N個皇后,每個皇后不能相遇按國際象棋的規(guī)則,皇后可以橫吃,豎吃,斜吃.以簡化的四皇后問題為例,說明八皇后問題.四皇后問題最后結(jié)果如附圖.●

●●●四皇后最后的結(jié)果14例1.2八皇后問題N皇后問題●●●●四皇后最后的結(jié)四皇后問題情形一

●

●

●

●●

●●15四皇后問題情形一●●●●●●●15例1.3交通燈管理問題交通管理問題（P3圖1.3）設(shè)計一個交通信號燈:

使車輛通行時互相之間不能碰撞.問題轉(zhuǎn)化為:對圖上的每一個頂點染一種顏色,要求有連線的頂點顏色不能相同.16例1.3交通燈管理問題交通管理問題（P3圖1.3）1例1.4交通咨詢問題城市公交線路圖，求解出行路徑。17例1.4交通咨詢問題城市公交線路圖，求解出行路徑。171.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)（Data）信息的載體，它能夠被計算機識別、存儲和加工處理。例如：

數(shù)值計算中的整數(shù)和實數(shù)，編譯程序或文本編輯程序中的字符串。多媒體技術(shù)中所涉及的視頻和音頻信號，經(jīng)采集轉(zhuǎn)換后都能形成被計算機所接受的數(shù)據(jù)。181.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)（Data）18第一講19第一講19基本術(shù)語數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素類（DataElementClass）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。例如：整數(shù)數(shù)據(jù)對象N＝｛0，1-1,2,-2……｝字母數(shù)據(jù)對象C＝｛’a’,’b’,’c’……｝20基本術(shù)語數(shù)據(jù)元素（DataElement）20數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。

四類基本的結(jié)構(gòu)：（圖1.5）（1）集合數(shù)據(jù)元素間的關(guān)系是’屬于同一個集合’。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。（3）樹形結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。（4）圖狀結(jié)構(gòu)

數(shù)據(jù)元素之間存在多對多的關(guān)系，圖狀結(jié)構(gòu)也稱網(wǎng)狀結(jié)構(gòu)。21數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲無關(guān)

邏輯結(jié)構(gòu)線性：線性表、棧、隊列、數(shù)組、串

非線性：廣義表、樹、圖22數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)結(jié)構(gòu)定義舉例DataStructure=(D,R)其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集例如:按員工的編號來建立元素間的線性關(guān)系Linear-List=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<02,03>,…………<09,10>}23數(shù)據(jù)結(jié)構(gòu)定義舉例DataStructure=(D,R)23按行政分組來建立樹形的數(shù)據(jù)結(jié)構(gòu)Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<02,07>,<03,08>,<03,09>,<04,10>}按員工的愛好來建立圖狀的數(shù)據(jù)結(jié)構(gòu)

Graph=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10,網(wǎng)，羽，乒}R＝{<01,羽>,<01,乒>,<05,網(wǎng)>,<05,乒>,<06,網(wǎng)>}24按行政分組來建立樹形的數(shù)據(jù)結(jié)構(gòu)24數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。

物理結(jié)構(gòu)順序使用一組連續(xù)的存儲單元非順序鏈?zhǔn)剿饕鎯Α⑸⒘写鎯?/p>

25數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）稱為數(shù)據(jù)的1.3抽象數(shù)據(jù)類型表示與實現(xiàn)

數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱。例如：整數(shù)類型，其取值的范圍為[-maxint,maxint]上的整數(shù)定義在其上的一組操作為加、減、乘、除及取模等。261.3抽象數(shù)據(jù)類型表示與實現(xiàn)數(shù)據(jù)類型（DataTyp抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。27抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTyp抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義可以由（元素、關(guān)系、操作）三種要素來進行定義（由于數(shù)據(jù)類型＝數(shù)據(jù)結(jié)構(gòu)＋操作，而數(shù)據(jù)結(jié)構(gòu)＝數(shù)據(jù)元素＋元素間的關(guān)系）例如棧的ADT定義：元素屬于同一個數(shù)據(jù)元素類。關(guān)系數(shù)據(jù)元素間呈線性關(guān)系。操作PUSH（S，X）進棧操作、POP（S）出棧操作等等

28抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義可以由28實現(xiàn)方法的比較

面向過程的方法在數(shù)據(jù)與操作二者之間并沒有建立必然的聯(lián)系順序執(zhí)行面向?qū)ο蟮姆椒ㄏ嚓P(guān)的數(shù)據(jù)及操作被統(tǒng)一在一個整體──對象之中程序簡潔有利于數(shù)據(jù)保護和代碼重用29實現(xiàn)方法的比較面向過程的方法29棧演示程序

面向過程的方法Node*top;charch;voidpush(charch);……charpop();……top=NULL;ch=’a’;while(ch!=‘E’){

輸入一個字符存入ch;

對ch進行判別并進行相應(yīng)的處理；輸出棧中的當(dāng)前元素};

面向?qū)ο蟮姆椒╟lassLinkStack

{private:Node*top;public:

LinkStack();voidinit();voidprnt();charpop();voidpush(charel);};

……LinkStacklz1;

lz1.init();lz1.push(el);lz1.prnt();

30棧演示程序面向過程的方法面向?qū)ο蟮姆椒?01.4算法及其分析

算法的概念：

算法是對特定問題求解步驟的一種描述

算法的特性：

有窮性、確定性、可行性、輸入、輸出算法的描述自然語言。使用流程圖、N－S圖等用于算法描述的工具，直接用某種高級程序設(shè)計語言來描述算法。使用偽碼語言算法設(shè)計的要求

正確、可讀、

健壯、

高效

311.4算法及其分析31時間的復(fù)雜性分析

表示形式：一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的。從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作：T(n)=o(f(n))該式表示算法中原操作的執(zhí)行次數(shù)與問題規(guī)模n的某個函數(shù)同階。

32時間的復(fù)雜性分析32常數(shù)階、線性階、平方階

o(1)o(n)o(n2)

x=x+1;for(i=1;i<=n;i++)x=x+1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//nfor(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n2};

33常數(shù)階、線性階、平方階

o(1)o(n)o例1.4n階矩陣相乘算法的時間復(fù)雜度

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//基本語句(1)

for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//基語句(2)};

在通常情況下算法的時間復(fù)雜度是指基本語句重復(fù)執(zhí)行的次數(shù)及頻度。在上述算法中主要語句的頻度分別是：基本語句(1)n2，基本語句(2)n3。該算法的時間復(fù)雜度所有語句的頻度之和T(n)=n2+n3=

o(n3)。因此該算法時間復(fù)雜度為o(n3),稱之為立方階。34例1.4n階矩陣相乘算法的時間復(fù)雜度34例1.5對數(shù)階時間復(fù)雜度

i=1;//語句(1)while(i<=n)i=i*2;//語句(2)其中語句(1)的頻度是1，設(shè)語句(2)的頻度是f(n)，則有2

f(n)<=n，即：f(n)<=log2n，取最大值f(n)=log2n，因此該算法時間復(fù)雜度為:T(n)=1+log2n=o(log2n)35例1.5對數(shù)階時間復(fù)雜度35空間的復(fù)雜性分析

類似于時間復(fù)雜性分析,空間的復(fù)雜性也可以表示為問題規(guī)模的函數(shù).

表示形式：S(n)=o(f(n))36空間的復(fù)雜性分析36例1.6空間的復(fù)雜性舉例

實例：將存放在一維數(shù)組a中的n個整數(shù)反向存放，即將a[1]存放在原a[n]存放的位置中，將a[2]存放在原a[n－1]存放的位置中，依次類推，直至將a[n]存放在原a[1]存放的位置中。

1.使用一組工作單元b[n]：for(i=1;i<=n;i++)b[n-i+1]=a[i];for(i=1;i<=n;i++)a[i]=b[i];

2.只使用工作單元i與w：for(i=1;i<=n/2;i++){w=a[i];a[i]=a[n-i+1];a[n-i+1]=w;};37例1.6空間的復(fù)雜性舉例37教學(xué)互動：算法及其算法分析試寫一個算法，實現(xiàn)將數(shù)組a[n]中的n個整數(shù)循環(huán)后移一個位置，并給出它的時間復(fù)雜度和輔助空間的大小。

38教學(xué)互動：算法及其算法分析38教學(xué)互動：算法及其算法分析inti,temp;temp=a[n-1];for(i=n-1;i>=1;i--)a[i]=a[i-1];a[0]=temp;時間復(fù)雜度T(n)=1+(n-1)+1=o(n)線性階空間復(fù)雜度S(n)=2=o(1)常數(shù)階39教學(xué)互動：算法及其算法分析39作業(yè)第一章習(xí)題

1,5,7,81、給出以下算法的時間復(fù)雜度1）voidfunA(intn){Inti=1,k=100;While(i<n){k=k+5;i+=2;}}2）voidfunB(intn){Inti,j,k,x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++);x=x+1;}40作業(yè)第一章習(xí)題40作業(yè)2、簡述下列術(shù)語的喊含義？數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、存貯結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。3、數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指什么？41作業(yè)2、簡述下列術(shù)語的喊含義？41數(shù)據(jù)結(jié)構(gòu)

付細楚

2011年2月42數(shù)據(jù)結(jié)構(gòu)付細楚1聯(lián)系方式電子郵件：xichuf@163.com歡迎同學(xué)們共同交流和探討。43聯(lián)系方式電子郵件：xichuf@163.com2課程的性質(zhì)綜合性的專業(yè)基礎(chǔ)課程軟件專業(yè)課程體系中的核心課程先修課:C++程序設(shè)計語言,離散數(shù)學(xué)后續(xù)課:幾乎所有的軟件方面課程,如:操作系統(tǒng),編譯原理,算法分析與設(shè)計,應(yīng)用系統(tǒng)開發(fā)等.

44課程的性質(zhì)綜合性的專業(yè)基礎(chǔ)課程3課程安排教學(xué)安排:

教學(xué)總學(xué)時數(shù)56學(xué)時（其中講授:40課時,實驗16課時）數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計（2周）10軟件4、5、6、7、8班

45課程安排教學(xué)安排:4研究對象主要是研究：非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作

46研究對象主要是研究：5學(xué)習(xí)目的了解計算機處理對象的特性，將現(xiàn)實世界中實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。與此同時，通過算法訓(xùn)練提高計算機思維的能力，通過程序設(shè)計的技能訓(xùn)練來促進綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。47學(xué)習(xí)目的了解計算機處理對象的特性，將現(xiàn)實世界中實際問題中所涉教材[1]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）,北京：清華大學(xué)出版社，1997年[2]李根強數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及實訓(xùn)指導(dǎo)北京：中國水利出版社，2009年48教材[1]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）,7參考資料[1]殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描）,北京：清華大學(xué)出版社，1999年[2]BrunoR.Preiss，數(shù)據(jù)結(jié)構(gòu)與算法——面向?qū)ο蟮腃++設(shè)計模式，北京：電子工業(yè)出版社，2003年[3]李春葆．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言版第二版）．北京：清華大學(xué)出版社，2004年[4]陳元春等編，用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，中國鐵道出版社2003年49參考資料[1]殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+第一章緒論介紹數(shù)據(jù)結(jié)構(gòu)的基本概念1.什么是數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)基本概念3.抽象數(shù)據(jù)類型表示與實現(xiàn)4.算法及算法分析50第一章緒論介紹數(shù)據(jù)結(jié)構(gòu)的基本概念91.1什么是數(shù)據(jù)結(jié)構(gòu)信息管理、人工智能、文字處理加工對象：數(shù)值字符、表格、圖像或其他具有一定結(jié)構(gòu)的數(shù)據(jù)應(yīng)用領(lǐng)域：科學(xué)計算511.1什么是數(shù)據(jù)結(jié)構(gòu)信息管理、人工智能、加工對象：字符、計算機解決問題的步驟用計算機解決具體實際問題時,一般過程如下:從具體問題抽象出適當(dāng)?shù)臄?shù)據(jù)模型,設(shè)計求解數(shù)據(jù)模型的算法編寫程序,運行并調(diào)試程序,直到解決實際問題.

舉例:求水仙花數(shù)問題.尋求數(shù)據(jù)模型實質(zhì)是:分析問題,從中提取操作的對象,并找出這些操作對象之間的關(guān)系,然后用數(shù)學(xué)語言加以描述.52計算機解決問題的步驟用計算機解決具體實際問題時,一般過程如下例1.1圖書信息檢索登錄號,書名,作者,出版社,出版日期等構(gòu)成一張表.

每本書一個登錄號.要求按書名,作者,分類號等進行查找,

建立分別按書名,作者名,分類號的順序排列的索引表.書目表,書名,作者名,分類號索引表構(gòu)成數(shù)學(xué)模型.53例1.1圖書信息檢索登錄號,書名,作者,出版社,出版圖書信息表

000001高等數(shù)學(xué)樊映川S01。。。000002理論力學(xué)羅遠祥

L01。。。000003高等數(shù)學(xué)華羅庚

S01。。。000004線性代數(shù)陽正宏

S02。。。。。。。。。。。。。。。。。。。54圖書信息表000001高等數(shù)學(xué)樊映川S01。。。000例1.2八皇后問題N皇后問題是要求一個N×N的棋盤上放置N個皇后,每個皇后不能相遇按國際象棋的規(guī)則,皇后可以橫吃,豎吃,斜吃.以簡化的四皇后問題為例,說明八皇后問題.四皇后問題最后結(jié)果如附圖.●

●●●四皇后最后的結(jié)果55例1.2八皇后問題N皇后問題●●●●四皇后最后的結(jié)四皇后問題情形一

●

●

●

●●

●●56四皇后問題情形一●●●●●●●15例1.3交通燈管理問題交通管理問題（P3圖1.3）設(shè)計一個交通信號燈:

使車輛通行時互相之間不能碰撞.問題轉(zhuǎn)化為:對圖上的每一個頂點染一種顏色,要求有連線的頂點顏色不能相同.57例1.3交通燈管理問題交通管理問題（P3圖1.3）1例1.4交通咨詢問題城市公交線路圖，求解出行路徑。58例1.4交通咨詢問題城市公交線路圖，求解出行路徑。171.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)（Data）信息的載體，它能夠被計算機識別、存儲和加工處理。例如：

數(shù)值計算中的整數(shù)和實數(shù)，編譯程序或文本編輯程序中的字符串。多媒體技術(shù)中所涉及的視頻和音頻信號，經(jīng)采集轉(zhuǎn)換后都能形成被計算機所接受的數(shù)據(jù)。591.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)（Data）18第一講60第一講19基本術(shù)語數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素類（DataElementClass）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。例如：整數(shù)數(shù)據(jù)對象N＝｛0，1-1,2,-2……｝字母數(shù)據(jù)對象C＝｛’a’,’b’,’c’……｝61基本術(shù)語數(shù)據(jù)元素（DataElement）20數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。

四類基本的結(jié)構(gòu)：（圖1.5）（1）集合數(shù)據(jù)元素間的關(guān)系是’屬于同一個集合’。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。（3）樹形結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。（4）圖狀結(jié)構(gòu)

數(shù)據(jù)元素之間存在多對多的關(guān)系，圖狀結(jié)構(gòu)也稱網(wǎng)狀結(jié)構(gòu)。62數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲無關(guān)

邏輯結(jié)構(gòu)線性：線性表、棧、隊列、數(shù)組、串

非線性：廣義表、樹、圖63數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)結(jié)構(gòu)定義舉例DataStructure=(D,R)其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集例如:按員工的編號來建立元素間的線性關(guān)系Linear-List=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<02,03>,…………<09,10>}64數(shù)據(jù)結(jié)構(gòu)定義舉例DataStructure=(D,R)23按行政分組來建立樹形的數(shù)據(jù)結(jié)構(gòu)Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<02,07>,<03,08>,<03,09>,<04,10>}按員工的愛好來建立圖狀的數(shù)據(jù)結(jié)構(gòu)

Graph=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10,網(wǎng)，羽，乒}R＝{<01,羽>,<01,乒>,<05,網(wǎng)>,<05,乒>,<06,網(wǎng)>}65按行政分組來建立樹形的數(shù)據(jù)結(jié)構(gòu)24數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。

物理結(jié)構(gòu)順序使用一組連續(xù)的存儲單元非順序鏈?zhǔn)剿饕鎯?、散列存?/p>

66數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）稱為數(shù)據(jù)的1.3抽象數(shù)據(jù)類型表示與實現(xiàn)

數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱。例如：整數(shù)類型，其取值的范圍為[-maxint,maxint]上的整數(shù)定義在其上的一組操作為加、減、乘、除及取模等。671.3抽象數(shù)據(jù)類型表示與實現(xiàn)數(shù)據(jù)類型（DataTyp抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。68抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTyp抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義可以由（元素、關(guān)系、操作）三種要素來進行定義（由于數(shù)據(jù)類型＝數(shù)據(jù)結(jié)構(gòu)＋操作，而數(shù)據(jù)結(jié)構(gòu)＝數(shù)據(jù)元素＋元素間的關(guān)系）例如棧的ADT定義：元素屬于同一個數(shù)據(jù)元素類。關(guān)系數(shù)據(jù)元素間呈線性關(guān)系。操作PUSH（S，X）進棧操作、POP（S）出棧操作等等

69抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義可以由28實現(xiàn)方法的比較

面向過程的方法在數(shù)據(jù)與操作二者之間并沒有建立必然的聯(lián)系順序執(zhí)行面向?qū)ο蟮姆椒ㄏ嚓P(guān)的數(shù)據(jù)及操作被統(tǒng)一在一個整體──對象之中程序簡潔有利于數(shù)據(jù)保護和代碼重用70實現(xiàn)方法的比較面向過程的方法29棧演示程序

面向過程的方法Node*top;charch;voidpush(charch);……charpop();……top=NULL;ch=’a’;while(ch!=‘E’){

輸入一個字符存入ch;

對ch進行判別并進行相應(yīng)的處理；輸出棧中的當(dāng)前元素};

面向?qū)ο蟮姆椒╟lassLinkStack

{private:Node*top;public:

LinkStack();voidinit();voidprnt();charpop();voidpush(charel);};

……LinkStacklz1;

lz1.init();lz1.push(el);lz1.prnt();

71棧演示程序面向過程的方法面向?qū)ο蟮姆椒?01.4算法及其分析

算法的概念：

算法是對特定問題求解步驟的一種描述

算法的特性：

有窮性、確定性、可行性、輸入、輸出算法的描述自然語言。使用流程圖、N－S圖等用于算法描述的工具，直接用某種高級程序設(shè)計語言來描述算法。使用偽碼語言算法設(shè)計的要求

正確、可讀、

健壯、

高效

721.4算法及其分析31時間的復(fù)雜性分析

表示形式：一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的。從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作：T(n)=o(f(n))該式表示算法中原操作的執(zhí)行次數(shù)與問題規(guī)模n的某個函數(shù)同階。

73時間的復(fù)雜性分析32常數(shù)階、線性階、平方階

o(1)o(n)o(n2)

x=x+1;for(i=1;i<=n;i++)x=x+1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//nfor(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n2};

74常數(shù)階、線性階、平方階

o(1)o(n)o例1.4n階矩陣相乘算法的時間復(fù)雜度

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//基本語句(1)

for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//基語句(2)};

在通常情況下算法的時間復(fù)雜度是指基本語句重復(fù)執(zhí)行的次數(shù)及頻度。在上述算法中主要語句的頻度分別是：基本語句(1)n2，基本語句(2)n3。該算法的時間復(fù)雜度所有語句的頻度之和T(n)=n2