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

上課前需要說明的幾個(gè)問題：任課教師：王歲花聯(lián)系電話：136639012732.交流信箱：dsjiaoxue@126.com3.公共信箱：

公共信箱：dsggxx@126.com

密碼：dsggxx20084.關(guān)于數(shù)據(jù)結(jié)構(gòu)課程：教材、重要性、時(shí)間按排（54+36）考試成績(jī)=期末考試*70%+平時(shí)成績(jī)*30%5.平時(shí)成績(jī)主要是實(shí)驗(yàn)作業(yè)完成情況，實(shí)驗(yàn)每次點(diǎn)名，隨機(jī)抽查驗(yàn)收，查看程序運(yùn)行。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.4算法和算法分析1.3抽象數(shù)據(jù)類型本章小結(jié)、教材、參考文獻(xiàn)作業(yè)1.1什么是數(shù)據(jù)結(jié)構(gòu)1)數(shù)據(jù)結(jié)構(gòu)討論的范疇NiklausWirth程序=數(shù)據(jù)結(jié)構(gòu)+算法

用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟:（1）抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型（2）設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（3）編出程序進(jìn)行測(cè)試、修改直至得到最終結(jié)果。

例1.田徑賽的時(shí)間安排問題設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示），設(shè)計(jì)比賽日程表，使得用盡可能少的時(shí)間段完成比賽。姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一馬二張三李四王五跳高標(biāo)槍標(biāo)槍鉛球跳遠(yuǎn)跳遠(yuǎn)100米鉛球100米200米200米跳高200米用無向圖的著色問題解決?。。?）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米

A B CDE F（2）用頂點(diǎn)代表比賽項(xiàng)目（3）用邊連接不能同時(shí)進(jìn)行比賽的項(xiàng)目如下圖所示：姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一馬二張三李四王五ACCDBBEDEFFAF韋爾奇.鮑威爾（WelchPowell)方法：

1.將圖G中的結(jié)點(diǎn)按度遞減的順序排列。

2.用沒有用過的顏色對(duì)第一個(gè)點(diǎn)著色，并且按排列次序，對(duì)與前面著色點(diǎn)不相鄰的點(diǎn)著相同顏色。

3.從序列中刪除第2步著過色的點(diǎn)。

4.重復(fù)第2、3步，直到序列為空。

例:對(duì)上例，執(zhí)行算法第1步結(jié)果為：

{F,A,E,B,C,D}

重復(fù)執(zhí)行第2,3步序列變化為：{A,E,B,C,D}{E,B,D}{B}{}

圖的變化為：

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和操作等的學(xué)科。2)數(shù)據(jù)結(jié)構(gòu)對(duì)研究對(duì)象及其之間關(guān)系的描述。結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D：是數(shù)據(jù)元素的有限集

S：是D上關(guān)系的有限集。（邏輯結(jié)構(gòu)）1.2基本概念和術(shù)語數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能被輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)(DataItem）:一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)或分為四種：線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。樹型結(jié)構(gòu)（層次結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，別無其它關(guān)系。Data_Structures=(D,S)（邏輯結(jié)構(gòu)）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——

邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)21.順序映象：借助于元素在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)位置來描述元素之間的邏輯關(guān)系。例：關(guān)系的映象方法（表示<x,y,z>的方法）

xyz2.鏈?zhǔn)接诚蠼柚谥甘驹卮鎯?chǔ)地址的指針表示元素之間的邏輯關(guān)系。xyz……^在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。

當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。數(shù)據(jù)類型：數(shù)據(jù)類型是一個(gè)值的集合和定義在這組值

集上的一組操作的總稱。例如：C-語言中的int,float,char等抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)稱ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型的描述方法:

抽象數(shù)據(jù)類型可用（D，S，P）三元組表示,其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。

本門課采用下面格式表示抽象數(shù)據(jù)類型：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é)果。引用變量和引用參數(shù)“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則省略之。

