insertionsort.c

insertion排序

/* Jason Boxall 1/24/97 CSC 131 Lab #13 */
/* this program uses the insert sort algorithm to sort a linear linked list */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct studentInfo


    {
    char fname[10];
    char lname[15];
    int age;
    float gpa;
    struct studentInfo *next;
} RECORD;
RECORD *create(RECORD *, FILE *);
RECORD *insertsort(RECORD *);
void display(RECORD *, FILE *);
void main()


    {
    FILE *fin, *fout;
    fout=fopen("Lab13out.rst","w");
    RECORD *head;
    head=NULL;
    head=create(head, fin);
    display(head, fout);
    head=insertsort(head);
    display(head, fout);
}
RECORD *create(RECORD *head, FILE *fin)


    {
    fin=fopen("Lab13inp.dat","r");
    RECORD *process;


        while(!feof(fin)){


            if(head==NULL){
            head=(RECORD *)malloc(sizeof(RECORD));
            head->next=NULL;
        }


            else{
            process=(RECORD *)malloc(sizeof(RECORD));
            process->next=head;
            head=process;
        }
        fscanf(fin,"%s%s%d%f",head->fname,
        head->lname,
        &head->age,
        &head->gpa);
    }
    return head;
}
void display(RECORD *head, FILE *fout)


    {
    if(head==NULL)
    fprintf(fout,"The file is empty.\n\n");


        else{
        fprintf(fout,"\nThe file is:\n\n");
        fprintf(fout,"First Last \n");
        fprintf(fout,"Name NameAgeQPR\n");
        fprintf(fout,"-------------------------------------\n\n");


            while(head!=NULL){
            fprintf(fout,"%-10s%-15s%3d\t%5.2f\n",head->fname,
            head->lname,
            head->age,
            head->gpa);
            head=head->next;
        }
    }
}
RECORD *insertsort(RECORD *head)


    {
    RECORD *p, *q, *r, *tail=head;
    if(head)
    while(tail->next)


        {
        q=tail->next;
        if(strcmp(q->lname,head->lname)<0)


            {
            tail->next=q->next;
            q->next=head;
            head=q;
        }
        else


            {
            r=head;
            p=head->next;
            while(strcmp(q->lname,p->lname)>0)


                {
                r=p;
                p=p->next;
            }
            if(q==p)
            tail=q;
            else


                {
                tail->next=q->next;
                q->next=p;
                r->next=q;
            }
        }
    }
    return head;
}