数据结构（C语言）——单链表的创建及基本功能的实现
1. 链表类型
2. 单链表的定义
单链表是由一连串的 “结点” 组成的，这里我们可以把每一个 “结点” 理解为一个小盒子，这个盒子内部由两部分组成：一部分用来储存数据，我们把它称为 “数据域” ，另一部分用来存放指针，及指向下一个结点的地址，我们把它称为 “指针域” 。像这样，我们从某一个结点访问其指针域即可以找到下一个节点。像这样通过寻找地址的方式进行链式连接，即构成了单链表。
1.单链表结构示意图（头部）：
2. 单链表结构图示（中间部分）：
3.单链表结构示意图（尾部）：
3.单链表的存储结构
单链表为链式储存结构，与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
4.学习单链表须弄明白的一些基本概念
一. 单链表必须元素（如下图）
1. 头指针
头指针，顾名思义，即为一个指针，指向的是头结点的地址
2. 头结点
a. 在单链表中设置头节点的作用是为了方便单链表的特殊操作（如：简化插入、删除操作），这样可以保持单链表操作的统一性。
b. 头结点同样包含了数据域和指针域，其数据域中可存值或者不存值，其指针域指向第一个结点
3. 中间结点
包含数据域指针域，通过结点地址以链式相连。
4.尾结点
注意尾结点的指针域为空(NULL)。
5.数据域
数据域包含多种类型，可以为整型，或者数组型，结构体型等等。
6.指针域
头结点指针域内的指针指向第一个结点的地址，第一个结点指针域的指针域指向第二个结点的地址，直到最后指向尾结点的空(NULL)。
5.代码部分
1.创建结点类型
a.数据域为int型
typedef int ElemType; //定义ElemType为int型，这里的类型根据实际情况而定(可以为数组或者结构体类型)，这里假设为int
typedef struct LinkList //定义结点类型，即LinkList型
{
ElemType data; //数据域，这里用的int形代替（这样声明是为了方便修改数据类型）
struct LinkList *next; //指针域，指向LinkList型的结点
}LinkListNode; //定义结点变量,名称为LinkListNode
b.数据域为结构体类型
typedef struct ElemType //定义结构体类型的数据域，名称为Elemtype
{
int ElemType_1; //ElemType类型中包含的元素
char ElemType_2;
double ElemType_3;
}Elem; //变量名为Elem
typedef struct LinkList
{
Elem data; //该处的数据域为一个结构体类型
struct LinkList *next;
}LinkListNode;
2.创建结点函数
LinkListNode *LinkListNodeCreat(ElemType e) //随机读入一个类型为ElemType的值(这里是int型)
{
/************************************************************************************************/
LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode)); //为结点随机分配内存空间
if(!pTmp)
{
printf("节点内存分配失败！\n");
return NULL; //判空操作
}
memset(pTmp,0x00,sizeof(LinkListNode)); //初始化分配的内存空间为0
/************************************************************************************************/
//以上是一套基本的创建结点的操作
pTmp->data = e; //将int型数据域存入该结点
pTmp->next = NULL; //记住一定将新节点的指针域赋为空！！
return pTmp; //返回指针
}
3.1插入函数(头插法)
这里我们要将一个新结点插入到头结点之后，让该节点作为第一个结点。
int LinkListHeadInsert(LinkListNode *L,ElemType e)//这里L是头结点
{
LinkListNode *NewNode = LinkListNodeCreat(e); //这里先创建一个名叫NewNode的新结点
NewNode->next = L->next;//将头结点中指针域的值赋给新结点的指针域中 PS:此时头结点的指针域有两种情况 1.头结点后无节点，此时相当于将NULL赋给新节点的指针域 2.头结点的指针域指向原链表的第一个结点，此时将头结点的指针域的值赋给新结点指针域，让新结点指针域指向原链表的第一个结点
L->next = NewNode; //再将新结点指针域的值赋给头结点的指针域，使头结点的下一个结点为新结点
return OK;
}
3.2输入函数
int LinkListInput(LinkListNode *L)
{
int i = 0,ElemNum = 0,Element = 0;
printf("请输入要插入结点的个数：\n"); //插入多少个循环多少次
scanf("%d",&ElemNum);
printf("请输入链表当中的元素：\n");
for(i=0 ;i<ElemNum;i++)
{
scanf("%d",&Element);
LinkListHeadInsert(L,Element); //直接调用头插法函数，头插法在调用创建结点
}
return OK;
}
4.输出函数
先判断链表是否为空，为空则不能打印输出！
int LinkListPrint(LinkListNode *L)
{
if(L->next==NULL) //判断头结点是否为空，是则不打印
{
printf("当前链表为空\n");
system("pause");
return 0;
}
LinkListNode *pTmp = L->next;//将pTmp的地址赋值为第一个结点的地址,若没有结点则为NULL
printf("当前链表元素为：\n");
while (pTmp) //判断是否有结点
{
printf("%d ",pTmp->data);//打印出数据域的值
pTmp = pTmp->next; //位移至下一个结点的地址
}
printf("\n");
system("pause");
return OK;
}
5.删除所有元素函数
先判断链表是否为空，为空则不能删除！
int ListDelete(LinkListNode *L)
{
if(L->next==NULL) //判断头结点是否为空，是则无法删除
{
printf("当前链表无元素\n");
system("pause");
return FALSE;
}
LinkListNode *HeadTmp = L; //将头指针的值赋给HeadTmp，作用是循环，直至空
LinkListNode *TestTmp; //中间过渡暂存指针
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp); //清除结点
}
L->next=NULL; //记住这里将头结点的指针域赋值为空！！ 否则使用上面的输出函数会报错，因为之后的结点已经被free了，但L还指向的是一个已经被清除的结点
printf("删除成功！\n");
system("pause");
return OK;
}
6.退出函数
这里和上面删除所有元素函数思想一样，只是把头结点也给free了
int OutList(LinkListNode *L)
{
if(L->next==NULL)
{
return OK;
}
LinkListNode *HeadTmp = L;
LinkListNode *TestTmp;
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp);
}
free(L); //free掉头结点
return OK;
}
全部代码：
这里主要看一下菜单函数和主函数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
//创建结点类型
typedef int ElemType; //定义ElemType为int型，这里的类型根据实际情况而定(可以为数组或者结构体类型)，这里假设为int
typedef struct LinkList //定义结点类型，即LinkList型
{
ElemType data; //数据域，这里用的int形代替（这样声明是为了方便修改数据类型）
struct LinkList *next; //指针域，指向LinkList型的结点
}LinkListNode;
//************************************************
//创建节点函数
LinkListNode *LinkListNodeCreat(ElemType e) //随机读入一个类型为ElemType的值(这里是int型)
{
LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode)); //为结点随机分配内存空间
if(!pTmp)
{
printf("节点内存分配失败！\n");
return NULL; //判空操作
}
memset(pTmp,0x00,sizeof(LinkListNode)); //初始化分配的内存空间为0
pTmp->data = e; //将int型数据域存入该结点
pTmp->next = NULL; //记住一定将新节点的指针域赋为空！！
return pTmp; //返回指针
}
//************************************************
//头插功能函数
int LinkListHeadInsert(LinkListNode *L,ElemType e)//这里L是头结点
{
LinkListNode *NewNode = LinkListNodeCreat(e); //这里先创建一个名叫NewNode的新结点
NewNode->next = L->next;//将头结点中指针域的值赋给新结点的指针域中 PS:此时头结点的指针域有两种情况 1.头结点后无节点，此时相当于将NULL赋给新节点的指针域 2.头结点的指针域指向原链表的第一个结点，此时将头结点的指针域的值赋给新结点指针域，让新结点指针域指向原链表的第一个结点
L->next = NewNode;//再将新结点指针域的值赋给头结点的指针域，使头结点的下一个结点为新结点
return OK;
}
//*************************************************
//输入函数
int LinkListInput(LinkListNode *L)
{
int i = 0,ElemNum = 0,Element = 0;
printf("请输入要插入结点的个数：\n"); //插入多少个循环多少次
scanf("%d",&ElemNum);
printf("请输入链表当中的元素：\n");
for(i=0 ;i<ElemNum;i++)
{
scanf("%d",&Element);
LinkListHeadInsert(L,Element); //直接调用头插法函数，头插法在调用创建结点
}
return OK;
}
//*************************************************
//输出函数
int LinkListPrint(LinkListNode *L)
{
if(L->next==NULL) //判断头结点是否为空，是则不打印
{
printf("当前链表为空\n");
system("pause");
return 0;
}
LinkListNode *pTmp = L->next;//将pTmp的地址赋值为第一个结点的地址,若没有结点则为NULL
printf("当前链表元素为：\n");
while (pTmp) //判断是否有结点
{
printf("%d ",pTmp->data);//打印出数据域的值
pTmp = pTmp->next; //位移至下一个结点的地址
}
printf("\n");
system("pause");
return OK;
}
//************************************************
//删除所有元素函数
int ListDelete(LinkListNode *L)
{
if(L->next==NULL) //判断头结点是否为空，是则无法删除
{
printf("当前链表无元素\n");
system("pause");
return FALSE;
}
LinkListNode *HeadTmp = L; //将头指针的值赋给HeadTmp，作用是循环，直至空
LinkListNode *TestTmp; //中间过渡暂存指针
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp); //清除结点
}
L->next=NULL; //记住这里将头结点的指针域赋值为空！！ 否则使用上面的输出函数会报错，因为之后的结点已经被free了，但L还指向的是一个已经被清除的结点
printf("删除成功！\n");
system("pause");
return OK;
}
//************************************************
//退出函数
int OutList(LinkListNode *L)
{
if(L->next==NULL)
{
return OK;
}
LinkListNode *HeadTmp = L;
LinkListNode *TestTmp;
while(HeadTmp)
{
TestTmp=HeadTmp;
HeadTmp=HeadTmp->next;
free(TestTmp);
}
free(L); //free掉头结点
return OK;
}
//************************************************
//菜单函数
int menu()
{
int n;
system("cls");
printf("===============================链表的基本功能实现=============================\n|\t\t\t\t\t\t\t\t |\n");
printf("|\t 1.增添元素 2.删除所有元素 3.查看元素 |\n");
printf("|\t |\n");
printf("|\t +--------------+ |\n");
printf("|\t | 4.退出 | |\n");
printf("|\t +--------------+ |\n");
printf("==============================================================================\n");
printf("请输入指令[1-4]:");
scanf("%d",&n);
return n;
}
int main()
{
int n;
LinkListNode *L = LinkListNodeCreat(0);//创建头结点L,头指针(及为头结点的地址)
do
{
n=menu();
switch(n)
{
case 1:
LinkListInput(L);
break;
case 2:
ListDelete(L);
break;
case 3:
LinkListPrint(L);
break;
}
}
while(n!=4);
OutList(L); //退出函数
printf("退出成功!\n");
system("pause");
return 0;
}
最后：
链表属于数据结构中较简单的内容，学起来不难的,理解了之后就很容易了,不要被那些人说的吓到了。笔者目前计算机大一在读，水平有限，所写仅供参考学习，如有错误，请在评论区指正、讨论。ps:愿本萌新在以后的学习能多点思考不受禁锢， 知识的学习也能跟得上发际线上移的速度~
转载：https://blog.csdn.net/qq_51527951/article/details/115531195
查看评论