數(shù)據(jù)結構第1章 緒論

計算機學院信管系

*

申艷梅

shenyanm@數(shù)據(jù)結構

*

編程基礎程序=算法+數(shù)據(jù)結構(NiklausWirth教授)計算機及相關專業(yè)考研考博課程計算機等級考試課程程序員考試課程面試的主要內(nèi)容學習數(shù)據(jù)結構的目的和重要性

*

課程學習指導1.提前預習、認真聽課、多做練習、勤于上機實踐2.注意先修課程的知識準備離散數(shù)學、C語言3.注意循序漸進：基本概念、基本思想、基本步驟、算法設計4.注意培養(yǎng)算法設計的能力理解所講算法、對此多做思考：若問題要求不同，應如何選擇數(shù)據(jù)結構，設計有效的算法課程特點：內(nèi)容抽象、概念性強、內(nèi)容靈活、不易掌握

*

平時成績:30%作業(yè)、小測驗、實驗課堂紀律期末成績:70%(閉卷筆試)考核方式課時安排：課程總學時64學時，其中理論教學學時數(shù)48學時，實踐教學學時數(shù)16學時。每周4學時。

*

教材和參考書教材：《數(shù)據(jù)結構》978-7-115-23490

嚴蔚敏，李冬梅，人民郵電出版社出版

參考書：《數(shù)據(jù)結構C語言版》，嚴蔚敏，清華大學出版社《數(shù)據(jù)結構——用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆等，清華大學出版社《數(shù)據(jù)結構與算法》張銘高教出版社

第1章緒論1.了解數(shù)據(jù)結構研究的主要內(nèi)容2.掌握數(shù)據(jù)結構中涉及的基本概念3.掌握算法的時間、空間復雜度及其分析的簡易方法

教學目標1.1數(shù)據(jù)結構的研究內(nèi)容1.2基本概念和術語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4算法與算法分析教學內(nèi)容電子計算機的主要用途：

早期：主要用于數(shù)值計算

后來：處理逐漸擴大到非數(shù)值計算領域，能處理多種復雜的具有一定結構關系的數(shù)據(jù)1.1數(shù)據(jù)結構的研究內(nèi)容書目自動檢索系統(tǒng)書目文件線性表人機對奕問題樹……..……..…...…...…...…...人機對弈：智能化浪潮已經(jīng)洶涌而來

人機對弈阿爾法棋4比1擊敗李世石,這個事件非常轟動，全球有10多億人次在觀看比賽。這樣一次對弈，會讓所有人得到洗禮。這是個啟蒙運動，受傷的是一些專業(yè)選手，但會激勵兩群人：第一是程序員，第二是IT創(chuàng)業(yè)人士。我們相信機器智能可以到來,未來的世界已經(jīng)不僅是講“互聯(lián)網(wǎng)+”，而是到了我們與機器為舞、為伴的世界。這是李世石和AlphaGo對弈里可以看到的未來。

*

例：交通最短路徑問題：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？圖AEDCB100605020301010其他：網(wǎng)絡工程圖、網(wǎng)絡通信圖等等求解非數(shù)值計算的問題：設計出合適的數(shù)據(jù)結構及相應的算法即：首先要考慮對相關的各種信息如何表示、組織和存儲？數(shù)據(jù)結構的研究內(nèi)容為：研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作。數(shù)據(jù)結構課程的形成和發(fā)展：形成階段：60年代初期，“數(shù)據(jù)結構”有關的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結構”被列入美國一些大學計算機科學系的教學計劃。發(fā)展階段：數(shù)據(jù)結構的概念不斷擴充，包括了網(wǎng)絡、集合代數(shù)論、關系等“離散數(shù)學結構”的內(nèi)容。70年代后期，我國高校陸續(xù)開設該課程?！稊?shù)據(jù)結構》所處的地位：介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程北京林業(yè)大學信息學院

*

數(shù)據(jù)結構在計算機學科中的地位

課程目的能夠分析研究計算機加工的對象的特性，獲得其邏輯結構，根據(jù)需求，選擇合適存貯結構及其相應的算法；學習一些常用的算法；復雜程序設計的訓練過程，要求編寫的程序結構清楚和正確易讀；初步掌握算法的時間分析和空間分析技術1、數(shù)據(jù)（data)—所有能輸入到計算機中去的描述客觀事物的符號

