数据结构(上)清华大学出版社ppt

《数据结构(上)清华大学出版社ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(上)1第1章绪论第2章线性表第3章栈和队列第4章串第5章数组与广义表2第一章绪论3学习重点：☆数据结构的基本概念；☆数据的逻辑结构、存储结构以及两者之间的关系；☆算法及特性；☆大O记号的表示。41.1数据结构的概念1.2抽象数据类型（ADT）1.3算法描述与分析5程序设计的实质即为计算机处理问题编制一组“指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略；数据结构即为问题的数学模型。6数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述.非数值计算问题的数学模型正是本门课程要讨论的数据结构。

2、7例如：迷宫、棋盘在计算机内部的表示交叉路口的红绿灯管理七桥问题8概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。9一、基本概念和术语二、数据结构三、数据类型和抽象数据类型10所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。数据是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。11是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素例如，学生信息系统中学生信息表中的一个记录12它是数据

3、结构中讨论的最小单位。又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项”。称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项13数据对象具有相同特性的数据元素的集合。如:整数、实数等。14数据结构指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。15如，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在着两个关系:“行”的次序关系:row={,,,

4、}col={,,}“列”的次序关系:a1a2a3a4a5a616在含6个数据元素{a1,a2,a3,a4,a5,a6}的集合上存在如下的次序关系:{

5、i=1,2,3,4,5}可见，不同的“关系”构成不同的“结构”则构成“一维数组”。17数据结构的形式定义描述为:数据结构是一个二元组Data_Structures=(D,R)其中:D是数据元素的有限集，R是D上关系的有限集。18从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构19数据结构包括“逻辑结构”和

6、“物理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。20数据的存储结构关系有两种表示方法：顺序存储以"B相对于A的存储位置"表示"B是A的后继"例如:令B的存储位置和A的存储位置之间相差一个预设常量C，而C是一个隐含值，AB21链式存储以附加信息(指针)表示后继关系以和A绑定在一起的附加信息(指针)表示后继关系，这个指针即为B的存储地址，由此得到的数据存储结构为"链式存储结构"。BA以“由数据元素A的存储映象和

7、附加的指针合成的结点”表示数据元素。22存储结构的描述方法随编程环境的不同而不同，对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。23数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型（AbstractDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作24抽象数据类型形式定义为：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}25一、什么是算法二、算法技术分析初步三、

8、算法效率的衡量方法和准则四、算法的存储空间需求26是一个有穷的规则集合，这些规则为解决某一特定任务规定了一个运算序列。算法描述算法的方法有：自然语言程序设计语言（或类程序设计语言）流程图（包括传统流程图和N-S结构图）伪语言PAD图27一个算法必须满足以下五个重要特性：3．可行性1．有穷性2．确定性5．有输出4．有输入28有穷性一个算法必须在有穷步之后正常结束，即必须在有限时间内完成而不能形成无穷循环。确定性算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。29可行性算法中的每一条指令必须是切实可行的，即原则上可

9、以通过已经实现的基本运算执行有限次来实现。有输入一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。