c - FILE 读取链表并排序

Question

看来我的FILE读取功能有点不对劲。当我调用打印函数时，它不是打印每个条目的所有数据(名字:姓氏:优先级:阅读级别:)，而是在两个条目后停止，并且只有最后三个条目需要打印的内容的框架。因此，当我根据每个 struct 链接列表中的优先级调用排序函数时，我无法判断它是否正确打印。

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#define NAME 25
#define TITLE 50

typedef struct Book{
    int bookID;
    char* title;
    bool checkedOut;
    struct Book* next;
}book;


typedef struct Student{
    char* firstName;
    char* lastName;
    int priority;
    int readingLevel;
    book* backPack;
    bookids* wishlist;
    struct Student* next;
}student;

student* buildStudentList(char* studentFile, student* head)
{
    FILE *cfptr=fopen(studentFile, "r");
    if(cfptr==NULL){
        printf("\nFIle could not be opened\n");
        return 0;
    }
    if(head==NULL){
        head=malloc(sizeof(student));
        head->next=NULL;
        head->firstName=malloc(sizeof(student)*35);
        head->lastName=malloc(sizeof(student)*35);
        fscanf(cfptr,"%s %s %d %d", head->firstName,head->lastName, 
                &head->priority, &head->readingLevel);
    }
    student* current=head;
    while(current->next!=NULL){
        current=current->next;
    }
    current->next=malloc(sizeof(student));
    current=current->next;
    current->firstName=malloc(sizeof(student)*35);
    current->lastName=malloc(sizeof(student)*35);
    while( fscanf(cfptr, "%s %s %d %d", current->firstName, current->lastName, 
            &current->priority, &current->readingLevel)!=EOF){
        student* current=head;
        while(current->next!=NULL){
            current=current->next;
        }
        current->next=malloc(sizeof(student));
        current=current->next;
        current->firstName=malloc(sizeof(student)*35);
        current->lastName=malloc(sizeof(student)*35);
    }
    return head;
}


void createPriorityQueue(student* head)
{
    if(head==NULL ||head->next==NULL){
        return;
    }
    student* curr; student* largest; student* largestPrev; student* prev;
    curr=head;
    largest=head;
    prev=head;
    largestPrev=head;
    while(curr!=NULL){
        if(&curr->priority>&largest->priority){
            largestPrev=prev;
            largest=curr;
        }
        prev=curr;
        curr=curr->next;
    }
    student* tmp;
    if(largest!=head)
    {
        largestPrev->next=head;
        tmp=head->next;
        head->next=tmp;
    }
}

Answer 1

存在一些错误。

用于分配字符串的 malloc 应该是 malloc(35) 而不是 malloc(sizeof(student) * 35) 。它不会崩溃，但很浪费。

你的构建函数太复杂并且有几个错误——我不得不重新编码。

您的优先级队列函数正在比较优先级的地址，而不是值[我们想要的]。

无论如何，这是您的代码，其中包含一些错误注释和重新编码的创建函数[请原谅无偿的样式清理]:

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

#define NAME 25
#define TITLE 50

typedef struct Book {
    int bookID;
    char *title;
    bool checkedOut;
    struct Book *next;
} book;

typedef struct Student {
    char *firstName;
    char *lastName;
    int priority;
    int readingLevel;
    book *backPack;
    bookids *wishlist;
    struct Student *next;
} student;

// NOTE/BUG: this function is way to complicated -- see below for a simpler one
student *
buildStudentList(char *studentFile, student * head)
{
    FILE *cfptr = fopen(studentFile, "r");

    if (cfptr == NULL) {
        printf("\nFIle could not be opened\n");
        return 0;
    }

    if (head == NULL) {
        head = malloc(sizeof(student));
        head->next = NULL;

// NOTE/BUG: we want just enough to store strings -- this is true for all the
// other mallocs that allocate names
#if 0
        head->firstName = malloc(sizeof(student) * 35);
        head->lastName = malloc(sizeof(student) * 35);
#else
        head->firstName = malloc(35);
        head->lastName = malloc(35);
#endif

        fscanf(cfptr, "%s %s %d %d",
            head->firstName, head->lastName, &head->priority,
            &head->readingLevel);
    }

    student *current = head;

    while (current->next != NULL) {
        current = current->next;
    }
    current->next = malloc(sizeof(student));
    current = current->next;
    current->firstName = malloc(sizeof(student) * 35);
    current->lastName = malloc(sizeof(student) * 35);

    while (fscanf(cfptr, "%s %s %d %d",
        current->firstName, current->lastName, &current->priority,
        &current->readingLevel) != EOF) {
        student *current = head;

        while (current->next != NULL) {
            current = current->next;
        }
        current->next = malloc(sizeof(student));
        current = current->next;
        current->firstName = malloc(sizeof(student) * 35);
        current->lastName = malloc(sizeof(student) * 35);
    }

    // NOTE/BUG: close input file
#if 1
    fclose(cfptr);
#endif

    return head;
}

