русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Прямой доступ и хеширования

Типовое задание

В файле записаны фамилии студентов. Для содержимого файла создать хэш-таблицу на 10 элементов с распределенными цепочками переполнения (в списки записывать фамилии - синонимы). Функция хеширования определяется как:
Адрес = ? (Код) i mod 10
где: ? (Код) i - сумма кодов всех букв фамилии,
mod - остаток от целочисленного деления.
Проверить работоспособность хэш-таблиц. Результаты выдать на экран.
ВЫХОДНЫЕ МОДУЛИ.
1). Файл с фамилиями

Pihtin .
Gavruk
Kovalenko
Popa
Semenuk
Kosenko
Yankovoy
Petrov
Ponomarenko
Panteleymonov
Sidorov
Lyashenko
Konashevich
Storogenko
Storogenko
Panin
Maslov
Ivanov
Ermolenko
Kolugniy

 

2). Файл с описанием ФУНКЦИЙ.

#define RAZM 10 // Размер хеш-таблицы
struct Stud
{char name [20]; // Фамилия студента
Stud *next; // Указатель на следующее фамилия
Stud *prev; // Указатель на предыдущую фамилию
Stud *beg; // Указатель на начало списка
Stud *curr; // Указатель на текущее фамилия
};
Stud *st;
Stud *p [RAZM]; / / Хеш-таблица
int Build (int position, char *str); // Создание элемента списка для данного фамилии str
void Del (); // Удаление фамилии из списка
void First (); // Инициализация хеш-таблицы
void Insert (); // Вставки фамилии в хэш-таблицу
int Kesh (char *str); / / Распределение фамилий по спискам
void Show (); // Выдача списков на экран
void Search (); / Поиск фамилии в списке
void Death (); // Уничтожение списков
void Menu (); // Выдача меню
void Update_File (); // Замена входного файла в соответствии с изменениями

 

3). ГЛАВНЫЙ МОДУЛЬ.
/ * Открывается файл, для каждой фамилии исчисляется позиция в хешованому списке записывается в список, выдается результат на экран и переход к меню. * /

 

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <string.h>
#include "func.h"
#include "do.cpp"
           
void main(void)
            {            FILE *f;
                          char *string="\0";
                          int pos=0;
                          clrscr();
                          First();
                          if((f=fopen("kesh.txt","rt"))==NULL)
                        {             cout<<"Error reading input file\n";
                                      getch();
                                      exit(1);
                         }
                                     while(!feof(f))
                                     {                    fgets(string,20,f);
                                                            if(string[strlen(string)-1]=='\n')
                                                            string[strlen(string)-1]='\0';
                                                            pos=Kesh(string);
                                                            Build(pos,string);
                                     }
                                    fclose(f);
                                    Show();
                                    Menu();
                                    Death();
                                    getch();
                        }

4). МОДУЛЬ, содержащий функции для реализации всех вышеуказанных действий.

int Kesh(char *str)
{          int i,kesh=0,size=0;
for(i=0;i<(strlen(str)-2);i++)            
size+=(int)str[i];                              //суммируем все коды строки
kesh=size%RAZM;                        //Значение хэш-функции
return kesh;
}

