文档介绍:什么是数据结构
“学生”表格
“课程”表格
“选课单”包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系
学生
(学号,姓名,性别,籍贯x, y)
contains(aPoint)
属性值
属性值
quadrilateral1
quadrilateral2
(35, 10) (50, 10)
(35, 25) (50, 25)
(45, 65) (50, 45)
(65, 66) (60, 70)
Draw( )
move(x, y)
contains(aPoint)
Draw( )
move(x, y)
contains(aPoint)
服务
服务
四边形类及其对象
quadrilateral
继承
派生类:四边形,三角形,…
子类 特化类(特殊化类)
基类:多边形
父类 泛化类(一般化类)
通信
消息传递
Draw( )
move(x, y)
contains(aPoint)
Polygon
referencePoint
Vertices
Polygon 类
referencePoint
Vertices
Draw( )
move(x, y)
contains(aPoint)
Polygon的子类
Quadrilateral类
Quadrilateral
线性结构
直接存取类 数组, 文件
顺序存取类 表, 栈, 队列, 优先队列
广义索引类 线性索引, 搜索树
非线性结构
层次结构类 树,二叉树,堆
群结构类 集合,图
数据结构的抽象层次
线性结构
树形结构
树 二叉树 二叉搜索树
14
13
12
11
2
3
4
5
6
7
8
9
10
3
1
5
8
7
10
11
9
9
8
7
4
5
6
6
2
3
13
1
bin
dev
etc
lib
user
1
堆结构
“最大”堆 “最小”堆
12
3
5
4
8
7
11
10
2
9
1
6
4
10
12
11
5
1
2
3
6
9
8
7
群聚类
图结构 网络结构
1
2
5
6
4
3
1
2
5
4
3
6
11
33
18
14
6
6
5
16
19
21
数据的两个视图
数据的逻辑结构 面向应用
数据的物理结构 面向存储
顺序结构
链表结构
散列结构
索引结构
在该数据结构上的操作
为什么选用面向对象及C++语言讲述数据结构?
PASCAL与C描述是面向过程的。
C++描述兼有面向过程与面向对象的特点。
Java描述是面向对象的。
用面向对象及C++描述与国际接轨,是市场需要。
用C++描述面向对象程序
C++的函数特征
C++的数据声明
C++的作用域
C++的类
C++的对象
C++的输入/输出
C++的函数
C++的参数传递
C++的函数名重载和操作符重载
C++的动态存储分配
友元(friend)函数
内联(inline)函数
结构(struct)与类
联合(Union)与类
算法定义
定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列
特性:
输入 有0个或多个输入
输出 有一个或多个输出(处理结果)
确定性 每步定义都是确切、无歧义的
有穷性 算法应在执行有穷步后结束
有效性 每一条运算应足够基本
事例学****选择排序问题
明确问题:递增排序
解决方案:逐个选择最小数据
算法框架: for ( int i = 0; i < n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小整数在a[k], 交换a[i]与a[k];
}
细化程序:程序 SelectSort
算法设计 自顶向下,逐步求精
void selectSort ( int a[ ], const