当前位置:
文档之家› 最新全国计算机等级考试--二级公共基础知识( 100)课件PPT
最新全国计算机等级考试--二级公共基础知识( 100)课件PPT
在循环队列为空或为满时,均有front=rear,因此需 要设置标志s进行区分,定义s=0表示队列为空,s=1 表示队列非空。
单链表
线性表的链式存储结构的特点是用一组任意的存 储单元(可以连续,也可以不连续)存储线性表的数 据元素,为了表示每个数据元素ai与其直接后继元 素ai+1之间的逻辑关系,对数据元素ai来说,除了 存储其本身的信息(数据域)之外,还需要存储其后 继元素的存储位置信息(指针域)。
队列是一种先进先出的数据结构。 向队尾插入一个元素的操作称为入队,从队头删除一个元素
的操作称为退队。
退队
A
B
C
D
E
F
Front
Rear
入队
循环队列
将队列存储空间的最后一个位置绕到第一个位置,形 成逻辑上的环状空间。
循环队列初始状态为空,即front=rear=m。
入队操作时,rear加1,若rear=m+1,则置rear=1; 退队操作时,front加1,若front=m+1,则置front=1。
数据的存储结构
数据的存储结构是数据元素及其关系在计算机存储器中 的表示。存储结构的主要内容是指在存储空间中使用一 个存储结点来存储一个数据元素,在存储空间中建立各 存储结点之间的关联,来表示数据元素之间的逻辑关系。
常见的存储结构:
顺序存储结构 链式存储结构 索引存储结构 散列存储结构
线性结构和非线性结构
通常用指针top指示栈顶位置,用指针bottom指示栈底位置。
入栈
出栈
栈顶 top
an
……
a2
栈底 bottom
a1
栈的顺序存储及运算
用一维数组S(1:m)作为栈的顺序存储空间,m 为栈的最大容量。top=0表示栈为空,top=m 表示栈满。
栈的操作
入栈:在栈顶位置插入一个新元素,栈顶指针top加 1。
删除运算是指撤销结构中的某个结点。 一般情况,要删除第i(1≤i≤n)个元素,要从第i+1
个元素开始,直到第n个元素,共n-i个元素依次向 前移动一个位置。
栈
栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和 删除的一端称为栈顶,另一端称为栈底。
栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈 底元素总是最先被插入,也是最后被删除的元素。因此,栈是一种 后进先出的线性表。
全国计算机等级考试--二级公共 基础知识( 100)
第一章 数据结构与算法(30%)
考试大纲
1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复 杂度)。 2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表 示;线性结构与非线性结构的概念。 3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序 和后序遍历。 7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类 排序,插入类排序)。
2. 在对数据进行处理时,各数据元素在计算机 中的存储关系,即数据的存储结构。
3. 对各种数据结构进行的运算。
数据的逻辑结构
数据逻辑结构是对数据 元素之间存在的逻辑关 系的描述,它可以用一 个数据元素的集合和定 义在此集合上的若干关 系表示。
与数据在计算机中的存 储位置无关,是独立于 计算机的。
线性结构
在数据元素的非空有限集合中,线性结构的逻辑特征 如下:
存在一个唯一的被称为“第一个”的数据元素 存在一个唯一的被称为“最后一个”的数据元素 除第一个之外,集合中的每个数据元素均有且只有一
个直接前驱 除最后一个之外,集合中的每个数据元素均有且只有
一个直接后继
非线性结构
非线性结构的逻辑特征是:一个结点可能有多个直接 前驱和直接后继,树和图都属于非线性结构。方案的准确而完整的描述。严格来
说,一个算法必须具有以下五个主要特征:
有穷性 确定性 可行性 输入 输出
综上,所谓算法,是一组严格定义运算顺序的规则, 而且每一个规则都是有效且明确的,此顺序将在有限 的次数终止。
算法的复杂度
算法的空间复杂度 算法的空间负杂度是指执行这个算法所
所有数据元素的存储位置均可由第一个数据元素的存储位置得到
ADR(ai) = ADR(a1) + (i-1)×C
↑
↑
基地址
一个数据元素所占存储量
线性表的插入和删除运算
插入运算是指在线性表的某个指定位置增加一个 新结点。
一般情况下,要在第i(1≤i≤n)个元素之前插入一个 新元素时,首先要从最后一个元素开始,直到第i 个元素之间共n-i+1个元素依次向后移动一个位置, 然后将新元素插入到第i项。
退栈:取出栈顶元素并赋值给一个指定的变量,栈 顶指针top减1。
取栈顶元素:将栈顶元素的值赋给一个指定的变量, 不删除栈顶元素,栈顶指针不变。
队列
队列是一种先进先出的线性表,它只允许在表的一端插入元 素(队尾),在另一端删除元素(队头)。通常定义头指针front 指向队头元素的前一个位置,定义尾指针rear指向队尾元素 的位置。
需要的内存空间。空间复杂度作为算法 所需存储空间的量度,记作: S(n)=O(g(n)),其中n为问题的规模, 表示随问题规模的增大,算法运行所需 存储量的增长率与g(n)的增长率相同。
数据结构
利用计算机进行数据处理是计算机应用的一 个重要领域。数据结构主要研究和讨论以下 三个方面的问题:
1. 数据集合中各数据元素之间的逻辑关系,即 数据的逻辑结构。
线性表
通常以下列 n 个数据元素的序列”表示 线性表 : (a1,a2 ,...,ai ,...,an)
序列中数据元素的个数 n 定义为线性表 的表长;n=0 时的线性表被称为空表。 称 i 为ai在线性表中的位序。
线性表的顺序存储
线性表的顺序存储结构用一组地址连续的存储单元依次存放线 性表中的数据元素,即以“存储位置相邻”表示“位序相继的 两个数据元素之间的前驱和后继的关系,并以表中第一个元素 的存储位置作为线性表的起始地址,称作线性表的基地址。