This HTML5 document contains 87 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n18http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n20https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
n7http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Parent_pointer_tree
rdf:type
yago:YagoPermanentlyLocatedEntity yago:Communication100033020 yago:Arrangement105726596 yago:Abstraction100002137 yago:VisualCommunication106873252 dbo:Building yago:WikicatDataStructures yago:WikicatDirectedGraphs yago:Continuance101017987 yago:WikicatContinuations yago:Activity100407535 yago:Cognition100023271 yago:Act100030358 yago:Structure105726345 yago:Event100029378 yago:Graph107000195 yago:DataStructure105728493 yago:PsychologicalFeature100023100
rdfs:label
スパゲッティスタック Pile spaghetti Parent pointer tree
rdfs:comment
Une pile spaghetti (ou pile cactus, pile saguaro ou in-tree) en informatique est un arbre enraciné N-aire dans lequel les nœuds fils ont un pointeur vers leur nœud père (mais pas l'inverse). Lors d'un parcours d'un nœud feuille en suivant ses ancêtres vers le nœud racine, la structure est semblable à une pile en liste chaînée. En effet, chaque nœud a un seul pointeur vers le nœud "suivant" (père), et ignore si ce père a d'autres enfants. Ni lui ni le père ne peut explorer les autres enfants, puisqu'il n'y a pas de pointeurs descendants. In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti stack, cactus stack or sahuaro stack (after the sahuaro, a kind of cactus). Parent pointer trees are also used as disjoint-set data structures. The structure can be regarded as a set of singly linked lists that part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node. スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。 スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。 類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。
foaf:depiction
n7:Spaghettistack.svg
dcterms:subject
dbc:Metaphors_referring_to_spaghetti dbc:Continuations dbc:Trees_(data_structures)
dbo:wikiPageID
2066241
dbo:wikiPageRevisionID
1092029872
dbo:wikiPageWikiLink
dbr:C_(programming_language) dbr:Burroughs_large_systems dbr:Stack_(abstract_data_type) dbr:Symbol_table dbc:Trees_(data_structures) dbr:Burroughs_Large_Systems dbr:Burroughs_MCP dbr:Mainframe_computers dbr:Tree_data_structure dbr:Disjoint-set_data_structure dbr:Pointer_(computer_programming) dbr:Stack_frame dbr:Structure_sharing dbr:Singly_linked_list dbr:Child_node dbr:Smalltalk dbr:Compiler dbr:Closure_(computer_science) dbr:Run-time_stack dbr:Sahuaro dbr:Parent_node dbr:Persistent_data_structure dbc:Metaphors_referring_to_spaghetti dbr:Cilk dbr:Programming_language n18:Spaghettistack.svg dbr:ALGOL_60 dbr:Garbage_collection_(computer_science) dbc:Continuations dbr:Dynamic_memory_allocation dbr:Computer_science dbr:Felix_(programming_language) dbr:Abstract_syntax_tree dbr:Nested_functions dbr:Scheme_(programming_language) dbr:Burroughs_Corporation dbr:Funarg_problem dbr:Scope_(computer_science) dbr:Standard_ML_of_New_Jersey dbr:Continuation
owl:sameAs
dbpedia-fr:Pile_spaghetti dbpedia-ja:スパゲッティスタック yago-res:Parent_pointer_tree wikidata:Q1453551 freebase:m.06jqw1 n20:U1X3 dbpedia-sr:Špageti_stek
dbp:wikiPageUsesTemplate
dbt:Mvar dbt:Reflist
dbo:thumbnail
n7:Spaghettistack.svg?width=300
dbo:abstract
Une pile spaghetti (ou pile cactus, pile saguaro ou in-tree) en informatique est un arbre enraciné N-aire dans lequel les nœuds fils ont un pointeur vers leur nœud père (mais pas l'inverse). Lors d'un parcours d'un nœud feuille en suivant ses ancêtres vers le nœud racine, la structure est semblable à une pile en liste chaînée. En effet, chaque nœud a un seul pointeur vers le nœud "suivant" (père), et ignore si ce père a d'autres enfants. Ni lui ni le père ne peut explorer les autres enfants, puisqu'il n'y a pas de pointeurs descendants. Par exemple, le compilateur d'un langage tel que C crée une pile spaghetti lorsqu'il ouvre et referme des tables de symboles représentant la portée de chaque bloc. Quand un nouveau bloc est ouvert, une table de symboles est empilée. À la fin du bloc, la portée est refermée et la table de symbole est dépilée. Toutefois cette table est conservée et non détruite, et son nœud conserve un lien vers celui de la table "parente". Ainsi lorsque le compilateur effectuera la traduction de l'arbre syntaxique abstrait, pour toute expression il pourra obtenir la table de symbole correspondant à l'environnement de l'expression, et résoudre les références des identifiants. Pour une variable X au sein de l'expression, on recherche X dans la table feuille (représentant la portée la plus intérieure), puis dans son parent, puis dans son grand-parent récursivement. In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti stack, cactus stack or sahuaro stack (after the sahuaro, a kind of cactus). Parent pointer trees are also used as disjoint-set data structures. The structure can be regarded as a set of singly linked lists that part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node. スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。 スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。 例えばC言語のようなコンパイラはブロックスコープ表現がシンボルテーブルを開閉するようなスパゲッティスタックを作る。新たなブロックスコープが開かれた時、シンボルテーブルはスタックにプッシュされる。閉じ中括弧が検出されたとき、スコープは閉じられ、シンボルテーブルがポップされる。しかしシンボルテーブルは破壊されるのではなく記憶される。そしてもちろんスタックは親のシンボルテーブルなども記憶している。そのためコンパイラが抽象構文木についてあとで翻訳を行うとき、与えられた任意の表現に対してスパゲッティスタックはその表現の環境で表現するシンボルテーブルを呼び出すことができ、識別子への参照を解決することが出来る。もし表現が変数Xを参照するときは、それは最も内部の静的スコープを表現する葉のシンボルテーブルをまずシークし次にその親のシンボルテーブルをシークしていく。 類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。
gold:hypernym
dbr:Structure
prov:wasDerivedFrom
wikipedia-en:Parent_pointer_tree?oldid=1092029872&ns=0
dbo:wikiPageLength
4203
foaf:isPrimaryTopicOf
wikipedia-en:Parent_pointer_tree