ОПИСАНИЕ ПОДПРОГРАММ - Структуры и алгоритмы обработки данных

Процедуры начальной обработки базы данных:

    1. void Read() - считывает базу данных и формирует индексный массив. 2. void PrintMas(void) - осуществляет просмотр базы данных.

Функции и процедуры сортировки:

    3 void heapsort(int N_) 4 void pyramid(int N_,int L, int R) эти 2 функции - сортируют базу данных по отделам и ФИО.

L - левая граница массива, R - правая граница массива.

Int Sravnenie(int p, int q) - сравнение дат рождения.

P, q - номера сравниваемых строк.

Void avl(struct BD D, derevo *&;p) - построение АВЛ дерева и добавление вершин в него.

Int PrintTree(derevo *p) чтение АВЛ Дерева

Void Searsh(int Ms, derevo *&;p) ) - поиск в дереве по ключу.

Int CompareDate(char s1[],char s2[]) - сравнение Фамилий

// Процедура расщепления для кодирования

Void SplittingCode(struct code *HEAD, struct code *&;a, struct code *&;b)

//Процедура Слияния Для Кодирования

Void MergeCode (struct code *&;a, struct code *&;b, int q, int r, struct code *&;c)

// Процедура сортировки методом прямого слияния для кодирования

Void MergeSortCode(struct code *&;HEAD, int N_)

// Процедура кодирования базы данных методом Шеннона

Void ShennonCode (FILE *f, char file_in[], char file_out[])

//Сравнение По Фио.

Int SravnenieFIO(int p1,int q1)

//Добавление в из массива в список

Void Addfrommas()

    4. ТЕКСТ ПРОГРАММЫ 5.

#include <cctype>

#include <math. h>

#include <clocale>

#include <iostream>

#include <windows. h>

#include <time. h>

#define N 10

#define n 10

Using namespace std;

//Вариант 37

Int *day;

Unsigned long int number;

Struct code

{

struct code *next;

unsigned char c;

double p;

int number;

};

Int sc=0;

Float entr, srdl;

Int rost, bal;

Char key_search[8];

FILE *f1,*f2;

//База данных "Пpедпpиятие"

Struct BD { char FIO[32]; // фоpмат <Фамилия>_<Имя>_<Отчество>

int numberO;

char dolzhnost[32];

char dateB[8];

} mas[10];

//Структура (список), используемая при сортировке базы данных.

Struct spisok { spisok *next;

BD data;

} *spis,*head,*end;

Struct list

{

struct BD note;

struct list *next;

};

Struct list *basehead,*keylist;

//AVL DEREVO

Struct derevo { BD sotrudnik;

short int bal;

struct derevo *left;

struct derevo *right;

struct derevo *down;

} *q,*r,*root,*start,*dn;

//ДЛЯ ПОИСКА

//по номеpу отдела и ФИО, К = номеp отдела;

Int Compare(char s1[],char s2[],int number)

{

int i=0;

do

{if (s1[i]<s2[i]) return 1;

else if (s1[i]>s2[i]) return 0;

else i++;

}

while (i<number);

return 2;

}

//Сравнение по номеру отдела и по фио.

Int SravnenieFIO(int p1,int q1)

{ if (Compare(mas[p1].FIO, mas[q1].FIO,32)==1) return 1; // I<I+1

else if (Compare(mas[p1].FIO, mas[q1].FIO,32)==0) return 0; // I>I+1

}

Int SravnenieNumberO(int p1,int q1)

{

if (mas[p1].numberO>mas[q1].numberO) return 0;// I>I+1

else if (mas[p1].numberO<mas[q1].numberO) return 1; // I<I+1

}

Void bubble(int N_)

{

int i, j,x;

struct BD temp;

for (i=1;i<N_-1;i++) {

for (j=0;j<N_-i;j++) {

if (SravnenieNumberO(day[j],day[j+1])==1) { temp=mas[day[j]]; mas[day[j]]=mas[day[j+1]]; mas[day[j+1]]=temp; } }}

}

