It’s gonna be ok.
一切都会好的。
内容概要 单向循环链表首先来看看图示:
图展示的是一个单向循环链表,他跟以上的单向链表对比只是多了一个指向头结点的 指针,因此,他们的算法几乎是一样的。
第一,设计节点。 单向循环链表的节点跟单向链表完全一致。
第二,初始化空链表。 跟单向链表类似,我们既可以初始化一个带有头结点的空循环链表,也可以不要头结点:
这边把两个步骤放在一起了
linklist init_list(void) // 带有头结点的单循环链表 { linklist head = malloc(sizeof(listnode)); head->next = head;return head; }然后就是插入节点的操作,跟单链表一样,可以去看我前面的文章,链接https://blog.csdn.net/qq_41835250/article/details/107568684
第三,由于单循环链表的特点,删除一个指定的节点时我们可以不需要头指针,而仅仅通过该 待删除节点的指针就可以回溯到他的前一个节点,进而实现删除操作:
void remove_node(linklist delete) { linklist tmp = delete; while(tmp->next != delete) // 从 delete开始,绕一圈找到其前面的节点{ tmp = tmp->next;}tmp->next = delete->next; delete->next = NULL;}第四,移动节点。 在单链表中,移动节点需要三个参数,因为移动的目的地可能在原始位置的前面,由于 没有头指针的情况下无法回溯回去,因此必须要链表的头指针来遍历。但是对于单循环链表
而言则不存在这个问题,链表中的任意一个节点,都可以从另一个任意节点出发找到,因此 移动节点不需要三个参数,请看代码:
第五,查找节点。 同理,单循环链表的查找跟单链表的查找基本是一样的,只是在判断是否遍历完链表的 条件上有所差别:
linklist find_node(linklist mylist, int data) { if(is_empty(mylist)) return NULL;linklist tmp;for(tmp=mylist->next; tmp!=mylist; tmp=tmp->next) {if(data == tmp->data) break; } return tmp==mylist ? NULL : tmp; // 如果遍历回到 mylist 则表示找不到} 双向循环链表通过上面的内容,可以看出来单循环链表的缺点就是每一次遍历都需要从头开始,不能从任意位置来遍历,于是双向循环链表的出现就是来解决这个问题的。
第一,设计节点。 双向链表的节点当然需要两个指针,节点的设计如下:
这里需要注意一下,:节点中的 prev 和 next 指针均是 struct node 型的指针,他们都是指向本结 构体类型的相邻节点的。
第二,初始化空链表。
因为一般情况下我们所使用的大都是带头结点的双向循环链表,所以我就直接使用带头结点的。
第三,插入节点
由于双向循环链表的特征,所以可以有两种插入方式,头插法和尾插法,先来看看头插法的图示步骤:
第 1 步,将新节点的 prev 指针指向 anchor 节点:new->prev = anchor
第 2 步,将新将节点的 next指向 anchor 下一个节点:new->next = anchor->next
第 3 步,将节点 anchor 的 next 指针指向新节点 new:anchor->next = new
第 4 步,将 anchor 原来的下一个节点的 prev 指针指向 new 节点: new->next->prev = new
把它们链接起来就是
尾插法也类似,不过是把节点插在头节点的后面
还是画个图示:
步骤:
第 1 步,将新节点的 prev 指向 anchor 的前节点:new->prev = anchor->prev
第 2 步,将新节点的 next 指向 anchor:new->next = anchor
第 3 步,将 anchor 的前节点的 next 指向新节点:anchor->prev->next = new
第 4 步,将 anchor 的前驱指针指向 new:anchor->prev = new;
代码:
第四,删除节点。
删除一个节点的步骤很简单,只需要将其前趋节点指向其后续节点,将其后续节点指向其前驱节点即可,另外要注意,需将被删除节点的前后向指针置空,使其彻底从链表中脱离 开来,防止错误的访问。
第五,移动节点。
移动节点很好理解,就是一个删除一个移动,画个图就很好理解
代码
第六,查找节点。 节点的查找无非就是对链表进行遍历,从头开始找,找一圈找到为止。直接上代码:
linklist find_node(int data, linklist mylist){if(is_empty(mylist))return NULL;linklist tmp = mylist->next; // 让 tmp从第一个节点开始while(tmp != mylist){if(tmp->data == data)return tmp;tmp=tmp->next; // 不断地向后遍历,查找}return NULL;}如果看到这里你都已经基本看明白了,那么你用双向循环链表写一个学生管理系统什么的已经没问题了,以前我也是学到这里也做过,如果需要欢迎私信。
写到这里突然想起来Linux里还有一个叫做内核链表的东西,下一篇更新一下内核链表。
每一个功能我都写成函数以便于调用,如有问题,欢迎指正。
感谢观看。