C++递归实现不带头节点的单链表操作

这篇具有很好参考价值的文章主要介绍了C++递归实现不带头节点的单链表操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

有一个不带头结点的单链表:

递归实现以下操作(强调:所有操作必须用递归完成)。

1,插入数据:13,15,8,4,8,3,4,8(可以用递归一次完成,也可以用递归将一个一维数组一个一个的尾部插入)

2,正向输出所有节点值

3,逆向输出所有节点值

4,输出单链表中数据结点个数

5,输出第k个节点的值(k由用户输入,要能给出错误情况)

6,在第k个位置上插入e元素。(k和e由用户输入,要能给出错误情况)

7,正向输出所有节点值

8,删除第k个结点(k由用户输入,要能给出错误情况)

9,正向输出所有节点值

10,删除值为X的数据结点(测试值为:8)

11,正向输出所有节点值

12,删除所有值为X的数据结点(测试值为:4)

13,正向输出所有节点值

14,输出该链表的最大值

15,输出该链表的最小值

16,查找值为X的数据结点在当前链表出现的位置(测试值为:3,要能给出错误情况)。

17,销毁该链表

=================================================

1.定义单链表的数据结构

#include <iostream>
using namespace std;
typedef int ElemType;

/* 定义单链表 */
typedef struct node {
	ElemType data;
	node* next;
} List;

2.插入元素到链表的第i个位置

在主函数时搭配 for 循环,从数组内的数组一个个插入链表

bool InsertList(List*& L, int i, ElemType e)	// 插入第i个位置(逻辑位序)
{
	if (i <= 0)             // 特判非正整数的非法位置
		return false;
	else if (1 == i)        // 找到了要插入的位置的前一个节点
	{
		List* s = new List;
		s->data = e;
		s->next = L;
		L = s;              // 前一个节点的next指针(在上一层递归中体现)指向新建的节点
		return true;
	}

	if (NULL == L)          // 如果这个节点已经是最后一个节点了,那么不用递归下去了
		return false;
	else
		return InsertList(L->next, i - 1, e);   // 递归到下一层, 若找到对应节点那么此处的指针值会相应改变
}

3.单链表中数据结点个数

int CountList(List* L)
{
	if (NULL == L)
		return 0;
	return 1 + CountList(L->next);      // 1 + 从L->next出发的节点数
}

4.正向输出所有节点值

先输出第一个节点值,然后进行递归到下一个节点,每递归到下一层输出下一层的节点值,直到最后一个节点。

void DispList(List* L)
{
	if (NULL == L)
		return;

	cout << L->data << ' '; // 先输出该元素
	DispList(L->next);      // 再递归到下一个节点
}

5.逆向输出所有节点值

先递归到最后一个节点,输出该节点值,然后一层一层退出递归,每退出一层输出该层节点值

void DispListRev(List* L)
{
	if (NULL == L)
		return;
	DispListRev(L->next);   // 先递归到下一个节点
	cout << L->data << ' '; // 返回该函数时,再输出元素
}

6.输出第i个位置上的节点

bool DispOne(List* L, int i, ElemType& e)
{
	if (i <= 0 || NULL == L)    // 越界判断
		return false;
	else if (1 == i)
	{
		e = L->data;
		return true;
	}
	return DispOne(L->next, i - 1, e);
}

7.删除第一个值为e的元素

bool DeleOneByValue(List*& L, ElemType e)
{
	if (NULL == L)      // 没找到
		return false;

	if (e == L->data)   // 发现了需要删除的元素
	{
		List* p = L;    // 新建一个指针保存要删除的节点的地址值
		L = L->next;    // 让上一个节点的next指针指向该节点的next指针
		delete p;       // 删除节点
		return true;    // 返回true,结束递归
	}
	return DeleOneByValue(L->next, e);    // 如果到此处,证明当前节点没有删除成功,返回值由下一层递归决定
}

8.删除所有值为e的元素

bool DeleAll(List*& L, ElemType e)
{
	if (NULL == L)
		return false;

	if (e == L->data)
	{
		List* p = L;
		L = L->next;
		delete p;
		DeleAll(L, e);  // 删除后L成为未检测过的节点,故递归从L开始
		return true;    // 最后再返回true,因为至少删除过一个节点了
	}
	return DeleAll(L->next, e);     // 同上一个函数此处的解释
}

9.通过位置删除第i个位置上的元素

