chestr
Гость
|
|
« : 20-05-2008 14:30 » |
|
Здравствуйте. Прошу помощи в написании алгоритма, он по учёбе нужен, но у меня возникли проблемы, сам уж точно не справлюсь. вот. помогите чем сможете. Постановка задачи :
Пользователь вводит шаблон, включающий в себя символы "?" и "*". Найти в файле все строки, соответствующиешаблону и вывести на экран. (причём ещё и на русском языке нужно что б читала)
Я кое-что пробовал, но у меня не очень вышло. Если есть варианты Вашей программы, напишите, или исправьте мою. Желательно с пояснениями. З.Ы: Спасибо.
|
|
« Последнее редактирование: 06-08-2008 19:08 от Алексей1153++ »
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #1 : 20-05-2008 14:33 » |
|
вот программа: #include <iostream.h> #include <stdio.h>
char fname[]="имя файла";
bool cmpchr(char z,char p) if (p=='?'||z==p) return true; return false; }
bool cmpstr(char *q, char *k) { if (*q=='\0'||*k=='\0') return false; while(true) { if (cmpchr(*q,*k)) { q++; k++; } else break; if (*q=='\0') return (*k=='\0'); } if (*k!='*') return false; else { while(*k=='*') k++; if (*k=='\0') return true; char *w=q; bool ok=false; while(*w!='\0') { ok=cmpstr(w,k); if (ok) break; w++; } return ok; } }
void norm(char s) { while(s!='\0') { if (s=='?'&&*(s+1)=='*') s='*'; if (s=='?'&&*(s-1)=='*') s='*'; s++; } }
int main() { char x[500],y[2049],*i,*j,t; FILE *fl; if ((fl=fopen(fname,"r"))==NULL) { cout<<"error"; return(0); } gets(x); norm(x); while(!feof(fl)) { fgets(y,2048,fl); for(i=y;*i!='\0';i++) for(j=i;*j!='\0';j++) { t=*j; *j='\0'; if (cmpstr(i,x)) cout<<i<<endl; *j=t; } } fclose(fl); return 0; }
|
|
« Последнее редактирование: 06-08-2008 19:10 от Алексей1153++ »
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #2 : 20-05-2008 15:43 » |
|
chestr, А идеи хоть какие-нибудь в плане построения алгоритма есть? Ну, тоесть, если ты писал приведенную выше програму, то на какую-то последовательность действий ты все-таки ориентировался. Может опишеш словами? ЗЫ Приведенная программа, ИМХО, даже не скомпилится.
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #3 : 20-05-2008 15:46 » |
|
ентую прогу мне парень написал, я начал разбираться, ничего не получается... не знаю что делать..(
|
|
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #4 : 20-05-2008 15:56 » |
|
chestr, Ну что тебе сказать, здравая мысль в программе есть, однако реализация маненько шалит. Там столько раз скачут с указателей на символы, что лично мне страшно. А относительно разбирать алгоритм по запутанной программе - так ето стоит делать только в крайних случаях. А вообще делается наоборот. Сначала алгоритм - потом реализация. Если реализация будет не твоя, то желательно еще и обильные коментарии в коде. А теперь отвлечемся маненько. Ты себе смысл задания представляеш хотя бы в общих чертах?
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #5 : 20-05-2008 16:01 » |
|
ничего подобного я ещё не делал, и лекций у нас не было таких.. так что у меня все представления основаны на том, что я вычитал в нете, и в книге о шаблонах... .
|
|
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #6 : 20-05-2008 16:06 » |
|
А вот книга о шаблонах(если имеются ввиду шаблоны, которые в С++ начинаются с template) это ты зря, тут шаблон - ето некоторое обобщенное понятие, синонимом которого является "образец", тоесть "шаблон строки" ето то же самое, что и "образец строки". Наводящий вопрос: Ты когда нибудь искал у себя на компе файлы, точное имя которых ты не помнил? Если да, то как ты задавал имя этого файла?
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #7 : 20-05-2008 16:09 » |
|
хм... естесственно искал.. задавал первыми буквами слова. ключевыми буквами
|
|
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #8 : 20-05-2008 16:14 » |
|
Идейно, но ето Виндовс тебя разбаловала, потому что она сама по твои мервым 2 буквам могла искать названия файлов, в которых ети буквы были и в конце и посредине. В ДОС-е таких вольностей не было, там все было менее лояльно, что просиш, то и дадут - причем имено так как поймет твой запрос система, а не так как ты думаеш он должен работать )) Ладно, поставим вопрос по другому: Понимаеш ли ты, что в шаблоне строки означают символы "?" и "*"?
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #9 : 20-05-2008 16:20 » |
|
Насколько я знаю, "*" - это соответствует 0 или более вхождений предшествующего выражения. например "до*" - соответствует "д" и "дом" "?" - Соответствует 0 или 1 предшествующих выражений. Например, "мыш(ка)?" - "мыш" и "мышка" но как это всё впихнуть в код, я даже не представляю...
|
|
« Последнее редактирование: 20-05-2008 16:22 от chestr »
|
Записан
|
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #10 : 20-05-2008 16:29 » |
|
Ну ето не совсем так "*" - ето 0 и больше символов вообще, тоесть шаблону "до*" будет соответствовать "до", "дом", "док", "долина" и так далее до бесконечности "?" - ето 0 или 1 любой символ, тоесть шаблону "?ост" будут соответствовать "ост", "мост", "пост", "Ыост"(слова такого в словаре нету, но ето не лишает права на существование подобную комбинацию букв)
(по крайней мере такие соответствия прочно укоренились в моем мозгу. Если есть другие, то с радостью почитаю)
Теперь появились какие-то мысли в плане шагов для поиска строк по шаблону? Если нет, поставь себя на место программы. Как бы ты совершал поиск строк в тексте, если бы тебе дали некоторый шаблон?
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #11 : 20-05-2008 16:43 » |
|
так... тогда я должен, основываясь на шаблоне (из скольки букв состоит, каких и тп.) задать код , состоящий из некоторых букв (шаблона) и * с ? вроде бы так. далее, через условный оператор надо делать проверку "похожести" на шаблон до конца файла , потом всё вывести на экран
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #12 : 20-05-2008 17:07 » |
|
chestr, задача учебная? Если да, то что уже знаешь/проходил, и в рамках какой дисциплины решаешь задачу? От этого зависит, какими словами тебе будут объяснять непонятое, и будут ли (может, ты уже всё должен знать ) Значит, так. Шаблон у тебя содержит, если грубо, "обычные слова" и спецсимволы. "Обычные слова" - это обязательные части, всё, кроме символов '*' и '?'. Следовательно, тебе нужно разбить шаблон на составные части и двигаться последовательно по проверяемой на соответствие шаблону строке. При этом для простых слов у тебя будет элементарная проверка на соответствие, а вот для спецсимволов нужно будет рассматривать каждый вариант от "0 символов" до "N любых символов" (для '?' N = 1, а вот для '*' N - любое).
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #13 : 20-05-2008 17:14 » |
|
вообще говоря, дисциплина "основы алгоритмизации и программирования", 1-й курс, курсач. на лекции не было этого на 100%, покупать не хочу, надо самому разбираться. вот. если будешь объяснять, попробуй по-понятнее) (благодарю за помощь) пока всё понятно.. дай пример, может, какой-нить..
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #14 : 20-05-2008 17:18 » |
|
Ага. Первый курс, значит "конечные автоматы" и "регулярные выражения" - наверное, ещё пустой звук. А как насчёт рекурсии, умеешь делать? По-моему, задача обработки спецсимволов в самом простом варианте - рекурсивная. Да и в твоём примере - тоже так решается.
|
|
« Последнее редактирование: 20-05-2008 17:20 от Вад »
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #15 : 20-05-2008 17:28 » |
|
был бы просто в восторге если бы объяснил эту штуку "рекурсию" ))
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #16 : 20-05-2008 17:33 » |
|
Рекурсивный вызов функции - это вызов функции из неё самой. В твоём примере так делает функция cmpstr. Ничего сложного. Пишется функция, которая выполняет один шаг алгоритма и затем новый шаг выполняется посредством рекурсивного вызова. Странно, что с этим понятием ты не знаком, хотя пример у тебя писал человек, с рекурсией знакомый
|
|
|
Записан
|
|
|
|
RXL
|
|
« Ответ #17 : 20-05-2008 17:40 » |
|
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
chestr
Гость
|
|
« Ответ #18 : 20-05-2008 18:10 » |
|
спасибо за ссылки, сейчас буду изучать)
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #19 : 20-05-2008 20:25 » |
|
#include <iostream.h> #include <stdio.h>
char fname[]="имя файла";
bool cmpchr(char z,char p) { if (p=='?'||z==p) return true; return false; }
bool cmpstr(char *q, char *k) { if (*q=='\0'||*k=='\0') return false; while(true) { if (cmpchr(*q,*k)) { q++; k++; } else break; if (*q=='\0') return (*k=='\0'); } if (*k!='*') return false; else { while(*k=='*') k++; if (*k=='\0') return true; char *w=q; bool ok=false; while(*w!='\0') { ok=cmpstr(w,k); if (ok) break; w++; } return ok; } }
void norm(char s) { while(s!='\0') { if (s=='?'&& ((s+1))=='*') s='*'; if (s=='?'&& ((s-1))=='*') s='*'; s++; } }
int main() { char x[500],y[2049],*i,*j,t; FILE *fl; if ((fl=fopen(fname,"r"))==NULL) { cout<<"error"; return(0); } gets(x); //norm(x); while(!feof(fl)) { fgets(y,2048,fl); for(i=y;*i!='\0';i++) for(j=i;*j!='\0';j++) { t=*j; *j='\0'; if (cmpstr(i,x)) cout<<i<<endl; *j=t; } } fclose(fl); return 0; }
|
|
|
Записан
|
|
|
|
chestr
Гость
|
|
« Ответ #20 : 20-05-2008 20:26 » |
|
ну а щас.
|
|
|
Записан
|
|
|
|
RXL
|
|
« Ответ #21 : 20-05-2008 20:43 » |
|
chestr, когда пишешь сообщение, оборачивай код этим тегом: [code] [/code].
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
Sands
Помогающий
Offline
|
|
« Ответ #22 : 21-05-2008 09:08 » |
|
chestr, Извини за нескромный вопрос, но ты сам-то приведенную программу компилировал? Запускал на выполнение? От того, что ты закоментировал функцию нормализации шаблона суть программы не особо поменялась. И, кстати, каковы твои познания в плане работы со строками и работы с файлами? А также в плане понимания чужого кода ))
|
|
|
Записан
|
|
|
|
|