(C语言)循环单链表(数据结构)(指针)(循环列表教程)

发布于:2025-04-11 ⋅ 阅读:(35) ⋅ 点赞:(0)

目录

源代码:

代码详解:

1. 头文件和宏定义

2. 类型定义

3. 初始化链表

4. 判断链表是否为空

5. 求链表的长度

6. 清空链表

7. 销毁链表

8. 链表的插入(头插法)

9. 链表的插入(尾插法)

10. 查看链表

11. 单链表插入(在第 i 个结点之前插入)

12. 删除第 i 个结点

13. 查看第 i 个元素

14. 主函数

 知识原理:

1. 基础结构定义

2. 初始化链表

3. 头插法创建链表(动图演示)

4. 尾插法创建链表

5. 遍历链表(带图解)

6. 插入结点(步骤分解)

7. 删除结点(安全版)

8. 内存管理要点

 运行结果:

 单链表教程:


源代码:

#include <stdio.h>
#include <stdlib.h>

//函数结果状态代码
#define OK 1
#define ERROR 0

typedef int Status;//函数返回状态,ok,error
typedef int Elemtype;//链表元素为整形
typedef struct Lnode//定义结构体
{
    Elemtype data;//数据域
    struct Lnode* next;//指针域
}Lnode,*LinkList;//单个结点,整个链表(指向结点的指针)

//初始化链表(建立一个头结点)
Status InitLinkList(LinkList* L){
    *L=(LinkList)malloc(sizeof(Lnode));//分配头结点内存
    if(*L==NULL){
        return ERROR;//判断是否分配成功
    }
    (*L)->next=*L;//头结点的指针域指向他自己(循环链表)
    return OK;
}

//判断链表是否为空
Status IsEmptyLinkList(const LinkList* L){
    if((*L)->next==(*L)){//看看是否指向他自己
        printf("该链表为空!\n");
        return ERROR;
    }else{
        printf("该链表不为空!\n");
        return OK;
    }
}

//求链表的长度
Status LenLinkList(const LinkList* L){
    IsEmptyLinkList(L);//判断链表是否为空
    int i=0;//计数
    Lnode* p;//定义一个临时的结点
    p=(*L)->next;
    while (p!=*L)//仍然是看看是否指向自己(回到头结点)
    {
        i++;//每循环一次计数加一
        p=p->next;
    }
    printf("该链表的长度为:%d\n",i);
    return OK;
}

//清空链表
Status ClearLinkList(LinkList* L){
    Lnode* p;
    Lnode* q;
    p=(*L)->next;
    while (p!=*L)//回到头结点时结束
    {
        q=p;
        p=p->next;
        free(q);
    }
    (*L)->next=*L;
    printf("该链表已清空!\n");
    return OK;
}

//销毁链表
Status DestoryLinkList(LinkList* L){
    LinkList p;//定义一个临时的指向结点的指针
    LinkList q=(*L)->next;
    while (q!=*L)
    {
        p=*L;//储存原来的指针(结点)
        *L=(*L)->next;//往后移动结点
        free(p);//释放原来的指针
    }
    printf("该链表已销毁!\n");
    return OK;
}

//链表的插入,头插法
Status CreateLinkList_h(LinkList* L,int n){//n是插入几条数据
    InitLinkList(L);//创建头结点
    for(int i=0;i<n;i++){
        LinkList newlnode;//创建一个新结点
        newlnode=(Lnode*)malloc(sizeof(Lnode));//为新节点分配内存
        if(newlnode==NULL){
            return ERROR;//判断是否分配成功
        }
        printf("请输入数据:\n");
        scanf("%d",&newlnode->data);
        newlnode->next=(*L)->next;//使新结点指向原指针
        (*L)->next=newlnode;//使头指针指向新结点
    }
    return OK;
}

//链表的插入,尾插入
Status CreateLinkList_r(LinkList* L,int n){
    InitLinkList(L);//创建头结点
    LinkList p=*L;//定义临时尾结点
    for(int i=0;i<n;i++){
        LinkList newlnode;
        newlnode=(Lnode*)malloc(sizeof(Lnode));//给新结点分配内存
        if(newlnode==NULL){
            return ERROR;//判断是否分配成功
        }
        printf("请输入数据:\n");
        scanf("%d",&newlnode->data);
        newlnode->next=*L;//使新结点指向头结点
        p->next=newlnode;//使原结点指向新结点
        p=p->next;//后移一次,定义新的尾结点
    }
    return OK;
}

