我在 c++ 中遇到了一些与排序链表相关的问题。我得到了一个要完成的任务，我已经创建了逻辑，但我的链表没有排序。
该程序要求用户输入名称，x和y坐标，以便在名为"auf2_euclidcalc"的函数中计算与原点的欧几里得距离。然后，我在函数"auf5_display(("中使用名为"auf2_euclidcalc"的函数来显示距离值。
该程序完美地编译并显示用户的输入，但不按升序对与原点的距离进行排序(排序功能为"auf4_sort(("(。
我需要有关这方面的帮助来排序与原点的距离以及相应的 x 和 y 坐标。有人可以帮忙吗？请更正排序功能中的错误以使其排序。
提前感谢！ 请在下面查看我的程序。
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;
struct thenode //auf 1
{
string nameofobstacle;
double x, y;
double distancetotheorigin;
thenode *next;
};
thenode *head = nullptr;
thenode *last = nullptr ;
void insertobstacle (string nameofobstacle, double x, double y);
double auf2_euclidcalc (double x1, double x2, double y1, double y2);
void auf4_sort ();
void auf5_display();
void outputobstacles();
void auf6_pointstobedeleted ();
void insertobstacle (string nameofobstacle, double x, double y)
{
thenode *storenewnode = new thenode; // newstorefourdata->distancetotheorigin = distancetotheorigin;
storenewnode->nameofobstacle = nameofobstacle;
storenewnode->x = x;
storenewnode->y = y;
storenewnode->next = head;
head = storenewnode;
double x2, y2;
x2 = storenewnode->x;
y2 = storenewnode->y;
auf2_euclidcalc(0, x2, 0, y2);
}
double auf2_euclidcalc (double x1, double x2, double y1, double y2) //Auf 2
{
thenode *ptr_storedx_y = new thenode;
double d; //how to link this to the structure so that we can store x and y
double p1= x1-x2;
double p2= y1-y2;
ptr_storedx_y->distancetotheorigin= pow(p1, 2) + pow(p2, 2);
d= sqrt(ptr_storedx_y->distancetotheorigin); //obs.d
return d;
}
void auf5_display()
{
double d;
thenode *tempo=new thenode;
tempo=head;
while(tempo!=nullptr)
{
double x1, y1, x2, y2;
x1=0; //from origin
y1=0; //from origin
x2=tempo->x; //inputted dist
y2=tempo->y; //inputted dist
cout << "obstacle " << tempo->nameofobstacle << ": ( " <<setprecision(3) << tempo->x << " , " <<
setprecision(3) <<tempo->y << " ) , ";
tempo = tempo->next;
cout<< "distance: " << auf2_euclidcalc(x1, x2, y1, y2) << endl;
}
}
void auf4_sort ()
{
double x_cor,y_cor;
string p_name;
double temproll;
thenode *temphead = head;
auf2_euclidcalc(0, x_cor, 0, y_cor);
int counter = 0;
while (temphead!=nullptr) //IT SHOULD CHANGE TO TEMP NULL
{
temphead = temphead->next;
counter++;
}
temphead = head;
for (int j=0; j<counter; j++)
{
while (temphead->next!=nullptr) //iterate through list until next is null
{
if (temphead->distancetotheorigin > temphead->next->distancetotheorigin)
{
temproll = temphead->distancetotheorigin;
temphead->distancetotheorigin = temphead->next->distancetotheorigin;
temphead->next->distancetotheorigin = temproll;
p_name = temphead->nameofobstacle;
temphead->nameofobstacle = temphead->next->nameofobstacle;
temphead->next->nameofobstacle = p_name;
x_cor = temphead->x;
temphead->x = temphead->next->x;
temphead->next->x = x_cor;
y_cor = temphead->y;
temphead->y = temphead->next->y;
temphead->next->y = y_cor;
temphead = temphead->next;
}
else
temphead = temphead->next;//increment node
}
temphead = head;//reset temphead
}
}
void auf6_pointstobedeleted ()
{
thenode *deletenow;
while (head != nullptr)
{
deletenow = head;
head = head->next;
cout << "delete: " << deletenow->nameofobstacle << " :DELETED: " << endl;
delete deletenow;
}
}
int main ()
{
thenode *ptrstoring = new thenode;
while (cin)
{
cout<< "string describing obstacle ('end' for end of input): "<<endl;
cin>> ptrstoring->nameofobstacle;
if (ptrstoring->nameofobstacle=="end" || ptrstoring->nameofobstacle== "END")
{
break;
}
else
{
cout<< "x and y coordinate: " <<endl;
cin>> ptrstoring->x;
cin>> ptrstoring->y;
insertobstacle (ptrstoring->nameofobstacle, ptrstoring->x, ptrstoring->y);
}
}
auf4_sort ();
auf5_display();
auf6_pointstobedeleted ();
return 0;
}
我不扫描整个代码，但我可以提出几点。
我想到的问题是什么，为什么您在auf2_euclidcalc函数中创建新节点并且以后不使用它产生内存泄漏。
关于您的排序算法。在第二个循环中，您一遍又一遍地遍历整个列表，但在运行之后，您知道最后一个元素要么被交换，要么在正确的位置。因此，您可以稍后在其他迭代中忽略它。因此，列表是从尾部排序的。
此外，某些实现使用布尔标志而不是计数器。当节点违反其顺序时设置此标志，只要存在交换，算法就会起作用。请注意，计算列表中的所有节点是 O(n(。
为方便起见，您可以为节点结构创建交换函数。
void swap(thenode *lhs, thenode *rhs)
{
swap(lhs->distancetotheorigin, rhs->distancetotheorigin);
swap(lhs->nameofobstacle, rhs->nameofobstacle);
swap(lhs->x, rhs->x);
swap(lhs->y, rhs->y);
}
Ckeckout 这篇文章对链表中的气泡排序进行了更多解释。
没有冒犯，我想说你应该养成一个习惯，有一个一致的表达代码风格。请查看有关此问题C++指南。