如何使用c中的结构数组创建排序链表

Question

Here is student.txt file with some information and I took them to the array and I created a sorted linked list using the array, but it is not listing any information. I could not find why it is happening! Here is the onlineGDB session.

谁能找出我代码中的错误并解释一下？

代码如下：

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

struct studInfo {
    int studNr;
    char studName[12];
    int grade;
};

struct node {
    struct studInfo info;
    struct node *link;
};

typedef struct node *NODEPTR;

NODEPTR getnode(void);
void fileIntoArray(struct studInfo allStudent[],int *num);
void sortByNum(struct studInfo allstudent[], NODEPTR *, int num);
void list(NODEPTR);

int main() {
    struct studInfo allStudent[150];
    NODEPTR headNum, headName;
    int choice;
    int num;
    
    fileIntoArray(allStudent, &num);
    sortByNum(allStudent, &headNum, num);
    list(headNum);
    
    return 0;
}

void fileIntoArray(struct studInfo allStudent[], int *num) {
    FILE *ptr = fopen("student.txt", "r");
    int i = 0;
    while (!feof(ptr)) {
        fscanf(ptr, "%d%s%d", &allStudent[i].studNr,
               allStudent[i].studName, &allStudent[i].grade);
        i++;
    }
    *num = i;
    fclose(ptr);
}

void sortByNum(struct studInfo allStudent[], NODEPTR *headNum, int num) {
    NODEPTR head, p, save, prev;
    head = NULL;
    for (int i = 0; i <= num; ++i)  {
        p = getnode();
        p->info = allStudent[i];
        if (head = NULL) {
            head = p;
            p->link = NULL;
        } else {
            if (p->info.studNr < head->info.studNr) {
                p->link = head;
                head = p;
            } else {
                save = head;
                while ((save->info.studNr < p->info.studNr) &&(save != NULL)) {
                    prev = save;
                    save = save->link;
                    if (save == NULL) {
                        prev->link = p;
                        p->link = NULL;
                    } else {
                        p->link = prev->link;
                        prev->link = p;
                    }
                }
            }
        }
    }
    *headNum = head;
}

void list(NODEPTR headNum) {
    NODEPTR p = headNum;
    int line = 0;
    while (p->link != NULL) {
        line++;
        if (line > 25) {
            printf("Tab a button\n");
            getchar();
            line = 1;
        }
        printf("%d %d  %s  %d\n", line, p->info.studNr,
               p->info.studName, p->info.grade);
        p = p->link;
    }
}

NODEPTR getnode() {
    NODEPTR q;
    q = (NODEPTR)malloc(sizeof(struct node));
    return(q);
}

Answer 1

存在多个问题：

在 sortByNum 中，循环 for (int i = 0; i <= num; ++i) 运行了一次迭代太远。您应该使用 i < num 来精确迭代 num 次。
在sortByNum()中，测试if (head = NULL)不正确。你应该写：
```
  if (head == NULL) 
```

while (!feof(ptr)) 也不正确。你应该改为写：

  while (fscanf(ptr, "%d%s%d", &allStudent[i].studNr,
         allStudent[i].studName, &allStudent[i].grade) == 3) {
      i++;
  }

您应该将数组长度传递给fileIntoArray，这样可以避免超出数组末尾的写入。
node 结构应该有指向数组中 studInfo 条目的指针，而不是副本。
节点插入代码太复杂，可能不正确。
在 list 中，如果作为参数传递的列表为空，测试 while (p->link != NULL) 将导致崩溃。
fileIntoArray 和 sortByNum 应该 return 结果而不是通过指针将其存储到调用者变量。
不建议将指针隐藏在 typedef 后面，例如 NODEPTR。使用 struct node *ptr 或可能将 node 定义为 typedef for struct node 并写入 node *ptr.

这是修改后的版本：

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

struct studInfo {
    int studNr;
    char studName[32];
    int grade;
};

struct node {
    struct studInfo *info;
    struct node *link;
};

struct node *getnode(void);
int fileIntoArray(struct studInfo allStudent[], int len);
struct node *sortByNum(struct studInfo allstudent[], int num);
struct node *sortByName(struct studInfo allstudent[], int num);
void list(const struct node *p);

int main() {
    struct studInfo allStudent[150];
    int num = fileIntoArray(allStudent, 150);
    struct node *headNum = sortByNum(allStudent, num);
    struct node *headName = sortByName(allStudent, num);

    printf("\nStudent list by ID:\n");
    list(headNum);
    printf("\nStudent list by name:\n");
    list(headName);

    return 0;
}

int fileIntoArray(struct studInfo allStudent[], int len) {
    int i = 0;
    FILE *ptr = fopen("student.txt", "r");
    if (ptr != NULL) {
        while (i < len && fscanf(ptr, "%d%31s%d",
                                 &allStudent[i].studNr,
                                 allStudent[i].studName,
                                 &allStudent[i].grade) == 3) {
            i++;
        }
        fclose(ptr);
    }
    return i;
}

struct node *sortByNum(struct studInfo allStudent[], int num) {
    struct node *head = NULL;
    for (int i = 0; i < num; ++i) {
        struct node *p = getnode();
        p->info = &allStudent[i];
        if (head == NULL || p->info->studNr < head->info->studNr) {
            p->link = head;
            head = p;
        } else {
            struct node *prev = head;
            while (prev->link && prev->link->info->studNr < p->info->studNr) {
                prev = prev->link;
            }
            p->link = prev->link;
            prev->link = p;
        }
    }
    return head;
}

