备案控制台
开发者社区 开发与运维 文章 正文

数据结构与算法——有头无头循环链表详解

2023-04-26 254
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 📖作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋和数据结构阶段>——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的📖作者主页：热爱编程的小K📖专栏链接：数据结构🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🐾————————————————版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/qq_72

d5a6207d65b14284a019985bdad14f82.png

015d54a49827495a89b8e9f16af7153d.png目录

一、循环链表的概念

二、有头单链表

1.准备

2.创建新节点

3.浏览

4.头插

5.尾插

6.查找

7.任意插

8.删除pos位置上得元素

9.修改

10.求表长

11.判表空

12.测试代码

13.综合代码

三、无头单链表

综合代码

四、无头循环单链表

综合代码

一、循环链表的概念

对于单链表以及双向链表，其就像一个小巷，无论怎么样最终都能从一端走到另一端，然>而循环链表则像一个有传送门的小巷，因为循环链表当你以为你走到结尾的时候，其实你又回到了开头。

循环链表和非循环链表其实创建的过程以及思路几乎完全一样，唯一不同的是，非循环链>表的尾结点指向空（NULL），而循环链表的尾指针指向的是链表的开头。通过将单链表的的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）

二、有头单链表

1.准备

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

2.创建新节点

Node* createNode(int newData)

{

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

newNode->data = newData;

newNode->next = NULL;

return newNode;

}

3.浏览

void watchData(Node* head)

{

if (NULL == head) return;        //防呆

Node* curNode = head->next;

printf("List:");

while (curNode)

{

 printf("%d ", curNode->data);

 curNode = curNode->next;

}

printf("\n");

}

4.头插

d44a1552f4e1481287025f3a5e7edcd1.png

void push_front(Node* head, int insertData)

{

if (NULL == head) return;

Node* pNode = createNode(insertData);

pNode->next = head->next;

head->next = pNode;

}

5.尾插

void push_back(Node* head, int insertData)

{

if (NULL == head) return;

while (head->next) head = head->next;

head->next = createNode(insertData);

}

6.查找

找到第pos个位置并返回地址，否则返回NULL

Node* findNode(Node* head, int pos)

{

if (pos <= 0) return NULL;

if (NULL == head) return NULL;

for (int i = 0; i < pos; i++)

{

 if (head)

  head = head->next;

 else

  return NULL;

}

return head;

}

7.任意插

在pos后面插入元素

776447b505b9421c92f2483e8fdf9244.png

void push_pos(Node* head, int pos, int insertData)

{

if ( NULL == head ) return;

Node* posNode = findNode(head, pos);  //找pos位置

Node* pNew = createNode(insertData);

pNew->next = posNode->next;

posNode->next = pNew;

}

8.删除pos位置上得元素

229e02f39dbe4b7c93db889fe5e2e7da.png

void pop_pos(Node* head, int pos)

{

if (NULL == head) return;

Node* posNode = findNode(head, pos);     //找删除节点

if (!posNode) return;                    //没找到

if ( 1 == pos )                        //要删除的为第一个节点

{

 head->next = posNode->next;

 free(posNode);

 posNode = NULL;

 return;

}

Node* posLift = findNode(head, pos - 1);       //找到要删除的上一个节点

posLift->next = posNode->next;

free(posNode);

posNode = posLift = NULL;

}

9.修改

void modif_pos(Node* head, int pos,int modifData)

{

if (NULL == head) return;

Node* posNode = findNode(head,pos);

if (!posNode) return;

posNode->data = modifData;

}

10.求表长

int listLenth(Node* head)

{

int Lenth = 0;

while (head->next)

{

 Lenth++;

 head = head->next;

}

return Lenth;

}

11.判表空

bool empty_List(Node* head)

{

if ( head->next == NULL )

{

 return true;

}

return false;

}

12.测试代码

int main()

{

Node* List = NULL;

Node* pHead = createNode(0);

List = pHead;

printf("%s\n", empty_List(List) ? "true" : "false");

for (int i = 0; i < 11; i++)

{

 push_back(List,i+1);

}

watchData(List);

push_front(List,99);

watchData(List);

//printf("%d", findNode(List, 4)->data);

push_pos(List, 5, 11);

watchData(List);

pop_pos(List, 5);

watchData(List);

modif_pos(List, 1, 88);

watchData(List);

printf("%d", listLenth(List));

printf("\n%s\n", empty_List(List) ? "true" : "false");

return 0;

}

