第一百一十二天学习记录：数据结构与算法基础：循环链表和双向链表以及线性表应用（王卓教学视频）

循环链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

带尾指针循环链表的合并

在这里插入图片描述
在这里插入图片描述

双向链表

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

单链表、循环链表和双向链表的时间效率比较

在这里插入图片描述

顺序表和链表的比较

链式存储结构的优点

1、结点空间可以动态申请和释放；
2、数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。

链式存储结构的缺点

1、存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
2、链式存储结构是非随机存取结构。对任一节点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
在这里插入图片描述
在这里插入图片描述

线性表应用

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
用C语言实现：

#include <stdio.h>

void mergeArrays(int arr1[], int size1, int arr2[], int size2, int mergedArray[]) {
    int i, j, k, duplicate;

    // 将arr1的元素插入合并数组
    for (i = 0; i < size1; i++) {
        mergedArray[i] = arr1[i];
    }
    k = size1;

    // 将arr2中非重复元素插入合并数组
    for (i = 0; i < size2; i++) {
        duplicate = 0;
        for (j = 0; j < size1; j++) {
            if (arr2[i] == arr1[j]) {
                duplicate = 1;
                break;
            }
        }
        if (!duplicate) {
            mergedArray[k++] = arr2[i];
        }
    }
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);

    int arr2[] = {4, 5, 6, 7, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    // 计算合并数组的最大长度
    int maxSize = size1 + size2;

    int mergedArray[maxSize];

    mergeArrays(arr1, size1, arr2, size2, mergedArray);

    // 输出合并并去重后的数组
    for (int i = 0; i < size1 + size2; i++) {
        printf("%d ", mergedArray[i]);
    }
    printf("\n");

    return 0;
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
实现代码如下：

#include<iostream>
using namespace std;

struct Mylist
{
	int m_int;
	Mylist* myl;
};

int main()
{
	Mylist* la = new Mylist;
	la->myl = new Mylist;
	la->myl->myl = new Mylist;
	la->myl->myl->myl = new Mylist;
	la->myl->myl->myl->myl = NULL;
	la->myl->m_int = 1;
	la->myl->myl->m_int = 7;
	la->myl->myl->myl->m_int = 8;
	
	Mylist* lb = new Mylist;
	lb->myl = new Mylist;
	lb->myl->myl = new Mylist;
	lb->myl->myl->myl = new Mylist;
	lb->myl->myl->myl->myl = new Mylist;
	lb->myl->myl->myl->myl->myl = new Mylist;
	lb->myl->myl->myl->myl->myl->myl = new Mylist;
	lb->myl->myl->myl->myl->myl->myl->myl = NULL;
	lb->myl->m_int = 2;
	lb->myl->myl->m_int = 4;
	lb->myl->myl->myl->m_int = 6;
	lb->myl->myl->myl->myl->m_int = 8;
	lb->myl->myl->myl->myl->myl->m_int = 10;
	lb->myl->myl->myl->myl->myl->myl->m_int = 11;

	Mylist* pc = la;
	Mylist* lc = la;
	Mylist* pa = la->myl;
	Mylist* pb = lb->myl;

	while (pa&&pb)
	{
		if (pa->m_int <= pb->m_int)
		{
			pc->myl = pa; pc = pa; pa = pa->myl;
		}
		else
		{
			pc->myl = pb; pc = pb; pb = pb->myl;
		}
	}
	pc->myl = pa ? pa : pb;
	delete lb;
	pc = lc;
	while (pc->myl)
	{
		cout << pc->myl->m_int << " ";
		pc = pc->myl;
	}
	cout << endl;
	return 0;
}

案例分析与实现

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

实现代码：

本来以为很简单，全部写在main函数里，结果……
本代码笔者尽可能将会导致程序出错以及内存泄漏的情况规避了。如果还有有缺陷的地方欢迎大佬们指出。

#include<iostream>
using namespace std;

struct Poly
{
	int c;
	int e;
	Poly* pnext;
};

int main()
{
	cout << "本程序用链表方式实现两个一元多项式相加" << endl;
	cout << "由低阶到高阶依次输入一元多项式的系数和指数" << endl;
	cout << "用空格分隔，回车结束：(系数为0不需要输入)" << endl;
	cout << "比如:y(x)=3x^0+4x^1+x^3  输入：3 0 4 1 1 3" << endl;
	cout << "提示：输入任意非数字键退出" << endl;
	int input;
	int ctmp = 0;
	int etmp = 0;
	int tmp = 0;
	int pta = 0;
	int ptb = 0;
	Poly* Pahead = new Poly;
	Pahead->pnext = NULL;
	Poly* Pa = Pahead;
	Poly* Pbhead = new Poly;
	Pbhead->pnext = NULL;
	Poly* Pb = Pahead;
	Poly* temp = NULL;
	Poly* Pc = NULL;
	while (true)
	{
		Pa = Pahead;
		Pa = Pa->pnext;
		while (Pa)
		{
			//cout << "Pa删除一项" << endl;
			temp = Pa->pnext;
			delete Pa;
			Pa = temp;
		}
		Pa = Pahead;
		Pb = Pbhead;
		Pb = Pb->pnext;
		Pahead->pnext = NULL;
		while (Pb)
		{
			//cout << "Pb删除一项" << endl;
			temp = Pb->pnext;
			delete Pb;
			Pb = temp;
		}
		Pb = Pbhead;
		Pbhead->pnext = NULL;
		cout << "下面请输入第一个一元多项式一共有几项" << endl;
		cout << "=>";
		while (true)
		{
			cin >> input;
			if (cin.fail())
			{
				cin.clear();
				cout << "已退出，欢迎再次使用。" << endl;
				Pa = Pahead;
				Pb = Pbhead;
				if (Pahead != NULL)
				{
					//cout << "删除Pahead。" << endl;
					Pa = Pahead;
					while (Pa)
					{
						temp = Pa->pnext;
						delete Pa;
						Pa = temp;
					}
				}
				if (Pbhead != NULL)
				{
					//cout << "删除Pbhead。" << endl;
					Pb = Pbhead;
					while (Pb)
					{
						temp = Pb->pnext;
						delete Pb;
						Pb = temp;
					}
				}
				return 0;
			}
			if (input <= 0)
			{
				cout << "请至少输入一项" << endl;
				continue;
			}
			if (input > 100)
			{
				cout << "最大不要超出100项……这么多的多项式爱因斯坦见了都得捂脸……" << endl;
				continue;
			}
			pta = input * 2;
			break;
		}
		cout << "下面请输入第一个一元多项式" << endl;
		cout << "=>";
		while (pta--)
		{
			cin >> input;
			if (cin.fail())
			{
				cin.clear();
				cout << "已退出，欢迎再次使用。" << endl;
				Pa = Pahead;
				Pb = Pbhead;
				if (Pahead != NULL)
				{
					//cout << "删除Pahead。" << endl;
					Pa = Pahead;
					while (Pa)
					{
						temp = Pa->pnext;
						delete Pa;
						Pa = temp;
					}
				}
				if (Pbhead != NULL)
				{
					//cout << "删除Pbhead。" << endl;
					Pb = Pbhead;
					while (Pb)
					{
						temp = Pb->pnext;
						delete Pb;
						Pb = temp;
					}
				}
				return 0;
			}
			if (tmp == 0)
			{
				ctmp = input;
				++tmp;
				continue;
			}
			else
			{
				etmp = input;
				Pa->pnext = new Poly;
				Pa->pnext->c = ctmp;
				Pa->pnext->e = etmp;
				Pa = Pa->pnext;
				Pa->pnext = NULL;
				--tmp;
			}
		}
		int availableChars = (int)cin.rdbuf()->in_avail();
		if (availableChars)
		{
			cin.ignore(numeric_limits<streamsize>::max(), '\n');
		}
		cout << "第一个一元多项式:" << endl;
		cout << "y(x)=";
		Pa = Pahead;
		cout << Pa->pnext->c << "x^" << Pa->pnext->e;
		Pa = Pa->pnext;
		while (Pa->pnext)
		{
			cout << "+";
			cout << Pa->pnext->c << "x^" << Pa->pnext->e;
			Pa = Pa->pnext;
		}
		cout << endl;
		//第二个
		Pb = Pbhead;
		cout << "下面请输入第二个一元多项式一共有几项" << endl;
		cout << "=>";
		while (true)
		{
			cin >> input;
			if (cin.fail())
			{
				cin.clear();
				cout << "已退出，欢迎再次使用。" << endl;
				Pa = Pahead;
				Pb = Pbhead;
				if (Pahead != NULL)
				{
					//cout << "删除Pahead。" << endl;
					Pa = Pahead;
					while (Pa)
					{
						temp = Pa->pnext;
						delete Pa;
						Pa = temp;
					}
				}
				if (Pbhead != NULL)
				{
					//cout << "删除Pbhead。" << endl;
					Pb = Pbhead;
					while (Pb)
					{
						temp = Pb->pnext;
						delete Pb;
						Pb = temp;
					}
				}
				return 0;
			}
			if (input <= 0)
			{
				cout << "请至少输入一项" << endl;
				continue;
			}
			if (input > 100)
			{
				cout << "最大不要超出100项……这么多的多项式爱因斯坦见了都得捂脸……" << endl;
				continue;
			}
			ptb = input * 2;
			break;
		}
		cout << "下面请输入第二个一元多项式" << endl;
		cout << "=>";
		while (ptb--)
		{
			cin >> input;
			if (cin.fail())
			{
				cin.clear();
				cout << "已退出，欢迎再次使用。" << endl;
				Pa = Pahead;
				Pb = Pbhead;
				if (Pahead != NULL)
				{
					//cout << "删除Pahead。" << endl;
					Pa = Pahead;
					while (Pa)
					{
						temp = Pa->pnext;
						delete Pa;
						Pa = temp;
					}
				}
				if (Pbhead != NULL)
				{
					//cout << "删除Pbhead。" << endl;
					Pb = Pbhead;
					while (Pb)
					{
						temp = Pb->pnext;
						delete Pb;
						Pb = temp;
					}
				}
				return 0;
			}
			if (tmp == 0)
			{
				ctmp = input;
				++tmp;
				continue;
			}
			else
			{
				etmp = input;
				Pb->pnext = new Poly;
				Pb->pnext->c = ctmp;
				Pb->pnext->e = etmp;
				Pb = Pb->pnext;
				Pb->pnext = NULL;
				--tmp;
			}
		}
		availableChars = (int)cin.rdbuf()->in_avail();
		if (availableChars)
		{
			cin.ignore(numeric_limits<streamsize>::max(), '\n');
		}
		cout << "第二个一元多项式:" << endl;
		cout << "z(x)=";
		Pb = Pbhead;
		cout << Pb->pnext->c << "x^" << Pb->pnext->e;
		Pb = Pb->pnext;
		while (Pb->pnext)
		{
			cout << "+";
			cout << Pb->pnext->c << "x^" << Pb->pnext->e;
			Pb = Pb->pnext;
		}
		cout << endl;
		//求和
		Pa = Pahead->pnext;
		Pc = Pahead;
		Pb = Pbhead->pnext;
		while (Pa&&Pb)
		{
			if (Pa->e < Pb->e)
			{
				Pc->pnext = Pa; Pc = Pa; Pa = Pa->pnext;
			}
			else if (Pa->e > Pb->e)
			{
				Pc->pnext = Pb; Pc = Pb; Pb = Pb->pnext;
			}
			else
			{
				if ((Pa->c + Pb->c) == 0)
				{
					temp = Pb;
					Pb = Pb->pnext;
					delete temp;
					temp = Pa;
					Pa = Pa->pnext;
					delete temp;
				}
				else
				{
					Pc->pnext = Pa; Pc = Pa; Pa = Pa->pnext;
					Pc->c += Pb->c;
					temp = Pb;
					Pb = Pb->pnext;
					delete temp;
				}
			}
		}
		Pc->pnext = Pa ? Pa : Pb;
		Pbhead->pnext = NULL;//必须设置为NULL，要不然下次对Pbhead进行释放时会造成野指针
		cout << "二个一元多项式之和为:" << endl;
		Pc = Pahead;
		cout << "y(x)+z(x)=";
		if (!Pc->pnext)//存在两个多项式相加为零的情况！
		{
			cout << 0 << endl;
			Pc = Pahead;
			continue;
		}
		cout << Pc->pnext->c << "x^" << Pc->pnext->e;
		Pc = Pc->pnext;
		while (Pc->pnext)
		{
			cout << "+";
			cout << Pc->pnext->c << "x^" << Pc->pnext->e;
			Pc = Pc->pnext;
		}
		cout << endl;
		Pc = Pahead;
	}
	return 0;
}

输出结果：

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述在这里插入图片描述

案例实现方式与第一百零六天写的资源管理系统类似，这里不再赘述。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/42647.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

去括号问题(C++处理)

去括号问题(C++处理)

继http://t.csdn.cn/kIcUT后的文章 题目描述 当老师不容易&#xff0c;尤其是当小学的老师更难:现在的小朋友做作业喜欢滥用括号。 虽然不影响计算结果&#xff0c;但不够美观&#xff0c;容易出错&#xff0c;而且可读性差。但又不能一棒子打死&#xff0c;也许他们就是将来的…
阅读更多...
多目标灰狼算法(MOGWO)的Matlab代码详细注释及难点解释

多目标灰狼算法(MOGWO)的Matlab代码详细注释及难点解释

目录 一、外部种群Archive机制 二、领导者选择机制 三、多目标灰狼算法运行步骤 四、MOGWO的Matlab部分代码详细注释 五、MOGWO算法难点解释 5.1 网格与膨胀因子 5.2 轮盘赌方法选择每个超立方体概率 为了将灰狼算法应用于多目标优化问题,在灰狼算法中引入外部种群Archi…
阅读更多...
extern “C“的作用效果

extern “C“的作用效果

代码 1.cpp #include <string.h>struct s {char data1;short data2;int data3;long data4; };// 定义C函数&#xff0c;汇编符号标头由g编译器按规则生成 void fun(void) {struct s src;src.data1 A;src.data2 2;src.data3 3;src.data4 4;struct s res;memcpy(&…
阅读更多...
深度学习——过拟合和Dropout

深度学习——过拟合和Dropout

基本概念 什么是过拟合&#xff1f; 过拟合&#xff08;Overfitting&#xff09;是机器学习和深度学习中常见的问题之一&#xff0c;它指的是模型在训练数据上表现得很好&#xff0c;但在未见过的新数据上表现较差的现象。 当一个模型过度地学习了训练数据的细节和噪声&#…
阅读更多...
web地理信息系统开发开源架构设计

web地理信息系统开发开源架构设计

Web端地理信息软件系统研发一般包括前端展示、后端服务、地图服务、数据库等几大部分。为了节约项目经费&#xff0c;实现地理信息软件项目研发&#xff0c;采用了开源技术路线&#xff0c;通过对比&#xff0c;采用如下开发架构&#xff1a; 1、前端展示 前端展示采用angular…
阅读更多...
FTP与HTTP: 哪种协议更适合大文件传输？

FTP与HTTP: 哪种协议更适合大文件传输？

随着互联网技术的发展&#xff0c;网络传输已成为了现代社会中不可或缺的一部分。无论是文本、图像、音频、视频等各种类型的数据&#xff0c;相应的传输协议也在不断地发展和更新。FTP&#xff08;File Transfer Protocol&#xff09;和HTTP&#xff08;Hyper Text Transfer P…
阅读更多...
java电子病历系统源码

java电子病历系统源码

电子病历系统采取结构化与自由式录入的新模式&#xff0c;自由书写&#xff0c;轻松录入。化实现病人医疗记录&#xff08;包含有首页、病程记录、检查检验结果、医嘱、手术记录、护理记录等等。&#xff09;的保存、管理、传输和重现&#xff0c;取代手写纸张病历。不仅实现了…
阅读更多...
EGE-UNet, 轻量化U-Net

EGE-UNet, 轻量化U-Net

随着transform 的出现&#xff0c;现在语义分割网路结构越来越复杂&#xff0c;轻量化网路也较少了&#xff0c;有些轻量化也只是名义上的轻量化。今天我看到一篇很好的论文&#xff0c;上海交大发表在 MICCAI 2023 的最新研究工作&#xff0c;一个称为Efficient Group Enhance…
阅读更多...
信息与通信工程学科面试准备——通信原理｜信息与通信工程方向保研面试题集｜BUAA

信息与通信工程学科面试准备——通信原理｜信息与通信工程方向保研面试题集｜BUAA

注意&#xff1a; 以下内容&#xff0c;基本上都是二系通信方向保研复试被提问过的内容。如果是专硕&#xff0c;那么电路分析、电磁场、DSP等方面的问题会更多&#xff0c;这里主要针对通信学硕。以下内容不能保证全覆盖&#xff1a;有的同学被问到什么是范德蒙行列式&#x…
阅读更多...
html a标签换行显示

html a标签换行显示

文章目录 用css display属性不用css&#xff0c;可以用<br>标签换行示例 用css display属性 可以使用CSS的display属性来实现多个a标签每行显示一个。 HTML代码&#xff1a; <div class"link-container"><a href"#">Link 1</a>…
阅读更多...
前端工程化第一章：webpack5基础（上）

前端工程化第一章：webpack5基础（上）

文章目录 1. 什么是webpack&#xff1f;2. webpack使用2.2. 前置知识2.1. 创建一个项目 3. webpack打包3.1. 创建一个webpack.config.js文件3.2. 入口&#xff08;entry&#xff09;3.2.1. webpack.config.js3.2.2. src/index.js3.2.3. package.json 3.3. 输出&#xff08;outp…
阅读更多...
基于深度学习的高精度课堂人脸检测系统（PyTorch+Pyside6+YOLOv5模型）

基于深度学习的高精度课堂人脸检测系统（PyTorch+Pyside6+YOLOv5模型）

摘要&#xff1a;基于深度学习的高精度课堂人脸检测系统可用于日常生活中或野外来检测与定位课堂人脸目标&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的课堂人脸目标检测识别&#xff0c;另外支持结果可视化与图片或视频检测结果的导出。本系统采用YOLOv5目标…
阅读更多...
【论文阅读】2020ECCV-DFDNet

【论文阅读】2020ECCV-DFDNet

Blind Face Restoration via Deep Multi-scale Component Dictionaries 中文&#xff1a;基于深度多尺度分量字典的盲人脸复原 paper&#xff1a; code&#xff1a;https://github.com/csxmli2016/DFDNet 摘要&#xff1a; 近年来&#xff0c;基于参考的人脸恢复方法因其在真…
阅读更多...
使用Seata解决分布式事务问题

使用Seata解决分布式事务问题

说明&#xff1a;在分布式架构下&#xff0c;一个请求需要多个微服务来实现。当一个请求牵扯到多个微服务时&#xff0c;事务问题就变得麻烦起来。 问题描述 现在有三个服务&#xff0c;分别是账户服务、库存服务和订单服务&#xff0c;生成一个订单&#xff0c;需要确保商品…
阅读更多...
Docker 命令（二）

Docker 命令（二）

查看 docker 版本信息 docker version #查看版本信息docker 信息查看 docker info Client:Context: defaultDebug Mode: falsePlugins:app: Docker App (Docker Inc., v0.9.1-beta3)buildx: Build with BuildKit (Docker Inc., v0.5.1-docker)Server:Containers: 0 …
阅读更多...
Python补充笔记3-bug问题

Python补充笔记3-bug问题

目录 一、Bug 粗心导致的语法错误​ ​编辑 知识不熟练导致的错误​ 思路不清晰导致的问题​ 被动掉坑​ 二、try…except…else结构​ 三、try…except…else…finally结构​ 四、常见异常类型​编辑traceback模块 pycharm调试 一、Bug 粗心导致的语法错误 知识不熟练导致的…
阅读更多...
【Vue 面试题10道】我好像之前想过要写，不过之前JavaScript面试题比较多，就暂时略过了，这些应该几乎把常问的都包括了

【Vue 面试题10道】我好像之前想过要写，不过之前JavaScript面试题比较多，就暂时略过了，这些应该几乎把常问的都包括了

博主&#xff1a;_LJaXi Or 東方幻想郷 专栏&#xff1a; 前端面试题 开发工具&#xff1a;Vs Code 本题针对 Vue2 这些几乎把常用的都包括了&#xff0c;问别的就没意思了&#xff0c;毕竟工作拧螺丝嘛 我都好久不用Vue了&#xff0c;不过用了React再回看Vue感觉好简单啊… 其…
阅读更多...
Dubbogo 详解

Dubbogo 详解

Dubbogo 详解 简介 dubbo功能很强大的微服务开发框架&#xff0c;支持多种通信协议&#xff0c;并具有流量治理的功能。 dubbo在有了大转变&#xff0c;拥抱了云原生&#xff0c;从哪些方面可以体现呢&#xff1f; 推出了自己的Trip协议修复了服务发现的级别&#xff0c;之…
阅读更多...
20230723红米Redmi Note8Pro掉在水里的处理步骤

20230723红米Redmi Note8Pro掉在水里的处理步骤

20230723红米Redmi Note8Pro掉在水里的处理步骤 2023/7/23 18:18 百度搜搜&#xff1a;小米手机进水 破音怎么处理 Redmi Note8Pro 6400万全场景四摄 液冷游戏芯 4500mAh长续航 NFC 18W快充 红外遥控 https://www.zhiliancy.com/a/q5podmr12.html 首页 / 热文 / 内容 小米喇叭…
阅读更多...
【从删库到跑路】MySQL数据库的索引(一)——索引的结构(BTree B+Tree Hash)，语法等

【从删库到跑路】MySQL数据库的索引(一)——索引的结构(BTree B+Tree Hash)，语法等

&#x1f38a;专栏【MySQL】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 &#x1f970;欢迎并且感谢大家指出小吉的问题 文章目录 &#x1f354;概述&#x1f354;索引结构⭐B-Tree多路平衡查找树&#x1f3f3;️‍&a…
阅读更多...
最新文章

Copyright @ 2022~2023