【学习嵌入式day-18-数据结构-循环链表】

循环链表

特点：

头节点的ppre指向链表最后一个节点

最后一个节点的ppre指向第一个节点

节点定义

//节点存放的数据类型
typedef int datatype;
//节点类型
typedef struct  node{datatype data;struct node *ppre;struct node *pnext;
}linknode;

链表创建

申请节点

pnext和ppre都指向自己

需要返回linknode *型的指针

//创建空链表
linknode *create_empty_linklist(void)
{linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(NULL == ptmpnode){perror("fail to malloc");return NULL;}ptmpnode->pnext = ptmpnode->ppre = ptmpnode;return ptmpnode;
}

头插法

（不需要区别第一次插入，每次插入都是一样步骤）

1、申请空间

2、存放数据ptmpnode->data = tmpdata

3、将pnext赋值为头节点的pnext，使申请的节点指向头节点ptmpnode->pnext = phead->pnext

4、将ppre指向头节点ptmpnode->ppre = phead

5、头节点的pnext指向新申请的节点phead->pnext = ptmpnode

6、将后续申请节点的ppre指向新申请的节点ptmpnode->pnext->ppre= ptmpnode

//头插法
int insert_head_linklist(linknode *phead, datatype tmpdata)
{linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(NULL == ptmpnode){perror("fail to malloc");return -1;}ptmpnode->data = tmpdata;           //存放数据ptmpnode->pnext = phead->pnext;     //将新申请的pnext赋值为头节点的pnext，使申请的节点指向头节点ptmpnode->ppre = phead;             //将新申请的ppre指向头结点ptmpnode->ppre->pnext = ptmpnode;   //前一个节点的pnext指向自己// phead->pnext = ptmpnode;            //头结点的pnext指向新申请的节点ptmpnode->pnext->ppre = ptmpnode;   //后一个节点的ppre指向自己//   ptmpnode->pnext->ppre = ptmpnode;   //将后续申请节点的ppre指向新申请的节点return 0;
}

尾插法

1、申请空间

2、存放数据     ptmpnode->data = tmpdata

3、将新申请的节点pnext赋值为头节点  ptmpnode->pnext = phead

4、将新申请的节点ppre赋值为之前的最后一个节点ptmpnode->ppre = phead->ppre(之前的最后一个节点)

5、将之前最后 一个节点的pnext指向新申请节点phead->ppre->pnext = ptmpnode

6、将头节点的ppre指向新申请的节点phead->ppre = ptmpnode

//尾插法
int insert_tail_linklist(linknode *phead, datatype tmpdata)
{linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(NULL == ptmpnode){perror("farl to malloc");return -1;}ptmpnode->data = tmpdata;       //存放数据ptmpnode->pnext = phead;        //将新申请的节点pnext赋值为头节点ptmpnode->ppre = phead->ppre;   //将新申请的节点ppre赋值为之前的最后一个节点ptmpnode->pnext->ppre = ptmpnode;   //后一个节点的ppre指向自己ptmpnode->ppre->pnext = ptmpnode;   //前一个节点的pnext指向自己return 0;
}

遍历

1、指针指向第一个有效节点

2、指针不等于头节点时，进入循环遍历

循环链表最终循环条件由不等于NULL，改为不等于头节点

//遍历
int show_linklist(linknode *phead)
{linknode *ptmpnode = NULL;ptmpnode = phead->pnext;        //将ptmp指针指向第一个有效节点while(ptmpnode != phead)        //ptmp指针不等于头结点时进入循环{printf("%d ", ptmpnode->data);ptmpnode = ptmpnode->pnext; //指针向后走}printf("\n");return 0;
}

查找指定元素

定义一个指针ptmp指向第一个有效节点

当ptmp不等于头结点时，进入循环，if语句判断是否找到指定元素，找到了就返回当前指针

没有找到ptmp指针继续往后走

最后循环结束还没有找到就返回NULL

//查找
linknode *find_linklist(linknode *phead, datatype tmpdata)
{linknode *ptmpnode = NULL;ptmpnode = phead->pnext;        //将ptmp指针指向第一个有效节点while(ptmpnode != phead)        //ptmp指针不等于头结点时进入循环{if(ptmpnode->data == tmpdata)//判断是否找到指定元素{return ptmpnode;        //找到，返回当前指针}ptmpnode = ptmpnode->pnext; //没找到，指针继续向后走}return NULL;                    //循环完成还没找到，返回NULL
}

修改

定义一个指针ptmp指向第一个有效节点

当ptmp不等于头结点时，进入循环，if语句判断是否找到指定元素，找到了就更换为新值

没有找到ptmp指针继续往后走

最后返回0

//修改
int update_linklist(linknode *phead, datatype olddata, datatype newdata)
{linknode *ptmpnode = NULL;ptmpnode = phead->pnext;        //ptmp指针指向第一个有效节点while(ptmpnode != phead)        //ptmp不等于头结点进入循环{if(ptmpnode->data == olddata)   //判断是否遇到olddata{ptmpnode->data = newdata;   //将旧值更新为新值}ptmpnode = ptmpnode->pnext;     //没找到旧值，ptmp指针继续向后走}return 0;
}

删除指定元素

定义两个指针，ptmp指向第一个有效节点，一个释放指针pfree

当ptmp不等于头指针时，进入循环，if语句判断是否找到指定元素，找到了：前一个节点的pnext指向后一个节点，后一个节点的ppre指向前一个节点，pfree指针赋值为ptmp指针，让ptmp向后走一步，释放掉pfree指针所指向的空间。

没有找到指定元素，ptmp向后走继续找

//删除指定元素
int delete_linklist(linknode *phead, datatype tmpdata)
{linknode *ptmpnode = NULL;linknode *pfreenode = NULL;ptmpnode = phead->pnext;    //ptmp指针指向第一个有效节点while(ptmpnode != phead){if(ptmpnode->data == tmpdata){ptmpnode->ppre->pnext = ptmpnode->pnext; //前一个节点的pnext指向后一个节点ptmpnode->pnext->ppre = ptmpnode->ppre;  //后一个节点的ppre指向前一个节点pfreenode = ptmpnode;                    //pfree指针跟着ptmp指针ptmpnode = ptmpnode->pnext;              //ptmp指针向后走free(pfreenode);                         //释放掉pfree所指的空间}else                                         //没有找到要删除的元素，指针ptmp向后走{ptmpnode = ptmpnode->pnext;}}return 0;
}

销毁所有元素

使用二级指针。

定义两个指针，ptmp指向第一个有效节点，pfree指向ptmp，当ptmp不等于头指针时，ptmp向后走，释放掉free指针指向的空间，pfree指向ptmp

循环结束，释放掉头指针，头指针清零，返回0

//销毁
int destory_linklist(linknode **pphead)
{linknode *ptmpnode = NULL;linknode *pfreenode = NULL;ptmpnode = (*pphead)->pnext;       //指针指向第一个有效节点pfreenode = ptmpnode;               //pfree指针指向ptmpwhile(ptmpnode != *pphead)          //ptmp不等于头指针时，进入循环{ptmpnode = ptmpnode->pnext;     //ptmp指针向后走free(pfreenode);                //释放pfree指针pfreenode = ptmpnode;           //pfree走到ptmp指针的位置}free(*pphead);                      //释放头指针*pphead = NULL;                     //头指针清零return 0;
}