I m trying to sort the node by score. I do not kno

问题:

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

struct student{
char firstname[20];
char lastname[20];
double grade;
char zipcode[10];
struct student *next;
};

void display(struct student *first)
{
while (first != NULL)
{
    printf("\nFirst name: %s", first->firstname);
    printf("\tLast name: %s", first->lastname);
    printf("\tGrade: %.2f", first->grade);
    printf("\t ZipCode: %s", first->zipcode);
    first = first->next;
}
}


/*void add_Record(struct student *first)
{
char r[20];
struct student *t;
t = first;

while (t != NULL)
{
    if (t == NULL)
    {
        first = (struct student*)malloc(sizeof(struct student));
        printf("\nEnter the first name of the student:");
        scanf("%s", first->firstname);
        printf("\nEnter the last name of the student:");
        scanf("%s", first->lastname);
        printf("\nEnter the score of the student:");
        scanf("%lf", &first->grade);
        printf("\nEnter the zipcode of the student:");
        scanf("%s", first->zipcode);
    }
}
}

void del()
{
struct student *back, *t, *k;
char r[10];
int flag = 0;
printf("\nEnter the last name of student  you want to delete:");
scanf("%s", r);
if (strcmpi(r, first->lastname) == 0)
{
    first = first->next;
    flag = 1;
}
else
{
    back = first;
    k = first->next;
    while (k != NULL)
    {
        if (strcmpi(r, k->lastname) == 0)
        {
            back->next = k->next;
            flag = 1;
            break;
        }
    }
}
if (flag == 0)
    printf("\nThe element not found!!!");
}
*/

void search(struct student *first)
{
char r[10];
int flag = 0;
printf("\nEnter the zipcode you want to search:");
scanf("%s", r);
struct student *t;
t = first;
while (t != NULL)
{
    if (strcmp(r, t->zipcode) == 0)
    {
        printf("\nFirst name: %s", t->firstname);
        printf("\tLast name: %s", t->lastname);
        printf("\tGrade: %.2f", t->grade);
        printf("\t ZipCode: %s", t->zipcode);
        flag = 1;
        break;
    }t = t->next;
}
if (flag == 0)
    printf("\nThe zipcode not in database!!");
}

void sort(struct student *first)
{
struct student *temp;
temp = NULL;
while (first != NULL)
{
    if (first-> grade > first->next->grade)
    {
        strcpy(temp->firstname, first->firstname);
        strcpy(temp->lastname, first->lastname);
        temp->grade = first->grade;
        strcpy(temp->zipcode, first->zipcode);
        strcpy(first->firstname, first->next->firstname);
        strcpy(first->lastname, first->next->lastname);
        first->grade = first->next->grade;
        strcpy(first->zipcode, first->next->zipcode);
        strcpy(first->next->firstname, temp->firstname);
        strcpy(first->next->lastname, temp->lastname);
        first->next->grade = temp->grade;
        strcpy(first->next->zipcode, temp->zipcode);
        break;
    }
}
printf("\nThe sorted record by score are: \n");
display(first);
}

int main(void)
{
struct student *first = NULL, *last = NULL;
struct student *temp;
int n;
printf("\nEnter the number of student:");
scanf("%d", &n);
int i;
for (i = 0; i < n; i++)
{
    temp = (struct student*)malloc(sizeof(struct student));
    printf("\nEnter the first name of the student:");
    scanf("%s", temp->firstname);
    printf("\nEnter the last name of the student:");
    scanf("%s", temp->lastname);
    printf("\nEnter the grade of the student:");
    scanf("%lf", &temp->grade);
    printf("\nEnter the zipcode of the student:");
    scanf("%s", temp->zipcode);
    temp->next = first;
    first = temp;
}
int o;
o = 1;
while (o != 0)
{
    printf("\nMENU\n");
    printf("\nEnter 1 for displaying database.");
    printf("\nEnter 2 for inserting an record.");
    printf("\nEnter 3 for deleting a record by lastname.");
    printf("\nEnter 4 for searching a record by zipcode.");
    printf("\nEnter 5 for sorting record by score.");
    printf("\nEnter 0 for exit!");
    printf("\nEnter the choice:");
    scanf("%d", &o);
    switch (o)
    {
    case 1:display(first); break;
        /*case 2:insertafter(*first); break;
    case 3:del(); break;*/
    case 4:search(first); break;
    case 5: sort(first); break;
    case 0:exit(0); break;
    default:printf("\nYou have entered a wrong choice!!!");
    }
}
}

