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

简介: 📖作者介绍: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

相关文章
|
1月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
65 1
|
1月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
45 0
|
1月前
|
算法
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
43 0
|
1月前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
32 0
|
1月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
87 0
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
43 4
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
1月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)