目录

一、栈

       介绍

       初始准备

       栈的初始化与销毁

       栈为空

       进栈与出栈

       栈的有效数据个数

       栈顶的数据

       全部代码

二、队列

       介绍

       初始准备

       队列的初始化与销毁

       队列为空

       进队列与出队列

       队列的有效数据个数

       队头和队尾的数据

       全部代码

一、栈

介绍

栈是一种线性结构,类似于链表和顺序表,但也有它的独特之处,只能栈顶入,栈顶出,所以栈也是“先进后出”或者“后进先出”

栈能采用链式结构也能采用数组结构来实现,这里采用数组结构

链式结构

采用单链表,头作栈顶,头插入数据,头删出数据

 

采用带头双链表,尾作栈顶,尾插入数据,尾删出数据

数组结构

尾部作栈顶,头部作栈底,尾插入数据,尾删出数据

 

初始准备

为了使存储的数据类型不固定,能够在存储其它类型数据时容易修改,所以用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; }

技术
©2019-2020 Toolsou All rights reserved,
程序员的520,送给女友的几行漂亮的代码(python版)基于stm32控制四轮小车电机驱动(一)linux查看磁盘空间命令实验四 自动化测试工具-软件测试axios拦截器封装与使用C语言——qsort函数opencv-python傅里叶变换以及逆变换在算法研究过程中如何进行算法创新nc的安装和简单操作C语言做一个简易的登陆验证(功能)界面