公共基础课件二

1,全国计算机等级考试 二级公共基础,计算机科学与技术系 董 再 秀 witsdongchzu.edu.cn,2,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),3,栈,栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示： 进行插入和删除的表尾端是浮动端，通常被称为栈顶， an 为栈顶元素， 并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底，a1为栈底元素。我们经常将栈用下图的形式描述：,a1, a2, a3, ., an 插入和删除端,4,5,栈的特征,结论：后进先出（Last In First Out），简称为LIFO线性表。 举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。 举例3：子弹夹。,6,栈的基本运算,（1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化,7,top=0 栈空 Top=m 栈满 （m为栈的最大容量）,B,A,C,D,8,1.4.2 队列及其基本运算,队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,9,下图是队列的示意图： a1 a2 an,出队,入队,10,队列的顺序存储结构,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,实现：用一维数组实现sqM,11,存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,12,入队运算是指在循环队列的队尾加入一个新元素 (1)首先将队尾指针进一,即rear=rear+1,并当rear=m+1时置rear=1。 (2)然后将新元素插入到队尾指针指向的位置。,出队运算是指在循环队列的排头位置退出一个元素并赋给指定变量。 (1)首先将排头指针进一，即front=front+1,并且当front=m+1时置front=1 (2)然后将排头指针指向的元素赋值给指定变量,13,队空：front=rear 队满：front=rear,解决方案： 另外设一个标志以区别队空、队满 S=0 (队空) S=1 (队满),14,队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括 （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 循环队列： s=0表示队列空 s=1且front=rear表示队列满,队列特征总结,15,1.5.1 线性链表的基本概念 线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 线性表顺序存储结构暴露的问题 在做插入或删除元素的操作时，会产生大量的数据元素移动； 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 线性表的容量难以扩充。,1.5 线性链表,16,线性表的链式存储结构,线性表的链式存储结构： 指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。 链表中结点的逻辑次序和物理次序不一定相同,17,为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系 数据结构中的每一个元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。 存储空间中的每一个结点分两部分：一部分用于存储元素的值，称数据域；另一部分用于存放下一个数据元素的 存储序号（存储结点的地址），即指向后件结点，称为指针域。,指针域，用来存放结点的直接后继的地址,数据域，用来存放结点的值,18,例如 ：线性表 （a, b,c,d),19,在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。,20,head,d,c,b,a,线性（单）链表的逻辑结构,null,其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。,L,双向链表：,R,21,110 hat 200,130 cat 135,135 eat 170,160 mat NULL,165 bat 130,170 fat 110,200 jat 205,205 lat 160,165,head,头指针,数据域,指针域,例如：线性表 （bat,cat,eat,fat,hat,jat,lat,mat）,bat,cat,eat,mat ,head,22,链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,23,1.5.2 线性链表的基本运算,1、在线性链表中查找指定元素 在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，要找到线性链表中指定值的前一个结点。,查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL,算法评价,24,插入：在线性表两个数据元素a和b间插入x，已知p指向a,s-link=p-link;,p-link=s;,算法评价,25,p,a,b,c,删除：删除链表中b结点，已知p指向a结点,p-link=p-link-link,算法评价,26,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。 人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。 由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,栈的链式存储,27,28,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。,front,rear,队列的链式存储,29,循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致，它可以使空表和非空表的运算统一 单链表p或p-link=NULL 循环链表p或p-link=H,1.5.2 循环链表的基本运算,30,例题讲解,31,线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构 链表不具有的特点是 A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比,32,线性表若采用链式存储结构时，要求内存中可用存储单元的地址 A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续不连续都可以 栈和队列的共同特点是 A)都是先进先出 B) 都是先进后出 C)只允许在端点处插入和删除元素 D) 没有共同点,33,如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序 一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用 A) 栈 B) 堆 C) 数组 D) 链表 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为 【2】 。,34,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 栈通常采用的两种存储结构是 A) 顺序存储结构和链表存储结构B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构 栈和队列通常采用的存储结构是 【1】 。 下列数据结构中，按先进后出原则组织数据的是 A) 线性链表 B) 栈 C) 循环链表 D) 顺序表,35,由两个栈共享一个存储空间的好处是 A) 减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率 C) 减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率 下列关于栈的叙述中正确的是 ）在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是后进先出的线性表,36,下列关于队列的叙述中正确的是 ）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是后进先出的线性表,37,1.6 树与二叉树,树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 例如家谱、行政组织机构都可用树形象地表示,38,在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。,39,本例是有13个结点的树，其中A是根，其余结点分成3个子集： T1 、T2 、T3 。都是根A的子树，且本身也是一棵树。例如： T1 其根为B，两棵子树为 T11 = F ， T12 = E, K, L ， T12 又是一棵子树，树根为