c - 链表-基本插入函数

Question

我编写了一个程序，它获取一些值并将其放入排序的链表中。 问题是输入第一个值后 程序停止 而且它甚至不运行插入功能

我知道问题在于将参​​数传递给插入函数 但我不知道如何修复它。

    #include <stdio.h>
#include <stdlib.h>
struct record{
    int data;
    struct record *nextptr;
};
void insert (struct record *ptr,int value);
void printList(struct record *ptr);

int main() {
    struct record *headptr = NULL;
    for (int i = 0; i < 4; ++i) {
        int data;
        printf("Enter your value");
        scanf("%d", &data);
        insert(headptr, data);
    }
    printList(headptr);


    return 0;
}
void insert (struct record *ptr,int value){
    printf("WE ARE IN THE INSERT FUNCTION");
    struct record *newptr = (struct record *) malloc(sizeof(struct record));
    newptr->data=value;
    newptr->nextptr=NULL;
    struct record *curptr;
    curptr=ptr;

    while(value >= (curptr->data)){
        curptr=curptr->nextptr;
    }
    if (curptr==NULL){
        ptr=newptr;
    }
    else{
        newptr->nextptr=curptr;
    }

}
void printList(struct record *ptr){
    while((*ptr).nextptr != NULL){
        printf("%d", ptr->data);
        ptr=ptr->nextptr;
    }
}

结果:

/Users/Danial/CLionProjects/Example/cmake-build-debug/Example 输入您的值3

进程结束，退出代码为 11

Answer 1

insert 有两个大问题。首先，将 ptr 作为指针传递给 struct record。发生这种情况时，您的insert 函数会收到一个指针的副本，它指向内存中的同一位置，但它本身具有不同的地址，与从 main() 传递的指针。这意味着无论您在 insert 中对指针的副本做什么，这些更改将永远不会在 main() 中看到，因为您正在对副本进行操作而不是以其他方式返回值。要解决该问题，请使您的参数 struct record ** 并从 main() 传递指针的地址。

您在 insert 中遇到的下一个最大问题是您无法检查 curptr 是否为 NULL(因为它将在第一次调用时在开始取消引用 curptr 之前插入 insert)——可能会导致段错误或其他未定义行为。

创建链表时，您必须处理两个不同的测试条件:

1. 我是在插入第一个节点吗？ (如果是这样，只需分配`*ptr = newptr)；和
2. 所有其他插入都需要您根据 data 的 value 进行迭代，以找到合适的 2 节点来插入您的数据。

您可以简单地处理这两种情况:

    rec_t *curptr = *ptr,
        *newptr = malloc (sizeof *newptr);
    if (!newptr) {
        perror ("malloc-newptr");
        return;
    }

    newptr->data = value;
    newptr->nextptr = NULL;

    if (curptr == NULL) {       /* handle new-list case and return */
        *ptr = newptr;
        return;
    }

    if (value < curptr->data) {     /* handle new 1st node */
        newptr->nextptr = curptr;
        *ptr = newptr;
        return;
    }

    /* iterate with curptr until value > curptr->nextptr->data */
    while (curptr->nextptr != NULL && value > curptr->nextptr->data)
        curptr = curptr->nextptr;

    newptr->nextptr = curptr->nextptr;      /* wire new node to next node */
    curptr->nextptr = newptr;               /* wire current to new node */

在您编写的任何分配内存的程序中，您必须保留一个指向每个分配 block 开始的指针，以便在不再需要该内存时可以释放它。您通常会希望编写一个 listfree 函数来为您处理该问题。您可以编写如下简单的内容:

void freelist (rec_t *head)
{
    while (head) {
        rec_t *victim = head;
        head = head->nextptr;
        free (victim);
    }
}

(注意在列表前进到下一个节点之前，要释放的节点如何保存在临时指针 victim 中)。

总而言之，您可以执行以下操作:

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

typedef struct record {
    int data;
    struct record *nextptr;
} rec_t;

void insert (rec_t **ptr, int value);
void printList (rec_t *ptr);
void freelist (rec_t *head);

int main (void) {
    rec_t *headptr = NULL;

    for (int i = 0; i < 4; ++i) {
        int data;
        printf("Enter your value: ");
        scanf("%d", &data);
        insert (&headptr, data);
    }
    printList(headptr);
    freelist (headptr);

    return 0;
}

void insert (rec_t **ptr, int value) 
{
    if ( ptr == NULL ) {
        return;  
    } 

    rec_t *curptr = *ptr,
        *newptr = malloc (sizeof *newptr);  /* don't cast the return */
    if (!newptr) {
        perror ("malloc-newptr");
        return;
    }

    newptr->data = value;
    newptr->nextptr = NULL;

    if (curptr == NULL) {       /* handle new-list case and return */
        *ptr = newptr;
        return;
    }

    if (value < curptr->data) {     /* handle new 1st node */
        newptr->nextptr = curptr;
        *ptr = newptr;
        return;
    }

    /* iterate with curptr until value > curptr->nextptr->data */
    while (curptr->nextptr != NULL && value > curptr->nextptr->data)
        curptr = curptr->nextptr;

    newptr->nextptr = curptr->nextptr;      /* wire new node to next node */
    curptr->nextptr = newptr;               /* wire current to new node */
}

void printList(struct record *ptr)
{
    while (ptr != NULL) {
        printf(" %d", ptr->data);
        ptr = ptr->nextptr;
    }
    putchar ('\n');
}

void freelist (rec_t *head)
{
    while (head) {
        rec_t *victim = head;
        head = head->nextptr;
        free (victim);
    }
}

示例使用/输出

$ ./bin/lltcmpl
Enter your value: 1
Enter your value: 8
Enter your value: 5
Enter your value: 7
 1 5 7 8

$ ./bin/lltcmpl
Enter your value: 2
Enter your value: 1
Enter your value: 4
Enter your value: 3
 1 2 3 4

检查一下，如果您有任何问题，请告诉我。