void First()
{          for(int i=0;i<RAZM;i++)
p[i]=NULL;                // инициализация массива указателей на списки
}
int Build(int position, char *str)
{          Stud *pt,*nw,*nxt;
int kol=0;
pt=new Stud;
if(!pt)
{         cout<<"Error"<<endl;
getch();
exit(1);
}
nw=p[position];                                // выделение памяти под новый элемент
if(!nw)
{         p[position]=pt;
p[position]->next=NULL;
p[position]->curr=pt;
}
else
{       pt->next=p[position]->curr;
p[position]->curr->prev=pt;
p[position]->curr=pt;
}
strcpy(p[position]->curr->name,str);  //занесение в элемент
return 0;
}
void Insert()
{          Stud *pt;
char *ss;
int pos;
setmem(ss,1,'\0');
scanf("%s",ss);          // фамилия, которая вставляется в список
pos=Kesh(ss);           // вычисления хэш-функции для данного фамилии
Build(pos,ss);            // вставка фамилии в список
cout<<"\nString inserted in "<<pos<<" position\n";
delay(1000);
}
void Del()
{                      int pos;
char *s;
Stud *pt,*pt1=NULL,*pt2=NULL;
scanf("%s",s);
pos=Kesh(s);
pt=p[pos]->curr;
pt1=pt;
while((strcmp(pt->name,s))&&(pt))
pt=pt->next;              // Удаление первого
if((pt1= =pt)&&(pt))
{          pt1=pt->next;
delete pt;
p[pos]->curr=pt1;
p[pos]->curr->prev=NULL;
}                    //Элемент не найден
if(!pt)
{            cout<<"This string is absent\n";
getch();
return;
}                     // Последний элемент
if(!pt->next)
{            Stud *temp;
Stud *temp1 = p[pos]->curr;
temp = p[pos];
p[pos] = temp->prev;
delete temp;
p[pos]->next = 0;
p[pos]->curr = temp1;
}                      // Элемент в середине
else
{          pt1=pt->prev;
pt2=pt->next;
pt1->next=pt2;
delete pt;
}
}
void Show()
{          Stud *ptr;
int len,o;
for(int i=0;i<RAZM;i++)
{          ptr=p[i];
cout<<"Segment "<<i<<" ";
if(ptr)
{            ptr=p[i]->curr;
while(ptr)
{                     cout<<" "<<ptr->name<<" ";
ptr=ptr->next;
}
}
cout<<"\n";
}
}
void Search()
{            Stud *ptr;
int pos;
char *str;
cout<<"\nInput string\n";
gets(str);                               // строка, вводимого
pos=Kesh(str);                      // вычисление номера списка фамилии
ptr=p[pos]->curr;
if(ptr)
{            while((strcmp(ptr->name,str))&&(ptr))
ptr=ptr->next;
if(ptr)
{        cout<<" is present on "<<pos<<" string\n";
return;
}  else
{       cout<<str<<"  is absent\n";
return;
}
}
}
void Death()
{          Stud *ptr;
for(int i=0;i<RAZM;i++)
{   ptr=p[i]->curr;
while(ptr)
{       ptr=ptr->next;
delete p[i]->curr;
p[i]->curr=ptr;
}
}
}
void Update_File()
{          Stud *ptr;
int len,o,i;
char c;
FILE *f;
cout<<"Do you realy want to Update input File (y/n)\n";
c=getch();
if(c= ='n')
return;
if(c=='y')
{           if((f=fopen("kesh.txt","w+t"))==NULL)
{            cout<<"Error writing          input file\n";
getch();
exit(1);
}
for(i=0;i<RAZM;i++)
{            ptr=p[i];
if(ptr)
{            ptr=p[i]->curr;
while(ptr)
{         fputs(ptr->name,f);
fputs("\n",f);
ptr=ptr->next;
}
}
}
fclose(f);
}          else
return;
}
void Menu()
{            char c;
do
{         cout<<"\n"<<"Input need number\n";
cout<<"1 - Search\n";
cout<<"2 - Insert\n";
cout<<"3 - Delete\n";
cout<<"4 - Show\n";
cout<<"5 - Update file\n";
cout<<"6 - Exit\n";
c=getche();
switch(c)
{
case '1': Search();clrscr();Show();break;
case '2':  printf("\nInput string for insert\n");Insert();clrscr();Show();break;
case '3': printf("\nInput string for delete\n");Del();clrscr();Show();break;
case '4': clrscr();Show();break;
case '5': clrscr();Update_File();break;
case '6': return;cout<<"\nExit";break;
default: cout<<" - Error of input";getch();clrscr();Show();
}
}while(c!=28);
}

Просмотров: 15634

Вернуться в оглавление:Cтруктура и организация данных




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.