C鏈接列表氣泡排序邏輯錯誤

Question

下面我有一個簡單的鏈接列表程序，它包含一個點和距離原點的距離。我的問題是，當調用排序函數時，它不能正確排序。我花了一段時間用gdb進行調試，但沒有運氣。我對C相對比較陌生，並且處理指針，所以如果有人能幫助我，我會非常感激！

我要發佈輸出的圖像，但我沒有足夠的聲譽看來，這樣的輸出看起來像下面是什麼：

點：（3,1） - 距離：3.16228

點：（4,1） - 距離：4.12311

點：（1,1） - 距離：1.41421

點：（7,1） - 距離：7.07107

測試。 c文件：

#include <stdlib.h> 
#include <stdio.h> 
#include "point.h" 

typedef struct node 
{ 
    Point p; 
    double distance; 
    struct node *next; 
} node; 

void insertAtFront(node **start, Point *ip); 
void sort(node *start); 
void swap(node *a, node *b); 
void printList(node *start); 

int main(int argc, char **argv) 
{ 
    Point *insertPoint = malloc(sizeof(Point)); 
    node *head = NULL; 

    point_set(insertPoint,7.0,1.0); 
    insertAtFront(&head,insertPoint); 

    point_set(insertPoint,1.0,1.0); 
    insertAtFront(&head,insertPoint); 

    point_set(insertPoint,4.0,1.0); 
    insertAtFront(&head,insertPoint); 

    point_set(insertPoint,3.0,1.0); 
    insertAtFront(&head,insertPoint); 

    sort(head); 

    printList(head); 
} 

void insertAtFront(node **start, Point *ip) 
{ 
    node *node1 = (node*)malloc(sizeof(node)); 
    node1->p = *ip; 
    node1->next = *start; 
    *start = node1; 
} 

void sort(node *start) 
{ 
    Point *tp1 = malloc(sizeof(Point)); 
    Point *tp2 = malloc(sizeof(Point)); 
    int swapped; 
    node *node1; 
    node *node2 = NULL; 
    node *tempNode; 
    double d1; 
    double d2; 
    if(start == NULL) 
     return; 
    do 
    { 
     swapped = 0; 
     node1 = start; 
     *tp1 = node1->p;   
     tempNode = node1->next;  
     *tp2 = tempNode->p;  
     d1 = distanceFromOrigin(tp1); 
     d2 = distanceFromOrigin(tp2); 
     while(node1->next != node2) 
     { 
      if(d1 > d2) 
      { 
       swap(node1,node1->next); 
       swapped = 1; 
      } 
      node1 = node1->next; 
     } 
     node2 = node1; 
    } 
    while(swapped); 
} 

void swap(node *a, node *b) 
{ 
    Point *tp; 
    *tp = a->p; 
    a->p = b->p; 
    b->p = *tp; 
} 

void printList(node *start) 
{ 
    node *temp = start; 
    Point *tp = malloc(sizeof(Point)); 
    printf("\n"); 
    while(temp != NULL) 
    { 
     *tp = temp->p; 
     printf("Point: (%g,%g) - Distance: %g\n", point_getX(tp), point_getY(tp), distanceFromOrigin(tp)); 
     temp = temp->next; 
    } 
} 

point.c文件：

#include <stdio.h> 
#include "point.h" 
#include <math.h> 

void point_translate(Point *p, double x, double y) 
{ 
    point_set(p,(point_getX(p)+x),(point_getY(p)+y)); 
} 

double point_distance(const Point *p1, const Point *p2) 
{ 
    double temp1 = (point_getX(p1) - point_getX(p2)); 
    double temp2 = (point_getY(p1) - point_getY(p2)); 
    double temp3 = (temp1*temp1)+(temp2*temp2); 
    double dist = sqrt(temp3); 
    return dist; 
} 

double distanceFromOrigin(const Point *p1) 
{ 
    double x = point_getX(p1); 
    double y = point_getY(p1); 
    double temp = (x*x)+(y*y); 
    double dist = sqrt(temp); 
    return dist; 
} 

point.h文件：

#ifndef _POINT_H_ 
#define _POINT_H_ 

typedef struct Point 
{ 
    double x; 
    double y; 
} Point; 

void point_translate(Point *p, double x, double y); 
double point_distance(const Point *p1, const Point *p2); 
double distanceFromOrigin(const Point *p1); 

static inline double point_getX(const Point *p) 
{ 
    return p->x; 
} 
static inline double point_getY(const Point *p) 
{ 
    return p->y; 
} 
static inline Point *point_set(Point *p, double x, double y) 
{ 
    p->x = x; 
    p->y = y; 
    return p; 
} 

#endif 

Answer 1

在你的「swap'功能的局部變量TP未初始化。你的編譯器應該警告你這個。然後你無論如何訪問它，這是未定義的行爲...

Answer 2

當與node1-> next交換node1時，需要更改指向node1的前一個節點的下一個指針，或者可以交換node1和node1-> next，保持下一個指針不變。

如果你是交換指針，這裏是什麼樣子交換前：

node0->next = node1, node1->next = node2, node2->next = node3 

和交換後：

node0->next = node2, node2->next = node1, node1->next = node3 

這隻適用於相鄰的節點。如果節點不相鄰，然後交換前：

nodea->next = node1, node1->next = nodeb 
nodec->next = node2, node2->next = noded 

交換後

nodea->next = node2, node2->next = nodeb 
nodec->next = node1, node1->next = noded