數(shù)值數(shù)據(jù)：整數(shù)、浮點數(shù)等，主要用于工程和科學計算。非數(shù)值數(shù)據(jù)：字母，表格，程序，符號，圖形，樹、圖、網(wǎng)頁、節(jié)點等。2、數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱結點（node）或記錄（record）3、數(shù)據(jù)項（dataitem）—有獨立含義的數(shù)據(jù)最小單位，也稱域(field)三者之間的關系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：學生表>個人記錄>學號、姓名……1.2基本概念和術語整數(shù)數(shù)據(jù)對象N={0,1,2,…}學生數(shù)據(jù)對象學生記錄的集合4、數(shù)據(jù)對象(DataObject)：相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集5、數(shù)據(jù)結構（DataStructure）是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)結構是帶“結構”的數(shù)據(jù)元素的集合，“結構”就是指數(shù)據(jù)元素之間存在的關系。數(shù)據(jù)結構的兩個層次：邏輯結構---數(shù)據(jù)元素間抽象化的相互關系，與數(shù)據(jù)的存儲無關，獨立于計算機，它是從具體問題抽象出來的數(shù)學模型。存儲結構（物理結構）----數(shù)據(jù)元素及其關系在計算機存儲器中的存儲方式。劃分方法一（1）線性結構----有且僅有一個開始和一個終端結點，并且所有結點都最多只有一個直接前趨和一個后繼。例如：線性表、棧、隊列、串（2）非線性結構----一個結點可能有多個直接前趨和直接后繼。例如：樹、圖邏輯結構線性結構——一個對一個，如線性表、棧、隊列樹形結構——一個對多個，如樹集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系圖形結構——多個對多個，如圖邏輯結構劃分方法二存儲結構分為：順序存儲結構——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關系鏈式存儲結構——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關系索引存儲

便于查找散列存儲存儲結構元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲1536元素21400元素11346元素3∧元素41345h存儲地址

存儲內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈式存儲

h邏輯結構和存儲結構都相同,但運算不同,則數(shù)據(jù)結構不同.例如,棧與隊列對于一種數(shù)據(jù)結構,常見的運算插入刪除修改查找排序數(shù)據(jù)的運算（操作）

數(shù)據(jù)的邏輯結構

數(shù)據(jù)的存儲結構數(shù)據(jù)的運算：插入、刪除、修改、查找、排序

線性結構

非線性結構

順序存儲

鏈式存儲線性表

棧、隊列

串、數(shù)組樹形結構圖形結構邏輯結構唯一存儲結構不唯一運算的實現(xiàn)依賴于存儲結構定義：在一種程序設計語言中，變量所具有的數(shù)據(jù)種類數(shù)據(jù)類型FORTRAN語言：整型、實型、和復數(shù)型C語言：基本數(shù)據(jù)類型：

charintfloatdoublevoid構造數(shù)據(jù)類型：數(shù)組、結構體、共用體、文件

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合,以及定義于這個集合上的一組運算的總稱

(ADT:AbstractDataTypes)抽象數(shù)據(jù)類型--更高層次的數(shù)據(jù)抽象由用戶定義，用以表示應用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關的操作抽象數(shù)據(jù)類型抽象：從許多事物中，舍棄個別的、非本質(zhì)的屬性，抽出共同的、本質(zhì)的屬性，叫抽象，是形成概念的重要手段。ADT特點：①降低了軟件設計的復雜性

②提高了程序的可讀性和可維護性

抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對象D上的關系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關系：<數(shù)據(jù)關系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式北京林業(yè)大學信息學院例如，抽象數(shù)據(jù)類型復數(shù)的定義：

數(shù)據(jù)對象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關系：

R1＝{<e1,e2>|e1是復數(shù)的實數(shù)部分

|e2

是復數(shù)的虛數(shù)部分}ADTComplex{基本操作：

Creat(&C,x,y)

操作結果：構造復數(shù)C,其實部和虛部分別被賦以參數(shù)x

和y

的值。

GetReal(C,&realPart)

初始條件：復數(shù)已存在。操作結果：用realPart返回復數(shù)Z的實部值。

GetImag(C,&ImagPart)

初始條件：復數(shù)已存在。操作結果：用ImagPart返回復數(shù)Z的虛部值。

Add(C1,C2,&sum)

初始條件：C1,C2是復數(shù)。操作結果：用sum返回兩個復數(shù)C1,C2的和值。......

}ADTComplex抽象數(shù)據(jù)類型查找插入刪除修改線性表接口或用戶界面數(shù)據(jù)類型的物理實現(xiàn)封裝信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離復習c/c++語言的內(nèi)容：c/c++程序的結構組成與不同

1、結構體

2、定義類型

3、指針類型及操作

4、動態(tài)空間的分配和刪除

5、函數(shù)調(diào)用及參數(shù)傳遞（引用類型）6、文件預處理（include）

7、c++中的引用類型及輸入、輸出8、多文件的程序結構

標準C++#include<iostream>usingnamespacestd;intadd(intx，inty)

{returnx+y;}

intmain()

{inta=10,b=20,z;//cin>>a>>b;

z=add(a,b);//函數(shù)調(diào)用

out<<"x+y"<<"="<<z;<<endl;return0;

}

