当前位置： 首页 > news >正文

南通专业网站建设公司西安今日头条最新新闻

news 2025/7/31 21:16:23
南通专业网站建设公司,西安今日头条最新新闻,武汉精准营销推广,网站建设销售还能做吗🐇 🔥博客主页： 云曦 📋系列专栏：数据结构 💨吾生也有涯，而知也无涯 💛 感谢大家👍点赞 😋关注📝评论 文章目录 前言一、栈📙1.1 栈…

在这里插入图片描述

🐇

🔥博客主页： 云曦
📋系列专栏：数据结构

💨吾生也有涯，而知也无涯
💛 感谢大家👍点赞 😋关注📝评论

文章目录

  • 前言
  • 一、栈
    • 📙1.1 栈的概念及结构
    • 📙1.2 栈的实现
      • 📜1.2.1 栈的结构
      • 📜1.2.2 初始化栈
      • 📜1.2.3 入栈
      • 📜1.2.4 出栈
      • 📜1.2.5 获取栈顶元素
      • 📜1.2.6 获取栈中有效元素个数
      • 📜1.2.7 检测栈是否为空
      • 📜1.2.8 销毁栈
      • 📜1.2.9 栈所有接口的测试
  • 二、队列
    • 📙2.1 队列的概念及结构
    • 📙2.2 队列的实现
      • 📜2.2.1 队列的结构
      • 📜2.2.2 初始化队列
      • 📜2.2.3 队尾入队列
      • 📜2.2.4 检测队列是否为空
      • 📜2.2.5 队头出队列
      • 📜2.2.6 获取队列头部元素
      • 📜2.2.7 获取队列尾部元素
      • 📜2.2.8 获取队列中有效元素个数
      • 📜2.2.9 销毁队列
      • 📜2.2.10 队列所有接口的测试
  • 完整代码
    • 📙**Stack.h**
    • 📙**Stack.c**
    • 📙**Queue.h**
    • 📙**Queue.c**
    • 📙**test.c**

前言

在上期中我们把双向链表学完了，这期我们要开始新的一章 “栈和队列” 的讲解，栈和队列基本都是拿我们之前所学的顺序表或链表来实现，可谓是新瓶装旧酒，有了对顺序表和链表的认识，实现栈和队列并不是难事!

一、栈

📙1.1 栈的概念及结构

概念：栈也是一种特殊的线性表，其次栈只允许在固定一端插入删除，进行数据插入或删除操作的一端叫作栈顶，另一端为栈底。 栈中的数据元素遵守后进先出LIFO的原则。

  • 压栈：栈插入数据的操作叫作进栈/入栈/压栈，且入数据是在栈顶。
  • 出栈：栈删除数据的操作叫作出栈，出数据也在栈顶。

结构：
栈结构
注意：栈如果用链表实现的话要考虑找前一个节点的问题，因为栈的插入删除都是在栈顶，所以实现栈时推荐用顺序表来实现，因为顺序表在尾部插入数据的代价比较小。

📙1.2 栈的实现

📜1.2.1 栈的结构

既然用顺序表实现那么栈的结构就是顺序表的结构

typedef int STDataType;typedef struct Stack
{int* arr;int top;//栈顶int capacity;//容量
}ST;

📜1.2.2 初始化栈

因为在栈的结构里，插入数据只能在栈顶插入，所有只需要实现一个插入的接口即可，把malloc改到插入接口(push)里即可.

void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}

📜1.2.3 入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//检测容量if (ps->top == ps->capacity){//使用三目操作符来解决扩容问题int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType)*newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity = newcapacity;}//入栈ps->arr[ps->top] = x;ps->top++;
}

需要注意的是：realloc有一个特性，如果传入的参数是NULL，则会像malloc一样开辟一个空间出来，相当于调用了malloc。

📜1.2.4 出栈

出栈很简单让栈顶减1即可。

void STPop(ST* ps)
{assert(ps);//栈为空就不能再删了assert(ps->top > 0);ps->top--;
}

需要注意的是：插入的指针有可能为空或者栈有可能为空，两个情况都要检查一下

📜1.2.5 获取栈顶元素

top是有效数据个数后一个的位置，减1就为栈顶的元素

STDataType STTop(const ST* ps)
{assert(ps);return ps->arr[ps->top-1];
}

📜1.2.6 获取栈中有效元素个数

top就是有效数据的个数，直接返回top即可

int STSize(const ST* ps)
{assert(ps);return ps->top;
}

📜1.2.7 检测栈是否为空

返回top是否等于0,等于返回真，不等于返回假

bool STEmpty(const ST* ps)
{assert(ps);return ps->top == 0;
}

📜1.2.8 销毁栈

