Метод Шелла

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

#include <locale.h>

void main()

{ int *c,*c2,i,j,k,d,f,t,kol_sym,r,q,*lent,N;

char *a,*a2,**b,**b2,s,el,str[25]="";

setlocale(LC_ALL,"Russian");

printf("Введите число лент: ");

scanf("%d",&N);

printf("Введите количество элементов, кратное %d: ",N);

scanf("%d",&kol_sym);

lent=(int*)(malloc(N*(sizeof(int))));//Выделение памяти под считчики лент

//Выделение памяти под элементы полей

a=(char*)(malloc (kol_sym*(sizeof(char))));

b=(char**)(malloc (kol_sym*(sizeof(char))));

for(i=0;i<kol_sym;i++)

b[i]=(char*)malloc(10*sizeof(char));

b2=(char**)(malloc (kol_sym*(sizeof(char))));

for(i=0;i<kol_sym;i++)

b2[i]=(char*)malloc(10*sizeof(char));

c=(int*)(malloc(kol_sym*(sizeof(int))));

c2=(int*)(malloc(kol_sym*(sizeof(int))));

a2=(char*)(malloc (kol_sym*(sizeof(char))));

//Ввод ключевого поля

for(i=0;i<kol_sym;i++) {

printf("\nВведите символ%d: ",i+1);

s=getch();

if((s>=65)&&(s<=122)) {

printf("%c",s);

a[i]=s; }

else {

printf("Некооректный символ, придется повторить");

i--; } }

printf("\n\n");

//Ввод строк

for(i=0;i<kol_sym;i++) {

printf("Введите строку %d: ",i+1);

scanf("%s",b[i]); }

printf("\n");

//Ввод числовых данных

for(i=0;i<kol_sym;i++) { printf("Введите число %d: ",i+1);

scanf("%d",&c[i]); }

//Сортировка каждой ленты методом Шелла

for(r=1;r<=N;r++)

{ d=kol_sym/(N*2);//Шаг сортировки равен: длина ленты/2

while(d>0)

{ for(j=(d+(r-1)*kol_sym/N);j<(r*kol_sym/N);j++) { for(t=0;t<25;t++) b2[0][t]=b[j][t]; f=a[j]; q=c[j];

for(k=j-d;f<a[k]&&k>=(r-1)*kol_sym/N;k=k-d)

{ for(t=0;t<25;t++)

b[k+d][t]=b[k][t];

a[k+d]=a[k];

c[k+d]=c[k]; }

for(t=0;t<25;t++)

b[k+d][t]=b2[0][t];

a[k+d]=f;

c[k+d]=q; }

d=d/2;//Уменьшить шаг на 2 } }

//Метод слияния лент

printf("\n\n");

for(i=0;i<N;i++)

lent[i]=i*kol_sym/N;//Счетчик каждой ленты

for(i=0;i<kol_sym;i++)

{ el='z';

for(j=0;j<N;j++) if((el>=a[lent[j]])&&(lent[j]!=-1))

{ el=a[lent[j]];

d=j; }

a2[i]=a[lent[d]];

c2[i]=c[lent[d]];

for(j=0;j<25;j++) b2[i][j]=b[lent[d]][j];

lent[d]++;

if(lent[d]==(d*kol_sym/N)+kol_sym/N)//если счетчик достиг предела lent[d]=-1; }

printf("\nРезультат:\n");

for(i=0;i<kol_sym;i++)

{ printf("\n%d: %2c",i+1,a2[i]);

printf("%12s ",b2[i]);

printf("%10d ",c2[i]); }

getch();}

Поиск по двоичному дереву

#include <conio.h>

#include <stdio.h>

#include <locale.h>

#include <stdlib.h>

#include <string.h>

typedef struct baza

{ char word[15];

float value;};

typedef struct tree

{baza w;

struct tree *left;

struct tree *right;};

tree *Addtree(tree *root, baza new_el)

{if (root==NULL)

{root=(tree*)malloc(sizeof(tree));

root->left=root->right=NULL;

root->w=new_el;

return root;}

if(strcmp(root->w.word,new_el.word)<0)

root->right=Addtree(root->right,new_el);

if(strcmp(root->w.word,new_el.word)>0)

root->left=Addtree(root->left,new_el);

return root;}

int Search(tree *root, char *key)

{if(root==NULL)

{printf("\n\n----------------------------------------");

printf("\nПоиск не дал результатов");

return 0;}

if(strcmp(root->w.word,key)<0)

Search(root->right,key);

if(strcmp(root->w.word,key)>0)

Search(root->left,key);

if(strcmp(root->w.word,key)==0){

printf("\n\n----------------------------------------");

printf("\nРезультат поиска:\n\n%s ",root->w.word);

printf("%f",root->w.value);}}

void main()

{setlocale(LC_ALL,"Rus");

int n,i;

printf("Введите количество данных: ");

scanf("%d",&n);

char key[15];

baza *masstruct;

tree *root;

root=NULL;

masstruct=(baza*)malloc(sizeof(baza)*n);

for(i=0;i<n;i++)

{printf("\nВведите слово %d: ",i+1);

scanf("%s",masstruct[i].word);

printf("Число %d: ",i+1);

scanf("%f",&masstruct[i].value);

root=Addtree(root,masstruct[i]); }

printf("\nВведите элемент поиска: ");

scanf("%s",key);

Search(root,key);

free(masstruct);

getch(); }