c/c++程序的結構組成與不同傳統(tǒng)C++#include<iostream.h>intadd(int

x，inty)

{returnx+y;}

intmain()

{inta=10,b=20,z;//cin>>a>>b;

z=add(a,b);//函數(shù)調(diào)用

out<<"x+y"<<"="<<z<<endl;return0;

}

C++程序由注釋、編譯預處理和程序主體組成。C++程序可以由一個程序單元或多個程序單元構成?每一個程序單元作為一個文件?一個面向過程的C++程序的組織結構一般由三部分組成：類型的定義（用戶自定義類型）、函數(shù)的實現(xiàn)和主函數(shù)。如果比較的小程序，可以將這三部分寫在同一個文件中。在規(guī)模較大的項目中，往往需要多個程序文件，通常一個項目（程序）可以劃分為三個文件：

類型聲明（*.h文件）函數(shù)實現(xiàn)函數(shù)使用文件（main()所在的*.cpp文件）。對于更為復雜的程序，每一個類型（數(shù)據(jù)結構）都有單獨的定義和實現(xiàn)文件，采用這樣的組織結構可以對不同的文件進行單獨的編寫、編譯，最后再連接，利于程序的調(diào)試和修改，實現(xiàn)多人合作開發(fā)。如圖2-1所示：假如學校的軟件學院2011級的同學有三個名字叫王曉的同學區(qū)分同名學生std命名空間標準C++將新格式頭文件中的內(nèi)容全部放到了std命名空間中，而非新格式的頭文件中的內(nèi)容被放到了全局命名空間中。如果程序中要引用標準C++新格式頭文件中的函數(shù)，就需要在程序中使用usingnamespacestd;語句將std命名空間中的標識符引入到全局命名空間。雖然C++編譯器提供了對新老格式頭文件的同時支持，但標準的C++具有更多的新特性和功能，在程序設計中建議使用新標準C++。

在數(shù)據(jù)中，經(jīng)常有一些既有聯(lián)系，類型又不同的數(shù)據(jù)，它們又需要一起處理。如：圖書數(shù)據(jù)字段：書號書名價格類型：charcharint

C語言允許用戶按自己的需要將不同的基本類型構造成一種特殊類型，即結構體。結構體/用戶自定義類型struct結構名{

type成員1；

type成員2；

…

type成員n；

};

結構類型中所含的成員項及其類型。結構的定義確定了如下兩點：⑴定義結構類型，確定結構中的成員項的名稱及類型。⑵指明該結構類型的變量在內(nèi)存中的組織形式。structBook{charno[15];charname[50];floatprice;};Bookb[10];//正確c++structBookb[10];//cstruct{charno[15];charname[50];floatprice;}Book;Bookb[10];//錯誤typedef

struct{charno[15];charname[50];floatprice;}Book;Bookb[10];//正確

*

函數(shù)調(diào)用時傳送給形參表的實參必須與形參在類型、個數(shù)、順序上保持一致參數(shù)傳遞有兩種方式傳值方式（參數(shù)為整型、實型、字符型等）傳地址參數(shù)為指針變量參數(shù)為引用類型參數(shù)為數(shù)組名C++中的參數(shù)傳遞

*

voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(floatm,floatn){floattemp;temp=m;m=n;n=temp;}傳值方式把實參的值傳送給函數(shù)局部工作區(qū)相應的副本中，函數(shù)使用這個副本執(zhí)行必要的功能。函數(shù)修改的是副本的值，實參的值不變

*

傳地址方式－－指針變量作參數(shù)voidmain(){floata,b,*p1,*p2;cin>>a>>b;

p1=&a;p2=&b;swap(p1,p2);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){floatt;t=*m;*m=*n;*n=t;}形參變化影響實參

*

傳地址方式－－引用類型作參數(shù)引用：它用來給一個對象提供一個替代的名字。#include<iostream.h>voidmain(){ inti=5; int&j=i; i=7; cout<<"i="<<i<<"j="<<j;}j是一個引用類型,代表i的一個替代名i值改變時,j值也跟著改變，所以會輸出i=7j=7什么是引用？？？

*

voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float＆m,float＆n){floattemp;temp=m;m=n;n=temp;}傳地址方式－－引用類型作參數(shù)1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。它有些類似C語言中的結構（struct)類型，但增加了相關的操作教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具但上機時要用具體語言實現(xiàn)，如C或C++等(1)預定義常量及類型//函數(shù)結果狀態(tài)代碼#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結果狀態(tài)代碼。typedefintStatus;(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。inta;typedefintElemType;ElemTypea;(3)算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語句序列；

}引用類型作參數(shù)返回結果（4）內(nèi)存的動態(tài)分配與釋放使用new和delete動態(tài)分配和釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間

