напечатать список в обратном порядке

если напишешь, обязательно под GPL наложи

struct node {
    int data;
    struct node *next;
};

void print_reversed(struct node *node)
{
    if (node != null) {
        print_reversed(node->next);
        printf("%d\n", node->data);
    }
}

> если напишешь, обязательно под GPL наложи

ну зачем же сразу глумиться над студентом :) Все проходят через свой первый "hello world", связанный список и segfault.

Просто не легко читается Кнут :( поэтому и обращаюсь к мудрому ALL-у

испортил студента, нет чтобы сказать "man рекурсия"

print_reversed([]) ->
    done;
print_reversed([H | T]) ->
    print_list(T),
    io:format("~p~n", [H]).

print_reversed([]) ->
    done;
print_reversed([H | T]) ->
    print_reversed(T),
    io:format("~p~n", [H]).

Хинт1. Можно ли по однонаправленному связному списку построить двунаправленный той же длины?
Хинт2. Можно ли обойтись вторый однонаправленным?
Хинт3. Можно ли испохабить исходный список, вместо генерации нового? Будет ли это преобразование обратимо?

mapM_ print $ reverse x

Надо понимать, что если исходный список нельзя разрушать, то операция требует объема памяти, пропорционального длине списка. Если это устраивает - то рекурсивно проще всего.

Для экономии памяти (предположим, что у тебя список занимает больше половины доступного пространства, тогда первый вариант не работает) можно развернуть список "на месте" (требуется всего два или три указателя), распечатать полученное, и развернуть список обратно.

Все вышеописанное относится к спискам, представленных в виде "struct node {struct node * next, void * data}", выделенных на куче. Если представление табличное - возможно, существуют более разумные алгоритмы. Но скорее всего - нет.

>> mapM_ print $ reverse x

print $ reverse x

Ну, удивил

lists:reverse(List).

мне и печатать не надо... ерланг не так ленив, он вернет результат :))

>мне и печатать не надо... ерланг не так ленив, он вернет результат :))

в ghci

reverse [1..10]

тоже напечатает

[10,9,8,7,6,5,4,3,2,1]

так что ленивость не мешает.

Ок =)

io:format("~p", [lists:reverse(List)]).

Какой язык?

1. Превратить его в двусвязный
2. Пройти один раз, запихивая элементы в стек, если память не жалко. Далее - пройтись по стеку.

Это варианты, а не последовательность действий :)

Кстати, если делать по второму варианту, то можно замутить хвостовую рекурсию :))

reversed(List) ->
    reversed(List, []).
reversed([], Reversed) ->
    Reversed;
reversed([H | T], Reversed) ->
    reversed(T, [H | Reversed]).

>mapM_ print $ reverse x

foldl (flip (:)) [] list

В стек можно пихать указатели на жлементы, если памяти жалко, и так будет быстрее, если элементы большие.

print_reverse( [ ] ).

print_reverse( [ Head | Tail ] ) :-
	print_reverse( Tail ),
	write( Head ),
	write( ' ' ).

А що ты таки будешь делать, если список очень большой?

Я так понял, что все показавшие код -- кодеры, а не программисты :-)

Студента интересует алгоритм, а не его реализация на конкретном языке.

>Я так понял, что все показавшие код -- кодеры, а не программисты :-)

либо у всех показавших код есть здоровое чувство юмора

>Студента интересует алгоритм, а не его реализация на конкретном языке.

алгоритм ему и так дали, в первых ответах - бери не хочу

Буду использовать двусторонний список (или на месте разверну, если это надо редко).

пагади, мы ему щас еще на какой-нить изотерике сейчас пример придумаем :)

на мозготрахе слабо?

   >10p0:p0:g10gg0:g1+0:p0:g10gg0:g1+0:p0:g10ggv
   |  ;>.v;         gg01g:0g01g:0p:0p01p02+1g02<
>0p>20g|
^2-1g02@#<

Программа распечаывает список в обратном порядке и завершается. Список ожидается в виде троек xyz разбросанных по памяти, где x - значение, y и z - координаты x из следующей тройки. Завершение списка - элемент со значением 0. Перед выполнением на стеке должен лежать адрес первого элемента.

