登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›数据结构-单向循环链表

数据结构-单向循环链表

东门清心 昨天 10:42
对于单向链表来说，只能从头结点遍历到尾结点，而没有办法从尾结点直接访问首节点，基于单链表的弊端，引入单向循环链表
构造单向循环链表的结点
  1. typedef struct CircularLinkedList
  2. {
  3.         DataType_t                   data; //结点的数据域
  4.         struct CircularLinkedList        *next; //结点的指针域
  6. }CircLList_t;
复制代码
创建一个空单向循环链表
  1. CircLList_t * CircLList_Create(void)
  2. {
  3.         //1.创建一个头结点并对头结点申请内存
  4.         CircLList_t *Head = (CircLList_t *)calloc(1,sizeof(CircLList_t));
  5.         if (NULL == Head)
  6.         {
  7.                 perror("Calloc memory for Head is Failed");
  8.                 exit(-1);
  9.         }
  11.         //2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
  12.         Head->next = Head;
  14.         //3.把头结点的地址返回即可
  15.         return Head;
  16. }
复制代码
创建新的结点
  1. CircLList_t * CircLList_NewNode(DataType_t data)
  2. {
  3.         //1.创建一个新结点并对新结点申请内存
  4.         CircLList_t *New = (CircLList_t *)calloc(1,sizeof(CircLList_t));
  5.         if (NULL == New)
  6.         {
  7.                 perror("Calloc memory for NewNode is Failed");
  8.                 return NULL;
  9.         }
  11.         //2.对新结点的数据域和指针域进行初始化
  12.         New->data = data;
  13.         New->next = NULL;
  15.         return New;
  16. }
复制代码
头部插入元素
  1. bool CircLList_HeadInsert(CircLList_t *Head,DataType_t data)
  2. {
  3.         CircLList_t *New = CircLList_NewNode(data);
  4.         CircLList_t *Phead=Head->next;
  5.         //判断新结点创建是否成功
  6.         if(New == NULL){
  7.                 printf("create new node false\n");
  8.                 return false;
  9.         }
  10.         //判断链表是否为空
  11.         if(Head->next == Head){
  12.                 Head->next = New;
  13.                 New->next = New;
  14.                 return true;
  15.         }
  16.          //链表不为空则执行
  17.        
  18.         while(Phead->next != Head->next){
  19.                 Phead = Phead->next;
  20.         }
  21.         New->next = Head->next;
  22.         Head->next = New;
  23.         Phead->next = New;
  24.         return true;
  26. }
复制代码
尾部插入结点
  1. bool CircLList_TailInsert(CircLList_t *Head,DataType_t data)
  2. {
  3.         CircLList_t *New = CircLList_NewNode(data);
  4.         CircLList_t *Phead=Head->next;
  5.         //判断新结点创建是否成功
  6.         if (NULL == New)
  7.         {
  8.                 perror("Calloc memory for NewNode is Failed");
  9.                 return NULL;
  10.         }
  11.         //判断链表是否为空
  12.         if(Head->next == Head){
  13.                 Head->next = New;
  14.                 New->next = New;
  15.                 return true;
  16.         }
  17.         //寻找尾节点
  18.         while(Phead->next != Head->next){
  19.                 Phead = Phead->next;
  20.         }
  21.        
  22.         Phead->next = New;
  23.         New->next = Head->next;
  24.         return true;
  25. }
复制代码
指定元素后边插入
  1. bool CircLList_DestInsert(CircLList_t *Head,DataType_t destval,DataType_t data)
  2. {
  3.         CircLList_t *New = CircLList_NewNode(data);
  4.         CircLList_t *Phead=Head->next;
  5.         //判断新结点创建是否成功
  6.         if (NULL == New){
  7.                 perror("Calloc memory for NewNode is Failed");
  8.                 return NULL;
  9.         }
  10.         //判断链表是否为空
  11.         if(Head->next == Head){
  12.                 Head->next = New;
  13.                 New->next = New;
  14.                 return true;
  15.         }
  16.         //寻找目标结点
  17.         while(Phead->next != Head->next && Phead->data != destval){
  18.                 Phead = Phead->next;
  19.         }
  20.         //判断循环终止条件是否是寻找到的尾节点
  21.         if(Phead->next == Head->next){
  22.                 if(Phead->data != destval){
  23.                         printf("can not find this value\n");
  24.                         return false;
  25.                 }
  26.                 //CircLList_TailInsert(Head,data);
  27.                
  28.         }
  29.         //Phead = Phead->next;
  30.         New->next = Phead->next;
  31.         Phead->next = New;
  32.         return true;
  33. }