a7e66d3e31ee4fa387531eda0c40b89a.png

13.综合代码

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

//创建新节点

Node* createNode(int newData);

//浏览

void watchData(Node* head);

//头插

void push_front(Node* head,int insertData);

//尾插

void push_back(Node* head, int insertData);

//找到第pos个位置并返回地址，否则返回NULL

Node* findNode(Node* head, int pos);

//在pos后面插入元素

void push_pos(Node* head, int pos, int insertData);

//删除pos位置上得元素

void pop_pos(Node* head, int pos);

//修改

void modif_pos(Node* head, int pos,int modifData);

//求表长

int listLenth(Node* head);

//判断表是否为空

bool empty_List(Node* head);

int main()

{

Node* List = NULL;

Node* pHead = createNode(0);

List = pHead;

printf("%s\n", empty_List(List) ? "true" : "false");

for (int i = 0; i < 11; i++)

{

 push_back(List,i+1);

}

watchData(List);

push_front(List,99);

watchData(List);

//printf("%d", findNode(List, 4)->data);

push_pos(List, 5, 11);

watchData(List);

pop_pos(List, 5);

watchData(List);

modif_pos(List, 1, 88);

watchData(List);

printf("%d", listLenth(List));

printf("\n%s\n", empty_List(List) ? "true" : "false");

return 0;

}

Node* createNode(int newData)

{

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

newNode->data = newData;

newNode->next = NULL;

return newNode;

}

void watchData(Node* head)

{

if (NULL == head) return;        //防呆

Node* curNode = head->next;

printf("List:");

while (curNode)

{

 printf("%d ", curNode->data);

 curNode = curNode->next;

}

printf("\n");

}

void push_front(Node* head, int insertData)

{

if (NULL == head) return;

Node* pNode = createNode(insertData);

pNode->next = head->next;

head->next = pNode;

}

void push_back(Node* head, int insertData)

{

if (NULL == head) return;

while (head->next) head = head->next;

head->next = createNode(insertData);

}

Node* findNode(Node* head, int pos)

{

if (pos <= 0) return NULL;

if (NULL == head) return NULL;

for (int i = 0; i < pos; i++)

{

 if (head)

  head = head->next;

 else

  return NULL;

}

return head;

}

void push_pos(Node* head, int pos, int insertData)

{

if ( NULL == head ) return;

Node* posNode = findNode(head, pos);  //找pos位置

Node* pNew = createNode(insertData);

pNew->next = posNode->next;

posNode->next = pNew;

}

void pop_pos(Node* head, int pos)

{

if (NULL == head) return;

Node* posNode = findNode(head, pos);     //找删除节点

if (!posNode) return;                    //没找到

if ( 1 == pos )                        //要删除的为第一个节点

{

 head->next = posNode->next;

 free(posNode);

 posNode = NULL;

 return;

}

Node* posLift = findNode(head, pos - 1);       //找到要删除的上一个节点

posLift->next = posNode->next;

free(posNode);

posNode = posLift = NULL;

}

void modif_pos(Node* head, int pos,int modifData)

{

if (NULL == head) return;

Node* posNode = findNode(head,pos);

if (!posNode) return;

posNode->data = modifData;

}

int listLenth(Node* head)

{

int Lenth = 0;

while (head->next)

{

 Lenth++;

 head = head->next;

}

return Lenth;

}

bool empty_List(Node* head)

{

if ( head->next == NULL )

{

 return true;

}

return false;

}

三、无头单链表

  • 无头单链表，即不含有头结点的单项链表
  • 与有头单链表原理一样，但是要注意对于头结点的插入和删除要变更头结点
  • 在面向过程编程时，需要注意函数参数应为二级指针

综合代码

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

//创建新节点

Node* createNode(int newData);

//浏览

void watchData(Node* head);

//头插

void push_front(Node** head, int insertData);

//尾插

void push_back(Node** head, int insertData);

//找到第pos个位置并返回地址，否则返回NULL