//查看链表
Status ShowLinkList(const LinkList* L){
    IsEmptyLinkList(L);
    Lnode* p=(*L)->next;//定义个临时结点
    int i=1;
    printf("该链表的数据为:\n");
    while (p!=*L)//指向头结点
    {
        printf("%d : %d\n", i, p->data);  // 打印序号和数据
        i++;            // 序号递增
        p = p->next;    // p 移动到下一个结点
    }
    return OK;
}

//单链表插入,在第i个结点之前插入一个结点
Status InsertLinkList(LinkList *L, int i, Elemtype value)
{
	Lnode* p;//定义临时结点
	p = (*L)->next;//初始化为第一个结点
	int j = 1;
	while (p && j < i - 1)		//找到第i-1个结点(就是i的前面)
	{
		j++;
		p = p->next;
	}
	if (!p || j > i - 1)		//i大于表长+1,或者小于1,插入位置非法
		return ERROR;

	Lnode* newlnode;//定义新结点
	newlnode = (Lnode*)malloc(sizeof(Lnode));
	newlnode->data = value;//插入的数据
	newlnode->next = p->next;
	p->next = newlnode;
	return OK;
}

//删除第i个结点
Status DelLinkList(LinkList* L,int i){
    int j=i;
    i=1;
    Lnode* p=(*L);
    Lnode* q;
    while (j!=i)//找到第i个结点
    {
        i++;
        p=p->next;
    }
    if (p->next == *L || j > i) return ERROR;//检查是否越界
    q=p->next;
    p->next=q->next;
    free(q);
    return OK;
}

//查看第i个元素
Status LocatElem(const LinkList* L,int i){
    int j=i;//赋值给j
    i=1;//初始化i
    LinkList p=(*L)->next;//创建临时结点表示第一个结点
    IsEmptyLinkList(L);//检查是否为空
    //逐步后移,直到i和j相等
    while (i!=j)
    {
        i++;
        p=p->next;
    }
    if (p->next == *L || j > i) return ERROR;//检查是否越界
    printf("第%d个 : %d\n", j, p->data);  // 打印第i个序号,和数据
    return OK;
}

//主函数
int main(){
    LinkList mylist;
    mylist=NULL;
    //CreateLinkList_h(&mylist,4);//头插
    CreateLinkList_r(&mylist,4);//尾插
    ShowLinkList(&mylist);
    InsertLinkList(&mylist, 3, 9);
    ShowLinkList(&mylist);
    LenLinkList(&mylist);
    DelLinkList(&mylist,3);
    ShowLinkList(&mylist);
    LocatElem(&mylist,2);
    IsEmptyLinkList(&mylist);
    ClearLinkList(&mylist);
    DestoryLinkList(&mylist);
}

代码详解:

1. 头文件和宏定义
#include <stdio.h>
#include <stdlib.h>

//函数结果状态代码
#define OK 1
#define ERROR 0
 
  • #include <stdio.h>:引入标准输入输出库,这样就能使用 printf 和 scanf 等函数了。
  • #include <stdlib.h>:引入标准库,可使用 malloc 和 free 等内存管理函数。
  • #define OK 1 和 #define ERROR 0:定义宏,用于表示函数执行的状态,OK 代表操作成功,ERROR 代表操作失败。
2. 类型定义
typedef int Status;//函数返回状态,ok,error
typedef int Elemtype;//链表元素为整形
typedef struct Lnode//定义结构体
{
    Elemtype data;//数据域
    struct Lnode* next;//指针域
}Lnode, * LinkList;//单个结点,整个链表(指向结点的指针)
 
  • typedef int Status:将 int 类型重命名为 Status,用来表示函数的返回状态。
  • typedef int Elemtype:把 int 类型重命名为 Elemtype,意味着链表中存储的元素类型为整数。
  • typedef struct Lnode:定义一个结构体 Lnode,它包含两个成员:
    • Elemtype data:数据域,用于存储结点的数据。
    • struct Lnode* next:指针域,指向链表中的下一个结点。
  • Lnode, * LinkListLnode 表示单个结点的类型,LinkList 表示指向结点的指针类型,也就是整个链表。
