Форум программистов, компьютерный форум CyberForum.ru

Список - C++

Восстановить пароль Регистрация
 
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
10.08.2012, 22:34     Список #1
дайте идею как можно рекурсивно обратить список

т.е есть список 1 -> 2 -> 3 -> 4 -> 5 ->(NULL)
должно стать так 5 -> 4 -> 3 -> 2 -> 1 ->(NULL)

хотя бы в общих слвах как сделать??))

структура списка примерно такая :
C++
1
2
3
4
5
6
7
8
9
10
11
struct Node
{
    Node(int _x)
    : x(_x)
    {
     next = NULL;
    }
    
    int x; 
    Node* next; 
};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2012, 22:34     Список
Посмотрите здесь:

Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. C++
C++ 3 класса: список, стек(как список), очередь(как список)
list. Cоздать список из результатов(с массивами), а потом просмотреть весь список C++
C++ создать список л3 из элементов входящих и в список л1 и в список л2
Создать список, после каждого отрицательного числа вставить в список 0 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Joke+R
 Аватар для Joke+R
41 / 41 / 3
Регистрация: 18.11.2011
Сообщений: 112
10.08.2012, 22:48     Список #2
Dark2012, реализуй стек, утопи в нём все элементы списка, а затем извлеки их из стека обратно в список
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
10.08.2012, 22:49     Список #3
Начинаешь с первого, запоминаешь его указатель на следующий во временную переменную и ставишь его на NULL. Запоминаешь адрес первого элемента в ещё одну временную переменную. Потом из временной переменной берёшь указатель (он указывает на второй), ставишь его текущим и повторяешь теже операции, что и для первого элемента с той лишь разницей, что вместо NULL ставишь указатель на первый элемент.
Наверное есть и более элегантные методы.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
10.08.2012, 23:21     Список #4
Lisp
1
2
3
4
5
6
(define (reverse list)
  (define (helper left rev)
    (if (pair? left)
        (helper (cdr left) (cons (car left) rev))
        rev ) )
  (helper list '()) )

Не по теме:

Ой, по-моему, я не в тот раздел пишу.



Добавлено через 12 минут
Хотя...
C++
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
#include <iostream>
 
struct List {
  int val;
  List *next;
 
  List(int val_) : val(val_), next(NULL) {}
  List(int val_, List *next_) : val(val_), next(next_) {}
  ~List() { delete next; }
 
  static int   car(List *list) { return list->val; }
  static List* cdr(List *list) { return list->next; }
  static List* cons(int val, List *list) { return new List(val, list); }
};
 
List* reverse(List *left, List *rev = NULL)
{
  if (left == NULL) {
    return rev;
  }
  else {
    return reverse(List::cdr(left), List::cons(List::car(left), rev));
  }
}
 
std::ostream& operator<<(std::ostream &stream, List *list)
{
  for (List *cur = list; cur != NULL; cur = cur->next) {
    stream << cur->val << " ";
  }
  return stream;
}
 
int main() {
  List *test = new List(1, new List(2, new List(3)));
  List *rev = reverse(test);
  std::cout << test;
  std::cout << std::endl;
  std::cout << rev;
  delete test;
  delete rev;
}
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
10.08.2012, 23:29     Список #5
Dark2012, эмм , а может STL?
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
11.08.2012, 00:53  [ТС]     Список #6
~OhMyGodSoLong~, - попробую...че то мне слово static не нравится)
John Prick, - ты описал итеративную версию - если ее писать как рекурсивную - то какова будет изначальная сигнатура функции??? -(там получается нужно передавать два списка)

Joke+R, это идея....тока опять поучается в параметры функции надо изначально какой то стек передавать)...

Добавлено через 49 секунд
Invader_Zim, да вот сказали так надо))
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.08.2012, 01:38     Список #7
Я написал тот вариант для прикола. Он делает перевёрнутую копию, а не переворачивает тот же самый список.

Вот тебе правильная переворачивалка, которая творит примерно то же самое, но изменяя тот же самый список, а не создавая новый. Это буквально алгоритм John Prick. И он как раз итеративный, но любую итерацию можно сделать рекурсией (хвостовой).
C++
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
#include <iostream>
 
struct List {
  int val;
  List *next;
 
  List(int val_, List *next_ = NULL) : val(val_), next(next_) {}
  ~List() { delete next; }
};
 
std::ostream& operator<<(std::ostream &stream, List *list)
{
  for (List *cur = list; cur != NULL; cur = cur->next) {
    stream << cur->val << " ";
  }
  return stream;
}
 
//  Суть: left = голова ещё не перевёрнутой части,
//  rev = голова перевёрнутой части.
//
//  reverse(1 -> 2 -> 3 -> NULL) == reverse(1 -> 2 -> 3 -> NULL, NULL) ==
//  == reverse(2 -> 3 -> NULL, 1 -> NULL) == reverse(3 -> NULL, 2 -> 1 -> NULL) == ...
List* reverse(List *left, List *rev = NULL)
{
  if (left == NULL) {
    return rev;
  }
  else {
    List *next = left->next;
    left->next = rev;
    reverse(next, left);
  }
}
 
int main()
{
  List *lst = new List(1, new List(2, new List(3)));
  std::cout << lst << std::endl;
  lst = reverse(lst); // важно переприсвоить
  std::cout << lst;
  delete lst;
  return 0;
}
Nameless One
11.08.2012, 08:38
  #8

Не по теме:

~OhMyGodSoLong~, есть же специальная форма

let
Lisp
1
2
3
4
5
6
7
(define (reverse lst)
  (let loop ((lst lst)
             (acc '()))
    (if (null? lst)
        acc
        (loop (cdr lst)
              (cons (car lst) acc)))))

Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
11.08.2012, 11:14  [ТС]     Список #9
~OhMyGodSoLong~, - Спасибо)

Я итеративную вот так написал....

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node* Reverse(Node* list)
{
    if (list == nullptr)
     return list;
        
    Node* next = list->next;
    list->next = nullptr;
    
    while (next)
    {
        if (next->next == NULL)
         {
           next->next = list;
           list = next;
           break;
         }
        Node* nextnext = next->next;
        next->next = list;
        list = next;
        next = nextnext;
    }
  return list;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2012, 11:26     Список
Еще ссылки по теме:

Сформировать список из 10 работников, используя динамическую структуру данных двусвязный список C++
C++ Сформировать список из 10 книг, используя динамическую структуру данных односвязный список
Напечатать пронумерованный список список первых 10 наиболее популярных газет C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Joke+R
 Аватар для Joke+R
41 / 41 / 3
Регистрация: 18.11.2011
Сообщений: 112
13.08.2012, 11:26     Список #10
Dark2012, со стеком всетаки легче:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
s_list* Reverse(s_list* list)
{   
    s_list* curr = list;
    int temp;
    
    while (curr)
    {
        temp = curr->data;
        _asm push(temp);
        curr = curr->next;
    }
 
    curr = list;
 
    while(curr)
    {
        _asm pop(temp);
        curr->data = temp;
        curr = curr->next;
    }
 
    return list;
}
Yandex
Объявления
13.08.2012, 11:26     Список
Ответ Создать тему
Опции темы

Текущее время: 18:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru