文档介绍：数据结构与算法——C++描述任课老师:吴献办公室:软件大楼212数据结构课程:理论课(4学时)+实验课(2学时)参考资料:(C++语言版)EllisHorowitx等著,张力等译(教材)(C语言版)严蔚敏等实验课案例:卡耐基梅隆大学(CarnegieMellonUniversity)考核方式:平时与实验(30%)+期中(20%)+期末(50%)什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次用C++描述面向对象程序算法概述与递归算法性能分析与度量第一章基本概念数据:数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象:数据的子集。具有相同性质的数据成员(数据元素)的集合。整数数据对象N={0,1,2,…}学生数据对象程序=数据结构+(NiklausWirth)教授提出程序=算法+数据结构以上公式说明了如下两个问题:(1)数据上的算法决定如何构造和组织数据(算法→数据结构)(2)算法的选择依赖于作为基础的数据结构(数据结构→算法)(1)非计算机专业的学生不学这门课程不是也能编写出不错的程序吗?(2)计算机专业为什么要学习“数据结构”这门课程?1、什么是数据结构计算机的主要应用早期:主要用于数值计算数据之间的关系相对比较简单,可以用一个数学方程表示步骤:数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是:如何得出数学模型(方程)?程序设计人员比较关注程序设计的技巧后来:处理逐渐扩大到非数值计算领域数据之间的关系比较复杂,无法用方程表示要求非数值计算能处理多种复杂的具有一定结构关系的数据1、什么是数据结构1、什么是数据结构定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为:Data_Structure={D,R}其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。 定义:一组性质相同的值的集合,++中的简单数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型 (ADTs:AbstractDataTypes)由用户定义,用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务(或称操作)信息隐蔽和数据封装,使用与实现相分离自然数的抽象数据类型定义ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的操作。Zero():返回自然数0NaturalNumber