//Сортировка Пирамидальная

Void pyramid(int N_,int L, int R)

{

int i, j,x;

x=day[L]; i=L;

printf("x=%d i=%d R=%d ",x, i,R);

while (true) { j=2*i;

printf("j=%d ",j);

if (j>R) { break;}//

if ((j<R)&;&; SravnenieNumberO(day[j+1],day[j])==1 ) { j++; }

if (SravnenieNumberO(x, day[j])==1) { break;} //

//mas[day[i]]=mas[day[j]]; i=j;

//day[i]=day[j]; i=j;

mas[i]=mas[j]; i=j;

}; //do

day[i]=x;

}

Void heapsort(int N_)

{

int i, j,x, L,R=N_;

int z, g; z=g=0;

struct BD temp;

L=1;

L=(int)(N_)/2;

while(L>=0)

{ //построение пирамиды

pyramid(N_,L, N_-1);

L=L-1;

};//while

R=N_;

while (R>=1) { z++; printf("z=%d ",z);

//temp=mas[day[1]]; mas[day[1]]=mas[day[R]]; mas[day[R]]=temp;

temp=mas[R]; mas[R]=mas[0]; mas[0]=temp;

// temp=mas[day[0]]; mas[day[0]]=mas[day[R]]; mas[day[R]]=temp;

R=R-1;

pyramid(N_,1,R);

g++; printf("g=%d ",g);

}//while;

}

Void Read() //Считывает базу данных, формирует индексный массив

{

int i;

f1=fopen("BASE2.DAT","rb");

day=(int*)realloc(day, N*sizeof(int));

//for (i=0;i<N;i++) free(mas[i]);

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

{

//mas[i]=(BD*)malloc(sizeof(BD));

fgets(mas[i].FIO,32,f1);

fgetc(f1);//отступ по символу

mas[i].numberO=fgetc(f1);

fgetc(f1);

fgets(mas[i].dolzhnost,22,f1);

fgetc(f1);

fgets(mas[i].dateB,8,f1);

fgetc(f1);

day[i]=i;

}

fclose(f1);

}

//void PrintMas(void) - осуществляет просмотр базы данных.

Void PrintMas()

{ int i; char h;

//system("cls");

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

{ printf("%4.d].%s %d %s %s ",i+1,mas[day[i]].FIO, mas[day[i]].numberO, mas[day[i]].dolzhnost, mas[day[i]].dateB);

if (kbhit()) { h=getch(); if (h==27) break; else getch(); }//FI

}//FOR

}

Void Addfrommas()

{ int i; spisok *p;

head=NULL;

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

p=(spisok*)malloc(sizeof(spisok));

if(i==0) {p->next=NULL; head=p; end=p; } else {p->next=NULL; end->next=p; end=p;}

p->data=mas[day[i]];

//printf(" %s ",p->data. FIO);

}

}

Void Print(spisok *p)

{

char h; int x=0;

do

{

printf("%s",p->data. FIO);

printf("%03d ",p->data. numberO);

printf("%s ",p->data. dolzhnost);

printf("%s ",p->data. dateB);

x++;

//if (p->next==NULL) break;

p=p->next;

} while (p!=NULL );

}

Void avl(struct BD D, derevo *&;p)

