计算机二级公共基础知识

《计算机二级公共基础知识》由会员分享，可在线阅读，更多相关《计算机二级公共基础知识（66页珍藏版）》请在金锄头文库上搜索。

1、全国计算机等级考试二级教程二级公共基础知识数据结构与算法(2008年版)赵国瑞 2009.2第1页第1章 数据结构与算法算法是指解题方案的准确而完整的描述。 所谓算法，是一组严谨地定义运算顺序的规 则，并且每一个规则都是有效的，且是明确的， 此顺序将在有限的次数下终止。 1.1 算法第2页(1)可行性。针对实际问题而设计的算法，执行后能够 得到满意的结果。 (2)确定性。每一条指令的含义明确，无二义性。并且 在任何条件下，算法只有唯一的一条执行路径，即相同的输 入只能得出相同的输出。 (3)有穷性。算法必须在有限的时间内完成。有两重含 义，一是算法中的操作步骤为有限个，二是每个步骤都能在 有限

2、时间内完成。 (4)拥有足够的情报。一个算法执行的结果总是与输入 的初始数据有关，不同的输入将会有不同的结果输出。当输 入不够或输入错误时，算法将无法执行或执行有错。一般说 来，当算法拥有足够的情报时，此算法才是有效的；而当提 供的情报不够时，算法可能无效。算法的基本特征第3页(1)算法中对数据的运算和操作 包括算术运算、逻辑运算、关系(比较)运算、数据传输( 赋值、输入、输出等) 算法的设计一般是按解题要求选择适当的操作组成解题 的操作序列。 (2)算法的控制结构 算法中各操作之间的执行顺序称为算法的控制结构。 算法可以用传统流程图、N-S结构化流程图、算法描述 语言等描述。 一个算法可以用

3、顺序、选择、循环三种基本控制结构组 合而成。算法的基本要素第4页计算机解题的过程实际上就是实施某种算法，这种算法 称为计算机算法。它与人工算法不同。 算法设计就是对给定的问题设计出解决它的有效算法。 常用的算法设计方法有：穷举法、归纳法、递推法、递 归法、减半递推技术、回溯法、迭代法、分治法等。 穷举法(列举法)： 穷举法是对可能的情况按某种顺序逐一列举、检验，从 中找出符合要求的解。 经常用于解决“是否存在”或者“有多 少种可能”等类型的问题。 例如，“百钱百鸡”问题，是我国古代数学家一道解不定 方程的问题。设公鸡每只5元，母鸡每只3元，小鸡每3只1元 。要用100元钱买100只鸡，问公鸡、

4、母鸡和小鸡各买多少 只。 在用穷举法设计算法时，要注意方案优化，减少列举量 。算法设计基本方法第5页归纳法： 归纳法是通过从少量简单而特殊的情况中找出一般 关系。归纳是一种抽象。 归纳出的结论还只是一种猜测，必须通过证明才能 知道是否正确或错误。但是，常有得不到证实对错的情 况。 例如，等差数列求和公式的证明。 递推法： 递推法是利用问题本身所具有的某种递推关系求问 题解的一种方法。 递推法从已知的初始条件出发，逐次推出所要求的 各中间结果和最后结果。递推本质上属于归纳法。 例如，数学和工程中的递推关系。 数值型的递推算法必须注意其计算的稳定性。第6页递归法： 递归过程是将一个复杂的问题，归结

5、为若干个较简单： 的问题，然后再将这些较简单的问题归结为简单的问题，直 到最简单的问题为止。 例如，计算n!可归结为n乘以(n-1)!，直到1!或者0!为 止。1!或者0!都等于1。 递归分为直接递归和间接递归。 递归算法的执行效率较低。递推本质上也属于归纳法。 减半递推技术： 减半递推技术是一种分治法。分治法的基本思想是把一 个大问题分解为一些较小的问题，然后由小问题的解方便地 构造出大问题的解。在很多领域应用此方法。 “减半”是指将问题的规模减半而问题的性质不变。 “递推”是指重复“减半”的过程。 例如，二分法求方程的根。第7页例1.1 二分法求方程的根。 设方程f(x) =0且f(a)与

