线性表 分类

用队列实现栈

zedo2022年8月11日大约 3 分钟

队列

数据结构

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
#include <assert.h>  

typedef int QDataType;

// 由于队列是 FIFO(先进先出)，采用数组会移动数据，故采用单链表(带头结点)
typedef struct QueueNode {
    QDataType data;
    struct QueueNode *next;
} QueueNode;

// 队列需要控制队头和队尾两个指针，单独用一个结构体存放
typedef struct Queue {
    QueueNode *head; // 队头
    QueueNode *tail; // 队尾
} Queue;

zedo2022年8月10日大约 2 分钟

数据结构 - 栈

栈

数据结构

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

// 栈可以用数组或链表来存取数据，数组更优，因此这里用数组实现
typedef int SDataType;
typedef struct Stack {
    SDataType *arr;
    int top; // 栈顶
    int capacity; // 容量
} Stack;

zedo2022年8月10日大约 1 分钟

数据结构 - 双向链表

这里我们主要介绍的是链表中最复杂的结构：循环双向链表(Circular Doubly Linked List)

数据结构：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;
typedef struct CDList {
    DataType data;
    struct CDList *prev; // 指向上一结点
    struct CDList *next; // 指向下一结点
} Node;

zedo2022年8月9日大约 3 分钟

数据结构练习题 - 双向循环链表

\emptyset \leftarrow a b ⇆ c d \to \emptyset

zedo2022年8月9日小于 1 分钟

数据结构练习题 - 单链表

这里的单链表是无头非循环的，与数据结构 - 单链表中介绍的一致，并使用到头文件：

zedo2022年8月8日大约 12 分钟

数据结构 - 单链表

链表的表示

顺序表的问题及思考

问题：

中间、头部的插入删除，时间复杂度为 $O (N)$ ；
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

zedo2022年8月8日大约 8 分钟

数据结构 - 顺序表

建议

在阅读本篇文章之前，建议先学会 C 语言的语法，包括但不限于：

指针
内存管理
结构体

zedo2022年8月7日大约 8 分钟

栈和队列习题