Pagini recente » Cod sursa (job #998120) | Cod sursa (job #2614031) | Cod sursa (job #1813447) | Cod sursa (job #155811) | Cod sursa (job #1704017)
/** trieSort **/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define Dragoste 4096
#define MAX_BIT 30
#define NIL -1
struct trie {
int count;
trie *son[2];
trie() {
this -> count = 0;
memset(this -> son, NULL, sizeof(this -> son));
}
};
trie *root = new trie;
int pos = Dragoste;
char buff[Dragoste];
char getChar(FILE *f) {
if (pos == Dragoste) {
fread(buff, 1, Dragoste, f);
pos = 0;
}
return buff[pos++];
}
void fscanf(FILE *f, const char *arg, int *result) {
*result = 0;
char c;
do {
c = getChar(f);
} while (!isdigit(c));
do {
(*result) = (*result << 3) + (*result << 1) + c - '0';
c = getChar(f);
} while (isdigit(c));
}
void insert(trie *nod, int x, int bit) {
if (bit == NIL) {
nod -> count++;
return;
}
int next = (x >> bit) & 1;
if (nod -> son[next] == NULL) {
nod -> son[next] = new trie;
}
insert(nod -> son[next], x, bit - 1);
}
int erase(trie *nod, int x, int bit) {
if (bit == NIL) {
nod -> count--;
} else {
int next = (x >> bit) & 1;
if (erase(nod -> son[next], x, bit - 1)) {
nod -> son[next] = NULL;
}
}
return nod != root && nod -> count == 0 && nod -> son[0] == NULL && nod -> son[1] == NULL;
}
int search(trie *nod, int bit, int result = 0) {
if (bit == NIL) {
return result;
}
if (nod -> son[0] != NULL) {
return search(nod -> son[0], bit - 1, result);
} else {
return search(nod -> son[1], bit - 1, result | (1 << bit));
}
}
int main(void) {
int N, i, val;
FILE *f = fopen("algsort.in", "r");
fscanf(f, "%d", &N);
for (i = 1; i <= N; i++) {
fscanf(f, "%d", &val);
insert(root, val, MAX_BIT);
}
fclose(f);
freopen("alsort.out", "w", stdout);
for (i = 1; i <= N; i++) {
val = search(root, MAX_BIT);
erase(root, val, MAX_BIT);
fprintf(stdout, "%d ", val);
}
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}