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

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.

Who can find my mistake in the code and explain it?

Here is the code:

#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);
}

CodePudding user response：

There are multiple problems:

in sortByNum, the loop for (int i = 0; i <= num; i) runs one iteration too far. You should use i < num to iterate exactly num times.
in sortByNum(), the test if (head = NULL) is incorrect. You should write:
```
  if (head == NULL) 
```

while (!feof(ptr)) is incorrect too. You should instead write:

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

you should pass the array length to fileIntoArray so it can avoid writing beyond the end of the array.
the node structures should have pointers to the studInfo entries in the array, not copies.
the node insertion code is too complicated and probably incorrect.
in list, the test while (p->link != NULL) will cause a crash if the list passed as argument is empty.
fileIntoArray and sortByNum should return a result instead of storing it to a caller variable via a pointer.

Here is a modified version:

#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, "%d1s%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;
}

CodePudding user response：

Corrected list function, see comment in the code.

Provided an implementation of Insertion Sort on the given data structure. (There is a more concise implementation available: Insertion Sort on Wikipedia.)

Please note that the code below is reduced. It just contains what is necessary to illustrate the sorting.

#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;
}

Students in the code are in inverse order, now see if the sorting works:

$ 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
$

Seems to work just fine. :-)