Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
#1

Список - C++

10.08.2012, 22:34. Просмотров 519. Ответов 9
Метки нет (Все метки)

дайте идею как можно рекурсивно обратить список

т.е есть список 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; 
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2012, 22:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Список (C++):

Создать список L3 из элементов, входящих и в список L1 и в список L2 - C++
создать список л3 из элементов входящих и в список л1 и в список л2

3 класса: список, стек(как список), очередь(как список) - C++
препод дал задание: написать 3 класса (список, стек, очередь), методы: вывод, добавление, удаление. Использовать при обращении указатель...

Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. - C++
Друзья помогите с реализацией списка. Нужно запрограммировать связный список, в котором информация о книгах сортируется по убыванию...

Вводится число N. Создать список его делителей и вывести список на экран - C++
#include<iostream> #include<stdio.h> #include<malloc.h> #include<string.h> #include<stdlib.h> using namespace std; struct...

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

list. Cоздать список из результатов(с массивами), а потом просмотреть весь список - C++
Подскажите пожалуйста как мне создать список из моих результатов(с массивами) а потом просмотреть весь список, вот код который имеется ...

9
Joke+R
41 / 41 / 3
Регистрация: 18.11.2011
Сообщений: 112
10.08.2012, 22:48 #2
Dark2012, реализуй стек, утопи в нём все элементы списка, а затем извлеки их из стека обратно в список
0
John Prick
830 / 763 / 152
Регистрация: 27.07.2012
Сообщений: 2,176
Завершенные тесты: 3
10.08.2012, 22:49 #3
Начинаешь с первого, запоминаешь его указатель на следующий во временную переменную и ставишь его на NULL. Запоминаешь адрес первого элемента в ещё одну временную переменную. Потом из временной переменной берёшь указатель (он указывает на второй), ставишь его текущим и повторяешь теже операции, что и для первого элемента с той лишь разницей, что вместо NULL ставишь указатель на первый элемент.
Наверное есть и более элегантные методы.
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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;
}
1
Invader_Zim
Twilight Parasite
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 908
10.08.2012, 23:29 #5
Dark2012, эмм , а может STL?
0
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
11.08.2012, 00:53  [ТС] #6
~OhMyGodSoLong~, - попробую...че то мне слово static не нравится)
John Prick, - ты описал итеративную версию - если ее писать как рекурсивную - то какова будет изначальная сигнатура функции??? -(там получается нужно передавать два списка)

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

Добавлено через 49 секунд
Invader_Zim, да вот сказали так надо))
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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;
}
1
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)))))

0
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;
}
0
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;
}
0
13.08.2012, 11:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2012, 11:26
Привет! Вот еще темы с ответами:

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

Упорядочить список студентов по среднему баллу и вывести весь список - C++
форумчане,выдает ошибку :( столько маюсь с задачей уже #include &lt;vcl.h&gt; #include &lt;stdio.h&gt; #pragma hdrstop /*Упорядочить список...

Описать функцию, которая будет проверять входит ли список l1 в список l2 - C++
Здравствуйте, нужно Описать функцию, которая будет проверять входит ли список l1 в список l2. Ни как не могу понять как это сделать. ...

std::sort. Как сортировать список? (список указателей на объект) - C++
Всем доброго времени суток! Извините за флуд темами, я не специально С простыми типами то всё понятно: std::vector&lt;string&gt; vStr; ...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.