复制代码
遍历打印链表
  1. bool CircLList_Print(CircLList_t *Head)
  2. {
  3.         //对单向循环链表的头结点的地址进行备份
  4.         CircLList_t *Phead = Head;
  5.        
  6.         //判断当前链表是否为空，为空则直接退出
  7.         if (Head->next == Head)
  8.         {
  9.                 printf("current linkeflist is empty!\n");
  10.                 return false;
  11.         }
  13.         //从首结点开始遍历
  14.         while(Phead->next)
  15.         {
  16.                 //把头结点的直接后继作为新的头结点
  17.                 Phead = Phead->next;
  19.                 //输出头结点的直接后继的数据域
  20.                 printf("data = %d\n",Phead->data);
  22.                 //判断是否到达尾结点，尾结点的next指针是指向首结点的地址
  23.                 if (Phead->next == Head->next)
  24.                 {
  25.                         break;
  26.                 }       
  27.         }
  29.         return true;
  30. }
复制代码
删除首结点
  1. bool LList_HeadDel(CircLList_t *Head)
  2. {
  3.         //对单向循环链表的头尾结点的地址进行备份
  4.         CircLList_t *Phead = Head->next;
  5.         CircLList_t *Pphead = Head->next;
  6.         //判断当前链表是否为空，为空则直接退出
  7.         if (Head->next == Head)
  8.         {
  9.                 printf("current linkeflist is empty!\n");
  10.                 return false;
  11.         }
  12.         //遍历链表找到尾结点
  13.         while(Phead->next != Head->next){
  14.                 Phead = Phead->next;
  15.         }
  16.         //进行删除操作，重新连接
  17.         Phead->next = Pphead->next;
  18.         Head->next = Pphead->next;
  19.         Pphead->next = NULL;
  20.         free(Pphead);
  21.         return true;
  23.        
  24. }
复制代码
删除尾结点
  1. bool LList_TailDel(CircLList_t *Head)
  2. {
  3.         //对单向循环链表的头尾结点的地址进行备份
  4.         CircLList_t *Phead = Head->next;
  5.         CircLList_t *Pphead = Head->next;
  6.         //判断当前链表是否为空，为空则直接退出
  7.         if (Head->next == Head)
  8.         {
  9.                 printf("current linkeflist is empty!\n");
  10.                 return false;
  11.         }
  12.         //遍历链表找到尾结点
  13.         while(Phead->next != Head->next){
  14.                 Pphead = Phead;
  15.                 Phead = Phead->next;
  16.         }
  17.         Pphead->next = Head->next;
  18.         Phead->next = NULL;
  19.         free(Phead);
  20.         return true;
  22. }
复制代码
删除指定元素
  1. bool CircLList_DestDel(CircLList_t *Head,DataType_t destval)
  2. {
  3.         //对单向循环链表的目标结点和直接前驱结点的地址进行备份
  4.         CircLList_t *Pphead = Head;//直接前驱的地址
  5.         CircLList_t *Phead = Head->next;
  6.         //判断当前链表是否为空，为空则直接退出
  7.         if (Head->next == Head)
  8.         {
  9.                 printf("current linkeflist is empty!\n");
  10.                 return false;
  11.         }
  12.         //寻找目标结点
  13.         while(Phead->next != Head->next && Phead->data != destval){
  14.                 Pphead = Phead;
  15.                 Phead = Phead->next;
  16.         }
  17.         //判断尾结点的data是不是目标值
  18.         if(Phead->data == destval && Phead->next == Head->next){
  19.                 LList_TailDel(Head);
  20.                 return true;
  21.         }
  22.         //判断首结点的data是不是目标值
  23.         else if(Pphead->next == Head->next){
  24.                 LList_HeadDel(Head);
  25.                 return true;
  26.         }
  27.         //到达链表尾但是没有找到目标元素
  28.         else if(Phead->next == Head->next){
  29.                 printf("do not find this value,do not delete\n");
  30.                 return false;
  31.         }
  32.         Pphead->next = Phead->next;
  33.         Phead->next = NULL;
  34.         free(Phead);
  35.         return true;
  36. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
东门清心
昨天 10:42

0

粉丝关注

12

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