Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Рекурсия в структурах

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки

Открыть новую тему     Написать ответ в эту тему

StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Доброе время суток!
В visual studio 2010 был создан проект CLR console application код которого приведен ниже. Программа должна принять члены бинарного дерева, а затем вывести на экран члены бинарного дерева. Программа не принимает больше одного символа и на экран ничего не выводит.

Код:
// 7_10_binaryTree.cpp : main project file.
 
#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
 
using namespace System;
 
#define eof -1
#define maxline 1000
int fix=0;
 
int getline(char s[], int lim)
{
    int i,c;
    for(i=0; i<lim-1 && (c=getchar())!=eof && c!='\n';i++)
        s[i]=c;
    s[i]='\0';
    return i++;
}
 
struct tnod
{
    char *word;
    int count;
    struct tnod *left;
    struct tnod *right;
};
 
char *strsave(char *s)
{
    char *p;
    p=(char*)malloc(sizeof(strlen(s)+1));
    if(p!=NULL)
        strcpy(p,s);
    return p;
}
 
tnod *nodAlloc(void)
{
    tnod *p=p=(tnod *)malloc(sizeof(tnod));
    return p;
}
 
tnod *makeTree(tnod *p, char *w)
{
    int cond;
    if(p==NULL)
    {
        p=nodAlloc();
        p->word=strsave(w);
        p->count=1;
        p->left=p->right=NULL;
    }
    else if((cond=strcmp(w,p->word))==0)
        p->count++;
    else if(cond<0)
        p->left=makeTree(p->left,w);
    else if(cond<0)
        p->right=makeTree(p->right,w);
    return p;
}
 
int treePrint(tnod *p)
{
    if(p!=NULL)
    {
        printf("Count word repetition=%d word's value=%s\n",p->count,p->word);
        treePrint(p->left);
        treePrint(p->right);
    }
    return 0;
}
 
int main()
{
    tnod *pp;
    char s[maxline];
    pp=NULL;
    int i=0;
    char c;
    printf("Enter your words: >\n");
    while(getline(s,maxline)-1)/*getline() возвращает количество введенных символов
Когда нажимаем только <Enter>, вводится всего один символ ('\n').
Если от единицы отнять единицу, получим нуль, а это — для оператора while  
сигнал о прекращении цикла*/
        pp=makeTree(pp,s);
    treePrint(pp);
    _getch();
}
 

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 20:43 15-08-2015
ne_viens

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
//...
    else if(cond<0)
        p->left=makeTree(p->left,w);
    else if(cond>0)           //crtl-c, ctrl-v программирование
//...
while(getline(s,maxline)) //getline() '/n' не возвращает
//...

Всего записей: 1530 | Зарегистр. 01-11-2004 | Отправлено: 21:20 15-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
в самой же getline return i++; непонятно, что хотели сказать - это же постинкремент  
апиридили

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 21:26 15-08-2015 | Исправлено: opencl26, 22:46 15-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Всё, разобрался. Работает.
Кроме того, что написал ne_viens, правим функцию getline так:

Код:
int getline(char s[], int lim)
{
    int i,c;
    for(i=0; i<lim-1 && (c=getchar())!=eof && c!='\n';i++)
        s[i]=c;
    s[i]='\0';
    i++;
    return i;
}  

 
 
Добавлено:
Или просто

Код:
return ++i;

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 22:16 15-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
и вашим курям не хворать!
а зачем этот инкремент?
учитесь оптимизировать сразу
инкремент убираете совсем и условие как написал выше ne_viens: и всё работает и минус две операции высокого уровня
компилятор конечно хорошо, но в алгоритмах всегда найдётся работа для оптимизатора из-за таких вот финтов

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 02:41 16-08-2015 | Исправлено: opencl26, 02:50 16-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Цикл wihle(), для нормальной работы, ждёт 0 или  число отличное от 0 (ложь/истина). Поэтому
Код:
int getline(char s[], int lim)
должна что-то соответствующее возвращать. Подробное объяснение в самом первом посте в комментарии к while(getline(s,maxline)-1).
Вот и получается: если мы вводим в программу 'a', то это 2 символа (+enter). А если оставляем пустую строку, то это 1 символ (клавиши enter) и цикл завершится.

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 16:08 16-08-2015
ne_viens

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
В Visual Studio есть отладчик, запусти в нём прогу и посмотри, как там на самом деле с энтером.
 
 

