數據結構任課教師：邱保志Email：iebzqiu@單位：鄭州大學信息工程學院持之以恒天道酬勤為什么要學習數據結構？介于數學、計算機軟件、硬件三者之間的核心課程一般程序設計（尤指非數值計算的程序設計）的基礎設計和實現編譯程序、操作系統、數據庫系統及其它系統程序和大型應用程序的重要基礎。如何利用計算機解決實際應用問題？需經過以下三步驟：從具體問題中抽象出一個適當的數學模型。設計一個解此數學模型的算法編程調試，得到最終答案

NiklausWirth：

Algorithm+DataStructures=Programs

算法:處理問題的策略

數據結構:問題的數學模型程序:為計算機處理問題編制一組指令集登錄號書名作者出版單位出版時間N.3.73.762數據結構嚴蔚敏吳偉民清華大學出版社2003.12圖書館的書目檢索系統自動化問題數學模型一對一的線性結構人機對弈問題數學模型一對多的樹結構“井”字棋對弈“樹”先手：C1C9C4C2C12C10C11C5C3C6C7C8計算機專業課程開設先后關系圖數學模型多對多的圖形結構計算機專業課程開設問題怎樣學數據結構？牢記基本概念和經典算法聯系實際，富于聯想總結算法之間的共性和特性。忌：求偏、求難、重算法輕概念。三階段：模仿->總結->創新

本書的內容簡介第一章:綜述數據結構等基本概念，介紹算法和算法分析(3/2周)第二章-第七章:討論線性表(3周)、棧和隊列(2周)、串(2周)

、數組和廣義表(2周)

、樹和二叉樹(2周)

、圖(2周)等基本類型的數據結構、物理結構及其相關操作的實現。第九章:靜態查找表和動態查找表。(2周)第十章:介紹五種內排序方法(2周)復習（1/2周）1.2基本概念和術語數據：信息的載體，是描述客觀事物的數、字符及所有能輸入到計算機中被計算機程序識別和處理的符號的集合。數值性數據非數值性數據數據元素：數據的基本單位一個數據元素可由若干個數據項組成。數據項是數據不可分割的最小單位。數據對象：數據的子集。具有相同性質的數據元素集合。例如：整數對象N={0,1,2,…}數據結構（邏輯結構）數據結構：相互間存在一種或多種特定關系的數據元素集合。結構：數據元素相互之間的關系特定關系：特定關系數據結構舉例沒有關系集合正整數一對一關系線性表圖書管理一對多關系樹棋局對弈樹多對多關系圖（網）課程開設先后關系圖數據結構的形式定義DS=(D,S)D：數據元素的有限集合。設Ｄ＝{a1,a2,…,ai,aj,…,an}S：定義在D上的關系的有限集合。若aiRaj,則＜ai,aj＞∈S若aiRaj,且ajRai,則(ai,aj)∈S例：復數可定義為一種數據結構：

COMPLEX=(C,R)C：含有兩個實數的集合{C1,C2}；R：{P}是定義在C上的一種關系{<C1,C2>}課上習題：T=(K,R)，畫出它所對應的邏輯結構K={1,2,3,4,5,6}；Ｒ={r}r={<1,2>,<1,3>,<2,4>,<2,5,>,<3,6>}aiajaiaj線性結構樹形結構456231ABEDCF圖形結構125643集合結構四類基本邏輯結構關系圖

數據結構在計算機中的表示：數據元素的表示數據元素之間關系的表示順序映象：借助元素在存儲器的相對位置表示數據元素之間的邏輯關系。對應于順序存儲結構(sequentialsets).非順序映象：利用指示元素存儲地址的指針表示數據元素間的邏輯關系。對應于鏈式存儲結構(linkedlists)索引樹(indexedtrees)散列表(hashtables)數據的物理結構(存儲結構)數據邏輯結構和物理結構之間的關系關系：任意一個算法的設計取決于選定的邏輯結構算法的實現依賴于采用的物理結構。實際應用算法數據結構線性結構非線性結構存儲結構

順序存儲結構非順序存儲結構定位(查找)加法、乘法比較、移動（邏輯）(物理)數據結構主要研究什么？解決問題時可能遇到的典型的邏輯結構邏輯結構的存儲映象（物理結構）數據結構的相關操作及其實現（算法）數據類型數據類型：一組性質相同的值的集合以及定義于該值集上的一組操作的總稱。例：C語言中整型變量值：定義在某區間上的整數操作：加、減、乘、除、取模按值的不同特性分：原子類型：值不可再分C的五種基本數據類型:char,int,float,double,void結構類型：值由若干個成分按某種結構組成抽象數據類型一個數據模型及定義在該模型上的一組操作。按照值域的不同特性:原子類型（值不可分解）、固定聚合類型（值有確定數目的成分）、可變聚合類型（成分的數目不確定）。例：抽象數據類型：矩陣=矩陣+(求轉置、加、乘、逆等）形式定義：DS=(D,S,P)。

D：數據對象

S：D上的關系集，

P：對D的基本操作集。構造性操作：插入、刪除、修改非構造性操作：查找、排序抽象數據類型的定義格式(僅適用于本書)ADT抽象數據類型名{

數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

基本操作：〈基本操作的定義〉}ADT抽象數據類型名基本操作的定義格式為基本操作名（參數表）初始條件：〈初始條件描述〉

操作結果：〈操作結果描述〉參數表有兩種參數：賦值參數：只為操作提供輸入值；引用參數：以&打頭，除可提供輸入值外，還將返回操作結果。初始條件描述了操作執行前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數據類型舉例-矩陣ADTMatrix{

數據對象:D={ai,j|i=1,2,…,m;j=1,2,…,n;ai,j∈ElemSet}

數據關系:R={Row,Col}Row={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}Col={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}

基本操作：

CreateMatrix(&M)

DestroyMatrix(&M)

PrintMatrix(&M)

AddMatrix(M,N,&Q)

SubMatrix(M,N,&Q)

MultMatrix(M,N,&Q)

TransposeMatrix(M,&T)}ADTMatrix1.3類Ｃ語言的語法規則1、預定義常量和類型：2、數據結構的描述，數據元素類型的定義3、基本操作的算法可以使用的函數表示4、算法描述中可以使用的賦值語句形式5、算法描述中可以使用的選擇結構語句形式6、算法描述中可以使用的循環結構語句形式7、描述算法中可以使用的結束語句形式8、算法描述中可以使用的輸入輸出語句形式9、算法描述中可以使用的注釋格式10、算法描述中可以使用的擴展函數11、算法描述中可以使用的邏輯運算的約定類Ｃ語言的語法規則示例例1typedef

intStatus;voidexample_1(){Statusa[10];

a[0..9]=0;}例2#defineOK1typedef

intStatus;Statusexample_2(intx,inty){

if(x>y)x<->y;

returnOK;}類Ｃ語言的語法規則示例（續）例3typedef

structstudent{

charid[5];

charname[11];

int

age;

intmath;

inteng;

int

ds;

int

os;}student;voidexample_3(){students;

s=('','',0,0,0,0,0);}附加內容：算法的描述方法步驟法程序流程圖N-S圖偽碼步驟法順序查找數據序列中某個特定值Step1：輸入數據序列data[n]和欲查找值keyStep2：從序列中的最后一個元素開始查找Step3：若該元素值不等于key，查找前一項．Step4

：若該元素值等于key，表示查找成功，返回key在序列中的位置，去第六步．Step5：如果數據全部查找過但未能找到key，表示查找失敗，返回０。Step6：結束程序流程圖——五種基本控制結構程序流程圖舉例開始輸入待查找序列data[n]查找成功，返回i輸入要查找的值key查找失敗返回０data[i]==key從最后一個元素開始查找待查序列全查過ＹＹNN順序查找數據序列中某特定值結束i--N-S圖N-S圖也叫盒圖，一種符合結構化程序設計原則的圖形描述工具。五種基本控制結構由五種圖形構件表示：N-S圖舉例順序查找數據序列中某特定值F輸入待查找序列data[n]輸入要查找的值key從最后一個元素開始查找

data[i]==key

查找成功返回key所在位置

全查過查找失敗返回０TFT下一次循環Dowhile(data!=key)偽碼以夾雜程序語法和自然語言的形式來描述解決問題的方法，有類C、類PASCAL語言等。本書用的是類C語言。順序查找數據序列中某特定值，由類C給出其算法StatusSearch_Seq(SqList

L,KeyTypekey){L.elem[0]=key;for(i=L.length;!EQ(L.elem[i],key);i--);returni;}Search_Seq.h代碼//說明部分#include<stdio.h>//包含預編譯頭文件#defineTRUE1

//宏定義#defineFALSE0typedef

int

KeyType;//類型別名的定義typedef

struct{

KeyType*elem;

intlength;}SqList;bool

EQ(int

i,intj)

//判斷兩個整數是否相等{ if(i==j)

returnTRUE;

else

returnFALSE;}順序查找數據序列中某特定值的程序代碼stdio.hmath.hstring.hmalloc.h//函數實現void

Construction(SqList&L)

//構造無序序列{inti;

printf(“inputthelengthofdata:\n");

scanf("%d",&L.length);

L.elem=(KeyType*)malloc((L.length+1)*sizeof(KeyType));

printf(“inputthekey:\n”);

//輸入待查找的關鍵字

for(i=1;i<=L.length;i++)

scanf("%d",&L.elem[i]);}int

Search(SqList

L,KeyTypekey)

//查找函數{

inti; L.elem[0]=key; for(i=L.length;!EQ(L.elem[i],key);--i);

returni;}順序查找數據序列中某特定值的程序代碼Search_Seq.cpp代碼#include“search_seq.h"voidmain(){ KeyTypekey;

SqListL;

printf(“inputkey:\n”);

scanf(“%d”,&key);

//讀入要查找的值

Construction(L);

//創建待查找數據序列

int

position=Search(L,key);

//查找

printf("thekeyislocatedin%d",position);}順序查找數據序列中某特定值的程序代碼1.4算法和算法分析算法的定義：對特定問題求解步驟的一種描述，是指令的有限序列，一條指令表示一個或多個操作。操作分為：數值計算：加、減、乘、除等算術運算非數值計算：檢索、排序、插入、刪除。算法的特性：有窮性：算法應在執行有窮步后結束確定性：每步定義都是確切、無歧義的可行性：算法中描述的操作都可通過已經實現的基本運算執行有限次實現輸入：有0個或多個輸入輸出：有一個或多個輸出(處理結果)算法與程序的區別算法設計的要求正確性：程序不含語法錯誤；程序對于幾組輸入數據能夠得出滿足要求的結果；對精心選擇帶有刁難性的幾組數據能得出滿足要求的結果；程序對于一切合法的輸入數據都能產生滿足要求的結果。可讀性：易于閱讀和交流，其次是機器運行。

健壯性：當輸入數據非法時，算法能適當地作出反應或進行處理，保證不會產生莫名其妙的輸出結果。處理出錯的方法是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理，不應中斷程序的執行。高效率和低存儲量需求：兩者都與問題的規模有關。1.4.3算法效率的度量事后統計：運用計算機的計時功能統計算法的運行時間。缺陷：要運行算法對應的程序；時間統計結果依賴于計算機軟、硬件環境；事前分析估計：算法消耗的時間與下列因素有關：算法采用的策略問題的規模書寫程序的語言編譯器產生的機器代碼的質量計算機執行指令的速度。doublestart,stop;time(&start); intk=search_seq(ST,key);time(&stop); doublerunTime=stop-start;printf(“%f”,runTime);算法的時間量度算法的時間量度與問題的規模n有關從算法中選取一種對于所研究問題來說是基本操作的原操作，以該基本操作重復執行次數作為算法的時間量度。算法中基本操作重復執行次數是問題規模n的某個函數f(n)(漸近)時間復雜度：算法的時間量度記作(n)=O(f(n))，表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱為算法的漸近時間復雜度。簡稱時間復雜度。語句頻度：語句重復執行的次數。兩個n*n矩陣相乘的算法

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];

}例１問題規模:n*n原操作:c[i][j]+=a[i][k]*b[k][j];基本操作重復執行的次數:f(n)=n3算法時間度:T(n)=O(f(n))=O(n3)例２程序段語句頻度時間復雜度{++x;s=0}@