6、f(b)异号，则f(x)在 区间a,b上必有实根。 (1)取区间的中点c(a+b)/2； (2)如果f(c)=0，则c即为所求，算法结束； (3)如果f(a)f(c)l)printf(“插入位置错n”); return 1;for(j=l-1;j=i;j-)aj+1=aj;ai=x;return 0; 第25页线性表的顺序存储结构顺序表的删除运算： 在一般情况下，要删除第i（1in）个元素时， 则要从第i+1个元素开始，直到第n个元素之间共n-i个 元素依次向前移动一个位置。删除结束后，线性表的长 度减1。 进行顺性表的删除运算时也需要移动元素，在等概 率情况下，平均需要移动（n-1）/2个元

7、素。 顺序表的优点： 实现简单，查找、排序等运算效率高。 顺序表的缺点： 插入、删除运算效率较低；事先必须有确定的最大 长度，大则浪费，小则不够用。第26页栈（stack） 栈是限定在一端进行插入与删除运算的线性表。 在栈中，允许插入与删除的一端称为栈顶，不允许插入 与删除的另一端称为栈底。栈顶元素总是最后被插入的元素， 栈底元素总是最先被插入的元素。即栈是按照“先进后出 (FILO Fist In Last Out)”或“后进先出(LIFO Last In Fist Out)”的原则组织数据的。因此，栈具有记忆作用。a1an入栈退栈栈顶 top栈底 bottom栈结构示意图：栈的例子: 子弹

8、夹 有底无盖桶第27页顺序栈顺序存储形式的栈-顺序栈 在程序设计语言中，一般用一维数组S(1:m)实现 顺序栈(m为栈的最大容量)。 S(top)表示栈顶元素， S(bottom)表示栈底元素。top为0表示栈空， top为 m表示栈满。栈的基本运算：入栈、退栈和读栈顶元素 。 顺序栈的基本运算： 1）入栈：插入元素x 如果栈不满，则top top+1，S(top) x； 否则栈满(top=m)，不能入栈(上溢)。 2）退栈： 如果栈不空，则x S(top)， top top-1。 否则栈空(top=0)，不能退栈(下溢) 。 3）读栈顶元素： 如果栈不空，则x S(top) 。第28页队列(

9、queue)队列是指允许在一端(队尾) 进入插入，而在另一端 (队 头)进行删除的线性表。尾指针( rear) 指向队尾元素，头 指针(front)指向排头元素(队头元素)的前一个位置。 队列是“先进先出(FIFO)”或“后进后出(LILO)”的线 性表。它体现了“先来先服务”的原则。队列示意图front入队退队rearEDABCFG队列长度= rear- front通过指针rear和front的变化，可以反映入队和退队的情况 。第29页队列在程序设计语言中，一般用一维数组Q(1:m)实现顺序队列 (m为队列的最大容量)。 在实际应用中，顺序队列一般采用循环队列的形式。 所谓循环队列，就是将队

10、列存储空间的最后一个位置绕到第 一个位置，形成逻辑上的环状空间，供队列循环使用。顺 序 循 环 队 列 示 意 图rearfrontG F E D C8 7 6 5 4 3 2 1Q(1:8)第30页循环队列由于循环队列为空或满的时候，都有front=rear，为了区别， 设立标志变量s，且规定s=0表示队列空，s=1表示队列非空。 因此，队列空的条件为s=0，队列满的条件为s=1同时 front=rear。 循环队列中元素的个数：队列不满时为rear-front，队列满时为 m。 循环队列的两种基本运算：入队运算和退队运算。 设循环队列的初始状态为空，即s=0，且front=rear=m。

11、入队运算：若队列不满，则rear=rear+1(若rear=m+1则置 rear=1)，Q(rear)=x；若队列满，则不能入队(上溢)。 退队运算：若队列非空，则front= front+1 (若front =m+1则置front=1)， x=Q(front) ；若队列空，则不能退 队(下溢)。第31页线性链表线性表顺序存储的优点： 构造简单，运算方便，可直接存取，适合于小线性表或者长 度固定的线性表。 线性表顺序存储的缺点： 1)插入或删除的运算效率很低。在顺序存储的线性表中，插 入或删除数据元素时需要移动大量的数据元素； 2)线性表的长度必须事先确定，存储空间不便于扩充； 3)在同时使用

