数据结构-用面向对象语言描述-殷人昆-导论概要.ppt

线性结构 直接存取类 数组, 文件 顺序存取类 表, 栈, 队列, 优先队列 广义索引类 线性索引, 有哪些信誉好的足球投注网站树 非线性结构 层次结构类 树，二叉树，堆 群结构类 集合，图 数据结构的抽象层次 数据结构的抽象层次 为什么选用面向对象及C++语言讲述数据结构？ PASCAL与C描述是面向过程的。 C++描述兼有面向过程与面向对象的特点。 Java描述是面向对象的。 用面向对象及C++描述与国际接轨，是市场需要。 算法定义 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有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 int n ) { //对n个整数a[0],a[1],…,a[n-1]按递增顺序排序 for ( int i = 0; i n-1; i++ ) { int k = i; //从a[i]查到a[n-1], 找最小整数, 在a[k] for ( int j = i+1; j n; j++ ) if ( a[j] a[k] ) k = j; int temp = a[i]; a[i] = a[k]; a[k] = temp; } } 模板 (template) 定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法 用模板定义用于排序的数据表类 #ifndef DATALIST_H #define DATALIST_H #include iostream.h template class Type class dataList { private: Type *Element; int ArraySize; void Swap (int m1, int m2); int MaxKey (int low, int high); public: dataList (int size = 10) : ArraySize (size), Element (new Type [Size]) { } ~dataList ( ) {delete [ ] Element;} void Sort ( ); friend ostream operator (ostream outStream, datalistType outList); friend istream operator (istream inStream, datalistType inList); }; #endif 类中所有操作作为模板函数的实现 #ifndef SELECTTM_H #define SELECTTM_H #include “datalist.h” template class Type void dataList Type :: Swap (int m1, int m2) { //交换由m1, m2为下标的数组元素的值 Type temp = Element [m1]; Element [m1] = Element [m2]; Element [m2] = temp; } template class Type int dataListType:: MaxKey (int low, int high) { //查找数组Element[low]到Element[high] //中的最大值，函数返回其位置 int max = low; for (int k = low+1, k = high, k++) if ( Element[max] Element[k