注意：这里的销毁指得是把这块空间还给操作系统。

void STDestroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

📜1.2.9 栈所有接口的测试

void TestStack()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);printf("栈的有效元素个数%d\n", STSize(&s));while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}//STPop(&s);printf("\n栈的有效元素个数%d\n", STSize(&s));STDestroy(&s);}

测试1

当栈为空还在删除时：
测试2

二、队列

📙2.1 队列的概念及结构

概念：队列也是一种只允许在一端插入数据，在另外一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO。

  • 入队列：进行插入操作的一端称为队尾。
  • 出队列：进行删除操作的一端称为队头。

结构：
结构图解
注意：队列也能用顺序表和链表实现，但使用链表的结构实现更优一些，因为如果是顺序表的话，头删要挪移数据才能完成，效率比链表低，所以实现队列推荐用链表来实现。

📙2.2 队列的实现

📜2.2.1 队列的结构

既然使用队列实现，那么结构自然是链表的形式。

typedef int QueDataType;typedef struct QueueNode
{QueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* tail;int size;
}Que;

因为是单链表，出队列是头删，入队列是尾插，导致需要一个头指针和尾指针，且单链表计算长度要遍历一遍数组，这样下来：

  1. 要传头和尾的参数
  2. 计算链表长度要遍历链表，复杂度为O(N)
  • 不如直接把头尾指针和定义一个存储链表元素个数的变量整合为一个结构体这样就方便多了

📜2.2.2 初始化队列

void QueueInit(Que* pq)
{pq->phead = NULL;pq->tail = NULL;pq->size = 0;
}

只有一个插入的接口，那么就直接在插入接口获取节点就行。

📜2.2.3 队尾入队列

首先获取并初始化节点，然后就是尾插，尾插分为两种情况：

  1. 链表为空，特殊处理。
  2. 链表不为空，正常尾插。
void QueuePush(Que* pq, QueDataType x)
{//获取并初始化节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("newnode fail");exit(-1);}newnode->data = x;newnode->next = NULL;//入队列if (pq->phead == NULL){//链表为空pq->phead = newnode;pq->tail = newnode;}else{//链表不为空pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

📜2.2.4 检测队列是否为空

直接返回pq->phead == NULL，等于返回真，不等于返回假

bool QueueEmpty(Que* pq)
{assert(pq);return pq->phead == NULL;
}

📜2.2.5 队头出队列

单链表头删很简单，但要注意：链表为空时，不能再删了，否则会出问题

void QueuePop(Que* pq)
{assert(pq);//检测链表是否为空，为空就不能再删了assert(!QueueEmpty(pq));//出队列QNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;pq->size--;
}

📜2.2.6 获取队列头部元素

phead指向的就是头节点,返回头节点的元素即可，但要注意：链表有可能为空，所以要检测一下

QueDataType QueueFront(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq->phead->data;
}

📜2.2.7 获取队列尾部元素

tail指向的就是尾节点，直接返回尾节点的元素即可，但要注意：链表有可能为空，所以要检测一下

QueDataType QueueBack(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq->tail->data;
}

📜2.2.8 获取队列中有效元素个数

size存储的就是队列的有效元素个数，返回size即可。

int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

📜2.2.9 销毁队列

  • 这里的销毁指的也是把这片空间还给操作系统
  • 遍历一遍队列，记录下一个节点的位置，释放掉当前节点，最后将头尾指针置空，size置为0即可。
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* Next = cur->next;free(cur);cur = Next;}pq->phead = NULL;pq->tail = NULL;pq->size = 0;
}

📜2.2.10 队列所有接口的测试

TestQueue()
{Que obj;QueueInit(&obj);QueuePush(&obj, 1);QueuePush(&obj, 2);QueuePush(&obj, 3);QueuePush(&obj, 4);QueuePush(&obj, 5);printf("队尾元素：%d\n", QueueBack(&obj));printf("队列的有效数据个数：%d\n", QueueSize(&obj));while (!QueueEmpty(&obj)){printf("%d ", QueueFront(&obj));QueuePop(&obj);}//QueuePop(&obj);printf("\n队列的有效数据个数：%d\n", QueueSize(&obj));QueueDestroy(&obj);
}

测试1

当队列为空还在删时：
测试2

完整代码

*

《栈》

📙Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//栈
typedef int STDataType;typedef struct Stack
{int* arr;int top;//栈顶int capacity;//容量
}ST;//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(const ST* ps);
//获取栈中有效元素的个数
int STSize(const ST* ps);
//检测栈是否为空
bool STEmpty(const ST* ps);
//销毁栈
void STDestroy(ST* ps);

📙Stack.c