Более компактная версия (по площади :D)

   >10p:0p:0g10gg:0g1+10gv
   |  ;>.v;<gg01g0:g01g0<
>0p>20g|  >g1+20p10p0:p0^
^2-1g02@#<^  02gg01+2g:0g<

Если в искомом языке есть замыкания, можно так:
(define (print-reversed l)
  (define (iter l fn)
    (if (null? l) 
      (fn)
      (iter (cdr l)
	    (lambda () (print (car l)) (fn)))))
  (iter l (lambda () #t)))

>в искомом языке
всмысле, в исходном, котором автор пользуется

>пагади, мы ему щас еще на какой-нить изотерике сейчас пример придумаем :)

Пожалуйста :)

USER list-stack-ptr

: {  ( -- addr )  DEPTH list-stack-ptr @ SWAP list-stack-ptr ! ;

: NODE-CHAIN  ( elem prev -- new )
    >R
    2 CELLS ALLOCATE DROP
    TUCK CELL+ ! 
    R> OVER !
;

: }  ( x1 x2 .. xn -- )
    DEPTH 1-
    0 0 NODE-CHAIN
    SWAP list-stack-ptr @
    ?DO NODE-CHAIN LOOP
    SWAP list-stack-ptr !
;

: NEXT-NODE  ( pos -- elem next )  DUP CELL+ @ SWAP @ ;

: LIST.  ( list -- )
    BEGIN
        NEXT-NODE DUP
    WHILE
        SWAP .
    REPEAT
;

: REVERSE-LIST.  ( list -- )
    0
    BEGIN
        SWAP NEXT-NODE DUP
    WHILE
        ROT 1+
    REPEAT
    2DROP
    0 ?DO . LOOP
;

{ 5 6 77 } VALUE list
list LIST.
> 5 6 77
list REVERSE-LIST.
> 77 6 5

:)

Ты еще на асме напиши. =)

Forth - не эзотерика! Кто возьмётся ниписать ни brainf***, SNUSP или INTERCAL? Компиляторы для всех существуют.

(Из этого треда можно уже новый task на http://rosettacode.org/ собрать.)

жосткие тут товарищи обитают я посмотрю... :)

спасибо за интересный пример :)

жесть какая... %))

Обратите внимание, среди языков в которых список не является примитивом и нет стандартных средств для работы с ними программа на Befunge оказалась самой короткой.

Но самая короткая - на J:

|. list

>программа на Befunge оказалась самой короткой.

Это потому что изначально синтаксис компактны и не расчитан на самодокументируемость :D

"u" alias USER
"d" alias DEPTH
"⇄" alias SWAP
"a" alias ALLOCATE
"⇣" alias DROP
"↶" alias TUCK
"↷" alias OVER
"↪" alias ?DO
"↫" alias LOOP
"↑" alias DUP
"↦" alias BEGIN
"⇒" alias WHILE
"↤" alias REPEAT
"↻" alias ROT
"⇣⇣" alias 2DROP

И теперь переписываем вышеприведённый код:

u p : { d p @ ⇄ p ! ; : n >r 8 a ⇣ ↶ 4 + ! r> ↷ ! ; : } d 1- 0 0 n ⇄ p @ ↪ n ↫ ⇄ p ! ; : e ↑ 4 + @ ⇄ @ ; : rl. 0 ↦ ⇄ e ↑ ⇒ ↻ 1+ ↤ ⇣⇣ 0 ↪ . ↫ ;

{ 5 6 77 } rl.
> 77 6 5

:)

Так компактнее? :D

Конечно, Befunge компактнее по количеству символов, но не по количеству операций. Например, 2DUP там реализуется как положить два значения куда-нибудь в память и достать их обратно в стек два раза. А возможности обратиться к 3-му и далее значению на стеке нет вообще.

> Обратите внимание, среди языков в которых список не является примитивом и нет стандартных средств для работы с ними программа на Befunge оказалась самой короткой.

$ man tac

Можно пройтись по списку, заменяя указатель на следующий элемент указателем на предыдущий элемент. Самый экономичный и один из самых быстрых вариантов, но портит список in-place.

О, картиночки... жесть, как у "хищника" на дисплейчике, который на руке... :)

А я сразу APL вспомнил, как замену на подходящие подобранные символы сделал :)