面向对象数据结构.ppt

面向对象的数据结构
山西省高校计算机精品课程及优质教学资源
建设与共享研讨会
山西 太原 2008年4月20日
问我祖先在何处，山西洪洞大槐树
版权所有，转载或翻印必究 Page *
——山西太原（交城）古郊麻会村
版权所有，转载或翻印必究 Page *
内容提要
1. 教学内容
2. 数据的定义
3. 抽象数据类型
4. 教学案例
5. 网络教学资源
数据结构在计算机学科中的地位
最重要的主干基础课程
就是“最”，没有“之一”
承前启后的重要作用
程序设计能力“质的飞跃”
操作系统、编译器、数据库系统、
网络、软件工程
版权所有，转载或翻印必究 Page *
版权所有，转载或翻印必究 Page *
版权所有，转载或翻印必究 Page *
数据结构与算法实习
概率统计
数据结构与算法
数学分析／高等数学
集合论与图论
算法分析与设计
程序设计实习
高等代数／线性代数
计算概论
程序设计语言原理
数据库概论
编译原理
操作系统
软件工程
计算机网络
版权所有，转载或翻印必究 Page *
1. 数据结构课程的主要内容
理论
算法的数学基础
算法的时间和空间度量
抽象
排序、检索等重要问题类的有效算法
重要数据结构技术
设计
算法的选择、实现和测试
版权所有，转载或翻印必究 Page *
2. 数据结构的定义
数据的逻辑结构
图树二叉树线性表
数据的存储结构
顺序方法、链接方法
索引方法、散列方法
数据的运算
增、删、查、改、排序、检索
存储
数据结构
逻辑
运算
版权所有，转载或翻印必究 Page *
3. 抽象数据类型ADT
抽象数据类型是定义了一组运算的数学模型
把数据结构的存储与实现细节剥离
在适当的抽象层次上考虑程序的结构和算法
封装和信息隐蔽
版权所有，转载或翻印必究 Page *
栈的抽象数据类型
template <class ELEM> class Stack
{ // 栈的元素类型为ELEM
Stack(int s); //创建栈的实例
~Stack(); //该实例消亡
void Push(ELEM item); // item压入栈顶
ELEM Pop(); // 返回栈顶内容，并从栈顶弹出
ELEM GetTop(); // 返回栈顶内容，但不弹出
void MakeEmpty(); // 变为空栈
Boolean IsEmpty(); // 返回真，若栈已空
Boolean IsFull(); // 返回真，若栈已满
};