数据结构清华大学学习教案

1、数据结构数据结构(sh j ji u)清华大学清华大学第一页，共72页。第一章第一章 数据结构数据结构(sh j (sh j ji u)ji u)概念概念第1页/共72页第二页，共72页。 学学 号号 姓姓 名名 性别性别 籍籍 贯贯 出生年月出生年月 1 98131 刘激扬刘激扬 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 岛岛 1979.07 3 98165 卢声凯卢声凯 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕

2、 女女 苏苏 州州 1980.03 7 98297 宫宫 力力 男男 北北 京京 1981.01 8 98310 蔡晓莉蔡晓莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健 男男 杭杭 州州 1979.12第2页/共72页第三页，共72页。 课程编号课程编号 课课 程程 名名 学时学时 024002 程序设计基础程序设计基础 64 024010 汇编语言汇编语言 48 024016 计算机原理计算机原理 64 024020 数据结构数据结构 64 024021 微机技术微机技术 64 024024 操作系统操作系统 48 024026 数据库原理数据库原理 48第3页/共72页

3、第四页，共72页。学生学生( (学号学号, ,姓名姓名, ,性别性别(xngbi),(xngbi),籍贯籍贯) )课程课程(kchng)(kchng)( (课程课程(kchng)(kchng)号号, ,课程课程(kchng)(kchng)名名, ,学分学分) )选课选课( (学号学号, ,课程课程(kchng)(kchng)号号, ,成绩成绩) )第4页/共72页第五页，共72页。/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第5页/共72页第六页，共72页。第6页/共72页第七页，共72页。姓名姓名 所在院系所

4、在院系 性别性别 出生日期出生日期 年年 月月职务职务 业绩业绩数据数据(shj)(shj)元素元素 (data element) (data element)n数据的基本单位。在计算机程序中常作为一数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。个整体进行考虑和处理。n有时一个数据元素可以由若干数据项有时一个数据元素可以由若干数据项 (Data (Data Item)Item)组成。数据项是具有独立含义的最小组成。数据项是具有独立含义的最小标识单位。标识单位。n数据元素又称为元素、结点数据元素又称为元素、结点(ji din)(ji din)、记录。记录。第7页/共72页第八页，共

5、72页。定义定义: 由某一数据元素的集合以及该集合中所有由某一数据元素的集合以及该集合中所有数据元素之间的关系组成数据元素之间的关系组成(z chn)。记为：。记为： Data_Structure = D, R 其中，其中，D 是某一数据元素的集合，是某一数据元素的集合，R 是该集是该集合中所有数据元素之间的关系的有限集合。合中所有数据元素之间的关系的有限集合。第8页/共72页第九页，共72页。 156152436243第9页/共72页第十页，共72页。数据结构是数据的组织数据结构是数据的组织(zzh)形式形式n包括三个方面：包括三个方面：n数据元素间的逻辑关系，即数据的逻辑结构；数据元素间的

6、逻辑关系，即数据的逻辑结构；n数据元素及其关系在计算机存储内的表示，数据元素及其关系在计算机存储内的表示，即数据的存储表示；即数据的存储表示；n数据的运算数据的运算(yn sun)，即对数据元素施加，即对数据元素施加的操作。的操作。第10页/共72页第十一页，共72页。数据的逻辑数据的逻辑(lu j)结构结构n数据的逻辑结构从逻辑关系上描述数据，与数数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关据的存储无关(wgun)；n数据的逻辑结构可以看作是从具体问题抽象出数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；来的数据模型；n数据的逻辑结构与数据元素本身的形式、内容数据的逻辑结构与数

7、据元素本身的形式、内容无关无关(wgun)；n数据的逻辑结构与数据元素的相对存储位置无数据的逻辑结构与数据元素的相对存储位置无关关(wgun)。第11页/共72页第十二页，共72页。数据数据(shj)的逻辑结的逻辑结构分类构分类n线性结构线性结构(jigu)n 线性表线性表n非线性结构非线性结构(jigu)n 树树n 图（或网络）图（或网络）第12页/共72页第十三页，共72页。线性结构线性结构(jigu)树形结构树形结构(jigu)树树 二叉树二叉树 二叉搜索二叉搜索(su (su su)su)树树bindevetclibuser1413121123456789103158710119987

8、4566231311第13页/共72页第十四页，共72页。堆结构堆结构(jigu)123548711102916410121151236987第14页/共72页第十五页，共72页。图结构图结构(jigu) (jigu) 网络结构网络结构(jigu)(jigu)12543611331814665161921125634第15页/共72页第十六页，共72页。数据数据(shj)的存储结构的存储结构n数据的存储结构是逻辑结构用计算机语言的数据的存储结构是逻辑结构用计算机语言的实现；实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。n 顺序存储表示顺序存储表示(biosh)n 链接

