带头结点单链表【详细解析+完整代码】
链表是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系，每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。
文章共6,249字 · 阅读需要大约21分钟
一键AI生成摘要，助你高效阅读
问答
·
C语言单链表
单链表的认识
单链表的定义
它是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系，每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。
结点结构:
带头结点链表结构:
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
带头结点优点
- 保证了每个结点都有前驱结点，因此在链表上第一个结点的操作与其他结点操作一致，无需特殊处理
- 无论链表是否为空，其头指针都是指向头结点的非空指针。可以对空表，非空表的情况进行统一处理。
单链表特点
- 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
- 单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。
单链表的操作
初始化
通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
L->next = NULL;
return true;
}
建立单链表
头插法
头插法顾名思义就是将新结点插入头结点之后，先让新结点的指针指向头结点的下一个结点地址，再让头结点的指针指向新结点地址。注意先后顺序，否则会断链。
LinkList List_HeadInsert(LinkList& L) { //逆序创建链表
InitList(L); //初始化链表
LNode* HeadNode = L;
LNode* NewNode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) { //输入0表示结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
NewNode->next = HeadNode->next; //头插核心
HeadNode->next = NewNode;
scanf_s("%d", &x);
}
return L;
}
头插法的特点：读入数据的顺序和输出的顺序是相反的，是逆序输出，时间复杂度是o(n)。
- tips：如果没有头结点，要特殊处理第一个结点。
尾插法
尾插法简单来说，就是把新加入的节点插入到上一个节点的尾部（头插法是把新加入的节点插入到上一个节点的头部），next存储下一个节点位置的地址，把尾指针指向尾结点地址，最后尾结点指向NULL。再简化语言就是，把新结点连上，让它成为尾结点。
注意：TailNode = NewNode 不要写成 NewNode = TailNode
交换顺序后图解
由此可看出交换顺序会导致插入不了结点
LinkList List_TailInsert(LinkList& L) { //顺序创建链表
InitList(L);
LNode* NewNode, * TailNode = L;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) { //输入0结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
TailNode->next = NewNode; //尾插核心
TailNode = NewNode;
scanf_s("%d", &x);
}
TailNode->next = NULL; //尾指针指向NULL
return L;
}
遍历单链表
这是带头结点的链表，所以先找到第一个结点p，p为空则为空链表，然后遍历到尾结点就行。
void PrintList(LinkList L) {
LNode* p = L->next;
if (!p) printf("空链表");
else
{
printf("遍历链表:");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
单链表的长度
思路就是遍历链表，记录遍历次数就是长度。
int Length(LinkList L) {
LNode* p = L->next;
int len = 0;
while (p) {
p = p->next;
len++;
}
return len;
}
查找操作
按值查找
从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；若整个单链表中没有这样的结点，则返回空。
LNode* LocateElem(LinkList L, int x) {
LNode* p = L->next;
while (p && p->data != x) {
p = p->next;
}
return p;
}
按位查找
从单链表的头结点开始，顺着指针域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域NULL。
LNode* GetElem(LinkList L, int i) {
LNode* p = L;
int j = 0;
if (i<0 || i>Length(L))
return NULL;
else {
while (j < i)
{
p = p->next;
j++;
}
}
return p;
}
当然你也可以从第一个结点开始，往下搜索。我为了方便后续操作找到头结点，所以是从头结点往下搜索。
插入操作
将值为x的新结点插入到单链表L的第i个位置上。从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后利用前插操作，令新结点s的指针域指向p的后继结点，再令结点p的指针域指向新结点*s。
bool Insert(LinkList& L, int i, int x) {
if (i < 1 || i>Length(L))
{
printf("输入位序不合法");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
从插入操作就能体现出GetElem函数从头结点往下搜索的好处，它能找到第一个结点的前驱结点(头结点)，因此就不用特殊处理第一个结点了。
删除操作
将单链表的第 i 个结点删除。先检查删除位置的合法性，然后从头开始遍历，找到i的前驱结点p，被删除结点为s，修改p的指针域，将其指向s的下一个结点，最后再释放结点s的存储空间。
bool Delete(LinkList& L, int i)
{
if (i < 1 || i>Length(L))
{
printf("输入位序不合法");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = p->next;
p->next = s->next;
free(s);
return true;
}
完整代码及实例
完整代码
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
L->next = NULL;
return true;
}
LinkList List_HeadInsert(LinkList& L) { //逆序创建链表
InitList(L); //初始化链表
LNode* HeadNode = L;
LNode* NewNode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) { //输入0表示结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
NewNode->next = HeadNode->next; //头插核心
HeadNode->next = NewNode;
scanf_s("%d", &x);
}
return L;
}
LinkList List_TailInsert(LinkList& L) { //顺序创建链表
InitList(L);
LNode* NewNode, * TailNode = L;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) { //输入0结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
TailNode->next = NewNode; //尾插核心
TailNode = NewNode;
scanf_s("%d", &x);
}
TailNode->next = NULL; //尾指针指向NULL
return L;
}
//遍历操作
void PrintList(LinkList L) {
LNode* p = L->next;
if (!p) printf("空链表");
else
{
printf("遍历链表:");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int Length(LinkList L) {
LNode* p = L->next;
int len = 0;
while (p) {
p = p->next;
len++;
}
return len;
}
LNode* LocateElem(LinkList L, int x) {
LNode* p = L->next;
while (p && p->data != x) {
p = p->next;
}
return p;
}
LNode* GetElem(LinkList L, int i) {
LNode* p = L;
int j = 0;
if (i<0 || i>Length(L))
return NULL;
else {
while (j < i)
{
p = p->next;
j++;
}
}
return p;
}
bool Insert(LinkList& L, int i, int x) {
if (i < 1 || i>Length(L))
{
printf("输入位序不合法");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
bool Delete(LinkList& L, int i)
{
if (i < 1 || i>Length(L))
{
printf("输入位序不合法");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = p->next;
p->next = s->next;
free(s);
return true;
}
int main()
{
LinkList L;
InitList(L);
printf("头插建立链表\n");
List_HeadInsert(L);
PrintList(L);
printf("插入99到第2位\n");
Insert(L, 2, 99);
PrintList(L);
printf("删除第1位\n");
Delete(L, 1);
PrintList(L);
printf("\n\n尾插建立链表\n");
List_TailInsert(L);
PrintList(L);
printf("插入99到第1位\n");
Insert(L, 1, 99);
PrintList(L);
printf("删除第1位\n");
Delete(L, 1);
PrintList(L);
}
测试结果
头插建立链表
输入链表元素（以0结束）：
1 2 3 4 5 6 7 0
遍历链表:7 6 5 4 3 2 1
插入99到第2位
遍历链表:7 99 6 5 4 3 2 1
删除第1位
遍历链表:99 6 5 4 3 2 1
尾插建立链表
输入链表元素（以0结束）:
1 2 3 4 5 6 7 0
遍历链表:1 2 3 4 5 6 7
插入99到第1位
遍历链表:99 1 2 3 4 5 6 7
删除第1位
遍历链表:1 2 3 4 5 6 7
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)