數據結構課件第1章

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

公共信箱：dsggxx@126.com

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

用計算機解決一個具體問題時，大致需要經過下列幾個步驟:（1）抽象出一個適當的數學模型（2）設計一個解此數學模型的算法（3）編出程序進行測試、修改直至得到最終結果。

例1.田徑賽的時間安排問題設有六個比賽項目，規定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示），設計比賽日程表，使得用盡可能少的時間段完成比賽。姓名項目1項目2項目3丁一馬二張三李四王五跳高標槍標槍鉛球跳遠跳遠100米鉛球100米200米200米跳高200米用無向圖的著色問題解決！！（1）設用如下六個不同的代號代表不同的項目：跳高跳遠標槍鉛球100米200米

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

1.將圖G中的結點按度遞減的順序排列。

2.用沒有用過的顏色對第一個點著色，并且按排列次序，對與前面著色點不相鄰的點著相同顏色。

3.從序列中刪除第2步著過色的點。

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

例:對上例，執行算法第1步結果為：

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

重復執行第2,3步序列變化為：{A,E,B,C,D}{E,B,D}{B}{}

圖的變化為：

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

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

——

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

xyz2.鏈式映象借助于指示元素存儲地址的指針表示元素之間的邏輯關系。xyz……^在不同的編程環境中，存儲結構可有不同的描述方法。

當用高級程序設計語言進行編程時，通常可用高級編程語言中提供的數據類型描述之。數據類型：數據類型是一個值的集合和定義在這組值

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

抽象數據類型可用（D，S，P）三元組表示,其中，D是數據對象，S是D上的關系集，P是對D的基本操作集。

本門課采用下面格式表示抽象數據類型：ADT抽象數據類型名{數據對象：〈數據對象的定義〉數據關系：〈數據關系的定義〉基本操作：〈基本操作的定義〉}ADT抽象數據類型名

其中，數據對象和數據關系的定義用偽碼描述，基本操作的定義格式為：基本操作名（參數表）初始條件：〈初始條件描述〉操作結果：〈操作結果描述〉基本操作有兩種參數：賦值參數只為操作提供輸入值；引用參數以&打頭，除可提供輸入值外，還將帶回操作結果。引用變量和引用參數“初始條件”描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。若初始條件為空，則省略之。

“操作結果”說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。例如：抽象數據類型三元組的定義：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);}運行結果: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);}運行結果x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=7//------采用動態分配的順序存儲結構-----typedefElemType*Triplet;//由InitTriplet分配三個元素存儲空間//Triplet類型是ElemType類型的指針//存放ElemType類型的地址例如：抽象數據類型三元組的定義：P9//bo1_1.cpp抽象數據類型Triplet和ElemType//(由c1_1.h定義)的基本操作(8個)StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//操作結果:構造三元組T,依次置T的三個元素的初

//值為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。

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

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

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

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

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

//操作結果：用e返回T的三個元素中的最大值

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已存在。

//操作結果：用e返回T的三個元素中的最小值

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

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

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

程序正確性的五個層面：（1）不含語法錯誤（2）程序對于n組輸入數據能夠得出滿足規格說明要求的結果。（3）程序對于精心選擇的典型、邊界性的n組輸入數據能得出滿足規格說明要求的結果。（4）程序對于一切合適的輸入數據都能得出滿足規格說明要求的結果（窮舉）。（5）用數學方法證明程序的正確性

嫦娥一號：98.8萬行源代碼，421萬份文件，打印出來有23000頁。用了160多萬行程序證明它的正確性。可讀性、健壯性和效率與存儲量要求。

4）高效率與低存儲量需求

通常，效率指的是算法執行時間；存儲量指的是算法執行過程中所需的最大存儲空間，兩者都與問題的規模有關。算法效率的衡量方法和準則衡量算法效率的方法:缺點：1．必須執行程序

2．其它因素掩蓋算法本質事后統計法：事前分析估算法和算法執行時間有關的因素：1．算法選用的策略2．問題的規模3．編寫程序的語言4．編譯程序產生的機器代碼的質量5．計算機執行指令的速度

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

算法的執行時間

與原操作執行次數之和

成正比

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

基本操作

的原操作，以該基本操作

在算法中重復執行的次數

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

也可以用：如何估算算法的時間復雜度？例：2n3+1000n2+1=O(n3)1000n2+n+1000000=O(n2)例一兩個矩陣相乘voidmult(inta[],intb[],intc[]){//以二維數組存儲矩陣元素，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基本操作:乘法操作時間復雜度:O(n3)例二冒泡排序基本操作:

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

//change為元素進行交換標志

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

4)算法的存儲空間需求算法的空間復雜度定義為:

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

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

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

若所需額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。例如在進行冒泡排序時所需的額外的空間就是一個常數,空間復雜度為O(1)。本章小結1.基本概念和術語數據、數據元素、數據項、數據結構、數據對象、數據結構（邏輯結構、存儲結構、運算）、多形數據類型、抽象數據類型（定義、表示和實現）2.抽象數據類型：描述、類-C中的基本語句和函數3.算法：算法的時間復雜度（漸近時間復雜度、最壞情況下的時間復雜度和平均時間復雜度），算法的空間復雜度（原地工作、額外空間）。對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.函數結果狀態代碼

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//Status是函數的類型,//其值是函數結果狀態代碼，如OK等

typedefintBoolean;//Boolean是布爾類型,其//值是TRUE或FALSE6.上機環境及注意事項

上機環境VC++6.0,