二路歸并算法(2PMM)--學生管理系統

有BUG待調試 編寫目的如下 

① dump input - file-name fill-factor? data.txt 80 - data.txt 파일내에저장된(id, name, age, grade) 쌍들을입력하여여러분들의파일 (student.dat)에저장(전체쌍의수> 1,000) - student.dat: 첫번째블록(block 0)은header block이며, block 1부터레코드저장. 단, 각block에는101 * fill-factor / 100 만큼의레코드가저장 - data.txt: ASCII 파일로서각field들은하나의줄에표시 

② block status - file-name block-number? student.dat 123 - block 123에저장된레코드의수및그수만큼의레코드를예쁘게출력 - block 0일경우에는header block의rec_num과fill_factor를출력할것. 

③ sort - 2PMM을이용하여학번에대한오름차순으로정렬하여sorted.dat에저장 (Memory 크기= 1,000개의block을저장할수있다고가정) - sorted.dat에대한block status 명령으로block 내용확인가능 

④ search - 찾고자하는학번? 학번입력 → 해당학생을검색후(binary search), 이름과나이, 그리고평점출력 

⑤ exit: 종료

FILE：struct.h
 
#ifndef STRUCT_H 
#define STRUCT_H 
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct student
{
    int id;
    char name[20];
    int age;
    double grade;
};
 
struct block
{
    struct student record[101];
    char fill[44];
    int rec_num;
    long next;
    long prev;
};
 
struct header
{
    int rec_num;
    int fill_factor;
    char fill[4088];
};
 
#define SSTU sizeof(struct student)
#define SBLC sizeof(struct block)
#define SHED sizeof(struct header)
#define HEAD1 "------------Students Info------------n"
#define HEAD2 "| Student ID |  Name  | Age | Grade |n"
#define HEAD3 "|------------|--------|-----|-------|n"
#define FORMAT "|   %-6d   | %-6s | %-3d | %-1.2lf  |n"
#define END "-----------------END-----------------n"
#define SMEMORY 1000    //Memory크기 == 1000 개의 block을 저장할 수 있다
 
int getnum();
int getfactor();
void dump();
void blockstatus();
 
int comp(const void *a,const void *b);
void Mergesort(int n1, int n2, int n3);
void sort();
int binsearch(struct block *p, int num, int left, int right);
void search();
 
void read();
void menu();
 
#endif
/************************************************************************************************/
 
 
FILE：dump.c
#include "struct.h"
 
int getnum()
{
    int num;
    int z;
     
    while(1)
    {
        fflush(stdin);          //清除輸入緩沖區防止因為scanf讀入為字元後enter産生死循環
        z = scanf("%d", &num);
        if (num < 0)
        {
            printf("Must > 0nRe_enter,please!n");
            continue;
        }
        else if (num >= 0 && z == 1) 
            break;
        else if (num >= 0 && z == 0)
        {
            printf("Must be a number!!nRe_enter,please!n");
            continue;
        }
    }
    fflush(stdin);
    return num;
}
 
int getfactor()         //獲得record的%比并傳回
{
    int n;
     
    while(1)
    {
        printf("Please enter the %% of recordn");
        n = getnum();
        if(n > 0 && n <= 100)
            break;
        else if(n > 100)
        {
            printf("%Record must < 100n");
            continue;
        }
    }
    return n;
}
 
