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

数据结构（2）—单链表（带头结点和不带头结点）

9月前 作者：阿尼亚哭哭 分类：Toy博客 阅读(55) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构（2）—单链表（带头结点和不带头结点）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、定义说明：

        单链表是通过一组任意的存储单元来存储线性表中的数据元素。每个结点都有data数据域（用来存放数据元素）和next指针域（用来存放后继节点的地址）。

        对于顺序表，单链表可以解决顺序表需要一整个大量的连续的存储单元的缺点，单链表的元素可以离散地分布在存储空间中，即非随机存取的存储结构，不能直接找到表中某个特定的结点，当查找某个特定的结点时，需要从表头开始一个一个遍历。因为单链表附加了指针域，缺点就是存储空间增大。

        单链表有带头结点和不带头结点两种类型。引入头结点的好处：①便于第一个结点的处理：增加头结点后，第一个结点的地址保存在头结点的指针域中，则对链表的第一个元素的操作和其他元素相同，无需进行特殊处理。（若单链表不带头结点，则第一个结点无前驱结点，在其前插入结点和删除该结点操作复杂些。）②便于空表和非空表的统一处理：增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。

二、带头结点的程序说明

2.1 单链表的存储结构

typedef struct LNode {
	Elemtype data; //数据域
	struct LNode* next; //指针域
}LNode, * LinkList;

2.2 初始化

bool Initlist(LinkList &L)
{
	//L = (LinkList)malloc(sizeof(LNode)); //c语言定义头结点
	L = new LNode; //定义头结点
	L->next = NULL; //尾指针为空，头结点指向空
	return true;
}

2.3 头插法建立单链表

void List_HeadInsert(LinkList& L)
{
	int n;  //输入元素的个数
	cout << "头插法--请输入元素个数n：" << endl;
	cin >> n;
	LinkList s;  //定义指针变量s
	cout << "请依次输入元素：" << endl;
	while (n--)
	{
		s = new LNode; //定义变量结点
		cin >> s->data;
		s->next = L->next;
		L->next = s;
	}
}

2.4 尾插法建立单链表

void List_TailInsert(LinkList& L)
{
	int n; //输入元素的个数
	cout << "尾插法--请输入元素个数n：" << endl;
	cin >> n;
	LinkList r; //定义一个表尾指针
	r = L;
	LinkList s;//定义指针变量s
	cout << "请依次输入元素：" << endl;
	while (n--) 
	{
		s = new LNode;
		cin >> s->data;
		s -> next = NULL;
		r->next = s;
		r = s;
	}
}

2.5 打印链表

void Print_list(LinkList& L)
{
	LinkList s;
	s = L->next;
	while(s)
	{
		cout << s->data << " ";
		s = s->next;
	}
	cout << endl;
}

2.6 求链表的长度

int Length_list(LinkList& L)
{
	int length=0;
	LinkList s;
	s = L->next;
	while (s)
	{
		length++;
		s = s->next;
	}
	return length;
}

2.7 按位置序号查找结点