#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);//检测容量if (ps->top == ps->capacity){//使用三目操作符来解决扩容问题int newcapacity = ps->capacit==0 ? 4 : ps->capacity*2;STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType)*newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity = newcapacity;}//入栈ps->arr[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);//栈为空就不能再删了assert(ps->top > 0);ps->top--;
}STDataType STTop(const ST* ps)
{assert(ps);return ps->arr[ps->top-1];
}int STSize(const ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(const ST* ps)
{assert(ps);return ps->top == 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

*

《队列》

📙Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//队列
typedef int QueDataType;typedef struct QueueNode
{QueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* tail;int size;
}Que;//初始化队列
void QueueInit(Que* pq);
//入队列
void QueuePush(Que* pq, QueDataType x);
//检测队列是否为空
bool QueueEmpty(Que* pq);
//出队列
void QueuePop(Que* pq);
//获取队列头部元素
QueDataType QueueFront(Que* pq);
//获取队列尾部元素
QueDataType QueueBack(Que* pq);
//获取队列中有效元素的个数
int QueueSize(Que* pq);
//销毁队列
void QueueDestroy(Que* pq);

📙Queue.c

#include"Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->phead = NULL;pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QueDataType x)
{assert(pq);//获取并初始化节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("newnode fail");exit(-1);}newnode->data = x;newnode->next = NULL;//入队列if (pq->phead == NULL){//链表为空pq->phead = newnode;pq->tail = newnode;}else{//链表不为空pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->phead == NULL;
}void QueuePop(Que* pq)
{assert(pq);//检测链表是否为空，为空就不能再删了assert(!QueueEmpty(pq));//出队列QNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;pq->size--;
}QueDataType QueueFront(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq->phead->data;
}QueDataType QueueBack(Que* pq)
{assert(pq);//检测链表是否为空assert(!QueueEmpty(pq));return pq->tail->data;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* Next = cur->next;free(cur);cur = Next;}pq->phead = NULL;pq->tail = NULL;pq->size = 0;
}

*

《测试》

📙test.c

#include"Stack.h"
#include"Queue.h"void TestStack()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);printf("栈的有效元素个数%d\n", STSize(&s));while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}//STPop(&s);printf("\n栈的有效元素个数%d\n", STSize(&s));STDestroy(&s);}TestQueue()
{Que obj;QueueInit(&obj);QueuePush(&obj, 1);QueuePush(&obj, 2);QueuePush(&obj, 3);QueuePush(&obj, 4);QueuePush(&obj, 5);printf("队尾元素：%d\n", QueueBack(&obj));printf("队列的有效数据个数：%d\n", QueueSize(&obj));while (!QueueEmpty(&obj)){printf("%d ", QueueFront(&obj));QueuePop(&obj);}//QueuePop(&obj);printf("\n队列的有效数据个数：%d\n", QueueSize(&obj));QueueDestroy(&obj);
}int main()
{TestStack();TestQueue();return 0;
}
http://www.yidumall.com/news/21647.html

相关文章：

  • 微企免费做网站广州seo托管
  • 专业的网站服务公司百度的网页地址
  • 装修设计公司网站有哪些百度查关键词显示排名
  • linx服务器怎么做网站网络广告推广
  • 网站建设方案书备案电商网
  • 济南济阳哪有做网站的seo优化流程
  • dede免费手机网站模板seo排名培训
  • 外国做ppt的网站怎么注册中视频账号
  • 漳州北京网站建设珠海seo推广
  • 清远市清城区网站建设公司石家庄百度快照优化排名
  • 在线做字网站公司广告推广方案
  • 睢宁做网站公司营销培训机构哪家最专业
  • 世界军事新闻视频深圳网站优化
  • 江苏林润建设工程有限公司网站sem是什么?
  • 南通网站建设规划网页制作的步骤
  • 福建省鑫通建设有限公司网站关键词林俊杰在线听免费
  • 大庆做网站公司张家界百度seo
  • 做网站前端有前途么？上海关键词排名优化价格
  • 网站域名的作用新东方教育机构官网
  • jsp做物流网站女排联赛最新排行榜
  • 网站 域名 空间 服务器四年级2023新闻摘抄
  • 做视频网站教程网络推广营销方案100例
  • 截图京东图片做网站杭州网站建设 seo
  • 丰联汽配网站建设成本北京seo顾问推推蛙
  • 服务平台名称网站优化seo培
  • 网站域名可以更换吗关键词点击工具
  • 做指甲的网站叫什么名字来着百度seo刷排名工具
  • 湖北移动网站建设怎么做网站推广和宣传
  • wordpress.org建站杭州推广公司
  • 昌吉市建设局网站谷歌搜索引擎入口363