Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2632a3a

Browse files
nari0shotatrekhleb
authored andcommitted
Add Japanese translation (trekhleb#1) (trekhleb#337)
* add japanese translation* fix typo
1 parent5c12f45 commit2632a3a

File tree

14 files changed

+323
-7
lines changed

14 files changed

+323
-7
lines changed
Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
#双方向リスト
2+
3+
コンピュータサイエンスにおいて、**双方向リスト**はノードと呼ばれる一連のリンクレコードからなる連結データ構造です。各ノードはリンクと呼ばれる2つのフィールドを持っていて、これらは一連のノード内における前のノードと次のノードを参照しています。最初のノードの前のリンクと最後のノードの次のリンクはある種の終端を示していて、一般的にはダミーノードやnullが格納され、リストのトラバースを容易に行えるようにしています。もしダミーノードが1つしかない場合、リストはその1つのノードを介して循環的にリンクされます。これは、それぞれ逆の順番の単方向のリンクリストが2つあるものとして考えることができます。
4+
5+
![Doubly Linked List](https://upload.wikimedia.org/wikipedia/commons/5/5e/Doubly-linked-list.svg)
6+
7+
2つのリンクにより、リストをどちらの方向にもトラバースすることができます。双方向リストはノードの追加や削除の際に、片方向リンクリストと比べてより多くのリンクを変更する必要があります。しかし、その操作は簡単で、より効率的な(最初のノード以外の場合)可能性があります。前のノードのリンクを更新する際に前のノードを保持したり、前のノードを見つけるためにリストをトラバースする必要がありません。
8+
9+
##基本操作の擬似コード
10+
11+
###挿入
12+
13+
```text
14+
Add(value)
15+
Pre: value is the value to add to the list
16+
Post: value has been placed at the tail of the list
17+
n ← node(value)
18+
if head = ø
19+
head ← n
20+
tail ← n
21+
else
22+
n.previous ← tail
23+
tail.next ← n
24+
tail ← n
25+
end if
26+
end Add
27+
```
28+
29+
###削除
30+
31+
```text
32+
Remove(head, value)
33+
Pre: head is the head node in the list
34+
value is the value to remove from the list
35+
Post: value is removed from the list, true; otherwise false
36+
if head = ø
37+
return false
38+
end if
39+
if value = head.value
40+
if head = tail
41+
head ← ø
42+
tail ← ø
43+
else
44+
head ← head.next
45+
head.previous ← ø
46+
end if
47+
return true
48+
end if
49+
n ← head.next
50+
while n = ø and value !== n.value
51+
n ← n.next
52+
end while
53+
if n = tail
54+
tail ← tail.previous
55+
tail.next ← ø
56+
return true
57+
else if n = ø
58+
n.previous.next ← n.next
59+
n.next.previous ← n.previous
60+
return true
61+
end if
62+
return false
63+
end Remove
64+
```
65+
66+
###逆トラバース
67+
68+
```text
69+
ReverseTraversal(tail)
70+
Pre: tail is the node of the list to traverse
71+
Post: the list has been traversed in reverse order
72+
n ← tail
73+
while n = ø
74+
yield n.value
75+
n ← n.previous
76+
end while
77+
end Reverse Traversal
78+
```
79+
80+
##計算量
81+
82+
##時間計算量
83+
84+
| Access| Search| Insertion| Deletion|
85+
| :-------:| :-------:| :-------:| :-------:|
86+
| O(n)| O(n)| O(1)| O(n)|
87+
88+
###空間計算量
89+
90+
O(n)
91+
92+
##参考
93+
94+
-[Wikipedia](https://en.wikipedia.org/wiki/Doubly_linked_list)
95+
-[YouTube](https://www.youtube.com/watch?v=JdQeNxWCguQ&t=7s&index=72&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/doubly-linked-list/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computer science, a**doubly linked list** is a linked data structure that
89
consists of a set of sequentially linked records called nodes. Each node contains
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
#ハッシュテーブル
2+
3+
コンピュータサイエンスにおいて、**ハッシュテーブル**（ハッシュマップ)は*キーを値にマッピング*できる*連想配列*の機能を持ったデータ構造です。ハッシュテーブルは*ハッシュ関数*を使ってバケットやスロットの配列へのインデックスを計算し、そこから目的の値を見つけることができます。
4+
5+
理想的には、ハッシュ関数は各キーを一意のバケットに割り当てますが、ほとんどのハッシュテーブルは不完全なハッシュ関数を採用しているため、複数のキーに対して同じインデックスを生成した時にハッシュの衝突が起こります。このような衝突は何らかの方法で対処する必要があります。
6+
7+
![Hash Table](https://upload.wikimedia.org/wikipedia/commons/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg)
8+
9+
チェイン法によるハッシュの衝突の解決例
10+
11+
![Hash Collision](https://upload.wikimedia.org/wikipedia/commons/d/d0/Hash_table_5_0_1_1_1_1_1_LL.svg)
12+
13+
##参考
14+
15+
-[Wikipedia](https://en.wikipedia.org/wiki/Hash_table)
16+
-[YouTube](https://www.youtube.com/watch?v=shs0KM3wKv8&index=4&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/hash-table/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computing, a**hash table** (hash map) is a data
89
structure which implements an*associative array*
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
#ヒープ (データ構造)
2+
3+
コンピュータサイエンスにおいて、*ヒープ*は特殊な木構造のデータ構造で、後述するヒープの特性を持っています。
4+
5+
*最小ヒープ*では、もし`P`が`C`の親ノードの場合、`P`のキー(値)は`C`のキーより小さい、または等しくなります。
6+
7+
![MinHeap](https://upload.wikimedia.org/wikipedia/commons/6/69/Min-heap.png)
8+
9+
*最大ヒープ*では、`P`のキーは`C`のキーより大きい、もしくは等しくなります。
10+
11+
![Heap](https://upload.wikimedia.org/wikipedia/commons/3/38/Max-Heap.svg)
12+
13+
ヒープの「トップ」のノードには親ノードが存在せず、ルートノードと呼ばれます。
14+
15+
##参考
16+
17+
-[Wikipedia](https://en.wikipedia.org/wiki/Heap_(data_structure))
18+
-[YouTube](https://www.youtube.com/watch?v=t0Cq6tVNRBA&index=5&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/heap/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computer science, a**heap** is a specialized tree-based
89
data structure that satisfies the heap property described
Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
#リンクリスト
2+
3+
コンピュータサイエンスにおいて、**リンクリスト**はデータ要素の線形コレクションです。要素の順番はメモリ内の物理的な配置によっては決まりません。代わりに、各要素が次の要素を指しています。リンクリストはノードのグループからなるデータ構造です。最も単純な形式では、各ノードはデータとシーケンス内における次のノードへの参照(つまり、リンク)で構成されています。この構造はイテレーションにおいて任意の位置へ要素を効率的に挿入、削除することを可能にしています。より複雑なリンクリストではリンクをさらに追加することで、任意の要素の参照から要素を効率的に挿入、削除することを可能にしています。リンクリストの欠点はアクセスタイムが線形である(そして、パイプライン処理が難しい)ことです。ランダムアクセスのような高速なアクセスは実現不可能です。配列の方がリンクリストと比較して参照の局所性が優れています。
4+
5+
![Linked List](https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg)
6+
7+
##基本操作の擬似コード
8+
9+
###挿入
10+
11+
```text
12+
Add(value)
13+
Pre: value is the value to add to the list
14+
Post: value has been placed at the tail of the list
15+
n ← node(value)
16+
if head = ø
17+
head ← n
18+
tail ← n
19+
else
20+
tail.next ← n
21+
tail ← n
22+
end if
23+
end Add
24+
```
25+
26+
```text
27+
Prepend(value)
28+
Pre: value is the value to add to the list
29+
Post: value has been placed at the head of the list
30+
n ← node(value)
31+
n.next ← head
32+
head ← n
33+
if tail = ø
34+
tail ← n
35+
end
36+
end Prepend
37+
```
38+
39+
###検索
40+
41+
```text
42+
Contains(head, value)
43+
Pre: head is the head node in the list
44+
value is the value to search for
45+
Post: the item is either in the linked list, true; otherwise false
46+
n ← head
47+
while n != ø and n.value != value
48+
n ← n.next
49+
end while
50+
if n = ø
51+
return false
52+
end if
53+
return true
54+
end Contains
55+
```
56+
57+
###削除
58+
59+
```text
60+
Remove(head, value)
61+
Pre: head is the head node in the list
62+
value is the value to remove from the list
63+
Post: value is removed from the list, true, otherwise false
64+
if head = ø
65+
return false
66+
end if
67+
n ← head
68+
if n.value = value
69+
if head = tail
70+
head ← ø
71+
tail ← ø
72+
else
73+
head ← head.next
74+
end if
75+
return true
76+
end if
77+
while n.next != ø and n.next.value != value
78+
n ← n.next
79+
end while
80+
if n.next != ø
81+
if n.next = tail
82+
tail ← n
83+
end if
84+
n.next ← n.next.next
85+
return true
86+
end if
87+
return false
88+
end Remove
89+
```
90+
91+
###トラバース
92+
93+
```text
94+
Traverse(head)
95+
Pre: head is the head node in the list
96+
Post: the items in the list have been traversed
97+
n ← head
98+
while n != ø
99+
yield n.value
100+
n ← n.next
101+
end while
102+
end Traverse
103+
```
104+
105+
###逆トラバース
106+
107+
```text
108+
ReverseTraversal(head, tail)
109+
Pre: head and tail belong to the same list
110+
Post: the items in the list have been traversed in reverse order
111+
if tail != ø
112+
curr ← tail
113+
while curr != head
114+
prev ← head
115+
while prev.next != curr
116+
prev ← prev.next
117+
end while
118+
yield curr.value
119+
curr ← prev
120+
end while
121+
yield curr.value
122+
end if
123+
end ReverseTraversal
124+
```
125+
126+
##計算量
127+
128+
###時間計算量
129+
130+
| Access| Search| Insertion| Deletion|
131+
| :-------:| :-------:| :-------:| :-------:|
132+
| O(n)| O(n)| O(1)| O(n)|
133+
134+
###空間計算量
135+
136+
O(n)
137+
138+
##参考
139+
140+
-[Wikipedia](https://en.wikipedia.org/wiki/Linked_list)
141+
-[YouTube](https://www.youtube.com/watch?v=njTh_OwMljA&index=2&t=1s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/linked-list/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
55
[_Русский_](README.ru-RU.md),
6-
[_Português_](README.pt-BR.md)
6+
[_Português_](README.pt-BR.md),
7+
[_日本語_](README.ja-JP.md)
78

89
In computer science, a**linked list** is a linear collection
910
of data elements, in which linear order is not given by
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
#優先度付きキュー
2+
3+
コンピュータサイエンスにおいて、**優先度付きキュー**は通常のキューやスタックのデータ構造と似た抽象データ型ですが、各要素に「優先度」が関連づけられています。優先度付きキューでは優先度の高い要素が優先度の低い要素よりも先に処理されます。もし2つの要素が同じ優先度だった場合、それらはキュー内の順序に従って処理されます。
4+
5+
優先度付きキューは多くの場合ヒープによって実装されていますが、概念的にはヒープとは異なります。優先度付きキューは「リスト」や「マップ」のような抽象的な概念です。リストがリンクリストや配列で実装できるのと同様に、優先度付きキューはヒープや未ソート配列のような様々な方法で実装することができます。
6+
7+
##参考
8+
9+
-[Wikipedia](https://en.wikipedia.org/wiki/Priority_queue)
10+
-[YouTube](https://www.youtube.com/watch?v=wptevk0bshY&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=6)

‎src/data-structures/priority-queue/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computer science, a**priority queue** is an abstract data type
89
which is like a regular queue or stack data structure, but where
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
#キュー
2+
3+
コンピュータサイエンスにおいて、**キュー**は特定の種類の抽象データ型またはコレクションです。コレクションの中のエンティティは順番に並べられており、コレクションに対する基本的な（または唯一の)操作は末尾にエンティティを追加するエンキューと、先頭からエンティティを削除するデキューがあります。これにより、キューは先入れ先出し(FIFO)のデータ構造となります。FIFOのデータ構造では、キューに追加された最初の要素が最初に削除されます。これは、新しい要素が追加されたら、その要素を削除するにはそれまでに追加された全ての要素が削除されなければならないという要件と同じです。多くの場合、ピークのような先頭の要素を検査する操作も備えていて、これはデキューせずに先頭の要素の値を返します。キューは線形のデータ構造や、より抽象的なシーケンシャルなコレクションの一例です。
4+
5+
FIFO(先入れ先出し)のキュー
6+
7+
![Queue](https://upload.wikimedia.org/wikipedia/commons/5/52/Data_Queue.svg)
8+
9+
##参考
10+
11+
-[Wikipedia](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))
12+
-[YouTube](https://www.youtube.com/watch?v=wjI1WNcIntg&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=3&)

‎src/data-structures/queue/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computer science, a**queue** is a particular kind of abstract data
89
type or collection in which the entities in the collection are
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
#スタック
2+
3+
コンピュータサイエンスにおいて、**スタック**は抽象データ型で、2つの主要な操作ができる要素のコレクションです。
4+
5+
***プッシュ**はコレクションに要素を追加します。
6+
***ポップ**は最近追加された要素でまだ削除されていないものを削除します。
7+
8+
要素がスタックから外れる順番から、LIFO(後入れ先出し)とも呼ばれます。スタックに変更を加えることなく、先頭の要素を検査するピーク操作を備えることもあります。「スタック」という名前は、物理的な物を上に積み重ねていく様子との類似性に由来しています。一番上の物を取ることは簡単ですが、スタックの下の方にあるものを取るときは先に上にある複数の物を取り除く必要があります。
9+
10+
プッシュとポップの例
11+
12+
![Stack](https://upload.wikimedia.org/wikipedia/commons/b/b4/Lifo_stack.png)
13+
14+
##参考
15+
16+
-[Wikipedia](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))
17+
-[YouTube](https://www.youtube.com/watch?v=wjI1WNcIntg&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=3&)

‎src/data-structures/stack/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@
22

33
_Read this in other languages:_
44
[_简体中文_](README.zh-CN.md),
5-
[_Русский_](README.ru-RU.md)
5+
[_Русский_](README.ru-RU.md),
6+
[_日本語_](README.ja-JP.md)
67

78
In computer science, a**stack** is an abstract data type that serves
89
as a collection of elements, with two principal operations:

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp