* アルゴリズムとデータ構造 [#p8c4a8bb] この頁の解説貧弱すぎwwなめてんだろwww~ と思った奴は何か書いてくれ #contents * アルゴリズム [#v958b98c] 問題を解くための手順をアルゴリズムと呼ぶ。~ 但し、アルゴリズムと呼ばれるためには以下の条件を満たさなければならない。 ・問題を解く上で正しいこと。 ・手順が具体的に示されていること。 つまり、コンピュータで実行可能なように、曖昧さがなく記述されていること。 ・有限の実行時間で、必ず終了すること。 ** 探索 [#i297b629] *** 線形探索 [#oc5e463b] 英語ではリニアサーチ。~ 何のひねりもなく、先頭から末尾まで探していくだけのサーチです。~ データが多くなると遅くなりがちですが、何の前提条件も無く使える手軽さが利点です。~ シンプルなので、要素の数が10個前後の小規模な配列に対してはかえって高速だったりします。~ 例:C言語(配列のアドレスとサイズを渡し、numと一致する要素の添字を返す)~ int linear_search(int *array, unsigned int size, int num){ int i; for(i = 0; i < size; i++){ if(array[i] == num) return i; } return -1; } 配列の要素数が増えれば増えただけ探索に時間がかかるようになります。~ 要素数10000の配列は、要素数10の配列の1000倍時間がかかるわけです。~ このように、データ量と処理時間が単純に比例して増える事を「線形時間」とかO(n)とか表現したりします。~ 1番時間がかかるのは探しているデータが存在しない場合で、1番時間がかからないのは、先頭にあった場合です。~ *** 二分探索 [#qce356fb] 英語ではバイナリサーチ。~ 整列済みの要素群に対して実行します。 性質上、再帰を用いて実装される場合が多いです。~ 例:C言語(配列のアドレスとサイズを渡し、numと一致する要素の添字を返す。配列はbegin側が小さい値になる順で並んでる) int binarysearch(int * array , unsigned int size , int num) { int begin = 0; int end = size - 1; int center; while(1) { //無限ループ center = (begin + end) / 2; if(array[center] >= num) { //numは中間より前にある(もしくは一致している if(array[center] == num) { return center; } //←発見! end = center - 1; } else { //numは中間より後にある begin = center + 1; } if(begin > end) return -1; //探す範囲が無くなってしまった } } 整列の中央と探索対象を比較すると、その結果で整列の 左側あるいは右側だけに候補を絞ることができます。~ そして、その搾られた候補に対して同じ要領で中央の値との比較と候補の絞り込みを繰り返していくと~ いずれある時の中央の値あるいはただひとつに絞られた候補として 探索対象が現れます(整列に探索対象があれば) 要素数1の時の処理時間を基準にすると、要素数4でも3倍、8でも4倍、16でも5倍……みたいな感じで増加が緩やかです。~ 1回の比較で、探索候補の半分を振るい落とせるためです。~ このように、データ量が倍に増えても処理時間は緩やかにしか増えない事を「対数時間」とかO(log n)とか表現したりします。 線形探索のO(n)と比べるとデータ量の増加に強いものの、処理が少々複雑なため~ 要素が少ないうちは線形探索よりも遅かったりしますが、総合的にはこちらの方が断然速いと言えます。 ** 整列 [#h84db045] *** ボゴソート [#h92fd60b] 世間にはあまり知られておらず、専門書にもまず載っていないが、~ 他のソートアルゴリズムに比べ極めて分かり易いアルゴリズムであり、~ 訓練をすれば猿はおろか犬でも習得できる。~ 要素をランダムに並べ替え、順番に並んでるかを確認し、もう一度ランダムに並べ替える。~ この操作をソートが完了するまで行う。~ 運がよかったら一発で終了するがそうでない場面の方が圧倒的に多く、乱数によっては永遠に終わらない可能性もある。~ ソートが終了するかかどうかは「無限の猿定理」でぐぐると幸せになれるかも。~ ~ 所謂ツンデレソート。「一回で終わるわよこんなソート!」~ 一回で終わったためしがなく、バブルソートよりはるかに遅い。~ 計算時間はO(n*n!)~ ~ ***バブルソート [#c164d24f] 初心者の坊や達を優しくソートの世界に導いてくれる方。~ とても素直だけど、遅いので実戦の場に出ず教育者として活躍しています。 例:C言語 void bubble_sort(int *array, unsigned int size){ int i, j, t; for(i = 0; i < size; i++){ for(j = size - 1; j > i; j--){ if (array[j] < array[j - 1]){ t = array[j]; array[j] = array[j - 1]; array[j - 1] = t; } } } } 隣り合ってる要素を比べて、並べたい順番になってなかったら入れ替える、という操作を繰り返すわけです。~ 要素が正しい位置に泡のように登っていくのでバブルソートと名付けられました。~ 単純ですが無駄な比較が多く、遅いです。 ***シェーカーソート [#eaad47d0] バブルソートの親戚。~ 挟みこむような動きで少しだけ無駄を減らす事に成功しました。~ カクテルソート等とも呼ばれます。 オシャレですね。~ バブルソートで走査中、最後に入れ替えがあった位置よりも後ろは、綺麗に並んでる事がわかります。~ つまり、最後に入れ替えがあった位置を記録し、次からはそれ以降を無視すれば少し無駄が少なくなるわけです。~ そこで更に、前方後方と交互に走査すれば、両方から範囲を狭める事が出来るので少しだけ効率が良くなるのです。~ %%ぶっちゃけ大して変わらないとか言うな。%% ***コムソート [#d6da5661] バブルソートの親戚。~ 色々な大きさの櫛を駆使します。~ 隣同士ではなく、まず適当に大きな間隔を開けて比較・交換をします。~ どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間隔が無くなり、隣同士を交換するようになります。~ この隣同士の交換が終わった時、既にちゃんと整列出来てしまっています。~ ずっと細かく見ていくよりも、最初は大雑把にやった方が効率が良いという事らしいです。~ 飛び飛びに揃えていくのが髪をとかす櫛(コム)のように見えるからこの名前がつきました。~ ***挿入ソート [#b78ed62f] 手当たり次第に突っ込む単純な子ですが、状況次第ではなかなかの速さ。~ 大変に開放的な性格です。~ 例:C言語~ void insertion_sort(int *array, unsigned int size){ for (i = 1; i <size ; i++) { for (j = i; j > 0 && array[j-1] > array[j] ; j--) {swap(data[j-1] , data[j]); } //要素の交換 } 前から順に見ていき、要素を正しい位置に挿入していきます。~ この「挿入」の操作そのものは、バブルソートと同じような要領です。離れた位置に挿入する程、比較や交換の回数が多くなります。~ 動きとしては、配列の前部に 整列したデータがどんどん溜まっていくような感じです。~ ほとんど整列済みのデータなら離れた所まで挿入する事が少なくなるので、かなり高速になります。 *** シェルソート [#ua3da88b] 挿入ソートの親戚。~ やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする賢さがあります。~ 別に貝殻が好きというわけではなく、Shellさんが開発しただけだったりする。~ 挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので~ 「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。~ 具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。 *** 選択ソート [#t69c50e9] 馬鹿ソートとか言われたりするけど気にしない明るい子。~ とりあえず一番小さいのを探し続ければそのうち揃うよね! 配列を走査し、最も小さい(ソート後に端に来る)データを見つけてから、それを1番最初のデータと交換します。~ そして、2番目の小さいデータ、3番目に小さいデータ、と次々に処理していきます。~ 最後の1個を見るまで「一番小さい」かどうかはわからないため、結局全部見ていく事になり、大して効率は良くありません。~ 交換回数は少ないため、バブルソートよりは高速と言えます。 *** クイックソート [#h788cb12] 最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん~ スレンダーな子です~ 複雑と思われがちですが、実は意外と単純です。~ まず配列から一番後ろの要素Aを取り出して、それぞれの要素がAより小さいければ前、大きければ後、と振り分けます。~ 次にAより前に振り分けられた部分の最後の要素Bを取り出して、Aより前に振り分けられた部分の中で、Bより小さければ前、大きければ後、と振り分けて行きます。 ~ このように最後の要素を取り出し、それを基準として前後に振り分けて行くのがクイックソートです *** マージソート [#y34cbfeb] いつも手を抜くことなく、速さを常に追求する努力家~ クイックソートには負け越しているのをくやしがっている~ 他の子より大きいのが悩み~ まず、配列を真っ二つに分けます。 分かれて出来た2つの配列を、更にそれぞれ真っ二つにします。~ これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。~ 分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。~ マージして出来た配列を更にマージしていって、最後にたった1つの配列になった時、ソートが完了しています。~ 綺麗に並んだ配列2つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。~ (1,4,5)と(2,3,6)なら、まず左端の1と2だけを、次は4と2だけを……という風に。~ マージに余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの1つです。 それだけじゃクイックソート使えばいいじゃないかとなりますが、こちらは速度が安定しています。~ 外部記憶が必要なくらい大きなソートをする場合クイックソートよりもこちらを使うことのほうが多いです。~ また、安定ソートでもあります。 なんとなく堅牢なイメージがありますね。 *** バケットソート [#b490822c] 他にもビンソートとか色々あだ名がある。~ 趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで~ 秘めたポテンシャルを発揮出来ずにいる。 「0~100点のテストの点数をソートするんなら、101個のバケツを並べてぶちこんで順に取りだしゃいいじゃん!」~ という事をマジでやるというトンでもなく豪快なソートです。~ 比較と入れ替えを繰り返すものが多いソートの中で、非常に独特な性質を持っています。 まず、データがいくら増えようと「バケツに入れる」という操作の回数が単に増えていくだけなので、なかなか重くなりません。~ (データ量が千倍になればクイックソートでも大体1万倍重くなりますが、バケットソートは、単に千倍です)~ 非常に速いソートですが、当然弱点があり「バケツを用意するために大量のメモリが必要」なのです。~ 例に出した0~100の範囲ならまだいいのですが、32bitのint型で表現出来る全ての数をソートしようとしたなら~ 範囲は-2,147,483,648~2,147,483,647という事で、4294967296個のバケツが必要になります。~ また、ソートしたいデータに同じ数値が重複してる場合があります(テストで同じ70点を取った子が何人もいたとか)から~ バケツは単純な配列として用意する事は出来ません。配列には1つのデータしか入れられないのです。~ 大抵はリンクリストの配列みたいな実装になるのですが、リンクリストにも余分なメモリが必要なので更に酷くなります。 このように、使うための条件は厳しいものの、クイックソートよりも高速に処理出来たりなどロマンが溢れるソートです。 *** 分布数えソート [#r779f37a] バケットソートの親戚。~ 一応バケットソートよりはマシなものの、やはり家が崩壊しがち。 バケットソートはリンクリストを使った実装だと 動的なメモリの確保や条件分岐が頻繁に起こり、折角の速度が出せません。~ なので、もっと上手い方法は無いのか、という事で考え出されたものがこれです。 まず、以下のようなデータがあったとします。 0 1 2 0 0 3 1 2 0 2 2 0 これを昇順にソートすると 0 0 0 0 0 1 1 2 2 2 2 3 このようになるわけですが、最も左を「0番目」として数えると~ 0は0番目から、1は「0の個数(5)」である5番目から、2は「0の個数(5)+1の個数(2)」である7番目から~ 3は「0の個数(5)+1の個数(2)+2の個数(4)」である11番目から始まっている事がわかります。 これを利用し「何番目から始まるか」という数だけをバケツに入れれば、リストでなく単なる配列で実装でき~ 同じ数値が重複してても、その要素を処理するたびに「何番目から始まるか」のバケツを+1していくだけで対処出来ます。~ このような実装をすれば リンクリストのための余分なメモリも、その確保にかかる時間も、分岐も、少なく済むため高速なのです。~ ただし、要素の数を数えるための走査と 実際にソートをするための走査で、合計2回の走査が必要になるため~ ソートしようとしているデータの規模によってはかえって低速かもしれません。~ (リンクリスト用のメモリの動的確保や分岐は結構重いので、測ってみると大抵はこちらの方式の方が速かったりしますが) *** 基数ソート [#od200194] バケットソートの友人。 英語にするとラディックスソート。~ 極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている~ しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。 基数というのは数を表す際に基本となるまとまりの事で、例えば「○進数」の○の部分です。~ 1桁目、2桁目、3桁目のように桁ごとにソートしても、順番さえ保存されてれば上手い事揃う、という事を利用するソートです。 以下のようなデータがあったとします。 19 70 35 48 24 14 40 これを1桁目だけに注目して、小さい方を左に来るようにソートすると 70 40 14 24 35 48 19 更に、この順番をなるべく保ったまま2桁目だけに注目してソートすると 14 19 24 35 40 48 70 このように、結果的に綺麗に揃っており、これは3桁に増えようと、10進数でなかろうと適用出来ます。 例えば、バケットソートで0~9999の範囲を整列せねばならなくなった場合、本来なら10000個のバケツを用意するわけですが~ これを利用して「下2桁を基準にソート→上2桁を基準にソート」とすれば、なんと100個のバケツで済むわけです。~ 当然、分けただけソートの回数は増えますし、分ける事そのものにいくらか時間がかかりますので(割り算したり剰余を取ったり)~ バケットソートほどの速度は出ないのですが、それでも十分速かったりします。~ 速度を求めるなら割り算や剰余ではなく、CPU的にキリの良い2のべき乗で区切ってシフトやマスクを駆使すればなお良し。 「桁ごとに区切っても揃う」という原理は別にバケットソートでなくても通用するのですが~ その他のソートだと単に処理の回数を増やすだけで何の利点も無いので、大抵バケットソートの改良版として紹介されます。~ 「バケットソートは超速いけど、メモリ喰いすぎるのがちょっと……」という方にお勧め。~ 範囲さえある程度絞れるならクイックソートよりも普通に高速に実装出来ます。~ 工夫次第で負の数を含んでたり浮動小数を扱ったりする場合にも対応出来ます。 *** 逆写像ソート [#pfbe4b79] バケットソートの親戚。~ 一見、数学的で難解な事を考えていそうな雰囲気ですが、割と豪快な性格です。 写像とは小難しそうな数学用語ですが、「2つの数字の集まりを対応させる」というだけの単純な概念です。~ 添字を入れると要素が出てくる配列も 添字→要素の写像と言えます。~ 「逆写像」というと、その逆になり、要素→添字という写像になるわけですが~ そういう配列=バケツと考えると、実の所それはただのバケットソートという事になります。 バケットソートとの違いは「値が同じ要素があった時の対処」の部分だけで、事実上それだけが逆写像ソートのアイデンティティです。~ その対処の仕方とは「添字をポインタ代わりに使ってリンクリストのようなものを作る」というもので~ リンクリストでいう next に対応する添字の値を確保するため、ソートする配列と同じサイズのnextの配列を用意するのです。~ この配列のおかげで、バケツに1つの要素しか入れる必要が無くなっているのがポイント。~ ぶっちゃけバケットソートや分布数えソートを使えば済むので、知ってる人すら少ないマニアックなソートです。 *** 奇遇転置ソート [#f9f10dce] バブルソートの親戚。~ チームプレーや流れ作業が得意な方。 バブルソートは隣合った要素を比較、交換していくので~ 「1 2」「2 3」「3 4」を添字として処理していくわけですが~ 奇遇転置ソートは「1 2」「3 4」「5 6」のような「奇数 偶数」要素を処理と~ 「2 3」「4 5」「6 7」のような「偶数 奇数」要素の処理を交互に行う、というような動きをします。 処理の回数そのものはバブルソートと大して変わらないのですが~ ポイントは「1 2」「2 3」 だと「2」が かぶってますが「1 2」「3 4」だと何もカブらない、という点です。~ つまり1回1回の処理が独立しているため、複数のCPUを使って並列に処理しやすいのです。~ いくら大量にCPUがあっても、走っているスレッドが1つだけなら1個分の性能しか出せません。~ CPUを増やせば増やしただけ速く出来るという限界の高さに並列処理の価値があるわけです。 逆に言えば、並列処理が出来る環境でなければ大して役に立たないソートです。 *** シェアソート [#ya8737c6] 共有のソート。~ 部下を団結させ、隊列を整えるチームワークを発揮させるやり手の指揮官です。~ 一次元の住人が多いソート業界では珍しい二次元の世界の住人です。 まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じに分割します。~ そして1行目[1][i] 2行目[2][i] 3行目[3][i]……のように各行別々にソートするのと~ 1列目[i][1] 2列目[i][2]……のように各列別々にソートするのを交互に行っていきます。~ 各行や列は、それぞれ独立しているので、並列に処理が出来ます。~ 「奇数行は左が小さくなるように、偶数行は、右が小さくなるようにソート」~ 「列は、上が小さくなるようにソート」~ これを交互に繰り返す事で、小さい値は左右にクネクネ動きながら上に登っていきます。かなりトリッキー。 ちなみに、各行に対して行うソートは何を使ってもいいですが~ 奇遇転置ソートやマージソート等を使うと並列性を更に上げられるでしょう。~ 複数のCPUを搭載している状態なら、かなりの速度向上が期待出来ます。~ もちろん、並列処理が出来る環境でなければ、さほどのスピードは出ません。 *** バイトニックソート [#ud51908c] 究極のスピードを誇っているものの、力を出しすぎると地球が吹き飛ぶため本気を出せない。~ が・・・あ・・・離れろ・・・死にたくなかったら早く俺から離れろ!!~ 理論上最高の速度が出るソートですが、やってる事は凄く単純で~ if や else等の分岐を大量に使って最小限の回数の比較、交換しかしない、というだけのものだったりします。~ 性質上、ソートする配列のサイズがわかってて、しかも極端に要素が少ないものにしか使えません。~ 要素の数が4つだけの場合でも使うifやelseの数は数十個に及び、6つを超えたあたりで百を超えます。~ 書くのが異様に面倒なので、実際に使いたいなら そういうコードを生成するジェネレータを作りましょう。~ また、当然実行ファイルのサイズも爆発的に増えていきます。 ~ 何億回もソートを繰り返すような処理が必要でなければコストに見合ったリターンは得られないソートです。 ※どうやら上記のソートは本来の(?)バイ・トニックソートとは違うもののようです。~ 本格的なバイ・トニックソートは、むしろマージソートに近く、並列処理なんかに使われるものなんだとか。~ 正確な情報はちょっと持ってないので、知ってる人は編集してくだしあ>< *** 安定ソートと、そうでないソート [#h37e2e26] 等価なデータの順番がソート前と同じという事が保証されているソートの事を「安定ソート」と呼びます。~ 言葉にすると難しいですので例を出しましょう。 例えば、このようなデータがあるとします。~ データ 「A:50」「B:20」「C:80」「D:20」「E:60」 これを「数字だけを基準に、小さい方が左に来るようにソート」すると 結果1 「B:20」「D:20」「A:50」「E:60」「C:80」 結果2 「D:20」「B:20」「A:50」「E:60」「C:80」 このどちらかになる事が予想出来ますが~ 安定ソートだと「元々Bの方が左にあった」という事で、必ず結果1になります。~ クイックソート等の安定でないソートを用いると、結果1になるか結果2になるかは全くわかりません。~ 「そんなのどうでもいいから速いほうがいいよ」という場合にクイックソートを使い、順番が重要な時は安定なソートを使うわけです。 多くのソートが安定ですが~ コムソート シェルソートなどの間隔を開けて処理をするソートや~ クイックソート等は、安定でないソートとして知られています。 安定と言われているソートでも、実装の仕方によっては安定でなくす事も出来てしまいますが~ あえて安定にしない事で得するような事はあまり無いです。~ また、基数ソートのように安定なバケットソートを利用しないと実現出来ないものもあります。 * データ構造 [#wc0c038f] ** 配列 [#p0a42e9d] 気にしたことないだろうけど、配列も立派なデータ構造なんだぜ。~ 重要なことは、多くの言語やその処理系でO(1)のアクセススピードが保証されてるってこと。~ つまり、ほかのデータ構造に比べて単純な分、早いんだなこれが。~ 馬鹿とはさみは使いようってやつだな。 ** スタック [#e04037cc] お菓子でいうとPEZ(ペッツ) 「干し草の山」の意。~ 名前の通り、新しいデータを上に積み上げていき、下に埋もれた古いデータを取り出すためには~ 上のデータを先に取り出さなければならない後入先出(あといれさきだし)の構造です。~ 「古いデータは取っておき、新しいデータに対して色々な処理をしてから利用する」ような場面で使われます。~ 例えば関数・メソッドの呼び出しの際に使われるコールスタックなんかが有名。~ ローカル変数は他の関数を呼び出してから戻ってくるまでずっと保存されてますが、それはスタック上にあるからなのです。 ** キュー [#x9b212e8] ところてんだよところてん 「待ち行列」の意。 名前の通り、古いデータは新しいデータの後ろに並び、新しいデータが出て行くまで取り出せません。~ 先入先出(さきいれさきだし)の構造です。~ 「先のデータの処理が終わるまで、後から来たデータにちょっと待ってもらう」ような場面で使われます。~ サーバーなんかは、すぐに処理出来ない大量のリクエストが来た場合のためのキューを持っているのが普通です。~ (優先度が高いリクエストはキューで待たせず割り込ませてあげるような機能もありがちです) ** デック [#gffe4778] Deque。 スタックとキューを合わせたような機能を持っています。~ 具体的には「前から入れる」「前から出す」「後から入れる」「後から出す」の全てが出来ます。~ 長所:両端へのデータ挿入がO(1) 添字アクセス可能~ 短所:要素の中央の挿入、削除が遅い 削除、挿入は平均すると動的配列より優れるが、単純なアクセスではやや劣る。 ** リスト [#n30cdd26] 連結リストとも呼ばれる非常に一般的なデータ構造の一種。~ ある箱を仮想的に考え、それと別のはことをつなぐようなイメージのデータ構造。~ 箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつかの種類に分かれる。~ 多くの言語では、箱と連結部分を一括して扱うために、構造体などを用いる。~ 最近のモダンな言語ではライブラリにリスト構造があらかじめ用意されている場合が多い。~ また、Lispなど「リスト構造ありき」で言語設計がなされているプログラム言語も少数ながら存在する。~ 似たようなデータ構造に配列が存在するが、N番目の要素にアクセスする時に必要な計算時間が、配列ではO(1)なのに対して、リストではO(N)かかるという点が大きく異なる。 従って、使用できるメモリーの割合や扱うデータの特性によっては、リストよりも配列を利用したほうが有効な場合もある。 *** 単方向リスト [#c3b02503] リストの要素同士を連結するとき、A→B→C→……のように、一方向のみの連結を利用する方法。~ このとき、例えばある要素を検索したい場合、現在の位置をAとすれば、Cを参照しするには、A→B→Cと順にたどっていけばいいが、現在の位置をCとしてBを検索するときにも、いったん現在位置をAに戻して、先頭から検索しなければならないという手間が生じる。(C→B→Aのように、逆順にはたどれない)~ 通常、リストといえばこちらを指す。~ 一方向への連結しかみないので管理が楽で、使用する領域も少なくて済み、デットリンク(リストの途中で無意味な場所を指している連結部分)を探すのも楽。~ 電話帳のように、前の要素に戻る必要が生じにくいデータの表現に適している。 *** 双方向リスト [#sf7d12f5] 単方向リストと異なり、逆順にも辿れるようにしたリスト。~ 単方向リスト同様、矢印表記を用いれば、A⇋B⇋C⇋D⇋……と表すことができる。~ 特徴は、ある要素Nへのアクセスオーダが必ずしもO(N)にならないことで、検索開始位置を現在の要素とすることで、O(N-現在の要素位置)の関係で要素にアクセスできる。~ 現在位置を覚えておきつつ、前後の要素にアクセスするようなデータの表現に適している。 *** 循環リスト [#wbdee299] 上記二つのリストのどちらとも併用できる連結方法で、リストの末尾の次の要素を、リストの先頭につなぐリストの作り方を言う。~ 通常、リストの末尾の次の要素は、NULL等の末端であることを明確に示すシンボルを指しているが、循環リストでは末尾が無くなるので、ある要素の次の要素に必ずアクセスできるようになる。~ 例えば、あるデータを検索するときに、末尾まで検索したら先頭要素から検索しなおすような場合、通常のリストでは末端に来た時には先頭に戻るような処理を書き加える必要があるが、循環リストではどのような場合に終了させるかを記述するだけで、検索処理自体には特別な末端処理を加えなくて良くなる。 ** 木 [#j0b14123] *** 二分木 [#d6d2cafb] *** ヒープ [#v35e1d11] ** ハッシュ表 [#f7c93b36] *** 連鎖法 [#l66cfcc0] *** オープンアドレス法 [#e44025a1] **その他 [#bbfb5391] ***最大公約数(GCD: greatest common divisor) [#i9b377e0] (ユークリッドの互除法)~ 紀元前300年頃には既に存在した、最古のアルゴリズム。~ 例 a0 = 497,a1 = 284とおく。 497 = 284 + a2 a2 = 213 284 = 213 + a3 a3 = 71 213 = 71 * 3 + a4 a4 = 0 つまり、497と284の最大公約数は71となる。 この計算手法をユークリッドの互除法と呼ぶ。 実装例:C言語 #include <stdio.h> int gcd(int a0, int a1) { int a, b, tmp; a = a0; b = a1; while (b != 0) { tmp = a % b; a = b; b = tmp; } return a; } 上記GCD関数用のテストコード int main(void) { int a0, a1, tmp; printf("一番目の整数を入力してね >> "); scanf("%d", &a0); printf("二番目の整数を入力してね >> "); scanf("%d", &a1); if (a0 <= 0 || a1 <= 0) { printf("0以下の数なんか入力すんなwww : %d, %d\n", a0, a1); exit(-1); // 異常終了 } if (a0 < a1) { // 関数GCDではa0 > a1と仮定しているので値を入れ替える tmp = a0; a0 = a1; a1 = tmp; } printf("%d と %d の最大公約数(GCD) = %d\n", a0, a1, gcd(a0, a1)); return 0; } ** 参考リンク [#d212128a] -[[C言語による最新アルゴリズム事典(Vevtor)>http://www.vector.co.jp/soft/data/prog/se002453.html]]~ 『C言語による最新アルゴリズム事典』全ソースコード~ -[[アルゴリズム演習300題(Vector)>http://www.vector.co.jp/soft/data/prog/se078278.html]]~ 「アルゴリズム演習300題」(日刊工業新聞社刊)のC言語による解答例~ -[[アルゴリズム系書籍ソース目次ファイル(Vector)>http://www.vector.co.jp/soft/data/prog/se269457.html]]~ Vectorで公開されている~ 『アルゴリズム演習300題』『C言語による最新アルゴリズム事典』用の目次ファイル~ -[[ソースコード探険隊 » アルゴリズムとデータ構造>http://www.codereading.com/algo_and_ds/]]~ データ構造の章では主に線形のデータ構造とグラフデータ構造を解説~ アルゴリズムの章では主に探索アルゴリズムと整列アルゴリズムを解説~ -[[Algorithm Collection>http://web.archive.org/web/20040208153438/http://alfin.mine.utsunomiya-u.ac.jp/~niy/algo/]]~ (web.archive)~ -[[Windowsプログラミング研究所 » ゲーム&その他>http://www13.plala.or.jp/kymats/study/game_other.html]]~ 実践(アルゴリズム中心)~ -[[京都大学OpenCourseWare » 工学部 » アルゴリズムとデータ構造入門 » 講義ノート>http://ocw.kyoto-u.ac.jp/faculty-of-engineering-jp/introduction-to-algorithm-and-data-structures/lecturenote]]~ -[[九州大学大学院システム情報科学研究院 金子研究室 Web ページ » アルゴリズムとデータ構造>http://www.db.is.kyushu-u.ac.jp/rinkou/algo/index.html]]~ -[[Fussyのホームページ > アルゴリズムの紹介>http://www2.starcat.ne.jp/~fussy/algo/index.htm]]~ -[[アルゴリズム - osdev-j (MMA)>http://wiki.osdev.info/index.php?%A5%A2%A5%EB%A5%B4%A5%EA%A5%BA%A5%E0]]~ -[[アルゴリズム辞典 [無料]>http://dir.kotoba.jp/ddcat.cgi?k=algorism&w=2&mL=&DC=100&LC=100&fsz=2]]~ -[[ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40>http://zapanet.info/blog/item/1145]]~ -[[技術計算用Cプログラム ソース>http://www5.airnet.ne.jp/tomy/cpro/csource.htm]]~ アルゴリズムをCソースプログラムと共に紹介、ダウンロード・サービス