Node* findNode(Node* head, int pos);

//在pos后面插入元素

void push_pos(Node** head, int pos, int insertData);

//删除pos位置上得元素

void pop_pos(Node** head, int pos);

//修改

void modif_pos(Node* head, int pos, int modifData);

//求表长

int listLenth(Node* head);

//判断表是否为空

bool empty_List(Node* head);

int main()

{

Node* List = NULL;  //创建链表

for (int i = 0; i < 11; i++)

{

 push_front(&List, i);

}

watchData(List);

push_back(&List, 9999);

watchData(List);

push_pos(&List, 5, 6666);

watchData(List);

pop_pos(&List, 4);

watchData(List);

modif_pos(List, 7, 8888);

watchData(List);

printf("%d ", listLenth(List));

printf("\n%s", empty_List(List) ? "true" : "false");

return 0;

}

Node* createNode(int newData)

{

//1 申请内存

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

//2 数据赋值

newNode->data = newData;

newNode->next = NULL;

//3 返回

return newNode;

}

void watchData(Node* head)

{

printf("List:");

while (head)

{

 printf("%d ", head->data);

 //切换到下一个节点

 head = head->next;

}

printf("\n");

}

void push_front(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* pNode = createNode(insertData);

//2 新节点的next指针指向原来的第一个结点

pNode->next = *head;

//3 新节点成为第一个节点

*head = pNode;

}

void push_back(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* pNode = *head;

Node* newNode = createNode(insertData);

if ( *head )//*head为真，非空链表

{

 //找到最后一个

 while ( pNode->next ) pNode = pNode->next;

 pNode->next = newNode;

}

else //空链表

{

 *head = newNode;

}

}

Node* findNode(Node* head, int pos)

{

if (pos <= 0) return NULL;

if (NULL == head) return NULL;

for (int i = 1; i < pos; i++)

{

 if (head)

  head = head->next;

 else

  return NULL;

}

return head;

}

void push_pos(Node** head, int pos, int insertData)

{

if (NULL == head) return;

Node* pNew = createNode(insertData);

if ( 0 == pos )     //相当于头插

{

 pNew->next = *head;

 *head = pNew;

 return;

}

Node* posNode = findNode(*head, pos);    //找pos位置

if (NULL == posNode) return;            //找不到，直接返回

//posNode的下一个节点成为新节点的下一个节点

pNew->next = posNode->next;

//新节点成为posNode的下一个节点

posNode->next = pNew;

}

void pop_pos(Node** head, int pos)

{

if (NULL == head) return;

Node* posNode = findNode(*head, pos);     //找删除节点

if (!posNode) return;                     //没找到

if (1 == pos)                        //要删除的为第一个节点

{

 //第二个成为新的头结点

 (*head) = (*head)->next;

 //释放节点

 free(posNode);

 posNode = NULL;

 return;

}

Node* posLift = findNode(*head, pos - 1);       //找到要删除的上一个节点

//posLift的next指针指向posNode的下一个节点

posLift->next = posNode->next;

//释放第pos个节点的内存

free(posNode);

//忘掉解除占用内存段的地址

posNode = posLift = NULL;

}

void modif_pos(Node* head, int pos, int modifData)

{

if (NULL == head) return;

Node* posNode = findNode(head, pos);

if (!posNode) return;

posNode->data = modifData;

}

int listLenth(Node* head)

{

int Lenth = 0;

while (head)

{

 Lenth++;

 head = head->next;

}

return Lenth;

}

bool empty_List(Node* head)

{

if (head->next == NULL)

{

 return true;

}

return false;

}

四、无头循环单链表

9df3d2eb3c4a4af6867504e032a63022.png

  • 最后一个节点的next指针指向第一个节点
  • 效率提高了一点，可以从前往后查找，也可以从后往前查找

综合代码

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

//创建新节点

Node* createNode(int newData);

//浏览

void watchData(Node* head);

//头插

void push_front(Node** head, int insertData);

//尾插

void push_back(Node** head, int insertData);

//找到第pos个位置并返回地址，否则返回NULL

Node* findNode(Node* head, int pos);

//在pos后面插入元素

void push_pos(Node** head, int pos, int insertData);

