第1章数据结构和算法[公共].pptVIP

第一章 数据结构与算法 ;1.1 算法;考点1 算法的基本概念 考试链接： 考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。算法不等于程序，但程序可以作为算法的一种描述。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报 2．算法的基本要素： 一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。 （1）算法中对数据的运算和操作 在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。 （2）算法的控制结构： 算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。;;;;;;;;;线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： （1）所有元素所占的存储空间是连续的； （2）各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。 顺序表的插入运算 设长度为n的线性表为（ a1,a2,…,ai,…an ），现要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表。 一般情况下，要在第i（1=i=n）个元素之前插入一个新元素，首先要从最后一个元素开始，直到第i个元素，其间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。 在平均情况下，在线性表中插入一个新元素，需要移动表中一半的元素。;顺序表的删除运算 设长度为n的线性表为（ a1,a2,…,ai,…an ），现要删除第i个元素ai，删除后得到长度为n-1的线性表。 一般情况下，要删除第i（1=i=n）个元素，则要从第i+1个元素开始，直到第n个元素，其间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。 在平均情况下，在线性表中删除一个新元素，需要移动表中一半的元素。;;;注：栈支持子程序调用。在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点（只能在一端进行插入与删除）。;3.队列的基本概念 队列是指允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常用一个队头指针（front）指向队头元素的前一个位置。 队列又称为“先进先出”或“后进后出”的线性表。在队列中，队尾指针rear和队头指针front共同反映了队列中元素动态变化的情况。 往队列的队尾插入一个元素称为入队运算，从队列的队头删除一个元素称为退队运算。 4.循环队列及其运算 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。;;;;;2.线性链表及其基本运算 指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL(或0)时称为空表。 （1）在线性链表中查找指定元素 在非空线性链表中寻找包含指定元素值x的前一个结点p的方法如下： 从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点序号。 （2）线性链表的插入 线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。 首先给该元素分配一个新结点，以便用于存储该元素的值，然后将存放新元素值的结点链接到线性链表中指定的位置。 （3）线性链表的删除 线性链表的删除是指在