首页 > 其他分享 >【数据结构】线性表作业——归并排序

【数据结构】线性表作业——归并排序

时间:2024-09-17 14:48:57浏览次数:13  
标签:链表 归并 NULL LNode next LinkList 数据结构 data 线性表

【问题描述】

有一个含n(n<=200000)个整数的无序序列,采用链表的二路归并排序实现递增排序

【输入形式】

一行字符串,包含多个整数,每个数之间用空格分开。

【输出形式】

递增排序的结果,每个数之间用空格分开。

【样例输入】

9 4 7 6 2 5 8 1 3

【样例输出】

1 2 3 4 5 6 7 8 9

【样例说明】

测试数据的文件名为in.txt,输出文件名为out.txt

【解题思路】

参考LeetCode148——排序链表
利用递归的方法进行排序
利用双指针法,对原链表进行分割,分成两个子链表,再对子链进行分割,直到只有一个结点,此时是递归终点。
然后进行合并,将两个有序链表合并为一个有序链表
具体过程如下图:
在这里插入图片描述

【完整代码】

(测试数据从"in.txt"文件中读取,结果输出到"out.txt"文件中)

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

void InitList(LinkList& L)
{
	L = NULL;
}

void CreateList(LinkList& L, vector<int>& data) //尾插法创建不带头节点的单链表
{
	LNode* r = L;
	LNode* s;
	for (int i = 0; i < data.size(); i++)
	{
		s = new LNode;
		s->data = data[i];
		s->next = NULL;
		if (r == NULL)
		{
			r = s;
			L = s;
		}
		else
		{
			r->next = s;
			r = s;
		}
	}
}

LinkList MergeList(LinkList& a, LinkList& b) //合并两有序链表
{
	LNode* head = new LNode;
	head->next = NULL;
	LNode* r = head;
	while (a != NULL && b != NULL)
	{
		if (a->data < b->data)
		{
			r->next = a;
			a = a->next;
		}
		else if(a->data > b->data)
		{
			r->next = b;
			b = b->next;
		}
		else  //两数相等时,不去重(该操作是因为提交作业时发现答案中依然保留了重复的数)
		{
			r->next = a;
			a = a->next;
			r = r->next;
			r->next = b;
			b = b->next;
		}
		r = r->next;
	}
	//最后要注意将没有遍历完的链表直接连接到新链表末尾
	if (a)  
		r->next = a;
	if (b)
		r->next = b;
	return head->next;
}

LinkList SortList(LinkList& L)
{
	//链表为空或者只有一个结点,直接返回
	if (L == NULL || L->next == NULL)
		return L;
	//利用快慢指针法找到中间结点
	LNode* slow = L;
	LNode* fast = L->next;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	//分割为两条子链
	LNode* mid = slow->next;
	slow->next = NULL;
	//对两条子链进行排序
	LNode* left = SortList(L);
	LNode* right = SortList(mid);
	//合并子链
	return MergeList(left, right);
}

int main()
{
	ifstream ifs;
	ifs.open("in.txt");
	if (!ifs.is_open())
		cout << "open file failed!" << endl;
	vector<int>data;
	int temp=0;
	while (ifs >> temp)
		data.push_back(temp);
	ifs.close();
	LinkList L;
	InitList(L);
	CreateList(L, data);

	LinkList ans=SortList(L);
	ofstream ofs;
	ofs.open("out.txt");
	LNode* p = ans;
	while (p)
	{
		ofs << p->data << " ";
		p = p->next;
	}
	ofs.close();
}

标签:链表,归并,NULL,LNode,next,LinkList,数据结构,data,线性表
From: https://blog.csdn.net/2402_84389946/article/details/142303470

相关文章

  • 数据结构(九)——队列(Queue)(上)
    一、概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstInFirstOut)入队列:进行插入操作的一端称为队尾(Tail/Rear)出队列:进行删除操作的一端称为队头(Head/Front)二、队列的使用在Java中,Queue是个接口,底层是通过链表......
  • 【数据结构】堆
    二叉树的顺序结构普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是......
  • 数据结构-树和二叉树
      树和二叉树 1.树的概念   树tree     是n(n>=0)个节点的有限集    在任意的一个非空树中       (1)有且仅有一个特定的被称为根(root)的节点       (2)当n>1时,其余的节点可分为m(m>0)个互不相交的有限......
  • C#数据结构与算法实战入门指南
    前言在编程领域,数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚分享一些非常不错的C#数据结构与算法实战教程,希望可以帮助到有需要的小伙伴。C#经典十大排序算法主要讲解C#经典......
  • 数据结构与算法(四)线性表的抽象数据类型描述
    一、回顾    上一篇我们讲到了线性表的定义,讲到了所谓抽象数据类型就是把数据类型和操作捆版在一起。那么我们接下来分析一下,线性表应该有什么样的相关操作呢?。    从一个例子来看一看,回到我们上一篇开学参加升旗仪式的例子:    老师把同学们按照规......
  • [Python手撕]归并排序
    classSolution:defsortArray(self,nums:List[int])->List[int]:defmerge(nums1,nums2):ifnotnums1andnotnums2:returnNoneifnotnums1:returnnums2ifnotnums2......
  • Java-数据结构-二叉树-习题(二) (´▽`)ノ
    文本目录:❄️一、习题一(分层遍历):   ▶ 思路:    ▶代码:❄️二、习题二(二叉树的最近公共祖先):    ▶ 思路: ▶代码: ❄️三、习题三(从前序和中序遍历序列中构造二叉树):     ▶ 思路:  ▶代码:❄️四、习题四(从中序和后序遍历序列中构造二......
  • C++数据结构-二叉树的三种遍历方法(进阶篇)
    1.遍历简介:树作为非线性数据结构,在我们取出数据时就需要设计遍历,所谓遍历,就是按照一定的规则性,将数据结构中的所有数据全部依次访问,而二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序,这便是我们常规定的先序......
  • C++数据结构-二叉树的存储方法(基础篇)
    1.简介根据前文的介绍,我们知道了二叉树的性值,其就是一种每一个结点中只允许拥有左右孩子(或为空)的树,这种数据结构在我们的实际设计中非常常用,如前文提到的STL中的set集合,其底层就是一颗标准的红黑树(二叉树的一种),我们这里以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达......
  • 数据库索引分类以及底层数据结构
    数据库索引的分类和底层数据结构直接决定了它在不同场景下的性能和适用性。以下是数据库索引的主要分类及其底层数据结构的详细分析:一、数据库索引的分类1.主键索引(PrimaryKeyIndex)分类:唯一性索引的一种特殊形式。特点:对主键列创建的索引,保证唯一性且不能为空。底层结构:B......