{

if (p==NULL)

{

p=(derevo *)malloc(sizeof(derevo));

p->sotrudnik=D;

p->left=NULL; p->right=NULL; p->down=NULL;

p->bal=0;

rost=1;

}

else

{ if(SravnenieNumberO(D. numberO,(p->sotrudnik. numberO)==1)) {dn=p;

while(1) {if (dn->down==NULL) {

dn->down=(derevo*)malloc(sizeof(derevo));

dn->down->sotrudnik=D; dn->down->down=NULL; break;}

else dn=dn->down;}

rost=0;}

if(SravnenieNumberO(D. numberO,(p->sotrudnik. numberO)==0))

{

avl(D, p->left);

if (rost)

{

if(p->bal>0)

{p->bal=0; rost=0;}

else

if( p->bal == 0)

{p->bal=-1;

}

else

{

if (p->left->bal < 0)

{ q=p->left;

p->bal=0;

q->bal=0;

p->left=q->right;

q->right=p;

p=q; rost=0;

} /*ll*/

else

{ q=p->left;

r=q->right;

if(r->bal < 0) p->bal=1;

else p->bal=0;

if(r->bal > 0) q->bal=-1;

else q->bal=0;

r->bal=0;

q->right=r->left;

p->left=r->right;

r->left=q;

r->right=p;

p=r;

rost=0;

} /*lr*/

}

}

}

//-------добавление в правое поддерево------------

if(SravnenieNumberO(D. numberO,(p->sotrudnik. numberO)==0))

{

avl(D, p->right);

if (rost)

{

if(p->bal < 0)

{p->bal=0; rost=0;}

else

if(p->bal==0)

{p->bal=1;

}

else

{

if (p->right->bal > 0)

{ q=p->right;

p->bal=0;

q->bal=0;

p->right=q->left;

q->left=p;

p=q; rost=0;

} /*rr*/

else

{

q=p->right;

r=q->left;

if( r->bal <0) q->bal=-1;

else q->bal=0;

if( r->bal >0) p->bal=1;

else p->bal=0;

r->bal=0;

p->right=r->left;

q->left=r->right;

r->left=p;

r->right=q;

p=r;

rost=0;

} /*rl*/

}

}

}

}

}

Int PrintTree(derevo *p)

{

if (p!=NULL)

{

PrintTree(p->left);

printf("%s %d %s %s ----------------------- ",p->sotrudnik. FIO,

p->sotrudnik. numberO,

p->sotrudnik. dolzhnost,

p->sotrudnik. dateB);

sc++;

dn=p; while(1)

{if (dn->down!=NULL)

{printf("%s %d %s %s ----------------------- ",dn->down->sotrudnik. FIO, dn->down->sotrudnik. numberO,

dn->down->sotrudnik. dolzhnost, dn->down->sotrudnik. dateB); sc++; dn=dn->down;}

else break; }

PrintTree(p->right);

}

return 0;

данные компьютер код

}

Int ravns(int ms, BD d2)

{ if(ms>d2.numberO) return 1;

if(ms<d2.numberO) return -1;

return 0;

}

Void searsh(int ms, derevo *&;p)

{ if(p==NULL) printf(" Not found ");

else {

if(ravns(ms, p->sotrudnik)==0){ printf("%s %d %s %s ----------------------- ",p->sotrudnik. FIO, p->sotrudnik. numberO, p->sotrudnik. dolzhnost, p->sotrudnik. dateB);

dn=p;

while(1)

{ if (dn->down!=NULL) {printf("%s %d %s %s ----------------------- ",dn->down->sotrudnik. FIO, dn->down->sotrudnik. numberO,

dn->down->sotrudnik. dolzhnost, dn->down->sotrudnik. dateB); dn=dn->down;}

else break;

}

}

if(ravns(ms, p->sotrudnik)>0) searsh(ms, p->right);

if(ravns(ms, p->sotrudnik)<0) searsh(ms, p->left);

}

}

Spisok *spissearsh(int ms, spisok *p)

{spisok *rt,*rthead,*rttail;

int i=0 ;

while(p->next!=0)

{ rt=(spisok*)malloc(sizeof(spisok));

if(ravns(ms, p->data)==0)

{

if(i==0) {rt->next=NULL; rthead=rt; rttail=rt; i=1; } else {rt->next=NULL; rttail->next=rt; rttail=rt;}

rt->data=p->data; p=p->next;

}

else p=p->next;

}

Return rthead;

}

//============================КОДИРОВАНИЕ

// Процедура записи данных из одного списка в другой

Void moveLtQ (struct code *&;l, struct code *&;t){

t->next=l;

t=l;

l=l->next;

}

// Процедура расщепления для кодирования

Void SplittingCode(struct code *HEAD, struct code *&;a, struct code *&;b)

