close

Вход

Забыли?

вход по аккаунту

?

lr5

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра "Вычислительная техника"
Отчет
к лабораторной работе № 5
по курсу: "Теория компиляции"
Выполнили: студенты гр.09ВВ1
Алеева А.Р.
Клейменова А.С.
Проверил: Егоров В. Ю.
Пенза, 2013
Построение таблиц идентификаторов. Часть 2
Цель работы:
Ознакомление с методами построения таблиц идентификаторов. Изучение метода построения таблиц на основе хэш-функций.
Лабораторное задание:
На основе заданной хэш-функции рассчитать размер M таблицы адресов. Написать программу на языке C, создающую для данной хэш-функции таблицы идентификаторов. Входной поток идентификаторов следует получать с консоли, либо из текстового файла, используя в качестве разделителя символы перевода строки и возврата каретки. Необходимо также предусмотреть в программе функцию поиска заданного идентификатора.
Результатом выполнения лабораторной работы должен явиться исполняемый файл программы. Вариант задания - хэш-функция n=F(r):
2. n = H(r), где H - сумма по модулю 256 всех символов идентификатора.
Текст программы.
#include <conio.h>
#include <stdio.h>
#include <locale.h>
#include <string.h>
struct TableElement
{
TableElement *next;
char *Identif;
}table[255];
int hashFunction( char* szIdentifier)
{
long summa=0;
for(int i=0; i<strlen(szIdentifier); i++){
summa=summa+szIdentifier[i];
}
returnsumma % 256;
}
int _insert(char *strID)
{
TableElement *curElement;
intnStrLen = 0;
int retStrCmp = 0;
bool flagFind = false;
int address=0;
address= hashFunction(strID);
curElement = &table[address];
if(!curElement->Identif)
{
curElement->next = NULL;
nStrLen = strlen(strID) + 1;
curElement->Identif = new char[nStrLen];
strcpy(curElement->Identif, strID);
}
else
{
while(!flagFind)
{
retStrCmp = strcmp(curElement->Identif, strID);
if(!retStrCmp)
{
return 0;
}
else
{
if(curElement->next)
{
curElement = curElement->next; }
else
{
curElement->next = new TableElement;
curElement->next->next = NULL;
nStrLen = strlen(strID) + 1;
curElement->next->Identif = new char[nStrLen];
strcpy(curElement->next->Identif, strID);
flagFind = true;
}
}
} //while()
}
return 1;
}
int _lookup(char *strID)
{
TableElement *curElement;
int retStrCmp = 0;
int address=0;
address= hashFunction(strID);
curElement = &table[address];
if(!curElement->Identif)
{
return 0;
}
else
{
while(true)
{
retStrCmp = strcmp(curElement->Identif, strID);
if(!retStrCmp)
{
return 1;
}
else
{
if(curElement->next)
{
curElement = curElement->next; }
else
{
return 0;
}
}
} //while()
}
}
void printT(TableElement *p){
TableElement currentElement;
// вывод таблицы на экран
for(int i=0; i<255; i++){
if(p[i].Identif){
printf("%d. %s", i+1, p[i].Identif);
currentElement = p[i];
while(currentElement.next){
printf("->%s", currentElement.next->Identif);
currentElement = *currentElement.next;
}
printf("\n");
}
else{
printf("%d. \n", i+1);
}
}
}
void main()
{
setlocale(LC_ALL, "Rus");
char *buf;
bool end=false;
while(1){
buf = new char[];
printf("Введите команду: ");
scanf("%s", buf);
if(strcmp(buf,"add")==0){
printf("Введите строку: ");
scanf("%s", buf);
if(_insert(buf))
{
printf("В таблицу добавлен элемент - %s\n", buf);
}
}else{
if(strcmp(buf,"find")==0){
printf("Введите элемент для поиска: ");
scanf("%s", buf);
if(_lookup(buf))
{
printf("Элемент найден!\n");
}
else
{
printf("Элемент не найден!\n");
}
}else{
if(strcmp(buf,"print")==0){
printT(table);
}else{
printf("Неверная команда\n");
}
}
}
}
getch();
}
Результат работы программы
Рисунок 1- результат работы программы
Рисунок 2- результат работы программы
Вывод: в результате выполнения данной лабораторной работы были изучены методы построения таблиц идентификаторов и методы построения таблиц на основе хэш-функций.
2
Документ
Категория
Рефераты
Просмотров
18
Размер файла
77 Кб
Теги
lr5
1/--страниц
Пожаловаться на содержимое документа