bool DeleOneByLocation(List*& L, int i)
{
	if (i <= 0)     // 按位置查找特殊些, 先判断非正整数越界的情况
		return false;
	else if (1 == i)
	{
		List* s = L;    // 删除跟之前的差不多
		L = L->next;
		delete s;
		return true;
	}
	
	if (L->next)        // 如果有下一个节点的话, 就递归下去
		return DeleOneByLocation(L->next, i - 1);
	else
		return false;   // 如果没有, 那么查找的位置越界了
}

 10.定位元素e的位置

int LocateElem(List* L, ElemType e)
{
	if (e == L->data)
		return 1;
	else if (L->next)
		return 1 + LocateElem(L->next, e);
	else
		return 2;               // 如果是最后一个节点的话, 那么返回2, 使得最终的结果超过链表的长度, 判断为越界
}

11.得到L节点开始的最大值

ElemType maxValue(List* L)
{
	if (NULL == L->next)        // 当前节点已经是最后一个节点了,返回当前节点data值即可
		return L->data;
		
	int nextMax = maxValue(L->next);    			// 得到该节点的后面的节点的最大值
	return L->data > nextMax ? L->data : nextMax;   // 判断返回当前data值和后面节点最大值中较大的数
}

12.得到L节点开始的最小值

ElemType minValue(List* L)
{
	if (NULL == L->next)
		return L->data;

	int nextMin = minValue(L->next);
	return L->data < nextMin ? L->data : nextMin;
}

13.销毁单链表

void DestroyList(List*& L)
{
	if (NULL == L)
		return;

	DestroyList(L->next);   // 先删除后面的节点
	delete L;               // 递归回到此处时,再删除当前节点
}

=================================================

主函数