LNode* GetElem(LinkList& L, int i)
{
	if (i<1 || i>Length_list(L))
		return NULL;
	int j = 1;
	LNode* p = L->next; //链表第一个结点赋给p，L是头结点
	while (p != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	return p; //返回第i个结点的指针，"p != NULL"其实是在和表长对比，但我这里其实不需要
}

2.8 按值查找位置信息

int LocateElem(LinkList& L, Elemtype e)
{
	LNode* p = L->next; //第一个结点赋给p;
	int j = 1;
	while (p != NULL && p->data != e)
	{
		p = p->next;
		j++;
	}
	return j;
}

2.9在第i个结点之后插入新的结点

bool ListInsert(LinkList& L, int i, Elemtype e)
{
	if (i<1 || i>Length_list(L) + 1)
		return false; //判断i的合法性
	if (i == 1)//这样就能在第1个位置插入结点了
	{
		LinkList p;
		p = new LNode; //创建想要插入的结点信息
		p->next = L->next;
		p->data = e;
		L->next = p;
	}
	else
	{
		LinkList s;
		s = GetElem(L, i - 1); //查找到第i-1个结点,是查不到第1个位置的
		LinkList p;
		p = new LNode; //创建想要插入的结点信息
		p->next = s->next;
		p->data = e;
		s->next = p;
	}

	return true;
}

2.10 删除第i个位置的结点

bool ListDelete(LinkList& L, int i)
{
	if (i<1 || i>Length_list(L))
		return false;
	if (i == 1)
	{
		LNode* p = L->next;//第一个结点赋给p;
		L->next = p->next;
		free(p);
	}
	else
	{
		LinkList s;
		s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的
		LinkList p; //被删除的结点
		p = s->next;
		s->next = p->next;
		free(p);
	}
	return true;
}

2.11单链表的逆置

bool ListReverse(LinkList& L)
{
	if (!L->next)
		return false; //空链表不需要逆置
	LinkList r, p, q; //r代表前驱节点，p当前节点，q后继节点
	r = NULL;
	p = L->next;
	q = p->next;  //从单链表的第一个节点开始，沿着链表滑动，直到最后一个节点，逐一反转

	while (p)
	{
		p->next = r;
		r = p;
		p = q;
		if (q) //保证指向后继节点的指针q不会移出表尾
			q = q->next;
	}
	L->next = r; //当从循环出来时说明p为空，则r就是最后一个节点，此时把最后一个节点作为首节点
}

2.12 两个链表的合并

//（11）两个链表的合并,把B有顺序地插入A中(假设A是有顺序的)
void CombineList(LinkList& A, LinkList& B)
{
	LinkList q, p, r;
	q = A; //q指向A的头指针
	p = B->next; //p指向B的第一个结点
	while (p)
	{
		while ((q->next) && (q->next->data < p->data))
		{
			q = q->next;
		} //找到现在的p应该插入到哪的位置
		r = p;
		p = p->next;
		r->next = q->next;
		q->next = r;
	}
}

2.13 main函数

#include<iostream>
#include"stdlib.h"
using namespace std;
#define Elemtype int

int main()
{
	LinkList L;
	//(1)初始化链表，形成带有"头节点"的空链表
	Initlist(L);
	//(2)使用头插法建立链表
	List_HeadInsert(L);
	Print_list(L);
	//(3)使用尾插法建立链表
	List_TailInsert(L);
	Print_list(L);
	//(4)按照序号进行查找
	int n1;
	cout << "想要查找的位置序号是：" << endl;
	cin >> n1;
	LinkList p;
	p = GetElem(L, n1);
	cout << p->data << endl;
	//(5)按值查找结点位置信息
	int n2;
	cout << "想要查找的数值是：" << endl;
	cin >> n2;
	cout << LocateElem(L,n2) << endl;
	//(6)在第i个位置插入结点
	int n3;
	int n4;
	cout << "想要（后插法）插入的位置和值分别是：" << endl;
	cin >> n3 >> n4;
	ListInsert(L, n3, n4);
	Print_list(L);
	//(7)在第i个位置插入结点
	int n5;
	cout << "想要删除的位置分别是：" << endl;
	cin >> n5;
	ListDelete(L, n5);
	Print_list(L);
	//(8)链表逆置
	ListReverse(L);
	Print_list(L);
	//(9)合并两个链表
	LinkList L1;
	Initlist(L1);
	List_TailInsert(L1);
	cout << "合并两个链表的结果是：" << endl;
	CombineList(L, L1);
	Print_list(L);

	system("pause");
	return 0;
}

三、不带头结点的程序说明

        如果不带头结点的单链表，则对表头的操作（插入和删除）要特殊处理，例如HeadInsert（头插法创建单链表）每次插入后都要更新头指针，而对于带头结点的单链表，它的头指针指向永远是头结点，只需要修改头结点的后继就可以完成插入。

3.1 单链表的存储结构

typedef struct LNode {
	Elemtype data;
	struct LNode* next;
}LNode,*LinkList;

3.2 初始化

bool InitList(LinkList& L)
{
	L = new LNode;
	L = NULL; //不带头结点，区别：L->next=NULL
	return true;
}

3.3 头插法建立单链表

void HeadInsert(LinkList& L)
{
	int n;
	cout << "请输入插入元素的个数" << endl;
	cin >> n;
	cout << "请依次输入元素的值" << endl;
	LinkList s; //定义指针变量s
	while (n--)
	{
		s = new LNode; //定义变量结点
		cin >> s->data;
		s->next = L;
		L = s;//更新头指针
	}
}

3.4 尾插法建立单链表

void TailInsert(LinkList& L)
{
	int n;
	cout << "请输入插入元素的个数" << endl;
	cin >> n;
	cout << "请依次输入元素的值" << endl;
	LinkList s; //定义指针变量s
	LinkList r; //定义一个表尾指针r
	r = new LNode;
	while (n--)
	{
		if (L == NULL)
		{
			s = new LNode;
			cin >> s->data;
			s->next = L;
			L = s; //更新头指针L
			r = s; //更新尾指针r
		}
		else
		{
			s = new LNode;
			cin >> s->data;
			s->next = r->next;
			r->next = s;
			r = s;
		}
	}
}

3.5 打印链表

void PrintList(LinkList& L)
{
	LinkList s;
	s = L;
	while (s)
	{
		cout << s->data << " ";
		s = s->next;

	}
	cout << endl;
}

3.6 求链表的长度

int Length_list(LinkList& L)
{
	int length = 0;
	LinkList s;
	s = L;
	while (s)
	{
		length++;
		s = s->next;
	}
	return length;
}

3.7 按位置序号查找结点

LNode* GetElem(LinkList& L, int i)
{
	if (i<1 || i>Length_list(L))
		return NULL;
	int j = 1;
	LNode* p = L; //链表第一个结点赋给p
	while (p != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	return p; //返回第i个结点的指针，"p != NULL"其实是在和表长对比，但我这里其实不需要
}

3.8 按值查找位置信息

int LocateElem(LinkList& L, Elemtype e)
{
	LNode* p = L; //第一个结点赋给p;
	int j = 1;
	while (p != NULL && p->data != e)
	{
		p = p->next;
		j++;
	}
	return j;
}

3.9在i位置插入新的结点（方法一）

//（8）在第i个位置插入结点(后插法)
bool ListInsert(LinkList& L, int i, Elemtype e)
{
	if (i<1 || i>Length_list(L) + 1)
		return false; //判断i的合法性
	if (i == 1)//这样就能在第1个位置插入结点了
	{
		LinkList p;
		p = new LNode; //创建想要插入的结点信息
		p->next = L;
		p->data = e;
		L = p; //更新头指针
	}
	else//不是在第1个位置插入结点
	{
		LinkList s;
		s = GetElem(L, i - 1); //查找到第i-1个结点
		LinkList p;
		p = new LNode; //创建想要插入的结点信息
		p->next = s->next;
		p->data = e;
		s->next = p;
	}
	return true;
}

3.10 在i位置插入新的结点（方法二）

//（9）在第i个位置插入结点(前插法)
bool List_HeadInsert(LinkList& L, int i, Elemtype e)
{
	if (i<1 || i>Length_list(L) + 1)
		return false; //判断i的合法性
	LinkList s;
	s = GetElem(L, i); //查找到第i个结点
	LinkList p;
	p = new LNode;
	p->next = s->next;
	p->data = s->data;//定义一个结点p，复制原本i结点的全部信息
	s->next = p;
	s->data = e;//再把原本i结点变成插入的新结点的信息
	return true;
}

3.11 删除第i个位置的结点　

bool ListDelete(LinkList& L, int i)
{
	if (i<1 || i>Length_list(L))
		return false;
	if (i == 1)
	{
		LNode* p = L;//第一个结点赋给p;
		L = p->next; //更新头指针
		free(p);
	}
	else
	{
		LinkList s;
		s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的
		LinkList p; //被删除的结点
		p = s->next;
		s->next = p->next;
		free(p);
	}
	return true;
}

3.13 main函数

#include<iostream>
using namespace std;
#include"stdlib.h"
#define Elemtype int


int main()
{
	LinkList L;
	InitList(L);
	//（1）使用头插法创建链表
	//HeadInsert(L);
	//PrintList(L);
	//(2)使用尾插法创建链表
	TailInsert(L);
	PrintList(L);
	//(3)按照位置序号进行查找
	//int n1;
	//cout << "想要查找的位置序号是：" << endl;
	//cin >> n1;
	//LinkList p;
	//p = GetElem(L, n1);
	//cout << p->data << endl;
	//(4)按值查找结点位置信息
	//int n2;
	//cout << "想要查找的数值是：" << endl;
	//cin >> n2;
	//cout << LocateElem(L, n2) << endl;
	//(5)后插法插入结点
	//ListInsert(L, 1, 1);
	//PrintList(L);
	//（6）前插法插入结点
	//List_HeadInsert(L, 1, 3);
	//PrintList(L);
	//(7)删除结点
	ListDelete(L, 1);
	PrintList(L);
	system("pause");
	return 0;
}

四、思考

        对于单链表，分为不带头结点和带头结点，有头结点只是可以少一些对于头指针的更新操作，链表的第一个元素和其他元素的处理是通用的，就会方便一点。文章来源地址https://www.toymoban.com/news/detail-745794.html

到了这里，关于数据结构（2）—单链表（带头结点和不带头结点）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表（单链表&&双向循环链表）附完整源码

    『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表（单链表&&双向循环链表）附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(80)
  • 数据结构——单链表(不带头节点)

    数据结构——单链表(不带头节点)

    链表是一种物理存储结构上非联系，非顺序的存储结构，但数据元素的逻辑顺序是通过链表中的指针链接实现的 逻辑结构： 实际物理结构： 每个链表节点都有自己的地址，链表的物理结构实际上是前一个结点保存着下一个结点的地址 所以从上面图中可以看出： 1.链表在逻辑

    2024年02月06日
    浏览(56)
  • 追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

    追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

        😎博客昵称：博客小梦 😊最喜欢的座右铭：全神贯注的上吧！！！ 😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！ 😘博主小留言：哈喽！ 😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不

    2024年01月17日
    浏览(61)
  • 【数据结构与算法分析】使用C语言实现队列的两种（带头结点与不带头结点）链式存储，并且给出一种循环队列的设计思想

    【数据结构与算法分析】使用C语言实现队列的两种（带头结点与不带头结点）链式存储，并且给出一种循环队列的设计思想

      当我们编写程序时，经常需要处理各种数据结构。队列是一种常见的数据结构，它有着广泛的应用场景。队列的基本操作包括入队和出队，应用于模拟等待队列、消息队列、计算机缓存等场合。   在实际编程中，我们可以用不同的数据结构来实现队列。本文主要介绍了

    2024年02月08日
    浏览(116)

  • 7-数据结构-（带头节点）单链表的增删改查

    问题：          单链表带头结点的创建以及输出，以及带与不带头节点的区别 思路： 单链表，逻辑上是线性结构，由许多单链表结点，串成一串。其单链表结构体中，数据项由data数据域和结点指针域。 带头节点是为了使在空表时的操作更统一。如果不带头节点，空表插

    2024年02月14日
    浏览(51)
  • 数据结构之带头节点的单链表增删改查操作实现

    数据结构之带头节点的单链表增删改查操作实现

            单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。       单链表的各个数据元素在物理上可以是离散存放的，每个结点除了存放数据元素外，还要存储指向下一个节点的指针。而顺序表是连续存放的，每个结点中只存放数据元

    2024年02月16日
    浏览(47)
  • 玩转带头双向链表——【数据结构】

    玩转带头双向链表——【数据结构】

    W...Y的主页 今天我们接着来说数据结构——带头双向链表 目录 带头双向链表的实现 结构体的创建 初始化兵创建哨兵节点 释放链表所以内容  打印链表函数 尾插 尾删 头插 ​编辑 头删 计数函数实现 查找数据相应位置函数 在pos位置之前插入  在pos位置删除  顺序表与链表的

    2024年02月14日
    浏览(39)
  • 数据结构之带头双向链表（易学版）

    数据结构之带头双向链表（易学版）

    目录 1.问题引入 2.结构实现 2.3.1接口实现 2.3.2函数实现 3.总结 ，又和大家见面了，今天要给大家分享的是双链表的知识，跟着我的脚步，包学包会哦~ 规矩不乱，先赞后看！ ps：（孙权劝学） 前期学习了单链表，我们尝到了它的甜头，但是容易越界访问这一个问题也是时有出

    2024年03月22日
    浏览(42)
  • 数据结构 - 链表详解（二）—— 带头双向循环链表

    数据结构 - 链表详解（二）—— 带头双向循环链表

    链表的结构一共有 八种 ：带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结构，它通

    2024年04月26日
    浏览(55)
  • C语言数据结构_查找并删除单链表中最大值结点并返回值

    C语言数据结构_查找并删除单链表中最大值结点并返回值

             

    2024年02月05日
    浏览(69)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包