Исходный код программы сортировки с использованием 2-3 дерева на Си
/*tree.h*/
struct Node{
struct Node * l, * m, * r;
char * kl, * kr;
};
int AddElem(struct Node **, char *);
char * SearchElem(struct Node *, char *);
void _print(struct Node *);
void PrintElem(struct Node *, char *);
void WriteElem(int, struct Node *);
int DelElem(struct Node **, char *);
void Free(struct Node *);
/*tree.c*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
struct Node{
struct Node * l, * m, * r;
char * kl, * kr;
};
char bufG[32];
struct Node * _AddElem(struct Node * R, char ** K){
struct Node * p, * q;
int k;
if (R==NULL)
return NULL;
if (strcmp(*K, R->kl)<0){
k=1;
q=R->l;
}
else if (strcmp(*K, R->kl)==0)
return (struct Node *)-1;
else if (R->kr==NULL || strcmp(*K, R->kr)<0){
k=2;
q=R->m;
}
else if (strcmp(*K, R->kr)==0)
return (struct Node *)-1;
else{
k=3;
q=R->r;
}
p=_AddElem(q, K);
if (p==(struct Node *)-1)
return p;
if (*K==NULL)
return NULL;
switch (k){
case 1:
if (R->kr==NULL){
R->kr=R->kl;
R->kl=*K;
R->r=R->m;
R->m=p;
*K=NULL;
return NULL;
}
else{
q=malloc(sizeof(struct Node));
q->kl=R->kr;
q->kr=NULL;
q->l=R->m;
q->m=R->r;
q->r=NULL;
R->kr=R->kl;
R->kl=*K;
*K=R->kr;
R->kr=NULL;
R->m=p;
R->r=NULL;
return q;
}
case 2:
if (R->kr==NULL){
R->kr=*K;
R->r=p;
*K=NULL;
return NULL;
}
else{
q=malloc(sizeof(struct Node));
q->kl=R->kr;
q->kr=NULL;
q->l=p;
q->m=R->r;
q->r=NULL;
R->kr=NULL;
R->r=NULL;
return q;
}
case 3:
q=malloc(sizeof(struct Node));
q->kl=*K;
q->kr=NULL;
q->l=R->r;
q->m=p;
q->r=NULL;
*K=R->kr;
R->kr=NULL;
R->r=NULL;
return q;
}
}
int AddElem(struct Node ** R, char * key){
struct Node * p, * q;
char * dkey;
dkey=malloc(strlen(key)+1);
strcpy(dkey, key);
if (*R==NULL){
*R=malloc(sizeof(struct Node));
(*R)->kl=dkey;
(*R)->l=(*R)->m=(*R)->r=NULL;
return 1;
}
p=_AddElem(*R, &dkey);
if (p==(struct Node *)-1){
free(dkey);
return 0;
}
if (p){
q=*R;
*R=malloc(sizeof(struct Node));
(*R)->kl=dkey;
(*R)->l=q;
(*R)->m=p;
(*R)->r=NULL;
return 1;
}
else
return 1;
}
char * SearchElem(struct Node * R, char * K){
while (R){
if (strcmp(K, R->kl)<0)
R=R->l;
else if (strcmp(K, R->kl)==0)
return R->kl;
else if (R->kr==NULL || strcmp(K, R->kr)<0)
R=R->m;
else if (strcmp(K, R->kr)==0)
return R->kr;
else
R=R->r;
}
return NULL;
}
void _print(struct Node * R){
static k=0;
if (R){
printf("%x k=%d %x %s %x %s %x\n", R, k, R->l, R->kl, R->m, R->kr, R->r);
k++;
_print(R->l);
_print(R->m);
_print(R->r);
k--;
}
}
void PrintElem(struct Node * R, char * K){
if (R){
if (strcmp(K, R->kl)<0){
PrintElem(R->l, K);
printf("Key=%s\n", R->kl);
}
if (R->kr==NULL || strcmp(K, R->kr)<0){
PrintElem(R->m, K);
if (R->kr)
printf("Key=%s\n", R->kr);
}
PrintElem(R->r, K);
}
}
void WriteElem(int f, struct Node * R){
int l;
if (R){
WriteElem(f, R->l);
l=strlen(R->kl);
write(f, R->kl, l);
write(f, bufG, 32-l);
WriteElem(f, R->m);
if (R->kr){
l=strlen(R->kr);
write(f, R->kr, l);
write(f, bufG, 32-l);
WriteElem(f, R->r);
}
}
}
int _DelElem(struct Node * R, char * K){
static char ** dkey=NULL;
struct Node * p, * q;
int k;
if (R==NULL){
if (dkey==NULL)
return -1;
else
return 1;
}
if (strcmp(K, R->kl)<0){
k=1;
q=R->l;
}
else if (strcmp(K, R->kl)==0){
free(R->kl);
dkey=&R->kl;
k=1;
q=R->l;
}
else if (R->kr==NULL || strcmp(K, R->kr)<0){
k=2;
q=R->m;
}
else if (strcmp(K, R->kr)==0){
free(R->kr);
dkey=&R->kr;
k=2;
q=R->m;
}
else{
k=3;
q=R->r;
}
switch (_DelElem(q, K)){
case -1:
return -1;
case 0:
return 0;
case 1:
switch (k){
case 1:
if (R->l==NULL){
if (R->kr){
R->kl=R->kr;
R->kr=NULL;
return 0;
}
else{
R->kl=NULL;
return 1;
}
}
if (R->m->kr){
R->l->kl=R->kl;
R->kl=R->m->kl;
R->l->m=R->m->l;
R->m->kl=R->m->kr;
R->m->l=R->m->m;
R->m->m=R->m->r;
R->m->kr=NULL;
R->m->r=NULL;
return 0;
}
R->l->kl=R->kl;
R->l->kr=R->m->kl;
R->l->m=R->m->l;
R->l->r=R->m->m;
free(R->m);
if (R->kr){
R->kl=R->kr;
R->m=R->r;
R->kr=NULL;
R->r=NULL;
return 0;
}
R->m=NULL;
return 1;
case 2:
if (R->m==NULL){
if (dkey!=&R->kr){
*dkey=R->kl;
R->kl=NULL;
return 1;
}
else{
R->kr=NULL;
return 0;
}
}
if (R->l->kr){
R->m->kl=R->kl;
R->m->m=R->m->l;
R->m->l=R->l->r;
R->kl=R->l->kr;
R->l->kr=NULL;
R->l->r=NULL;
return 0;
}
R->l->kr=R->kl;
R->l->r=R->m->l;
free(R->m);
if (R->kr){
R->kl=R->kr;
R->m=R->r;
R->kr=NULL;
R->r=NULL;
return 0;
}
R->m=NULL;
return 1;
case 3:
if (R->r==NULL){
*dkey=R->kr;
R->kr=NULL;
return 0;
}
if (R->m->kr){
R->r->kl=R->kr;
R->kr=R->m->kr;
R->r->m=R->r->l;
R->r->l=R->m->r;
R->m->kr=NULL;
R->m->r=NULL;
return 0;
}
R->m->kr=R->kr;
R->m->r=R->r->l;
free(R->r);
R->r=NULL;
return 0;
}
}
}
int DelElem(struct Node ** R, char * key){
struct Node * p;
if (*R==NULL)
return 0;
switch (_DelElem(*R, key)){
case -1:
return 0;
case 1:
p=*R;
*R=(*R)->l;
free(p);
case 0:
return 1;
}
}
void Free(struct Node * p){
if (p){
Free(p->l);
Free(p->m);
free(p->kl);
if (p->kr){
Free(p->r);
free(p->kr);
}
free(p);
}
}
/*main.c*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include "tree.h"
#define FILENAME "primer.raw"
#define FILENAMEOUT "primersort0.raw"
int main(){
struct Node * P=NULL;
int f, l;
char * buf, * p, * pend, * q;
struct stat st;
if ((f=open(FILENAME, O_RDONLY))==-1){
perror("open");
exit(1);
}
if (fstat(f, &st)==-1){
perror("stat");
exit(1);
}
if ((buf=malloc(st.st_size+1))==NULL){
perror("malloc");
exit(1);
}
memset(buf, '\0', st.st_size+1);
if (read(f, buf, st.st_size)!=st.st_size){
perror("read");
exit(1);
}
close(f);
pend=buf+st.st_size;
p=buf;
l=0;
/*Добавление праймеров в дерево*/
while (p<pend){
q=strchr(p, '\n');
if (!q)
break;
*q='\0';
l+=AddElem(&P, p);
p=q+1;
}
/*Длина праймера*/
printf("l=%d\n", l);
if ((f=creat(FILENAMEOUT, 0600))==-1){
perror("creat");
exit(1);
}
/*Запись*/
WriteElem(f, P);
close(f);
exit(0);
}