for(i=1;i<=n;++i){++x;s+=x;}@for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}@i=1;while(i<=n)i=i*2;@1O(1)nO(n)n2log2nO(log2n)O(n2)大O表示法的加法規則和乘法規則加法規則針對并列程序段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

乘法規則針對嵌套程序段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

特例：若T1(n)=O(c)，T2(n)=O(f(n))則T(n)=T1(n)*T2(n)=O(c*f(n))=O(f(n))問題規模:m*n原操作:

sum[i]+=x[i][j];

基本操作重復執行的次數:f(n)=m*n算法時間度:T(n)=O(f(n))=O(m*n)

voidadd(floatx[][],intm,intn){for(inti=0;i<m;i++){sum[i]=0.0;

for(intj=0;j<n;j++) sum[i]+=x[i][j];}for(i=0;i<m;i++)

printf(“%f”,sum[i]);}例３O(max(m*n,m))問題規模:n原操作:

a[j]<->a[j+1];基本操作重復執行的次數:

不定算法時間度:T(n)=O(n2)例４voidbubble_sort(int

a[],int

n){for(i=n-1,change=TRUE;i>=1,change;--i){change=FALSE;//判斷是否有相鄰元素交換

for(j=0;j<i;++j)

if(a[j]>a[j+1]){a[j]<->a[j+1];change=TRUE;}}}例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}問題規模:n原操作:

a[i][j]=x;基本操作重復執行的次數:

難以精確計算(1+1+2+…+n-2)算法時間度:T(n)=O(n2)算法的設計、選取和時間復雜度分析的原則應該盡可能選用多項式階的算法，不希望用指數階算法的時間復雜度只考慮問題規模n的增長率，在難以精確計算基本操作執行次數（或語句頻度）時，只需求得它關于n的增長率或階即可。算法中基本操作重復執行次數隨問題的輸入數據集不同而不同，要考慮最壞情況下的時間復雜度。例６：百錢買百雞問題100元錢買100只雞，母雞每只5元，公雞每只3元，小雞3只1元，問共可以買多少只母雞、多少只公雞、多少只小雞？解：設母雞、公雞、小雞各為x,y,z只。則有：

x+y+z=100 5x+3y+z/3=100方法1：for(i=0;i<=100;i++)

for(j=0;j<=100;j++)

for(k=0;k<=100;k++){

if(k%3==0&&i+j+k==100&&5*I+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k);

}方法2：用兩重循環：

for(i=0;i<100;i++) for(j=0;j<100;j++) {k=100–i–j;//小雞的數目可以由母雞數和公雞數得到。

if(k%3==0&&5*i+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k); }方法3：用兩重循環：

for(i=0;i<=20;i++)//母雞數不可能超過20只

for(j=0;j<33;j++)//公雞數也不超過33只

{k=100–i–j; if(k%3==0&&5*i+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k); }例６：百錢買百雞問題(續)例６：百錢買百雞問題(續)方法4：用一重循環由x+y+z=100和5*x+3*y+z/3=100合并為一個方程：

14*x+8*y=200,進一步簡化為:7*x+4*y=100x不超過14，并可以進一步判斷x必為4的倍數，有：for(i=0;i<=14;i+=4){ j=(100–7*i)/4; k=100–i–j;

printf(“%d,%d,%d\n”,i,j,k);}方法一的循環次數為：100*100*100方法二的循環次數為：100*100，1萬次；方法三的循環次數為：20*34，680次，方法四的循環次數為：4次，時間復雜度O（n3）O(n2)O(n2)O(n)事前估計與事后統計方法：

