RFpro.ru: Алгоритмы и теория программирования (comp.soft.prog.algorythmfaq) : Рассылка : Subscribe.Ru

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS

← Ноябрь 2010 →
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

За последние 60 дней ни разу не выходила

Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор

Калашников О.А.

Статистика

295 подписчиков
0 за неделю

← Все выпуски →

RFpro.ru: Алгоритмы и теория программирования

Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты данной рассылки

Гаряка Асмик
Статус: Профессор
Рейтинг: 5498
∙ повысить рейтинг »

Boriss
Статус: Академик
Рейтинг: 2544
∙ повысить рейтинг »

Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2035
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска:	126
Дата выхода:	27.11.2010, 17:30
Администратор рассылки:	Борисыч (Профессор)
Подписчиков / экспертов:	394 / 173
Вопросов / ответов:	1 / 2

Вопрос № 180896: Здравствуйте, уважаемые эксперты! Прошу Вас ответить на следующий вопрос:Дан текстовый файл.Вывести на экран строки файла в алфавитном порядке. Программа должна производить проверку особых ситуаций при операциях ввода-вывода ...

Вопрос № 180896:

Здравствуйте, уважаемые эксперты! Прошу Вас ответить на следующий вопрос:Дан текстовый файл.Вывести на экран строки файла в алфавитном порядке. Программа должна производить проверку особых ситуаций при операциях ввода-вывода

Отправлен: 23.11.2010, 01:34
Вопрос задал: Magma (Посетитель)
Всего ответов: 2
Страница вопроса »

Отвечает vladisslav (8-й класс) :
Здравствуйте, Magma!
Такой вариант. На C. Передавать 1 аргумент - исследуемый файл.
Используется список сортировки (точнее таблицы).
Используется b+ дерево. (Быстро и при большом количестве одинаковых слов занимает меньше памяти.)
Под словами подразумевается то, что читает функция scanf("%s",word).
Комментарии на английском (не люблю переключать раскладку).

