데이터 구조 실천 - 색인 파일

본 고 는 [데이터 구조 기초 시리즈 (11): 파일] 중의 실천 프로젝트 를 대상 으로 한다.
【 항목 】 색인 파일 에 몇 명의 학생 들 의 성적 데 이 터 는 다음 과 같 습 니 다. 이 데 이 터 를 st 배열 에 저장 합 니 다.

                             
    1            20       78   90   84
    5            21       78   68   92
    8            20       86   81   86
    3            21       78   92   88
    2            20       80   83   78
    4            20       78   88   82
    7            21       56   67   75
    6            20       78   89   82

이러한 데 이 터 를 바탕 으로 프로그램 은 다음 과 같은 기능 을 실현 합 니 다. (1) st 배열 의 중 학생 기록 을 stud. dat 파일 에 메 인 파일 (2) 로 출력 메 인 파일 의 학생 기록 (3) 메 인 파일 에 대응 하 는 색인 파일 을 만 듭 니 다. 그 중에서 각 기록 은 두 필드 로 구성 되 어 있 습 니 다. 학 번 과 이 학생 이 데이터 파일 에 기록 한 변위 량 입 니 다.(예: 데이터 중학교 번호 가 2 인 학생 허 가 를 보 여 줍 니 다. 변위 량 은 5 입 니 다. 이 예 는 정 해진 파일 을 사용 하기 때문에 변위 량 에 따라 메 인 파일 에 기 록 된 상대 주 소 를 계산 할 수 있 습 니 다). 색인 파일 은 학 번 에 따라 질서 가 있 습 니 다. (4) 색인 파일 의 모든 기록 (5) 을 출력 합 니 다.사용자 가 입력 한 학 번 에 따라 색인 파일 을 이용 하여 2 분 검색 법 으로 해당 하 는 기록 번 호 를 찾 은 다음 에 메 인 파일 을 통 해 이 기록 (6) 을 출력 할 생각 이 있 습 니까? 이 항목 을 다시 확장 하 였 습 니까? 데 이 터 량, 해시 파일, 다 중 키워드 파일...
[참고 해답]

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MaxRec 100 //       
typedef struct Index        //        
{
    int no;                 //  
    long offset;            //        
} Index;
typedef struct
{
    int no;                 //  
    char name[10];          //  
    int age;                //  
    char sex[3];            //  
    int deg1,deg2,deg3;     //  1-  3  
} StudType;
void InsertSort(Index R[],int n) //          R[0..n-1]       
{
    int i,j;
    Index temp;
    for (i=1; i<n; i++)
    {
        temp=R[i];
        j=i-1;
        while (j>=0 && temp.no<R[j].no)
        {
            R[j+1]=R[j];    //      R[i].key     
            j--;
        }
        R[j+1]=temp;        // j+1   R[i]
    }
}
void CreatIdxFile()         //      
{
    FILE *mfile,*idxfile;
    Index idx[MaxRec];
    StudType st;
    int n=0,i;
    if ((mfile=fopen("stud.dat","rb"))==NULL)
    {
        printf("   :       
");
        return;
    }
    if ((idxfile=fopen("index.dat","wb"))==NULL)
    {
        printf("   :        
");
        return;
    }
    i=0;
    while ((fread(&st,sizeof(StudType),1,mfile)))
    {
        idx[i].no=st.no;
        idx[i].offset=++n;
        i++;
    }
    InsertSort(idx,n);  // idx   no   
    rewind(idxfile);
    for (i=0; i<n; i++)
        fwrite(&idx[i],sizeof(Index),1,idxfile);
    fclose(mfile);
    fclose(idxfile);
    printf("   :        
");
}
void OutputMainFile()   //         
{
    FILE *mfile;
    StudType st;
    int i=1;
    if ((mfile=fopen("stud.dat","rb"))==NULL)
    {
        printf("   :      
");
        return;
    }
    printf(" ----     ----
");
    printf("                        
");
    while ((fread(&st,sizeof(StudType),1,mfile))==1)
    {
        printf("%6d%5d%10s%6d%5s%5d%5d%5d
",i,st.no,st.name,st.age,st.sex,st.deg1,st.deg2,st.deg3);
        i++;
    }
    fclose(mfile);
}
void OutputIdxFile()    //          
{
    FILE *idxfile;
    Index irec;
    printf(" ----     ----
");
    printf("\t      
");
    if ((idxfile=fopen("index.dat","rb"))==NULL)
    {
        printf("   :       
");
        return;
    }
    while ((fread(&irec,sizeof(Index),1,idxfile))==1)
        printf("\t%5d%6ld
",irec.no,irec.offset);
    fclose(idxfile);
}
void ReadIndexFile(Index idx[MaxRec],int &n)    //         idx   
{
    int j;
    FILE *idxfile;
    if ((idxfile=fopen("index.dat","rb"))==NULL)
    {
        printf("   :        
");
        return;
    }
    fseek(idxfile,0,2);
    j=ftell(idxfile);       //j      
    rewind(idxfile);
    n=j/sizeof(Index);      //n          
    fread(idx,sizeof(Index),n,idxfile);
    fclose(idxfile);
}
int SearchNum(Index idx[],int n,int no) //   n        idx      no         
{
    int mid,low=0,high=n-1;
    while (low<=high)                   //    
    {
        mid=(low+high)/2;
        if (idx[mid].no>no)
            high=mid-1;
        else if (idx[mid].no<no)
            low=mid+1;
        else    //idx[mid].no==no
            return idx[mid].offset;
    }
    return -1;
}
void FindStudent()          //         
{
    int no;
    FILE *mfile;
    Index idx[MaxRec];
    StudType st;
    int i,n;
    if ((mfile=fopen("stud.dat","rb+"))==NULL)
    {
        printf("   :          
");
        return;
    }
    ReadIndexFile(idx,n);       //      idx
    printf("    :");
    scanf("%d",&no);
    i=SearchNum(idx,n,no);      // idx   
    if (i==-1)
        printf("   :  %d   
",no);
    else
    {
        fseek(mfile,(i-1)*sizeof(StudType),SEEK_SET); //                 
        fread(&st,sizeof(StudType),1,mfile);
        printf("%5d%10s%6d%5s%5d%5d%5d
",st.no,st.name,st.age,st.sex,st.deg1,st.deg2,st.deg3);
    }
    fclose(mfile);
}
void WriteFile(StudType st[], int n)  // st    n       stud.dat   
{
    int i;
    FILE *fp;
    if ((fp=fopen("stud.dat","wb"))==NULL)
    {
        printf("\t  :    stud.dat  
");
        return;
    }
    for (i=0; i<n; i++)
        fwrite(&st[i],1,sizeof(StudType),fp);
    fclose(fp);
    printf("   :  stud.dat    
");
}
int main()
{
    int n=8,sel;        //n       
        StudType st[]= {{1,"  ",20," ",78,90,84},
        {5,"  ",21," ",78,68,92},
        {8,"  ",20," ",86,81,86},
        {3,"  ",21," ",78,92,88},
        {2,"  ",20," ",80,83,78},
        {4,"  ",20," ",78,88,82},
        {7,"  ",21," ",56,67,75},
        {6,"  ",20," ",78,89,82}
    };
    printf("     
");
    WriteFile(st,n);        //     
    do
    {
        printf("1:      2:      3:       4:      0:  :");
        scanf("%d",&sel);
        switch(sel)
        {
        case 1:
            OutputMainFile();
            break;
        case 2:
            CreatIdxFile();
            break;
        case 3:
            OutputIdxFile();
            break;
        case 4:
            FindStudent();
            break;
        }
    }
    while (sel!=0);
    return 0;
}