void dump()
{   
    FILE *in, *out;                     //檔案指針
    struct block *p =  NULL;            //定義指向block結構體的指針p并賦空值
    struct header *head = NULL;         //定義header結構體的元素 head;
    char filename[20];                  //需要轉換的TXT檔案名稱
    int blk;                            //定義block長度
    int x;                              //判斷用
    char key;                           //判斷用
 
    x = 1;
    while(1)
    { 
        printf("TXT파일의 이름을 입력하세요!n");
        scanf("%s", filename);
        if ( (in = fopen (filename, "r")) == NULL)      //如果無法找到TXT檔案
        {
            printf("Can't open file '%s'. Please make sure the name.n", filename);
            getchar();
            getchar();
            break;
        }
        if ( (out = fopen("student.dat", "rb+")) != NULL)   //如果學生資料檔案存在
            x = 0;
        else
        {
            printf("Try to open file 'student.dat',but can't find it!n");
            printf("파일'student.dat'새로 만들래");
            getchar();
            while(1)
            {
                printf("[Y]/[N]?");
                scanf("%c", &key);
                if (key == 'y' || key == 'Y')
                {
                    if ( (out = fopen ("student.dat", "wb+")) == NULL)  //如果無法建立
                        printf("Can't creat 'student.dat'!n");
                    else        //建立成功
                    {
                        printf("File 'student.dat' has been created!n");
                        x = 0;
                    }   
                    break;
                }
                else if (key == 'n' || key == 'N')
                {
                    printf("취소했다!n");
                    fclose(in);
                    getchar();
                    getchar();
                    break;
                }
            }
        }
        if (x == 0)     //如果檔案被成功打開
        {          
            head = (struct header*)malloc(SHED);
            head->fill_factor = getfactor();  //獲得record可使用的百分比
            head->rec_num = 0;                  //初始record為0
            x = (int)(101 * head->fill_factor / 100);   //計算可使用的record個數
            p = (struct block*)malloc(SBLC);  //申請動态記憶體空間p，大小為block結構體大小
            fseek(out,SHED,0);      //跳過結構體header檔案頭（block0），最後寫入
            blk = 0;
            while(!feof(in))
            {
                blk += 1;     //塊自增
                p->rec_num = 0;
                while(p->rec_num < x && !feof(in)) //當record小于可用數且txt檔案不為結尾時
                {   
                    //讀取txt檔案内的資料
                    if(fscanf(in, "%d %s %d %lf", &p->record[p->rec_num].id, p->record[p->rec_num].name,
                                                &p->record[p->rec_num].age, &p->record[p->rec_num].grade) == EOF)
                                                break;
                    head->rec_num += 1;         //record總數目+1
                    p->rec_num += 1;            //目前塊record數目+1
                }
                if(feof(in))p->next = 1;
                else p->next = blk + 1;
                if(blk > 1)p->prev = blk - 1;
                else p->prev = 1;
                if(!feof(in) || p->rec_num > 0)fwrite(p, SBLC, 1, out);
            }
            fseek(out, 0, 0);
            fwrite(head, SHED, 1, out);
            fseek(out, SHED + 101*SSTU + 48, 0);        //重新寫入第一個block中的連結清單指向結尾
            fwrite(&blk, 4, 1, out);
            free(p);
            free(head);
            fclose(in);
            fclose(out);
            printf("데이터 파일 만들어되었습니다.");
            getchar();
            break;
        }
    }
}
     
void blockstatus(char FILENAME[])
{
    FILE *fp;
    struct block *p = NULL;     //指向block指針p
    struct header *h = NULL;    //指向header指針h
    int blknum;                 //block-number
    int i, j;
 
    if ((fp = fopen(FILENAME, "rb")) == NULL)
    {
        printf("Can't find '%s'!", FILENAME);
        getchar();
    }
    else
    {
        printf("Please enter the block number :");
        blknum = getnum();
        printf("blknum = %dn",blknum);
         
         
        if (blknum != 0)                    //當block位置不為0
        {
            p = (struct block*)malloc(SBLC);    //申請動态空間
            fseek(fp, blknum*SBLC, 0);
            if (fread(p, SBLC, 1, fp) != 0) //當該block存在時
            {
                printf(HEAD1);
                printf(HEAD2);
                printf(HEAD3);
                j = 4;
                for(i = 0; i < p->rec_num; i++)
                {
                    printf(FORMAT, p->record[i].id, p->record[i].name, p->record[i].age, p->record[i].grade);
                    j += 1;
                    if (j == 24)
                    {
                        printf("Press enter to next page!n");
                        getchar();
                        j = 0 ;
                    }
                }
                printf(END);
                printf("이 block안에 전체record의 개수는 %d 이다.n", p->rec_num);
                getchar();
            }   
            else
            {
                printf("Out of block!n");
                getchar();
            }
            free(p);
        }
        else if (blknum == 0)               //當block位置為0
        {
            h = (struct header*)malloc(SHED);   
            fseek(fp, 0, 0);
            fread(h, SHED, 1, fp);
            printf("파일안에 저장되어 있는 record개수는 %d 이다.n", h->rec_num);
            printf("block 용량 대비는 %d 이다.n", h->fill_factor);
            free(h);
            getchar();
        }
    }
}
/************************************************************************************************/
 
 
FILE:sort.c
#include "struct.h"
 
