创建一个排序的链表 [英] Create a sorted linked list

问题描述

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

After almost 3 years, I've started relearning C.

我已经创建了一个链表，并希望将其扩展为创建一个排序的链表.这是我的代码:

I've created a Linked list, and would like to extend this to creating a sorted linked list. Here is my code:

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 = '';
if(head==''){
    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 = '';
do{
    printf("Enter a number");
    scanf("%d",&num);
    if(num!=0)
        head = insert(head,num);
}while(num!=0);
p = head;
printf("
The numbers are:
");
while(p!=''){
    printf("%d ",p->data);
    p = p->ptr;
}
}

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

This is my idea. I traverse the list till I find a number >= the input. I store the previous node in prev and next node contains the current value. If next is null, then the list is ended and the number is the highest among the list so it is to be inserted in the last place, if the number is some where in the middle then, prev node's address part is stored in temp nodes address part now temp node pointer holds address of next node.

我的代码的问题是，如果我输入 1,2，我会收到错误消息，因为 a.exe 已停止工作.我正在使用 MinGW 进行编译.当用户输入 0 时，我正在打破循环.

Problem with my code is if I enter 1,2 I get error message as a.exe has stopped working. I am using MinGW for compiling. I am breaking the loop when user inputs 0.

推荐答案

你必须换行

while(next->data<=num)

到

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

当您插入第二个元素时 next 将是 '' 在第二次迭代并尝试使用 data 获取字段 datacode>next->data 会导致分段错误.

When you insert the second element next will be '' at the second iteration and trying to get the field data with next->data will lead to a segmentation fault.

如果 next!='' 为假(因此 next=='')，while 中的条件改变了，while 将被中止并因为 && 的短路 next->data 没有被计算.

With the changed condition in the while if next!='' will be false (hence next=='') the while is aborted and because of &&'s shortcircuiting next->data is not computed.

编辑

您的代码有更多问题.

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

If you look at the input 2 1 0 then the output with a correctly working program should be 1 2 but it's 2 1 instead. Teh problem is that in your insert function you do not consider the case where you insert the current smallest element that will be the new head.

还有一个问题是你最后没有释放malloced的内存，导致内存泄漏.

Another problem is that you do not free the malloced memory at the end, which leads to memory leaks.

我更改了您的代码以使其正确运行:

I changed your code to behave correctly:

#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("
The numbers are:
");
    while(p) {
        printf("%d ", p->data);
        p = p->ptr;
    }
    free_list(head);
    return 0;
}

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

See https://ideone.com/wT5iQ8 for my code on a testinput together with the correct output.

这篇关于创建一个排序的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！