C语言基于考研的栈和队列

目录
  • 栈
    • 栈的基本操作
    • 三角矩阵
  • 总结

栈

栈的基本操作

InitStack(&S):初始化

StackEmpty(S):判空，空则true，非空则false

Push(&S,x):入栈

Pop(&S,&x):出栈，并用x返回元素内容

GetTop(S,&x):读栈顶元素

DestroyStack(&S):销毁并释放空间

栈是一种受限的线性表，只允许在一端操作

栈若只能在栈顶操作，则只可能上溢

采用非递归方式重写递归时，不一定要用栈，比如菲波那切数列只要用循环即可

共享栈：

从两头往中间填充，有效的利用空间。

出栈序列的个数：1𝑛+1𝐶2𝑛𝑛

队列

队列也是受限的线性表，只允许在一端插入，另一端删除

FIFO（First in first out）

常见操作：

InitQueue（&Q）：初始化，构造一个空队列Q

QueueEmpty（Q）：判空

EnQueue（&Q，x）：入队

DeQueue（&Q，&x）：出队并返回出队的元素至x

GetHead（Q，&x）：获取对头元素

队列的大题真题考的是，画初始状态，判空判满的条件，入队基本过程

So先看类似的概念，想法，思路，后期再看具体的代码实现，毕竟没考过具体代码

顺序存储定义：

#define Maxsize 50

typedef struct{
Elemtype data[Maxsize];

int front,rear;

}SqQueue;

循环队列：

初始化：Q.front=Q.rear=0

队首指针+1\入队：Q.front=(Q.front+1)%Maxsize

队尾指针+1\出队：Q.rear=(Q.rear+1)%Maxsize

队列长度：(Q.rear+Maxsize-Q.front)%Maxsize

因为队满和队空都是Q.front=Q.rear，所以无法判断到底是队空还是队满

有三个解决办法

1）常用方法：牺牲一个单元来区分队空和队满，入队是少用一个单元

队满条件：（Q.rear+1）%MaxsizeQ.front

队空条件：Q.frontQ.rear

队列中元素个数：（Q.rear-Q.front+Maxsize）%Maxsize

2）类型中增设一个数据成员表示元素个数，这样队空：Q.size0,队满：Q.sizeMaxsize

3）增设tag，入队时令tag=1，出队时令tag=0，这样能表示当Q.frontQ.rear时，如果tag1，则队满，tag==0则队空

链式存储：

typedef struct LinkNode{ //定义节点

Elemtype data;

struct LinkNode *next;

}LinkNode;

typedef struct{ //定义队列的首尾节点

Node *front,*rear;

}LinkQueue;

栈和队列的应用

括号匹配

表达式求值

后缀表达式：数据进栈，操作符则弹出2个数据进行操作再将结果进栈

同一个问题，递归算法和非递归算法一般来说，非递归效率比较低，因为有很多重复计算

图的广度优先算法要借助辅助队列

将中缀表达式转换为前缀表达式

转换步骤如下:

初始化两个栈:运算符栈s1，储存中间结果的栈s2

从右至左扫描中缀表达式

遇到操作数时，将其压入s2

遇到运算符时，比较其与s1栈顶运算符的优先级

如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈

否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1

否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较

遇到括号时

如果是右括号“)”，则直接压入s1

如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃

重复步骤2至5，直到表达式的最左边

将s1中剩余的运算符依次弹出并压入s2

依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

将中缀表达式转换为后缀表达式

与转换为前缀表达式相似，步骤如下：

初始化两个栈：运算符栈s1和储存中间结果的栈s2；

从左至右扫描中缀表达式；

遇到操作数时，将其压s2；

遇到运算符时，比较其与s1栈顶运算符的优先级：

如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；

否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；

遇到括号时：

