目录
一、循环链表的概念
二、有头单链表
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.头插
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后面插入元素
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位置上得元素
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;
}
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;
}
四、无头循环单链表
- 最后一个节点的
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