C 中的链表 - 在排序位置添加结构

Question

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "Book.h"


int main(int argc, char** argv) {

    Book * dummy = newBook("dummy", "dummy", 00000);

    printf("%s %s %ld", dummy->title, dummy->author, dummy->ISBN);

    dummy->next = NULL;


    Book* newishBook = newBook("Foo", "Chris", 1234);
    insertToList(newishBook, dummy);

    Book* another = newBook("Bar", "Jim", 23344);
    insertToList(another, dummy);

    Book* yet = newBook("Derp", "Bob", 999);
    insertToList(yet, dummy);

    displayList(dummy);

    searchISBN(999);

    return (EXIT_SUCCESS);
}

Book* newBook(char* newTitle, char* newAuthor, long newISBN) {
    Book* new_book = malloc(sizeof(Book));

    strcpy(new_book->title, newTitle);
    strcpy(new_book->author, newAuthor);
    new_book->ISBN = newISBN;
    return new_book;
}



void insertToList(Book* bookToInsert, Book* dummy){
    Book* currentNode = dummy;
    Book* temp = malloc(sizeof(Book));

    if (currentNode->next == NULL){
        currentNode->next = bookToInsert;
        printf("Head");
    } else {
        currentNode= currentNode->next;        
        while(currentNode->ISBN > bookToInsert->ISBN){

            if (bookToInsert ->ISBN < currentNode->ISBN){
                // if isbn of current book more than current node, move to next current node
                //otherwise add here
                printf("Added");
                temp->next = currentNode->next;
                bookToInsert->next = currentNode->next;
                currentNode->next = temp->next;
            }
        }
    }
}

void displayList(Book* dummy){
    //start at dummy node-
    Book* currentNode = dummy;
    bool run = true;

    //print until next = null
    while(run==true){
        if (currentNode->next != NULL){
            printf("%s %s %ld \n", currentNode->title, currentNode->author, currentNode->ISBN); 
            currentNode = currentNode ->next;
        } else {
            run = false;
        }
    }    
}

该程序旨在创建作为链表节点的书籍结构。一本书在头文件中定义如下Book.h:

#ifndef BOOK_H
#define BOOK_H

#ifdef  __cplusplus
extern "C" {
#endif


typedef struct book_t {
    char title[50];
    char author[30];
    long ISBN;
    struct Book *next;
} Book;

Book* newBook(char* newTitle, char* newAuthor, long newISBN);

#ifdef  __cplusplus
}
#endif

#endif  /* BOOK_H */

我觉得我的 insertToList 函数快要工作了，但是我对它的看法太错误了，所以我对代码视而不见，我确信它确实存在一些基本的错误。目前没有输出——只有一个空终端，我相信循环没有正确退出。取消注释 printf 语句 "added" 和 "head" 会导致程序无限循环，输出 "added" 到终端。

Answer 1

insertToList 函数未处理所有情况。

你首先检查列表是否为空（正确） while 循环之后缺少逻辑。你应该：

1) check if currentNode is larger (same as your if statement)
  a) if it is smaller, insert the book,
  b) if it is larger, you need another check:
      i) if currentNode has next !== NULL, move down and repeat loop
      ii) if next == NULL, add book at the end and return;

Answer 2

结构应该是：

typedef struct Book {
    char title[50];
    char author[30];
    long ISBN;
    struct Book *next;
} Book;

代码可以是：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Book.h"

Book *newBook(char *newTitle, char *newAuthor, long newISBN);
void displayList(Book *dummy);
void insertToList(Book *bookToInsert, Book *dummy);
void freeList(Book *head);

int main(void)
{
    Book *dummy = newBook("dummy", "dummy", 00000);

    printf("%s %s %ld\n", dummy->title, dummy->author, dummy->ISBN);

    printf("Newish\n");
    Book *newishBook = newBook("Foo", "Chris", 1234);
    insertToList(newishBook, dummy);
    displayList(dummy);

    printf("Another\n");
    Book *another = newBook("Bar", "Jim", 23344);
    insertToList(another, dummy);
    displayList(dummy);

    printf("Yet\n");
    Book *yet = newBook("Derp", "Bob", 999);
    insertToList(yet, dummy);
    displayList(dummy);

    //searchISBN(999);
    freeList(dummy);

    return(EXIT_SUCCESS);
}

Book *newBook(char *newTitle, char *newAuthor, long newISBN)
{
    Book *new_book = malloc(sizeof(Book));

    strcpy(new_book->title, newTitle);
    strcpy(new_book->author, newAuthor);
    new_book->ISBN = newISBN;
    new_book->next = NULL;
    return new_book;
}

void insertToList(Book *bookToInsert, Book *dummy)
{
    Book *currentNode = dummy;

    while (currentNode->next != NULL && currentNode->next->ISBN < bookToInsert->ISBN)
        currentNode = currentNode->next;
    bookToInsert->next = currentNode->next;
    currentNode->next = bookToInsert;
}

void displayList(Book *dummy)
{
    Book *currentNode = dummy;

    while (currentNode != NULL)
    {
        printf("%s %s %ld\n", currentNode->title, currentNode->author, currentNode->ISBN);
        currentNode = currentNode->next;
    }
}

void freeList(Book *head)
{
    Book *bp = head;
    while (bp != 0)
    {
        Book *bn = bp->next;
        free(bp);
        bp = bn;
    }
}

由于添加和使用了 freeList() 功能，这在 valgrind 下运行无泄漏。

注意添加每个条目后列表是如何打印的。这有助于确保正确构建列表。还要注意每行输出如何以换行符结尾。在打印换行符之前，您不一定会看到打印的数据。特别是对于调试，请确保包含换行符——但即使不调试，这通常也是一个好主意。

C 中的链表 - 在排序位置添加结构

Linked Lists in C- adding a struct in sorted position

c

linked-list

singly-linked-list