如果是左括号“(”，则直接压入s1；

如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；

重复步骤2至5，直到表达式的最右边；

将s1中剩余的运算符依次弹出并压入s2；

依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）

特殊矩阵的压缩存储

对称矩阵

三角矩阵

三对角矩阵：又称带状矩阵

稀疏矩阵：三元组既可以用数组存储，也可以用十字链表法

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C语言用栈和队列实现的回文检测功能示例

    C语言用栈和队列实现的回文检测功能示例

    本文实例讲述了C语言用栈和队列实现的回文功能.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h>//内存分配头文件 #include<math.h>//在math.h中已定义OVERFLOW的值为3 #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typede

  • C语言中栈和队列实现表达式求值的实例

    C语言中栈和队列实现表达式求值的实例 实现代码: #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemty

  • C语言 表、栈和队列详解及实例代码

    C语言 表.栈和队列详解 表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指

  • 深入浅析C语言中堆栈和队列

    深入浅析C语言中堆栈和队列

    1.堆和栈 (1)数据结构的堆和栈 堆栈是两种数据结构. 栈(栈像装数据的桶或箱子):是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取.这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体). 堆(堆像一棵倒过来的树):是一种经过排序的树形数据结构,每个结点都有一个值.通常所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆.由于堆的这个特性,常用来实现优先队列,堆的存取是随意,

  • C语言基于考研的栈和队列

    C语言基于考研的栈和队列

    目录 栈 栈的基本操作 三角矩阵 总结 栈 栈的基本操作 InitStack(&S):初始化 StackEmpty(S):判空,空则true,非空则false Push(&S,x):入栈 Pop(&S,&x):出栈,并用x返回元素内容 GetTop(S,&x):读栈顶元素 DestroyStack(&S):销毁并释放空间 栈是一种受限的线性表,只允许在一端操作 栈若只能在栈顶操作,则只可能上溢 采用非递归方式重写递归时,不一定要用栈,比如菲波那切数列只要用循

  • C语言编程数据结构的栈和队列

    C语言编程数据结构的栈和队列

    目录 栈 数组实现 标题全部代码 Stack_array.c Stack_array.h 初始化数组栈 满栈后扩容 是否为空栈 压栈和退栈 链表实现 stack_chain.h stack_chain.c 整个压栈流程 整个弹栈流程 出栈情况 队列 队列的实现 queue_chain.h queue_chain.c 一个结构体类型用于维护这个队列 概念流程图 入队列的实现 出队列的实现 是否空队 栈 栈是一种以后进先出为顺序对对象进行添加或删除的数据结构 对栈进行形象记忆就像是桌子上的一堆书或一

  • C语言数据结构进阶之栈和队列的实现

    C语言数据结构进阶之栈和队列的实现

    目录 栈的实现: 一.栈的概念和性质 二.栈的实现思路 三.栈的相关变量内存布局图 四.栈的初始化和销毁 五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空 队列的实现: 一.队列的概念和性质 二.队列的实现思路 三.队列相关变量的内存布局图 四.队列的初始化和销毁 五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空 总结 栈的实现: 一.栈的概念和性质 栈(stack)又名

  • C语言超详细讲解栈与队列实现实例

    C语言超详细讲解栈与队列实现实例

    目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用

  • C语言示例代码讲解栈与队列

    C语言示例代码讲解栈与队列

    目录 栈 栈的定义 顺序栈 顺序栈的定义 顺序栈的初始化 顺序栈的入栈 顺序栈的出栈 取顺序栈的栈顶元素 链栈 队列 队列的定义 队列的顺序表达与实现 队列顺序存储结构 假溢出 循环队列 循环队列的初始化 循环队列的入队 循环队列的出队 链队列 链栈的初始化 链栈的入队 链栈的出队 上文详细的讲解了顺序表与链表的实现,相信大家在顺序表与链表的指基础上,很容易就能学会站和队列,废话不多说,我们马上开始! 栈 栈的定义 栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作 假设栈 [s =

  • JavaScript基于数组实现的栈与队列操作示例

    JavaScript基于数组实现的栈与队列操作示例

    本文实例讲述了JavaScript基于数组实现的栈与队列操作.分享给大家供大家参考,具体如下: 栈数据结构: 1. 后进先出 队列在列表的尾端添加项,从列表的尾端移除项 队列图: 实现代码: var colors = ["red","blue"]; colors.push("brown"); //从队列尾部添加一项 console.log(colors);//[ 'red', 'blue', 'brown' ] var item =colors.

  • C语言编程数据结构栈与队列的全面讲解示例教程

    C语言编程数据结构栈与队列的全面讲解示例教程

    目录 一.栈的表示和实现 1栈的概念和结构 2栈的初始化 3压栈(栈顶插入一个数据) 4出栈(栈顶删除一个数据) 5取栈顶元素 6取栈顶元素 7判断栈是否为空 二.队列的表示和实现 1队列的概念及结构 2队列的实现 3队列初始化 4入队(队尾插入一个数据) 5出队(队头删除一个数据) 6取队头数据 7取队尾数据 8计算队列中数据个数 9判断队列是否为空 10销毁队列 总结 一.栈的表示和实现 1栈的概念和结构 栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作.

随机推荐