c - 制作自动排序插入功能

Question

#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

ListNode *temp;

int get_length(ListNode *nodetype) {
    int i;
    for (i = 0; nodetype != NULL; i++) {
        nodetype = nodetype->link;
    }
    return i;
}

void add(ListNode *listtype, element elementtype){
    listtype = (ListNode *)malloc(sizeof(ListNode));
    listtype->data= elementtype;
    listtype = listtype->link;
}


void display(ListNode *nodetype) {
    for (int i=0; nodetype != NULL; i++) {
        printf("%d ", nodetype->data);
        nodetype = nodetype->link;
    }
}

int main() {
    ListNode *list1=NULL;

    add(list1, 3);
    add(list1, 3);

    printf("%d\n", get_length(list1));
    display(list1);
}

当我有三个因素(ListNode **phead、ListNode *p、ListNode *new_node)时，程序没有出现任何错误。但我必须仅使用“列表”因素和“项目”因素来遵守原始要求。因为“get_length”函数和“display”函数在以前的代码中运行良好，所以我认为“add”函数似乎有错误。 我必须使排序插入功能“添加”来解决问题。

Answer 1

注意:

我还没有测试过这段代码，而且我已经很长时间没有用 C 编写代码了。

描述

首先，让我们修复您的添加函数。

它应该检查您的列表是否为空，如果是则添加一个新节点。如果列表不为空，那么它应该遍历它直到找到最后一个节点，创建一个新节点并将其附加到其末尾。

void add(ListNode *listNode, element data){

    // The list is non-existent! Create it.
    if (listNode == null){
        // Create new node
        ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
        newNode->data = data;
        newNode->link = null;
        listNode = newNode;
        return;
    }

    // We always want to ensure that the pointer to the first element
    // of your list doesn't get override. 
    // Therefore, we create a new pointer which hold that address. 
    ListNode *currentNode = listNode;

    // Traverse the linked list until finding last element.
    while(currentNode->link != null){
        currentNode = currentNode->Link; 
    }

    // Create new node
    ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = null;

    // Attach new node to linked list
    currentNode->link = newNode;
}

现在我们修复了您的 add 方法，我们可以为您的 insert 方法创建逻辑，该逻辑与您的 add 方法类似，但具有有序逻辑。

差不多，如果列表不存在，我们就创建它。我们遍历列表，直到到达列表末尾或包含我们正在搜索的数据的元素。如果找到数据，则将该节点设置为临时节点(这样我们就不会丢失它)，将新节点的链接指向临时节点，并将当前节点的链接指向新节点。如果我们到达列表的末尾并且没有找到数据，那么我们将新节点添加到列表的末尾。

void insert(ListNode *listNode, element data){

    // The list is non-existent! Create it.
    if (listNode == null){
        // Create new node
        ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
        newNode->data = data;
        newNode->link = null;
        listNode = newNode;
        return;
    }

    // We always want to ensure that the pointer to the first element
    // of your list doesn't get override. 
    // Therefore, we create a new pointer which hold that address. 
    ListNode *currentNode = listNode;

    // Traverse the linked list until finding last element.
    // Play here with >=, >, =<, <, or any other order combination.
    while(currentNode->link != null
          && currentNode->data < data){
        currentNode = currentNode->link; 
    }

    // Create new node
    ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = null;

    // insert in the correct position
    if (currentNode->link != null){
        ListNode* tempNode = currentNode->link;
        currentNode->link = tempNode;
        currentNode->link = newNode;
        return;
    }

    // Attach new node to linked list
    currentNode->link = newNode;
}