《《数据结构A》第01章zlh》由会员分享，可在线阅读，更多相关《《数据结构A》第01章zlh（42页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院 2007年1月,数据结构,Data Structures in C+,主讲：朱立华,南京邮电大学计算机学院 2007年1月,数据结构A课程性质、任务和目的,性质：是计算机学科的一门专业基础课。 目的：在于学习如何组织和表示数据，并在相应的数据结构上实现对数据的操作。 基本任务: 是学习常见的基本数据结构，包括线性表、栈和队列、数组和字符串、树、搜索树、散列表、图和文件等，理解它们的逻辑结构、存储结构，领会在这些数据结构上定义的运算和实现运算的算法。学习和领会内、外排序算法。,南京邮电大学计算机学院 2007年1月,教材及参考书,教材：陈慧南，数据结构使用C+描述，人民邮
2、电出版社，2006.10 参考书： 1 Sahni Sahni 等著，汪诗林 等译，数据结构、算法与应用-C+语言描述北京：机械工业出版社，1999 2 Preiss B R著，胡广斌 等译，数据结构与算法，北京：电子工业出版社，2000 3 殷人昆，陶永雷 等著，数据结构（用面向对象方法与C+描述），北京：清华大学出版社，1999 4 陈慧南数据结构与算法北京：高等教育出版社，2005 5 严蔚敏，吴伟民，数据结构（C语言版），北京：清华大学出版社，1997,南京邮电大学计算机学院 2007年1月,上机安排及答疑,(每周二中午12:0013:30, 2-326,信息安全机房),南京邮电大学计
3、算机学院 2007年1月,对学生的要求,时间紧任务重，课前要预习、课后要复习 不迟到早退，课上认真听讲，并做适量的笔记 理论课和实验课均不可缺席 作业按时完成，编程题建议上机调试通过 完成并提交四次实验报告,南京邮电大学计算机学院 2007年1月,考试方式及成绩评定,平时成绩共占总评的 30%，平时成绩仍由3部分组成，其中出勤占10%，平时作业占50%，实验占40% 期末考试形式：笔试闭卷,期末考试成绩占总评的70% 课程总成绩 平时成绩*0.3+期末成绩*0.7,南京邮电大学计算机学院 2007年1月,关于任课教师,姓名：朱立华 教龄：22年 毕业于：北京邮电大学应用数学专业 爱好：运动、读
4、书、交友 热爱：教学、学生、生活 家庭：牙医丈夫、初二女儿 E-mail: Tel: 18951896417,南京邮电大学计算机学院 2007年1月,1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法,第1章 基础知识,南京邮电大学计算机学院 2007年1月,数据：计算机处理加工 的对象。 数据分为两类：,1.1 算法与数据结构,数值数据,非数值数据,数据结构的学科定义：是为研究和解决如何使用计算机组织和处理非数值问题而产生的理论、技术和方法。是计算机学科的基础之一，更是软件技术的基础。,南京邮电大学计算机学
5、院 2007年1月,数据的组织和表示方法直接影响使用计算机求解问题的效率。 算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。,面向过程的程序设计范型:程序=数据结构+算法,因此数据结构与算法是密不可分的。,1.1 算法与数据结构,南京邮电大学计算机学院 2007年1月,基本概念： 数据（data）：计算机加工处理的对象。 数据元素：组成数据成分数据，是数据的基本单位。 数据项：组成数据元素的最小不可再分单元。,1.2 什么是数据结构,数据结构：由数据元素依某种逻辑联系组织起来的，在其上定义一定的运算；根据数据在计算机内
6、存储的存储结构实现该结构上的运算。,南京邮电大学计算机学院 2007年1月,数据结构包括三个方面： 逻辑结构：数据元素间的逻辑关系； 存储结构：数据在计算机内的表示形式，是逻辑结构在机内的映象； 运算：在该数据结构上操作（运算）的定义及实现。,1.2 什么是数据结构,依赖于逻辑结构,依赖于存储结构,南京邮电大学计算机学院 2007年1月,数据的逻辑结构 对数据元素间逻辑关系的描述被称为数据的逻辑结构(logical structure) ，是面向应用的。,1.2 什么是数据结构,逻辑结构可以用一个二元组表示： DS=（D，R）， 其中，D是数据元素的有限集合， R是D中元素序偶的集合。,南京邮
7、电大学计算机学院 2007年1月,四种基本逻辑结构 （a）线性结构：一对一，前后关系 （b）集合结构：松散，无固定关系 （c）树形结构：一对多，上下关系 （d）图状结构：多对多，任意关系,1.2 什么是数据结构,非线性结构,线性结构,南京邮电大学计算机学院 2007年1月,数据的存储表示：是数据在计算机内的表示形式，是逻辑结构在计算机内的存储映象，是面向计算机的。,1.2 什么是数据结构,几种常用的存储结构 顺序结构 链接结构 索引结构 散列结构,南京邮电大学计算机学院 2007年1月,顺序存储 需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中，可以随机访问。,1.2
8、 什么是数据结构,例：4个元素组成的线性数据结构,任意元素的存储位置可用公式Loc（ak） Loc（a0） 2* k,每个元素需要的字节数,南京邮电大学计算机学院 2007年1月,链接存储 不需要一块连续的存储空间，用结点存储元素，每个结点包括元素本身的数据信息及其它元素的地址信息，只能顺序访问。,1.2 什么是数据结构,例：4个元素组成的线性数据结构,头指针，很重要,最后结点指针域为空,南京邮电大学计算机学院 2007年1月,数据结构最常见的运算 创建运算:创建一个数据结构； 清除运算:删除数据结构中的全部元素； 插入运算:在数据结构中插入一个新元素； 删除运算:将数据结构中的某个元素删除；
9、 搜索运算:搜索满足一定条件的元素； 更新运算:修改某个指定元素的值； 访问运算:访问数据结构中某个元素； 遍历运算:依一定策略访问每个元素一遍,1.2 什么是数据结构,南京邮电大学计算机学院 2007年1月,静态数据结构和动态数据结构 如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。,例1.1 栈数据结构：是一种线性数据结构 （1） Push运算：向栈中加入一个元素 （2） Pop运算:从栈中删除最后加入的元素 （3） Top运算:访问最后加入栈中的元素 ,1.2 什么是数据结构,南京邮电大学计算机学院 2007年1月,抽象：其实质是抽取共同的和本质的内
10、容，忽略非本质的细节。 数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。 过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。,1.3 数据抽象和抽象数据类型,南京邮电大学计算机学院 2007年1月,封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。 信息隐蔽：对使用者隐藏了数据结构以及程序的实现细节。,1.3 数据抽象和抽象数据类型,封装与信息隐蔽,通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。,南
11、京邮电大学计算机学院 2007年1月,模块应采用封装和信息隐蔽原则来设计,这样的模块被称为黑盒子。 封装和信息隐蔽的作用：错误局部化，降低问题求解的复杂性，提高程序的可靠性。 C+语言的类 可以封装数据和运算，其公有、保护和私有成员机制有利于实现信息隐蔽。,1.3 数据抽象和抽象数据类型,南京邮电大学计算机学院 2007年1月,数据类型 是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。 抽象数据类型（abstract data type ADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，
12、实行封装和信息隐蔽，即所谓使用和实现分离。,1.3 数据抽象和抽象数据类型,南京邮电大学计算机学院 2007年1月,逻辑结构和运算的定义组成了数据结构的规范( specification)。 数据的存储表示和运算算法的描述构成数据结构的实现(implementation)。 从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。 一种数据结构被视为一个抽象数据类型。,1.3 数据抽象和抽象数据类型,南京邮电大学计算机学院 2007年1月,数据结构的抽象层次 抽象层：讨论数据的逻辑结构及其运算定义， 实现层：讨论数据的存储表示以及运算的算法实现。,本教材用C+的抽象类模板描述,本教材用C+
13、的相应的派生类模板描述,1.3 数据抽象和抽象数据类型,南京邮电大学计算机学院 2007年1月,数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。 数据结构可以形式地用一个C+的抽象类模板描述，但是算法必须在一个派生类上实现。,1.4 描述数据结构和算法,南京邮电大学计算机学院 2007年1月,ADT Stack 数据： 0个或多个元素的线性序列（a0,a1,.,an-1）, 其最大允许长度为MaxStackSize。 运算： Create()： 建立一个空栈 Destroy()：撤消一个栈 Push(x)：值为x的新元素进栈，成为栈顶元素 Pop()：从栈中删除栈顶元
14、素 Top(x)：在x中返回栈顶元素 ,栈的ADT描述,1.4 描述数据结构和算法,南京邮电大学计算机学院 2007年1月,template class Stack / 栈类Stack是一个模板抽象类， 其成员函数为纯虚函数，未定义数据成员。 public: virtual bool Push(T x)=0; virtual bool Pop()=0; virtual bool Top(T ,1.4 描述数据结构和算法,栈的C+抽象类模板描述：,南京邮电大学计算机学院 2007年1月,template class SeqStack:public Stack public: bool Push(
15、T x)=0; private: int top; /top记录最后入栈的元素在s的下标 int maxTop; /最大栈顶指针 T *s; /s指向动态生成的一维数组，存放元素 ;,1.4 描述数据结构和算法,栈在一个派生类上实现算法,南京邮电大学计算机学院 2007年1月,template SeqStack:SeqStack(int mSize) maxTop=mSize-1; /设置栈的容量值 s=new TmSize; /生成存储栈的数组 top=-1; /top=1表示空栈 ,1.4 描述数据结构和算法,栈的构造函数实现代码,南京邮电大学计算机学院 2007年1月,什么是算法 笼统的
16、说，算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述，它是指令的有限序列。,1.5 算法分析的基本方法,南京邮电大学计算机学院 2007年1月,输入：算法有零个或多个输入 输出：算法至少产生一个输出 确定性：算法的每一条指令都有确切的定义，没有二义性。 能行性：算法的每一条指令都足够基本，它们可以通过已实现的基本运算执行有限次来实现。 有穷性：算法必须总能在执行有限步后终止。,算法的五大特征：,1.5 算法分析的基本方法,南京邮电大学计算机学院 2007年1月,算法的性能标准 正确性：算法的执行结果应当满足预先规定的功能和性能要求。 简明性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。 健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。 效率：有
