C 语言实现置换选择排序算法 - 败者树优化

#include\x20\x3Cstdio.h\x3E #define\x20MAXKEY\x2010000 #define\x20RUNEND_SYMBOL\x2010000\x20\x2F\x2F\x20归并段结束标志 #define\x20w\x206\x20\x2F\x2F\x20内存工作区可容纳的记录个数 #define\x20N\x2024\x20\x2F\x2F\x20设文件中含有的记录的数量 typedf\x20int\x20KeyType;\x20\x2F\x2F\x20定义关键字类型为整型

\x2F\x2F\x20记录类型 typedf\x20struct\x20{ \x20\x20KeyType\x20key;\x20\x2F\x2F\x20关键字项 }\x20RedType;

typedf\x20int\x20LoserTree[w];\x2F\x2F\x20败者树是完全二叉树且不含叶子，可采用顺序存储结构 typedf\x20struct

{ \x20\x20RedType\x20rec;\x20\x2F\x2F\x20记录 \x20\x20KeyType\x20key;\x20\x2F\x2F\x20从记录中抽取的关键字 \x20\x20int\x20rnum;\x20\x2F\x2F\x20所属归并段的段号 }\x20RedNode,\x20WorkArea[w];

\x2F\x2F\x20从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段 void\x20Select_MiniMax(LoserTree\x20ls,\x20WorkArea\x20wa,\x20int\x20q)\x20{ \x20\x20int\x20p,\x20s,\x20t; \x20\x20\x2F\x2F\x20ls[t]为q的双亲节点，p作为中介

\x20\x20for\x20(t\x20=\x20(w\x20+\x20q)\x20/\x202,\x20p\x20=\x20ls[t];\x20t\x20\x3E\x200;\x20t\x20=\x20t\x20/\x202,\x20p\x20=\x20ls[t])\x20{ \x20\x20\x20\x20\x2F\x2F\x20段号小者\x20或者\x20段号相等且关键字更小的为胜者 \x20\x20\x20\x20if\x20(wa[p].rnum\x20\x3C\x20wa[q].rnum\x20||\x20(wa[p].rnum\x20==\x20wa[q].rnum\x20&&\x20wa[p].key\x20\x3C\x20wa[q].key))\x20{ \x20\x20\x20\x20\x20\x20s\x20=\x20q; \x20\x20\x20\x20\x20\x20q\x20=\x20ls[t];\x20\x2F\x2Fq指示新的胜利者 \x20\x20\x20\x20\x20\x20ls[t]\x20=\x20s; \x20\x20\x20\x20} \x20\x20} \x20\x20ls[0]\x20=\x20q;\x20\x2F\x2F\x20最后的冠军 } \x2F\x2F输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录，并由s指示其在wa中的位置。 void\x20Construct_Loser(LoserTree\x20ls,\x20WorkArea\x20wa,\x20FILE*\x20fi)\x20{ \x20\x20int\x20i; \x20\x20for\x20(i\x20=\x200;\x20i\x20\x3C\x20w;\x20++i)\x20{ \x20\x20\x20\x20wa[i].rnum\x20=\x20wa[i].key\x20=\x20ls[i]\x20=\x200; \x20\x20} \x20\x20for\x20(i\x20=\x20w\x20-\x201;\x20i\x20\x3E=\x200;\x20--i)\x20{ \x20\x20\x20\x20fread(&wa[i].rec,\x20sizeof(RedType),\x201,\x20fi);\x2F\x2F\x20输入一个记录 \x20\x20\x20\x20wa[i].key\x20=\x20wa[i].rec.key;\x20\x2F\x2F\x20提取关键字 \x20\x20\x20\x20wa[i].rnum\x20=\x201;\x20\x2F\x2F\x20其段号为＂1＂ \x20\x20\x20\x20Select_MiniMax(ls,\x20wa,\x20i);\x20\x2F\x2F\x20调整败者树 \x20\x20} }

