单项循环链表及其带头指针的链表

对于链表我们要仔细深入的学习它，为何呢，因为他是我们在后面学习非线性数据结构的基础，像后面的树，图等结构都是由链表演变出来的，所以我们这篇博客继续探究链表

带头指针的链表

我们上篇博客讲述了带头节点的链表

如图

在这里插入图片描述

然后演示出了一系列公式化的打法

像什么插入删除

//找到前置节点p
//插入
new_node->next=p->next;
p->next=new_node;
//删除
temp=p->next;
p->next=temp->next;
free(temp);

但是我们今天的主角带头指针的链表，你需要考虑的就多了，公式化的打法已经无法满足我们了

看图
在这里插入图片描述

那我们是否能复刻之前的打法，一套代码打天下？

肯定不行，你会发现你想要采用头插法一下就要如下

new_node->next=head;
head=new_node;

当你遇见空的头指针的时候还要if一下，看起来就麻烦。

那么有简化一下书写难度的方法吗？

有的兄弟，有的。

我们可引入一个dummy节点，这个节点是一个临时节点，然后将指针的信息临时传入进去，而后我们就可以继续我们的公式化打法处理了，处理完以后再将地址的值返回。

如图
在这里插入图片描述

这样的好处就又回到了之前的公式化的打法，只要我们注意最后的维护就行了

具体的代码如下

带头指针的链表（代码）

结构定义及其接口


#ifndef CHAINLIST_H
#define CHAIN_LIST_H
//带头指针的单向链表，维护节点也是node
#include"common.h"//定义链表头结构只保存头指针
typedef struct {node_t *header;int cout;}ChainList_t;
//表头放到数据区，放到全局变量
//初始化
void initChainList(ChainList_t *table);
//释放空间
void destoryChainList(ChainList_t *table);//插入
int insertChainListHeader(ChainList_t* table, Element_t data);//头插法
int insertChainListpos(ChainList_t* table,int pos, Element_t data);//按位置插入//删除
int deleteChainListHeader(ChainList_t* table, Element_t data);//打印
void showChainList(const ChainList_t* table);#endif //CHAIN_LIST_H

对操作的具体实现


