创建排序的链表 [英] 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 = '\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 ，则列表结束，并且编号是列表中的最高编号，因此要插入到最后一个位置，如果编号位于中间的某个位置，则为上一个节点地址部分存储在临时节点的地址中，现在临时节点指针保存下一个节点的地址.

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!='\0' && next->data<=num)

当您插入第二个元素时， next 将在第二次迭代中为'\ 0'，并尝试使用 next-> data 会导致分段错误.

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

在条件改变的情况下，如果 next！='\ 0'为假(因此 next =='\ 0')，则while终止并因为&& 的短路 next->数据而无法计算.

With the changed condition in the while if next!='\0' will be false (hence next=='\0') 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.

另一个问题是，您不会在最后释放释放 malloc 的内存，这会导致内存泄漏.

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

有关我在testinput上的代码以及正确的输出，请参见 https://ideone.com/wT5iQ8 .

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

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