The problem is that how do i sort the scores by score. My code seems right but doesn't work. I made a temp structure and tried to swap values but it doesn't work. Am i doing the loop wrong? Or all my code is wrong?

回答1:

Here are two answers to the problem

First one sorts the nodes in the node linked list by bubble sorting them, rearranging the linked list

Second one walks the linked list, copies a pointer to each one into an array and then sorts the array by using the struct grade members, the linked list remains unchanged

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

#define SWAP(T,x,y) {T *p = &(x); T *q = &(y); T z = *p; *p = *q; *q = z;}

struct student{
    char firstname[20];
    char lastname[20];
    double grade;
    char zipcode[10];
    struct student *next;
};

struct student *head=NULL;

void add(char *f, char *s, double score) {
struct student *a;
a=(struct student*)malloc(sizeof(struct student));
strcpy(a->firstname,f);
strcpy(a->lastname,s);
a->grade = score;
a->next = head;
head = a;
}
void printout(char *label) {
    struct student *node;
    printf("%s\n",label);
    for(node=head; node !=NULL; node=node->next) {
        printf("%s %s %f\n", node->firstname, node->lastname, node->grade);
    }
}

int main(int argc, char ** argv){
    int mark=8;
    struct student *walk, *prev; 
    add("Bob","Smith",10);
    add("Eric","Von Däniken",90);
    add("Morris","Minor",91);
    add("Master","Bates",9);
    add("Zoe","Bodkin",20);
    add("Mary","Pippin",30);
/* bubble sort */
printout("before");
        prev=head;
        while(mark) {
            mark=0;
        for(walk=head; 
        walk != NULL; 
        walk=walk->next) {
            if (walk->next && walk->grade > walk->next->grade) {
                /* printf("swapping %s %s\n", walk->firstname, walk->next->firstname); */
                mark=1;
                if (walk == head) {
                   struct student *v2=walk->next;
                   struct student *v3=walk->next->next;
                   SWAP(struct student *, v3->next, v2->next);
                   SWAP(struct student *, head, v3->next);
                   walk = v3;
                } else { 
                   struct student *v1=prev;
                   struct student *v2=walk;
                   struct student *v3=walk->next;
                   SWAP(struct student *, v3->next, v2->next);
                   SWAP(struct student *, v1->next, v3->next);
                   walk = v3;
                } 
            } 
            prev=walk;
        }

        }
        printout("after");
    return 0;
}

second version, uses qsort, retains linked list order

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

struct student{
    char firstname[20];
    char lastname[20];
    double grade;
    char zipcode[10];
    struct student *next;
};

struct student *head=NULL;
size_t nodecount=0;

void add(char *f, char *s, double score) {
struct student *a;
a=(struct student*)malloc(sizeof(struct student));
strcpy(a->firstname,f);
strcpy(a->lastname,s);
a->grade = score;
a->next = head;
head = a;
nodecount++;
}


static int cmpgrade(const void *p1, const void *p2) {
    struct student *g1, *g2;
    g1=*(struct student **)p1;
    g2=*(struct student **)p2;
    return g1->grade > g2->grade;
}

int main(int argc, char ** argv){
    int i;
    struct student *walk,**sa, **sap; 
    add("Bob","Smith",10);
    add("Eric","Von Däniken",90);
    add("Morris","Minor",91);
    add("Master","Bates",9);
    add("Zoe","Bodkin",20);
    add("Mary","Pippin",30);

/*copy into array of pointers*/
sa=calloc(sizeof (struct student*), nodecount);
sap=sa;
        for(walk=head; walk != NULL; walk=walk->next) {
              *sap = walk;
              sap++;
        }
        printf("before\n");
        for (i=0; i< nodecount; i++) {
            printf("%s %s %f\n", sa[i]->firstname, sa[i]->lastname, sa[i]->grade);
        }
        /* qsort */
        qsort(sa, nodecount, sizeof (struct student *), cmpgrade);

        printf("after\n");
        for (i=0; i< nodecount; i++) {
            printf("%s %s %f\n", sa[i]->firstname, sa[i]->lastname, sa[i]->grade);
        }
    return 0;
}