#include <stdio.h>
#include <stdlib.h>
#include "chainList.h"void initChainList(ChainList_t *table) {table->cout=0;table->header=NULL;
}int insertChainListHeader(ChainList_t *table, Element_t data) {node_t dummy;//定义临时节点dummy.next=table->header;node_t*p=&dummy;node_t* newnode=(node_t*)malloc(sizeof(node_t));if (newnode==NULL) {return -1;}newnode->data=data;newnode->next=p->next;p->next=newnode;;++table->cout;table->header=dummy.next;return 0;
}int insertChainListpos(ChainList_t *table, int pos, Element_t data) {node_t dummy;dummy.next=table->header;//判断边界条件if (data<0||pos>table->cout) {return -1;}//寻找到插入位置node_t *p=&dummy;int node=-1;while (node<pos-1) {p=p->next;node++;}//插入node_t *newnode=(node_t*)malloc(sizeof(node_t));newnode->data=data;newnode->next=p->next;p->next=newnode;++table->cout;table->header=dummy.next;return 0;}
int deleteChainListHeader(ChainList_t *table, Element_t data) {node_t dummy;dummy.next=table->header;node_t* p=&dummy;while (p->next&&p->next->data!=data) {p=p->next;}//判断是否为空if (p->next==NULL) {printf("No find");return-1;}//删除node_t*node=p->next;p->next=node->next;free(node);table->cout--;table->header=dummy.next;return 0;}void destoryChainList(ChainList_t *table) {node_t dummy;dummy.next=table->header;node_t* p=&dummy;node_t*node;while (p->next) {node=p->next;p->next=node->next;free(node);table->cout--;}printf("link list number %d",table->cout);}void showChainList(const ChainList_t *table) {node_t* p=table->header;printf("link list number %d\n:",table->cout);while (p) {printf(" %d ",p->data);p=p->next;}printf("\n");}

其实说实话跟之前的带链表的头指针一样，只不过需要先申请一个节点对节点做包装，而后维护一下表头指针的数据罢了。

我们再来做一下测试

int text2() {ChainList_t stu1;initChainList(&stu1);for (int i=0;i<10;i++) {insertChainListHeader(&stu1,i+100);}insertChainListpos(&stu1,3,300);showChainList(&stu1);destoryChainList(&stu1);}int main() {text2();return 0;
}

这就是对带头指针的链表的实现

但是如果我们再想提出一个需求，就是链表的最后的一个元素要指向第一个元素应该咋整。

这就是引出我们下一个主题

单项循环链表

在开始我们的学习之前，我们可以先思考一个对代码

node_t*p=&header;
while(p->next)
{p=p->next;
}
……node_t*p=&header;
while(p)
{p=p->next
}

你思考就会发现，这两段代码是站在不同的角度进行遍历的，一个是对自己前一个元素进行看的，一个是对自己本身进行看的。

前者更适合插入和删除，而后者更适合遍历。

但是，一到循环链表这两段代码就不管用了，为啥？因为首尾连接了呗。

很自然的，也有两种循环链表的表示方法，一种是带头指针的，一种是不带头指针的

带头指针的

在这里插入图片描述

不带头指针的

在这里插入图片描述

很正常的我们先实现带头指针的

单项循环链表代码

结构定义以及函数接口


#ifndef LINKLOOP_H
#define LINKLOOP_H
typedef int Element;
//节点
typedef struct _loop_node {Element val;struct _loop_node *next;}loopnode;
//头节点
typedef struct {loopnode head;loopnode *tail;int num;
}LinkLoopList;//结构操作
//初始化
void initLinkLoopList(LinkLoopList *link_loop);
//插入(头插，尾插)
int insertLinkLoop(LinkLoopList *link_loop, Element val);
int inserLinkLoopRear(LinkLoopList *link_loop, Element val);
//遍历显示
void showLinkLoop(const LinkLoopList *link_loop);
//删除
int deleteLinkLoop(LinkLoopList *link_loop, Element val);
//释放空间不释放表头
void destoryLinkLoopRear(LinkLoopList *link_loop);#endif //LINKLOOP_H

结构操作的实现


#include "linkLoop.h"
#include <stdio.h>
#include <stdlib.h>void initLinkLoopList(LinkLoopList *link_loop) {//循环链表一开始就要指向自己link_loop->head.next=link_loop->tail=&link_loop->head;link_loop->num=0;}int insertLinkLoop(LinkLoopList *link_loop, Element val) {//先定义一个新节点loopnode*node=malloc(sizeof(loopnode));if (node==NULL)return -1;node->val=val;node->next=link_loop->head.next;link_loop->head.next=node;//判断是否维护尾指针if (link_loop->tail==&link_loop->head) {link_loop->tail=node;}link_loop->num++;return 0;}int inserLinkLoopRear(LinkLoopList *link_loop, Element val) {loopnode*node=malloc(sizeof(loopnode));if (node==NULL)return -1;node->val=val;node->next=link_loop->tail->next;link_loop->tail->next=node;link_loop->tail=node;link_loop->num++;return 0;}void showLinkLoop(const LinkLoopList *link_loop) {loopnode*node=link_loop->head.next;while (node!=&link_loop->head) {printf("%d->", node->val);node=node->next;}printf("\n");}int deleteLinkLoop(LinkLoopList *link_loop, Element val) {loopnode*node=&link_loop->head;while (node->next!=&link_loop->head&&node->next->val!=val) {node=node->next;}if (node->next->val==val) {loopnode *tmp=node->next;node->next=tmp->next;free(tmp);link_loop->num--;}else {printf("not found%d\n",val);}return 0;}void destoryLinkLoopRear(LinkLoopList *link_loop) {loopnode*node=link_loop->head.next;while (node!=&link_loop->head) {loopnode *tmp=node;node=node->next;free(tmp);link_loop->num--;}printf("Table %d element\n",link_loop->num);
}

测试函数


#include "linkLoop.h"void text1() {LinkLoopList table;initLinkLoopList(&table);for (int i = 0; i < 10; i++) {inserLinkLoopRear(&table, i+100);}deleteLinkLoop(&table,101);showLinkLoop(&table);destoryLinkLoopRear(&table);}int main() {text1();return 0;
}