网站提交至google,襄阳住房和城乡建设局网站,手机怎么制作图文广告,网站建设1000zhu目录 1.栈
1.1.栈的概念及结构
1.2栈的实现
2.队列
2.1队列的概念及结构
2.2队列的实现 1.栈
1.1.栈的概念及结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶#xff0c;另一端称为…目录 1.栈
1.1.栈的概念及结构
1.2栈的实现
2.队列
2.1队列的概念及结构
2.2队列的实现 1.栈
1.1.栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈出数据也在栈顶。
图源来自天命客 1.2栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 图来自小白苦学 Stack.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int STDataType;
//支持动态增长的栈
typedef struct Stact
{int* a;int top;int capacity;
}ST;
//初始化栈
void STInit(ST*ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,STDataType x);
//出栈
void STPop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//检测栈是否为空如果为空返回非零结果如果不为空返回0
bool STEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
#includeStack.hvoid STInit(ST* ps)
{ps-a (STDataType*)malloc(sizeof(STDataType) * 4);if (ps-a NULL){perror(malloc::fail);return;}ps-top 0; //ps-top0; top是栈顶元素的下一个位置ps-capacity 4; //ps-top-1; top是栈顶元素位置
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * ps-capacity * 2);if (tmp NULL){perror(realloc::fail);return;}ps-a tmp;ps-capacity * 2;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}int STSize(ST* ps)
{return ps-top;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}bool STEmpty(ST* ps)
{return ps-top 0;
}
2.队列
2.1队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。可以抽象理解为左耳进右耳出队列具有先进先出FIFO(First In First Out)入列队进行插入操作一端称为队尾出队列进行删除操作的一端称为队头
(图源长相思979) 2.2队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
(图源weixin_52872520) Queue.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDataType x);void QueuePop(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);Queue.c
#includeQueue.h
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while(cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc::fail);return;}newnode-next NULL;newnode-data x;if (pq-head NULL){assert(pq-tail NULL);pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