int comp(const void *a,const void *b)
{
    struct block *aa = (struct block*)a;
    struct block *bb = (struct block*)b;
 
    if (aa[0].record->id < bb[0].record->id) return -1;
    else if (aa[0].record->id> bb[0].record->id) return  1;
    else return  0;
}
 
/*void Quicksort(struct student *p, int left, int right)    //QuickSort but i will not use it
{
    int pivot;
    int i;
    int j; 
    struct student temp;
     
    if(left < right)
    {
        i = left;
        j = right;
        pivot = p[(i + j) / 2].id;      //設定keyword為中間數的值
 
        while(i < j)
        {
            for(;(i < right)&&(p[i].id < pivot);i++); //從左往右持續尋找直到目前數小于Keyword
            for(;(j > left)&&(p[j].id > pivot);j--);  //從右往左持續尋找直到目前數大于Keyword
            if (i <= j)                      //當滿足上面條件時 左 仍然小于等于 右
               {    
                   //swap 左 右
                    temp = p[i];
                    p[i] = p[j];
                    p[j] = temp;
                    i++;
                    j--;
                }
        }
        if (i < right)       //當左邊沒有達到右邊時
            Quicksort(p, i, right);
        if (j > left)        //當右邊沒有達到左邊時
            Quicksort(p, left, j);
    }
}
*/
 
void Mergesort(int n1, int n2, int n3)  //2PMM 之 階段2 歸并排序(Merge Sort)
{
    FILE *tmp1, *tmp2;
    FILE *fp;
    struct student loser;
    struct student p1;
    struct student p2;
    char TempFile[50];
    int i, j;
 
    sprintf(TempFile, "Temp_%d", n1);
    tmp1 = fopen(TempFile,"rb");
    sprintf(TempFile, "Temp_%d", n2);
    tmp2 = fopen(TempFile,"rb");
    sprintf(TempFile, "Temp_%d", n3);
    fp = fopen(TempFile,"wb");
     
    fread(&p1, SSTU, 1, tmp1);
    fread(&p2, SSTU, 1, tmp2);
    while(!feof(tmp1) && !feof(tmp2))
    {
        if(p1.id <= p2.id)
        {
            fwrite(&p1, SSTU, 1, fp);
            if((fread(&p1, SSTU, 1, tmp1)) != 0)
                continue;
        }
        else if(p1.id > p2.id )
        {
            fwrite(&p2, SSTU, 1, fp);
            if((fread(&p2, SSTU, 1, tmp2)) != 0)
                continue;
        }
    }
    if(feof(tmp1))
    {
        while(fread(&p2, SSTU, 1, tmp2) != 0)
        {
            fwrite(&p2, SSTU, 1, fp);
        }
    }
    if(feof(tmp2))
    {
        while(fread(&p1, SSTU, 1, tmp1) != 0)
        {
            fwrite(&p1, SSTU, 1, fp);
        }
    }
    fclose(tmp1);
    fclose(tmp2);
    fclose(fp);
    sprintf(TempFile, "Temp_%d", n1);
    remove(TempFile);
    sprintf(TempFile, "Temp_%d", n2);
    remove(TempFile);
}
 
