《数据结构A》第01节zlh

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

标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载

正确性：算法的执行结果应当满足预先

规定

关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定

的功能和性能要求。简明性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。效率：有效使用存储空间并有高的时间效率。1.5算法分析的基本方法算法的时间复杂度是程序运行从开始到结束所需的时间，以程序步的数量级来统计。程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。1.5算法分析的基本方法floatSum(floatlist[],constintn){//此程序的程序步数为2n＋3floattempsum=0.0;count++;//针对赋值语句for(inti=0;i