C链表排序问题

Question

我正试图使用冒泡排序来排序链表。我也不能交换节点内的值。我一直在画画，试图弄清楚如何在没有帮助的情况下自己做到这一点，但我开始头疼，不明白为什么这不起作用。

void sort_ascending(struct node ** head){
  int x;
  struct node*temp;
  struct node*temp2;
  x = length(*head)+1;    //checks if more than one node is in the list
  if(x < 2){
    printf("1 or lessn");
    //free(temp);
    return;
  }
  printf("longer than 1n");
  printf("%d %dn", (*head)->val, (*head)->next->val);
  if((*head)->val > (*head)->next->val){
    printf("needs to sort!n");
    temp = (*head)->next->next; //sets temp to the node after the two nodes being swapped
    printf("test1n");
    temp2 = (*head); //sets temp2 to the node1
    printf("test2n");
    *head = (*head)->next; //changes head to point at node2 instead of node1
    printf("test3n");
    (*head)->next = temp2; //sets node2 to point to node1
    (*head)->next->next = temp; //sets node2 to point back into the list
    printf("test4n");
    //free(temp);
  }
}

现在我正在尝试对两个节点进行排序。在我可以让它工作之后，我会让它进入一个循环。由于某些原因，它甚至没有对前两个元素进行排序。

这里是我的一些其他函数，以帮助理解:

结构定义:

struct node {
int val;
struct node *next;

};

其他功能:

void push(struct node ** headRef, int data){
struct node* newNode =  malloc(sizeof(struct node)); //alocates space on heap
printf("pushed noden");
newNode->val = data;//sets data value
printf("%dn", newNode->val);
newNode->next = *headRef; // The '*' to dereferences back to the real head
*headRef = newNode; // ditto

};

void print(struct node * head, int length){
int x = 0;
printf("tried to printn");
//struct node*temp = head;
//while(head->next != NULL){
while (x < length + 1){
    printf("ran loopn");
    printf("%dn", head->val);
    printf("got numbern");
    head = head->next;
    x++;
}
printf("done with loopn");

}

int main(){
char ans;
int num;
struct node *head = NULL;
do {
    do {
        printf("Enter a number: ");
        scanf("%d", &num);
        push(&head, num);//Can change to append for back
        printf("Do you want another num (y or n): ");
        scanf("%1s", &ans);
    } while (ans == 'y');
    printf("Sort ascending or descending (a or d)? ");
    scanf("%1s", &ans);
    if(ans == 'a') sort_ascending(&head);
    //else if(ans == 'd') sort_descending(&head);
    print(head, length(head));
    printf("Do you want to do this again (y or n)? ");
    scanf("%1s", &ans);
    if (ans == 'y') clear(&head);
} while (ans == 'y');

return 0;

}

int length(struct node* head){
int length = 0;
//struct node*temp = head;
printf("tried to find lengthn");
while (head->next != NULL){
    length++;
    head = head->next;
}
printf("%dn", length + 1);
return length;

}

Answer 1

我们来总结一下。

函数长度差1

int length(struct node* head){
    int length = 0;
    while (head != NULL){
        ++length;
        head = head->next;
    }
    return length;
}

函数print打印太多。

void print(struct node * head, int length){
    int x;
    for(x = 0; x < length; ++x){
        printf("%dn", head->val);
        head = head->next;
    }
}

你的扫描正在破坏内存。Scanf with"%1"需要一个指向至少两个字符的指针，一个用于存储，后面是空字节。因此，您需要提供两个字符(char ans[2];)，或者更好的解决方案是，仅将一个字符作为字符读取。

char ans;
scanf("%c", &ans);

同样，如前所述，如果你在用c语言编程，不要强制转换malloc的返回值。

如果你想知道为什么我将后缀++(如x++)更改为前缀++(如++x):我是一名c++程序员，对于c++，出于性能原因(与int或指针无关，但对于复杂类型如迭代器)，建议首选前缀++而不是后缀++。