精·chap2-DS课件-1.pptVIP

学习目标与要求 重点 1）数据结构的基本概念 2）线性表、栈与队列的定义，存储表示 3）排序 难点 1）线性表的链式存储结构及其运算 本章要点 对许多规模大、结构复杂的程序，要考虑其效率及可靠性，除了对程序设计的方法进行系统的研究之外，还要研究程序所处理的信息，信息的表示和组织，直接影响到计算机程序处理信息的效率。本章主要讨论数据处理过程中数据的储存方式与处理算法。 (1）线性链表(单链表):链式存储的线性表 结点除信息域外还含有一个指针域，用来指出其后继结点的位置 最后一个结点没有后继结点，指向它的指针域为空(记为NIL 或∧)。另外还需要设置一个头指针head，指向单链表的第一个结点，如下图示： 链表的重要特点是：插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可。 1）双向链表的插入 2）双向链表的删除 栈 栈(Stack)：是一种特殊的线性表，是一种“后进先出”(LIFO)的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构。 (1）栈的结构特点 栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom) 栈的物理存储可以用顺序存储结构，也可以用链式存储结构 (2）栈的运算 设置一个空栈 判定栈是否为空 进栈、退栈 读取栈顶元素等 堆栈操作 栈的应用 栈的应用非常广泛，只要问题满足先进后出的原则，均可使用栈作为其数据结构。 数制转换 括号匹配检查 行编辑处理 表达式求解 栈在递归算法中的应用 ……… 队列 (1）队列的结构特点 队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表 表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front) 队列的操作是按先进先出的原则进行的 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。 (2）队列的运算设置一个空队列；判定队列是否是空队列；入队列；出队列；读取队头元素等 如果队列的容量无法预先估计时，可以采用链表存储结构 顺序队列出入队 顺序队列的假上溢现象 当队列满时，做进栈运算产生空间溢出的现象称为”上溢”。 由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数小于向量空间的规模时，也由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。 循环队列 链队列－队列的链式表示和实现 用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针，如图所示。 串 串(String)可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作 许多高级语言把串作为一种单独的类型，其元素不可作四则运算 进行连接、删除、插入操作，用子串有时很方便 子串(Substring)是串的一部分，具有串的一切特征 初始时, 队列为空, 有 front = -1 rear = -1 约定 rear 指出实际队尾元素所在的位置, front 指出实际队头元素所在位置的前一个位置. queue[0~M-1] 0 M-1 a b c d front rear a d A出队后 为充分利用向量空间，克服“假上溢”现象的方法 是：将向量空间想象为一个首尾相接的圆环，并 称这种向量为循环向量。存储在其中的队列称为 循环队列（Circular Queue）。 0 1 2 3 4 M-1 M-2 : : 利用模运算 * 上一张 下一张 结 束 数据结构与算法 第2章 数据结构与算法 计算机软件技术基础 Technology Fundamentalsof Computer Softwar 概述 线性表数据结构 查找 概述 数据结构的概念 数据的逻辑结构 数据的物理结构 算法及其描述 （1）数据的逻辑结构独立于计算机，是数据本身所固 有的。 （2）存贮结构是逻辑结构在计算机存贮器中的映像， 必须依赖于计算机。 （3）运算是指所施加的一组操作总称。运算的定义直 接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 数据的物理结构 数据结构在计算机中的表示（映像），也称存储结构。 1．顺序存贮（向量存贮） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 2 ．链式存贮 所有元素存