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

  这是我写的我们学校作业的题解，

  空闲空间申请模拟和 ***文件加密!***这两道题都用到了循环链表，但是比刚刚的基础操作要复杂很多，但是基本的思想都是大差不差的，我在本文中提到的一些注意事项，在这两道题中都有体现，比如说开始访问位置，判断是否为空等等，大家如果想要提高一下可以去看看那两道题哈~