前面我们学到线性表的顺序存储结构(顺序表),发现它有着明显的缺点:插入和删除元素时需要频繁的移动元素,运算效率低。必须按事先估计的最大元素个数申请连续的存储空间。存储空间估计大了,造成浪费空间;估计小了,容易产生溢出,空间难以扩大。
采用链式存储结构的线性表(链表)可以克服以上的不足。
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(存放的数据元素)+指针(指示下一个元素存储位置,单、双链表的最后一个节点除外,它们存储的是一个空指针NULL),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
节点的结构如下图所示:
对节点的定义如下:
typedef struct LNode
{int data;//节点的数据域struct LNode *next;//节点的指针域
}LNode,*LinkList;
这里我们用typedef进行类型重定义,把struct LNode定义一个新名字LNode,把struct LNode定义成另一个新名字* LinkLIst。这里注意:LNode和*LinkLIst是一样的。但在使用上LNode和LinkList是不同的。

注:我们假设节点里存放的是int型数据。
单链表由多个节点依次连接而成,结构如下图:

最开始的那个节点是头节点,头节点的数据域是不存放数据的,指针域指向链表的第一个节点。在单链表的定义中,带有头节点的称为带头节点单链表,不带头节点的称为不带头节点单链表。我们这次介绍的就是带头节点单链表。
单链表的基本操作:
- 1.链表的初始化
- 2.创建单链表
- 2.1.用头插法创建单链表
- 2.2.用尾插法创建单链表
- 3.打印单链表
- 4.插入元素
- 4.1.在指定位置插入元素
- 4.2.在指定节点后面插入元素(后插)
- 4.3.在指定节点前面插入元素(前插)
- 5.按位查找元素
- 6.按值查找元素
- 7.求表长
- 8.删除元素
- 9.判断是不是空表
- 10.销毁单链表
- **全部代码:**
1.链表的初始化
我们先用malloc函数分配一个头节点,让头节点的指针域指向空指针,对产生的头节点的情况要进行判断。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>typedef struct LNode
{int data;//数据域struct LNode *next;//指针域
}LNode,*LinkList;bool InitList(LinkList &L)//初始化单链表
{L = (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L == NULL)return false;//内存不足,分配失败L->next = NULL;//头节点之后还没有节点return true;
}
2.创建单链表
链表的建立有两种方式,一种是头插法,一种是尾插法。由于单链表的头插和尾插性质,有时候常用来解决链表的逆置问题。
2.1.用头插法创建单链表
头插法:把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反,输出时为倒序。
用通俗的语言来说,有一家奶茶店开业了,人们去买奶茶,A第一个排队,而后来的B插到A前面排队,后来的C插到B前面排队,这样排队下去A到了最后一位。节点的插入也是这样子。假设往里面放入元素1 2 3 4 5,有趣的是存放进去的元素则是5 4 3 2 1,刚好是相反的,这种特性可以用于链表的逆置。
下图是节点s插入到单链表中:

