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

链表的合并和分解-习题1-5

10月前 作者：头歌作业 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了链表的合并和分解-习题1-5。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：两个递增有序链表合并为一个递增有序链表

本关任务：编写一个递增有序链表的合并程序。

#include<iostream>
#include<fstream>
using namespace std;
#define ERROR 0

typedef struct LNode //定义单链表
{
	int data;
	struct LNode *next;
} LNode, *LinkList;

int num_a, num_b;


void InitList_L(LinkList &L) //创建单链表
{
	L = new LNode;
	L->next = NULL;
}

void input(LinkList &L, int n) //依次往单链表L里输入数据
{
	int i;
	LNode *p, *r;
	r = L;
	while (n --) 
	{
		p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}

}

void output(LinkList L) //依次输出单链表里的每个元素
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) {
		if (i)
			cout << " ";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC) //算法设计1 
{
	//已知单链表LA和LB的元素按值递增排列
	//归并LA和LB得到新的单链表LC，LC的元素也按值递增排列，不允许有重复数据 
	/*******************************Begin***************************/
    LinkList k = LA,p = LA -> next,q = LB -> next;

    while(p && q)
    {
        int a = p -> data,b = q -> data;
        if(a <= b)
        {
            k -> next = p;
            k = p;
            p = p -> next;
            if(a == b) q = q -> next;
        }
        else
        {
            k -> next = q;
            k = q;
            q = q -> next;
        }
    }

    k -> next = p ? p : q;

    LC = LA;
    /********************************End****************************/
} //MergeList_L()

int main() 
{
	LinkList La, Lb, Lc;
	
	scanf("%d %d", &num_a, &num_b);
	
	InitList_L(La); //La表的创建
	input(La, num_a); //依次往单链表La里输入数据

	InitList_L(Lb); //Lb表的创建	
	input(Lb, num_b); //依次往单链表La里输入数据

	InitList_L(Lc);
	MergeList_L(La, Lb, Lc); //将单链表La和Lb进行合并

	output(Lc);

	return 0;
}

第2关：两个非递减链表合并成一个非递增链表

本关任务：编写一个非递增有序链表的合并程序。

思路 ： 可以先将两个递增链表合并成一个递增链表，再将得到的新链表翻转（用头插法）。

#include<iostream>
#include<fstream>
using namespace std;
#define ERROR 0

typedef struct LNode //定义单链表
{
	int data;
	struct LNode *next;
} LNode, *LinkList;

int num_a, num_b;


void InitList_L(LinkList &L) //创建单链表
{
	L = new LNode;
	L->next = NULL;
}

void input(LinkList &L, int n) //依次往单链表L里输入数据
{
	int i;
	LNode *p, *r;
	r = L;
	while (n --) 
	{
		p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}

}

void output(LinkList L) //依次输出单链表里的每个元素
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) {
		if (i)
			cout << " ";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC) //算法设计1 
{
	//已知单链表LA和LB的元素按值非递减排列
	//归并LA和LB得到新的单链表LC，LC的元素按值非递增排列，允许有重复数据 
    /****************************Begin***************************/
    LinkList k = LA,p = LA -> next,q = LB -> next;

    while(p && q)
    {
        int a = p -> data,b = q -> data;
        if(a <= b)
        {
            k -> next = p;
            k = p;
            p = p -> next;
        }
        else
        {
            k -> next = q;
            k = q;
            q = q -> next;
        }
    }

    k -> next = p ? p : q;

    k = LA -> next;
    LinkList t = k -> next;

    while(t)
    {
        LinkList m = t;
        t = t -> next;

        m -> next = LA -> next;
        LA -> next = m;
    }
    /***************************End******************************/
	
    k -> next = NULL;
    LC = LA;
}

int main() 
{
	LinkList La, Lb, Lc;
	
	scanf("%d %d", &num_a, &num_b);
	
	InitList_L(La); //La表的创建
	input(La, num_a); //依次往单链表La里输入数据

	InitList_L(Lb); //Lb表的创建	
	input(Lb, num_b); //依次往单链表La里输入数据

	InitList_L(Lc);
	MergeList_L(La, Lb, Lc); //将单链表La和Lb进行合并

	output(Lc);

	return 0;
}

