首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2020考研计算机《数据结构(C语言版)》复习笔记(3)

2019-05-23 12:18:31来源：网络

　　2020年计算机考研复习已经开始，新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(3)，希望能帮助大家!

　　第三章 栈和队列知识点整理

　　栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。

　　栈的基本运算有六种： ·

　　构造空栈：InitStack(S)

　　·判栈空： StackEmpty(S)

　　·判栈满： StackFull(S)

　　·进栈： Push(S，x)

　　·退栈： Pop(S)

　　·取栈顶元素：StackTop(S)

　　在顺序栈中有“上溢”和“下溢”的现象。 ·“上溢”是栈顶指针指出栈的外面是出错状态。·“下溢”可以表示栈为空栈，因此用来作为控制转移的条件。

　　顺序栈中的基本操作有六种：·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取栈顶元素

　　链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。

　　链栈中的基本操作有五种：·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素

　　队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) ，队列的操作原则是先进先出的，又称作FIFO表(First InFirst Out) .队列也有顺序存储和链式存储两种存储结构。

　　队列的基本运算有六种：

　　·置空队：InitQueue(Q)

　　·判队空：QueueEmpty(Q)

　　·判队满：QueueFull(Q)

　　·入队：EnQueue(Q，x)

　　·出队：DeQueue(Q)

　　·取队头元素：QueueFront(Q)

　　顺序队列的“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。

　　判定循环队列是空还是满，方法有三种：

　　·一种是另设一个布尔变量来判断;

　　·第二种是少用一个元素空间，入队时先测试((rear+1)%m = front)? 满：空;

　　·第三种就是用一个计数器记录队列中的元素的总数。

　　队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。


本文关键字: 2020考研计算机

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10