C语言实现置换-选择排序算法求初始归并段

#include <stdio.h>\n#define MAXKEY 10000\n#define RUNEND_SYMBOL 10000 // 归并段结束标志\n#define w 6 // 内存工作区可容纳的记录个数\n#define N 24 // 设文件中含有的记录的数量\ntypedef int KeyType; // 定义关键字类型为整型\n\n// 记录类型\ntypedef struct {\n KeyType key; // 关键字项\n}RedType;\n\n\ntypedef int LoserTree[w];// 败者树是完全二叉树且不含叶子，可采用顺序存储结构\ntypedef struct\n\n{\n RedType rec; /* 记录 /\n KeyType key; / 从记录中抽取的关键字 /\n int rnum; / 所属归并段的段号 /\n}RedNode, WorkArea[w];\n\n// 从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段\nvoid Select_MiniMax(LoserTree ls, WorkArea wa, int q) {\n int p, s, t;\n // ls[t]为q的双亲节点，p作为中介\n\n for (t = (w + q) / 2, p = ls[t]; t > 0; t = t / 2, p = ls[t]) {\n // 段号小者 或者 段号相等且关键字更小的为胜者\n if (wa[p].rnum < wa[q].rnum || (wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key)) {\n s = q;\n q = ls[t]; //q指示新的胜利者\n ls[t] = s;\n }\n }\n ls[0] = q; // 最后的冠军\n}\n//输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录，并由s指示其在wa中的位置。\nvoid Construct_Loser(LoserTree ls, WorkArea wa, FILE fi) {\n int i;\n for (i = 0; i < w; ++i) {\n wa[i].rnum = wa[i].key = ls[i] = 0;\n }\n for (i = w - 1; i >= 0; --i) {\n fread(&wa[i].rec, sizeof(RedType), 1, fi);// 输入一个记录\n wa[i].key = wa[i].rec.key; // 提取关键字\n wa[i].rnum = 1; // 其段号为＂1＂\n Select_MiniMax(ls, wa, i); // 调整败者树\n }\n}\n\n// 求得一个初始归并段，fi为输入文件指针，fo为输出文件指针。\nvoid get_run(LoserTree ls, WorkArea wa, int rc, int* rmax, FILE* fi, FILE* fo) {\n int q;\n KeyType minimax;\n // 选得的MINIMAX记录属当前段时\n while (wa[ls[0]].rnum == rc) {\n q = ls[0];// q指示MINIMAX记录在wa中的位置\n minimax = wa[q].key;\n // 将刚选得的MINIMAX记录写入输出文件\n fwrite(&wa[q].rec, sizeof(RedType), 1, fo);\n // 如果输入文件结束，则虚设一条记录（属＂rmax+1＂段）\n if (feof(fi)) {\n wa[q].rnum = rmax + 1;\n wa[q].key = MAXKEY;\n }\n else { // 输入文件非空时\n // 从输入文件读入下一记录\n fread(&wa[q].rec, sizeof(RedType), 1, fi);\n wa[q].key = wa[q].rec.key;// 提取关键字\n if (wa[q].key < minimax) {\n // 新读入的记录比上一轮的最小关键字还小，则它属下一段\n rmax = rc + 1;\n wa[q].rnum = rmax;\n }\n else {\n // 新读入的记录大则属当前段\n wa[q].rnum = rc;\n }\n }\n // 选择新的MINIMAX记录\n Select_MiniMax(ls, wa, q);\n }\n\n}\n\n//在败者树ls和内存工作区wa上用置换－选择排序求初始归并段\nvoid Replace_Selection(LoserTree ls, WorkArea wa, FILE fi, FILE fo) {\n int rc, rmax;\n RedType j;\n j.key = RUNEND_SYMBOL;\n // 初建败者树\n Construct_Loser(ls, wa, fi);\n rc = rmax = 1;//rc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号\n\n while (rc <= rmax) {// ＂rc=rmax+1＂标志输入文件的置换－选择排序已完成\n // 求得一个初始归并段\n get_run(ls, wa, rc, &rmax, fi, fo);\n fwrite(&j, sizeof(RedType), 1, fo);//将段结束标志写入输出文件\n rc = wa[ls[0]].rnum;//设置下一段的段号\n }\n}\n\nvoid print(RedType t) {\n printf("%d ", t.key);\n}\n\nint main() {\n RedType a[N] = { 51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76 };\n RedType b;\n FILE fi, * fo; //输入输出文件\n LoserTree ls; // 败者树\n WorkArea wa; // 内存工作区\n int i, k;\n fo = fopen("ori", "wb"); //准备对 ori 文本文件进行写操作\n //将数组 a 写入大文件ori\n fwrite(a, sizeof(RedType), N, fo);\n fclose(fo); //关闭指针 fo 表示的文件\n fi = fopen("ori", "rb");//准备对 ori 文本文件进行读操作\n printf("文件中的待排序记录为:\n");\n for (i = 1; i <= N; i++) {\n // 依次将文件ori的数据读入并赋值给b\n fread(&b, sizeof(RedType), 1, fi);\n print(b);\n }\n printf("\n");\n rewind(fi);// 使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件。\n fo = fopen("out", "wb");\n // 用置换－选择排序求初始归并段\n Replace_Selection(ls, wa, fi, fo);\n fclose(fo);\n fclose(fi);\n fi = fopen("out", "rb");\n printf("初始归并段各为:\n");\n do {\n k = fread(&b, sizeof(RedType), 1, fi); //读 fi 指针指向的文件，并将读的记录赋值给 b，整个操作成功与否的结果赋值给 k\n if (k == 1) {\n if (b.key == MAXKEY) {//当其值等于最大值时，表明当前初始归并段已经完成\n printf("\n\n");\n continue;\n }\n print(b);\n }\n } while (k == 1);\n return 0;\n}\n