第3关：两个链表的交集

本关任务：编写两个链表交集的程序。

定义一个新的指针 k 指向链表 A 的头结点，遍历链表 A 和 B，找到相同的元素，将A中节点链到  k 后面，再让 k 指向该节点，最后让 k 的后继指向 NULL。

#include<iostream>
#include<fstream>
using namespace std;
#define ERROR 0

typedef struct LNode //定义单链表
{
	int data;
	struct LNode *next;
} LNode, *LinkList;

int num_a, num_b;


void InitList_L(LinkList &L) //创建单链表
{
	L = new LNode;
	L->next = NULL;
}

void input(LinkList &L, int n) //依次往单链表L里输入数据
{
	int i;
	LNode *p, *r;
	r = L;
	while (n --) 
	{
		p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}

}

void output(LinkList L) //依次输出单链表里的每个元素
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) {
		if (i)
			cout << " ";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC) //算法设计3 
{
	//已知单链表LA和LB的元素按值递增排列
	//将两个链表的交集数据存放在A链表当中 
	/*******************************************Begin***************************************************/
    LinkList k = LA,p = LA -> next,q = LB -> next;

    while(p && q)
    {
        int a = p -> data,b = q -> data;
        if(a < b) p = p -> next;
        else if(a > b) q = q -> next;
        else
        {
            k -> next = p;
            k = p;
            p = p -> next;
        }
    }

    k -> next = NULL;
    LC = LA;
    /**********************************************End*************************************************/
} //MergeList_L()

int main() 
{
	LinkList La, Lb, Lc;
	
	scanf("%d %d", &num_a, &num_b);
	
	InitList_L(La); //La表的创建
	input(La, num_a); //依次往单链表La里输入数据

	InitList_L(Lb); //Lb表的创建	
	input(Lb, num_b); //依次往单链表La里输入数据

	InitList_L(Lc);
	MergeList_L(La, Lb, Lc); //将单链表La和Lb进行合并

	output(Lc);

	return 0;
}

第4关：两个递增链表的差集

本关任务：编写一个递增有序链表差集的程序。

找到链表 A 中有，但链表 B 中没有的元素

#include<iostream>
#include<fstream>
using namespace std;
#define ERROR 0

typedef struct LNode //定义单链表
{
	int data;
	struct LNode *next;
} LNode, *LinkList;

int num_a, num_b;


void InitList_L(LinkList &L) //创建单链表
{
	L = new LNode;
	L->next = NULL;
}

void input(LinkList &L, int n) //依次往单链表L里输入数据
{
	int i;
	LNode *p, *r;
	r = L;
	while (n --) 
	{
		p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}

}

void output(LinkList L) //依次输出单链表里的每个元素
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) {
		if (i)
			cout << " ";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}

void MergeList_L(LinkList &LA, LinkList &LB, int &n) //算法设计4 
{
	//已知单链表LA和LB的元素按值递增排列
	//将两个链表的差集数据存放在A链表当中 ,并返回元素个数 
	/***************************************Begin**************************/
    LinkList k = LA,p = LA -> next,q = LB -> next;

    while(p && q)
    {
        int a = p -> data,b = q -> data;
        if(a < b)
        {
            k -> next = p;
            k = p;
            p = p -> next;
            n ++ ;
        }
        else if(a == b) p = p -> next,q = q -> next;
        else q = q -> next;
    }

    k -> next = NULL;
    /**************************************End***************************/
} //MergeList_L()

int main() 
{
	LinkList La, Lb, Lc;
	
	scanf("%d %d", &num_a, &num_b);
	
	InitList_L(La); //La表的创建
	input(La, num_a); //依次往单链表La里输入数据

	InitList_L(Lb); //Lb表的创建	
	input(Lb, num_b); //依次往单链表La里输入数据
	
	int n;
	MergeList_L(La, Lb, n); //将单链表La和Lb进行合并

	cout << n << endl;
	output(La);
	
	return 0;
}

第5关：分解链表

本关任务：编写一个链表的分解程序。文章来源地址https://www.toymoban.com/news/detail-735500.html

#include<iostream>
#include<fstream>
using namespace std;
#define ERROR 0

