ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / K&R 6.3 Решение приведённой задачи. Вопросы по реализации
16 сообщений из 16, страница 1 из 1
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38605971
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
В главе 6.3 K&R предлагается разобрать решение следующей задачи(своими словами, ибо распечатанный вариант книги на работе, а pdf-варианта сейчас нет):

У нас есть keyword языка C, такие как fe : {else,if,then, ..., smth_else}.
У нас есть какой-то текст.
Задача: Найти число вхождений каждого слова из keyword в данном тексте.

Прочитал первую страницу, и дальше решил делать сам. Понял для чего нужны в данном случае (и видимо вообще) структуры.

Данные предлагают хранить следующим образом:
Код: plaintext
1.
2.
3.
4.
5.
struct keyword
{
char* name;
int count;
} word[]={"if",0,"else",0,"then",0};



Окей, пусть будем хранить так, хотя я не уверен что это моветон хранить подобным образом массив word (ведь я явным образом не указываю размерность массива, хоть K&R и говорит, что компилятор сам определит размерность и переживать не стоит).

Решать эту задачу я решил в лоб. Для начала в лоб, а потом буду пытаться улучшить алгоритм. При решение в лоб я делаю цикл между каждым отдельно взятым словом из char* buf cо всеми word.name(1 слова из char* buf на n слов word.name). И вот этим то и проблема, я не знаю как его сделать, ведь мне неизвестна размерность массива. Могу конечно определить сколько выделено байт на массив, и исходя из этого рассчитать размерность. Но не хочу так.
Подскажите как лучше сделать ?
...
Рейтинг: 0 / 0
05.04.2014, 09:15
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38605973
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petalvik
Участник
SashaMercury,

в конце каждой строки (массива char'ов) будет символ \0. Следовательно, идём в цикле по строке, пока не встретится ноль.
...
Рейтинг: 0 / 0
05.04.2014, 09:32
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38605975
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryИ вот этим то и проблема, я не знаю как его сделать, ведь мне неизвестна размерность массива. Могу конечно определить сколько выделено байт на массив, и исходя из этого рассчитать размерность. Но не хочу так.
Подскажите как лучше сделать ?

Код: plaintext
1.
elem_count = sizeof(words) / sizeof(words[0]); // words - массив
...
Рейтинг: 0 / 0
05.04.2014, 09:41
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606017
smald
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
smald
Участник
SashaMercury

Где такие простые задачки задают?
Лучше реализуйте ls -l, полезнее для развития.
...
Рейтинг: 0 / 0
05.04.2014, 11:37
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606020
smald
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
smald
Участник
SashaMercury
А вообще Вам или сюда или сюда
...
Рейтинг: 0 / 0
05.04.2014, 11:42
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606121
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly Moskovsky, а количество байт выделенных для каждого words будет одинаковым ? Слова ведь разной длины. Или произойдет выравнивание по максимуму ?
...
Рейтинг: 0 / 0
05.04.2014, 15:58
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606130
-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
-
Гость
SashaMercuryAnatoly Moskovsky, а количество байт выделенных для каждого words будет одинаковым ? Слова ведь разной длины. Или произойдет выравнивание по максимуму ?

Конечно, там же указатель.
...
Рейтинг: 0 / 0
05.04.2014, 16:12
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606132
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
То есть у меня будет 100 элементов в массиве структур, и в 99 максимум будет три символа, а в одном 10 символов в с концом строки, и в итоге я потрачу 1000 байт для хранения этого массива ?
...
Рейтинг: 0 / 0
05.04.2014, 16:21
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606134
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryТо есть у меня будет 100 элементов в массиве структур, и в 99 максимум будет три символа, а в одном 10 символов в с концом строки, и в итоге я потрачу 1000 байт для хранения этого массива ?
Нет, вы не поняли.
Размер элементов одинаковый не потому что выравниваются по размеру строк, а потому что в массиве хранятся не сами строки, а указатели на них. А указатели все одного размера.
...
Рейтинг: 0 / 0
05.04.2014, 16:31
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606135
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Да и вообще массив - это по определению коллекция из одинаковых элементов :)
...
Рейтинг: 0 / 0
05.04.2014, 16:33
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606138
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Балбес:( ну конечно вы правы, только адрес хранится ! Понял, спасибо C:
...
Рейтинг: 0 / 0
05.04.2014, 16:41
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606622
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
smaldГде такие простые задачки задают?

SashaMercuryВ главе 6.3 K&R ...
...
Рейтинг: 0 / 0
06.04.2014, 20:34
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606788
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Сегодня решил эту задачу, потратил около 60 минут, с учётом исправления ошибок. Это много, но лучше чем раньше. Плохо что целый месяц не занимался конечно. Проверьте пожалуйста

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
//count C keywords
#include "stdafx.h"

//Функция сравнивает "C строку" с открытым диапазоном [s_w2,e_w2)
bool compare2w(const char* w1, const char* s_w2, const char* e_w2)
{
	while (*w1 == *s_w2)
	{
		if (*(w1+1) == '\0' && e_w2-1 == s_w2) return true;
		w1++;
		s_w2++;
	}
	return false;
}
struct key
{
	char* word;
	int count;
} tab[] = { "break", 0, "case", 0, "char", 0, "continue", 0, "default", 0, "unsigned", 0, "while", 0 , "if", 0 };


int _tmain(int argc, _TCHAR* argv[])
{
        //1
        char* buf = "break wordbreak if if if break char else cahr alligator if" ; 
	//2
        int tab_power = sizeof(tab) / sizeof(*(tab + 0)); 
	printf("tab_power = %i \n", tab_power); 
	char* buf_curst = buf;
	while (*buf!='\0')
	{
		if (*(buf+1) == ' ' || *(buf+1)=='\0')
		{
			printf("%c \n", *buf_curst);
			//умножаю один выделенный участок памяти на весь словарь 
			for (int i = 0; i < tab_power; i++)
			{
                              //3
				if (compare2w(tab[i].word, buf_curst, buf+1))
				{
					++tab[i].count;
					break;
				}
			} //end for
			buf_curst = buf + 2;
		}//end if		
		++buf;
	}
	for (int i = 0; i < tab_power; i++)
	{
		printf("%i %s \n", tab[i].count, tab[i].word);
	}
	return 0;
}



Также у меня возникли вопросы:
1) Возможно ли написать buf в несколько строк ?
2)Всё-же мне не очень нравится строка
Код: plaintext
1.
int tab_power = sizeof(tab) / sizeof(*(tab + 0));


