2018最新数据结构第1章绪论.pptx

教材 数据结构（C语言版）严蔚敏，吴伟民作业及考核作业：时间：周二数量：每次交三分之一考核：期末笔试：50%期末机试：30%上机实验：10%作业：10%课件mailto:courseware_ds@126.comcourseware_ds@126.com /帐号：courseware_ds 密码：123abc基本要求掌握数据组织和数据处理的方法掌握大型软件开发方法掌握基本编程方法课程关系C语言 数据结构 软件工程学习识字学习写作文学习写小说与语文学习过程类比后期课程前期课程承上启下操作系统编译原理数据库原理软件工程计算机基础C语言离散数学数据结构第1章 绪论 1.1 什么是数据结构（定义）1.2 数据结构的内容1.3 算法1.4 算法描述的工具1.5 对算法作性能评价1.6 关于学习数据结构 第一章 绪论计算机的应用:科学计算；控制、管理及数据处理等非数值计算的处理工作；计算机加工的对象:纯粹的数值；文本、表格和图像数据；如何表示、处理这些新的、具有一定结构的数据？《数据结构》是一门什么课程数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。解决数值计算问题的中心:建立适当的数学模型。解决非数值计算问题的中心:寻找适当的数据结构。例1，求解梁架结构中的应力。数学模型: K U = Ma11x1b1×＝……annxnbn例2，预报人口增长情况。dN(t)数学模型:r N(t)＝d tN(t)|t=t ＝ N00N(t) ＝ N0 e r t数值问题:例1，图书馆的书目检索系统自动化问题。通过提供书名、作者或分类信息，你就可以从图书馆中检索某一本书。…001数据结构周劲S01数据结构001,003…002程序设计潘玉奇L01程序设计002…003数据结构王永燕S01数据库004周劲001…S001,003004数据库曲守宁D01…潘玉奇002L002……………王永燕003D004曲守宁004…非数值问题:数据结构:线性表。当前格局OO××××OOOO××OO×××××××××××OOOO例2，计算机和人对奕问题。计算机可以根据当前棋盘格局，来预测棋局发展的趋势，甚至最后结局。数据结构:对弈树。派生格局143276521473652147365例3，地图的着色问题。对地图上的每个区域染一种颜色，并且要求相邻的两个区域不能具有相同颜色。数据结构:图。红绿绿蓝红绿黑用最少的颜色染色数学数据结构计算机硬件计算机软件 1. 数据（Data）对客观事物的符号描述，能输入到计算机中并被计算机程序处理的符号的总称；能被计算机识别、存储和加工处理的信息的载体。 例，数字：自然数、整数 字母：a ~ z, 单词 图像： 视频、音频信号等 表格： 2. 数据元素（Data Element） 数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。 例，“对弈树”中的一个格局 书目信息中的一条书目数据项: 一个数据元素可由若干个数据项组成。例，一条书目信息是由书名、作者名、分类等多个数据项组成的数据项是数据的不可分割的最小单位。例如 有一个学生表如下所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓名、性别和班号)组成。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901 3. 数据结构（Data Structure） 数据结构是指相互之间存在一种或多种特定关系的数据元素集合， 结构（Structure） 数据元素相互之间的关系。 在形式上可用二元组表示： Data_Structure = ( D,S) D: 数据元素的有限集 S: D上关系的有限集D = { ki | 1≤i≤n, n≥0}ki表示集合D中的第i个结点或数据元素n为D中结点的个数若n=0, 则D是一个空集, 表示D无结构可言, 有时也可以认为它具有任意的结构S={rj| 1≤j≤m, m≥0}rj 表示集合S中的第j个二元关系(简称关系)m为S中关系的个数若m=0, 则S是一个空集, 表明集合D中的元结点间不存在任何关系, 彼此是独立的 D上的一个关系r是序偶的集合, 对于r中的任一序偶x,y(x,y∈D),我们称序偶的第一结点为第二结点的直接前驱结点(通常简称前驱结点),称第二结点为第一结点的直接后继结点(通常简称后继结点)。如在x,y的序偶中,x为y的前驱结点,而y为x的后继结点。 若某个结点没有前驱,则称该结点为开始结点；若某个结点没有后继,则称该结点为终端结点；除此之外的节点称为内部节点。 “尖括号”表示有向关系，“圆括号”表