数据结构与算法

《数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法——C++描述任课老师：吴献办公室：软件大楼212数据结构课程:理论课(4学时)+实验课(2学时)参考资料：1.数据结构基础（C++语言版）EllisHorowitx等著，张力等译（教材）2.数据结构（C语言版）严蔚敏等实验课案例：卡耐基梅隆大学（CarnegieMellonUniversity）考核方式：平时与实验（30％）＋期中（20％）＋期末（50％）什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次用C++描述面向对象程序算法概述与递归算法性能分析与度量第一章基本概念数据：

2、数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}学生数据对象程序=数据结构+算法N.沃思（NiklausWirth)教授提出程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）（1）非计算机专业的学生不学这门课程不

3、是也能编写出不错的程序吗？（2）计算机专业为什么要学习“数据结构”这门课程？1、什么是数据结构计算机的主要应用早期：主要用于数值计算数据之间的关系相对比较简单，可以用一个数学方程表示步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧后来：处理逐渐扩大到非数值计算领域数据之间的关系比较复杂，无法用方程表示要求非数值计算能处理多种复杂的具有一定结构关系的数据1、什么是数据结构1、什么是数据结构定义:由某一数据对象及该对象中

4、所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。n个网站之间的连通关系树形网状2.抽象数据类型及面向对象概念数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C++中的简单数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型(ADTs:AbstractDataTypes)由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相

5、关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离自然数的抽象数据类型定义ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的操作。Zero():返回自然数0NaturalNumberIsZero(x):if(x==0)返回TrueBooleanelse返回FalseAdd(x,y):if

6、(x+y<=MaxInt)返回x+yNaturalNumberelse返回MaxIntSubtract(x,y):if(x

7、组值上的一组服务（或称操作）构成类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类类中的一个对象为该类的一个实例继承派生类：载重车，轿车，摩托车，…子类特化类(特殊化类)基类：车辆父类泛化类(一般化类)通信消息传递用于描述数据结构的面向对象语言C++JavaDelphi3.数据结构的抽象层次数据结构的三个方面逻辑结构数据元素间抽象化的相互关系（简称为数据结构）与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型存储结构也称物理结构数据元素及其关系在计算机存储

8、器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言与系统环境数据的运算对数据能进行的操作，全部合理的操作构成数据结构的运算集合集合——数据元素间除“同属于一个集合”外，无其它关系逻辑结构通过对现实世界的大量研究和抽象，人们总结出了几种典型的逻辑结构线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图存储结构存储结构两方面的内容：（1）数据元素自身值的表示（数据域）（2）一个结点与其