“操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如：抽象數(shù)據(jù)類型三元組的定義：P9#include"stdio.h"voidmain(){intx=3,y=4,&z=x;printf("x=%d,y=%d,z=%d\n",x,y,z);z=x+y;printf("x=%d,y=%d,z=%d\n",x,y,z);}運(yùn)行結(jié)果:x=3,y=4,z=3x=7,y=4,z=7voidsum1(inta,intb,intc){c=a+b;return;}voidsum2(inta,intb,int&c){c=a+b;return;}voidmain(){intx=3,y=4,z=5;printf("x=%d,y=%d,z=%d\n",x,y,z);sum1(x,y,z);printf("x=%d,y=%d,z=%d\n",x,y,z);sum2(x,y,z);printf("x=%d,y=%d,z=%d\n",x,y,z);}運(yùn)行結(jié)果x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=7//------采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)-----typedefElemType*Triplet;//由InitTriplet分配三個(gè)元素存儲(chǔ)空間//Triplet類型是ElemType類型的指針//存放ElemType類型的地址例如：抽象數(shù)據(jù)類型三元組的定義：P9//bo1_1.cpp抽象數(shù)據(jù)類型Triplet和ElemType//(由c1_1.h定義)的基本操作(8個(gè))StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//操作結(jié)果:構(gòu)造三元組T,依次置T的三個(gè)元素的初

//值為v1,v2和v3if(!(T=(ElemType*)malloc(3*sizeof(ElemType))))exit(OVERFLOW);T[0]=v1,T[1]=v2,T[2]=v3;returnOK;}StatusGet(TripletT,inti,ElemType&e){//初始條件：三元組T已存在，1≤i≤3。

//操作結(jié)果：用e返回T的第i元的值

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}StatusPut(TripletT,inti,ElemTypee){//初始條件：三元組T已存在，1≤i≤3。

//操作結(jié)果：改變T的第i元的值為eif(i<1||i>3)returnERROR;T[i-1]=e;returnOK;}StatusIsAscending(TripletT){//初始條件：三元組T已存在。操作結(jié)果：如果

//T的三個(gè)元素按升序排列，返回1，否則返回0return(T[0]<=T[1]&&T[1]<=T[2]);}StatusIsDescending(TripletT){//初始條件:三元組T已存在。

//操作結(jié)果:如果T的三個(gè)元素按降序排列,返回1,否則返回0return(T[0]>=T[1]&&T[1]>=T[2]);}StatusMax(TripletT,ElemType&e){//初始條件：三元組T已存在。

//操作結(jié)果：用e返回T的三個(gè)元素中的最大值

e=(T[0]>=T[1])?((T[0]>=T[2])?T[0]:T[2]):

((T[1]>=T[2])?T[1]:T[2]);returnOK;}StatusMin(TripletT,ElemType&e){//初始條件：三元組T已存在。

//操作結(jié)果：用e返回T的三個(gè)元素中的最小值

e=(T[0]<=T[1])?((T[0]<=T[2])?T[0]:T[2]):((T[1]<=T[2])?T[1]:T[2]);returnOK;}1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)本書采用類C-語言作為描述工具，類C-精選了C語言的一個(gè)核心子集，同時(shí)做了若干擴(kuò)充修改，增強(qiáng)了語言的描述功能。P10-111.4算法和算法分析1）什么是算法？算法（Algorithm)是對(duì)特定問題求解步驟的描述。描述算法的方法有：自然語言、流程圖、N-S圖和偽碼語言等。本書采用類C語言來描述算法。偽碼語言是包括高級(jí)語言的三種基本結(jié)構(gòu)、自然語言和數(shù)學(xué)語言成份的面向讀者的一種語言。2）一個(gè)算法必須滿足的五個(gè)準(zhǔn)則：（1）有窮性一個(gè)算法必須在執(zhí)行有窮步驟之后正常結(jié)束，而不能形成無窮循環(huán)，且必須在有窮時(shí)間內(nèi)完成。（2）確定性（無二義）:

算法的每一步操作都必須有確切含義，不得有任何二義性。（3）可行性:

算法中的每一條指令必須是切實(shí)可執(zhí)行的，即原則上可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。（4）輸入：一個(gè)算法有n（n>=0)個(gè)初始數(shù)據(jù)的輸入。（5）輸出：一個(gè)算法有一個(gè)或多個(gè)與輸入有某種關(guān)系的有效信息的輸出。3）算法設(shè)計(jì)的要求正確性、可讀性、健壯性和效率與存儲(chǔ)量要求。