3. 初始化链表
//初始化链表(建立一个头结点)
Status InitLinkList(LinkList* L) {
    *L = (LinkList)malloc(sizeof(Lnode));//分配头结点内存
    if (*L == NULL) {
        return ERROR;//判断是否分配成功
    }
    (*L)->next = *L;//头结点的指针域指向他自己(循环链表)
    return OK;
}
 
  • LinkList* L:传入的是指向链表指针的指针,这样就能修改调用者的链表指针了。
  • *L = (LinkList)malloc(sizeof(Lnode)):为头结点分配内存。
  • if (*L == NULL):检查内存分配是否成功,若失败则返回 ERROR
  • (*L)->next = *L:让头结点的 next 指针指向自身,形成循环链表。
  • return OK:若初始化成功,返回 OK
 

图解

 
        +--------+
        |  头结点  |
        +--------+
          |    ^
          |    |
          +----+
4. 判断链表是否为空

//判断链表是否为空
Status IsEmptyLinkList(const LinkList* L) {
    if ((*L)->next == (*L)) {//看看是否指向他自己
        printf("该链表为空!\n");
        return ERROR;
    }
    else {
        printf("该链表不为空!\n");
        return OK;
    }
}
 
  • const LinkList* L:传入指向链表指针的常量指针,不修改链表指针。
  • if ((*L)->next == (*L)):检查头结点的 next 指针是否指向自身,若是则链表为空,输出提示信息并返回 ERROR
  • 反之,输出链表不为空的提示信息并返回 OK
5. 求链表的长度
//求链表的长度
Status LenLinkList(const LinkList* L) {
    IsEmptyLinkList(L);//判断链表是否为空
    int i = 0;//计数
    Lnode* p;//定义一个临时的结点
    p = (*L)->next;
    while (p != *L)//仍然是看看是否指向自己(回到头结点)
    {
        i++;//每循环一次计数加一
        p = p->next;
    }
    printf("该链表的长度为:%d\n", i);
    return OK;
}
 
  • IsEmptyLinkList(L):先判断链表是否为空。
  • int i = 0:初始化计数器。
  • Lnode* p:定义一个临时结点指针。
  • p = (*L)->next:让 p 指向头结点的下一个结点。
  • while (p != *L):当 p 不等于头结点时,继续循环。
    • i++:计数器加一。
    • p = p->nextp 指向下一个结点。
  • 最后输出链表的长度并返回 OK
6. 清空链表
//清空链表
Status ClearLinkList(LinkList* L) {
    Lnode* p;
    Lnode* q;
    p = (*L)->next;
    while (p != *L)//回到头结点时结束
    {
        q = p;
        p = p->next;
        free(q);
    }
    (*L)->next = *L;
    printf("该链表已清空!\n");
    return OK;
}
 
  • Lnode* p 和 Lnode* q:定义两个临时结点指针。
  • p = (*L)->nextp 指向头结点的下一个结点。
  • while (p != *L):当 p 不等于头结点时,继续循环。
    • q = p:用 q 保存当前结点。
    • p = p->nextp 指向下一个结点。
    • free(q):释放 q 指向的结点。
  • (*L)->next = *L:让头结点的 next 指针指向自身,恢复为空链表状态。
  • 输出清空提示信息并返回 OK
7. 销毁链表
//销毁链表
Status DestoryLinkList(LinkList* L) {
    LinkList p;
    LinkList q = (*L)->next;
    while (q != *L) {
        p = q;
        q = q->next;
        free(p);
    }
    free(*L);
    printf("该链表已销毁!\n");
    return OK;
}
 
  • LinkList p 和 LinkList q:定义两个链表指针。
  • q = (*L)->nextq 指向头结点的下一个结点。
  • while (q != *L):当 q 不等于头结点时,继续循环。
    • p = q:用 p 保存当前结点。
    • q = q->nextq 指向下一个结点。
    • free(p):释放 p 指向的结点。
  • free(*L):释放头结点。
  • 输出销毁提示信息并返回 OK