12、多个线性表时，难以对它们进行顺序存储分配 ，要保持顺序存储结构的“连续、依次存放”的特点，不便于 对存储空间的动态分配。 为了克服线性表顺序存储的缺点，一般采用“依次但未必连续 存放”的链式存储结构。第32页线性链表线性链表：线性表的链式存储结构称为线性链表，是一种物理 存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序 是通过链表中的指针链接来实现的。因此，在链式存储方式中 ，每个结点由两部分组成：一部分用于存放数据元素的值，称 为数据域；另一部分用于存放指针，称为指针域，用于指向该 结点的前一个和/或后一个结点（即前件和/或后件）。 线性链表分为单链表、双向链表和循环链表三种类型。 在

13、单链表中，每一个结点只有一个指针域，指向其后件结点。 如下图所示：datanext数据域指针域结点结构非空线性链表的逻辑结构an-1HEADan-1a1a2an当头指针HEAD为(null、0)时称为空表。第33页线性链表在双向链表中，每个结点设置两个指针，一个称为左指 针(Llink)，指向其前件结点；另一个称为右指针(Rlink) ， 指向其后件结点。如下图所示：在循环链表中，最后一个结点的指针域不是空，而是指 向表头结点，所有结点的指针构成了一个环状链。单循环链 表和双循环链表如下图所示：an-1HEADan-1a1a2anHEAD a1a2anHEAD a1a2an第34页线性链表链式

14、栈：采用链接存储结构的栈。top0an-1a1a2an链式栈可以用于收集计算机存储空间中的全体空闲存储结 点，这种链式栈称为可利用栈。 可利用栈的作用是管理可用于链表插人和删除的结点，当 链表需要插入一个新结点时，就从可利用空间表中删除第一个 结点，用这个结点去做链表插入；当从链表中删除一个结点时 ，就把这个结点插入到可利用栈的第一个结点前面。 链式队列：采用链接存储结构的队列。 front 0an-1a1a2anrear第35页线性链表的基本运算在线性链表中包含指定元素的结点之前插入一个新元 素。在线性链表中插入元素时，不需要移动数据元素，只需要 修改相关结点指针即可，也不会出现“上溢”现象

15、。 在线性链表中删除包含指定元素的结点。在线性链表 中删除元素时，也不需要移动数据元素，只需要修改相关结点 指针即可。 将两个线性链表按要求合并成一个线性链表。 将一个线性链表按要求进行分解。 逆转线性链表。 复制线性链表。 线性链表的排序。 线性链表的查找。 注意：线性链表不能随机存取 。 第36页线性链表线性链表的插入与删除运算都需要查找指定元素的前一个结点 。 在非空单线性链表中，查找指定元素x的前一个结点p的方法： 从头指针指向的结点开始，往后沿指针进行扫描，直到下一个 结点的数据域为x或者后面已没有结点为止。 因此，查找运算有两种结果：当表中存在x结点时，则找到的p 为第一次遇到的x

16、结点的前一个结点；否则，找到的p为表中的 最后一个结点。 在线性链表中包含指定元素x的结点之前插入一个新元素k： 在链表中查找指定元素x的前一个结点p 获取一个新结点q，填入结点元素值k 使结点q指向包含指定元素x的结点(即成为q的后件) 使结点p指向结点q (即成为p的后件)一个非空链表的插入运算示意图(见下页)第37页线性链表在线性链表中删除包含指定元素x的结点： 在链表中查找指定元素x的前一个结点p 使结点p指向包含指定元素x后的结点(即成为p的后件) 释放包含指定元素x结点的存储空间x p qk 点击鼠标演示 点击鼠标演示x p第38页循环链表及其基本运算线性链表的插入与删除运算虽然比较方便，但在运算过程 中对于空表和对第一个结点的处理必须单独考虑，使空表与非 空表的运算不统一。为了克服线性链表的这个缺点，可以采用 另一种链接方式，即循环链表(Circular Linked List)。 循环链表的特点： 在链表中增加了一个表头结