{

struct code *k,*p;

a=HEAD;

b=HEAD->next;

k=a;

p=b;

while (p!=NULL)

{

k->next=p->next;

k=p;

p=p->next;

}

}

//Процедура слияния для кодирования

Void MergeCode (struct code *&;a, struct code *&;b, int q, int r, struct code *&;c)

{

while (q!=0 &;&; r!=0)

{

if (a->p > b->p)

{

moveLtQ(a, c);

q--;

}

else

{

moveLtQ(b, c);

r--;

}

}

while (q>0)

{

moveLtQ(a, c);

q--;

}

while (r>0)

{

moveLtQ(b, c);

r--;

}

}

// Процедура сортировки методом прямого слияния для кодирования

Void MergeSortCode(struct code *&;HEAD, int N_)

{

struct code *a,*b,*ch[2],*ct[2];

int p, q,r, m,i;

SplittingCode(HEAD, a,b);

p=1;

while (p<N_)

{

ch[0]=ch[1]=NULL;

ct[0]=(code*)&;ch[0];

ct[1]=(code*)&;ch[1];

i=0;

m=N_;

while (m>0)

{

if (m>=p)

q=p;

else q=m;

m=m-q;

if (m>=p)

r=p;

else r=m;

m=m-r;

MergeCode(a, b, q, r, ct[i]);

i=1-i;

}

a=ch[0];

b=ch[1];

p*=2;

}

ct[0]->next=NULL;

HEAD=ch[0];

}

// Процедура кодирования базы данных методом Шеннона

Void ShennonCode (FILE *f, char file_in[], char file_out[])

{

unsigned char *d, *dd, **C; //временные перменные для информации, двумерный массив

double H, LA, td, Q[257]; //H - энтропия, LA средняя длина, Q сумма вероятностей

int i, j,_N, lbit, lbyte, pbit, pbyte, cbit, lt, inds, L[256],INDX[256],INDXB[256]; //индексные массивы

//pbit pbyte - для записи побитовой

int l=sizeof(struct BD)*N; //l общее кол-во симаволов во всем файле

struct code *lst, *hlst, *p; //используемые списки для кодирповаия

f=fopen(file_in, "rb");

if (f==NULL)

{

printf("File not found.");

getch();

return;

}

d=(unsigned char*)malloc(l);//все символы в Д считывает

fread(d, 1, l, f);

fclose(f);

lst=(struct code*)malloc(sizeof(struct code)*256); //список в который последовательно по каждому возможному симвоу будет вноситься инфа

for (i=0; i<256; i++) //256 - всевозможные АСКИ символы

lst[i].number=0; //подсчет кол-ва используемых символов в файле

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

lst[d[i]].number++; //если такой символ встретился то он перемещается в нужную ячейку увеличивает параметр обращения к себе

_N=0;

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

{

if (lst[i].number)

_N++;

lst[i].next=(&;(lst[i]))+1; //переходим в следующий эл-т списка

lst[i].p=(double)lst[i].number/l; //расчитываем вероятность

lst[i].c=i; //записываем символ

}

hlst=lst;

lst[255].next=NULL;

MergeSortCode(lst,256);

for (p=lst, i=0; i<_N; p=p->next, i++)

INDX[i]=p->c;

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

INDXB[INDX[i]]=i; //заносим инфо в индексные массивы

Q[0]=0;

H=LA=0;

for (i=0; i<_N; i++)//по псевдокоду

{

Q[i+1]=Q[i]+hlst[INDX[i]].p;

td=-log(hlst[INDX[i]].p)/0.693147180559945309417;

L[i]=(int)ceil(td);

H=H+td*hlst[INDX[i]].p;

LA=LA+L[i]*hlst[INDX[i]].p;

}

C=(unsigned char**)malloc(sizeof(unsigned char*)*_N);

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

{

C[i]=(unsigned char*)malloc(sizeof(unsigned char)*L[i]);

}

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

{

for (j=0; j<L[i]; j++)

{

Q[i]*=2;

C[i][j]=(Q[i]);

if (Q[i]>=1)

Q[i]=Q[i]-1;

}

}

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

{

printf("%c:(%3i):",hlst[INDX[i]].c, hlst[INDX[i]].c);

for (j=0; j<L[i]; j++)

{

printf("%i",C[i][j]);

}

printf(" ");

}

for (i=lbit=0; i<_N; i++)

lbit=lbit+hlst[INDX[i]].number*L[i]; //преставляем в нулях и единицах информацию

lbyte=lbit/8;

if (lbit%8)

lbyte++;

dd=(unsigned char*)malloc(lbyte);

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

dd[i]=0;

for (i=pbit=0; i<l; i++)

{

inds=INDXB[d[i]];

lt=L[inds];

for (j=0; j<lt; j++,pbit++)

{

pbyte=pbit/8;

cbit=pbit%8;

dd[pbyte]|=C[inds][j]<<(7-cbit); //побитовый сдвиг

}

} //Разница му Энтрпией и сред. дл Степень Сжатия

printf ("Entropy=%f Average Length=%f Redundancy=%f Compression ratio=%f ",

H, LA, LA-H,(double)l/lbyte);

f=fopen(file_out, "wb");

if (f==NULL)

printf ("File not created");

else {

fwrite(dd, 1, lbyte, f);

fclose(f);

}

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

free(C[i]);

free(C);

free(hlst);

free(d);

}

