数据结构教程绪论

《数据结构教程绪论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第一章绪言1.1什么是数据结构程序=数据结构+算法例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2人机对奕问题树……..……..…...…...…...…...例2人机对奕问题课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c11c5c3c6c7c8计算机专业必修课程开设先后关系多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图特点l课程之间的先后关系用图结构描述

2、；l通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科1.2基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据

3、元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}D是某一数据对

4、象，R是该对象中成员之间的关系的有限集合。例如：编制学校的科研课题小组的管理程序，首先要为程序的操作对象——课题小组设计一个数据结构。假设每个小组由1位教师、1~3名研究生及1~6名本科生组成，小组成员的关系是：教师指导研究生，每位研究生指导一至两名本科生，则定义如下数据结构Group=(P,R)数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链

5、式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结

6、构图形结构数据结构的三个方面：数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称（值的集合及值集上的一组操作）数据类型：原子类型——（C中的int、float、char，枚举等）结构类型——数组、结构体、共用体、链表等因此：从某种意义上讲：数据结构可以看成是一组具有相同结构的值，而数据类型则是由一种数据结构和定义在其上的一组操作组成。抽象数据类型（abstractdatatype,简称ADT）是指一个数据模型以及定义在该模型上的一组操作，定义取决于逻辑特性，而与内部存储无关抽象数据类型的定义抽象数据类型的定义由一个值域和定义在该值域上的

7、一组操作组成。信息隐蔽和数据封装，使用与实现相分离抽象数据类型可以有以下三元组表示(D，S，P)本书中采用以下格式定义抽象数据类型：ADT抽象数据类型{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中，数据对象和数据关系用位代码描述，基本操的格式定义为基本操作名（参数表）//参数有两种：赋值参数，引用参数初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉用户自定义类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDE

8、NTstu1,stu2,*p;1.3算法的描述和算法分析简介算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序