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

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

付細(xì)楚

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

3課程安排教學(xué)安排:

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

4研究對(duì)象主要是研究：非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作

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

舉例:求水仙花數(shù)問題.尋求數(shù)據(jù)模型實(shí)質(zhì)是:分析問題,從中提取操作的對(duì)象,并找出這些操作對(duì)象之間的關(guān)系,然后用數(shù)學(xué)語(yǔ)言加以描述.11例1.1圖書信息檢索登錄號(hào),書名,作者,出版社,出版日期等構(gòu)成一張表.

每本書一個(gè)登錄號(hào).要求按書名,作者,分類號(hào)等進(jìn)行查找,

建立分別按書名,作者名,分類號(hào)的順序排列的索引表.書目表,書名,作者名,分類號(hào)索引表構(gòu)成數(shù)學(xué)模型.12圖書信息表

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

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

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

S02。。。。。。。。。。。。。。。。。。。13例1.2八皇后問題N皇后問題是要求一個(gè)N×N的棋盤上放置N個(gè)皇后,每個(gè)皇后不能相遇按國(guó)際象棋的規(guī)則,皇后可以橫吃,豎吃,斜吃.以簡(jiǎn)化的四皇后問題為例,說明八皇后問題.四皇后問題最后結(jié)果如附圖.●

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

●

●

●

●●

●●15例1.3交通燈管理問題交通管理問題（P3圖1.3）設(shè)計(jì)一個(gè)交通信號(hào)燈:

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

數(shù)值計(jì)算中的整數(shù)和實(shí)數(shù)，編譯程序或文本編輯程序中的字符串。多媒體技術(shù)中所涉及的視頻和音頻信號(hào)，經(jīng)采集轉(zhuǎn)換后都能形成被計(jì)算機(jī)所接受的數(shù)據(jù)。18第一講19基本術(shù)語(yǔ)數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素類（DataElementClass）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。例如：整數(shù)數(shù)據(jù)對(duì)象N＝｛0，1-1,2,-2……｝字母數(shù)據(jù)對(duì)象C＝｛’a’,’b’,’c’……｝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)系是’屬于同一個(gè)集合’。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。（3）樹形結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。（4）圖狀結(jié)構(gòu)

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

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

非線性：廣義表、樹、圖22數(shù)據(jù)結(jié)構(gòu)定義舉例DataStructure=(D,R)其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集例如:按員工的編號(hào)來建立元素間的線性關(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)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)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映象）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。

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

251.3抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)

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

28實(shí)現(xiàn)方法的比較

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

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

輸入一個(gè)字符存入ch;

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

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

{private:Node*top;public:

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

……LinkStacklz1;

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

301.4算法及其分析

算法的概念：

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

算法的特性：

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

正確、可讀、

健壯、

高效

31時(shí)間的復(fù)雜性分析

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

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例1.4n階矩陣相乘算法的時(shí)間復(fù)雜度

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

for(k=1;k<=n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];//基語(yǔ)句(2)};

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

T(n)=n2+n3=

o(n3)。因此該算法時(shí)間復(fù)雜度為o(n3),稱之為立方階。34例1.5對(duì)數(shù)階時(shí)間復(fù)雜度

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

f(n)<=n，即：f(n)<=log2n，取最大值f(n)=log2n，因此該算法時(shí)間復(fù)雜度為:

T(n)=1+log2n=o(log2n)35空間的復(fù)雜性分析

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

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

實(shí)例：將存放在一維數(shù)組a中的n個(gè)整數(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教學(xué)互動(dòng)：算法及其算法分析試寫一個(gè)