2017年数据结构c语言版算法与数据结构ppt模板课件.docVIP

2017年数据结构c语言版 算法与数据结构ppt模板课件 导读：就爱阅读网友为您分享以下“2017年数据结构c语言版 算法与数据结构ppt模板课件”资讯，希望对您有所帮助，感谢您对92的支持! 算法与数据结构 第 1章 绪 论 目前，计算机已深入到社会生活的各个领域，其应用已不 再仅仅局限于科学计算，而更多的是用于控制，管理及数据处 理等非数值计算领域。计算机是一门研究用计算机进行信息表 示和处理的科学。这里面涉及到两个问题：信息的表示，信息 的处理。 信息的表示和组织又直接关系到处理信息的程序的效率。 随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽， 使许多系统程序和应用程序的规模很大，结构又相当复杂。因 此，必须分析待处理问题中的对象的特征及各对象之间存在的 关系，这就是数据结构这门课所要研究的问题。 计算机求解问题的一般步骤 编写解决实际问题的程序的一般过程： ? 如何用数据形式描述问题?—即由问题抽象出一个适当的 数学模型; ? 问题所涉及的数据量大小及数据之间的关系; ? 如何在计算机中存储数据及体现数据之间的关系? ? 处理问题时需要对数据作何种运算? ? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。 1.1 数据结构及其概念 《算法与数据结构》是计算机科学中的一门综合性专业基础 课。是介于数学、计算机硬件、计算机软件三者之间的一门核 心课程，不仅是一般程序设计的基础，而且是设计和实现编译 程序、操作系统、数据库系统及其他系统程序和大型应用程序 的重要基础。 1.1.1 数据结构的例子 例1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电 话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)， 其中ai, bi(i=1，2…n) 分别表示某人的名字和电话号码。 本问 题是一种典型的表格问题。如表1-1，数据与数据成简单的一对 一的线性关系。 姓名 陈海 李四锋 。。。 表1-1 电话号码13056112345 。。。 线性表结构 例2：磁盘目录文件系统 磁盘根目录下有很多子目录及文 件，每个子目录里又可以包含多个子 目录及文件，但每个子目录只有一个 父目录，依此类推： 本问题是一种典型的树型结构问 题，如图1-1 ，数据与数据成一对多 的关系，是一种典型的非线性关系结 构—树形结构。 图1-1 树形结构 例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问题是一种 典型的网状结构问题，数据与数据成多对多的关系，是一种非 线性关系结构。 广州 佛山 惠州 东莞 中山 深圳 珠海 图1-2 网状结构 1.1.2 基本概念和术语 数据(Data) ：是客观事物的符号表示。在计算机科学中指的 是所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素( Data Element) ：是数据的基本单位，在程序中通 常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。数据项是 数据的不可分割的最小单位。数据项是对客观事物某一方面特性 的数据描述。 数据对象(Data Object)：是性质相同的数据元素的集合，是 数据的一个子集。如字符集合C={?A,‘B‘,‘C,…} 。 数据结构(Data Structure)：是指相互之间具有(存在)一定联 系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻 辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所 示。 集合：结构中的数据元素除了“同属于一个集合”外， 没有其它关系。 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中的数据元素之间存在多对 多的关系。 图1-3 四类基本结构图 1.1.3 数据结构的形式定义 数据结构的形式定义是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例2：设数据逻辑结构B=（K，R） K={k1, k2, …, k9} R={ k1, k3，k1, k8，k2, k3，k2, k4，k2, k5，k3, k9，k5, k6，k8, k9， k9, k7，k4, k7，k4, k6 } 画出这逻辑结构的图示，并确定那些是起点，那些是终点 数据元素之间的关系可以是元素之间代表某种含义的自然关 系，也可以是为处理问题方便而人为定义的关系，这种自然或 人为定义的 “关系”称为数据元素之间的逻辑关系，相应的结 构称为逻辑结构。 1.1.4 数据结构的存储方式 数据结构在计算机内存中的存储包括数据元