void sort()
{
    FILE *in, *out, *t;
    int cntn;
    char TempFile[50];
    struct block *p;
    struct header *h;
    struct student *temp;
    struct student st;
    int i, j, k;
 
    cntn = i = k = 0;
    in = fopen("student.dat", "rb");
    p = (struct block*)malloc(SBLC);
    fseek(in, SHED, 0);     //跳過BLOCK O将在最後寫入該位置
 
 
    //先進行2PMM第一步快速排序 因為BLOCK内的其他元素不會改變為節約記憶體僅提取出學生資料
    temp = (struct student*)malloc((SMEMORY - 3 ) * 101 * SSTU);
    while(!feof(in))
    {   
        fread(p, SBLC, 1, in);
        while ((!feof(in)) && i < (SMEMORY - 3 ) * 101)
        {
            for(j =0; j < p->rec_num && i < (SMEMORY - 3 ) * 101; i++, j++)
                temp[i] = p->record[j];
            fread(p, SBLC, 1, in);  
        }
        //Quicksort(temp, 0, i - 1);    //if use Quciksort();
        qsort(temp,i,SSTU,comp);        //if use qsort();
        sprintf(TempFile, "Temp_%d", cntn);
        t = fopen(TempFile, "wb");
        for(k = 0; k < i; k++)
            fwrite(&temp[k], SSTU, 1, t);
        cntn++;
        fclose(t);
        i = 0;
        if(j< p->rec_num)
        {
            while(j < p->rec_num)
            {
                temp[i] = p->record[j];
                i++;
                j++;
            }
        }
    }
    free(temp);
    i = 0, j = cntn;
 
    while(cntn > 1)
    {   
        Mergesort(i,i+1, j);
        i = i + 2;
        j++;
        cntn -= 1;
    }
    if(cntn <= 1)
    {
        h = (struct header*)malloc(SHED);
        sprintf(TempFile, "Temp_%d", j - 1);
        t = fopen(TempFile, "rb");
        out = fopen("sorted.dat","wb");
        fseek(in, 0, 0);
        fread(h, SHED, 1, in);
        fwrite(h, SHED, 1, out);
 
        fread(p, SBLC, 1, in);
        while(!feof(in))
        {
            for(i = 0; i < p->rec_num; i++)
            {
                fread(&st, SSTU, 1, t);
                p->record[i] = st;
                //printf(FORMAT, p->record[i].id, p->record[i].name, p->record[i].age, p->record[i].grade);
            }
            fwrite(p, SBLC, 1, out);
            fread(p, SBLC, 1, in);
        }
        fclose(out);
        fclose(t);
        remove(TempFile);
    }
    fclose(in);
    free (p);
    printf("Sort end!n");
    getchar();
}
 
int binsearch(struct block *p, int num, int left, int right)
{
    int middle;
 
    while (left <= right)
    {
        middle = (left + right) / 2;
        switch( (p->record[middle].id < num) ? -1 : (p->record[middle].id == num) ? 0 : 1)
        {
            case -1: left = middle + 1;break;
            case 0 : return middle;
            case 1 : right = middle - 1; 
        }
    }
    return -1;
}
 
void search()
{
    FILE *fp;
    struct block *p;
    int num;
    int i;
 
    printf("Please enter a num:");
    num = getnum();
    fp = fopen("sorted.dat", "rb");
    i = -1;
 
    p = (struct block*)malloc(SBLC);
    fseek(fp, SBLC, 0);
    while((fread(p, SBLC, 1, fp)) != 0)
    {
        if(p->record[0].id <= num && num <= p->record[p->rec_num-1].id)
        {   
            i = binsearch(p, num, 0, p->rec_num);
            break;
        }
         
    }
    if(i == -1)
    {
        printf("Can't find it!n");
    }
    else
    {
        printf(HEAD1);
        printf(HEAD2);
        printf(HEAD3);
        printf(FORMAT, p->record[i].id, p->record[i].name, p->record[i].age, p->record[i].grade);
        printf(END);
    }
    fclose(fp);
    free(p);
    getchar();
} 
/************************************************************************************************/
 
 
FILE：main.c
 
 
/* 
 * File:   main.c
 * Author: section
 *
 * Created on 2011年4月30日, 下午9:46
 */
#include "struct.h"
 
void menu()
{
    system("cls");
    printf("----------------MENU-----------------n");
    printf("| 1.Block 검색                      |n");
    printf("| 2.Sort                            |n");
    printf("| 3.Block 검색(Sorted)              |n");
    printf("| 4.학생 검색                       |n");
    printf("| 5.종료                            |n");
    printf("-------------------------------------n");
    printf("|!*0.데이터 파일      만들기        |n");
    printf("------------------학새관리-Ver 1.0---n");
}
 
int main(void)
{
    char key;
    while(1)
    {
    fflush(stdin);
        menu();
    scanf("%c", &key);
    if(key == '5' || key == 'q' || key == 'Q')
           break;
    switch(key)
    {
            case '1': blockstatus("student.dat");break;
            case '2': sort();break;
        case '3': blockstatus("sorted.dat");break;
        case '4': search();break;
            case '0': dump();break;
        case '6': read();break;
    }
    }
    return 0;
}