浙江萬(wàn)里學(xué)院計(jì)算機(jī)系

數(shù)據(jù)結(jié)構(gòu)課件第1章緒論第1講2004年9月1浙江萬(wàn)里學(xué)院計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)課程學(xué)分：5共計(jì)16周周學(xué)時(shí)：4（講）+2（實(shí)驗(yàn)）教師：電話：88222400短624289郵箱：yxj@地點(diǎn):7207答疑:星期一下午2浙江萬(wàn)里學(xué)院計(jì)算機(jī)系課程基本要求

記筆記（到課堂聽(tīng)課）成績(jī)構(gòu)成：考勤10%完成書(shū)面作業(yè)10%完成上機(jī)實(shí)驗(yàn)作業(yè)10%期末卷面考試70%考試資格：缺課或作業(yè)1/3取消資格3浙江萬(wàn)里學(xué)院計(jì)算機(jī)系本講主要內(nèi)容1.1數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語(yǔ)

1.2抽象數(shù)據(jù)類型（ADT）和面向?qū)ο蠹夹g(shù)（OOP）

1.3C++語(yǔ)言回顧4浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語(yǔ)1.1.1引言圖書(shū)檔案類問(wèn)題、棋類對(duì)奕問(wèn)題、

交通或通信網(wǎng)問(wèn)題、

非數(shù)值計(jì)算5浙江萬(wàn)里學(xué)院計(jì)算機(jī)系圖書(shū)檔案類問(wèn)題

線性表6浙江萬(wàn)里學(xué)院計(jì)算機(jī)系棋類對(duì)奕問(wèn)題

樹(shù)結(jié)構(gòu)7浙江萬(wàn)里學(xué)院計(jì)算機(jī)系交通或通信網(wǎng)問(wèn)題

圖結(jié)構(gòu)8浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語(yǔ)1.1.2概念與術(shù)語(yǔ)1.數(shù)據(jù)(data):

是描述客觀事物的數(shù)字、字符以及所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)處理的信息的總稱。

9浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1.2概念與術(shù)語(yǔ)2.數(shù)據(jù)元素(DataElement)

是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素除了可以是一個(gè)數(shù)字或一個(gè)字符串以外，它也可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)(DataItem)是有獨(dú)立含義的數(shù)據(jù)的最小單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段(field)。

10浙江萬(wàn)里學(xué)院計(jì)算機(jī)系圖書(shū)檔案類問(wèn)題

線性表11浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1.2概念與術(shù)語(yǔ)3.數(shù)據(jù)對(duì)象(DataObject)

是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(shù)數(shù)據(jù)對(duì)象是集合Ｎ＝{０，±１，±２，…}，字母字符數(shù)據(jù)對(duì)象是集合Ｃ＝{′Ａ′，′Ｂ′，…，′Ｚ′}。圖1.1中的學(xué)籍表也可看成一個(gè)數(shù)據(jù)對(duì)象。12浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1.2概念與術(shù)語(yǔ)4.數(shù)據(jù)的邏輯結(jié)構(gòu)(DataStructure)

是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它是指數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。把數(shù)據(jù)元素間的邏輯上的聯(lián)系，稱之為數(shù)據(jù)的邏輯結(jié)構(gòu)，如:線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)。特點(diǎn)：

抽象關(guān)系，獨(dú)立于計(jì)算機(jī)。13浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1.2概念與術(shù)語(yǔ)5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)設(shè)備中的映象被稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也可以說(shuō)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)，又稱物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)常見(jiàn)存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)結(jié)構(gòu)（順序映象）、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（非順序映象）。14浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.1.2概念與術(shù)語(yǔ)6.“數(shù)據(jù)結(jié)構(gòu)”課程研究?jī)?nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)結(jié)構(gòu)以及定義在它們之上的一組運(yùn)算?？紤]存儲(chǔ)空間的開(kāi)銷和運(yùn)行時(shí)間的效率。數(shù)據(jù)結(jié)構(gòu)課程不僅講授數(shù)據(jù)信息在計(jì)算機(jī)中的組織和表示方法，同時(shí)也訓(xùn)練高效地解決復(fù)雜問(wèn)題程序設(shè)計(jì)的能力。數(shù)據(jù)結(jié)構(gòu)是專業(yè)基礎(chǔ)課、核心課15浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.2抽象數(shù)據(jù)類型（ADT）和

面向?qū)ο蠹夹g(shù)（OOP）1.2.1高級(jí)語(yǔ)言的數(shù)據(jù)類型(DateType)intkey;charch,*st;

只需了解整數(shù)的加、減、乘法或取模運(yùn)算的抽象特性，不必了解“位運(yùn)算”細(xì)節(jié)，就可運(yùn)用高級(jí)語(yǔ)言進(jìn)行程序設(shè)計(jì)。還有用戶自己定義的：數(shù)組、結(jié)構(gòu)體、類

16浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.2.2

