数据结构 第一章 绪论

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

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

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

4、称为结构。 根据数据元素之间的不同特性，通常有下列四类基本结构：集合：集合结构中的所有元素都“属于同一集合”，即只要满足同属于一个集合就是集合结构，这是一种极为松散的结构。线性结构：该结构的数据元素之间存在着一对一关系。树形结构：该结构的数据元素之间存在着一对多关系。图形结构：该结构的数据元素之间存在着多对多的关系，图形结构也称为网状结构。基本结构图例：线形结构：元素关系为“一对一”树形结构：元素关系为“一对多”图状结构：元素关系为“多对多”集合结构：元素关系为“同属于”思考：对四种基本结构分别举出例子大街上熙熙攘攘的人群是“集合”火车站上排队买票的长龙是“线性结构”四世同堂的大家族是“树形结

5、构”济南一日游线路是“图结构”示例：linear=(D, R)D=1,2,3,4,5,6,7,8,9 R=, , ,逻辑图为：示例：tree=(D, R)D=a,b,c,d,e,f,g,h,i,j,k,lR=(a,b),(a,c),(a,d),(b,e),(b,f),(b,g),(c,h),(c,i),(c,j),(d,k),(d,l)逻辑图为:习题：设数据元素的集合为D=d1, d2, d3, d4, d5，画出各关系R对应的数据结构B=(D, R)的图形，并判断其所属逻辑结构的类型？ R=(d1, d2), (d2, d4), (d1, d3), (d2, d5) R=(d5, d4),

6、(d4, d3), (d3, d1), (d1, d2) R=(di, dj)| i j数据结构分类：数据结构包括数据的逻辑结构和数据的物理结构。从实际问题中抽象出来的数学模型，结构中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。集合、线性结构、树、图 数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。数据元素之间的关系在计算机中的表示方法（数据的物理结构）有两种：顺序存储结构和链式存储结构。数据结构的逻辑结构分类数据结构的物理结构分类数据类型：数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称。数据类型分为两类1、原子类型 基本数据类型有：

7、整型（int）：存储整型量，如123，-7浮点型（float）：表示实型数据（带有小数点），如3.14159等字符型（char）：表示单个字符，如a 2、结构类型，如数组、结构体。数 组：用于保存一批相同类型的数据；结构体（structure）是一种数据类型，它把互相联系的数据组合成一个整体。例：1.3抽象数据类型的表示与实现抽象数据类型：抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。本书中所定义的抽象数据类型，既可以是整型

8、、实型、字符型或某种结构体类型，具体使用时只需将它重新定义一下即可。 抽象数据类型可以用三元组表示：ADT = (D, S, P) 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。1.4 算法和算法分析算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列，其中每个指令表示一个或多个操作。算法的特性有穷性：一条指令都只能执行有限次，算法必须在执行有限步后结束确定性：算法中每条指令的含义必须明确，不允许有二义性可行性：算法应该在有限时间内执行完毕输入：算法开始前必须给算法中用到的变量赋初值，即算法的输入可包含零个数据或多个数据(也称为输入数据)，这些输入数据取自确定的对象集合输出：算法有一个或多个输出算法设计的要求正确性可读性健壮性效率与低存储量需求算法效率的度量：时间复杂度和空间复杂度设：执行每条语句所需时间为单位时间，则：算法耗费时间=基本语句的重复执行的次数之和。例1：NXN矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; +x;s=0For (i=1;i=n;+i)+x;s+=xFor(j=1;j=n;+j) for(k=1;k=n;+k)+x;s+=x;O(1)、O(n)、O(n2)练习：For(i