RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 186114: Здравствуйте! У меня возникли сложности с таким вопросом: Написать программу для работы с перемешанной таблицей, использующей перемешивание сцеплением, по запросу оператора. Перемешанная таблица представлена массивом указателей на элементы таблицы, имеющие следующую структуру: struct Item{ int key; /* ключ элемента char *info; /*указ... Здравствуйте! У меня возникли сложности с таким вопросом:
Дата отправки: 20.05.2012, 17:05 Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, ШмонинЕА! Код : #include <locale>
#include <iostream>
using namespace std;
void AddElement(void);
void DelElement(void);
void SearchRange(void);
void OutTable(void);
void Exit(void);
int GetNum(void);
const int SIZE = 10;
typedef struct Item
{
int key; //ключ элемента
char *info; //указатель на информацию
Item *next; //указатель на след. элемент
}ITEM;
char *mesMain[] = //сообщения меню
{
"Включить новый элемент",
"Удалить элемент",
"Найти элемент из диапозона ключей",
"Вывести таблицу",
"Выход"
};
//количество пунктов меню
int MesMainCount = sizeof( mesMain ) / sizeof( mesMain[0] );
//функции отработки пунктов меню
void ( *funcMain[] )()={AddElement,
DelElement,
SearchRange,
OutTable,
Exit};
ITEM *table[SIZE]; //таблица-вектор
//Поиск элемента и места, куда вставить
//Вызывается при добавлении нового элемента
//параметры: ключ и адрес указателя в цепочке next, куда додавим новый элемент
//или NULL, если цепочка пуста
//возвращает true, если элемент найден и false, если не найден
bool Find(int num, ITEM **ppItem)
{
ITEM *pItem;
int i = num%SIZE; //функция расстановки - остаток от деления на SIZE=10
//результат - производный ключ
//найдем, есть ли уже заданный ключ
//*ppItem в итоге будет указывать на предыдущий последний элемент,
//после которого мы вставим новый
for (*ppItem=NULL,pItem=table[i]; pItem!=NULL; pItem=pItem->next)
{
*ppItem = pItem; //возвращаем указатель предыдущего последнего
//ищем искомый ключ
if (pItem->key == num) //ключ равен!
return true; //выходим
}
return false; //не нашли, в *ppItem будет указатель последнего (или NULL)
}
//Поиск по всей таблице элементов с ключом в заданном интервале [min, max]
//Для первого вызова необходимо задать *idx = -1
//После каждого вызова по этим адресам будут возвращаться индекс в таблице и адрес
//удовлетворяющего условию элемента.
//Повторный вызов будет продолжен с того же места.
//Т.о., можно найти все элементы в цикле
bool FindRange(int min, int max, int *idx, ITEM **ppItem)
{
ITEM *pItem;
int i;
if (min > max) //на всякий случай, проверим min < max
{
i = min;
min = max;
max = i;
}
if (*idx == -1) //первый вызов?
{
i = 0; //начинаем с 0-го индекса
pItem=table[0];
}
else //продолжение поиска
{
i = *idx; //индекс
pItem = (*ppItem)->next; //следующий за обработанным!
}
while (i<SIZE) //по всей таблице
{
for(; pItem; pItem=pItem->next) //по элементам одной цепочки
{
//проверяем условие попадания ключа в интервал
if ((pItem->key >= min) && (pItem->key <= max))
{ //попал
*idx = i; //сохраняем индекс
*ppItem = pItem; //и указатель на элемент
return true; //нашли!
}
}
pItem=table[++i]; //на первый элемент следующей цепочки
//для последней будет несуществующий адрес
//но мы выйдем по while(i<SIZE) !
}
return false; //больше нет
}
//добавление элемента в таблицу
void AddElement()
{
int num; //индекс нового элемента
char str[80];
ITEM *pItem; //указатель на текущий элемент
ITEM *pItemPrev; //указатель на элемент, после которого вставим
cout << "Введите ключ элемента: ";
num = GetNum(); //вводим ключ
if(Find(num, &pItemPrev))
{
cout << "Элемент с таким ключем уже есть" << endl;
return;
}
pItem = new ITEM; //создаем новый элемент
//заполняем поля
pItem->key = num; //ключ
pItem->next = NULL; //признак последнего элемента в цепочке
cout << "Введите строку: ";
cin.ignore();
cin.getline(str, 80);
pItem->info = new char[strlen(str)+1];
strcpy(pItem->info, str); //добавляем строку
//определимся со ссылкой на наш элемент
if (pItemPrev != NULL) //если вставляется не в начало цепочки
pItemPrev->next = pItem; //то предыдущий будет на него ссылаться
else
table[num%SIZE] = pItem; //если первый элемент, то запоминаем ссылку в массиве table
cout << "Элемент добавлен" << endl;
}
//поиск элементов из интервала ключей
void SearchRange()
{
int i = -1; //для поиска с начала таблицы
ITEM *pItem;
int count, min, max;
cout << "Введите минимальный ключ диапозона: ";
min = GetNum(); //вводим ключ
cout << "Введите максимальный ключ диапозона: ";
max = GetNum(); //вводим ключ
count = 0; //посчитаем, чтобы определить нашли или нет
while (FindRange(min, max, &i, &pItem))
{ //выводим
cout << "key = " << pItem->key //ключ
<< ", info = " << pItem->info //строка
<< endl;
count++; //считаем
}
if (0==count) //выведем сообщение, если не нашли
cout << "Элементы не найдены" << endl;
}
//удаление элемента с заданным ключем
void DelElement()
{
int i, num;
ITEM *pItemPrev, *pItem, *pItemNext;
cout << "Введите ключ элемента: ";
num = GetNum(); //вводим ключ
i = num%SIZE; //функция расстановки - остаток от деления на SIZE=10
//результат - производный ключ
//по всем элементам цепочки для производного ключа
for (pItemPrev=NULL,pItem=table[i]; pItem; pItem=pItemNext)
{
pItemNext = pItem->next; //указатель на следующего
//сравниваем ключ
if (pItem->key == num)
{ //выкинем элемент из цепочки указателей
if (pItemPrev == NULL) //первый элемент в цепочке?
table[i] = pItemNext; //пишем в массив table адрес следующего
else //иначе, предыдущий ссылается
pItemPrev->next = pItemNext; //на следующего
delete [] pItem->info; //удаляем строку
delete pItem; //и сам элемент
cout << "Элемент удален" << endl;
return;
}
pItemPrev=pItem; //сдвигаем указатель на предыдущий элемент
}
//прошли всю цепочку, значит не нашли
cout << "Элемент не найден" << endl;
}
//вывод всей таблицы
void OutTable()
{
int i, count = 0; //посчитаем число элементов
ITEM *pItem;
for(i=0; i<SIZE; i++) //по всем элементам таблицы
{
//по всем элементам цепочек
for (pItem = table[i]; pItem; pItem=pItem->next)
{
cout << "key = " << pItem->key
<< ", info = " << pItem->info
<< endl;
count++;
}
}
if (0 == count) //сообщение для пустой таблицы
cout << "Таблица пуста" << endl;
}
//выход, удалим все элементы
void Exit()
{
ITEM *pItem, *pItemNext;
for (int i=0; i<SIZE; i++)
{
for (pItem=table[i]; pItem; pItem=pItemNext)
{
pItemNext = pItem->next; //запомним уазатель на следующего
delete [] pItem->info; //удаляем текущего
delete pItem;
}
}
}
//ввод числа
int GetNum()
{
int a;
cin >> a;
while ( !( cin.good() || cin.eof() ) || ( a < 0 ) )
{
cout << "Введите число! " << endl;
cin.clear();
cin.ignore();
cin >> a;
}
return a;
}
//показ меню с вводом номера строки
int ViewMenu(char** mes, int max)
{
int ret;
do
{
//меню
for ( int i = 0; i < max; i++ )
cout << i+1 << ". " << mes[i] << endl;
cout << "Ваш выбор: ";
//вводим число
ret = GetNum();
}
//проверим на допустимость
while ( ret < 1 || ret > max );
//вернем номер строки
return ret;
}
int main()
{
int ret;
system("chcp 1251 >> nul");
// locale::global(locale("Russian_Russia.866")); //чтобы писалось по-русски
do
{
ret = ViewMenu(mesMain, MesMainCount); //выводим меню, вводим номер строки
funcMain[ret-1](); //отрабатываем пункт меню
cout << "--------------------------------" << endl;
if (ret == MesMainCount) //последняя - выход
break;
}
while ( ret );
return 0;
}б) Код : #include <locale>
#include <iostream>
using namespace std;
void ReadTableFromFile(void);
void WriteTableToFile(void);
void AddElement(void);
void DelElement(void);
void SearchRange(void);
void OutTable(void);
void Exit(void);
int GetNum(void);
const int SIZE = 10;
typedef struct Item
{
int key; //ключ элемента
int seek; //смещение поля info относительно начала строк в файле
int len; //длина info
Item *next; //указатель на след. элемент
}ITEM;
char *mesMain[] = //сообщения меню
{
"Включить новый элемент",
"Удалить элемент",
"Найти элементы из диапозона ключей",
"Вывести таблицу",
"Выход"
};
//количество пунктов меню
int MesMainCount = sizeof( mesMain ) / sizeof( mesMain[0] );
//функции отработки пунктов меню
void ( *funcMain[] )()={AddElement,
DelElement,
SearchRange,
OutTable,
Exit};
int StringsOff; //начало строк в файле
ITEM *table[SIZE]; //таблица-вектор
FILE *file = NULL; //указатель на открытый файл
char fName[256];
//чтение таблицы из файла
//формат файла:
//int StringsOff - начало строк в файле
//ITEM *table[SIZE] - таблица (вся), после каждого элемента цепочка элементов
//... - строки info
void ReadTableFromFile()
{
int i;
ITEM *pItem, *pItemPrev;
cout << "Введите имя файла: ";
cin.getline(fName, 256); //вводим имя файла
file = fopen(fName, "r+b"); //открываем на чтение/запись, тип двоичный
if (NULL == file) //если нет такого
{
file = fopen(fName, "w+b"); //то создаем новый файл
if (file) //создался?
{ //запишем файл с пустой таблицей
//смещение строк равно сумме длин всех указателей
//и самого поля смещения
StringsOff = sizeof(ITEM*) * SIZE + sizeof(int);
//пишем смещение блока строк в файле
fwrite(&StringsOff, sizeof(int), 1, file);
//нулевой массив указателей
fwrite(table, sizeof(ITEM*), SIZE, file);
}
else
cout << "Ошибка создания файла" << endl;
}
else //файл есть
{ //читаем смещение блока строк в файле
fread(&StringsOff, sizeof(int), 1, file);
for (i=0; i<SIZE; i++) //читаем элементы таблицы
{ //читаем указатель в таблице
fread(&pItem, sizeof(ITEM*), 1, file);
if (pItem) //ненулевой - дальше будут элементы!
{
while(pItem) //читаем цепочку элементов, пока указатель ненулевой
{
pItem = new(ITEM); //создаем элемент
if (table[i] == NULL) //первый?
table[i] = pItem; //записываем указатель в таблицу
else //непервый - делаем ссылку у предыдущего на текущего
pItemPrev->next = pItem;
//читаем с файла элемент
fread(pItem, sizeof(ITEM), 1, file);
pItemPrev = pItem; //запоминаем текущего, как нового предыдущего
pItem=pItem->next; //у последнего в цепочке здесь будет нуль
}
}
else //нулевой - элементов нет!
table[i] = NULL;
}
}
fclose(file); //файл закрываем
}
//запись таблицы в файл (в конце работы)
void WriteTableToFile()
{
ITEM *pItem;
int i, len;
fpos_t pos; //позиция в файле
void *pStrings; //адрес буфера для чтения массива строк
if (fName[0]) //проверим на наличие имени файла
{
file = fopen(fName, "r+b"); //открываем на чтение/запись
if (file) //открылся?
{
//прочитаем массив строк из файла
//определим длину файла
fseek(file, 0, SEEK_END); //в конец файла
fgetpos(file, &pos); //определяем позицию
fseek(file, StringsOff, SEEK_SET); //в начало массива строк!
len = (int)pos - StringsOff; //длина массива строк
pStrings = malloc(len); //выделим память под массив строк
fread(pStrings, len, 1, file); //прочитаем
fseek(file, 0, SEEK_SET); //позицию в начало файла!
//формируем файл!
fwrite(&StringsOff, sizeof(int), 1, file); //начало массива строк
//выводим таблицу
for (i=0; i<SIZE; i++)
{
//указатель начала цепочки (или 0)
fwrite(&table[i], sizeof(ITEM*), 1, file);
//выводим структуры цепочек
for (pItem=table[i]; pItem; pItem=pItem->next)
fwrite(pItem, sizeof(ITEM), 1, file);
}
//запишем массив строк и подправим новое смещение массива строк!
StringsOff = ftell(file); //равно позиции после записи таблицы
fwrite(pStrings, len, 1, file); //пишем сохраненный массив строк
fseek(file, 0, SEEK_SET); //в начало файла!
fwrite(&StringsOff, sizeof(int), 1, file); //и пишем новое смещение массива строк
fclose(file); //файл закрываем
free(pStrings); //освобождаем память под строки
}
else
cout << "Ошибка открытия файла" << endl;
}
else
cout << "Имя файла не задано" << endl;
}
//Поиск элемента и места, куда вставить
//Вызывается при добавлении нового элемента
//параметры: ключ и адрес указателя в цепочке next, куда додавим новый элемент
//или NULL, если цепочка пуста
//возвращает true, если элемент найден и false, если не найден
bool Find(int num, ITEM **ppItem)
{
ITEM *pItem;
int i = num%SIZE; //функция расстановки - остаток от деления на SIZE=10
//результат - производный ключ
//найдем, есть ли уже заданный ключ
//*ppItem в итоге будет указывать на предыдущий последний элемент,
//после которого мы вставим новый
for (*ppItem=NULL,pItem=table[i]; pItem!=NULL; pItem=pItem->next)
{
*ppItem = pItem; //возвращаем указатель предыдущего последнего
//ищем искомый ключ
if (pItem->key == num) //ключ равен!
return true; //выходим
}
return false; //не нашли, в *ppItem будет указатель последнего (или NULL)
}
//Поиск по всей таблице элементов с ключом в заданном интервале [min, max]
//Для первого вызова необходимо задать *idx = -1
//После каждого вызова по этим адресам будут возвращаться индекс в таблице и адрес
//удовлетворяющего условию элемента.
//Повторный вызов будет продолжен с того же места.
//Т.о., можно найти все элементы в цикле
bool FindRange(int min, int max, int *idx, ITEM **ppItem)
{
ITEM *pItem;
int i;
if (min > max) //на всякий случай, проверим min < max
{
i = min;
min = max;
max = i;
}
if (*idx == -1) //первый вызов?
{
i = 0; //начинаем с 0-го индекса
pItem=table[0];
}
else //продолжение поиска
{
i = *idx; //индекс
pItem = (*ppItem)->next; //следующий за обработанным!
}
while (i<SIZE) //по всей таблице
{
for(; pItem; pItem=pItem->next) //по элементам одной цепочки
{
//проверяем условие попадания ключа в интервал
if ((pItem->key >= min) && (pItem->key <= max))
{ //попал
*idx = i; //сохраняем индекс
*ppItem = pItem; //и указатель на элемент
return true; //нашли!
}
}
pItem=table[++i]; //на первый элемент следующей цепочки
//для последней будет несуществующий адрес
//но мы выйдем по while(i<SIZE) !
}
return false; //больше нет
}
//добавление элемента в таблицу
void AddElement()
{
int num; //индекс нового элемента
char str[80];
ITEM *pItem; //указатель на текущий элемент
ITEM *pItemPrev; //указатель на элемент, после которого вставим
cout << "Введите ключ элемента: ";
num = GetNum(); //вводим ключ
if(Find(num, &pItemPrev))
{
cout << "Элемент с таким ключем уже есть" << endl;
return;
}
pItem = new ITEM; //создаем новый элемент
//заполняем поля
pItem->key = num; //ключ
pItem->next = NULL; //признак последнего элемента в цепочке
cout << "Введите строку: ";
cin.ignore();
cin.getline(str, 80);
if (fName[0]) //проверим на наличие имени файла
{
file = fopen(fName, "r+b"); //открываем
if (file) //открылся?
{
//определим смещение строки в массиве строк
fseek(file, 0, SEEK_END); //становимся в конец файла
pItem->seek = ftell(file)-StringsOff; //запоминаем позицию, как
// смещение в массиве строк поля info
pItem->len = strlen(str)+1; //запоминаем длину строки
fwrite(str, pItem->len, 1, file); //и пишем строку в конец файла
fclose(file); //закрываем файл
//определимся со ссылкой на наш элемент
if (pItemPrev != NULL) //если вставляется не в начало цепочки
pItemPrev->next = pItem; //то предыдущий будет на него ссылаться
else
table[num%SIZE] = pItem; //если первый элемент, то запоминаем ссылку в массиве table
cout << "Элемент добавлен" << endl;
}
else
cout << "Ошибка открытия файла" << endl;
}
else
cout << "Имя файла не задано" << endl;
}
//поиск элемента всех версий
//поиск элементов из интервала ключей
void SearchRange()
{
int i = -1; //для поиска с начала таблицы
ITEM *pItem;
int count, min, max;
char str[80];
cout << "Введите минимальный ключ диапозона: ";
min = GetNum(); //вводим ключ
cout << "Введите максимальный ключ диапозона: ";
max = GetNum(); //вводим ключ
count = 0; //посчитаем, чтобы определить нашли или нет
if (fName[0]) //имя файла задано?
{
file = fopen(fName, "r+b"); //открываем файл
if (file) //открылся?
{
while (FindRange(min, max, &i, &pItem))
{
fseek(file, pItem->seek+StringsOff, SEEK_SET); //становимся в позицию, где начинается строка
fread(str, pItem->len, 1, file); //читаем нужное число байт
//выводим
cout << "key = " << pItem->key //ключ
<< ", info = " << str //строка
<< endl;
count++; //считаем
}
fclose(file); //файл закрываем
}
else
cout << "Ошибка открытия файла" << endl;
}
else
cout << "Имя файла не задано" << endl;
if (0==count) //выведем сообщение, если не нашли
cout << "Элементы не найдены" << endl;
}
//удаление элемента с заданным ключем
//файл не используется.
//удаление происходит только в памяти!
void DelElement()
{
int i, num;
ITEM *pItemPrev, *pItem, *pItemNext;
cout << "Введите ключ элемента: ";
num = GetNum(); //вводим ключ
i = num%SIZE; //функция расстановки - остаток от деления на SIZE=10
//результат - производный ключ
//по всем элементам цепочки для производного ключа
for (pItemPrev=NULL,pItem=table[i]; pItem; pItem=pItemNext)
{
pItemNext = pItem->next; //указатель на следующего
//сравниваем ключ
if (pItem->key == num)
{ //выкинем элемент из цепочки указателей
if (pItemPrev == NULL) //первый элемент в цепочке?
table[i] = pItemNext; //пишем в массив table адрес следующего
else //иначе, предыдущий ссылается
pItemPrev->next = pItemNext; //на следующего
delete pItem; //удаляем элемент
cout << "Элемент удален" << endl;
return;
}
pItemPrev=pItem; //сдвигаем указатель на предыдущий элемент
}
//прошли всю цепочку, значит не нашли
cout << "Элемент не найден" << endl;
}
//вывод всей таблицы
void OutTable()
{
int i, count = 0; //посчитаем число элементов
ITEM *pItem;
char str[80];
if (fName[0]) //имя файла задано?
{
file = fopen(fName, "r+b"); //открываем файл
if (file) //открылся?
{
for(i=0; i<SIZE; i++) //по всем элементам таблицы
{
//по всем элементам цепочек
for (pItem = table[i]; pItem; pItem=pItem->next)
{
fseek(file, pItem->seek+StringsOff, SEEK_SET); //становимся в позицию, где начинается строка
fread(str, pItem->len, 1, file); //читаем нужное число байт
cout << "key = " << pItem->key
<< ", info = " << str
<< endl;
count++;
}
}
fclose(file); //файл закрываем
}
else
cout << "Ошибка открытия файла" << endl;
}
else
cout << "Имя файла не задано" << endl;
if (0 == count) //сообщение для пустой таблицы
cout << "Таблица пуста" << endl;
}
//выход, удалим все элементы
void Exit()
{
ITEM *pItem, *pItemNext;
WriteTableToFile(); //сохраним таблицу в файле
//удалим элементы таблицы со всеми цепочками
for (int i=0; i<SIZE; i++)
{
for (pItem=table[i]; pItem; pItem=pItemNext)
{
pItemNext = pItem->next; //запомним уазатель на следующего
delete pItem;
}
}
}
//ввод числа
int GetNum()
{
int a;
cin >> a;
while ( !( cin.good() || cin.eof() ) || ( a < 0 ) )
{
cout << "Введите число! " << endl;
cin.clear();
cin.ignore();
cin >> a;
}
return a;
}
//показ меню с вводом номера строки
int ViewMenu(char** mes, int max)
{
int ret;
do
{
//меню
for ( int i = 0; i < max; i++ )
cout << i+1 << ". " << mes[i] << endl;
cout << "Ваш выбор: ";
//вводим число
ret = GetNum();
}
//проверим на допустимость
while ( ret < 1 || ret > max );
//вернем номер строки
return ret;
}
int main()
{
int ret;
system("chcp 1251 >> nul");
// locale::global(locale("Russian_Russia.866")); //чтобы писалось по-русски
ReadTableFromFile(); //читаем таблицу из файла (или создаем новый)
do
{
ret = ViewMenu(mesMain, MesMainCount); //выводим меню, вводим номер строки
funcMain[ret-1](); //отрабатываем пункт меню
cout << "--------------------------------" << endl;
if (ret == MesMainCount) //последняя - выход
break;
}
while ( ret );
return 0;
}
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
