1. 约瑟夫环问题——双向无头回环链表
1.1 问题描述
给定 ( n ) 个人(编号为 ( 1, 2, \ldots, n )),他们围成一个圈。从第一个人开始报数,每报到第 ( k ) 个人时,杀掉这个人,然后从下一个人重新开始报数。重复这个过程,直到所有人都被杀死。约瑟夫环问题是要确定最后一个幸存者的编号。
1.2 实质
每次删除循环链表中的一个节点,直到链表中仅剩一个节点结束
2. 双向无头循环链表代码
2.1 makefile
OBJ:=a.out
OBJS+=main.c doublelink.c
CCl=gcc
$(OBJ):$(OBJS)
$(CC) $^ -o $@
.PHONY:
clean:
rm $(OBJ)
test:
valgrind --tool=memcheck --leak-check=full ./$(OBJ)
2.2 double.h
#ifndef _DOUBLELINK_H_
#define _DOUBLELINK_H_
typedef struct stu
{
int id;
char name[32];
int score;
}DataType;
typedef struct node
{
DataType data;
struct node *ppre;
struct node *pnext;
}DouNode;
typedef struct list
{
DouNode *phead;
int clen;
}DouList;
extern DouList *create_dou_link();
extern int is_empty_dou_link(DouList *plist);
extern void dou_link_for_each(DouList *plist, int dir);
extern int push_head_dou_link(DouList *plist, DataType data);
extern int push_tail_dou_link(DouList *plist, DataType data);
extern int pop_head_dou_link(DouList *plist);
extern int pop_tail_dou_link(DouList *plist);
extern void loop_dou_link(DouList *plist);
extern DouNode *Joseph_loop(DouList *plist);
extern void dou_link_for_remain(DouList *plist);
#endif
2.3 double.c
#include "doublelink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
DouList *create_dou_link()//创建标签
{
DouList *plist = NULL;
plist = (DouList *)malloc(sizeof(DouList));
if (NULL == plist)
{
perror("fail to malloc");
return NULL;
}
plist->phead = NULL;
plist->clen = 0;
return plist;
}
int is_empty_dou_link(DouList *plist)//判断空链表
{
if (NULL == plist->phead)
{
return 1;
}
return 0;
}
int push_head_dou_link(DouList *plist, DataType data)//头插
{
DouNode *pnode = NULL;
pnode = malloc(sizeof(DouNode));
if (NULL == pnode)
{
perror("fail to malloc");
return -1;
}
pnode->data = data;
pnode->ppre = NULL;
pnode->pnext = NULL;
if (is_empty_dou_link(plist))//空链表直接插
{
plist->phead = pnode;
}
else
{
pnode->pnext = plist->phead;
plist->phead->ppre = pnode;
plist->phead = pnode;
}
plist->clen++;
return 0;
}
int push_tail_dou_link(DouList *plist, DataType data)//头插
{
DouNode *p = NULL;
DouNode *pnode = NULL;
pnode = malloc(sizeof(DouNode));
if (NULL == pnode)
{
perror("fail to malloc");
return -1;
}
pnode->data = data;
pnode->ppre = NULL;
pnode->pnext = NULL;
if (is_empty_dou_link(plist))//空链表直接插
{
plist->phead = pnode;
}
else
{
p = plist->phead;
while (p->pnext != NULL)
{
p = p->pnext;
}
p->pnext = pnode;
pnode->ppre = p;
}
plist->clen++;
return 0;
}
int pop_head_dou_link(DouList *plist)//头删
{
if (is_empty_dou_link(plist))//空链表直接结束程序
{
return -1;
}
DouNode *pfree = NULL;
pfree = plist->phead;
plist->phead = pfree->pnext;//标签指向第二个节点首地址
if (plist->phead != NULL)//判断是否空链表
{
plist->phead->ppre = NULL;//将第二个节点的ppre变为NULL
}
free(pfree);
plist->clen--;
return 0;
}
int pop_tail_dou_link(DouList *plist)//尾删
{
if (is_empty_dou_link(plist))//空链表程序结束
{
return -1;
}
DouNode *pfree = NULL;
pfree = plist->phead;
while (pfree->pnext)//指针指向最后一个节点
{
pfree = pfree->pnext;
}
if (pfree->ppre != NULL)//链表有两个以上节点
{
pfree->ppre->pnext = NULL;
}
else //链表只有一个节点
{
plist->phead = NULL;
}
free(pfree);
plist->clen--;
return 0;
}
void loop_dou_link(DouList *plist)//将非回环链表改为双向回环链表
{
DouNode *ptmpnode = NULL;
ptmpnode = plist->phead;
while (ptmpnode->pnext != NULL)//将指针移动到末尾节点
{
ptmpnode = ptmpnode->pnext;
}
ptmpnode->pnext = plist->phead;
plist->phead->ppre = ptmpnode;
}
void dou_link_for_remain(DouList *plist)//打印约瑟夫回环一次处理后链表中剩下的成员信息
{
int i = 0;
DouNode *ptmpnode = plist->phead;
for (i = 0; i < plist->clen; i++)
{
printf("%d ", ptmpnode->data.id);
printf("%s ", ptmpnode->data.name);
printf("%d\n", ptmpnode->data.score);
ptmpnode = ptmpnode->pnext;
}
printf("=========================\n");
}
DouNode *Joseph_loop(DouList *plist)//约瑟夫回环、实质是删除链表节点直到留下最后一个节点为止
{
DouNode *pfreenode = NULL;//
DouNode *ptmpnode = NULL;//指向回环
ptmpnode = plist->phead;
while (ptmpnode != ptmpnode->pnext)//判断回环是否只剩下一个节点
{
pfreenode = ptmpnode;//指向当前所在回环的位置
pfreenode = pfreenode->pnext->pnext;//回环向后移动两个单位
pfreenode->ppre->pnext = pfreenode->pnext;
pfreenode->pnext->ppre = pfreenode->ppre;
ptmpnode = pfreenode->pnext;//记录要删除的回环的下一个位置,保证循环的延续
if (pfreenode == plist->phead)//判断要删除的节点是否是表头后的第一个节点、若是,给表头接入要删除节点的下一个节点
{
plist->phead = ptmpnode;
}
free(pfreenode);
plist->clen--;
dou_link_for_remain(plist);//打印链表中剩下的节点信息
}
return ptmpnode;
}
2.4 main.c
#include <stdio.h>
#include <stdlib.h>
#include "doublelink.h"
int main(void)
{
DataType stus[] = {{1, "doinb", 100},
{2, "lwx", 67},
{3, "lqs", 99},
{4, "tian", 98},
{5, "gimgoon", 78},
{6, "xinyi", 88},
{7, "nuguri", 99},
{8, "khan", 77},
{9, "bo", 94},
{10, "xiaolaohu", 60}
};
DouNode *ptmpnode = NULL;
int i = 0;
DouList *plist = create_dou_link();//表头创建
if (NULL == plist)
{
return -1;
}
for (i = 0; i < sizeof(stus) / sizeof(stus[0]); i++)//给链表中插入结构体中的所有内容
{
push_tail_dou_link(plist, stus[i]);//尾插
}
dou_link_for_each(plist, 1);
dou_link_for_each(plist, 0);
loop_dou_link(plist);//创建双向回环链表
ptmpnode = Joseph_loop(plist);//约瑟夫回环
printf("%s\n", ptmpnode->data.name);
return 0;
}
2.5 判断单向链表是否有环
利用快慢指针,慢指针走一步,快指针走两步
快指针每走一步,判断是否为空或者是否与慢指针相遇,相遇为有环链表
3. 内核链表(有头、双向循环链表)
3.1 定义
Linux内核链表是一种双向循环链表,它的实现非常简洁而高效,主要通过一些宏和内联函数来操作链表。链表节点的结构定义在头文件 <linux/list.h>
中。
3.1 offsetof宏
获取结构体某个成员到结构体开头的偏移量
3.2 container_of宏
通过offsetof偏移量获取结构体的首地址
3. 栈
3.1 定义
栈(Stack)是一种抽象的数据结构,它遵循后进先出(LIFO, Last In First Out)的原则。也就是说,最后放入栈中的元素最先被取出。
3.2 栈的基本操作
1. 入栈、压栈:将一个元素放入栈顶。
2. 出栈、弹栈:从栈顶移除一个元素。
3. 取栈顶元素:查看栈顶元素但不移除它。
4. 判断栈是否为空:检查栈中是否有元素。
3.3 分类
(1)按实现方式分类:栈分为顺序栈和链式栈
1. 顺序栈
使用数组实现的栈,数组中的元素按顺序存储。优点是实现简单,访问效率高;缺点是栈的容量固定,扩展不便。
2. 链式栈
使用链表实现的栈,链表的每个节点存储一个栈元素。优点是栈的容量可以动态扩展;缺点是指针操作复杂,访问效率相对较低。
(2)按用途来分类
1. 操作系统栈
用于管理程序执行时的函数调用,保存函数调用的返回地址、本地变量等信息。操作系统栈通常是顺序栈,采用固定大小。
1. 局部变量
2. 函数的形参、返回值
3. 函数调用关系——保护现场、恢复现场
3.4 数据结构中的栈——链式栈
4. 面试考点
区分满增栈、满减栈、空增栈、空减栈(前提:仅限于顺序栈,数组方式构成的)
4.1 满栈和空栈——判断栈顶所在位置是否存有数据而非整个栈有没有数据
1. 满栈:栈顶所在位置有数据
入栈操作流程:先向上移动栈顶指针,再将数据压入栈中
2. 空栈:栈顶所在位置没有数据
入栈操作流程:先将数据压入栈顶,再向上移动栈顶指针
4.2 增栈和减栈——判断栈的生长方向
0x1000与0x2000,内存高地址为0x2000,内存低地址为0x1000
1. 增栈:数据入栈时栈顶指针向内存高地址移动
2. 减栈:数据入栈时栈顶指针向内存低地址移动
(1) 满增栈
1. 出栈时:栈顶指针向内存高地址移动,再向栈顶入栈数据,
2. 出栈时:出栈数据,栈顶指针向内存低地址移动,
(2) 满减栈
(3) 空增栈
1. 出栈时:先向栈顶入栈数据,栈顶指针向内存高地址移动
2. 出栈时:栈顶指针向内存低地址移动,出栈数据
(4) 空减栈
5. 数据结构中的栈——链式栈
5.1 代码
(1)makefile
OBJ:=a.out
OBJS+=main.c stack.c
CCl=gcc
$(OBJ):$(OBJS)
$(CC) $^ -o $@
.PHONY:
clean:
rm $(OBJ)
test:
valgrind --tool=memcheck --leak-check=full ./$(OBJ)
注意:在终端输入make test可以测试销毁是否成功以及是否有内存泄漏
(2)stack.h
#ifndef _STACK_H_
#define _STACK_H_
typedef int DataType;
typedef struct stact_node
{
DataType data;
struct stact_node *pnext;
}StackNode;
typedef struct Stack
{
StackNode *ptop;
int clen;
}StackList;
extern StackList *create_stack();
extern int is_empty_stack(StackList *plist);
extern int push_stack(StackList *plist, DataType data);//入栈头插
extern void stack_for_each(StackList *plist);
extern int pop_stack(StackList *plist, DataType *pdata);//出栈头删
extern void clear_stack(StackList *plist);
extern void destory_stack(StackList *plist);
extern int get_stack_top(StackList *plist, DataType *pdata);
#endif
(3)stack.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
StackList *create_stack()
{
StackList *plist = malloc(sizeof(StackList));
if (NULL == plist)
{
perror("fail to malloc");
return NULL;
}
plist->ptop = NULL;
plist->clen = 0;
return plist;
}
int is_empty_stack(StackList *plist)
{
if (NULL == plist->ptop)
{
return 1;
}
return 0;
}
int push_stack(StackList *plist, DataType data)//入栈头插
{
StackNode *pnode = malloc(sizeof(StackNode));
if (NULL == pnode)
{
perror("fail to malloc");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
pnode->pnext = plist->ptop;
plist->ptop = pnode;
plist->clen++;
return 0;
}
void stack_for_each(StackList *plist)
{
StackNode *ptmp = plist->ptop;
while (ptmp != NULL)
{
printf("%d ", ptmp->data);
ptmp = ptmp->pnext;
}
printf("\n");
}
int pop_stack(StackList *plist, DataType *pdata)//出栈头删
{
if (is_empty_stack(plist))
{
return -1;
}
StackNode *pfree = plist->ptop;
plist->ptop = pfree->pnext;
if (pdata != NULL)//传入非空地址,将删除的节点的数据传出
{
*pdata = pfree->data;
}
free(pfree);
plist->clen--;
return 0;
}
void clear_stack(StackList *plist)//清空栈区
{
while (!is_empty_stack(plist))
{
pop_stack(plist, NULL);
}
}
void destory_stack(StackList *plist)
{
if (!is_empty_stack(plist))
{
clear_stack(plist);
}
free(plist);
}
int get_stack_top(StackList *plist, DataType *pdata)//获得栈顶数据
{
if (is_empty_stack(plist))
{
return -1;
}
*pdata = plist->ptop->data;
return 0;
}
(4)main.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
int main(void)
{
DataType tmpdata = 0;
DataType data[] = {1, 2, 3, 4, 5};
StackNode *ptmpnode = NULL;
int i = 0;
int ret = 0;
StackList *plist = create_stack();//创建栈表头
if (NULL == plist)
{
return -1;
}
for (i = 0; i < sizeof(data) / sizeof(data[0]); i++)//入栈所有数据
{
push_stack(plist, data[i]);//入栈头插
}
stack_for_each(plist);//遍历打印所有数据
#if 0
for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)//获取栈顶元素并打印,出栈数据,打印栈中的剩下元素
{
printf("======== %d ========", i);
ret = get_stack_top(plist, &tmpdata);
if (0 == ret)
{
printf("ptop data:%d ", tmpdata);
}
pop_stack(plist, NULL);
stack_for_each(plist);//遍历打印所有数据
}
#endif
#if 0
clear_stack(plist);//清理栈中所有节点
if (is_empty_stack(plist))
{
printf("clear_stack success!\n");
}
#endif
#if 1
destory_stack(plist);
#endif
return 0;
}
5.2 应用
1. 撤回操作
2. 浏览器返回上一层操作
3. 计算器
示例:利用链式栈实现四则运算
1. makefile
OBJ:=a.out
OBJS+=calculate.c stack.c
CCl=gcc
$(OBJ):$(OBJS)
$(CC) $^ -o $@
.PHONY:
clean:
rm $(OBJ)
test:
valgrind --tool=memcheck --leak-check=full ./$(OBJ)
2. calculate.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
int is_char_num(char ch)//判断此指针是否指向数字
{
if (ch >= '0' && ch <= '9')
{
return 1;
}
return 0;
}
int get_opt_level(char opt)//获得运算符优先级
{
switch(opt)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
}
int get_result(int num1, int num2, char opt)//获得运算结果
{
switch(opt)
{
case '+':return num1 + num2;
case '-':return num1 - num2;
case '/':return num1 / num2;
case '*':return num1 * num2;
}
}
int main(int argc, const char *argv[])
{
char press[128] = {0};//运算表达式
DataType num = 0;//存储每个运算数
DataType data;
DataType opt;
DataType num1;
DataType num2;
DataType res = 0; //计算器返回值
StackList *pNumStack = create_stack();//存储数字的栈
StackList *pOptStack = create_stack();//存储运算符的栈
fgets(press, sizeof(press), stdin);
press[strlen(press)-1] = '\0';
char *p = press;//遍历运算式字符串
while (1)
{
if ('\0' == *p && is_empty_stack(pOptStack))//循环结束的条件,指针遍历到字符串末尾,运算符栈为空
{
break;
}
/*判断条件1*/
while (is_char_num(*p))//拆解数字
{
num = num * 10 + (*p - '0');
p++;
if (!is_char_num(*p))
{
push_stack(pNumStack, num);//入栈数字
num = 0;
}
}
/*判断条件2*/
if (is_empty_stack(pOptStack))//运算符栈为空,入栈
{
push_stack(pOptStack, *p);
p++;
continue;
}
/*判断条件3*/
if ('\0' == *p && !is_empty_stack(pOptStack))//结束条件
{
pop_stack(pOptStack, &opt);
pop_stack(pNumStack, &num2);
pop_stack(pNumStack, &num1);
res = get_result(num1, num2, opt);
push_stack(pNumStack, res);
continue;
}
/*判断条件4*/
get_stack_top(pOptStack, &data);
if (get_opt_level(data) < get_opt_level(*p))//运算符栈不为空,本次运算符优先级大于栈顶中运算符优先级
{
push_stack(pOptStack, *p);
p++;
}
else if (get_opt_level(data) >= get_opt_level(*p))
{
pop_stack(pOptStack, &opt);
pop_stack(pNumStack, &num2);
pop_stack(pNumStack, &num1);
res = get_result(num1, num2, opt);
push_stack(pNumStack, res);
}
}
get_stack_top(pNumStack, &res);
printf("res = %d\n", res);
destaroy_stack(pNumStack);
destaroy_stack(pOptStack);
return 0;
}
3. stack.c
#include "stack.h"
#include <stdlib.h>
#include <stdio.h>
StackList *create_stack()
{
StackList *pstack = malloc(sizeof(StackList));
if (NULL == pstack)
{
perror("fail malloc");
return NULL;
}
pstack->ptop = NULL;
pstack->clen = 0;
return pstack;
}
int is_empty_stack(StackList *pstack)
{
if (NULL == pstack->ptop)
{
return 1;
}
return 0;
}
int push_stack(StackList *pstack, DataType data)
{
StackNode *pnode = malloc(sizeof(StackNode));
if (NULL == pnode)
{
perror("fail malloc");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
pnode->pnext = pstack->ptop;
pstack->ptop = pnode;
pstack->clen++;
return 0;
}
int pop_stack(StackList *pstack, DataType *pdata)
{
if (is_empty_stack(pstack))
{
return 1;
}
StackNode *pfree = pstack->ptop;
pstack->ptop = pfree->pnext;
if (pdata != NULL)
{
*pdata = pfree->data;
}
free(pfree);
pstack->clen--;
return 0;
}
void clear_stack(StackList * pstack)
{
while (!is_empty_stack(pstack))
{
pop_stack(pstack, NULL);
}
}
void destaroy_stack(StackList *pstack)
{
clear_stack(pstack);
free(pstack);
}
int get_stack_top(StackList *pstack, DataType *pdata)
{
if (is_empty_stack(pstack))
{
return 1;
}
*pdata = pstack->ptop->data;
return 0;
}
4. stack.h
#ifndef __STACK_H__
#define __STACK_H__
typedef int DataType;
typedef struct stk_node
{
DataType data;
struct stk_node *pnext;
}StackNode;
typedef struct Stack
{
StackNode *ptop;
int clen;
}StackList;
StackList *create_stack();
int is_empty_stack(StackList *);
int push_stack(StackList *, DataType );
int pop_stack(StackList *, DataType *);
void clear_stack(StackList *);
void destaroy_stack(StackList *);
int get_stack_top(StackList *, DataType *);
#endif