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

这篇具有很好参考价值的文章主要介绍了数据结构(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语言』⑨ - 基于结点的数据结构——链表(单链表&&双向循环链表)附完整源码

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

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

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

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

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

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

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

    2024年02月08日
    浏览(102)
  • 7-数据结构-(带头节点)单链表的增删改查

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

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

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

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

    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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包