链表|栈和队列(跑路人笔记) 链表|数据结构

【链表|栈和队列(跑路人笔记)】
文章目录

前言
栈的代码实现
- 结构体类型
- 初始化
- 摧毁栈
- 入栈
- 其他琐碎接口
队列的代码实现
- 队列的结构类型
- 初始化
- 摧毁
- 入元素
- 出元素
- 琐碎的重要接口

前言老样子数据结构

注重逻辑
平时敲代码易忽略的点培养
特殊例子的想象
调试能力的培养
…
复习一下,省的学习时失去目标
本次是栈和队列代码的实现和易错点的解析
感觉博主写的带劲的来点带劲的赞
(PS:栈和队列在代码实现方面其实很简单,如果大家实现过顺序表链表之路的会发现这个简单的yap).

栈的代码实现还是讲个闲话,这里的栈的实现可以通过链表的形式或者通过顺序表的形式实现,不过通过栈的特性-----栈顶如栈顶出,我们不难发现栈使用顺序表的形式实现有很多优点,这个大家应该不用例子吧.
结构体类型

typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST;

a用来储存数据,top来记录栈顶,capacity用来保存容量大小
初始化

void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0; }

像之前完成顺序表一样我们可以用两种方式来进行这个栈实现的初始化不过有一说一还是在初始化时直接给一段空间会很舒服.而且方便未来的更改调试,模块化也比较到位,所以我推荐这样进行初始化,不过你感觉舒服最重要.
摧毁栈

void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }

顺序表的优点来了,在摧毁的时候真的很方便,直接free置空就好.记得置空=-=.
入栈

void StackPush(ST* ps, STDataType x) { assert(ps); // 满了->增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; }

这里我没有把扩容功能单独包装,其实很简单因为只有一个地方用到了扩容功能,不过你要是想单独包装一下也是挺好的看着很简洁.不过博主这里就偷个懒了.

文章图片

这里用了==来判断是否增容当然也可以用>=但是top是一个一个涨的所以用==我个人认为更优可以比较直观一些.
没了=-=也是很简单的一个函数.
其他琐碎接口

STDataType StackTop(ST* ps) { assert(ps); // 栈空了，调用Top，直接中止程序报错 assert(ps->top > 0); return ps->a[ps->top - 1]; }int StackSize(ST* ps) { assert(ps); return ps->top; }bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }

第一个接口,用来返回栈顶元素.
第二个接口,用来返回栈顶位置
第三个接口,测试栈是否为空, 为空就返回1,否则返回0
可以看到这三个函数简单的不能再简单了哪为啥还要专门弄个函数呢???
其实很简单这些代码虽然简单但是在别人使用时如果不看看你代码是很难直接写出这些程序的更不用说未来几万行代码时别痛苦的翻找你的代码时骂骂咧咧的嘴脸了.
所以这些接口是非常非常重要的千万不可以图省事不写!!!?
队列的代码实现应该有一些人不知到队列是啥东西,其实很简单队列就跟我们排队一样数据从队尾进入从队头出去.
举个例子: 1 2 3 4 分别进入队列要想删除4就只能先删除1 2 3 最后才可以删除4.
希望上面这个例子大家可以看懂毕竟舒文的语言表达能力实在一般.
也正因为队列的这个特点队列使用单链表是很香的毕竟如果使用顺序表的话找队尾比较麻烦,使用带头循环双向链表的结构又很麻烦,所以使用单链表就刚刚好,又够用又方便
队列的结构类型

typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue;

很标准的单链表结构哈.
初始化

void QueueInit(Queue* pq) { assert(pq); pq->head = 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 = pq->tail = NULL; }

摧毁也是很经典的单链表形式一个节点一个节点的释放, 至于这个为啥用cur做临时变量进行而不是直接用pq->head呢?
入元素

// 队尾入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }

队尾入的第一件事当然是检查是否需要扩容然后因为我们初始化时是将队头和队尾直接NULL对待了所以在扩容时我们就需要下一些功夫.
在newnode开辟好了之后我们先将要输入的值输进去,并把newnode->next置空—这一步挺重要的如果不置空的话摧毁函数就用不了了然后newnode->next也变成了野指针非常恐怖??.
填入数据后我们就分开进行处理

文章图片

这个if else语句就是为了判断的

1.队列内无元素,无元素时直接让头尾都指向newnode.
2. 有元素连接尾部并将尾指针指向newnode.

出元素

void QueuePop(Queue* pq) { assert(pq); assert(pq->head); // 1、一个 // 2、多个 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和空链表都断言了大家也可以温柔温柔.
琐碎的重要接口再次强调这部分的接口虽然简单但是绝对不能不实现?

QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; }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; }

第一个函数QueueFront返回头部元素
第二个QueueBack返回尾部元素
第三个QueueSize返回链表现在的大小
第四个QueueEmpty判断是否为空链表