Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> reverse в связном списке, поменять порядок следования элементов 
V
    Опции темы
Luyan
Дата 2.11.2009, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
мне надо написать функцию реверсивного обращения списка. Я взял её с буржуйского сайта и она пашет только один раз, то есть только один раз может поменять порядок элементов. Кто-нибудь мог бы объяснить почему? и как это исправить?

Код

struct yzel
{
    int infa;
    yzel* next;
};
class List
{
    private:
        yzel* first;
    public:
        List()
        {
            first = new yzel;
            first->next = NULL;
        }
        ~List(){delete first;}

        void additems();
        void display();
        void remove();
        void reverselist();
};

void List::additems()
{
    yzel *t;
    int   va_el;
    t = first;
    cout << "Enter elements(0 - stop): " << endl;
    cin >> va_el;
    while  (va_el!=0)
    {
        t->next = new yzel;
        t = t->next;
        t->infa = va_el;
        t->next = NULL;
        cin >> va_el;
    }
}
void List::display ()
{
    yzel* t;
    t = first->next;
    cout << "List: ";
    while  (t!=NULL)
    {
        cout << t->infa << " ";
        t = t->next;
    }
    cout << endl;
}
void List::remove()
{
    yzel *q,*q1;
    q = first;
    q1 = q->next;
    while (q1!=NULL)
    {
        q = q1;
        q1 = q1->next;
        delete q;
    }
}


/************************************************/
yzel* reverse(yzel* head) 
{
    yzel* newNode = NULL;
    yzel* current = head;
    while(current)
    {
        yzel* n = current->next;
        current->next = newNode;
        newNode = current;
        current = n;
    }
    return newNode;
}
void List::reverselist()
{
    yzel* q = first->next;
    q = reverse(q);
    cout << "List: ";
    while(q!=NULL)
    {
        cout << q->infa << " ";
        q = q->next;
    }
    cout << endl;
}
/************************************************/


int main ()
{
    List Q;
    Q.additems();
    Q.display();

    Q.reverselist();
    Q.reverselist();
    
    Q.remove();
    system("pause");
    return 0;
}


Это сообщение отредактировал(а) Luyan - 2.11.2009, 18:01
PM   Вверх
bsa
Дата 2.11.2009, 19:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196
Если бы у тебя список был двусвязным, то проблем бы не было вообще - нужно бы было только поменять prev и next у каждого узла, а так же указатель на первый узел списка...



--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
Luyan
Дата 2.11.2009, 19:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
Цитата(bsa @  2.11.2009,  19:12 Найти цитируемый пост)
Если бы у тебя список был двусвязным, то проблем бы не было вообще - нужно бы было только поменять prev и next у каждого узла, а так же указатель на первый узел списка...

да, в двусвязном это не сложно, но мне надо реализовать именно в односвязном, в этом то вся и проблема, что я не представляю себе как.
PM   Вверх
Sosed
Дата 2.11.2009, 19:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 52
Регистрация: 18.8.2009

Репутация: 1
Всего: 1
Как вариант создать копию списка и заполнить в нужном порядке
PM MAIL   Вверх
Luyan
Дата 2.11.2009, 19:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
Цитата(Sosed @  2.11.2009,  19:37 Найти цитируемый пост)
Как вариант создать копию списка и заполнить в нужном порядке 

тогда уж в два раза список увеличить и заполнить в обратном порядке, потом удалить первую половину. 
А получше способа нету?
PM   Вверх
Anikmar
Дата 2.11.2009, 19:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59
Может как-то так (чисто идея - псевдокод)
Код

NextUzel=NULL
TempUzel = NULL;
CurUzel = FirstUzel;
while(CurUzel!= NULL)
{
  TempUzel = CurUzel->Next;
  CurUzel->Next = NextUzel;
  NextUzel = CurUzel;
  CurUzel = TempUzel;
}
FirstUzel = TempUzel;
PM MAIL ICQ   Вверх
Luyan
Дата 2.11.2009, 21:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
Цитата(Anikmar @  2.11.2009,  19:57 Найти цитируемый пост)
Может как-то так (чисто идея - псевдокод)

хорошая идея, только после первого прохода возникает лишний элемент, в чём причина?
Код

void List::reverselist()
{
    yzel *node, *next, *pred;
    node = first;
    pred = NULL;
    while(node != NULL)
    {
        next = node->next;
        node->next = pred;
        pred = node;
        node = next;
    }
    first = pred;

    yzel* q = first;
    cout << "List: ";
    while(q!=NULL)
    {
        cout << q->infa << " ";
        q = q->next;
    }
    cout << endl;
}
 
PM   Вверх
zim22
Дата 2.11.2009, 22:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69
рекурсивный круть-верть
Код

struct Node {
  Node *next;
  int value;
  Node(int v, Node *n = 0) : value(v), next(n) { }
};
typedef Node *Link;

Link reverse(Link head, Link prev = 0) {
  static Link result = 0;
  if (head->next == NULL) {    
    head->next = prev;
    return result = head;
  }
  reverse(head->next, head);
  head->next = prev;
  return result;
}
int main()
{
  Link first = new Node(1);
  Link begin = first;

  for (int i = 0; i != 2; ++i)
    first = (first->next = new Node ((i + 1) * 10));

  Link new_beginning = reverse(begin);
  return 0;
}




--------------------
C++ FAQ Lite
PM MAIL   Вверх
mes
Дата 2.11.2009, 23:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250
Цитата(zim22 @  2.11.2009,  21:45 Найти цитируемый пост)
рекурсивный круть-верть

имхо красивей смотрелось бы в foreach`евом исполнении  (в смысле в цикле), чем в рекурсивном, так как оставляла бы больше свободы для действий.

Это сообщение отредактировал(а) mes - 2.11.2009, 23:47


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Luyan
Дата 2.11.2009, 23:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
zim22, попробывал рекурсивную, выдаёт тоже, что и предидущая, вот:
Код

Enter elements(0 - stop):
1
2
3
4
5
0
List: 1 2 3 4 5
List: 5 4 3 2 1 -842150451
List: -842150451 1 2 3 4 5
Для продолжения нажмите любую клавишу . . .

у меня уже от указателей мозги кипят smile 
что происходит?

Это сообщение отредактировал(а) Luyan - 2.11.2009, 23:35
PM   Вверх
Anikmar
Дата 3.11.2009, 00:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59
Цитата(Luyan @  2.11.2009,  23:35 Найти цитируемый пост)
zim22, попробывал рекурсивную, выдаёт тоже, что и предидущая, вот:


Цитата(Luyan @  2.11.2009,  23:35 Найти цитируемый пост)
у меня уже от указателей мозги кипят  
что происходит?


Думаю, если при использовании разных реверсов одна и та же ошибка - значит где-то что-то с начальным вводом...
PM MAIL ICQ   Вверх
Luyan
Дата 3.11.2009, 15:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7
всё, разобрался.
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0571 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.