一.栈
1.概念：
栈是一种只能从栈顶入，栈顶出的一种数据结构。先进入的后出来（像弹夹一样）
2.实现一个栈
经过分析，我们用顺序表实现栈是最高效的。
（1）头文件声明
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STtype; typedef struct Stark { STtype* a; int top; int capacity; }ST; //初始化 void STInit(ST* ps); //入栈 void STPush(ST* ps,STtype x); //出栈 void STPop(ST* ps); //得到栈顶数据 STtype STTop(ST* ps); //统计栈内元素个数 int STSize(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps); //打印栈 void STPrint(ST* ps); //销毁 void STDestory(ST* ps);
（2）函数实现源文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stark.h" void STInit(ST* ps) { assert(ps); ps->a = (STtype*)malloc(4 * sizeof(STtype)); ps->top = 0; ps->capacity = 4; } void STPush(ST* ps, STtype x) { assert(ps); //增容 if (ps->top == ps->capacity) { STtype* tmp = (STtype*)realloc(ps->a, (ps->capacity + 4) * sizeof(STtype)); if (tmp == NULL) { perror("STpush::realloc"); return; } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STtype 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) { if (ps->top == 0) return true; else return false; } void STPrint(ST* ps) { int i = 0; for (i = ps->top - 1; i >= 0; i--) { printf("%d ", ps->a[i]); } } void STDestory(ST* ps) { free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
（3）测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stark.h" void test1() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); STPop(&st); while (!STEmpty(&st)) { printf("%d", STTop(&st)); STPop(&st); } } int main() { test1(); return 0; }
二.队列
1.概念：
队列是一种队尾入，队头出的数据结构。先进去的先出来。用单链表实现较为高效（头删和尾插）
2.实现一个队列
（1）头文件声明
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType a; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); //队尾入 void QueuePush(Queue* pq, QDataType x); //队头出 void QueuePop(Queue* pq); //取队头数据 QDataType QueueFront(Queue* pq); //取队尾数据 QDataType QueueBack(Queue* pq); //取数据的个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq);
（2）函数实现源文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = NULL; pq->tail = NULL; } //尾插 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("QueuePush::malloc"); return; } //对新开的结点初始化 newnode->a = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = newnode; pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } } //头删 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); //如果只有一个元素，会导致tail被free 变成野指针的问题 if (pq->head->next == NULL) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } //取队头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->a; } //取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->a; } //取数据的个数 int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
（3）测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void test1() { Queue pq; QueueInit(&pq); QueuePush(&pq, 1); QueuePush(&pq, 2); QueuePush(&pq, 3); QueuePush(&pq, 4); QueuePush(&pq, 5); int sz = QueueSize(&pq); while (!QueueEmpty(&pq)) { printf("%d ", QueueFront(&pq)); QueuePop(&pq); } printf("\n%d\n", sz); } int main() { test1(); return 0; }
