资源描述：
《数据结构讨论的范畴》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章绪论1.1数据结构讨论的范畴1.2与数据结构相关的概念1.3算法和算法的量度软件开发的过程:系统分析系统实现系统维护系统设计系统设计确定系统所要达到的目标确定实现方案并生成系统实地安装调试系统修整完善NiklausWirthAlgorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型例如:鸡兔同笼问题二元一次代数方程组结构静力分析问题全球天气预报高次线性代数方程组球面坐标系下的环流模式方程非数值计算的程序设计问题例一求一组(n个)整数中的最大值例二交叉路口的交通管制问
2、题例三煤气管道的铺设问题例四数据库中表格管理问题概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。一、基本概念和术语二、数据结构三、数据类型和抽象数据类型所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。数据是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素例如，整数“5”,字符“N”等。----是不可分割的“原子”它是数据结构中讨论的最小单位。又如
3、,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项”。称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项关键字能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。数据对象具有相同特性的数据元素的集合。如:整数、实数等。数据结构带结构的数据元素的集合有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系例如，可用三个4位的十进制数表示一个含12位数的“长整数”。3214,6587,9345─a1(3214),a2(6587),
4、a3(9345)对长整数进行运算的程序中的操作对象是一个含三个数据元素{a1,a2,a3}的集合，且三者之间存在下列“次序”关系:{a1,a2、a2,a3}。又如，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在着两个关系:“行”的次序关系:row={,,,}col={,,}“列”的次序关系:a1a2a3a4a5a6在含6个数据元素{a1,a2,a3,a4,a5,a6}的集合上存在如下的次序关系:{
5、i=1,2,
6、3,4,5}“数据结构”是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”则构成“一维数组”。可用如下的数据结构描述“班集体”:{班主任，班长1，班长2，舍长1，……，舍长p,学生1，学生2，……，学生n}{<班主任，班长1>，<班主任，班长2>，<班长1，舍长1>，……，<班长2，舍长p>,<舍长1，学生1>，<舍长1，学生2>，……，<舍长p，学生n>}班主任班长1班长2舍长1舍长k舍长k+1舍长p学生1学生2学生3学生4学生n-3学生n-2学生n-1学生n…………数据结构的形式定义描述为:数据结构是一个二元组Data_St
7、ructures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。存储结构是逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(0010000
8、01)2“关系”的两种映象方法：（表示x,y的方法）顺序映象以x和y之间相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间相差一个预设常量C，而C是一个隐含值，存储结构中只包含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x绑定在一起的附加信息(指针)指示y的存储位置yx以“由数据元素x的存储映象和附加的指针合成的结点”表示数据元素。存储结构的描述方法随编程环境的不同而不同，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。typedefintLong_int[3]例如，当以“顺序映象”表示长
9、整数时，可定义为:定义“
