Консультация № 186760
29.10.2012, 18:25
311.20 руб.
0 8 1
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

Прошу вас помочь написать программу - словарь: Описание задания

Реализацию КЧ-дерева нашел здесь: Реализация дерева

Язык любой (С/С++), но чем быстрее работает программа, тем лучше (почему-то на С++ некоторые программы не проходят time limit, а они же, реализованные на Си, проходят).

Заранее огромное спасибо откликнувшимся экспертам!

С уважением,

Иван.

Обсуждение

Неизвестный
29.10.2012, 18:26
общий
Структура - красно-черное дерево
давно
Посетитель
7438
7205
29.10.2012, 22:55
общий
Если никто не ответит раньше, то сделаю
Кстати, сообщения выводить на экран или в файл?
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
30.10.2012, 00:01
общий
Адресаты:
Спасибо Вам!

Сообщения выводить на экран
давно
Профессор
399103
482
05.11.2012, 09:55
общий
это ответ
Здравствуйте, Барс Иван!

В паре мест C++11 - возможно, для компиляции потребуется явно указать ключ, подобный -std=c++11 для gcc(-std=c++0x тоже соберёт).

Код:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

typedef unsigned long long uint64;

// Словарь, с которым работаем
map<string, uint64> dict;

// Вывод сообдения об ошибке
void err(const string & message)
{
cerr << "ERROR: " << message << "\n";
}

// Вывод обычного сообщения
void out(const string & str)
{
cout << str << "\n";
}

// Проверка, является си строка словом
// Считаем строку словом, если она содержит лишь символы A-Za-z
bool isWord(const string & str)
{
return find_if(str.begin(), str.end(), [](char c) { return !isalpha(c); }) == str.end();
}

// Является ли строка допустимым словом
// Т.е. не слишком длинным
bool isValidWord(const string & str)
{
return isWord(str) && str.length() <= 256;
}

// Сохранение словаря в файл
// Формат файла:
// тройки (L,W,V), где
// L - байт, содержащий длину слова(слова не более 256 символов)
// W - L байт - по байту на символ слова
// V - sizeof(unsigned long long) - 8 байт, содержащих значение, соответствующее слову
void save(const string & path)
{
ofstream file(path, ios::out | ios::binary | ios::trunc );
if (file.is_open())
{
for (const auto & pair : dict)
{
const string & key = pair.first;
unsigned char keyLen = key.length();
file.write(reinterpret_cast<const char *>(&keyLen), 1); // remember that key string is no more than 256 characters
file.write(key.data(), keyLen);

const uint64 & val = pair.second;
file.write(reinterpret_cast<const char *>(&val), sizeof(uint64));
}
file.close();
out("OK");
}
else
{
err("Unable to open file " + path + " for writing");
}
}

// Загрузка данных из файла

// Макрос проверки состояния файлового потока
#define CHECK_FS_GOOD(fs) if (!fs.good()) \
{ \
err("Bad file format"); \
fs.close(); \
return; \
}

void load(const string & path)
{
ifstream file(path, ios::in | ios::binary );
if (file.is_open())
{
vector<char> buf;
while (file.good())
{
unsigned char keyLen;
file.read(reinterpret_cast<char *>(&keyLen), 1);
// If EOF is after full data group it is OK.
if (file.eof())
{
break;
}
// But the other fails are not.
CHECK_FS_GOOD(file)

buf.reserve(keyLen+1); // one more character to a terminal symbol
file.read(buf.data(), keyLen);
CHECK_FS_GOOD(file)
buf[keyLen] = 0; // add a terminal symbol to the raw string data
string key(buf.data());

uint64 val;
file.read(reinterpret_cast<char *>(&val), sizeof(uint64));
CHECK_FS_GOOD(file)

//cout << "keyLen = " << (int)keyLen << "; key = " << key << "; val = " << val << "\n";

dict[key] = val;
}

file.close();
out("OK");
}
else
{
err("Unable to open file " + path + " for reading");
}
}

