私はSchemeとLisp（おそらく）が循環リストをサポートしていることに注意し、C / C ++で循環リストを使用して要素の挿入と削除を「単純化」しましたが、それらは何に適していますか？
スキームは、それらが構築および処理できることを保証しますが、何のために？
円形またはテール円形である必要がある「キラー」データ構造はありますか？
4174 次
5 に答える
6
Saying it supports 'circular lists' is a bit much. You can build all kinds of circular data structures in Lisp. Like in many programming languages. There is not much special about Lisp in this respect. Take your typical 'Algorithms and Datastructure' book and implement any circular data structure: graphs, rings, ... What some Lisps offer is that one can print and read circular data structures. The support for this is because in typical Lisp programming domains circular data structures are common: parsers, relational expressions, networks of words, plans, ...
It is quite common that data structures contain cycles. Real 'circular lists' are not that often used. For example think of a task scheduler which runs a task and after some time switches to the next. The list of tasks can be circular so that after the 'last' task the scheduler takes the 'first' task. In fact there is no 'last' and 'first' - it is just a circular list of tasks and the scheduler runs them without end. You could also have a list of windows in a window system and with some key command you would switch to the next window. The list of windows could be circular.
Lists are useful when you need a cheap next operation and the size of the data structure is unknown in advance. You can always add another node to the list or remove a node from a list. Usual implementations of lists make getting the next node and adding/removing an item cheap. Getting the next element from an array is also relatively simple (increase the index, at the last index go to the first index), but adding/removing elements usually needs more expensive shift operations.
Also since it is easy to build circular data structures, one just might do it during interactive programming. If you then print a circular data structure with the built-in routines it would be a good idea if the printer can handle it, since otherwise it may print a circular list forever...
于 2010-03-07T09:33:51.780 に答える
4
モノポリーをプレイしたことがありますか？
カウンターやモジュロなどを使ってゲームをプレイせずに、ゲームのコンピューター実装でモノポリーボードをどのように表現しますか？循環リストは当然です。
于 2010-03-07T10:08:17.047 に答える
2
たとえば、二重リンクリストのデータ構造は、Scheme / LISPの観点では「循環」です。つまり、cons-structureを出力しようとすると、後方参照、つまり「サイクル」が得られます。したがって、実際には「リング」のように見えるデータ構造を持つことではありません。ある種のバックポインターを持つデータ構造は、Scheme/LISPの観点からは「循環」です。
「通常の」LISPリストは単一リンクです。つまり、リスト内からアイテムを削除するための破壊的な突然変異はO（n）操作です。二重リンクリストの場合はO（1）です。これが二重リンクリストの「キラー機能」であり、Scheme/LISPのコンテキストでは「循環」しています。
于 2010-03-07T06:50:41.040 に答える
2
リストの先頭に要素を追加および削除するのは安価です。リストの最後に要素を追加または削除するには、リスト全体をトラバースする必要があります。
循環リストを使用すると、一種の固定長キューを作成できます。
長さ5の循環リストを設定します。
> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))
リストに番号を追加しましょう：
> (set-car! q 6)
それでは、リストの最後の要素を作成しましょう。
> (set! q (cdr q))
リストを表示します。
> (take q 5)
(2 3 4 5 6)
したがって、これは、要素がリストの最後に入り、先頭から削除されるキューと見なすことができます。
リストに7を追加しましょう：
> (set-car! q 7)
> (set! q (cdr q))
> (take q 5)
(3 4 5 6 7)
等...
とにかく、これは私が循環リストを使用した1つの方法です。
この手法は、 Processingブックの例から移植したOpenGLデモで使用しています。
エド
于 2010-03-07T14:04:09.210 に答える
0
循環リストの使用法の1つは、srfi-1バージョンのマップを使用するときに値を「繰り返す」ことです。たとえば、valの各要素に追加するには、次のlstように記述します。
(map + (circular-list val) lst)
例えば：
(map + (circular-list 10) (list 0 1 2 3 4 5))
戻り値：
(10 11 12 13 14 15)
もちろん、これをに置き換えることでこれを行うことができますが+、(lambda (x) (+ x val))上記のイディオムの方が便利な場合もあります。これは、さまざまなサイズのリストを受け入れることができるsrfi-1バージョンのマップでのみ機能することに注意してください。
于 2011-05-21T06:03:33.803 に答える