typedef struct LNode //定义单链表
{
	int data;
	struct LNode *next;
} LNode, *LinkList;

int num_a, num_b;


void InitList_L(LinkList &L) //创建单链表
{
	L = new LNode;
	L->next = NULL;
}

void input(LinkList &L, int n) //依次往单链表L里输入数据
{
	int i;
	LNode *p, *r;
	r = L;
	while (n --) 
	{
		p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}

}

void output(LinkList L) //依次输出单链表里的每个元素
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) {
		if (i)
			cout << " ";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}

void DivList_L(LinkList &LA, LinkList &LB, LinkList &LC) //算法设计5 
{
	//已知单链表LA
	//将LA拆分成两个表，LB中的数据小于0， LC中的数据大于0 
	/**************************Begin****************************/
    InitList_L(LB);
    InitList_L(LC);

    LinkList p = LA -> next,b = LB,c = LC;

    while(p)
    {
        LinkList t = p;
        p = p -> next;
        if(t -> data > 0)
        {
            t -> next = c -> next;
            c -> next = t;
        }
        if(t -> data < 0)
        {
            t -> next = b -> next;
            b -> next = t;
        }
    }
    /************************End******************************/
} 

int main() 
{
	LinkList La, Lb, Lc;
	
	scanf("%d", &num_a);
	
	InitList_L(La); //La表的创建
	input(La, num_a); //依次往单链表La里输入数据
	
	DivList_L(La, Lb, Lc); //将单链表La拆分成Lb和Lc 

	output(Lb);
	cout << endl;
	output(Lc);
	
	return 0;
}

到了这里，关于链表的合并和分解-习题1-5的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • 【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    正如标题所说，本文会图文详细解析三道单链表OJ题，分别为：  反转链表 （简单）  链表的中间节点 （简单）  链表的回文结构 （较难） 把他们放在一起讲的原因是：  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说？请往下看： 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 【数据结构】链表的回文结构

    【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(55)
  • 【数据结构】——线性表的相关习题

    【数据结构】——线性表的相关习题

    1、线性表的顺序存储结构是一种（）存储结构。 A、顺序存取 B、随机存取 C、索引存取 D、散列存取 解析： （B） 顺序存储结构 的可以实现 随机存取 ，可以在O(1)内通过首地址和元素序号找到元素，每个元素占用最少的存储空间，其存储密度高，但只能使用相邻的一块存储

    2024年02月14日
    浏览(39)
  • 【数据结构】链表的分类和双向链表

    【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作，推荐与上篇配合阅读，效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构： 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(39)

  • 数据结构-二叉链表的结构与实现

    目录 一、引言 二、什么是二叉链表 三、二叉链表的结构 四、二叉链表的实现 1. 创建二叉链表 2. 遍历二叉链表 3. 插入节点 4. 删除节点 五、应用场景 六、总结 七、代码示例 数据结构是计算机科学中的重要概念，它是计算机程序设计的基础。二叉链表是一种常见的数据结构

    2024年02月08日
    浏览(49)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后

    2024年02月21日
    浏览(51)
  • 【数据结构】十字链表的画法

    【数据结构】十字链表的画法

    有向边又称为弧 假设顶点 v 指向 w，那么 w 称为弧头，v 称为弧尾 顶点节点采用顺序存储 顶点节点 data：存放顶点的信息 firstin：指向以该节点为终点（弧头）的弧节点 firstout：指向以该节点为起点（弧尾）的弧节点 弧节点 tailvex：起点（弧尾）在数组中的索引 headvex：终点（

    2024年02月11日
    浏览(49)
  • 【数据结构】双向链表的实现

    【数据结构】双向链表的实现

    我要扼住命运的咽喉，他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表，创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(47)
  • 数据结构——双向链表的实现

    数据结构——双向链表的实现

    注意： 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点，实际为“ 哨兵位 ”，哨兵位节点不存储任何有效元素，只

    2024年02月06日
    浏览(48)
  • 【（数据结构）— 双向链表的实现】

    【（数据结构）— 双向链表的实现】

    注意： 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念，实际前面的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点，实际为 “哨兵位” ，哨兵位节点不存储任何有效元素，只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包