我想使用java实现只使用链表而不使用任何数组的合并排序。但我陷入了一个逻辑错误;我的代码消除了一些输入并对剩余部分进行排序。我应用了三个类:Divide
、
Merg
、
MergSort
,如下所示:
public class Divide {
List firstList = new List();
List secondList = new List();
public int GetLength(List list) {
int Length = 0;
Link temp = new Link();
temp.next = list.head.next;
while (temp.next != null) {
temp.next = temp.next.next;
Length++;
}
return Length;
}
public List rightSide(List list) {
int Length = GetLength(list);
Link temp = new Link();
temp.next = list.head.next;
for (int i = 1; i <= Math.floor(Length / 2); i++) {
firstList.Insert(temp.next.data);
temp.next = temp.next.next;
}
return firstList;
}
public List leftSide(List list) {
int Length = GetLength(list);
Link temp = new Link();
temp.prev = list.head.prev;
for (int i = 1; i <= Math.ceil(Length / 2); i++) {
secondList.Insert( temp.prev.data);
temp.prev = temp.prev.prev;
}
return secondList;
}
}
合并:
public class Merg {
public List MergedList = new List();
private List Temp = new List();
public List Merg (List one, List two)
{
Link onelink = new Link();
Link twolink = new Link();
onelink.next = one.head.next;
twolink.next = two.head.next;
while (onelink.next!= null || twolink.next!= null)
{
if(onelink.next!= null && twolink.next != null)
{
if(onelink.next.data < twolink.next.data)
{
Temp.Insert(onelink.next.data);
onelink.next = onelink.next.next;
}
else
{
Temp.Insert(twolink.next.data);
twolink.next = twolink.next.next;
}
}
if (onelink.next != null && twolink.next == null)
{
Temp.Insert(onelink.next.data);
onelink.next = onelink.next.next;
}
if (twolink.next != null && onelink.next == null)
{
Temp.Insert(twolink.next.data);
twolink.next = twolink.next.next;
}
}
if (Temp.head.next.data > Temp.head.prev.data)
{
while (Temp.head.next != null)
{
MergedList.Insert(Temp.head.next.data);
Temp.head.next = Temp.head.next.next;
}
}
else
{
MergedList.head.next = Temp.head.next;
}
return MergedList;
}
}
默格索特:
public class MergSort {
public List mergSort (List list)
{
Divide divide = new Divide();
Merg merg = new Merg();
if (divide.GetLength(list) > 1) {
return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
}
else
{
return list;
}
}
}
虽然我也编写了链接和列表类,但我认为这里面没有问题。(然而,如果有必要,我会提到它们)现在,当我导入一些输入时:{100,3,1,7,6},输出是:3,6,7100。(1已消除!)或者另一个例子:{100,3,1}输出是:1100(其中是3°)
我想知道是否有人能帮我。。。
链接:
public class Link {
public double data;
public Link prev;
public Link next;
}
列表:
public class List {
public Link head = new Link();
public void setHead(Link head) {
this.head = head;
head.prev = null;
head.next = null;
}
public void Insert(double x)
{
Link link = new Link();
link.data = x;
if (head.next == null)
{
head.next = link;
head.prev = link;
}
else
{
head.next.prev = link;
link.next = head.next;
head.next = link;
}
}
public Link delete()
{
Link temp = new Link();
temp = head;
head = head.next;
return temp;
}
public Link search(double x)
{
Link link = new Link();
link.next = head;
while (link.next.data != x)
{
link.next = link.next.prev;
}
return link.next;
}
}
我已经调试了很多,但我无法理解你的划分类。你根本不需要它。
public class MergSort {
public List mergSort(List list) {
Divide divide = new Divide();
Merg merg = new Merg();
int n = list.getLength();
if (n > 1) {
// return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
Link cursor = list.head.next;
List left = new List();
List right = new List();
// for (i = 0; ....... i will be 0 if head is not dummy
for (int i = 1; cursor != null; i++) {
if (i <= n/2)
left.Insert(cursor.data);
else
right.Insert(cursor.data);
cursor = cursor.next;
}
left = mergSort(left);
right = mergSort(right);
return merg.Merg(left, right);
} else {
return list;
}
}
}
在您的List
类中创建一个getLlong()
方法。它应该在List
类中,因为您想要列表的长度。
public int getLength() {
int Length = 0;
Link temp = head.next;
while (temp != null) {
temp = temp.next;
Length++;
}
return Length;
}
另外,将链接类重命名为节点。因为链接是指对象之间的链接或节点之间的边。您真正想要的是一个节点。这让人困惑。
在您的列表
类中,您定义了如下头:
public Link head = new Link();
我不明白你为什么需要一个假头链表。
具有虚拟头的链表基本上是没有值的头,因此是虚拟的。
因为你的虚拟头,你正在Divide
类中从i=1
开始你的for循环。为什么要把事情复杂化?如果你真的需要一个虚拟头,那么保留它或像这样定义它:
public Link head;
// don't instantiate the head. It's just a reference
此外,您似乎创建了一个半圆形链表。我的意思是头。prev指向列表中的最后一个链接/节点。如果你真的想要一个循环链表,那就指向你的尾巴。下一步是头。
以下是循环链表的样子:
或者,如果你不想要一个循环列表,那么不要指向你的头。上一个对象。
在列表中的Insert()方法中:
if (head.next == null)
{
head.next = link;
// remove head.prev = link;
}
我试图借助单链表编写合并排序,节点定义如下, 合并排序的工作方式如下: i、 将未排序的列表划分为n个子列表,每个子列表包含1个元素(1个元素的列表被视为已排序)。 二、。重复合并子列表以生成新排序的子列表,直到只剩下1个子列表。这将是排序列表。代码如下所示。 我像这样打入会电话, 结果是,所有负值似乎都消失了。这里有什么问题?
我有一个练习,我必须在链表中插入一个字符串。假设字符串如下所示: 在合并排序之后,链表应该是这样的: 问题是在我的合并排序代码中,我收到以下内容: 所有的单词都被排序,但第一个单词(原始列表的头部)不是。 我有两个类:TextList和WordNode。 WordNode类有两个属性: TextList类只有一个属性:链接列表头的地址: 我有一个构造函数,在其中我将字符串随机插入到一个链表中。最后
合并排序通常是对链表排序的首选方式。链表缓慢的随机访问性能使得一些其他算法(如quicksort)表现不佳,而另一些算法(如heapsort)则完全不可能。我一直在努力在链表上做归并排序。它不断返回一个错误。我正在提供我试图执行的代码。请一定要帮我。它不断给出运行时错误。
//我怎样才能实现这个功能?我想合并两个未排序的链表。
NowCoder 题目描述 解题思路 递归 // java public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= lis
假设列表“A”是1- 请回顾一下这个,帮我即兴创作