程序正確性的五個(gè)層面：（1）不含語法錯(cuò)誤（2）程序?qū)τ趎組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。（3）程序?qū)τ诰倪x擇的典型、邊界性的n組輸入數(shù)據(jù)能得出滿足規(guī)格說明要求的結(jié)果。（4）程序?qū)τ谝磺泻线m的輸入數(shù)據(jù)都能得出滿足規(guī)格說明要求的結(jié)果（窮舉）。（5）用數(shù)學(xué)方法證明程序的正確性

嫦娥一號(hào)：98.8萬行源代碼，421萬份文件，打印出來有23000頁。用了160多萬行程序證明它的正確性?？勺x性、健壯性和效率與存儲(chǔ)量要求。

4）高效率與低存儲(chǔ)量需求

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。算法效率的衡量方法和準(zhǔn)則衡量算法效率的方法:缺點(diǎn)：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)事后統(tǒng)計(jì)法：事前分析估算法和算法執(zhí)行時(shí)間有關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度

一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)f(n)。算法=控制結(jié)構(gòu)+原操作//基本操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對(duì)于所研究的問題來說是

基本操作

的原操作，以該基本操作

在算法中重復(fù)執(zhí)行的次數(shù)

作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。表示隨著問題規(guī)模的增大，算法執(zhí)行時(shí)間增長(zhǎng)增長(zhǎng)率和f(n)相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。一般情況下，算法中基本操作執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間量度記作：T(n)=O(f(n))(M是>0的常數(shù))

也可以用：如何估算算法的時(shí)間復(fù)雜度？例：2n3+1000n2+1=O(n3)1000n2+n+1000000=O(n2)例一兩個(gè)矩陣相乘voidmult(inta[],intb[],intc[]){//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}//for}//mult基本操作:乘法操作時(shí)間復(fù)雜度:O(n3)例二冒泡排序基本操作:

交換兩個(gè)相鄰元素的操作時(shí)間復(fù)雜度:O(n2)voidbubble_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for(i=n-1,change=TRUE;i>=1&&change;--i)}//bubble_sort{change=FALSE;

//change為元素進(jìn)行交換標(biāo)志

for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE;}}//一趟冒泡交換次數(shù)：最好情況：0最壞情況：n(n-1)/2最壞情況下的時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度若不特別說明，以后我們所說的都是最壞情況下的時(shí)間復(fù)雜度常見函數(shù)的時(shí)間復(fù)雜度按數(shù)量遞增排列及增長(zhǎng)率。常數(shù)階O(1)對(duì)數(shù)階O(log2n)線性階O(n)線性對(duì)數(shù)階O(nlog2n)平方階O(n2)立方階O(n3)……多項(xiàng)式階O(nk)指數(shù)階O(2n）1.10按增長(zhǎng)率由小到大的排列順序是：(2/3)n,2100,log2(log2n),log2n,(log2n)2,,n2/3,n/log2n,n,nlog2n,n3/2,(4/3)n,(3/2)n,nlog2n,n!,nn解題依據(jù)為：

4)算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=O(g(n))算法的存儲(chǔ)量包括:輸入數(shù)據(jù)所占空間程序本身所占空間輔助變量所占空間

若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

若需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。

若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。例如在進(jìn)行冒泡排序時(shí)所需的額外的空間就是一個(gè)常數(shù),空間復(fù)雜度為O(1)。本章小結(jié)1.基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算）、多形數(shù)據(jù)類型、抽象數(shù)據(jù)類型（定義、表示和實(shí)現(xiàn)）2.抽象數(shù)據(jù)類型：描述、類-C中的基本語句和函數(shù)3.算法：算法的時(shí)間復(fù)雜度（漸近時(shí)間復(fù)雜度、最壞情況下的時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度），算法的空間復(fù)雜度（原地工作、額外空間）。對(duì)O的理解4.編程常用頭文件：

#include<string.h>#include<ctype.h>#include<malloc.h>//malloc(),alloc(),realloc()等

#include<limits.h>//INT_MAX等

#include<stdio.h>//EOF(=^Z或F6),NULL#include<stdlib.h>//srand(),rand(),exit(n)#include<io.h>//eof()#include<math.h>//floor(),ceil(),abs()#include<process.h>//exit(n)#include<iostream.h>//cout,cin5.函數(shù)結(jié)果狀態(tài)代碼

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//Status是函數(shù)的類型,//其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等

typedefintBoolean;//Boolean是布爾類型,其//值是TRUE或FALSE6.上機(jī)環(huán)境及注意事項(xiàng)

上機(jī)環(huán)境VC++6.0,