\x2F\x2F\x20求得一个初始归并段，fi为输入文件指针，fo为输出文件指针。 void\x20get_run(LoserTree\x20ls,\x20WorkArea\x20wa,\x20int\x20rc,\x20int*\x20rmax,\x20FILE*\x20fi,\x20FILE*\x20fo)\x20{ \x20\x20int\x20q; \x20\x20KeyType\x20minimax; \x20\x20\x2F\x2F\x20选得的MINIMAX记录属当前段时 \x20\x20while\x20(wa[ls[0]].rnum\x20==\x20rc)\x20{ \x20\x20\x20\x20q\x20=\x20ls[0];\x2F\x2F\x20q指示MINIMAX记录在wa中的位置 \x20\x20\x20\x20minimax\x20=\x20wa[q].key; \x20\x20\x20\x20\x2F\x2F\x20将刚选得的MINIMAX记录写入输出文件 \x20\x20\x20\x20fwrite(&wa[q].rec,\x20sizeof(RedType),\x201,\x20fo); \x20\x20\x20\x20\x2F\x2F\x20如果输入文件结束，则虚设一条记录（属＂rmax+1＂段） \x20\x20\x20\x20if\x20(feof(fi))\x20{ \x20\x20\x20\x20\x20\x20wa[q].rnum\x20=\x20rmax\x20+\x201; \x20\x20\x20\x20\x20\x20wa[q].key\x20=\x20MAXKEY; \x20\x20\x20\x20} \x20\x20\x20\x20else\x20{\x20\x2F\x2F\x20输入文件非空时 \x20\x20\x20\x20\x20\x20\x2F\x2F\x20从输入文件读入下一记录 \x20\x20\x20\x20\x20\x20fread(&wa[q].rec,\x20sizeof(RedType),\x201,\x20fi); \x20\x20\x20\x20\x20\x20wa[q].key\x20=\x20wa[q].rec.key;\x2F\x2F\x20提取关键字 \x20\x20\x20\x20\x20\x20if\x20(wa[q].key\x20\x3C\x20minimax)\x20{ \x20\x20\x20\x20\x20\x20\x20\x20\x2F\x2F\x20新读入的记录比上一轮的最小关键字还小，则它属下一段 \x20\x20\x20\x20\x20\x20\x20\x20rmax\x20=\x20rc\x20+\x201; \x20\x20\x20\x20\x20\x20\x20\x20wa[q].rnum\x20=\x20*rmax; \x20\x20\x20\x20\x20\x20} \x20\x20\x20\x20\x20\x20else\x20{ \x20\x20\x20\x20\x20\x20\x20\x20\x2F\x2F\x20新读入的记录大则属当前段 \x20\x20\x20\x20\x20\x20\x20\x20wa[q].rnum\x20=\x20rc; \x20\x20\x20\x20\x20\x20} \x20\x20\x20\x20} \x20\x20\x20\x20\x2F\x2F\x20选择新的MINIMAX记录 \x20\x20\x20\x20Select_MiniMax(ls,\x20wa,\x20q); \x20\x20}

}

\x2F\x2F在败者树ls和内存工作区wa上用置换－选择排序求初始归并段 void\x20Replace_Selection(LoserTree\x20ls,\x20WorkArea\x20wa,\x20FILE*\x20fi,\x20FILE*\x20fo)\x20{ \x20\x20int\x20rc,\x20rmax; \x20\x20RedType\x20j; \x20\x20j.key\x20=\x20RUNEND_SYMBOL; \x20\x20\x2F\x2F\x20初建败者树 \x20\x20Construct_Loser(ls,\x20wa,\x20fi); \x20\x20rc\x20=\x20rmax\x20=\x201;\x2F\x2Frc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号

\x20\x20while\x20(rc\x20\x3C=\x20rmax)\x20{\x20\x2F\x2F\x20＂rc=rmax+1＂标志输入文件的置换－选择排序已完成 \x20\x20\x20\x20\x2F\x2F\x20求得一个初始归并段 \x20\x20\x20\x20get_run(ls,\x20wa,\x20rc,\x20&rmax,\x20fi,\x20fo); \x20\x20\x20\x20fwrite(&j,\x20sizeof(RedType),\x201,\x20fo);\x2F\x2F将段结束标志写入输出文件 \x20\x20\x20\x20rc\x20=\x20wa[ls[0]].rnum;\x2F\x2F设置下一段的段号 \x20\x20} }

void\x20print(RedType\x20t)\x20{ \x20\x20printf("%d\x20",\x20t.key); }

