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

計(jì)算機(jī)學(xué)院信管系

*

申艷梅

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

*

編程基礎(chǔ)程序=算法+數(shù)據(jù)結(jié)構(gòu)(NiklausWirth教授)計(jì)算機(jī)及相關(guān)專業(yè)考研考博課程計(jì)算機(jī)等級(jí)考試課程程序員考試課程面試的主要內(nèi)容學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的和重要性

*

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

*

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

*

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

嚴(yán)蔚敏，李冬梅，人民郵電出版社出版

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

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

教學(xué)目標(biāo)1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法與算法分析教學(xué)內(nèi)容電子計(jì)算機(jī)的主要用途：

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

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

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

*

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

*

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)學(xué)科中的地位

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

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

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

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

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

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

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：插入、刪除、修改、查找、排序

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表

棧、隊(duì)列

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

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

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

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

②提高了程序的可讀性和可維護(hù)性

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

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

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

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

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

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

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

數(shù)據(jù)關(guān)系：

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

|e2

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

Creat(&C,x,y)

操作結(jié)果：構(gòu)造復(fù)數(shù)C,其實(shí)部和虛部分別被賦以參數(shù)x

和y

的值。

GetReal(C,&realPart)

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

GetImag(C,&ImagPart)

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

Add(C1,C2,&sum)

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

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

1、結(jié)構(gòu)體

2、定義類型

3、指針類型及操作

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

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

7、c++中的引用類型及輸入、輸出8、多文件的程序結(jié)構(gòu)

標(biāo)準(zhǔn)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++程序的結(jié)構(gòu)組成與不同傳統(tǒng)C++#include<iostream.h>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++程序由注釋、編譯預(yù)處理和程序主體組成。C++程序可以由一個(gè)程序單元或多個(gè)程序單元構(gòu)成?每一個(gè)程序單元作為一個(gè)文件?一個(gè)面向過程的C++程序的組織結(jié)構(gòu)一般由三部分組成：類型的定義（用戶自定義類型）、函數(shù)的實(shí)現(xiàn)和主函數(shù)。如果比較的小程序，可以將這三部分寫在同一個(gè)文件中。在規(guī)模較大的項(xiàng)目中，往往需要多個(gè)程序文件，通常一個(gè)項(xiàng)目（程序）可以劃分為三個(gè)文件：

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

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

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

type成員1；

type成員2；

…

type成員n；

};

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

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

*

函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致參數(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í)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副本中，函數(shù)使用這個(gè)副本執(zhí)行必要的功能。函數(shù)修改的是副本的值，實(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í)參

*

傳地址方式－－引用類型作參數(shù)引用：它用來給一個(gè)對(duì)象提供一個(gè)替代的名字。#include<iostream.h>voidmain(){ inti=5; int&j=i; i=7; cout<<"i="<<i<<"j="<<j;}j是一個(gè)引用類型,代表i的一個(gè)替代名i值改變時(shí),j值也跟著改變，所以會(huì)輸出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ù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。它有些類似C語(yǔ)言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作教材中用的是類C語(yǔ)言（介于偽碼和C語(yǔ)言之間）作為描述工具但上機(jī)時(shí)要用具體語(yǔ)言實(shí)現(xiàn)，如C或C++等(1)預(yù)定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。inta;typedefintElemType;ElemTypea;(3)算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語(yǔ)句序列；

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

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

cin>>a>>b;

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

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

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

數(shù)據(jù)關(guān)系：

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