8. 链表的插入(头插法)
//链表的插入,头插法
Status CreateLinkList_h(LinkList* L, int n) {//n是插入几条数据
    InitLinkList(L);//创建头结点
    for (int i = 0; i < n; i++) {
        LinkList newlnode;//创建一个新结点
        newlnode = (Lnode*)malloc(sizeof(Lnode));//为新节点分配内存
        if (newlnode == NULL) {
            return ERROR;//判断是否分配成功
        }
        printf("请输入数据:\n");
        scanf("%d", &newlnode->data);
        newlnode->next = (*L)->next;//使新结点指向原指针
        (*L)->next = newlnode;//使头指针指向新结点
    }
    return OK;
}
 
  • InitLinkList(L):初始化链表,创建头结点。
  • for (int i = 0; i < n; i++):循环 n 次,插入 n 个结点。
    • LinkList newlnode:定义一个新结点指针。
    • newlnode = (Lnode*)malloc(sizeof(Lnode)):为新结点分配内存。
    • if (newlnode == NULL):检查内存分配是否成功,若失败则返回 ERROR
    • scanf("%d", &newlnode->data):从用户输入读取数据存入新结点的数据域。
    • newlnode->next = (*L)->next:让新结点的 next 指针指向头结点原来指向的结点。
    • (*L)->next = newlnode:让头结点的 next 指针指向新结点。
  • 最后返回 OK
 

图解
插入前:

 
        +--------+    +--------+
        |  头结点  | -> |  结点1  |
        +--------+    +--------+
 

插入后:

 
        +--------+    +--------+    +--------+
        |  头结点  | -> |  新结点 | -> |  结点1  |
        +--------+    +--------+    +--------+
9. 链表的插入(尾插法)
//链表的插入,尾插入
Status CreateLinkList_r(LinkList* L, int n) {
    InitLinkList(L);//创建头结点
    LinkList p = *L;//定义临时尾结点
    for (int i = 0; i < n; i++) {
        LinkList newlnode;
        newlnode = (Lnode*)malloc(sizeof(Lnode));//给新结点分配内存
        if (newlnode == NULL) {
            return ERROR;//判断是否分配成功
        }
        printf("请输入数据:\n");
        scanf("%d", &newlnode->data);
        newlnode->next = *L;//使新结点指向头结点
        p->next = newlnode;//使原结点指向新结点
        p = p->next;//后移一次,定义新的尾结点
    }
    return OK;
}
 
  • InitLinkList(L):初始化链表,创建头结点。
  • LinkList p = *L:定义一个临时尾结点指针,初始指向头结点。
  • for (int i = 0; i < n; i++):循环 n 次,插入 n 个结点。
    • LinkList newlnode:定义一个新结点指针。
    • newlnode = (Lnode*)malloc(sizeof(Lnode)):为新结点分配内存。
    • if (newlnode == NULL):检查内存分配是否成功,若失败则返回 ERROR
    • scanf("%d", &newlnode->data):从用户输入读取数据存入新结点的数据域。
    • newlnode->next = *L:让新结点的 next 指针指向头结点。
    • p->next = newlnode:让原尾结点的 next 指针指向新结点。
    • p = p->next:更新尾结点指针,使其指向新结点。
  • 最后返回 OK
10. 查看链表
//查看链表
Status ShowLinkList(const LinkList* L) {
    IsEmptyLinkList(L);
    Lnode* p = (*L)->next;//定义个临时结点
    int i = 1;
    printf("该链表的数据为:\n");
    while (p != *L)//指向头结点
    {
        printf("%d : %d\n", i, p->data);  // 打印序号和数据
        i++;            // 序号递增
        p = p->next;    // p 移动到下一个结点
    }
    return OK;
}
 
  • IsEmptyLinkList(L):先判断链表是否为空。
  • Lnode* p = (*L)->next:定义一个临时结点指针,指向头结点的下一个结点。
  • int i = 1:初始化序号。
  • while (p != *L):当 p 不等于头结点时,继续循环。
    • printf("%d : %d\n", i, p->data):打印序号和结点的数据。
    • i++:序号加一。
    • p = p->nextp 指向下一个结点。
  • 最后返回 OK