выше я писал о том что не уверен что это моветон. Насколько эта запись безопасна ? Пока не знаю как работает sizeof, нужно будет посмотреть исходный код. Меня терзают сомнения, по поводу этой строчки.
3)Хотел обратиться к tab[i].word по-нормальному, через указатели, не получилось. Подскажите как это сделать ?


Мне не очень нравится мой код. fe, не нравится как я назвал переменную в которой хранится текущее начало диапазона buf_curst. Не очень доволен именованием переменных в функции для сравнения слова и полуоткрытого диапазона. Далее, код слишком большой, мне кажется что его можно уменьшить. На что ещё обратить внимание ?

Далее, касаемо алгоритма. Очевидно, он не оптимален. Пока не понятно в какую сторону копать чтобы его улучшить. Но улучшать нужно. Какие-то слова, fe, нужно отметать сразу. Возможно стоит сравнивать только с теми словами в алфавите, длина которых равна длине найденного диапазона символов. Для длины, ввести третью размерность. Пока что так.


И теперь касаемо первой страницы K&R 6.3. Пока прочитал только её.

1. Выводы по структурам: поля - есть атрибуты, и по факту структура описывает схему отношений в РМД. Структуры используются для работы с таблицами при написании СУБД ?

2. Вот как K&R задают структуру:
K&RSTRUCT KEY {
CHAR *KEYWORD;
INT KEYCOUNT; };
STRUCT KEY KEYTAB [NKEYS];


Мне не нравится эта избыточность, к чему она тут ?зачем везде добавлять key ? Их читают, и остальные могут так начать делать.

Дочитаю 6.3
...
Рейтинг: 0 / 0
07.04.2014, 04:43
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606789
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Видимо smald уже подсказал мне как улучшить алгоритм, использовать алгоритм Бойера — Мура. Тоже почитаю
...
Рейтинг: 0 / 0
07.04.2014, 04:57
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606885
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
SashaMercuryПока не знаю как работает sizeof, нужно будет посмотреть исходный код. Меня терзают сомнения, по поводу этой строчки.исходник чего ты хочешь посмотреть, компилятора? ))) sizeof - оператор языка, а не функция, он вычисляет размер типа данных в момент компиляции.
SashaMercuryзачем везде добавлять key ? Их читают, и остальные могут так начать делать.это синтаксис языка С для типа данных "структура". struct key; Стандартная идиома, кстати, описывать структуры в С, такая:
Код: plaintext
1.
2.
3.
typedef struct key {...};
// теперь можно задавать экземпляры так:
key a;


PS в С++ typedef не нужен, ещё одно отличие языков
...
Рейтинг: 0 / 0
07.04.2014, 09:28
| Ответить | Цитировать | Написать  
K&R 6.3 Решение приведённой задачи. Вопросы по реализации
    #38606889
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Egorych, спасибо. Я имел ввиду добавление префикса key к членам структуры, плохо объяснил в предыдущем посте
...
Рейтинг: 0 / 0
07.04.2014, 09:34
| Ответить | Цитировать | Написать  
16 сообщений из 16, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / K&R 6.3 Решение приведённой задачи. Вопросы по реализации
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]