《公共基础课件二》PPT课件

《《公共基础课件二》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试二级公共基础计算机科学与技术系董再秀witsdong@chzu.edu.cn1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)栈栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：进行插入和删除的表尾端是浮动端，通常被称为栈顶，an为栈顶元素，并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底，a1为栈底元素。我们经常

2、将栈用下图的形式描述：a1,a2,a3,...,an插入和删除端栈的特征结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。举例3：子弹夹。栈的基本运算（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化bottom

3、ABCDEtoptop=0栈空Top=m栈满（m为栈的最大容量）bottomtopBA1234512345bottomtopBA12345CD1.4.2队列及其基本运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加

4、入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。下图是队列的示意图：a1a2…　an出队入队队列的顺序存储结构front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==r

5、ear入队列：sq[++rear]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront实现：用一维数组实现sq[M]存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出当front-1,rear=M-1时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则

6、令rear=0;1M2frontrear…...…...入队运算是指在循环队列的队尾加入一个新元素(1)首先将队尾指针进一,即rear=rear+1,并当rear=m+1时置rear=1。(2)然后将新元素插入到队尾指针指向的位置。出队运算是指在循环队列的排头位置退出一个元素并赋给指定变量。(1)首先将排头指针进一，即front=front+1,并且当front=m+1时置front=1(2)然后将排头指针指向的元素赋值给指定变量123456rearfrontJ4J5J6123456rearfrontJ9J8J7J4J5J61

7、23456rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：另外设一个标志以区别队空、队满S=0(队空)S=1(队满)队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空s=1且front=rear表示队列满

8、队列特征总结1.5.1线性链表的基本概念线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。线性表顺序存储结构暴露的问题在做插入或删除元素的操作时，