//删除pos位置上得元素

void pop_pos(Node** head, int pos);

//修改

void modif_pos(Node* head, int pos, int modifData);

//求表长

int listLenth(Node* head);

//判断表是否为空

bool empty_List(Node* head);

//找最后一个节点

Node* findtailNode(Node** head);

int main()

{

Node* List = NULL;  //创建链表

for (int i = 0; i < 12; i++)

{

 push_back(&List, i);

}

watchData(List);

push_front(&List, 999);

watchData(List);

//printf("%d ", findNode(List, 1)->data);

push_pos(&List, 13, 2222);

watchData(List);

pop_pos(&List, 1);

watchData(List);

pop_pos(&List, 13);

watchData(List);

modif_pos(List, 5, 777);

watchData(List);

printf("%d ", listLenth(List));

printf("\n%s", empty_List(List) ? "true" : "false");

return 0;

}

Node* createNode(int newData)

{

//1 申请内存

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

//2 数据赋值

newNode->data = newData;

newNode->next = NULL;

//3 返回

return newNode;

}

void watchData(Node* head)

{

printf("List:");

if (NULL != head)

{

 Node* pTemp = head;

 while (1)

 {

  printf("%d ", pTemp->data);

  if (pTemp->next == head)   break;    //pTemp是最后一个节点

  pTemp = pTemp->next;                 //切换到下一个节点

 }

}

printf("\n");

}

void push_front(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* pNode = createNode(insertData);

//2 找到尾结点

Node* tailNode = findtailNode(head);

//3 新节点的next指针指向原来的第一个结点

pNode->next = *head;

//4 新节点成为第一个节点

*head = pNode;

//5 tailNode的next指针指向第一个节点

tailNode->next = *head;

}

void push_back(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* newNode = createNode(insertData);

if (*head)//*head为真，非空链表

{

 //找到最后一个

 Node* pNode = findtailNode(head);

 newNode->next = *head; //新节点的next指针指向头,newNode->next = pNode->next;

 pNode->next = newNode; //新节点成为原来的尾节点的下一个节点

}

else //空链表

{

 //顺序不能地颠倒，*head为空

 *head = newNode;         //新节点成为头结点

 newNode->next = *head;   //新节点的next指针指向头结点

}

}

Node* findNode(Node* head, int pos)

{

if (pos <= 0) return NULL;

if (NULL == head) return NULL;

Node* pTemp = head;

for (int i = 1; i < pos; i++)

{

 if (pTemp->next == head) return NULL;

 else pTemp = pTemp->next;

}

return pTemp;

}

void push_pos(Node** head, int pos, int insertData)

{

if (NULL == head) return;

Node* pNew = createNode(insertData);

Node* tailNode = findtailNode(head);

if (0 == pos)     //相当于头插

{

 pNew->next = *head;

 *head = pNew;

 tailNode->next = pNew;

 return;

}

Node* posNode = findNode(*head, pos);    //找pos位置

if (NULL == posNode) return;             //找不到，直接返回

//posNode的下一个节点成为新节点的下一个节点

pNew->next = posNode->next;

//新节点成为posNode的下一个节点

posNode->next = pNew;

}

void pop_pos(Node** head, int pos)

{

if (NULL == head) return;

Node* pHead = *head;

Node* posNode = findNode(*head, pos);     //找删除节点

if (!posNode) return;                     //没找到

//找尾结点

Node* tailNode = findtailNode(head);

if ( NULL == tailNode )

{

 printf("pop_pos中tailNode没有找到 %d", __LINE__);  

 return;

}

if (1 == pos)                        //要删除的为第一个节点

{

 if ( posNode->next == pHead )   //链表中就一个节点

 {

  free(*head);

  *head = NULL;

 }

 else

 {

  //让第二个节点成为新的头结点

  *head = pHead->next;

  //尾结点的下一个指向头结点

  tailNode->next = *head;

  free(pHead);

  pHead = NULL;

 }

 return;

}

Node* posLift = findNode(*head, pos - 1);       //找到要删除的上一个节点

//posLift的next指针指向posNode的下一个节点

posLift->next = posNode->next;

//释放第pos个节点的内存

free(posNode);

//忘掉解除占用内存段的地址

posNode = posLift = NULL;

}