操作步骤:创建指针p指向头节点,用malloc函数申请空间给节点s,接下来让节点s的指针域等于头节点的指针域,头节点的指针域指向节点s。把这段代码放到循环里面,进行多次头插操作。
void Inita(LinkList &L)//初始化单链表(使用的是头插)
{printf("请输入你要创建的单链表的长度:");int a;scanf("%d", &a);printf("请输入%d个数:",a);for (int i = 1; i <= a; i++){LNode *p = L;LNode *s = (LNode*)malloc(sizeof(LNode));//申请空间给新的节点sscanf("%d", &s->data);//输入值放入插入节点的数据域s->next = p->next;//改变插入节点的指针域p->next = s;//使头节点的指针域指向插入的节点}
}
2.2.用尾插法创建单链表
尾插法就是在链表的尾部依次插入节点,和你去买奶茶依次排队是一个情况的,一个个排队。假设输入元素1 2 3 4 5,那么存储进去的元素也是 1 2 3 4 5。
操作步骤:先找到链表的最后一个节点,然后在最后一个节点后面插入节点。接下来的操作和头插差不多了。
void Initb(LinkList &L)
{LNode *p = L;while (p->next)//用循环让p指向尾节点p = p->next;int a;printf("请输入你要创建的单链表的长度:");scanf("%d", &a);printf("请输入%d个数:", a);for (int i = 1; i <= a; i++){LNode *s = (LNode*)malloc(sizeof(LNode));//创建一个新节点sp->next = s;//此时的p指向尾节点,让p指向sscanf("%d", &s->data);//输入值放入s节点的数据域s->next = NULL;//让s节点的指针指向空指针p = p->next;//让p指针指向此时的尾指针(s节点)}
}
3.打印单链表
打印单链表就只能一个个从前往后打印。
void PrintList(LinkList &L)//打印单链表
{LNode *p=L;//创建一个p指针指向头节点printf("表中的元素为:");while (p->next!=NULL)//判断下一个节点是不是空指针,也可以简写为p->next{p = p->next;//p指向下一个节点printf("%d ", p->data);}printf("\n");
}
4.插入元素
4.1.在指定位置插入元素
在指定位置插入元素,我们只需要找到要插入元素位置的前一个节点就可以了,然后修改节点指针域即可。
bool ListInsert(LinkList &L)//插入操作,把一个值插入要求的位置
{int i,e;printf("请输入你要插入的元素和要插入的位置:");scanf("%d %d",&e, &i);if (i < 1){printf("数据非法,插入失败\n");return false;//输入的i小了}LNode *p;//创建一个p指针int j = 0;p = L;//L指向头节点,头节点是第0个节点(不存数据)while (p != NULL&&j < i - 1)//这里进行循环,为了让p指向要插入位置的前一个节点{p = p->next;//p指向下一个节点j++;}if (p == NULL)//判断i值是否大了{printf("数据非法,插入失败\n");return false;}LNode *s = (LNode*)malloc(sizeof(LNode));//创建一个新的节点s->data = e;//把要插入的值放入节点ss->next = p->next;//把p的指针复制给sp->next = s;//把p的指针改为指向sprintf("插入成功\n");return true;//插入成功,返回true(1)
}
注意:
1.在p指向下一个节点的循环那里,是j<i-1,而不是j<i。
2.改变指针域的时候要先改变插入节点的指针域,后改变前面那个节点的指针域。
4.2.在指定节点后面插入元素(后插)
后插比4.1的在指定位置插入元素更容易,因为要插入位置前面的那个元素已经传给你了。代码实现大同小异。后插的过程中要注意指针域的修改。
bool InsertNextNode(LNode *p, int e)//后插操作
{if (p == NULL)return false;LNode *q = (LNode*)malloc(sizeof(LNode));//新建一个节点qif (q == NULL)return false;//内存分配失败q->next = p->next;q->data = e;p->next = q;return true;
}
4.3.在指定节点前面插入元素(前插)
前插的实现有两种方法,这里我主要介绍更容易操作的那种方法。
方法1:假设要在节点p前面进行插入节点,那么就是循环查找p的前面那一个节点q,然后对q节点进行后插。
bool InsertPriorNode(LinkList &L,LNode *p, int e)//前插操作
{//。。。。。。return 0;
}
方法二:移形换位。在p节点后插一个节点q,然后把p和q的值交换就好了。
bool InsertPriorNode(LNode *p, int e)//前插操作
{if (p == NULL)return false;LNode *q = (LNode*)malloc(sizeof(LNode));//新建一个节点qif (q == NULL)return false;q->next = p->next;//把p的指针复制给q的指针p->next = q;//把p的指针指向qq->data = p->data;//让q的数据域等于p的数据域p->data = e;//让p的数据域等于元素e的值return true;
}
5.按位查找元素
bool GetElem(LinkList &L)//按位查找
{int i;printf("你要查找第几个元素:");scanf("%d", &i);if (i < 1){printf("输入的数值非法,删除失败\n");return false;}int j = 0;LNode *p = L;while (p != NULL&&j < i )//为了让p指针指向要删除的节点{p = p->next;//p循环指向下一个节点j++;}if (p == NULL)//判断输入的i是不是大了{printf("输入的数值非法,删除失败\n");return false;}if (p->next == NULL)return false;printf("第%d个元素是%d\n", i, p->data);return true;
}
注意: 与插入元素不同的是,这次的p只需要指向要删除的节点即可,不必指向被删除节点的前一个节点,所以在循环那里就是j < i。
6.按值查找元素
按值查找元素就是一个个去比对,从头到尾比对。
void LocateElem(LinkList &L )//按值查找
{int e;int i = 0;int ret= 1;printf("请输入你要查找的元素值:");scanf("%d", &e);LNode* p = L;//新建指针p指向头节点while (p->next != NULL){i++;p=p->next;//p指针指向下一个节点if (p->data == e){printf("找到了,元素%d在第%d个位置\n", e, i);ret = 0;//break;}}if (ret)printf("找不到元素%d\n", e);
}
注意: 在while循环那里判断语句不能写成p!=NULL,不然就会陷入死循环。如果你需要只找到一个元素就退出,可以在if语句里面加上break。
7.求表长
求表长就是从头节点依次往后扫描,扫到空指针的时候停下来,每次扫描就len++,最后返回len。
int Length(LinkList &L)//求表长
{int len=0;LNode *p = L;//新建一个指针p指向头节点while (p->next != NULL){p = p->next;//p指向下一个节点len++;}return len;//返回表长
}
8.删除元素
操作步骤:先找到要删除节点前面的那个节点,然后修改指针域,用free释放要删除节点的空间,删除操作完成。
bool ListDelete(LinkList &L)//删除操作
{int i;printf("请输入你要删除的元素的位置:");scanf("%d", &i);if (i < 1)//判断输入i是不是小了{printf("输入的数值非法,删除失败\n");return false;}int j = 0;LNode *p = L;//新建一个p节点指向头节点while (p!= NULL&&j < i-1)//为了让p节点指向要删除节点的前一个节点{p = p->next;//让p指针一直循环指向下一个节点j++;}if (p==NULL)//判断输入的i是不是大了{printf("输入的数值非法,删除失败\n");return false;}if (p->next == NULL)return false;LNode *q = p->next;//用q指向要删除的节点int e = q->data;//把要删除的节点的值放入到e里面去p->next = q->next;//把要删除的节点的指针放到p里面去free(q);//释放空间printf("删除成功,删除的是第%d个元素,这个元素的数值是%d\n",i,e);return true;
}
9.判断是不是空表
判断是不是空表,只需判断头节点的指针是不是指向空指针。如果是空表,返回1,如果不是空表,返回0。
bool Empty(LinkList &L)//判断是不是空表
{return (L == NULL);//如果是空表,返回1。如果不是空表,返回0。
}
10.销毁单链表
因为单链表的一个个节点是用malloc申请的空间,这一部分的空间在内存的堆区,系统不会自动回收堆区的空间,所以要用free函数去把一个个的节点释放空间。
void DestroyList(LinkList &L)//销毁单链表
{char a;getchar();printf("是否销毁单链表(Y/N):");scanf("%c", &a);if (a == 'Y'){LNode *p, *q;//创建两个指针p = L;//指针p指向头节点while (p != NULL)//当头结点的指针域不为0,即不是链尾时{q = p->next;//让q指向头结点的后续结点free(p);//把p指针指向的节点空间释放,但是p指针还存在。p = q;//让p和q都指向后续结点,此时p和q指针指向的都是下一个节点,接下来重复这一段的操作就好了。}L = NULL;//让头指针指向空指针printf("销毁成功\n");}elseprintf("未销毁单链表\n");
}
全部代码:
#include<stdio.h>
#include<stdlib.h>typedef struct LNode
{int data;//数据域struct LNode *next;//指针域
}LNode,*LinkList;
// LinkList:强调这是一个单链表
// LNode*:强调这是一个节点
// LNode=*LinkListbool InitList(LinkList &L)//初始化单链表
{L = (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L == NULL)return false;//内存不足,分配失败L->next = NULL;//头节点之后还没有节点return true;
}bool Empty(LinkList &L)//判断是不是空表
{return (L == NULL);//如果是空表,返回1。如果不是空表,返回0。
}//void Inita(LinkList &L)//初始化单链表(使用的是头插)
//{
// printf("请输入你要创建的单链表的长度:");
// int a;
// scanf("%d", &a);
// printf("请输入%d个数:",a);
// for (int i = 1; i <= a; i++)
// {
// LNode *p = L;
// LNode *s = (LNode*)malloc(sizeof(LNode));//申请空间给新的节点s
// scanf("%d", &s->data);//输入值放入插入节点的数据域
// s->next = p->next;//改变插入节点的指针域
// p->next = s;//使头节点的指针域指向插入的节点
// }
//}void Initb(LinkList &L)//初始化单链表(使用的是尾插)
{LNode *p = L;while (p->next)//用循环让p指向尾指针p = p->next;int a;printf("请输入你要创建的单链表的长度:");scanf("%d", &a);printf("请输入%d个数:", a);for (int i = 1; i <= a; i++){LNode *s = (LNode*)malloc(sizeof(LNode));//创建一个新节点sp->next = s;//让p指向sscanf("%d", &s->data);//输入值放入s节点的数据域s->next = NULL;//让s节点的指针指向空指针p = p->next;//让p指针指向此时的尾指针(s节点)}
}bool ListInsert(LinkList &L)//插入操作,把一个值插入要求的位置
{int i,e;printf("请输入你要插入的元素和要插入的位置:");scanf("%d %d",&e, &i);if (i < 1){printf("数据非法,插入失败\n");return false;//输入的i小了}LNode *p;//创建一个p指针int j = 0;p = L;//L指向头节点,头节点是第0个节点(不存数据)while (p != NULL&&j < i-1 ){p = p->next;//p指向下一个节点j++;}if (p == NULL)//判断i值是否大了{printf("数据非法,插入失败\n");return false;}LNode *s = (LNode*)malloc(sizeof(LNode));//创建一个新的节点s->data = e;//把要插入的值放入节点ss->next = p->next;//把p的指针复制给sp->next = s;//把p的指针改为指向sprintf("插入成功\n");return true;//插入成功,返回true(1)
}bool GetElem(LinkList &L)//按位查找
{int i;printf("你要查找第几个元素:");scanf("%d", &i);if (i < 1){printf("输入的数值非法,删除失败\n");return false;}int j = 0;LNode *p = L;while (p != NULL&&j < i )//为了让p节点指向要查找的节点{p = p->next;//p循环指向下一个节点j++;}if (p == NULL)//判断输入的i是不是大了{printf("输入的数值非法,删除失败\n");return false;}if (p->next == NULL)return false;printf("第%d个元素是%d\n", i, p->data);return true;
}int Length(LinkList &L)//求表长
{int len=0;LNode *p = L;//新建一个指针指向头节点while (p->next != NULL){p = p->next;//指向下一个节点len++;}return len;//返回表长
}void LocateElem(LinkList &L )//按值查找
{int e;int i = 0;int ret= 1;printf("请输入你要查找的元素值:");scanf("%d", &e);LNode* p = L;//新建指针p指向头节点while (p->next != NULL)//这里不能写成p!=NULL,不然就会陷入死循环,出不来{i++;p=p->next;//p指针指向下一个节点if (p->data == e){printf("找到了,元素%d在第%d个位置\n", e, i);ret = 0;}}if (ret)printf("找不到元素%d\n", e);
}bool ListDelete(LinkList &L)//删除操作
{int i;printf("请输入你要删除的元素的位置:");scanf("%d", &i);if (i < 1)//判断输入i是不是小了{printf("输入的数值非法,删除失败\n");return false;}int j = 0;LNode *p = L;//新建一个p节点指向头节点while (p!= NULL&&j < i-1)//为了让p节点指向要删除节点的前一个节点{p = p->next;//p循环指向下一个节点j++;}if (p==NULL)//判断输入的i是不是大了{printf("输入的数值非法,删除失败\n");return false;}if (p->next == NULL)return false;LNode *q = p->next;//用q指向要删除的节点int e = q->data;//把要删除的节点的值放入到e里面去p->next = q->next;//把要删除的节点的指针放到p里面去free(q);//释放空间printf("删除成功,删除的是第%d个元素,这个元素的数值是%d\n",i,e);return true;
}void PrintList(LinkList &L)//打印单链表
{LNode *p=L;//创建一个p指针指向头节点printf("表中的元素为:");while (p->next!=NULL)//判断下一个节点是不是空指针,也可以简写为p->next{p = p->next;printf("%d ", p->data);}printf("\n");
}void DestroyList(LinkList &L)//销毁单链表
{char a;getchar();printf("是否销毁单链表(Y/N):");scanf("%c", &a);if (a == 'Y'){LNode *p, *q;//创建两个指针p = L;//指针p指向头节点while (p != NULL)//当头结点的指针域不为0,即不是链尾时{q = p->next;//让q指向头结点的后续结点free(p);//把p指针指向的空间释放了,但是p指针还存在。p = q;//让p和q都指向后续结点,此时p和q指针指向的都是下一个节点,接下来重复这一段的操作就好了。}L = NULL;//让头指针指向空指针printf("销毁成功\n");}elseprintf("未销毁单链表\n");
}void main()
{LinkList L;//声明一个指向单链表的指针,此时并没有创建一个节点InitList(L);//初始化一个空表//Inita(L);//头插Initb(L);//尾插PrintList(L);//打印单链表ListInsert(L);//插入元素PrintList(L);//打印单链表GetElem(L);//按位查找int len=Length(L);//求表长printf("表长是:%d\n",len);LocateElem(L);//按值查找ListDelete(L);//删除元素PrintList(L);//打印单链表int a=Empty(L);//判断是不是空表if (!a)printf("不是空表\n");elseprintf("空表\n");DestroyList(L);//销毁单链表
}bool InsertNextNode(LNode *p, int e)//后插操作
{if (p == NULL)return false;LNode *q = (LNode*)malloc(sizeof(LNode));//新建一个节点qif (q == NULL)return false;//内存分配失败q->next = p->next;q->data = e;p->next = q;return true;
}bool InsertPriorNode(LinkList &L,LNode *p, int e)//前插操作
{//方法1,循环查找p的前面那一个节点q,然后对q节点进行后插。我感觉是不如方法二好使。return 0;
}bool InsertPriorNode(LNode *p, int e)//前插操作
{//方法2,移形换位。在p节点后插一个节点q,然后把p和q的值交换就好了。if (p == NULL)return false;LNode *q = (LNode*)malloc(sizeof(LNode));if (q == NULL)return false;q->next = p->next;p->next = q;q->data = p->data;p->data = e;return true;
}
代码实现:

在上面的代码中有很多重复的代码,是可以写成函数替换的,这是详细讲解就没有去用函数替换。单链表的代码可以多看看,多理解理解。
如果有什么不懂的,文中有错误的可以私信联系我,非常感谢。
觉得这篇博客对你有帮助的话可以点个赞呀。


















