本文主要是介绍C语言 带头双向循环链表的基本操作,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
带头双向循环链表的基本操作
- 结构体定义
- 初始化
- 创建新节点
- 头插
- 头删
- 尾插
- 尾删
- 查找
- 在指定位置之后插入
- 删除指定位置的值
- 打印
结构体定义
typedef int DataType;
typedef struct LinkNode
{DataType data;struct LinkNode* prev;struct LinkNode* next;
}LNode;
初始化
有两种初始化方式
第一种你需要在main函数里或者全局定义一个LNode* phead,注意,只需要定义就可以了,然后再调用Init(&phead);
为什么要传地址呢?
因为在Init函数内部我们需要对phead进行操作(分配空间),那么一旦需要对参数进行操作,那就不能只穿本身,而要传地址。
void Init(LNode** pphead)
{*pphead=(LNode*)malloc(sizeof(LNode));(*pphead)->data=-1;(*pphead)->next=(*pphead)->prev=*pphead;
}
这一种的话,不需要在main函数里创建,直接调用Init_1()函数就行。
void Init_1()
{LNode* phead=(LNode*)malloc(sizeof(LNode));phead->data=-1;phead->prev=phead->next=phead;
}
初始化以后,头结点就是这样子了:
创建新节点
函数参数为DataType类型
LNode* CreateNode(DataType x)
{LNode* newnode=(LNode*)malloc(sizeof(LNode));newnode->prev=newnode->next=NULL;//这个地方也将prev和next初始化为newnode自身//因为这两个指针后续都会改变方向,因此初始状态无所谓。return newnode;
}
头插
这里的头插指的是在第一个有效节点之前插入,也就是插入到head的后一个。
我们第一步先把新节点的prev和next设置好,因为这样做不影响链表结构,肯定先把简单的搞了嘛~
然后再修改head->next和head->next->prev(图中1号节点)的指向,至于这两个谁先谁后,那就无所谓了。
头插完以后就是这个样子了
void PushHead(LNode* phead,DataType x)
{LNode* new=CreateNode(x);new->next=phead->next;new->prev=phead;phead->next->prev=new;phead->next=new;
}
头删
头删需要注意的一个点就是判断是否只剩下了一个节点,有些题目会要求头删直至为NULL,有的会要求删到只剩最后一个,我们这里以后者为例
先这么改
再这么改(这两步顺序可以变)
最后再释放掉new节点就可以了(当然考试的时候不释放也行,平时养成这个习惯还是很好的!)
void DelHead(LNode* phead)
{if(phead->next==phead)return;else{LNode* tmp=phead->next;phead->next=tmp->next;tmp->next->prev=phead; free(tmp); }
}
尾插
尾插其实就是在头结点的前一个插,所以简单程度可想而知:
void PushBack(LNode*phead,DataType x)
{LNode*new=CreateNode(x);new->next=phead;new->prev=phead->prev;phead->prev->next=new;phead->prev=new;
}
尾删
跟刚才尾插一个道理,就是头结点的前一个。
void DelBack(LNode*phead)
{LNode* tmp=phead->prev;phead->prev=tmp->prev;tmp->prev->next=phead;free(tmp);
}
查找
查找的时候,有时候对查找的开始位置可能也有限制。如果是带头的双循环链表比较好办,如果是不带头的,如果要从phead开始查找,那么开始访问位置cur就得是phead->prev;
我们这里介绍从phead的next开始访问的情况,其他情况趋同,只需要改变初始访问指针cur的值就可以
LNode* Find(LNode* phead,DataType x)
{LNode* cur=phead->next;while(cur!=phead){if(cur->data==x)return cur;cur=cur->next;}return NULL;
}
在指定位置之后插入
跟头插简直一模一样,就是把参数换了个名儿
void Insert(LNode* pos,DataType x)
{LNode* new=CreateNode(x);new->next=pos;new->prev=pos->prev;pos->prev->next=new;pos->prev=new;
}
删除指定位置的值
跟刚才头删尾删一样,有些题可能需要删到最后一个为止
void DelPos(LNode* pos)
{if(pos->next=pos)return;else{LNode* front=pos->prev;LNode* after=pos->next;front->next=after;after->prev=front;}
}
打印
这个地方比较巧妙,如果想让phead的值第一个被打印,那么循环就要用do while 因为如果用了while(cur!=phead),那么循环完全进不去,因为访问指针cur的初始值就为phead,用do while可以先执行一次,执行完之后cur的指向就不再是phead了,然后再判断循环条件。
void Print(LNode* phead)
{LNode* cur=phead;do{printf("%d ",cur->data);cur=cur->next;} while (cur!=phead);}
有两道非常好的双向循环链表的题推荐给大家:
link
这是我写的我们学校作业的题解,
空闲空间申请模拟和 ***文件加密!***这两道题都用到了循环链表,但是比刚刚的基础操作要复杂很多,但是基本的思想都是大差不差的,我在本文中提到的一些注意事项,在这两道题中都有体现,比如说开始访问位置,判断是否为空等等,大家如果想要提高一下可以去看看那两道题哈~
这篇关于C语言 带头双向循环链表的基本操作的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!