struct node *sortByName(struct studInfo allStudent[], int num) {
    struct node *head = NULL;
    for (int i = 0; i < num; ++i) {
        struct node *p = getnode();
        p->info = &allStudent[i];
        if (head == NULL || strcmp(p->info->studName, head->info->studName) < 0) {
            p->link = head;
            head = p;
        } else {
            struct node *prev = head;
            while (prev->link && strcmp(prev->link->info->studName, p->info->studName) < 0) {
                prev = prev->link;
            }
            p->link = prev->link;
            prev->link = p;
        }
    }
    return head;
}

void list(const struct node *p) {
    int line = 0, c;
    while (p != NULL) {
        line++;
        if (line > 25) {
            printf("Press enter>");
            fflush(stdout);
            while ((c = getchar()) != EOF && c != '\n')
                continue;
            printf("\r            \r");
            line = 1;
        }
        printf("%d %d  %s  %d\n", line, p->info->studNr,
               p->info->studName, p->info->grade);
        p = p->link;
    }
}

struct node *getnode(void) {
    struct node *q = malloc(sizeof(*q));
    if (q == NULL) {
        perror("cannot allocate node");
        exit(1);
    }
    return q;
}

Answer 2

更正了 list 函数，请参阅代码中的注释。

提供了对给定数据结构的插入排序的实现。（有一个更简洁的实现可用：Insertion Sort on Wikipedia。）

请注意，下面的代码被简化了。它只包含说明排序所必需的内容。

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

struct studInfo {
    int studNr;
    char studName[12];
    int grade;
};

struct node {
    struct studInfo info;
    struct node *link;
};

typedef struct node *NODEPTR;

void list(NODEPTR headNum) {
    NODEPTR p = headNum;
    int line = 0;
    while (p != NULL) { // corrected from  p->link != NULL
        line++;
        if (line > 25) {
            printf("Tab a button\n");
            getchar();
            line = 1;
        }
        printf("%d %d  %s \t %d\n", line, p->info.studNr,
               p->info.studName, p->info.grade);
        p = p->link;
    }
}

// Insertion Sort
NODEPTR sort(NODEPTR root, bool sortByName) {
    if (root == NULL || root->link == NULL) {
        // All lists with less than two elements are already sorted.
        return root;
    }

    // put first element into sorted list
    NODEPTR sorted_root = root;

    // start iteration with second element
    NODEPTR iterator = root->link;

    // set end of sorted list
    sorted_root->link = NULL;

    while (iterator != NULL) {
        // trace position directly before insertion point
        NODEPTR previous = NULL;
        // iterate over already sorted list
        NODEPTR sorted_iterator = sorted_root;
        // determine insertion point in already sorted list
        while (
            // list end not reached
            sorted_iterator != NULL
            &&
            // need to advance in sorted list for proper position
            (sortByName ?
                strcmp(sorted_iterator->info.studName, iterator->info.studName) <= 0
                :
                sorted_iterator->info.studNr < iterator->info.studNr)) {
            previous = sorted_iterator;
            sorted_iterator = sorted_iterator->link;
        }
        if (previous == NULL) {
            // prepend sorted list with element
            NODEPTR tmp = sorted_root;
            sorted_root = iterator;
            iterator = iterator->link;
            sorted_root->link = tmp;
        } else if (sorted_iterator == NULL) {
            // append new last element in sorted list
            previous->link = iterator;
            NODEPTR tmp = iterator->link;
            iterator->link = NULL;
            iterator = tmp;
        } else {
            // insert element at correct position
            NODEPTR tmp = iterator->link;
            previous->link = iterator;
            iterator->link = sorted_iterator;
            iterator = tmp;                
        }
    }
    return sorted_root;
}

int main() {
    struct studInfo allStudent[3];
    allStudent[0].studNr = 303; strcpy(allStudent[0].studName,"Bella");   allStudent[0].grade = 1;
    allStudent[1].studNr = 202; strcpy(allStudent[1].studName,"Carla");   allStudent[1].grade = 2;
    allStudent[2].studNr = 101; strcpy(allStudent[2].studName,"Adeline"); allStudent[2].grade = 3;
    struct node links[3];
    links[0].info = allStudent[0]; links[0].link = &links[1];
    links[1].info = allStudent[1]; links[1].link = &links[2];
    links[2].info = allStudent[2]; links[2].link = NULL;
    NODEPTR head;
    head = &links[0];
    printf("Sort by student number\n");
    head = sort(head, false);
    list(head);
    printf("Sort by student name\n");
    head = sort(head, true);
    list(head);
    return 0;
}

代码中的同学是倒序的，现在看看排序是否有效：

$ gcc students.c
$ ./a.out       
Sort by student number
1 101  Adeline   3
2 202  Carla     2
3 303  Bella     1
Sort by student name
1 101  Adeline   3
2 303  Bella     1
3 202  Carla     2
$

似乎工作正常。 :-)

如何使用c中的结构数组创建排序链表

How to create sorted linked list using array of structure in c

c

sorting

struct

linked-list

file-sorting