数据结构+线性表+队列+栈.pptVIP

数据结构 数据结构 现在开始详细介绍数据结构三方面内容： 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立与计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数据模型。数据逻辑结构分为线性结构和非线性结构。若数据元素之间的逻辑关系可以用一个线性序列简单地表示出来，则称为线性结构，否则称为非线性结构。 数据的存储结构是逻辑结构在计算机存储器中的表现，它不仅要存储数据元素本身，还要把数据元素间的关系体现出来，它是逻辑结构用计算机语言的实现（亦称为映像）。它是依赖计算机语言的，对机器语言而言，存储结构是具体的，但我们只在高级语言的层次上来讨论存储结构。存储结构主要分为顺序结构（Sequential Storage Structure）和链式结构（Linked Storage Structure）。顺序结构用元素在存储器中的相对位置来表示元素间的逻辑关系，链式结构借助元素存储地址的指针来表示元素间的逻辑关系。 数据的运算是在数据上所施加的一系列操作，称为抽象运算。它只考虑这些操作的功能是怎样的，而暂时不考虑其如何完成。只有在确定了存储结构，才会具体实现这些操作（本讲座中讨论的数据运算，均以Pascal语言描述的算法来实现）。也就是说，抽象运算是定义在逻辑结构上，而实现在存储结构上，数据的运算是数据结构的一个重要方面。 学习数据结构都离不开对该结构上的数据运算及算法设计的讨论，典型的运算有插入、删除、遍历和排序等。 算法的定义和描述 数据的运算是通过算法（Algorithm）描述的，所以讨论算法是数据结构课程的重要内容之一。 通俗的讲，一个算法就是一种解题方法。更严格的说，算法是由若干条指令组成的有穷序列，它必须满足下述准则： （1）输入：一个算法有0个或多个输入，以刻划运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。 （2）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 （3）有穷性：一个算法必须保证执行有限步之后结束。 （4）确定性：算法的每一步骤必须确定定义。 （5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次即可完成。 算法与程序二者是有区别的。一个程序不一定满足有穷性。 线性结构中线性表 线性表的逻辑结构 线性表的逻辑结构 线性表的逻辑结构 线性表的基本运算 线性表的逻辑结构 栈的原理 队列的原理 * 郑集中学信息中心 郑集中学 计算机奥林匹克竞赛辅导 数据结构（Data Structure）指的是数据之间的相互关系，即数据的组织形式。它一般包括以下三方面的内容： （1）数据元素之间的逻辑关系，也称为数据的逻辑结构（Logical Structure）。 （2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）。 （3）数据的运算，即对数据施加的操作。 先了解几个概念： 数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。 数据元素（Data Element）是数据的基本单位。有些情况下，数据元素也成为元素、结点、顶点、记录。有时一个数据元素可以有若干个数据项（也可以称为字段、域）组成，数据项是具有独立含义的标识单位。 线性表是最简单最常用的一种数据结构。 线性表的例子不胜枚举，例如，一副扑克牌的点数（2，3，4，5，6，7，8，9，10，J，Q，K，A）是一个线性表，其中每一张牌的点数是一个数据元素。 在较复杂的线性表中，数据元素可由若干数据项组成，如学生成绩表（图一），每个学生及其成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项组成。 ┋ ┋ ┋ ┋ ┋ ┋ ┋ 85 255 81 82 90 王… 200104 86 258 86 80 92 郭… 200103 87 261 82 82 97 赵… 200102 92 276 92 89 95 李… 200101 平均成绩 总成绩 计算几何 离散数学 数据结构 姓名 学号 1.线性表简单的定义 n个数据元素的的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。 1、线性表的顺序存储结构线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。 在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。 2、线性表的链式存储结构a.