1. Toy模板网首页
  2. > Toy博客

带头结点单链表【详细解析+完整代码】

7月前 作者：ChenLin55 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了带头结点单链表【详细解析+完整代码】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

单链表的认识

单链表的定义

它是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系，每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。

结点结构:
编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,c语言,单链表
带头结点链表结构:
编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,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;
}

建立单链表

头插法

头插法顾名思义就是将新结点插入头结点之后，先让新结点的指针指向头结点的下一个结点地址，再让头结点的指针指向新结点地址。注意先后顺序，否则会断链。

编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,c语言,单链表

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。再简化语言就是，把新结点连上，让它成为尾结点。

编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,c语言,单链表
注意：TailNode = NewNode 不要写成 NewNode = TailNode
交换顺序后图解
编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,c语言,单链表
由此可看出交换顺序会导致插入不了结点

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的存储空间。
编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点,链表,数据结构,算法,c语言,单链表文章来源地址https://www.toymoban.com/news/detail-852427.html

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

到了这里，关于带头结点单链表【详细解析+完整代码】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包