int main()
{
	int k;
	List* L1 = NULL;
	ElemType x;
	ElemType a[] = {13, 15, 8, 4, 8, 3, 4};

	cout << "(1) 插入数据" << endl << endl;
	k = sizeof(a) / sizeof(ElemType);
	for (int i = 0; i < k; ++i)
	{
		InsertList(L1, i + 1, a[i]);
	}
	
	cout << "(2) 正向输出所有节点值" << endl;
	cout << "正向输出所有值为: " ; DispList(L1);
	cout << endl << endl;
	
	cout << "(3) 逆向输出所有节点值" << endl;
	cout << "逆向输出所有值为: " ; DispListRev(L1);
	cout << endl << endl;
	
	cout << "(4) 输出单链表中数据节点的个数" << endl;
	cout << "该单链表有" << CountList(L1) << "个节点" << endl << endl;
	
	cout << "(5) 输出第k个节点的值" << endl;
 	cout << "请输入你要输出的节点的序号: "; cin >> k;
 	if (DispOne(L1, k, x))
 	{
 		cout << "找到第" << k << "个元素: " << x;
	}
	else
		cout << "你输入的位置不正确";
	cout << endl << endl;
	
	cout << "(6) 在第k个元素位置上插入e元素" << endl;
	cout << "请输入你需要插入的位置: "; cin >> k;
	cout << "请输入你要插入的元素: "; cin >> x;
	cout << (InsertList(L1, k, x) ? "插入成功" : "插入失败");
	cout << endl << endl;
	
	cout << "(7) 正向输出所有节点值" << endl;
	cout << "正向输出所有值为: " ; DispList(L1);
	cout << endl << endl;
	
	cout << "(8) 删除第k个节点" << endl;
	cout << "请输入需要删除的节点的序号: "; cin >> k;
	cout << (DeleOneByLocation(L1, k) ? "删除成功" : "删除失败") << endl << endl;
	
	cout << "(9) 正向输出所有节点值" << endl;
	cout << "正向输出所有值为: " ; DispList(L1);
	cout << endl << endl;
	
	cout << "(10) 删除值为X的数据节点(删除第一个)" << endl;
	cout << "请输入需要删除的节点的值: "; cin >> x;
	cout << (DeleOneByValue(L1, x) ? "删除成功" : "删除失败") << endl << endl;
	
	cout << "(11) 正向输出所有节点值" << endl;
	cout << "正向输出所有值为: " ; DispList(L1);
	cout << endl << endl;
	
	cout << "(12) 删除所有值为X的数据节点" << endl;
	cout << "请输入你需要删除的值: "; cin >> x;
	cout << (DeleAll(L1, x) ? "删除成功" : "删除失败") << endl << endl;
	
	cout << "(13) 正向输出所有节点值" << endl;
	cout << "正向输出所有值为: " ; DispList(L1);
	cout << endl << endl;
	
	cout << "(14) 输出该链表的最大值" << endl;
	cout << "该链表的最大值为: " << maxValue(L1) << endl << endl;
	
	cout << "(15) 输出该链表的最小值" << endl;
	cout << "该链表的最小值为: " << minValue(L1) << endl << endl;
	
	cout << "(16) 查找值为X的数据节点在当前链表第一次出现的位置" << endl;
	cout << "请输入你需要查找的元素: "; cin >> x;
	if ( (k = LocateElem(L1, x) ) <= CountList(L1) )
	{
		cout << "找到该元素, 它是链表中第" << k << "个元素";
	}
	else
		cout << "找不到该元素";
	cout << endl << endl;
	
	cout << "(17) 销毁该链表" << endl;
	DestroyList(L1);
	
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-409577.html

到了这里,关于C++递归实现不带头节点的单链表操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】——单链表的基本操作(带头结点)

            单链表解决了顺序表需要大量连续存储单元的缺点,但单链表附加指针域, 存储密度较顺序表低(考点!!) 。由于单链表的元素离散地分布在存储空间中,所以单链表是 非随机存取 的存储结构,即不能直接找到表中某个特定的结点。当查找某个特定结点时,需要

    2024年02月05日
    浏览(52)
  • 【数据结构】C语言实现单链表(带头结点)

    Single linked list with leading nodes 关于不带头结点的单链表:不带头结点的单链表 结点定义: 接口定义: 初始化需要申请头结点,让头指针指向空的头结点。 将申请结点的代码进行封装: 需要越过头结点 找到尾结点,然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(219)
  • 数据结构——单链表基本操作实现 (c++)

    单链表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这里存储单元可以是连续的,也可以是不连续的),为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系,除了存储信息本身外还要存储一个指示其直接后继的信息(地址). 这两部分信

    2024年02月03日
    浏览(68)
  • 数据结构三:线性表之单链表(带头结点单向)的设计与实现

            线性表的链式存储结构正是所谓的单链表,何谓单链表?通过地址将每一个数据元素串起来,进行使用,这可以弥补顺序表在进行任意位置的插入和删除需要进行大量的数据元素移动的缺点,只需要修改指针的指向即可;单链表的种类又可划分为很多种,本篇博客详

    2024年02月19日
    浏览(62)
  • 设计一个算法删除单链表L(有头节点)中的一个最小值结点

    笔试题:设计一个算法删除单链表L(有头节点)中的一个最小值结点。

    2024年04月22日
    浏览(46)
  • ROS实现一个节点同时发布订阅多个话题(C++版)

      如果想在一个节点同时发布订阅多个话题就要使用到多线程机制,在C++中如何使用多线程,在C++中开多线程模板已经有了介绍,就是下面这个:    但是有一点需要注意的是,创建节点的涉及到一个主线程,如果想同时发布订阅是不能使用主线程的(也就是不能主线程发

    2024年02月11日
    浏览(39)
  • 数据结构(2)—单链表(带头结点和不带头结点)

            单链表 是通过一组任意的存储单元来存储线性表中的数据元素。每个结点都有 data数据域 (用来存放数据元素)和 next指针域 (用来存放后继节点的地址)。         对于顺序表,单链表可以解决顺序表需要一整个大量的连续的存储单元的缺点,单链表的元素

    2024年02月05日
    浏览(56)
  • 单链表创建之--头插法创建带头结点的单链表

    单链表常见的创建方法有 头插法 和 尾插法 ,这里记录头插法创建 带头结点的单链表 具体过程: 以C语言为例, 1)首先使用  typedef  定义结点数据类型 4行的 LNode 和 * LinkList 可有可无,有的话后面定义结点变量和指针变量时更方便,不必须在LNode前面加 struct

    2024年02月06日
    浏览(40)
  • 带头结点单链表【详细解析+完整代码】

    它是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系,每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。 结点结构: 带头结点链表结构: 保证了每个结点都有前驱结点,因此在链表上第一个结点的操作与其他结点操

    2024年04月15日
    浏览(44)
  • 数据结构:图文详解单链表的各种操作(头插法,尾插法,任意位置插入,删除节点,查询节点,求链表的长度,清空链表)

    目录  一.什么是链表 二.链表的实现 节点的插入 头插法 尾插法 指定位置插入 节点的删除 删除第一次出现的节点 删除所有节点 节点的查找 链表的清空 链表的长度 前言: 在上一篇文章中,我们认识了线性数据结构中的顺序表,而本篇文章则是介绍线性数据结

    2024年02月05日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包