9、存储表示链接存储表示(biosh)n 索引存储表示索引存储表示(biosh)n 散列存储表示散列存储表示(biosh)主要用于内存主要用于内存(ni cn)的存储表示的存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示第16页/共72页第十七页，共72页。第17页/共72页第十八页，共72页。n构造数据类型由基本数据类型或构造数构造数据类型由基本数据类型或构造数据类型组成。据类型组成。n构造数据类型由不同成分类型构成。构造数据类型由不同成分类型构成。n基本数据类型可以看作是计算机中已实基本数据类型可以看作是计算机中已实现的数据结构。现的数据结构。n数据类型就是数据结构，不过它

10、是从编数据类型就是数据结构，不过它是从编程者的角度来使用程者的角度来使用(shyng)的。的。n数据类型是模板，必须定义属于某种数数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。据类型的变量，才能参加运算。 第18页/共72页第十九页，共72页。第19页/共72页第二十页，共72页。抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表第20页/共72页第二十一页，共72页。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义(dngy) 数据关系：数据关系的定义数据关系：数据关系的定义(dngy) 基本操作：基本操作的

11、定义基本操作：基本操作的定义(dngy) ADT 抽象数据类型名抽象数据类型名基本操作名（参数表）基本操作名（参数表）前置条件：前置条件：先决条件描述先决条件描述后置条件：后置条件：操作结果描述操作结果描述第21页/共72页第二十二页，共72页。第22页/共72页第二十三页，共72页。第23页/共72页第二十四页，共72页。第24页/共72页第二十五页，共72页。第25页/共72页第二十六页，共72页。面向对象的概念面向对象的概念(ginin)n面向对象面向对象 = = 对象类继承通信对象类继承通信n对象对象n在应用问题中出现的各种在应用问题中出现的各种( zhn)( zhn)实实体、事件、规

12、格说明等。体、事件、规格说明等。n由一组属性值和在这组值上的一组服务由一组属性值和在这组值上的一组服务（或称操作）构成。（或称操作）构成。n与与C C中构造数据类型不同在于：中构造数据类型不同在于：C C中的构造中的构造数据类型的变量仅涉及属性值，与操作分数据类型的变量仅涉及属性值，与操作分离，而离，而C+C+中的对象则不然。中的对象则不然。第26页/共72页第二十七页，共72页。n类类 (class)，实例，实例 (instance)n具有相同属性和服务的对象归于同一类，形成具有相同属性和服务的对象归于同一类，形成类。类。n类中的对象为该类的实例。类中的对象为该类的实例。n同一类的实例同一类

