网络推广机构,网站优化分析软件,注册深圳公司新政策,电脑系统重装wordpress#x1f497;个人主页#x1f497; ⭐个人专栏——数据结构学习⭐ #x1f4ab;点击关注#x1f929;一起学习C语言#x1f4af;#x1f4ab; 目录 导读#xff1a;一、 栈1. 栈的概念及结构2. 栈的实现3. 实现代码3.1 定义结构体3.2 初始化栈3.3 销毁栈3.4 入栈3.5 出栈… 个人主页 ⭐个人专栏——数据结构学习⭐ 点击关注一起学习C语言 目录 导读一、 栈1. 栈的概念及结构2. 栈的实现3. 实现代码3.1 定义结构体3.2 初始化栈3.3 销毁栈3.4 入栈3.5 出栈3.6 获取栈顶元素3.7 检测栈是否为空3.8 获取栈中有效元素个数 4. 代码整理4.1 **Stack.h**4.2 Stack.c4.3 study.c 二、队列1. 队列的概念及结构2. 队列的实现3. 实现代码3.1 定义结构体3.2 初始化队列3.3 销毁队列3.4 队尾入队列3.5 队头出队列3. 6 获取队列头部元素3.7 获取队列队尾元素3.8 检测队列是否为空3.9 获取队列中有效元素个数 4. 代码整理4.1 **Queue.h**4.2 Queue.c4.3 study.c 导读
我们在前面学习了单链表和顺序表今天我们来学习栈和队列。 栈和队列相对于单链表和顺序表来说是较为简单的之后我们再深入学习双链表。关注博主或是订阅专栏掌握第一消息。
一、 栈
1. 栈的概念及结构
栈(Stack)是一种只能在一端进行插入和删除操作的线性数据结构该端被称为栈顶(Top)另一端被称为栈底(Bottom)。 栈的特点是后进先出(Last In First Out, LIFO)即最后放入栈中的元素最先被弹出。栈中的元素可以是任意类型但栈顶永远只能是一个元素。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 2. 栈的实现
栈可以用数组或链表来实现常见应用场景包括函数调用、表达式求值、括号匹配、逆序输出等。 相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。 其基本操作包括 push(x): 将元素x压入栈顶。 pop(): 弹出栈顶元素并返回其值。 top(): 返回栈顶元素的值但不弹出。 empty():判断栈是否为空。 3. 实现代码
我们需要创建两个 C文件: study.c 和 Stack.c以及一个 头文件 Stack.h。 头文件来声明函数一个C文件来定义函数另外一个C文件来用于主函数main进行测试。 3.1 定义结构体
typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。 若struct Stack {}这样来定义结构体的话。在申请Stack 的变量时需要这样写struct Stack n; 若用typedef可以这样写typedef struct Stack{}ST; 。在申请变量时就可以这样写ST n; 区别就在于使用时是否可以省去struct这个关键字。 Stack.h
typedef struct Stack
{STDataType* a;int top; //标识栈顶的位置int capacity;
}ST;3.2 初始化栈
Stack.h 声明函数
// 初始化栈
void STInit(ST* pst);Stack.c 定义函数
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;pst-capacity 0;
}3.3 销毁栈
动态内存空间开辟使用完之后需要进行销毁。 Stack.h 声明函数
// 销毁
void STDestroy(ST* pst);Stack.c 定义函数
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;
}3.4 入栈
我们在顺序表和单向链表里都另定义一个函数来进行空间的开辟这样我们在其它的函数中有开辟空间的需要只用调用即可而无需再去写一次开辟空间的代码。但是在栈中我们只有在入栈的函数中需要进行空间的开辟所有不用再单独写一个函数。 Stack.h 声明函数
// 入栈
void STPush(ST* pst, STDataType x);Stack.c 定义函数 void STPush(ST* pst, STDataType x)
{assert(pst);// 检查空间如果满了进行增容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}//如果开辟成功则重新赋给原来的数组指针pst-a tmp;pst-capacity newcapacity;}//栈顶从0开始可以作为数组的下标来进行插入数据pst-a[pst-top] x;pst-top;
}3.5 出栈
后进先出原则最后进来的数据先出。 Stack.h 声明函数
// 出栈
void STPop(ST* pst);Stack.c 定义函数
// 出栈
void STPop(ST* pst)
{assert(pst);//top大于0栈里面有数据才能删除数据assert(pst-top 0);//直接让top--不让访问即可pst-top--;
}3.6 获取栈顶元素
栈并不能像打印数组那样把数据全部打印出来只能获取到栈顶的元素想要获取其它数据就只能先把其它的数据给删除也就是出栈。 Stack.h 声明函数
// 获取栈顶元素
STDataType STTop(ST* pst);Stack.c 定义函数
// 获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);//top-1即是栈顶元素return pst-a[pst-top - 1];
}3.7 检测栈是否为空
Stack.h 声明函数
// 检测栈是否为空如果为空返回true如果不为空返回false
bool STEmpty(ST* pst);Stack.c 定义函数
// 检测栈是否为空如果为空返回true如果不为空返回false
bool STEmpty(ST* pst)
{assert(pst);//如果表达式成立则为真return pst-top 0;
}3.8 获取栈中有效元素个数
Stack.h 声明函数
// 获取栈中有效元素个数
int STSize(ST* pst);Stack.c 定义函数
//获取栈中有效元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}4. 代码整理
4.1 Stack.h
#pragma once
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h
typedef int STDataType;typedef struct Stack
{STDataType* a;int top; //标识栈顶的位置int capacity;
}ST;// 初始化栈
void STInit(ST* pst);// 销毁
void STDestroy(ST* pst);// 入栈
void STPush(ST* pst, STDataType x);// 出栈
void STPop(ST* pst);// 获取栈顶元素
STDataType STTop(ST* pst);// 检测栈是否为空如果为空返回true如果不为空返回false
bool STEmpty(ST* pst);// 获取栈中有效元素个数
int STSize(ST* pst);4.2 Stack.c
#include Stack.h//初始化栈
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;pst-capacity 0;
}// 销毁栈
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;
}// 入栈
void STPush(ST* pst, STDataType x)
{assert(pst);// 检查空间如果满了进行增容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}//如果开辟成功则重新赋给原来的数组指针pst-a tmp;pst-capacity newcapacity;}//栈顶从0开始可以作为数组的下标来进行插入数据pst-a[pst-top] x;pst-top;
}// 出栈
void STPop(ST* pst)
{assert(pst);//top大于0栈里面有数据才能删除数据assert(pst-top 0);//直接让top--有效数据减一即可pst-top--;
}// 获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);//top-1即是栈顶元素return pst-a[pst-top - 1];
}// 检测栈是否为空如果为空返回true如果不为空返回false
bool STEmpty(ST* pst)
{assert(pst);//如果表达式成立则为真return pst-top 0;
}//获取栈中有效元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}4.3 study.c
#include Stack.hvoid TestST1()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);printf(%d\n, STTop(s));//一 对 多//入栈顺序 -- 出栈顺序while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);STDestroy(s);
}
int main()
{TestST1();return 0;
}二、队列
1. 队列的概念及结构
队列是一种线性的数据结构它可以存储一系列数据其中第一个添加的数据会被第一个删除也就是先进先出FIFO的原则。 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 2. 队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 队列通常有两个指针一个是front指针指向队列的第一个元素另一个是rear指针指向队列的最后一个元素。当一个新元素进入队列时它被插入到rear指针所指向的位置当一个元素从队列中删除时它会从front指针所指向的位置被删除。 3. 实现代码
我们需要创建两个 C文件: study.c 和 Queue.c以及一个 头文件 Queue.h。 头文件来声明函数一个C文件来定义函数另外一个C文件来用于主函数main进行测试。 3.1 定义结构体
定义了一个链式队列的数据结构。 包含了两个结构体 QNode结构体表示队列中的一个节点包含一个整数数据成员val和指向下一个节点的指针next。 Queue结构体表示一个队列包含指向队头和队尾节点的指针phead和ptail以及队列的大小size。 这个队列是通过链式结构实现的即每个节点都包含一个指向下一个节点的指针。队列的头指针phead指向队列的第一个节点而队列的尾指针ptail指向队列的最后一个节点。 链式队列的优点是可以动态地增加和减少队列的大小而不需要像顺序队列那样预留一定的空间。缺点是每个节点都需要额外的指针空间来指向下一个节点因此相对于顺序队列会占用更多的存储空间。 Queue.h
// 链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;// 队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;3.2 初始化队列
Queue.h
// 初始化队列
void QueueInit(Queue* pq);Queue.c
void QueueInit(Queue* pq)
{pq-phead NULL;pq-ptail NULL;pq-size 0;
}3.3 销毁队列
Queue.h
// 销毁队列
void QueueDestroy(Queue* pq);Queue.c
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead-next;while (cur){free(pq-phead);pq-phead cur;cur cur-next;}cur NULL;pq-phead NULL;pq-ptail NULL;pq-size 0;
}3.4 队尾入队列
Queue.h
// 队尾入队列
void QueuePush(Queue* pq, QDataType x);Queue.c
void QueuePush(Queue* pq, QDataType x)
{//开辟新空间QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}3.5 队头出队列
Queue.h
// 队头出队列
void QueuePop(Queue* pq);Queue.c
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* tmp pq-phead;pq-phead pq-phead-next;free(tmp);tmp NULL;if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}3. 6 获取队列头部元素
Queue.h
// 获取队列头部元素
QDataType QueueFront(Queue* pq);Queue.c
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}3.7 获取队列队尾元素
Queue.h
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);Queue.c
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}3.8 检测队列是否为空
Queue.h
// 检测队列是否为空如果为空返回true如果非空返回false
bool QueueEmpty(Queue* pq);Queue.c
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
3.9 获取队列中有效元素个数
Queue.h
// 获取队列中有效元素个数
int QueueSize(Queue* pq);Queue.c
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}4. 代码整理
4.1 Queue.h
#pragma once
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h// 链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;// 队列的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);// 销毁队列
void QueueDestroy(Queue* pq);// 队尾入队列
void QueuePush(Queue* pq, QDataType x);// 队头出队列
void QueuePop(Queue* pq);// 获取队列头部元素
QDataType QueueFront(Queue* pq);// 获取队列队尾元素
QDataType QueueBack(Queue* pq);// 检测队列是否为空如果为空返回true如果非空返回false
bool QueueEmpty(Queue* pq);// 获取队列中有效元素个数
int QueueSize(Queue* pq);4.2 Queue.c
#include Queue.h// 初始化队列
void QueueInit(Queue* pq)
{pq-phead NULL;pq-ptail NULL;pq-size 0;
}// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead-next;while (cur){free(pq-phead);pq-phead cur;cur cur-next;}cur NULL;pq-phead NULL;pq-ptail NULL;pq-size 0;
}// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* tmp pq-phead;pq-phead pq-phead-next;free(tmp);tmp NULL;if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}// 检测队列是否为空如果为空返回true如果非空返回false
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}4.3 study.c
#include Queue.hvoid TestQ1()
{Queue s;QueueInit(s);QueuePush(s, 1);QueuePush(s, 2);QueuePush(s, 3);QueuePush(s, 4);QueuePush(s, 5);printf(%d , QueueFront(s));printf(%d , QueueBack(s));printf(%d\n, QueueSize(s));QueuePop(s);QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));if (!QueueEmpty(s)){QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));}QueueDestroy(s);printf(%d\n, QueueSize(s));}
int main()
{TestQ1();return 0;
}