11. 单链表插入(在第 i 个结点之前插入)
//单链表插入,在第i个结点之前插入一个结点
Status InsertLinkList(LinkList* L, int i, Elemtype value)
{
    Lnode* p;//定义临时结点
    p = (*L);
    int j = 0;
    while (p && j < i - 1)		//找到第i-1个结点(就是i的前面)
    {
        j++;
        p = p->next;
    }
    if (!p || j > i - 1)		//i大于表长+1,或者小于1,插入位置非法
        return ERROR;

    Lnode* newlnode;//定义新结点
    newlnode = (Lnode*)malloc(sizeof(Lnode));
    newlnode->data = value;//插入的数据
    newlnode->next = p->next;
    p->next = newlnode;
    return OK;
}
 
  • Lnode* p:定义一个临时结点指针,初始指向头结点。
  • int j = 0:初始化计数器。
  • while (p && j < i - 1):循环找到第 i - 1 个结点。
    • j++:计数器加一。
    • p = p->nextp 指向下一个结点。
  • if (!p || j > i - 1):检查插入位置是否合法,若不合法则返回 ERROR
  • Lnode* newlnode:定义一个新结点指针。
  • newlnode = (Lnode*)malloc(sizeof(Lnode)):为新结点分配内存。
  • newlnode->data = value:将插入的值存入新结点的数据域。
  • newlnode->next = p->next:让新结点的 next 指针指向第 i 个结点。
  • p->next = newlnode:让第 i - 1 个结点的 next 指针指向新结点。
  • 最后返回 OK
12. 删除第 i 个结点
//删除第i个结点
Status DelLinkList(LinkList* L, int i) {
    if (i < 1) return ERROR;
    int j = 1;
    Lnode* p = *L;
    Lnode* q;
    while (p->next != *L && j < i) {
        j++;
        p = p->next;
    }
    if (p->next == *L || j > i) return ERROR;
    q = p->next;
    p->next = q->next;
    free(q);
    return OK;
}
 
  • if (i < 1):检查 i 是否小于 1,若小于 1 则返回 ERROR
  • int j = 1:初始化计数器。
  • Lnode* p = *L:定义一个临时结点指针,初始指向头结点。
  • while (p->next != *L && j < i):循环找到第 i - 1 个结点。
    • j++:计数器加一。
    • p = p->nextp 指向下一个结点。
  • if (p->next == *L || j > i):检查 i 是否超出链表长度,若超出则返回 ERROR
  • q = p->next:用 q 保存第 i 个结点。
  • p->next = q->next:让第 i - 1 个结点的 next 指针指向第 i + 1 个结点。
  • free(q):释放第 i 个结点的内存。
  • 最后返回 OK
13. 查看第 i 个元素
//查看第i个元素
Status LocatElem(const LinkList* L, int i) {
    if (i < 1) return ERROR;
    int j = 1;
    LinkList p = (*L)->next;
    IsEmptyLinkList(L);//检查是否为空
    while (p != *L && j < i) {
        j++;
        p = p->next;
    }
    if (p == *L) {
        printf("位置超出链表长度!\n");
        return ERROR;
    }
    printf("第%d个 : %d\n", i, p->data);  // 打印第i个序号,和数据
    return OK;
}
 
  • if (i < 1):检查 i 是否小于 1,若小于 1 则返回 ERROR
  • int j = 1:初始化计数器。
  • LinkList p = (*L)->next:定义一个临时结点指针,指向头结点的下一个结点。
  • IsEmptyLinkList(L):检查链表是否为空。
  • while (p != *L && j < i):循环找到第 i 个结点。
    • j++:计数器加一。
    • p = p->nextp 指向下一个结点。
  • if (p == *L):检查 i 是否超出链表长度,若超出则输出提示信息并返回 ERROR
  • printf("第%d个 : %d\n", i, p->data):打印第 i 个结点的数据。
  • 最后返回 OK