Int main(void)

{ //setlocale(LC_ALL,"rus");

char c; int i; int nom; char zz;

FILE *Base;

while (c!='n') { system("cls");

printf("1 - Read base from file. ");

printf("2 - On Bubble sort. ");

printf("3 - On Heap sort. ");

printf("4 - Read massiv ");

printf("5 - Read Spisok ");

printf("6 - Read AVL ");

printf("7 - Add data in AVL tree ");

printf("8 - Add data in Spisok ");

printf("9 - Search ");

printf("10 - Shennon Code ");

printf("n - Exit ");

scanf("%c",&;c);

switch(c)

{ case '1': { system("cls"); Read(); printf("Information: "); PrintMas(); printf("OK!"); getch(); system("cls"); break; }

case '2': { system("cls"); bubble(n); printf("OK!"); getch(); system("cls"); break; }

case '3': { system("cls"); heapsort(10); printf("OK!");getch(); system("cls"); break; }

case '4': { system("cls"); PrintMas(); printf("OK!"); getch(); system("cls"); break; }

case '5': { system("cls"); Print(head); printf("OK!"); getch(); system("cls"); break; }

case '6': { system("cls"); PrintTree(root); printf("OK!");getch(); system("cls"); break; }

case '7': { system("cls"); root=NULL; for (i=0;i<n;i++){ avl(head->data, root); head=head->next;}

printf("OK!");getch(); system("cls"); break; }

case '8': { system("cls"); Addfrommas(); printf("OK!");getch(); system("cls"); break; }

case '9': { system("cls"); printf("Input number otdela.."); scanf("%d",&;nom); searsh(nom, root); getch();

system("cls"); break; }

case '10': { system("cls"); ShennonCode (Base,

"BASE2.dat",

"OutBase. dat"); printf(" OK"); getch();

system("cls"); break; }

} }

/*

//s1=s1->next;

// }

Read();

// PrintMas();

// heapsort(10);

bubble(10);

//system("cls");

// PrintMas();

Addfrommas();

// Print(head);

// struct spisok p1;

//p1=head;

// getch();

for (i=0;i<n;i++){ avl(head->data, root); head=head->next;}

// PrintTree(root);

while(nom!=) {

system("cls");

printf("Input number otdela.."); scanf("%d",&;nom);

searsh(nom, root); getch(); system("cls"); printf("one more or quit? (quit - '0')"); getch(); scanf("%d",&;nom);}

getch();

*/

return 0;

}

Похожие статьи




ОПИСАНИЕ ПОДПРОГРАММ - Структуры и алгоритмы обработки данных

Предыдущая | Следующая