数据结构 第一章 绪论

《数据结构 第一章 绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章绪论课程介绍：1、计算机应用技术专业的核心课程；数据结构是计算机科学与技术专业的一门专业技术基础课。该课程是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。2、应用软件开发必备理论知识；1）人机对弈树形结构2）如何实现打印时次序不乱队列3）汉字输入时如何使常用字排在前面查找方法4）图书馆书目检索线性表5）城市的交通布线及信号灯的显示图……本课程是一门综合理论课程，理论性比较强，比较抽象，同时也比较枯燥。教学上主要采用课堂讲授的方式来学习，为了激发同学的学习兴趣，同时也采用游戏式

2、、启发式、讨论式、自主式多种教学方法相辅。希望同学们能积极主动的参与进来，使我们的课堂变得生动活泼。学习目标：q了解数据结构的有关概念q掌握逻辑数据结构q线性表q树q图q熟悉常用查找方法原理及使用方法q熟悉常用排序方法原理及使用方法q掌握常用算法q1.1什么是数据结构q1.2基本概念和术语q1.3抽象数据类型的表示和实现q1.4算法和算法分析1.1什么是数据结构一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：具体问题→数学模型→算法→程序例子：q图书馆的书目检索系统q人机对弈问题q交通灯的管理例1书目自动检索系统例2人机对奕问题例

3、3多叉路口交通灯管理问题例4城市间的通信布线问题数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。1.2基本概念和术语²数据是对客观事物的符号表示，在计算机科学中是指所有能输入计算机并能被计算机处理的符号的总称。²数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。例如一个棋盘格局、一个城市结点、线性表中一条记录等。一个数据元素是由若干个数据项组成的。²数据项是数据元素的详细描述，是数据处理中不可分割的最小单位。²数据对象是具有相同性质的数据元素的集合。²数据结构是相互之间存

4、在一种或多种特定关系的数据元素的集合。²在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间的不同特性，通常有下列四类基本结构：1.集合：集合结构中的所有元素都“属于同一集合”，即只要满足同属于一个集合就是集合结构，这是一种极为松散的结构。2.线性结构：该结构的数据元素之间存在着一对一关系。3.树形结构：该结构的数据元素之间存在着一对多关系。4.图形结构：该结构的数据元素之间存在着多对多的关系，图形结构也称为网状结构。基本结构图例：1.线形结构：元素关系为“一对一”1.树形结构

5、：元素关系为“一对多”2.图状结构：元素关系为“多对多”3.集合结构：元素关系为“同属于”思考：对四种基本结构分别举出例子大街上熙熙攘攘的人群是“集合”火车站上排队买票的长龙是“线性结构”四世同堂的大家族是“树形结构”济南一日游线路是“图结构”示例：qlinear=(D,R)qD={1,2,3,4,5,6,7,8,9}qR={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>,<8,9>}q逻辑图为：示例：qtree=(D,R)qD={a,b,c,d,e,f,g,h,i,j,k,l}qR={(a,b),(a,c),

6、(a,d),(b,e),(b,f),(b,g),(c,h),(c,i),(c,j),(d,k),(d,l)}q逻辑图为:习题：设数据元素的集合为D={d1,d2,d3,d4,d5}，画出各关系R对应的数据结构B=(D,R)的图形，并判断其所属逻辑结构的类型？⑴R={(d1,d2),(d2,d4),(d1,d3),(d2,d5)}⑵R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}⑶R={(di,dj)

7、i

8、数据元素之间的逻辑关系，因此又称为数据的逻辑结构。²集合、线性结构、树、图²数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。²数据元素之间的关系在计算机中的表示方法（数据的物理结构）有两种：顺序存储结构和链式存储结构。数据结构的逻辑结构分类数据结构的物理结构分类数据类型：数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称。数据类型分为两类1、原子类型基本数据类型有：²整型（int）：存储整型量，如123，-7²浮点型（float）：表示实型数据（带有小数点），如3.14159等²字符型（char）：表示单个字符，如

9、‘a’2、结构类型，如数组、结构体。²数组：用于保存一批相同类型的数据；²结构体（structure）是一种数据类型，它把互相联系的数据