14. 主函数
//主函数
int main() {
    LinkList mylist;
    mylist = NULL;
    //CreateLinkList_h(&mylist,4);//头插
    CreateLinkList_r(&mylist, 4);//尾插
    ShowLinkList(&mylist);
    InsertLinkList(&mylist, 3, 9);
    ShowLinkList(&mylist);
    LenLinkList(&mylist);
    DelLinkList(&mylist, 3);
    ShowLinkList(&mylist);
    LocatElem(&mylist, 2);
    IsEmptyLinkList(&mylist);
    ClearLinkList(&mylist);
    DestoryLinkList(&mylist);
}
 
  • LinkList mylist:定义一个链表指针。
  • mylist = NULL:初始化链表指针为 NULL
  • CreateLinkList_r(&mylist, 4):使用尾插法插入 4 个结点。
  • ShowLinkList(&mylist):显示链表内容。
  • InsertLinkList(&mylist, 3, 9):在第 3 个结点之前插入值为 9 的结点。
  • ShowLinkList(&mylist):再次显示链表内容。
  • LenLinkList(&mylist):计算并输出链表长度。
  • DelLinkList(&mylist, 3):删除第 3 个结点。
  • ShowLinkList(&mylist):再次显示链表内容。
  • LocatElem(&mylist, 2):查看第 2 个结点的数据。
  • IsEmptyLinkList(&mylist):判断链表是否为空。
  • ClearLinkList(&mylist):清空链表。
  • DestoryLinkList(&mylist):销毁链表。

 知识原理:

1. 基础结构定义
typedef struct Lnode {
    int data;           // 数据域(存储整型数据)
    struct Lnode* next; // 指针域(指向下一个结点)
} Lnode, *LinkList;     // Lnode是结点类型,LinkList是指向结点的指针类型

图示

[data|next] → [data|next] → ... → [头结点]

2. 初始化链表
Status InitLinkList(LinkList* L) {
    *L = (LinkList)malloc(sizeof(Lnode)); // 创建头结点
    (*L)->next = *L; // 头结点指向自己,形成空环
    return OK;
}

原理

  • 分配头结点内存

  • 让头结点的next指向自己,表示空链表

  • 内存状态

    头结点
     ↓
    [NULL|] ←┐
      ↑_____┘

3. 头插法创建链表(动图演示)
newNode->next = (*L)->next;  // ① 新结点指向原首结点
(*L)->next = newNode;        // ② 头结点指向新结点

插入过程

初始:头结点 → [A]
步骤1:newNode → [A]
步骤2:头结点 → newNode → [A]

4. 尾插法创建链表
newNode->next = *L;  // 新结点指向头结点
p->next = newNode;   // 尾结点指向新结点
p = newNode;         // 更新尾指针

特点

  • 需要维护尾指针p

  • 插入顺序与数据顺序一致


5. 遍历链表(带图解)
while (p != *L) {  // 回到头结点时停止
    printf("%d ", p->data);
    p = p->next;
}

遍历路径

头结点 → [10] → [20] → [30] → 头结点
  ↑_________________________|

6. 插入结点(步骤分解)
// 在位置i前插入
newNode->next = p->next;  // ① 新结点指向原i位置结点
p->next = newNode;        // ② i-1结点指向新结点

示例(在第2个位置插入9):

插入前:头结点 → [10] → [20] → [30]
插入后:头结点 → [10] → [9] → [20] → [30]

7. 删除结点(安全版)
q = p->next;        // ① 保存待删除结点
p->next = q->next;  // ② 绕过待删除结点
free(q);            // ③ 释放内存

边界检查

if (p->next == *L) return ERROR; // 防止删除不存在的结点

8. 内存管理要点
操作 关键步骤 注意事项
创建结点 malloc分配内存 检查是否分配成功
删除结点 free释放内存 必须先保存next再释放
清空链表 循环释放所有结点 最后重置头结点指针
销毁链表 先清空再释放头结点 将头指针设为NULL

 运行结果:

请输入数据:
12
请输入数据:
23
请输入数据:
34
请输入数据:
45
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 34
4 : 45
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 9
4 : 34
5 : 45
该链表不为空!
该链表的长度为:5
该链表不为空!
该链表的数据为:
1 : 12
2 : 23
3 : 34
4 : 45
该链表不为空!
第2个 : 23
该链表不为空!
该链表已清空!
该链表已销毁!

请按任意键继续. . .

 单链表教程:

(C语言)单链表(2.0)数据结构(指针,单链表教程)-CSDN博客

 注:该代码是本人自己所写,可能不够好,不够简便,欢迎大家指出我的不足之处。如果遇见看不懂的地方,可以在评论区打出来,进行讨论,或者联系我。上述内容全是我自己理解的,如果你有别的想法,或者认为我的理解不对,欢迎指出!!!如果可以,可以点一个免费的赞支持一下吗?谢谢各位彦祖亦菲!!!!!