一、循环链表(环形链表)
循环链表是一种特殊的单链表,尾节点的指针域不指向 NULL,而是指向头节点,形成一个环。
1. 节点结构体
typedef struct node
{
data_t data;
struct node *next;
}node_t;
2. 创建空循环链表
创建头节点后,头节点的指针域指向自己,形成一个"自环"。
node_t * clinklist_create(void)
{
//创建头节点
node_t *head = malloc(sizeof(node_t));
if (head == NULL)
{
printf("malloc fail\\n");
return NULL;
}
//头节点的指针域指向自己
head->next = head;
return head;
}
3. 插入数据——头插
循环链表的头插需要分三种情况考虑:
- 空循环链表
- 只有一个数据节点
- 多个节点
思路:
- p_new->next = phead->next;(新节点指向原来的首节点)
- 找到头节点的上一个节点(p->next == phead),让其指向新节点
- p->next = p_new;
特殊情况: 单个节点时,数据节点要指向自己。
int is_empty(node_t *phead)
{
if (phead==NULL)
{
return -1;
}
return phead->next == phead;
}
int clinklist_insert_head(node_t* phead,data_t data)
{
if (phead==NULL)
{
return -1;
}
//创建节点
node_t *p_new = malloc(sizeof(node_t));
if (p_new == NULL)
{
printf("malloc fail\\n");
return -1;
}
p_new->data = data;
//空循环链表
if (is_empty(phead) == 1)
{
phead->next = p_new;
p_new->next = p_new;
}else
{
node_t *tail = phead->next;
//找到尾节点(头节点上一个节点)
while (tail->next != phead->next)
tail=tail->next;
//链接
p_new->next = phead->next;
tail->next = p_new;
phead->next = p_new;
}
return 0;
}
多节点时的操作: 遍历找到头节点的前一个节点(p->next == phead),让 p->next = p_new 即可。
3.5 遍历打印
循环链表的遍历终止条件与普通链表不同:当指针回到头节点时停止(p != phead),而不是 p != NULL。
int clinklist_print(node_t *phead)
{
if (phead==NULL || is_empty(phead) == 1)
{
return -1;
}
node_t *p = phead->next;
while (p->next != phead->next)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d \\n",p->data);
return 0;
}
与普通链表的区别: 普通链表遍历条件是 p != NULL,循环链表因为尾节点指向头节点,永远不会有 NULL,所以必须用 p != phead 作为终止条件,否则会死循环。
4. 查找
node_t * clinklist_find_key(node_t *phead,data_t key)
{
if (phead==NULL || is_empty(phead) == 1)
{
return NULL;
}
node_t *p = phead->next;
while (p->next != phead->next)
{
if (p->data == key)
{
return p;
}
p = p->next;
}
if (p->data == key)
{
return p;
}
return NULL;
5. 删除(头删)
思路:
- p:移动的指针,找到要删除节点的前一个节点
- p_temp:要删除的节点
int clinklist_delete_head(node_t *phead)
{
if (phead==NULL || is_empty(phead) == 1)
{
return -1;
}
node_t *p_temp = phead->next;
node_t *tail = phead->next;
while (tail->next != phead->next)
tail = tail->next;
phead->next = p_temp->next;
tail->next = p_temp->next;
free(p_temp);
return 0;
}
6. 销毁
销毁逻辑:
int clinklist_destroy(node_t **phead)
{
if (*phead==NULL || is_empty(*phead) == 1)
{
return -1;
}
node_t *p = (*phead)->next;
while (p->next != (*phead)->next)
{
node_t *p_temp = p;
p = p->next;
free(p_temp);
}
free(p);
free(*phead);
*phead = NULL;
return 0;
}
循环链表操作小结
| 1 | 创建 | 头节点指针域指向自己 |
| 2 | 插入 | 头插法,注意空链表和单节点的特殊处理 |
| 3 | 查找 | 遍历条件为 p != phead |
| 4 | 删除 | 找前驱节点,注意释放内存 |
| 5 | 销毁 | 逐个释放所有节点,头节点最后释放 |
| 6 | 判空 | phead->next == phead |
二、栈
1. 栈的基本概念
栈是一种线性的数据结构,属于受限的线性表——只能在一端进行数据操作。
- 栈顶:操作数据的一端(入栈、出栈都在此进行)
- 栈底:不能进行数据操作的一端
- 操作顺序:FILO(First In Last Out,先进后出)
类比:筒装羽毛球,先放进去的在最下面,最后才能拿出来。
栈的基本操作:
| 1 | 创建栈 | 初始化栈结构 |
| 2 | 入栈(push) | 将数据放入栈顶 |
| 3 | 出栈(pop) | 从栈顶取出数据 |
| 4 | 获取栈顶元素 | 返回栈顶元素但不出栈 |
| 5 | 获取栈的容量 | 栈能存放的最大元素个数 |
| 6 | 获取栈的大小 | 栈中有效数据的个数 |
| 7 | 销毁 | 释放栈的内存 |
2. 顺序栈(数组实现)
结构体定义
typedef int data_t;
typedef struct seqstack
{
data_t *stack; //需要空间 堆上开辟
int top;
int max;
}seqstack_t;
关键约定
- 栈空:top == -1
- 栈满:top == max – 1
创建栈
seqstack_t * seqstack_create(int n) //n表示栈容量
{
//栈结构创建出来
seqstack_t *ps = malloc(sizeof(seqstack_t));
if (ps == NULL)
{
return NULL;
}
//创建栈的空间
ps->stack = malloc(sizeof(data_t) * n);
//栈顶指针 初始化
//容量初始化一下
ps->top = -1;
ps->max = n;
return ps;
}
判空与判满
int is_empty(seqstack_t *ps)
{
if (ps == NULL)
{
return -1;
}
return ps->top == -1;
}
int is_full(seqstack_t *ps)
{
if (ps == NULL)
{
return -1;
}
return ps->top == ps->max-1;
}
入栈(push)
int push(seqstack_t *ps, data_t data)
{
if (ps == NULL)
{
return -1;
}
if (is_full(ps) == 1)
{
printf("full stack!\\n");
return -1;
}
ps->top ++;
ps->stack[ps->top] = data;
return 0;
}
出栈(pop)
int pop(seqstack_t *ps,data_t *data)
{
if (ps == NULL || is_empty(ps) == 1)
{
return -1;
}
//栈空 is_empty
// *data = 栈顶数据
// top–
*data = ps->stack[ps->top];
ps->top–;
return 0;
}
获取栈顶元素
data_t get_top_element(seqstack_t *ps)
{
/// 直接返回此时栈指针所指向的元素
if (ps == NULL)
{
return -1;
}
if (is_empty(ps) == 1)
{
return -1;
}
return ps->stack[ps->top];
}
获取栈的大小
int get_stack_size(seqstack_t *ps )
{
// 就是top+1
if (ps == NULL)
{
return -1;
}
if (is_empty(ps) == 1)
{
return 0;
}
return ps->top + 1;
}
销毁栈
int seqstack_destroy(seqstack_t **pps)
{
if(pps == NULL)
{
return -1;
}
free((*pps)->stack);
free(*pps);
*pps = NULL;
return 0;
}
3. 链式栈(链表实现)
链式栈本质上还是单向链表的操作,属于受限的线性表。
- 入栈 push → 对应链表的头插
- 出栈 pop → 对应链表的头删
- 栈顶 → 链表的首节点(头节点的下一个)
- 栈底 → 不动
链式栈不需要考虑容量限制。
节点结构体
typedef struct stack
{
data_t data;
struct stack *next;
} node_t;
创建栈(创建空链表)
node_t *linkstack_create(void)
{
node_t *pstack = malloc(sizeof(node_t));
if (pstack == NULL)
return NULL;
pstack->next = NULL;
return pstack;
}
入栈 push(头插)
int push(node_t *pstack, data_t data)
{
node_t *p_new = malloc(sizeof(node_t));
if (p_new == NULL)
return -1;
p_new->data = data;
p_new->next = pstack->next;
pstack->next = p_new;
return 0;
}
出栈 pop(头删)
int pop(node_t *pstack, data_t *data)
{
if (pstack == NULL || pstack->next == NULL)
return -1;
node_t *p_temp = pstack->next;
*data = p_temp->data;
pstack->next = p_temp->next;
free(p_temp);
return 0;
}
获取栈顶元素
data_t get_top_element(node_t *pstack)
{
// 获取首节点的数据,先判断是否为空栈
if (pstack == NULL || pstack->next == NULL)
return (data_t)-1;
return pstack->next->data;
}
获取栈的大小
int get_stack_size(node_t *pstack)
{
int count = 0;
node_t *p = pstack->next;
while (p != NULL)
{
count++;
p = p->next;
}
return count;
}
销毁(逐个销毁链表节点)
int linkstack_destroy(node_t **ppstack)
{
if (ppstack == NULL || *ppstack == NULL)
return -1;
// 链表节点挨个销毁
node_t *p = *ppstack;
while (p != NULL)
{
node_t *temp = p;
p = p->next;
free(temp);
}
// 悬空指针
*ppstack = NULL;
return 0;
}
三、队列
1. 队列的基本概念
队列是一种受限的线性表,类似于排队。
- 队头:负责出数据
- 队尾:负责入数据
- 操作顺序:FIFO(First In First Out,先进先出)
队列可以用顺序表(数组) 或 链表 实现。
2. 顺序队列——循环队列
用数组实现队列时,为了避免"假溢出"问题,采用循环队列的方式,通过取模运算让下标循环。
队列结构体
typedef int data_t;
typedef struct queue
{
data_t *que; // 队列的空间
int head; // 队头——负责出数据
int tail; // 队尾——负责入数据
int tlen; // 容量
} queue_t;
关键状态判断
- 队空:head == tail == 0
- 队满:(tail + 1) % N == head(牺牲一个存储空间来区分队空和队满)
取模运算 %N 保证下标在 [0, N-1] 范围内循环。
创建队列
queue_t *queue_create(int len)
{
queue_t *pq = malloc(sizeof(queue_t));
if (pq == NULL)
{
return NULL;
}
pq->que = malloc(sizeof(data_t)*len);
if (pq->que == NULL)
{
free(pq);
return NULL;
}
pq->head = pq->tail = 0;
pq->len = len;
return pq;
}
判空与判满
int is_empty(queue_t *pq)
{
if (pq == NULL)
{
return -1;
}
return pq->tail == pq->head;
}
int is_full(queue_t *pq)
{
if (pq == NULL)
{
return -1;
}
return ((pq->tail+1) % pq->len) == 0;
}
入队 enqueue
int enqueue(queue_t *pq,data_t data)
{
if (pq == NULL)
{
return -1;
}
if (is_full(pq) == 1)
{
return -1;
}
pq->que[pq->tail] = data;
pq->tail++;
return 0;
}
出队 dequeue
int dequeue(queue_t *pq, data_t *data)
{
//判断是否空? — is_empty()
//队头负责出数据
//先出值
//后 移动head
if (pq == NULL)
{
return -1;
}
if (is_empty(pq) == 1)
{
return -1;
}
*data = pq->que[pq->head];
pq->head++;
return 0;
}
销毁队列
int queue_destroy(queue_t **ppq)
{
if(ppq == NULL ||*ppq==NULL )
{
return -1;
}
free((*ppq)->que);
free(*ppq);
*ppq=NULL;
return 0;
}
3. 链式队列(链表实现)
用链表实现队列,操作对应到链表的基本操作:
| 创建队列 | 创建空链表 | 初始化 |
| 入队 | 尾插 | 队尾入数据 |
| 出队 | 头删 | 队头出数据 |
| 销毁队列 | 销毁链表 | 释放所有节点 |
四、总结回顾
核心要点
1. 循环链表
- 尾节点指针指向头节点,形成环形结构
- 遍历终止条件为 p != phead(而不是 p != NULL)
- 头插时注意空链表和单节点的特殊处理
2. 栈
- 受限的线性表,只能在栈顶操作
- FILO(先进后出)
- 顺序栈用数组实现,注意 top == -1 表示空栈,top == max-1 表示满栈
- 链式栈本质上是单向链表,入栈即头插,出栈即头删
3. 队列
- 受限的线性表,队头出数据,队尾入数据
- FIFO(先进先出)
- 循环队列通过取模 %N 实现下标循环,牺牲一个空间区分队空和队满
- 链式队列入队对应尾插,出队对应头删



