当前位置: 首页> 房产> 政策 > 摄影网站开题报告_全球设计网络芯片的公司_种子库_免费建一个自己的网站

摄影网站开题报告_全球设计网络芯片的公司_种子库_免费建一个自己的网站

时间:2025/7/11 15:39:02来源:https://blog.csdn.net/2401_84538476/article/details/142562908 浏览次数:1次
摄影网站开题报告_全球设计网络芯片的公司_种子库_免费建一个自己的网站

【数据结构】栈和队列(vs)

前言:

栈和队列是两种重要的线性结构。本章讨论栈和队列的定义、表示方法。这里栈和队列分别用数组实现和链表实现(这里所说是实现的底层逻辑分别是数组结构和链表结构)

一、栈

1.1概念与结构

栈是一种特殊的线性表,只允许在固定的一端进行插入和删除操作,进行数据插入和删除的一端称为栈顶和栈底。(可得出,栈是先进后出LIFO)

压栈:栈的插入操作,入数据在栈顶

出栈:栈的删除操作,出数据也在栈顶

在这里插入图片描述

1.2用数组的结构实现栈(vs):

头文件:stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* arr;int top;//元素个数int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);//判空
bool STEmpty(ST*ps);//入栈&出栈
void STPush(ST* ps, STDatatype x);
void STpop(ST* ps);//取栈顶元素
STDatatype StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);

实现栈的基本功能:初始化栈、入栈和出栈、获取栈的元素、销毁栈等:

  • 初始化:创建一个空栈,设置栈顶指针为初始化状态。
void STInit(ST* ps)
{assert(ps);ps-> arr = NULL;ps->top = ps->capacity = 0;
}
  • 栈的销毁:将栈顶指针恢复到初始状态,释放栈中所有元素占用的空间。
void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}
  • 入栈和出栈:
void STPush(ST* ps, STDatatype x)
{assert(ps);//看空间是否足够,不够就申请if (ps->capacity == ps->top){int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;STDatatype* tmp = (STDatatype*)realloc(ps->arr, sizeof(STDatatype) * newCapacity);if (tmp == NULL){perror("reallloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;}
//这里是判空操作
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));--ps->top;
}
  • 获取栈顶的元素:可在不删除栈顶元素的情况下,返回栈顶元素的值。获取元素个数,直接取ps->top。
//获取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}
//获取元素个数
int STSize(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->top;
}

二、队列

2.1概念与结构

概念:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,具有先进先出特点。

入队列:进行插入操作的一端称为队尾。

出队列:进行删除操作的一端称为队头。

在这里插入图片描述

队列的底层结构

2.2用链表结构实现队列(vs):

头文件:Queue.h

//定义队列节点的结构.
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;int size;//保存队列有效数据个数..
}Queue;//初始化.
void QueueInit(Queue* pq);//入队列,从队尾
void QueuePush(Queue* pq, QDataType x);//队列判空.
bool QueueEmpty(Queue* pq);//出队列,从队头
void QueuePop(Queue* pq);//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

实现队列的基本操作:初始化、出入队列操作、获取队列的长度、销毁队列。

  • 初始化队列,创建一个空的队列、设置队头指针和队尾指针为初始状态。
//初始化.
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
  • 入队列:将元素插到队尾,若队列为空,则将插入的数据作为初始的队头队尾指针元素,若不为空,则将队尾指针更新指向新插入的元素。

//入队列,队尾.
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请一个新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}
  • 出队列:首先先判空,若队列为空,无法进行出队操作,通常会返回一个特定的错误值或进行错误处理;若队列中只有一个元素,删除该元素后,队头指针和队尾指针都恢复到初始状态;若有多个元素,删除队头元素后,队头指针指向下一个指针。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//出队列,队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}
  • 取队头队尾数据:首先判空,若队列为空,则不再执行下面的代码。
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾元素
QDataType QUeueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
  • 获取队列有效元素个数:这里用的是链表结构实现队列,所以直接取元素个数就可以了。
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
  • 销毁队列:将队头队尾指针恢复到初始状态,释放队列中所有元素占用的内存。
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
关键字:摄影网站开题报告_全球设计网络芯片的公司_种子库_免费建一个自己的网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: