2

将近 3 年之后，我开始重新学习C.

我创建了一个Linked list, 并希望将其扩展为创建一个排序的链表。这是我的代码：

typedef struct node{
int data;
struct node *ptr;
}node;

node* insert(node* head, int num){
node *temp,*prev,*next;
temp = (node*)malloc(sizeof(node));
temp->data = num;
temp->ptr = '\0';
if(head=='\0'){
    head=temp;
}else{
    next = head;
    prev = next;
    while(next->data<=num){
        prev = next;
        next = next->ptr;
    }
    if(next==NULL){
        prev->ptr = temp;
    }else{
        temp->ptr = prev->ptr;
        prev-> ptr = temp;
    }

}
return head;
}

void main(){
int num;
node *head, *p;
head = '\0';
do{
    printf("Enter a number");
    scanf("%d",&num);
    if(num!=0)
        head = insert(head,num);
}while(num!=0);
p = head;
printf("\nThe numbers are:\n");
while(p!='\0'){
    printf("%d ",p->data);
    p = p->ptr;
}
}

这是我的想法。我遍历列表，直到找到>=输入的数字。我将前一个节点存储在其中prev，next节点包含当前值。如果 next 是null，则列表结束并且列表中的数字是最高的，因此将其插入到最后一个位置，如果数字在中间的某个位置，则上一个节点的地址部分存储在临时节点地址中现在部分临时节点指针保存下一个节点的地址。

编辑：我的代码的问题是，如果我输入 1,2，我会收到错误消息a.exe has stopped working。我正在使用 MinGW 进行编译。当用户输入 0 时，我正在打破循环。

4

1 回答 1

5

你必须换行

while(next->data<=num)

至

while(next!='\0' && next->data<=num)

当您插入第二个元素时，next将'\0'在第二次迭代中尝试获取该字段data将next->data导致分段错误。

随着 while 条件的改变 ifnext!='\0'将是假next=='\0'的（因此 ） while 被中止并且因为&&'s 的短路next->data不会被计算。

编辑

您的代码中有更多问题。

如果您查看输入，2 1 0那么具有正确工作程序的输出应该是1 2，但它是2 1相反的。问题在于，在您的insert函数中，您没有考虑插入当前最小元素将成为新头部的情况。

另一个问题是你最后没有释放malloced 内存，这会导致内存泄漏。

我更改了您的代码以使其行为正确：

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

typedef struct node{
    int data;
    struct node *ptr;
} node;

node* insert(node* head, int num) {
    node *temp, *prev, *next;
    temp = (node*)malloc(sizeof(node));
    temp->data = num;
    temp->ptr = NULL;
    if(!head){
        head=temp;
    } else{
        prev = NULL;
        next = head;
        while(next && next->data<=num){
            prev = next;
            next = next->ptr;
        }
        if(!next){
            prev->ptr = temp;
        } else{
            if(prev) {
                temp->ptr = prev->ptr;
                prev-> ptr = temp;
            } else {
                temp->ptr = head;
                head = temp;
            }            
        }   
    }
    return head;
}

void free_list(node *head) {
    node *prev = head;
    node *cur = head;
    while(cur) {
        prev = cur;
        cur = prev->ptr;
        free(prev);
    }       
}

int main(){
    int num;
    node *head, *p;
    head = NULL;
    do {
        printf("Enter a number");
        scanf("%d",&num);
        if(num) {
            head = insert(head, num);
        }
    } while(num);
    p = head;
    printf("\nThe numbers are:\n");
    while(p) {
        printf("%d ", p->data);
        p = p->ptr;
    }
    free_list(head);
    return 0;
}

请参阅https://ideone.com/wT5iQ8，了解我在测试输入上的代码以及正确的输出。

于 2013-04-16T18:10:02.453 回答