13、的实例n共享类的属性和类的操作；共享类的属性和类的操作；n通过继承共享其父类的公共通过继承共享其父类的公共(gnggng)的和保的和保护性的属性和操作；护性的属性和操作；n同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。第27页/共72页第二十八页，共72页。四边形类及其对象四边形类及其对象(duxing)属性aPoint1 aPoint2aPoint3 aPoint4服务服务Draw( )move(x, y)contains(aPoint)属性值属性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(

14、45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服务服务服务服务quadrilateral第28页/共72页第二十九页，共72页。派生类派生类继承的特性继承的特性+特有的特性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形第29页/共72页第三十页，共72页。第30页/共72页第三十一页，共72页。Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPoly

15、gon 类类referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral第31页/共72页第三十二页，共72页。第32页/共72页第三十三页，共72页。算法算法(sun f)(sun f)设计设计 自顶向下，逐步求精自顶向下，逐步求精 第33页/共72页第三十四页，共72页。 void selectSort ( int a , const int n ) /对对n个整数个整数a0,a1,an-1按递增顺序按递增顺序(shnx)排序排序 for (int i = 0

16、; i n-1; i+) int k = i; /从从ai查到查到an-1, 找最小整数找最小整数, 在在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; 第34页/共72页第三十五页，共72页。定义定义 适合多种数据类型的类定义或算法，在特定适合多种数据类型的类定义或算法，在特定环境下通过环境下通过(tnggu)(tnggu)简单地代换，变成针简单地代换，变成针对具体某种数据类型的类定义或算法。对具体某种数据类型的类定义或算法。第35页/共72页第三十六页，共72页。用模板用模

17、板(mbn)定义用于排序的数据表类定义用于排序的数据表类#ifndef DATALIST_H#define DATALIST_H#include /K是表项关键码是表项关键码类型类型template / /E是是表项类型表项类型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);第36页/共72页第三十七页，共72页。 public: dataList (int size = 10) : listSize (size), elem

18、ent (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 第37页/共72页第三十八页，共72页。类中所有操作作为模板函数的实现类中所有操作作为模板函数的实现template void dataList : sw

19、ap (int m1, int m2) /交换由交换由m1, m2为下标的为下标的(bio de)数组元数组元素的值素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;第38页/共72页第三十九页，共72页。template int dataList:minKey (int low, int high) /查找数组查找数组Elementlow到到Elementhigh中具中具/有最小关键码值的表项，函数返回有最小关键码值的表项，函数返回(fnhu)其位置其位置 int min = low; for (int

20、 i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定义定义(dngy)的重载的重载操作操作第39页/共72页第四十页，共72页。template ostream& operator (ostream& outStream, dataList outList) outStream “输出数组内容输出数组内容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl;

21、ouStream “输出数组当前输出数组当前(dngqin)大小大小 : ” outList.listSize endl; return outStream; 第40页/共72页第四十一页，共72页。 template istream& operator (istream& inStream, dataList inList) /输入输入(shr)对象为对象为inList，输入，输入(shr)流对象流对象为为inStream cout inList.listSize; cout “输入输入(shr)数组元素值数组元素值 : n”; for (int i = 0; i inLis

22、t.listSize; i+) cout “元素元素” i inList.elementi; return inStream; 第41页/共72页第四十二页，共72页。template void dataList : sort ( ) /按非递减按非递减(djin)顺序对顺序对listSize个关键码个关键码element0到到/elementArraySize-1排序排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif 第42页/共72页第四

23、十三页，共72页。使用模板的选择排序使用模板的选择排序(pi x)算法的主函算法的主函数数 #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; 第43页/共72页第四十四页，共72页。 dataList TestList (SZ); cin TestList; cout TestList endl; Te

24、stList.Sort ( ); cout TestList endl; return 0; 定义定义(dngy)对象对象时，代入实际数时，代入实际数据类型据类型重载重载(zhn zi)友元操作友元操作标准标准(biozhn)IO操作操作消息通信消息通信第44页/共72页第四十五页，共72页。第45页/共72页第四十六页，共72页。第46页/共72页第四十七页，共72页。第47页/共72页第四十八页，共72页。例如，给出顺序搜索例如，给出顺序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an-1中搜索

25、与给定值中搜索与给定值 x 相等的元相等的元/素，函数返回素，函数返回(fnhu)其位置，失败返回其位置，失败返回(fnhu)-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;第48页/共72页第四十九页，共72页。 插装 time( ) 的计时程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout

26、 n runTime endl;事实上，算法运行时间要受输入规模、利用编译程序(bin y chn x)生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。第49页/共72页第五十页，共72页。第50页/共72页第五十一页，共72页。第51页/共72页第五十二页，共72页。第52页/共72页第五十三页，共72页。n程序步确定方法程序步确定方法(fngf)n插入计数全局变量插入计数全局变量countn建表，列出个语句的程序步建表，列出个语句的程序步例例 以迭代以迭代(di di)(di di)方式求累加和的方式求累加和的函数函数 float sum (float a , int n) f

27、loat sum (float a , int n) float s = 0.0; float s = 0.0; for (int i = 0; i n; for (int i = 0; i n; i+)i+) s = s + ai; s = s + ai; return s; return s; 第53页/共72页第五十四页，共72页。在求累加和程序中加入在求累加和程序中加入 count 语句语句 float sum (float a , int n) float s = 0.0; count+; /count 统计统计(tngj)执行语句条数执行语句条数 for (int i = 0; i

28、 n; i+) count += 2; /针对针对 for 语句语句s += ai;count+; /针对赋值语句针对赋值语句 count += 2; /针对针对 for 的的最后一次最后一次 count+; /针对针对 return 语句语句 return s; 执行结束得执行结束得 程序步数程序步数 count = 3*n+4第54页/共72页第五十五页，共72页。第55页/共72页第五十六页，共72页。注意注意(zh y)： 一个语句本身的程序步数可能不等于该语句一次一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。执行所具有的程序步数。 例如：例如：赋值语句赋值语句x =

29、 sum (R, n) 本身程序步数为本身程序步数为 1；一次执行对函数一次执行对函数 sum (R, n) 的调用需要的程序步数为的调用需要的程序步数为 3*n+4；一次执行的程序步数为一次执行的程序步数为 1+3*n+4 = 3*n+5第56页/共72页第五十七页，共72页。第57页/共72页第五十八页，共72页。例例 求两个求两个(lin )n阶方阵的乘积阶方阵的乘积C = ABvoid MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2

30、n+2) Cij = 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2第58页/共72页第五十九页，共72页。第59页/共72页第六十页，共72页。第60页/共72页第六十一页，共72页。T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;第61页/共72页第六十二页，共72页。第62页/共72页第六十三页，共72页。 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行中各行 sumi = 0.0; /数据累加数据累加 for (int j = 0; j n; j+