delete指針變量;（5）賦值語句（6）選擇語句（7）循環(huán)語句（8）使用的結束語句形式有：函數(shù)結束語句return循環(huán)結束語句break;異常結束語句exit（異常代碼）；（9）輸入輸出語句形式有：輸入語句cin(scanf())輸出語句cout(printf())

cin>>a>>b;

cout<<a<<""<<b<<endl;（10）擴展函數(shù)有：求最大值max求最小值min例如，抽象數(shù)據(jù)類型復數(shù)的定義：

數(shù)據(jù)對象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關系：

R1＝{<e1,e2>|e1是復數(shù)的實數(shù)部分

|e2

是復數(shù)的虛數(shù)部分}ADTComplex{基本操作：

Creat(&C,x,y)

操作結果：構造復數(shù)C,其實部和虛部分別被賦以參數(shù)x

和y

的值。

GetReal(C,&realPart)

初始條件：復數(shù)已存在。操作結果：用realPart返回復數(shù)Z的實部值。

GetImag(C,&ImagPart)

初始條件：復數(shù)已存在。操作結果：用ImagPart返回復數(shù)Z的虛部值。

Add(C1,C2,&sum)

初始條件：C1,C2是復數(shù)。操作結果：用sum返回兩個復數(shù)C1,C2的和值。......

}ADTComplextypedefstruct{

float

Realpart；

float

Imagpart；}Complex；抽象數(shù)據(jù)類型復數(shù)的表示與實現(xiàn)//-----基本操作的實現(xiàn)voidCreat(Complex&C,floatx,floaty)

{C.Realpart=x;C.Imagpart=y;}//-----存儲結構的定義----表示floatGetReal(complexC)//返回復數(shù)C

的實部值

voidAdd(Complexz1,Complexz2,Complex&sum){//以sum返回兩個復數(shù)z1,z2的和

sum.Realpart=z1.Realpart+z2.Realpart;sum.Imagpart=z1.Imagpart+z2.Imagpart;}{returnC.Realpart;}{其它省略}算法定義：一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列算法的描述：

自然語言流程圖程序設計語言

偽碼1.4算法和算法分析算法的特性：

輸入

有0個或多個輸入輸出

有一個或多個輸出(處理結果)

確定性

每步定義都是確切、無歧義的有窮性

算法應在執(zhí)行有窮步后結束有效性

每一條運算應足夠基本算法的評價正確性可讀性健壯性高效性（時間代價和空間代價）算法效率：用依據(jù)該算法編制的程序在計算機上執(zhí)行所消耗的時間來度量 算法的效率的度量事后統(tǒng)計事前分析估計1.事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分

缺點：必須先運行依據(jù)算法編制的程序所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

2.事前分析估計：一個高級語言程序在計算機上運行所消耗的時間取決于：

依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———使用絕對時間單位衡量算法效率不合適算法中基本語句重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作：T(n)=O(f(n))

時間復雜度的漸進表示法數(shù)學符號“O”的定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)

=

O(f(n))表示存在正的常數(shù)C和n0，使得當n≥n0時都滿足0≤T(n)≤Cf(n)。表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復雜度。n越大算法的執(zhí)行時間越長排序：n為記錄數(shù)矩陣：n為矩陣的階數(shù)多項式：n為多項式的項數(shù)集合：n為元素個數(shù)樹：n為樹的結點個數(shù)圖：n為圖的頂點數(shù)或邊數(shù)算法中重復執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的語句對算法運行時間的貢獻最大例如：T(n)=4n3+3n2+2n+1=

O(n3)其中c=10,n0=1n*n階矩陣加法：for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=a[i][j]+b[i][j]; 語句的頻度（FrequencyCount):重復執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;找出語句頻度最大的那條語句作為基本語句計算基本語句的頻度得到問題規(guī)模n的某個函數(shù)f(n)取其數(shù)量級用符號“O”表示分析算法時間復雜度的基本方法f(n)=n2T(n)=O(n2)

voidexam(floatx[][],intm,intn){floatsum[];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++)

cout<<i<<“:”<<sum[i]<<endl;

}時間復雜度是由嵌套最深層語句的頻度決定的f(n)=m*nT(n)=O(m*n)例1：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]=c[i][j]+a[i][k]*b[k][j];} 算法中的基本操作語句為c[i][j]=c[i][j]+a[i][k]*b[k][j];

例2：for(i=1;i<=n;i++)

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

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

x=x+1;語句頻度

=定理1.1若f(n)=amnm+am-1nm-1+

+a1n+a0是m次多項式，則T(n)=O(nm)。忽略所有低次冪項和最高次冪系數(shù)，體現(xiàn)出增長率的含義例3：分析以下程序段的時間復雜度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時間復雜度T(n)=O(log2n)例4：順序查找，在數(shù)組a[i]中查找值等于e的元素，返回其所在位置。

for(i=0;i<n;i++)if(a