Приложение:
/* Includes */ #include <stdio.h> #include <stdlib.h> #include <errno.h> #include <string.h> /* Structures */ /* Tree node, half a byte to reduce memory usage.*/ struct node { int count; struct node * leaves[1<<4]; }; /* Functions */ /* Add a word to a tree. Adds 2 node per 1 character.*/ void addword(struct node * root,char * str,unsigned char * collation) { struct node *p=NULL; p=root; unsigned char * s=(unsigned char *)str; if(*s==0)return; while(*s != 0) { /*Translate to sortable form*/ unsigned char c=collation[*s]; if(p->leaves[c >> 4] == NULL) p->leaves[c >> 4]=calloc(1,sizeof(struct node)); if(p->leaves[c >> 4] == NULL) { perror("Failed to allocate node. "); exit(1); } p=p->leaves[c >> 4]; if(p->leaves[c & 15] == NULL) p->leaves[c & 15]=calloc(1,sizeof(struct node)); if(p->leaves[c & 15] == NULL) { perror("Failed to allocate node. "); exit(1); } p=p->leaves[c & 15]; ++s; } ++p->count; } /* Walk the tree from lower to higher and print words found.*/ void printwords(struct node * n,unsigned char * buffer,int bp,unsigned char * collation) { int k=0,t=0,l=0; if(n->count>0) { l=strlen(buffer); unsigned char *cc=calloc(1,l+1); if(cc==NULL) { perror("Failed to allocate translation buffer. "); exit(1); } /*Translate to printable form*/ for(t=0;t<l;t++)cc[t]=collation[buffer[t]]; /*Print words found*/ for(k=0;k<n->count;k++) printf("%s\n",cc); free(cc); } /*Check all leaves*/ for(k=0;k<16;k++) if(n->leaves[k]!=NULL) { buffer[bp>>1]&=(bp&1)?((1<<4) -1)<<4:0; buffer[bp>>1]|=(bp&1)?k:(k<<4); /*Change to next position in a buffer and reenter*/ printwords(n->leaves[k],buffer,bp+1,collation); } /*clear last bufer position from remaining garbage (Is it really needed???)*/ buffer[bp>>1]&=(bp&1)?((1<<4) -1)<<4:0; } /*Entry point*/ int main(int argc,char **argv) { /*collation tables*/ unsigned char cf[256]; unsigned char cr[256]; /*Set up collation tables so small letters are sorted after corresponding capital ones*/ int a=0,b=0; while(a<\'A\') { cf[a]=a; cr[a]=a; ++a; } for(b=\'A\';b<=\'Z\';b++) { cf[a]=b; cr[b]=a; ++a; cf[a]=b+(\'a\'-\'A\'); cr[b+(\'a\'-\'A\')]=a; ++a; } for(;b<\'a\';b++) { cf[a]=b; cr[b]=a; ++a; } for(b=\'z\'+1;b<256;b++) { cf[a]=b; cr[b]=a; ++a; } /*Hope there will not be strings longer than 1023 characters (1024 including terminating zero byte) in input file*/ unsigned char *buffer=calloc(1,1024); if(buffer==NULL) { perror("Failed to allocate buffer. "); exit(1); } int got=0; /*tree root node*/ struct node * root=calloc(1,sizeof(struct node)); if(root==NULL) { perror("Failed to allocate root node. "); exit(1); } /*Check argument count*/ if(argc!=2) { fprintf(stderr,"Exactly 1 file expected.\n"); exit(1); } /*Open input file*/ FILE * fd=fopen(argv[1],"r"); if(fd==NULL) { perror("Failed to open file: "); exit(1); }; /*Read words*/ while(!feof(fd)) { got=fscanf(fd,"%1023s",buffer); if(got==0)break; if(got==EOF)break; //buffer[got]=0; addword(root,&buffer[0],&cr[0]); } if(errno != 0)perror("Railed to read word from file: "); /*close file*/ if(fclose(fd)!=0) { perror("Error while trying to close input file: "); }; /*Clear buffer*/ memset(buffer,0,1024); /*Show results*/ printwords(root,buffer,0,&cf[0]); return 0; }

Ответ отправил: vladisslav (8-й класс)
Ответ отправлен: 24.11.2010, 18:44
Номер ответа: 264309

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?

Отправить SMS #thank 264309 на номер 1151 (Россия) | Еще номера »

Отправить WebMoney:

Отвечает Борисыч (Профессор) :
Здравствуйте, Magma! G++/Code::Blocks. Файл читается в массив строк, массив сортируется "пузырьком", печатается на экран.

Код:

#include <stdio.h>
#include <string.h>

int main(void)
{

   enum {MAX_LINE_SIZE=100, MAX_VEC_SIZE=1000};
    char line[MAX_LINE_SIZE], tmp[MAX_LINE_SIZE];
    char v[MAX_VEC_SIZE][MAX_LINE_SIZE];
    char fname[40];
    int i, j, vec_size;
    FILE *f;

    printf("Файл " );
    scanf("%s", &fname);

    // Проверка открытия
    if ((f = fopen(fname, "r")) == NULL)
    {
        printf("Файл не найден\n");
        system("pause");
 
        return 1;
    }

    // Заполняем массив строк
    vec_size=0;
    while( fgets(line, MAX_LINE_SIZE, f) != NULL )
    {
        strcpy(v[vec_size++], line);
    }

    // Проверка закрытия
    if (fclose(f)!=0)
    {
        printf("Ошибка закрытия файла\n");
        system("pause");
        return 1;
    }

    // Сортируем массив строк
    // Правильней было бы сортировать массив указателей
    for (i=0; i<vec_size-1;
i++)
        for (j=vec_size-1; j>i; j--)
            if (strcmp(v[j], v[j-1])<0)
            {
                strcpy(tmp, v[j]);
                strcpy(v[j], v[j-1]);
                strcpy(v[j-1], tmp);
            }

    printf("\nПосле сортировки\n");
    for (i=0; i<vec_size; i++)
        printf(v[i]);

    system("pause");
    return 0;
}

Исходный файл.

Код:

Richard Bach
Jonathan Livingston Seagull

To the real Jonathan Seagull,
who lives within us all.

Part One

It was morning, and the new sun sparkled gold across the ripples of a
gentle sea. A mile from shore
a fishing boat chummed the water. and the
word for Breakfast Flock flashed through the air, till a crowd of a
thousand seagulls came to dodge and fight for bits of food. It was another
busy day beginning.
But way off alone, out by himself beyond boat and shore, Jonathan
Livingston Seagull was practicing. A hundred feet in the sky he lowered
his webbed feet, lifted his beak, and strained to hold a painful hard
twisting curve through his wings. The curv
 e meant that he would fly
slowly, and now he slowed until the wind was a whisper in his face, until
the ocean stood still beneath him. He narrowed his eyes in fierce
concentration, held his breath, forced one... single... more... inch...
of... curve... Then his featliers ruffled, he stalled and fell.
Seagulls, as you know, never falter, never stall. To stall in the air
is for them disgrace and it is dishonor.
But Jonathan Livingston Seagull, unashamed, stretching his wings
again in that
trembling hard curve - slowing, slowing, and stalling once
more - was no ordinary bird.
Most gulls don't bother to learn more than the simplest facts of
flight - how to get from shore to food and back again. For most gulls, it
is not flying that matters, but eating. For this gull, though, it was not
eating that mattered, but flight. More than anything else. Jonathan
Livingston Seagull loved to fly.

Пример работы

Код:

Файл test.txt
После сортировки



But Jonathan Livingston Seagull, unashamed, stretching his wings
But way off alone, out by himself beyond boat and shore, Jonathan
It was morning, and the new sun sparkled gold across the ripples of a
Jonathan Livingston Seagull
Livingston Seagull loved to fly.
Livingston Seagull was practicing. A hundred
feet in the sky he lowered
Most gulls don't bother to learn more than the simplest facts of
Part One
Richard Bach
Seagulls, as you know, never falter, never stall. To stall in the air
To the real Jonathan Seagull,
again in that trembling hard curve - slowing, slowing, and stalling once
busy day beginning.
concentration, held his breath, forced one... single... more... inch...
eating that mattered, but flight. More than anything else. Jon
 athan
flight - how to get from shore to food and back again. For most gulls, it
gentle sea. A mile from shore a fishing boat chummed the water. and the
his webbed feet, lifted his beak, and strained to hold a painful hard
is for them disgrace and it is dishonor.
is not flying that matters, but eating. For this gull, though, it was not
more - was no ordinary bird.
of... curve... Then his featliers ruffled, he stalled and fell.
slowly, and now he slowed until the wind was a whisper in
his face, until
the ocean stood still beneath him. He narrowed his eyes in fierce
thousand seagulls came to dodge and fight for bits of food. It was another
twisting curve through his wings. The curve meant that he would fly
who lives within us all.
word for Breakfast Flock flashed through the air, till a crowd of a

Если требуются разъяснения, пожалуйста, вопросы в мини-форум.

Ответ отправил: Борисыч (Профессор)
Ответ отправлен: 25.11.2010, 21:03
Номер ответа: 264331

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?

Отправить SMS #thank 264331 на номер 1151 (Россия) | Еще номера »

Отправить WebMoney:

Оценить выпуск »
Нам очень важно Ваше мнение об этом выпуске рассылки!

Задать вопрос экспертам этой рассылки »

Скажите "спасибо" эксперту, который помог Вам!

Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
на короткий номер 1151 (Россия)
Номер ответа и конкретный текст СМС указан внизу каждого ответа.

Полный список номеров »

* Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
*** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

© 2001-2010, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2010.6.23 от 23.11.2010

В избранное

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} {#if $P.login_register_tab == 1} <form class="authentication-form" method="post" action="/MEMBERLOGIN_authen_cred"> <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <h1>Войти на сайт</h1> {* {#include js_tmpl_auth_reg_button} *} {#include js_tmpl_auth_reg_action} <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones"><p>{#include js_tmpl_auth_reg_descr} </p></div> <div class="logreg_advice noPhones"> Если вы еще не с нами, то начните с <a href="#" onclick="rgNav('js_tab_reg');return false;" class="dashed" data-func="registr">регистрации</a> </div> <br><br> <a class="dashed auth-enter" href="/manage/author/"><b>Вход для авторов</b></a> </dt> </dl> </form> {#/if} {#if $P.login_register_tab == 2} <div class="rg_block_options"> <div id="js_tap_panel_auth"> <h1>Регистрация</h1> <div class="social_reg"> {* <div class="rg_description">{#include js_tmpl_soc_auth_reg_descr}</div> *} {#include js_tmpl_auth_reg_soc} <div class="rg_soc_auth_agree">{#include js_tmpl_auth_reg_agree}</div> </div> <div class="subscribe_reg"> {* <div class="rg_description"> #include js_tmpl_auth_reg_descr </div> *} {#include js_tmpl_auth_reg_action} </div> {* {#include js_tmpl_auth_reg_button} *} <div class="clr"> </div> <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones">{#include js_tmpl_auth_reg_descr} {#include js_tmpl_soc_auth_reg_descr} </div> </div> </div> {#/if} </div> {* <div class="gray_bg register_shadow"></div> *} </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_auth" class="{#if $P.login_register_tab == 1} rg_active_nav {#/if} rg_first_nav"><a onclick="rgNav('js_tab_auth');return false;" href="">Вход на сайт</a></li> <li id="js_tab_reg" class="{#if $P.login_register_tab == 2} rg_active_nav {#/if}"><a onclick="rgNav('js_tab_reg');return false;" href="">Регистрация </a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_action} {#if $P.login_register_tab == 1} {#include js_tmpl_auth_reg_soc} {#/if} <div class="rg_forms"> <input type="hidden" id="login_register_destination" value="{$P.login_register_destination}"/> {#if $P.login_register_tab == 1} <div class="rg_for_input"> <span class="rg_text_inner">E-mail или код подписчика</span> <input id="credential_0" class="js_keydown_selector rg_input_text" data-js_submit="no" data-js_next_input_name="credential_1" name="" type="text" /> </div> <div class="rg_for_input"> <span class="rg_text_inner">Пароль</span> <input id="credential_1" class="js_keydown_selector rg_input_text" data-js_submit="yes" data-js_action="js_loginFormBut" name="" type="password" onkeyup="showAttention(this,!!window.event.shiftKey)" /> <span class="pswd_attention" id="attention_pswd"> <span class="icon_attention"></span> <span class="pswd_attention-text" id="attention-text_pswd1">Русская раскладка клавиатуры!</span> <span class="pswd_attention-text" id="attention-text_pswd2">У вас включен Caps Lock!</span> <span class="pswd_attention-text" id="attention-text_pswd3">У вас включен Caps Lock и русская раскладка клавиатуры!</span> </span> </div> <div class="rg_for_input input-alien"> <span class="chk noPhones"><input id="chk_alien" name="" type="checkbox" /></span><label for="chk_alien" class="noPhones"> Чужой компьютер</label> <a class="forgot_pass" href="/member/totalrecall">Забыли пароль?</a> </div> <div class="rg_for_input"> <em id="auth_msg" class="reg_error"></em> <input id="lf_typeauthid" value="email" type="hidden"> <input type="submit" class="button button-red logreg_submit" id="js_loginFormBut" value="Войти">  <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} {#if $P.login_register_tab == 2} <div class="rg_for_input"> <span class="rg_text_inner">E-mail</span> <input id="arfemail" class="js_keydown_selector rg_input_text" name="" type="text" data-js_submit="yes" data-js_action="js_regFormBut"/> </div> <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a> </label> <br /> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_personal' type="checkbox" data-js_submit="yes" /></span> Нажимая на кнопку "Готово!", я даю <a class="link_txd logreg_accLink" href="/faq/persverordnung.html">согласие на обработку персональных данных</a> </label> </div> {* <div style="float: left;position: absolute;left: 11em;"> <img src="http://www.kupivip.ru/images/vip/logo.png?1604" style="width: 86px; vertical-align: middle;display: block;"> </div> <div class="rg_for_input rg_set_lineh"> <label class="js_tap_panel_checkbox"><input name="" id="js_tap_panel_checkbox_kupivip" type="checkbox" data-js_submit="yes"> Я хочу получать новости о скидках на одежду</label> </div> *} <div class="rg_for_input"> <em id="reg_msg" class="reg_error rg_for_input_wide"></em> <em id="reg_msg2" class="reg_error rg_for_input_wide"></em> <input id="rf_typeauthid" value="email" type="hidden"> <a class="button button-red logreg_submit" id="js_regFormBut" href="#">Готово!</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} </div> {#/template js_tmpl_auth_reg_action} {#template js_tmpl_auth_reg_agree} <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms_reg' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a></label> <em id="reg_msg_soc" class="reg_error rg_for_input_wide"></em> </div> {#/template js_tmpl_auth_reg_agree} {#template js_tmpl_auth_reg_button} <div class="rg_butons_socials"> {#if $P.login_register_tab == 1} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} {#if $P.login_register_tab == 2} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} </div> {#/template js_tmpl_auth_reg_button} {#template js_tmpl_auth_reg_descr} {#if $P.login_register_tab == 1} Для оформления подписки на выбранную рассылку, работы с интересующей вас группой или доступа в нужный вам раздел, просим авторизоваться на Subscribe.ru {#/if} {#if $P.login_register_tab == 2} Для регистрации укажите ваш e-mail адрес. Адрес должен быть действующим, на него сразу после регистрации будет отправлено письмо с инструкциями и кодом подтверждения. {#/if} {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_soc_auth_reg_descr} Или зарегистрируйтесь через социальную сеть. {#/template js_tmpl_soc_auth_reg_descr} {#template js_tmpl_auth_reg_soc} <div class="rg_soc"> {#if $P.login_register_tab == 1} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/login/vk/&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} {#if $P.login_register_tab == 2} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/join/vk&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} </div> {#/template js_tmpl_auth_reg_soc}

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <p class="rg_description">{#include js_tmpl_auth_reg_descr}</p> <div class="clr"> </div> {#include js_tmpl_auth_reg_action} <div class="clr"> </div> </dt> </dl> </div>  </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_reg" class="rg_active_nav rg_first_nav"><a href="" onclick="return false;" >Регистрация</a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_descr} <strong>Пожалуйста, подтвердите ваш адрес.</strong><br><br>Вам отправлено письмо для подтверждения вашего адреса {$P.register_confirm_mail}.<br>Для подтверждения адреса перейдите по ссылке из этого письма. {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_auth_reg_action} <div class="rg_forms confirm_code_from_letter"> <div class="rg_for_input"> <span class="rg_inp_descr" style="width:15em;">Или введите код из письма:</span> <input type="text" value="" id="confirm_code" name="" data-js_submit="yes" data-js_action="js_confirmFormBut" class="js_keydown_selector rg_input_text_conf" > </div> <div class="rg_for_input"><label>Не пришло письмо? <b>Пожалуйста, проверьте папку Спам</b><br /> (папку для нежелательной почты).</label><br /> <a href="" onclick="ajax_recall_code();return false" >Вышлите мне письмо еще раз!</a></div> <div class="rg_for_input"> <em class="reg_error" id="confirm_msg"></em> <a href="#" class="button button-red" id="js_confirmFormBut">Готово</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> <br> </div> </div> {#/template js_tmpl_auth_reg_action}