외부 정렬 대체 선택
#include <stdio.h>
#include<queue>
#include"fatal.h"
#define M 3//
#define N 33// ,1—N
typedef int ElementType;
char name[200];//
std::queue<int> notHandleFile;
std::queue<int> nullFile;
char* fileName(char *buf, int i) {
strcpy(buf, "T");
char num[5];
strcat(buf, _itoa(i + 1, num, 10));
return buf;
}
int RandInt(int i, int j) {
int temp;
temp = (int)(i + (1.0*rand() / RAND_MAX)*(j - i));
return temp;
}
void getRandomInt(int *A, int n) {
for (int i = 0; i < n; i++) {
A[i] = i + 1;
}
for (int i = 1; i < n; i++) {
//std::swap(A[i], A[RandInt(0, i)]);
int randAdrr = RandInt(0, i);
int t = A[i];
A[i] = A[randAdrr];
A[randAdrr] = t;
}
}
void writeRandIntToFile() {
int a[N];
getRandomInt(a, N);
FILE *fp = fopen("ta1", "w");
for (int &i : a)
fprintf(fp, "%d ", i);
fclose(fp);
}
#define leftChild(i) (2*(i)+1) // 0
void percDown(int *a, int i, int n) {
int child = leftChild(i);
int temp;
for (temp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if (child != n - 1 && a[child] > a[child + 1])
child++;
if (temp > a[child])
a[i] = a[child];
else
break;
}
a[i] = temp;
}
void buildHeap(int *arr, int n) {
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
percDown(arr, i, n);
}
}
void insertHeap(int *arr, int &n) {
int i;
int X = arr[n];
n++;
for (i = n - 1; i > 0 && arr[(i - 1) / 2] > X; i = (i - 1) / 2)// 0 ,
arr[i] = arr[(i - 1) / 2];
arr[i] = X;
}
int deleteMin(int *arr, int &n) {//n
int i, child;
ElementType minElement, lastElement;
minElement = arr[0];
lastElement = arr[n - 1];//
n--;
for (i = 0; i <n; i = child) {
child = leftChild(i);
if (child >= n)// , , i child,child
break;
if (child != n - 1 && arr[child] > arr[child + 1]) {//
child++;
}
if (lastElement > arr[child])
arr[i] = arr[child];
else
break;
}
arr[i] = lastElement;
return minElement;
}
void initRun(char *inputFileName) {
FILE* readFp = fopen(inputFileName, "r");
if (readFp == NULL)
Error("OPEN FILE FAILED");
int fileNum = 0;//
int arr[M];//
int size = 0;//
int deadSpace = M - 1;//
while (size < M && fscanf(readFp, "%d", &arr[size]) == 1) {//
size++;
}
do {
FILE *writeFile = fopen(fileName(name, fileNum), "w");
buildHeap(arr, size);
while (size != 0) {//
int min = deleteMin(arr, size);
fprintf(writeFile, "%d ", min);
if (fscanf(readFp, "%d", &arr[deadSpace]) == 1) {// ,
if (arr[deadSpace]>min) {//
insertHeap(arr, size);// size deadSize
}
else {//
deadSpace--;
}
}
}
fclose(writeFile);
notHandleFile.push(fileNum);
fileNum++;//
size = M - 1 - deadSpace;//
deadSpace = M - 1;//
if (size > 0 && size<M) {//
for (int i = 0; i < size; i++) {
arr[i] = arr[i + M - size];
}
}
} while (!feof(readFp));
nullFile.push(fileNum);
}
void mergeRun(int file1, int file2, int writefile) {
FILE *readFp1 = fopen(fileName(name, file1),"r");
FILE *readFp2 = fopen(fileName(name, file2), "r");
FILE *writeFp = fopen(fileName(name, writefile), "w");
int a, b;
int hasNum1 = 0, hasNum2 = 0;
while ((hasNum1==1||fscanf(readFp1, "%d", &a)==1)&& (hasNum2 == 1 || fscanf(readFp2, "%d", &b) == 1)) {
hasNum1 = 1;
hasNum2 = 1;
if (a < b) {
fprintf(writeFp, "%d ", a);
hasNum1 = 0;
}
else {
fprintf(writeFp, "%d ", b);
hasNum2 = 0;
}
}
while ((hasNum1 == 1 || fscanf(readFp1, "%d", &a) == 1)) {
fprintf(writeFp, "%d ", a);
hasNum1 = 0;
}
while (hasNum2 == 1 || fscanf(readFp2, "%d", &b) == 1) {
fprintf(writeFp, "%d ", b);
hasNum2 = 0;
}
fclose(readFp1);
fclose(readFp2);
fclose(writeFp);
}
int main() {
writeRandIntToFile();
char inputFileName[20] = "ta1";//
//scanf("%s", inputFileName);
initRun(inputFileName);//
int cnt = 0;
while (notHandleFile.size() > 1) {
int file1 = notHandleFile.front();
notHandleFile.pop();
int file2 = notHandleFile.front();
notHandleFile.pop();
int writeFile = nullFile.front();
nullFile.pop();
mergeRun(file1, file2, writeFile);
nullFile.push(file1);
nullFile.push(file2);
notHandleFile.push(writeFile);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.