c++ - 在 C++ 中使用链表对距原点、x 和 y 坐标的距离进行排序

Question

我遇到了一些与在 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;
}

Answer 1

我没有扫描整个代码，但我可以提出几点。

我想到的问题是，为什么您在 auf2_euclidcalc 函数中创建了一个新节点，但后来不使用它会产生内存泄漏。

关于您的排序算法。在第二个循环中，你一遍又一遍地遍历整个列表，但在运行之后你知道最后一个元素要么被交换了，要么在正确的位置。因此您可以稍后在其他迭代中忽略它。因此列表是从尾部开始排序的。

此外，一些实现使用 bool 标志而不是计数器。当节点违反它们的顺序时设置此标志，并且只要存在交换，算法就会工作。请注意，计算列表中的所有节点是 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);
}

结账 this article有关链表中冒泡排序的更多解释。

无意冒犯我想说的是，您应该养成拥有一致的表达代码风格的习惯。请查看有关此问题的 C++ 指南。