// Обработка команды

// Макрос проверки состояния строкового потока
#define CHECK_SS_GOOD(ss) if (!ss.good()) \
{ \
err("Invalid command"); \
return; \
}

// Макрос проверки строки
#define CHECK_WORD(word) if (!isValidWord(word)) \
{ \
err("String " + key + " is not valid"); \
return; \
}

// Преобразование символов строки в нижний регистр
void lowercase(string * str)
{
transform(str->begin(), str->end(), str->begin(), ::tolower);
}

void process(const string & command)
{
stringstream ss;
ss << command;

CHECK_SS_GOOD(ss)
string tok;
ss >> tok;
if (tok == "+")
{
CHECK_SS_GOOD(ss)
string key;
ss >> key;
// String validity check.
CHECK_WORD(key)
lowercase(&key);

CHECK_SS_GOOD(ss)
uint64 val;
ss >> val;

if (dict.count(key) == 0)
{
dict[key] = val;
out("OK");
}
else
{
out("Exist");
}
}
else if (tok == "-")
{
CHECK_SS_GOOD(ss)
string key;
ss >> key;
CHECK_WORD(key)
lowercase(&key);

if (dict.count(key) > 0)
{
dict.erase(key);
out("OK");
}
else
{
out("NoSuchWord");
}
}
else if (tok == "!")
{
CHECK_SS_GOOD(ss)
ss >> tok;
if (tok == "Save")
{
CHECK_SS_GOOD(ss)
string path;
ss >> path;

save(path);
}
else if (tok == "Load")
{
CHECK_SS_GOOD(ss)
string path;
ss >> path;

load(path);
}
else
{
err("Invalid command");
}
}
else if (isValidWord(tok))
{
lowercase(&tok);
if (dict.count(tok) > 0)
{
out("OK: " + dynamic_cast<std::ostringstream &>(std::ostringstream() << dict[tok]).str());
}
else
{
out("NoSuchWord");
}
}
else
{
err("Invalid command");
}
}

int main(int argc, char *argv[])
{
/*while (true)
{
string command;
getline(cin, command);
if (command == "exit") break;
process(command);
}*/

if (argc < 2)
{
cout << "Usage: my_cool_prog input_file" << endl;
return 1;
}

ifstream file(argv[1]);
if (file.is_open())
{
while (file.good())
{
string command;
getline(file, command);
process(command);
}
}
else
{
err("Unable to open file " + string(argv[1]) + " for reading");
}

return 0;
}



Путь к файлу команд - первый(и обязательный) аргумент командной строки.

Пример файла команд:
Код:

+ a 1
+ b 2
+ qwerty 512345678942
- b
qwerty
+ abc4 2
! Save database
- qwerty
qwerty
! Load database
qwerty
+ aBc 42
AbC


Соответствующий вывод:
Код:

OK
OK
OK
OK
OK: 512345678942
ERROR: String abc4 is not valid
OK
OK
NoSuchWord
OK
OK: 512345678942
OK
OK: 42
Неизвестный
05.11.2012, 12:48
общий
Александр, спасибо Вам большое за Ваш ответ, но не могли бы Вы приправить код некоторыми комментариями, а то разобраться очень тяжело
давно
Профессор
399103
482
05.11.2012, 16:20
общий
Хорошо. Скажите какие места вызывают затруднение, чтобы комментарии были там, где действительно надо.
Неизвестный
06.11.2012, 21:36
общий
Интересуют комментарии к функциям (за что отвечает каждая функция), а также в местах, требующих особого внимания (на Ваше усмотрение)
А также, скажите, пожалуйста, в какой среде Вы компилировали программу

Заранее спасибо!
давно
Профессор
399103
482
09.11.2012, 09:16
общий
Добавил описания функций. Я компилировал последним MinGW.
Форма ответа