抽象數(shù)據(jù)類型（ADT）

（Abstract

DateType）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)如何表示和實(shí)現(xiàn)無(wú)關(guān)。抽象數(shù)據(jù)類型（ADT）和數(shù)據(jù)類型（DataType）實(shí)質(zhì)上是一個(gè)概念。整數(shù)類型就是一個(gè)ADT實(shí)例。所定義的數(shù)據(jù)類型的抽象層次越高，含有該抽象數(shù)據(jù)類型的軟件復(fù)用程度就越高。

17浙江萬(wàn)里學(xué)院計(jì)算機(jī)系例1.1復(fù)數(shù)的抽象數(shù)據(jù)類型ADT。

ADTcomplex

[復(fù)數(shù)ADT的描述]

{數(shù)據(jù)對(duì)象：D={c1,c2c1,c2∈FloatSet}

數(shù)據(jù)關(guān)系：R={<c1,c2>c1是實(shí)部，c2是虛部}

基本操作：創(chuàng)建一個(gè)復(fù)數(shù)

creat(a);

輸出一個(gè)復(fù)數(shù)

outputc(a);

求兩個(gè)復(fù)數(shù)相加之和

add(a,b);

求兩個(gè)復(fù)數(shù)相減之差

sub(a,b);

求兩個(gè)復(fù)數(shù)相乘之積

chengji(a,b);

等等;}ADTcomplex;

18浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.復(fù)數(shù)ADT實(shí)現(xiàn)的面向過(guò)程源程序-1#include<iostream.h>#include<conio.h>structcomp//存儲(chǔ)表示，結(jié)構(gòu)體類型的定義{floatx;//實(shí)部子域

floaty;//虛部的實(shí)系數(shù)子域};voidcreat(comp&c);//子函數(shù)的原型聲明voidoutputc(compa);compadd(compk,comph);compsub(compk,comph);compa,b,a1,b1;intz;//全局變量的說(shuō)明19浙江萬(wàn)里學(xué)院計(jì)算機(jī)系復(fù)數(shù)ADT實(shí)現(xiàn)的面向過(guò)程源程序-2intmain()//主函數(shù){creat(a);outputc(a);

creat(b);outputc(b);a1=add(a,b);outputc(a1);_getch();return0;}voidcreat(comp&c){floatx1,y1;

cout<<“輸入實(shí)部realx=?”);cin>>x1;

cout<<“輸入實(shí)部xvpuy=?”);cin>>y1;c.x=x1;c.y=y1;}20浙江萬(wàn)里學(xué)院計(jì)算機(jī)系復(fù)數(shù)ADT實(shí)現(xiàn)的面向過(guò)程源程序-3voidoutputc(compa)//

輸出一個(gè)復(fù)數(shù){cout<<“復(fù)數(shù)：”<<a.x<<“+i*”<<a.y<<endl;}compadd(compk,comph)//求兩個(gè)復(fù)數(shù)相加之和{compl;l.x=k.x+h.x;l.y=k.y+h.y;returnl;}compsub(compk,comph)//求兩個(gè)復(fù)數(shù)相減之差{compl;l.x=k.x-h.x;l.y=k.y-h.y;returnl;}21浙江萬(wàn)里學(xué)院計(jì)算機(jī)系2.復(fù)數(shù)ADT實(shí)現(xiàn)的面向?qū)ο笤闯绦?1#include<iostream.h>#include<conio.h>classComplex

//定義復(fù)數(shù)類Complex{private:floatx;//實(shí)部

floaty;//虛部

public:

Complex(){}

Complex(floatx0,floaty0){x=x0;y=y0;}~Complex(){}

22浙江萬(wàn)里學(xué)院計(jì)算機(jī)系復(fù)數(shù)ADT實(shí)現(xiàn)的面向?qū)ο笤闯绦?2voidoutputc(){cout<<“復(fù)數(shù)：”<<x<<“+i*”<<y<<endl;}Complexoperator+(Complexk){returnComplex(x+k.x,y+k.y);}Complexoperator-(Complexk){returnComplex(x-k.x,y-k.y);}Complexoperator*(Complexk);};

//類定義結(jié)束

23浙江萬(wàn)里學(xué)院計(jì)算機(jī)系復(fù)數(shù)ADT實(shí)現(xiàn)的面向?qū)ο笤闯绦?3ComplexComplex::operator*(Complexk){Complexg;g.x=k.x*x-k.y*y;g.y=k.y*x+y*k.x;returng;}intmain(){Complexa1(1,2),a2(4,6),a3,a4,a5;a3=a1+a2;a3.outputc();a4=a1-a2;a4.outputc();a5=a1*a2;a5.outputc();_getch();return0;}24浙江萬(wàn)里學(xué)院計(jì)算機(jī)系1.3C++語(yǔ)言簡(jiǎn)介1.3.1基本輸入/輸出1.3.2函數(shù)與參數(shù)傳遞