// simplified version
student *
buildStudentList(char *studentFile, student * head)
{
    FILE *cfptr = fopen(studentFile, "r");
    student *current;
    student *tail;
    char firstName[5000];
    char lastName[5000];

    if (cfptr == NULL) {
        printf("\nFIle could not be opened\n");
        return 0;
    }

    // find last element in list
    tail = NULL;
    for (current = head;  current != NULL;  current = current->next)
        tail = current;

    while (1) {
        // allocate new node
        current = malloc(sizeof(student));

        // initialize the next pointer (in a singly linked list, this is nulled)
        current->next = NULL;

        // get data for new node
        if (fscanf(cfptr, "%s %s %d %d",
            firstName, lastName, &current->priority,
            &current->readingLevel) == EOF) {
            free(current);
            break;
        }

        // allocate space for strings
        current->firstName = strdup(firstName);
        current->lastName = strdup(lastName);

        // add to empty list
        if (head == NULL)
            head = current;

        // add to tail of list
        else
            tail->next = current;

        // set this as new tail of list
        tail = current;
    }

    fclose(cfptr);

    return head;
}

void
createPriorityQueue(student * head)
{
    if (head == NULL || head->next == NULL) {
        return;
    }
    student *curr;
    student *largest;
    student *largestPrev;
    student *prev;

    curr = head;
    largest = head;
    prev = head;
    largestPrev = head;
    while (curr != NULL) {
// NOTE/BUG: this compares _addresses_ but we want to compare values
#if 0
        if (&curr->priority > &largest->priority) {
#else
        if (curr->priority > largest->priority) {
#endif
            largestPrev = prev;
            largest = curr;
        }
        prev = curr;
        curr = curr->next;
    }
    student *tmp;

    if (largest != head) {
        largestPrev->next = head;
        tmp = head->next;
        head->next = tmp;
    }
}

<小时/>

更新:

how do I make the createpriority function sort in the opposite order, its form highest to lowest, i need lowest to highest?

不确定您现在想要哪个订单或您已经进行了哪些更改。在您的原始代码中，您仅对列表执行单次传递，而不是与元素数量一样多的传递。

我已经修复了原始代码，使用简单的插入/选择来执行正确的传递次数。这很慢。您可以通过对链接列表进行合并排序来加快速度，但这会更加复杂。

无论如何，这是代码。我没有测试它，甚至没有编译它，但它应该会让你更接近:

student *
createPriorityQueue(student *head)
{
    student *curr;
    student *bestCurr;
    student *bestPrev;
    student *prev;
    student *tail;
    student *rtn;

    // initialize sorted list
    rtn = NULL;
    tail = NULL;

    // process all elements of unsorted list
    while (head != NULL) {
        // assume head of unsorted list is best priority in unsorted list
        bestCurr = head;
        bestPrev = NULL;

        // find best in unsorted list
        prev = NULL;
        for (curr = head;  curr != NULL;  curr = curr->next) {
#ifdef SORT_LOW_TO_HIGH
            if (curr->priority < bestCurr->priority) {
                bestCurr = curr;
                bestPrev = prev;
            }
#else
            if (curr->priority > bestCurr->priority) {
                bestCurr = curr;
                bestPrev = prev;
            }
#endif
            prev = curr;
        }

        // remove element from unordered list
        if (bestPrev != NULL)
            bestPrev->next = bestCurr->next;
        else
            head = bestCurr->next;

        // add the next best priority to the end of the ordered list
        if (tail != NULL)
            tail->next = bestCurr;
        else
            rtn = bestCurr;

        // set new tail of ordered list
        tail = bestCurr;
        tail->next = NULL;
    }

    return rtn;
}