万网放网站,网页设计与制作教程杨选辉,影视网站设计论文,四川省建设信息网站前言
这个专栏将会用纯C实现常用的数据结构和简单的算法#xff1b;有C基础即可跟着学习#xff0c;代码均可运行#xff1b;准备考研的也可跟着写#xff0c;个人感觉#xff0c;如果时间充裕#xff0c;手写一遍比看书、刷题管用很多#xff0c;这也是本人采用纯C语言…前言
这个专栏将会用纯C实现常用的数据结构和简单的算法有C基础即可跟着学习代码均可运行准备考研的也可跟着写个人感觉如果时间充裕手写一遍比看书、刷题管用很多这也是本人采用纯C语言实现的原因之一欢迎收藏 关注本人将会持续更新。 文章目录 双向链表简介双链表实现 循环链表循环链表约瑟夫环问题 双向链表
简介 双向链表对比单链表来说顾名思义就是指向指向有两个指针指向前后节点。 结合单链表单链表有无头和有头之分双向链表也是一样这里是无头双链表采用再封装写法不是二级指针写法再封装写法比较写起来比较容易个人比较偏爱
双链表图示 从ADT抽象中来说
总结起来一句话增删改查假设双向链表是一个结合这这个结合功能有
增加元素删除元素拿取元素查询元素修改元素…………………………
双链表实现
这里采用再封装的方法实现无头链表有头和无头再单链表的那一节以及讲过了这里采用无头实现 节点封装
在双链表中对于每一个节点来说都有一个指向前、指向后节点的指针。
typedef int DataType;typedef struct Node {DataType data;struct Node* prev; // 前struct Node* next; // 后
}Node;⚜️ 链表封装
这一步封装的作用是可以更好的操作链表的一些操作这个size的一个再封装写法的核心无头与有头再实现的过程中核心就在于第一个头节点的处理无头如果没有任何节点则插入的节点则作为第一个节点但是这样会改变指针的指向这也是因为需要传递二级指针的原因而再封装写法则很好的解决了这个问题。
typedef struct List {Node* headNode;Node* tailNode;int size;
}List;创建节点
采用calloc创建节点这样可以自动赋值为0。
Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}创建链表
List* create_list()
{List* list (List*)calloc(1, sizeof(List));assert(list);return list;
}插入–头插
情况判断是否为空链表 空链表插件节点作为头不为空头插如图
void push_front(List* list, DataType data)
{if (list NULL) {return;}Node* node create_node(data);if (list-size 0) { // 这种写法的优势不用传递二级指针list-tailNode node;}else {node-next list-headNode;list-headNode-prev node;}list-headNode node;list-size;
}插入–尾插入
情况判断是否为空链表 为空插入作为头不为空找到尾节点插入
void push_back(List* list, DataType data)
{if (list NULL) {return;}Node* node create_node(data);if (list-size 0) {list-headNode node;}else {list-tailNode-next node;node-prev list-tailNode;}list-tailNode node;list-size;
}插入–任意位置
规则 在元素后位置插入情况3种 没有该元素尾插任意插
void insert(List* list, DataType posData, DataType data)
{if (list NULL || list-size 0) { // size 0 保证有头return;}Node* t list-headNode;while (t-next ! NULL t-data ! posData) {t t-next;}if (t-data ! posData) { // 没有该元素return;}else if (t-next NULL t-data posData) { // 尾插Node* node create_node(data);node-prev t;t-next node;list-tailNode node; // 尾巴移位}else{Node* node create_node(data);node-next t-next;t-next-prev node;node-prev t;t-next node;}list-size;
}删除–头删
注意点释放后指针指向问题
如果说就一个元素则删除后在封装头需要指向NULL如果不是则下一个元素的prev指针需要赋值为NULL
void pop_front(List* list)
{if (list NULL || list-size 0) {return;}Node* node list-headNode;list-headNode node-next;free(node);(list-headNode) ? (list-headNode-prev NULL) : (list-tailNode NULL); // 判断是否只有一个节点的情况node NULL;
}删除–尾删除
注意点释放后指针指向问题
如果说就一个元素则删除后在封装头需要指向NULL如果不是则上一个元素的next指针需要赋值为NULL
void pop_back(List* list)
{if (list NULL || list-size 0) {return;}Node* node list-tailNode;list-tailNode list-tailNode-prev;free(node);(list-tailNode) ? (list-tailNode-next NULL) : (list-headNode NULL);list-size--;
}删除–任意位置删除
四种情况
没有找到找到了 头删尾删任意位置删
void erase(List* list, DataType posData)
{if (list NULL || list-size 0) {return;}Node* cur list-headNode;while (cur-next ! NULL cur-data ! posData) {cur cur-next;}// 没有找到if (cur-data ! posData) {return;}else if (cur-next NULL) { // 尾删除pop_back(list);}else if (cur-prev NULL) { // 头删pop_front(list);}else {Node* t cur;cur-prev-next cur-next;cur-next-prev cur-prev;free(t);t NULL;list-size--;}
} 万金油函数
bool empty(List* list)
{if (list NULL) {return true;}return list-size 0;
}size_t size(List* list)
{if (list NULL) {return 0;}return list-size;
} 向前遍历
void travel_front(List* list)
{if (list NULL) {return;}Node* cur list-headNode;while (cur) {printf(%d , cur-data);cur cur-next;}printf(\n);
}向后遍历
void travel_back(List* list)
{if (list NULL) {return;}Node* cur list-tailNode;while (cur) {printf(%d , cur-data);cur cur-prev;}printf(\n);
}⏰ 总代码
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int DataType;typedef struct Node {DataType data;struct Node* prev;struct Node* next;
}Node;typedef struct List {Node* headNode;Node* tailNode;int size;
}List;Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}List* create_list()
{List* list (List*)calloc(1, sizeof(List));assert(list);return list;
}void push_front(List* list, DataType data)
{if (list NULL) {return;}Node* node create_node(data);if (list-size 0) {list-tailNode node;}else {node-next list-headNode;list-headNode-prev node;}list-headNode node;list-size;
}void push_back(List* list, DataType data)
{if (list NULL) {return;}Node* node create_node(data);if (list-size 0) {list-headNode node;}else {list-tailNode-next node;node-prev list-tailNode;}list-tailNode node;list-size;
}void insert(List* list, DataType posData, DataType data)
{if (list NULL || list-size 0) { // size 0 保证有头return;}Node* t list-headNode;while (t-next ! NULL t-data ! posData) {t t-next;}if (t-data ! posData) { // 没有该元素return;}else if (t-next NULL t-data posData) { // 尾插Node* node create_node(data);node-prev t;t-next node;list-tailNode node; // 尾巴移位}else{Node* node create_node(data);node-next t-next;t-next-prev node;node-prev t;t-next node;}list-size;
}void pop_front(List* list)
{if (list NULL || list-size 0) {return;}Node* node list-headNode;list-headNode node-next;free(node);(list-headNode) ? (list-headNode-prev NULL) : (list-tailNode NULL); // 判断是否只有一个节点的情况node NULL;
}void pop_back(List* list)
{if (list NULL || list-size 0) {return;}Node* node list-tailNode;list-tailNode list-tailNode-prev;free(node);(list-tailNode) ? (list-tailNode-next NULL) : (list-headNode NULL);list-size--;
}void erase(List* list, DataType posData)
{if (list NULL || list-size 0) {return;}Node* cur list-headNode;while (cur-next ! NULL cur-data ! posData) {cur cur-next;}// 没有找到if (cur-data ! posData) {return;}else if (cur-next NULL) { // 尾删除pop_back(list);}else if (cur-prev NULL) { // 头删pop_front(list);}else {Node* t cur;cur-prev-next cur-next;cur-next-prev cur-prev;free(t);t NULL;list-size--;}
}bool empty(List* list)
{if (list NULL) {return true;}return list-size 0;
}size_t size(List* list)
{if (list NULL) {return 0;}return list-size;
}void travel_front(List* list)
{if (list NULL) {return;}Node* cur list-headNode;while (cur) {printf(%d , cur-data);cur cur-next;}printf(\n);
}void travel_back(List* list)
{if (list NULL) {return;}Node* cur list-tailNode;while (cur) {printf(%d , cur-data);cur cur-prev;}printf(\n);
}int main()
{List* list create_list();for (int i 1; i 4; i) {push_front(list, i);}for (int i 1; i 4; i) {push_back(list, i * 10);}travel_front(list);travel_back(list);insert(list, 3, 33);insert(list, 30, 300);travel_front(list);travel_back(list);pop_front(list);travel_front(list);travel_back(list);pop_back(list);travel_front(list);travel_back(list);erase(list, 33);erase(list, 30);erase(list, 10);travel_front(list);travel_back(list);return 0;
}循环链表
循环链表分为循环单链表循环双链表单链表和双链表又分为有头和无头链表这里是有头循环双链表。
双向循环链表Doubly Circular Linked List是一种数据结构其中每个节点都包含两个指针一个指向前一个节点一个指向后一个节点。与普通链表不同的是双向循环链表的最后一个节点的下一个指针指向头节点而头节点的前一个指针指向最后一个节点形成一个循环。 节点封装
typedef int DataType;typedef struct Node {DataType data;struct Node* prev;struct Node* next;
}Node;创建节点
Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}⚜️ 创建链表
这里需要构建一个循环节点(链表)如图 Node* create_list()
{Node* list (Node*)calloc(1, sizeof(Node));assert(list);list-next list;list-prev list;return list;
}插入–头插
双向头删就很容易了如图 void push_front(Node* list, DataType data)
{assert(list);Node* node create_node(data);node-next list-next;list-next-prev node; // 难点不用担心 nextprev为空的时候node-prev list;list-next node;
}插入–尾插
尾巴删除也很容易因为头和尾巴互相找到如图 void push_back(Node* list, DataType data)
{assert(list);Node* node create_node(data);node-prev list-prev;list-prev-next node;node-next list;list-prev node;
}⛹️♀️ 插入–任意位置
任意位置也不难找到要插入的位置要注意的是找不到的情况。
// 找到要插入那个节点的位置节点
void insert(Node* list, DataType posData ,DataType data)
{assert(list);Node* cur list-next;while (cur-next ! list cur-data ! posData) {cur cur-next;}if (cur-data ! posData) { // 思考为什么不能 cur-next ! list ?????return;}else {Node* node create_node(data);node-next cur-next;cur-next-prev node;node-prev cur;cur-next node;}}删除–头删
注意 一个节点的头节点指向不同。
两种情况
如果一个元素这个时候删除头节点指向修改和两个元素以上删除不同这个时候头节点需要指向自己两个元素及上
void pop_front(Node* list)
{assert(list);Node* cur list-next;if (cur list) { // 无节点return;}else if(cur-next list) { // 一个节点list-prev list;list-next list;}else {list-next cur-next; // 两个节点以上cur-next-prev list;}free(cur);cur NULL;
}删除–尾删
这个也是简单的因为可以通过头节点直接找到尾节点这个时候就只需要一种情况即可因为创建双链表有一个很好的特性
void pop_back(Node* list)
{assert(list);Node* cur list-prev; // 因为可以获取尾节点if (cur list) {return;}else {cur-prev-next list; // 哪怕是一个节点也和普通情况也是一样list-prev cur-prev; // 这个也是一样free(cur);cur NULL;}}♀ 删除–任意位置
很简单因为这个也不用记录前驱节点也不用找尾节点了只需要考虑两种情况
没有找到找到了
void erase(Node* list, DataType posData)
{assert(list);Node* cur list-next;while (cur-next ! list cur-data ! posData) {cur cur-next;}if (cur-data ! posData) {return;}else {cur-prev-next cur-next;cur-next-prev cur-prev;free(cur);cur NULL;}
}遍历
void travel_front(Node* list)
{assert(list);Node* cur list-next;while (cur ! list) {printf(%d , cur-data);cur cur-next;}printf(\n);
}void travel_back(Node* list)
{assert(list);Node* cur list-prev;while (cur ! list) {printf(%d , cur-data);cur cur-prev;}printf(\n);
}⚗️ 总代码
#include stdlib.h
#include assert.h
#include stdbool.h
#include stdio.h// 有头链表实现简单点typedef int DataType;typedef struct Node {DataType data;struct Node* prev;struct Node* next;
}Node;Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}Node* create_list()
{Node* list (Node*)calloc(1, sizeof(Node));assert(list);list-next list;list-prev list;return list;
}void push_front(Node* list, DataType data)
{assert(list);Node* node create_node(data);node-next list-next;list-next-prev node; // 难点不用担心 nextprev为空的时候node-prev list;list-next node;
}void push_back(Node* list, DataType data)
{assert(list);Node* node create_node(data);node-prev list-prev;list-prev-next node;node-next list;list-prev node;
}
// 找到要插入那个节点的位置节点
void insert(Node* list, DataType posData ,DataType data)
{assert(list);Node* cur list-next;while (cur-next ! list cur-data ! posData) {cur cur-next;}if (cur-data ! posData) { // 思考为什么不能 cur-next ! list ?????return;}else {Node* node create_node(data);node-next cur-next;cur-next-prev node;node-prev cur;cur-next node;}}void pop_front(Node* list)
{assert(list);Node* cur list-next;if (cur list) {return;}else if(cur-next list) {list-prev list;list-next list;}else {list-next cur-next;cur-next-prev list;}free(cur);cur NULL;
}void pop_back(Node* list)
{assert(list);Node* cur list-prev;if (cur list) {return;}else {cur-prev-next list;list-prev cur-prev;free(cur);cur NULL;}}void erase(Node* list, DataType posData)
{assert(list);Node* cur list-next;while (cur-next ! list cur-data ! posData) {cur cur-next;}if (cur-data ! posData) {return;}else {cur-prev-next cur-next;cur-next-prev cur-prev;free(cur);cur NULL;}
}void travel_front(Node* list)
{assert(list);Node* cur list-next;while (cur ! list) {printf(%d , cur-data);cur cur-next;}printf(\n);
}void travel_back(Node* list)
{assert(list);Node* cur list-prev;while (cur ! list) {printf(%d , cur-data);cur cur-prev;}printf(\n);
}int main()
{Node* list create_list();push_front(list, 1);push_front(list, 2);push_front(list, 3);travel_front(list);travel_back(list);push_back(list, 11);push_back(list, 22);push_back(list, 33);travel_front(list);travel_back(list);insert(list, 2, 20);insert(list, 3, 30);insert(list, 33, 330);travel_front(list);travel_back(list);pop_front(list);travel_front(list);travel_back(list);pop_back(list);travel_front(list);travel_back(list);erase(list, 33);travel_front(list);travel_back(list);return 0;
}循环链表约瑟夫环问题
讲一个比较有意思的故事约瑟夫是犹太军队的一个将军在反抗罗马的起义中他所率领的军队被击溃只剩下残余的部队40余人他们都是宁死不屈的人所以不愿投降做叛徒。一群人表决说要死所以用一种策略来先后kill所有人。 于是约瑟夫建议每次由其他两人一起kill一个人而被kill的人的先后顺序是由抽签决定的约瑟夫有预谋地抽到了最后一签在kill了除了他和剩余那个人之外的最后一人他劝服了另外一个没死的人投降了罗马。
我们这个规则是这么定的
在一间房间总共有n个人下标0n-1只能有最后一个人活命。按照如下规则去排除人 所有人围成一圈顺时针报数每次报到q的人将被排除掉被排除掉的人将从房间内被移走然后从被kill掉的下一个人重新报数继续报q再清除直到剩余一人
#include stdio.h
#include stdlib.h
#include assert.h/*
* 用上一个链表也可以。这里采用无头循环双链表实现
* 无头采用再次封装的写法
*/typedef struct Node {int data;struct Node* prev;struct Node* next;
}Node;typedef struct List {Node* headNode;
}List;// 每一个节点创建都是循环
Node* create_node(int data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;node-prev node;node-next node;return node;
}void push_back(List* list, int data)
{assert(list);Node* node create_node(data);if (list-headNode NULL) {list-headNode node;}else {Node* cur list-headNode-prev;node-next list-headNode;list-headNode-prev node;cur-next node;node-prev cur;}
}void erase(List* list, Node* node)
{assert(list);assert(node);// 一个节点if (node-next node) {free(node);node NULL;list-headNode NULL;}else {node-prev-next node-next;node-next-prev node-prev;if (list-headNode node) { // 防止删除头list-headNode node-next;}free(node);node NULL;}
}void travel(List* list)
{Node* cur list-headNode;while (cur-next ! list-headNode) {printf(%d , cur-data);cur cur-next;}printf(%d , cur-data);printf(\n);
}// 只做演示不考虑内存问题
void game_run(int n, int m)
{if (n 0 || m 0) {return;}List list { NULL };for (int i 1; i n; i) {push_back(list, i);}travel(list);Node* cur list.headNode;while (n 1) {// 报数for (int i 1; i m; i) {cur cur-next;}Node* next cur-next;erase(list, cur);// 重置报数cur next;n--;}printf(天选之子: %d\n, cur-data);
}int main()
{game_run(10, 3);return 0;
}