Всего записей: 1530 | Зарегистр. 01-11-2004 | Отправлено: 16:22 16-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
//...
while(getline(s,maxline)) //getline() '/n' не возвращает
//...

Согласен. Не возвращает. Функция getline(s,maxline) обрабатывает введеные символы и возвращает количество введеных символов. А символы, которые были введены, getchar() из своего буфера  передаёт в массив s[i], адрес которого, естественно, известен вызывающей функции. Ведь он определён в блоке операторов вызывающей функции в самом начале (char s[maxline]). Если мы нажмём просто <Enter>, то функция getline() возвратит 1, но не перевод строки т.к. цикл for(), по условию, прерывается при нажатии <Enter> и этот <Enter> (или '\n') в s[i] не попадёт тоже.
Поэтому getline() в конце выполнит:

Код:
 
//
    s[i]='\0';
    i++;
    return i;

возвращая тем самым 1.
Т.к. getline() вызывается через while(), и 0 условие его звершения, то нужно вычесть из getline() 1. Поэтому:

Код:
int main()
{
    tnod *pp;
    char s[maxline];
    pp=NULL;
    int i=0;
    printf("Enter your words: >\n");
    while(getline(s,maxline)-1)
        pp=makeTree(pp,s);
    treePrint(pp);
    _getch();
}  

Это просто обработчик завершения ввода текста (определение факта нажатия <Enter> он же '\n'). Вот и получается, что по вышеописаным причинам '\n' нигде, кроме внутреннего буфера getchar() и переменной int с в getline() (а какже иначе определить, что мы нажали <Enter>), не светится.

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 17:43 16-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
падаждите
я вот тупо не понял, почему если убрать инкремент и убрать "минус один" в while, то работать не булет? или всё-таки будет, но "тут так написано"?
объясните мне тупому!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1111111111111111111

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 17:53 16-08-2015 | Исправлено: opencl26, 18:40 16-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
падаждите
я вот тупо не понял, почему если убрать инкремент и убрать "минус один" в while, то работать не булет?

Потому, что getline(s,maxline) возвращает 1. А выражение
Код:
getline(s,maxline)-1  
условие выхода из цикла (1-1=0). Поэтому:
Код:
while(getline(s,maxline)-1)
.Инкримент можно и убрать. Но тогда пишите альтернативный обработчик условия завершения ввода. Инкримент и "минус один" это часть обработчика завершения ввода строки.

Цитата:
или если так оптимизировать, то рационализаторам карандашной фабрики премий не достанется

Нам больше денег будет.

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 18:42 16-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
ну вот же:
getline(s,maxline) без инкремента возвращает 0 в случае пустой строки
тогда while(getline(s,maxline))  заврешает цикл, ничего писать не надо
в итоге избавились от двух ненужных операций, оптимизировали код  
 
 

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 19:15 16-08-2015 | Исправлено: opencl26, 19:53 16-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
getline(s,maxline) без инкремента возвращает 0 в случае пустой строки
тогда while(getline(s,maxline))  заврешает цикл, ничего писать не надо
в итоге избавились от двух ненужных операций, оптимизировали код  
просто я как программист больше как хирург работаю, ничего не знаю, но всё умею  
как у врачей
терапевт всё знает, но ничего не умеет
хирург ничего не знает, но всё умеет
и лишь патологогоанатом всё знает и всё умеет, но пациент попадает к нему слишком поздно) [/q]

Код:
int getline(char s[], int lim)  
где int - тип возвращаемого значения. Если убрать
Код:
return ++i;
нужно ставить void вместо int. Тип char не солидно: массив строки ввода передаётся по ссылке. Поэтому
Цитата:
Инкримент можно и убрать. Но тогда пишите альтернативный обработчик условия завершения ввода. Инкримент и "минус один" это часть обработчика завершения ввода строки

 
Откомпилируйте пример и прогоните через отладчик.
 

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 20:03 16-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
вы меня недопоняли, инкремент это операция - "++", а не выражение "return ++i"
вот правильный оптимальный код

Код:
 
int getline(char s[], int lim)
{
    int i,c;
    for(i=0; i<lim-1 && (c=getchar())!=eof && c!='\n';i++)
        s[i]=c;
    s[i]='\0';
    return i;
}  
 

и условие

Код:
 
