c - 在 C : How to construct a linked list in order based on a variable?

Question

假设我正在对多个项目进行 fread() 处理，每个项目都存储在一个结构中，并带有一个指示其顺序的整数变量。所以像这样:

struct book {
    int order;
}

而且我还构建了一个链表来包含所有阅读的书籍，这样具有最小“顺序”的书将成为头部。

链表声明如下:

struct list {
    struct book p;
    struct list *next;
}

由于我正在阅读的书是随机排列的，并且没有前导指针，我应该如何确保我能找到顺序最小的书并使它成为我的链表的头部？

这是我目前所拥有的，它只是以随机顺序添加它们:

list *lst, *temp;
struct book buff2;

lst=malloc(sizeof(struct list));

while((nread2=fread(&buff2,sizeof(buff2),1,infp))>0) {

        temp = malloc(sizeof(*temp));
        temp->p=buff2;
        lst->next=temp;
        lst=temp;
}

谢谢!

Answer 1

为了让您的列表按从小到大的顺序排列，您可以执行以下操作，但您应该记住，这不是该任务的最佳数据结构。

请注意，我既没有编译也没有测试这段代码 - 它只是一个合理的起点，供您继续前进并说明迭代器和插入的概念。

// Declare lst (head), item (new item), and a list iterator (iter).
list *lst = NULL, *item = NULL, *iter = NULL; // Initialize all to NULL.
struct book buff2;

while ((nread2 = fread(&buff2, sizeof(buff2), 1, infp)) > 0) { // Read item.
    item = malloc(sizeof(list)); // Allocate node for new item.
    item->p = buff2; // Assignment to the new node data.
    item->next = NULL; // Initialize the next to NULL.

    if (lst == NULL) lst = temp; // Add item to blank list.
    else { // List has items, find insertion point, then insert.
       // lst is always the first item (or head).  iter moves down list.
       iter = lst; 

       // Find the insertion point, taking order into consideration.
       while ((iter->next != NULL) && (iter->p.order < temp->p.order)) 
           iter = iter->next; // Move the iterator down the list.

       // We now just need to insert our new node into the list. Adjust nexts.
       item->next = iter->next; // New item takes over the insertion item next.
       iter->next = item; // Change insertion next to point to the new item.
    }
}