Исходный код программы сортировки с использованием 2-3 дерева на Си — КиберПедия 

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Исходный код программы сортировки с использованием 2-3 дерева на Си

2017-11-16 218
Исходный код программы сортировки с использованием 2-3 дерева на Си 0.00 из 5.00 0 оценок
Заказать работу

 

/*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);

}

 


Поделиться с друзьями:

Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.032 с.