目录
一、栈
介绍
初始准备
栈的初始化与销毁
栈为空
进栈与出栈
栈的有效数据个数
栈顶的数据
全部代码
二、队列
介绍
初始准备
队列的初始化与销毁
队列为空
进队列与出队列
队列的有效数据个数
队头和队尾的数据
全部代码
一、栈
介绍
栈是一种线性结构，类似于链表和顺序表，但也有它的独特之处，只能栈顶入，栈顶出，所以栈也是“先进后出”或者“后进先出”
栈能采用链式结构也能采用数组结构来实现，这里采用数组结构
链式结构
采用单链表，头作栈顶，头插入数据，头删出数据
采用带头双链表，尾作栈顶，尾插入数据，尾删出数据
数组结构
尾部作栈顶，头部作栈底，尾插入数据，尾删出数据
初始准备
为了使存储的数据类型不固定，能够在存储其它类型数据时容易修改，所以用typedef修改类型名
然后得建立一个结构体，有三个成员，一个是动态数组的起始地址(指针)，另一个是栈顶变量，用来取出栈顶数据、判断是否还有空间时使用和有效数据个数，还有一个是数组容量
用typedef将其类型名修改，使其简洁方便使用
栈的初始化与销毁
将其三个成员初始化，指针置空，其余两个置为0即可
销毁栈时，和初始化栈类似，只是多加了个free来释放空间，放置内存泄漏
栈为空
这里采用bool类型，判断栈是否为空，为真就是空，为假就是有数据
注意：在C中使用bool类型要引用头文件stdbool.h
进栈与出栈
入数据得先判断是否有空间，没有就增容，一般是扩为原来的2倍，避免频繁扩容
然后再添加数据
删除数据时，得先判断栈是否为空，否则一直出，就容易出错，采用断言较好
栈的有效数据个数
有效数据就是top的大小，因为top从0开始，每次添加数据就+1
栈顶的数据
取出栈顶数据时，得先判断栈是否为空，采用断言较好
由于有效数据个数比其下标大1，所以要-1
全部代码
//头文件 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>
#include<stdbool.h> typedef int DataType; typedef struct Stack { DataType* a;
int top; int capacity; }ST; //初始化栈 void STInit(ST* ps); //入栈 void STPushTop(ST*
ps, DataType x); //出栈 void STPopTop(ST* ps); //栈顶数据 DataType STTop(ST* ps);
//有效数据个数 int STDataSize(ST* ps); //销毁栈 void STDestroy(ST* ps); //栈为空 bool
STEmpty(ST* ps); //定义文件 #include"Stack.h" void STInit(ST* ps) { assert(ps);
ps->a = NULL; ps->top = 0; ps->capacity = 0; } void STPushTop(ST* ps, DataType
x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity
== 0 ? 4 : 2 * ps->capacity; DataType* ptr = (DataType*)realloc(ps->a,
sizeof(DataType) * newcapacity); if (ptr == NULL) { printf("realloc fail\n");
exit(-1); } ps->a = ptr; ps->capacity = newcapacity; } ps->a[ps->top] = x;
ps->top++; } void STPopTop(ST* ps) { assert(ps); assert(!STEmpty(ps));
ps->top--; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } DataType
STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->top - 1]; }
int STDataSize(ST* ps) { assert(ps); return ps->top; } void STDestroy(ST* ps) {
assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //测试文件
#include"Stack.h" void test1() { ST st; STInit(&st); STPushTop(&st, 1);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 2);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 3);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 4);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 5);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 6);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STDestroy(&st); } void
test2() { ST st; STInit(&st); STPushTop(&st, 1); STPushTop(&st, 2);
STPushTop(&st, 3); STPushTop(&st, 4); printf("%d\n", STTop(&st));
STDestroy(&st); } int main() { test1(); //test2(); return 0; }
二、队列
介绍
队列也是一种线性结构，类似于链表和顺序表，但也有它的独特之处，只能队尾入，队头出，所以队列也是“先进先出”或者“后进后出”
由于用数组结构实现队列不太方便，效率不高，无论是数组开头作队头，还是数组尾作队头，都要挪动数据
数组开头作队头，数组尾作队尾，入数据方便，但得从数组开头出数据，即头删，需要往前挪动数据，比较麻烦
数组开头作队尾，数组尾作队头，入数据得从数组开头入，即头插，需要往后挪动数据，很麻烦，出数据方便
所以采用链式结构较好，这里采用单链表实现
初始准备
为了使存储的数据类型不固定，能够在存储其它类型数据时容易修改，所以用typedef修改类型名
然后得创建一个结构体，有2个成员，一个用来存储数据，另一个用来存储下一个数据的地址
为了方便进队列和出队列，所以定义了两个指针，一个指向头节点，另一个指向尾节点，用结构体的形式将二者封装在一起
队列的初始化与销毁
将第二个结构体的两个指针置为空即可
销毁队列时，得从头节点遍历，一个一个用free释放，最后再将头指针和尾指针置空即可
队列为空
判断队列是否为空，只需判断头指针是否为空即可，依然采用bool类型
进队列与出队列
入数据进队列时，得先用malloc开辟空间，然后进行判断是否开辟成功，再然后就是对其成员赋值，得分两种情况
第一种是第一次入数据进队列，直接作头节点
第二种则是在队列尾后链接节点
出数据时也得考虑队列是否为空，不能一直出数据，否则取数据时会出现随机值，采用断言判断
出数据时还得考虑一种情况，就是删除最后一个数据时，得将尾指针置空，要不然会出现野指针
队列的有效数据个数
由于队列是单链表实现的，所以只能采用从头节点开始遍历计数的方法
队头和队尾的数据
由于已经定义了头和尾两个指针，所以直接访问即可，只是要判断队列是否为空
全部代码
//头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h>
#include<stdbool.h> typedef int DataType; typedef struct QueueNode { DataType
data; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode*
head; QueueNode* tail; }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void
QueueDestroy(Queue* pq); //尾部插入 void QueuePushBack(Queue* pq, DataType x);
//头部删除 void QueuePopFront(Queue* pq); //头部数据 DataType QueueTop(Queue* pq);
//尾部数据 DataType QueueTail(Queue* pq); //队列为空 bool QueueEmpty(Queue* pq);
//链表数据个数 int QueueSize(Queue* pq); //定义文件 #include"Queue.h" void
QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void
QueuePushBack(Queue* pq, DataType x) { assert(pq); QueueNode* newnode =
(QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc
fail\n"); exit(-1); } newnode->next = NULL; newnode->data = x; if (pq->head ==
NULL) { pq->head = newnode; pq->tail = pq->head; } else { pq->tail->next =
newnode; pq->tail = newnode; } } void QueuePopFront(Queue* pq) { assert(pq);
assert(!QueueEmpty(pq)); QueueNode* Next = pq->head->next; if (pq->head ==
pq->tail) { pq->tail = NULL; } free(pq->head); pq->head = Next; } bool
QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } DataType
QueueTop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return
pq->head->data; } DataType QueueTail(Queue* pq) { assert(pq);
assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) {
assert(pq); QueueNode* cur = pq->head; int count = 0; while (cur) { count++;
cur = cur->next; } return count; } void QueueDestroy(Queue* pq) { assert(pq);
QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next;
free(cur); cur = next; } pq->head = NULL; pq->tail = NULL; } //测试文件
#include"Queue.h" void test1() { Queue q; QueueInit(&q); QueuePushBack(&q, 1);
QueuePushBack(&q, 2); QueuePushBack(&q, 3); QueuePushBack(&q, 4);
QueuePushBack(&q, 5); QueuePopFront(&q); QueuePopFront(&q); QueuePopFront(&q);
QueuePopFront(&q); //QueuePopFront(&q); //QueuePopFront(&q); QueueNode* cur =
(&q)->head; while (cur) { printf("%d ", cur->data); cur = cur->next; }
QueueDestroy(&q); } void test2() { Queue q; QueueInit(&q); QueuePushBack(&q,
1); QueuePushBack(&q, 2); QueuePushBack(&q, 3); QueuePushBack(&q, 4); DataType
top = QueueTop(&q); printf("%d ", top); QueuePopFront(&q); top = QueueTop(&q);
printf("%d ", top); printf("\n"); DataType tail = QueueTail(&q); printf("%d ",
tail); printf("\n"); int sz = QueueSize(&q); printf("%d\n",sz);
QueuePopFront(&q); sz = QueueSize(&q); printf("%d\n", sz); QueueDestroy(&q); }
int main() { test1(); //test2(); return 0; }
今日推荐