如何注册网站卖东西,网站服务合同范本,成都软件网站开发,网业小游戏在线玩目录
栈#xff1a;
栈的概念#xff1a;
栈的实现#xff1a;
栈接口的实现#xff1a;
1.初始化栈#xff1a;
2.入栈#xff1a;
3.出栈#xff1a;
4. 获取栈顶元素#xff1a;
5.获取栈中有效数据的个数#xff1a; 6.检测栈是否为空#xff0c;如果为…目录
栈
栈的概念
栈的实现
栈接口的实现
1.初始化栈
2.入栈
3.出栈
4. 获取栈顶元素
5.获取栈中有效数据的个数 6.检测栈是否为空如果为空返回非零结果如果不为空返回0 7.销毁栈
队列
队列的概念
队列的实现
接口的实现
1.初始化队列
2. 队尾入队列
3.队头出队列
4.获取队列头部元素 5.获取队列尾元素
6.获取队列中有效数据个数
7.检测队列是否为空如果为空返回非零结果如果非空返回0
8.销毁队列 栈
栈的概念
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵循先进先出LIFO(Last In First Out)的原则
压栈栈的插入操作叫做进栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 C语言单链表-CSDN博客 C语言实现顺序表(增,删,改,查)-CSDN博客 0基础小白学C语言看这一篇就够了(C语言详讲万字)_用c设计一个程序,实现输入任意一个数(不大于10的5次方),计算从1加到这个数-CSDN博客
栈接口的实现
栈和顺序表一样可以做成动态的也可以做成静态的因为静态的一般是用在那种给定长度的地方所以这里使用动态的实现栈。
实现之前我们需要各个文件分别是头文件Stack.h以及两个源文件Stack.c和Test.c他们的作用如下:
Stack.h栈的结构体头文件引用接口函数的声明。Stack.c接口函数的实现。Test.c测试各个函数的功能。
如下我们先来展示各种接口的声明Stack.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDataType;
typedef struct Stack {STDataType*a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST*ps,STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);int STSize(ST* ps);
bool STEmpty(ST* ps);
1.初始化栈
把传递进来的第一个栈的置空和值为0
void STInit(ST* ps) {assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}
2.入栈
入栈之前判断栈的大小是否足够如果足够那么直接将数据存入对应的位置然后有效值就行如果空间不够那么需要扩容如果扩容失败直接报错误信息。
void STPush(ST* ps, STDataType x) {assert(ps);if (ps-topps-capacity) {int newCapacity ps-capacity * 2 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmpNULL) {perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps - top;
}
3.出栈
首先断言以下以免出现栈都没有还在出栈然后有效数据减减就行了。
void STPop(ST* ps) {assert(ps);assert(ps-top 0);--ps-top;
}
4. 获取栈顶元素
直接返回数据没啥好说的。
STDataType STTop(ST* ps) {assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
5.获取栈中有效数据的个数
直接返回栈顶元素。
int STSize(ST* ps) {assert(ps);return ps-top;
} 6.检测栈是否为空如果为空返回非零结果如果不为空返回0
返回类型是一个布尔型也就是不是false就是true。
bool STEmpty(ST* ps) {assert(ps);return ps-top 0;
} 7.销毁栈
把栈释放之后然后把指针置空值值为0.
void STDestroy(ST* ps) {assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity0;
}如下是全代码的示例Stack.c:
#includeStack.hvoid STInit(ST* ps) {assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}
void STDestroy(ST* ps) {assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity0;
}void STPush(ST* ps, STDataType x) {assert(ps);if (ps-topps-capacity) {int newCapacity ps-capacity * 2 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmpNULL) {perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps - top;
}void STPop(ST* ps) {assert(ps);assert(ps-top 0);--ps-top;
}
STDataType STTop(ST* ps) {assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
int STSize(ST* ps) {assert(ps);return ps-top;
}
bool STEmpty(ST* ps) {assert(ps);return ps-top 0;
}
如下我们用Test.c文件测试整个代码运行是否正常:
#includeStack.hvoid TestStack1() {ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);while (!STEmpty(st)) {printf(%d ,STTop(st));STPop(st);}printf(\n); STDestroy(st);
}
int main() {TestStack1();return 0;
} 队列
队列的概念
队列只允许一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列进入插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。 队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 接口的实现
我们首先创建一个头文件Queue.h和两个源文件分别是Queue.c跟Test.c他们的作用为:
Queue.h:头文件的引用接口函数的声明以及栈的结构体。Queue.c:接口的实现。Test.c测试每个接口。
如下代码是Queue.h中所有接口以及头文件引用的代码
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int QDataType;
typedef struct QueueNode {struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue {QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que*pq,QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* p);
1.初始化队列
把拿到的头指针和尾指针置空然后把其值置为0...
void QueueInit(Que* pq) {assert(pq);pq-head pq-tail NULL;pq-size 0;
}2. 队尾入队列
先使用malloc创建出一个队列然后判断创建是否成功如若成功执行下列代码首先把指针置空然后给数据赋值最后判断一下是第几个元素如果是第一个那么直接让头指针和尾指针都指向它即可如果不是那么需要改变尾指针的指向然后有效数据加加。
void QueuePush(Que* pq, QDataType x) {assert(pq);QNode* newnode malloc(sizeof(QNode));if (newnode NULL) {perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tailNULL) {pq-head pq-tail newnode;}else {pq-tail-next newnode;pq-tail newnode;}pq-size;
}
3.队头出队列
出数据大致原理就是保存第一个然后让头指针指向下一个然后再把之前那个释放了最后有效数据个数减减即可。
void QueuePop(Que* pq) {assert(pq);assert(!QueueEmpty(pq));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--;
}
4.获取队列头部元素
队头有一个指针head直接拿取即可。
QDataType QueueFront(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
} 5.获取队列尾元素
队尾有一个指针也就是tail直接拿取即可。
QDataType QueueBack(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
6.获取队列中有效数据个数
直接拿取有效数据size即可。
int QueueSize(Que* pq) {assert(pq);return pq-size;
}7.检测队列是否为空如果为空返回非零结果如果非空返回0
首先断言返回时是一个表达式用来判断是否是真还是假。
bool QueueEmpty(Que* pq) {assert(pq);return pq-head NULL;
}
8.销毁队列
使用循环从队列的头部一直释放即可最后把传进来的pq指针置空。
void QueueDestroy(Que* 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;
}
下列是队列接口实现的全部代码Queue.c中的
#includeQueue.hvoid QueueInit(Que* pq) {assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* 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(Que* pq, QDataType x) {assert(pq);QNode* newnode malloc(sizeof(QNode));if (newnode NULL) {perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tailNULL) {pq-head pq-tail newnode;}else {pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Que* pq) {assert(pq);assert(!QueueEmpty(pq));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--;
}
QDataType QueueFront(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}bool QueueEmpty(Que* pq) {assert(pq);return pq-head NULL;
}
int QueueSize(Que* pq) {assert(pq);return pq-size;
}
然后test.c测试代码是否能够正常运行:
#includeQueue.hvoid TestQueue() {Que q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);while (!QueueEmpty(q)) {printf(%d , QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);
}int main() {TestQueue();
}