while(getline(s,maxline))
 

учите английский, чтобы говорить на одном языке с другими разработчиками, я, например, владел наполовину от сегодняшнего уровня до изучения программирования английским, потом в процессе чтения технической литературы расширил и углубил словарный запас, а грамматику знал очень давно на примитивном уровне..но конечно, если будете им пользоваться, потому как забывается со временем любой скилл, даже автоматический, просто автоматический намного дольше забывается, чем обычный..

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 20:29 16-08-2015 | Исправлено: opencl26, 20:45 16-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Инкримент тут нужен для учёта количества введеных символов, ибо массив начинается с нуля. Считаем почти всегда с 1, но не 0. Мне так удобнее. Это просто тестовый пример. Теперь я вас понял. Просто вам надо было начать с кода последнего вашего поста. В нём на одну команду add x,y меньше. Экономия примерно в пару "тиков" процессора. И потом, чужие мысли не английский: читать не научишься.
 
Добавлено:
Пардон, ошибся inc x, а не add x,y

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 00:12 17-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
ну и в условии  

Код:
 
while(getline(s,maxline)-1)  
 

убрали -1 это dec eax
и потом неизвестно заранее, во что развернёт компилятор эту экономию, может он уже сразу сам соптимизировал, а может и нет...просто это правило хорошего стиля экономить на высоком уровне(с&c++), тогда ассемблерщику будет легче после вас чистить код, если ассемблерщик - не вы сам.
программирование - создание массового продукта, когда вашей программой будут пользоватся тысячи и миллионы каждый день 360 дней в году, то экономия в пару "тиков" выливается в огромные ресурсы, но это если вы программист майкрософт или подобной компании.  
для других же целей не имеет смысла так глубоко учить c&c++, освойте php в противном случае и сидите на зарплате в какой-нибудь подвальной конторе в москве или киеве, там оптимизация не нужна
отлично, что пришли к консенсусу! больше не буду мешать!

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 01:30 17-08-2015 | Исправлено: opencl26, 11:39 17-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
opencl26, мне был нужен учёт количества всех фактически введеных символов. Включая <Enter>. Без инкримента <Enter> выпадает. Просто тут оптимизировать нечего.
Но если сделать так, как вы сказали, то уйдут 2 команды (visual studio 2010): inc x и sub x,y (возможно dec x вместо sub). Без автоматической оптимизации а-ля "от коппилятора" скорее всего это будут эти команды. В сумме они дадут примерно 15 байт (если sub x,y). Следовательно на процессоре 3Ghz экономия процессорного времени будет примерно 5ns или 5е-9 секунд (если dec то ещё меньше). А с понтами, которые встраивает в свои процессоры intel/AMD для увеличения производительности эти 5нс могут уменьшиться ещё больше.
А теперь подумаем нафига попу гармонь. Подобная оптимизация критична при разработке , например, драйверов, ядер ОС, высоконагруженых систем и т.д. где критична производительность. Что делает наш getline()? Обрабатывает пользовательский ввод данных. Согласитесь, для удобства пользователя 5нс можна пренебречь и повысить коммерческий рейтинг программы.
По большому счёту, если весь исполнительный код операционной системы заточить на высокую скорость работы, то практически весь GUI прийдётся викинуть, что бы не загружал процессор всякой фигнёй. Но тогда на Ru.Board мы будем писать через консоль.
Ну а свопросом сколько мы сэкономим электроенергии на 15Гц - к инженерам intel/AMD. Они единственные кто знает как работает их процессор со всеми понтами, наворотами и причандалами.

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 17:09 17-08-2015
opencl26

Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
А теперь подумаем нафига попу гармонь.

тоже так подумал, когда приезжали американские проповедники и начали петь на собрании, и свалил оттуда..
мож не надо было, и нужна-таки попу гармонь, и я был бы в америке?
извините за офтоп, но наболело
 

Всего записей: 319 | Зарегистр. 17-09-2014 | Отправлено: 17:13 17-08-2015 | Исправлено: opencl26, 18:13 17-08-2015
StillPhelix



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Не интересно.
Вам сода http://forum.ru-board.com/forum.cgi?forum=3.

Всего записей: 173 | Зарегистр. 18-08-2013 | Отправлено: 18:28 17-08-2015
Открыть новую тему     Написать ответ в эту тему

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Рекурсия в структурах


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru