精品大学课件清华殷人昆数据结构笔记（c版）_2

《精品大学课件清华殷人昆数据结构笔记（c版）_2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次用C++描述面向对象程序算法定义模板性能分析与度量小结第一章绪论“学生”表格“课程”表格选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系学生(学号,姓名,性别,籍贯)课程(课程号,课程名,性别,籍贯)选课(学号,课程号,成绩)UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非

2、数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}学生数据对象什么是数据结构定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。n个网站之间的连通关系树形关系网状关系152643152643抽象数据类型及面向对象概念数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型(A

3、DTs:AbstractDataTypes)由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离抽象数据类型查找登录删除修改符号表自然数的抽象数据类型定义ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的服务。Zero():返回自然数0NaturalNumberIsZero(x):if(x==

4、0)返回TrueBooleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+yNaturalNumberelse返回MaxIntSubtract(x,y):if(x

5、值上的一组服务（或称操作）构成类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类类中的一个对象为该类的一个实例继承派生类：载重车，轿车，摩托车，…子类特化类(特殊化类)基类：车辆父类泛化类(一般化类)通信消息传递用于描述数据结构的语言SmalltalkEffelC++Java线性聚类直接存取类顺序存取类广义索引类非线性聚类层次聚集类树，二叉树，堆群聚集类集合，图数据结构的抽象层次数据结构的抽象层次线性关系树形结构树二叉树二叉搜索树14131211123456789103158710119987456623131bindevetclibuser堆

6、结构“最大”堆“最小”堆123548711102916410121151236987群聚类图结构网络结构12564312543611331814665161921用C++描述面向对象程序C++的函数特征C++的数据声明C++的作用域C++的类C++的对象C++的输入/输出C++的函数C++的参数传递C++的函数名重载和操作符重载C++的动态存储分配友元(friend)函数内联(inline)函数结构(struct)与类联合(Union)与类算法定义定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性

7、每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算应足够基本事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最小数据算法框架：for(inti=0;i