void modif_pos(Node* head, int pos, int modifData)

{

if (NULL == head) return;

Node* posNode = findNode(head, pos);

if (!posNode) return;

posNode->data = modifData;

}

int listLenth(Node* head)

{

int Lenth = 0;

Node* pTemp = head;

while (1)

{

 Lenth++;

 if (pTemp->next == head) break;

 pTemp = pTemp->next;

}

return Lenth;

}

bool empty_List(Node* head)

{

if (head->next == head)

{

 return true;

}

return false;

}

Node* findtailNode(Node** head)

{

if (NULL == head)return NULL;

Node* pTemp = *head;

while (1)

{

 if (pTemp->next == *head)return pTemp;

 pTemp = pTemp->next;

}

}

版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_72157449/article/details/128754708

文章标签：
C++
关系型数据库
Linux
Windows
MySQL
算法
关键词：
数据结构链表
数据结构循环链表
算法链表
数据结构与算法链表
算法循环链表
热爱编程的小K
目录
相关文章
是基德吖
|
4天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
是基德吖
24 8
【数据结构OJ题】合并两个有序链表
是基德吖
|
6天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
是基德吖
11 2
【数据结构OJ题】移除链表元素
是基德吖
|
6天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
是基德吖
9 1
【数据结构OJ题】链表中倒数第k个结点
是基德吖
|
6天前
|
存储 DataX C语言
【数据结构】双链表
数据结构中的双链表
是基德吖
14 1
【数据结构】双链表
是基德吖
|
3天前
【数据结构OJ题】链表分割
牛客题目——链表分割
是基德吖
5 0
【数据结构OJ题】链表分割
是基德吖
|
4天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
是基德吖
6 0
【数据结构OJ题】链表的回文结构
是基德吖
|
6天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
是基德吖
9 0
【数据结构OJ题】链表的中间结点
是基德吖
|
6天前
【数据结构OJ题】反转链表
力扣题目——反转链表
是基德吖
10 0
【数据结构OJ题】反转链表
weixin_836869520
|
19天前
|
算法 Java
Java数据结构与算法：双向链表
Java数据结构与算法：双向链表
weixin_836869520
17 0
weixin_836869520
|
19天前
|
算法 Java
Java数据结构与算法：循环链表
Java数据结构与算法：循环链表
weixin_836869520
16 0

热门文章

最新文章

  • 1
    Redis数据结构精讲：选择与应用实战指南
  • 2
    【Python进阶（七）】——Series数据结构
  • 3
    深入浅出Redis（一）：对象与数据结构
  • 4
    中间件应用合理使用缓存和数据结构
  • 5
    深入浅出Redis（十一）：Redis四种高级数据结构：Geosptial、Hypeloglog、Bitmap、Bloom Filter布隆过滤器
  • 6
    数据结构可视化 Graphviz在Python中的使用 [树的可视化]
  • 7
    深入浅出数据结构之布隆过滤器
  • 8
    数据结构/C++：位图 & 布隆过滤器
  • 9
    【数据结构】二叉树的三种遍历（非递归讲解）
  • 10
    数据结构/C++：红黑树
  • 1
    C语言字符串知识点和算法总结
    35
  • 2
    八种常见顺序存储的算法
    33
  • 3
    【机器学习】在使用K-means算法之前，如何预处理数据？
    107
  • 4
    【机器学习】比较分层聚类（Hierarchical Clustering）和K-means聚类算法
    154
  • 5
    算法刷题小技巧【持续补充~】
    14
  • 6
    【计算机图形学】实验三 用Cohen-Sutherland裁剪算法实现直线段裁剪
    263
  • 7
    【计算机图形学】实验二 用扫描线算法实现多边形填充
    67
  • 8
    【计算机图形学】实验一 DDA算法、Bresenham算法
    69
  • 9
    【计网·湖科大·思科】实验三 总线型以太网的特性、集线器和交换机的区别、交换机的自学习算法
    33
  • 10
    Python 数据结构和算法实用指南（四）（4）
    109

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
    • 下一篇
    2024年阿里云免费云服务器及学生三百通用额度申请教程参考