int\x20main()\x20{ \x20\x20RedType\x20a[N]\x20=\x20{\x2051,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76\x20}; \x20\x20RedType\x20b; \x20\x20FILE*\x20fi,\x20*\x20fo;\x20\x2F\x2F输入输出文件 \x20\x20LoserTree\x20ls;\x20\x2F\x2F\x20败者树 \x20\x20WorkArea\x20wa;\x20\x2F\x2F\x20内存工作区 \x20\x20int\x20i,\x20k; \x20\x20fo\x20=\x20fopen_s(&fo,\x20"ori",\x20"wb");\x20\x2F\x2F准备对\x20ori\x20文本文件进行写操作 \x20\x20\x2F\x2F将数组\x20a\x20写入大文件ori \x20\x20fwrite(a,\x20sizeof(RedType),\x20N,\x20fo); \x20\x20fclose(fo);\x20\x2F\x2F关闭指针\x20fo\x20表示的文件 \x20\x20fi\x20=\x20fopen_s(&fi,\x20"ori",\x20"rb");\x2F\x2F准备对\x20ori\x20文本文件进行读操作 \x20\x20printf("文件中的待排序记录为:\n"); \x20\x20for\x20(i\x20=\x201;\x20i\x20\x3C=\x20N;\x20i++)\x20{ \x20\x20\x20\x20\x2F\x2F\x20依次将文件ori的数据读入并赋值给b \x20\x20\x20\x20fread(&b,\x20sizeof(RedType),\x201,\x20fi); \x20\x20\x20\x20print(b); \x20\x20} \x20\x20printf("\n"); \x20\x20rewind(fi);\x2F\x2F\x20使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件。 \x20\x20fo\x20=\x20fopen_s(&fo,\x20"out",\x20"wb"); \x20\x20\x2F\x2F\x20用置换－选择排序求初始归并段 \x20\x20Replace_Selection(ls,\x20wa,\x20fi,\x20fo); \x20\x20fclose(fo); \x20\x20fclose(fi); \x20\x20fi\x20=\x20fopen_s(&fi,\x20"out",\x20"rb"); \x20\x20printf("初始归并段各为:\n"); \x20\x20do\x20{ \x20\x20\x20\x20k\x20=\x20fread(&b,\x20sizeof(RedType),\x201,\x20fi);\x20\x2F\x2F读\x20fi\x20指针指向的文件，并将读的记录赋值给\x20b，整个操作成功与否的结果赋值给\x20k \x20\x20\x20\x20if\x20(k\x20==\x201)\x20{ \x20\x20\x20\x20\x20\x20if\x20(b.key\x20==\x20MAXKEY)\x20{\x2F\x2F当其值等于最大值时，表明当前初始归并段已经完成 \x20\x20\x20\x20\x20\x20\x20\x20printf("\n\n"); \x20\x20\x20\x20\x20\x20\x20\x20continue; \x20\x20\x20\x20\x20\x20} \x20\x20\x20\x20\x20\x20print(b); \x20\x20\x20\x20} \x20\x20} while\x20(k\x20==\x201); \x20\x20return\x200; } 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(115,34):\x20error\x20C2440:\x20“=”:\x20无法从“errno_t”转换为“FILE\x20*” 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(115,17):\x20message:\x20从整型类型转换为指针类型需要 reinterpret_cast、C\x20样式转换或带圆括号的函数样式强制转换 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(119,34):\x20error\x20C2440:\x20“=”:\x20无法从“errno_t”转换为“FILE\x20*” 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(119,17):\x20message:\x20从整型类型转换为指针类型需要 reinterpret_cast、C\x20样式转换或带圆括号的函数样式强制转换 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(128,34):\x20error\x20C2440:\x20“=”:\x20无法从“errno_t”转换为“FILE\x20*” 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(128,17):\x20message:\x20从整型类型转换为指针类型需要 reinterpret_cast、C\x20样式转换或带圆括号的函数样式强制转换 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(133,34):\x20error\x20C2440:\x20“=”:\x20无法从“errno_t”转换为“FILE\x20*” 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(133,17):\x20message:\x20从整型类型转换为指针类型需要 reinterpret_cast、C\x20样式转换或带圆括号的函数样式强制转换 1\x3E:/code/ConsoleApplication6/ConsoleApplication6.cpp(136,46):\x20warning\x20C4267:\x20“=”:\x20从“size_t”转换到“int”，可能丢失数据内容：It\x20seems\x20that\x20there\x20is\x20an\x20error\x20in\x20the\x20code\x20because\x20the\x20fopen_s\x20function\x20is\x20not\x20being\x20called\x20correctly.\x20The\x20function\x20expects\x20the\x20first\x20parameter\x20to\x20be\x20a\x20pointer\x20to\x20a\x20FILE\x20object,\x20but\x20it\x20is\x20receiving\x20an\x20integer\x20value\x20instead.

To\x20fix\x20this\x20issue,\x20you\x20should\x20change\x20the\x20lines\x20where\x20fopen_s\x20is\x20called\x20to\x20pass\x20the\x20address\x20of\x20the\x20FILE\x20object\x20pointers,\x20like\x20this:

fopen_s(&fo,\x20"ori",\x20"wb");

fopen_s(&fi,\x20"ori",\x20"rb");

fopen_s(&fo,\x20"out",\x20"wb");

fopen_s(&fi,\x20"out",\x20"rb");

This\x20will\x20correctly\x20pass\x20the\x20address\x20of\x20the\x20FILE\x20object\x20pointers\x20to\x20the\x20fopen_s\x20function.