网站建设公司 - 百度,wordpress重新发布,功能性质网站有哪些网站,莫名接到网站建设电话—————————————本文旨在讨论计算机知识欢迎指正——————————————— 书接上回#xff1a;我们已经了解了链表如何编写与前置节点和头指针两种表示方式#xff0c;下面#xff0c;我们来了解进阶写法———如何实现单向循环链表。 下面#xff0c;我…—————————————本文旨在讨论计算机知识欢迎指正——————————————— 书接上回我们已经了解了链表如何编写与前置节点和头指针两种表示方式下面我们来了解进阶写法———如何实现单向循环链表。 下面我们来梳理一下循环链表的实现方式 这是朴素的链表实现形式 这是我们理想中的循环链表实现形式 这就是我们大体的思路然后我们将要实现它
首先我们第一个难点就是———如何来构造链表的结构体因为我们需要循环那么我们必须要知道尾巴在哪里所以结构体里必须有tail这一容器然后我们还要考虑如果每次我们都用一个迭代器去迭代遍历找尾巴tail的话效率会非常低我们需要一个更好的表示形式
// 定义节点结构
typedef int Element;
typedef struct _loop_node {Element val;//数据域struct _loop_node *next;//地址域指向下一个
} LoopNode;// 定义单向循环链表的头结构
typedef struct {LoopNode header;//头结点LoopNode *tail;//尾巴的容器相当于一个移动指针迭代器int num;//计数器用来遏制循环次数防止无限循环
} LinkLoopList;
于是笔者想到了两种结构分别是头插法和尾插法
1、头插法
int insertLinkLoopHeader(LinkLoopList* link_loop, Element value) {// 1. 先有新节点LoopNode *node malloc(sizeof(LoopNode));if (node NULL) {return -1;}node-val value;//新节点赋值node-next link_loop-header.next;//插到头结点的下一个元素的前面link_loop-header.next node;//更新头结点在新节点的前面// 2. 判断尾指针是否需要更新if (link_loop-tail link_loop-header) {link_loop-tail node;}link_loop-num;return 0;
}
2、尾插法
int insertLinkLoopTail(LinkLoopList* link_loop, Element value) {// 1. 先有新节点LoopNode *node malloc(sizeof(LoopNode));if (node NULL) {return -1;}node-val value;node-next link_loop-tail-next;//尾部插入link_loop-tail-next node;//与原尾部节点衔接link_loop-tail node;//更新尾部link_loop-num;//更新数量return 0;
}
然后我们从头考虑初始化和声明结构体
// 定义节点结构
typedef int Element;
typedef struct _loop_node {Element val;struct _loop_node *next;
} LoopNode;// 定义单向循环链表的头结构
typedef struct {LoopNode header;LoopNode *rear;int num;
} LinkLoopList;
这是初始化
void initLinkLoopList(LinkLoopList* link_loop) {link_loop-header.next link_loop-tail link_loop-header;//头指针和尾指针同时指向头结点link_loop-num 0;
}
删除
int deleteLinkLoopList(LinkLoopList* link_loop, Element value) {LoopNode *node link_loop-header;while (node-next ! link_loop-header node-next-val ! value) {node node-next;}if (node-next-val value) {LoopNode *tmp node-next;node-next tmp-next;free(tmp);//释放空间删除操作--link_loop-num;} else {printf(No %d element!\n, value);}return 0;
}
呈现操作
void showLinkLoopList(const LinkLoopList* link_loop) {LoopNode *node link_loop-header.next;while (node ! link_loop-header) {printf(\t%d, node-val);node node-next;}printf(\n);
}
销毁函数
void destroyLinkLoopList(LinkLoopList* link_loop) {LoopNode *node link_loop-header.next;while (node ! link_loop-header) {LoopNode *tmp node;node node-next;free(tmp);--link_loop-num;}printf(Table %d element!\n, link_loop-num);
} 最后是测试函数
void test01() {LinkLoopList table;initLinkLoopList(table);for (int i 0; i 10; i) {insertLinkLoopRear(table, i 100);}showLinkLoopList(table);printf(\n);deleteLinkLoopList(table, 106);showLinkLoopList(table);destroyLinkLoopList(table);
}/* 以下是几组约瑟夫环的测试答案包括每个被杀者的顺序编号和最后的幸存者:* 当n5k2时被杀者的顺序编号为2, 4, 1, 5最后的幸存者是3。* 当n10k3时被杀者的顺序编号为3, 6, 9, 2, 7, 1, 8, 5, 10最后的幸存者是4。* 当n7k2时被杀者的顺序编号为2, 4, 6, 1, 5, 3最后的幸存者是7。* 当n10k17时最后的幸存者是3*/
void test_Joseph() {}int main() {test01();return 0;
}
————————完结撒花——————希望对你有所帮助