例:設兩個矩陣相乘算法的時間復雜度為T(n)=O(n3),兩個10*10的矩陣相乘,執行時間為12ms，請問估計兩個31＊31矩陣相乘的時間。

10312

－－＝－－

313time算法的空間復雜度度量漸進的空間復雜度：算法所需存儲空間的量度。記作：S(n)=O(g(n))，其中n為問題的規模,表示隨著問題規模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。算法的存儲量包括:

1．輸入數據所占空間; 2．程序本身所占空間；

3．額外輔助空間。應掌握的類型題一、數據結構的基本概念

1、在數據結構中，從邏輯上可以把數據結構分成

和

。

2、線性結構中元素之間存在

關系，樹形結構中元素之間存在

關系，圖形結構中元素之間存在

關系。

3、數據元素是數據的最小單位(對/錯)(北京郵電大學1998年)二、算法和時間復雜度分析

1、將下列函數，按它們在n->∞時的無窮大階數，從小到大排序（中科院計算所1995年）

n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n答：log2n,n1/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!c<log2n<n<nlog2n<n2<n3<2n<3n<n!應掌握的類型題2、voidprime(intn){inti=2;

while((n%i)!=0&&i*1.0<sqrt(n))i++;if(i*1.0>sqrt(n))printf(“%disaprimenumber!”);else

printf(“%disnotaprimenumber!”);}答：prime嵌套最深層語句是：i++，頻度由((n%2)!=0&&i*1.0<sqrt(n))決定，時間復雜度是O(√n)鄭州大學歷年試題選（第一章）(2005).已知有實現同一功能的兩個算法A和B，其時間復雜度分別為O(n)和O(n2)，當問題規模n=100時，執行A算法需要10秒鐘，請問在同樣的運行環境下，對同一問題規模能否估計B算法運行的時間？若能，試估計B算法的運行時間；若不能，說明原因。(不能。算法復雜度是指用算法的基本操作重復執行的次數作為時間的量度，不能用一個算法的具體執行時間估計另一個算法具體的執行時間，因為復雜度表示中常量被忽略了。)（2006）

任何一個算法設計取決于選定的數據（邏輯）結構，而算法的實現依賴于采用的存儲結構。（2006）

算法的有窮性的含義是：對任何合法的輸入值，一個算法必須再執行有窮步后結束，且每一步都可在有窮時間內完成，也就是說，在算法中不能使用無限循環語句。

（2001）計算下列程序段中x-=10的執行次數。

X=91;y=100; While(y>0) If(x>100){x-=10;y--;} Elsex++;鄭州大學歷年試題選（第一章續）有一計算矩陣相乘的程序，它的時間復雜度為O(n3)，當上機運行兩個10×10矩陣相乘時，執行時間為5ms，試計算兩個30×30的矩陣相乘所需的時間。1.數據類型是一個值集合和定義在這個值集合上的一組___總稱。

2.若上機運行兩個10×10矩陣相乘，執行時間為5ms，該矩陣相乘算法的時間復雜度T(n)=O(n3)，其中n為矩陣的規模，則利用該算法計算兩個20×20的矩陣相乘時，執行時間為_____________。

3.單鏈表中，邏輯上相鄰的元素的物理位置__________緊鄰。

4.數據元素在計算機中有兩種不同的存儲結構即__________。

5.程序段for(i=1;i<=n;i++)for(j=i;j<=n;j++)k++中k++執行的頻度是______________。設問題規模為n，算法1和算法2的基本語句執行的頻度分別為f(n)、g(n)，用戶從n=1測試到n=103

，發現f(n)<g(n)總成立，請問：算法1的時間復雜度小于算法2的時間復雜度嗎？說明理由。鄭州大學歷年試題選（第一章續）（2004）一個算法的基本語句執行的頻度如下：，其中n是問題的規模，試計算該算法的時間復雜度。

（2007）設n為3的倍數，試分析程序段中帶“＊”語句的執行頻度

for(i=