Green with White Lines

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "Green with White Lines"

Transcription

1 各種コンテナの実装と性能 Qt #4 kikairoya

2 About 宮崎県都城市から来ました 本職 : 精密機械設計 組込機器開発 C++ とか出来ます Qt わかりません

3 Abstruct STL コンテナと Qt コンテナの比較 データ構造 パフォーマンス 安全性 インタフェース おまけで Boost コンテナも

4 STL Containers vector deque list/forward_list set/multiset map/multimap array unordered_set/unordered_multiset unordered_map/unordered_multimap

5 Qt Containers QVector QList QLinkedList QMap/QMultiMap QSet QHash/QMultiHash

6 Boost Containers vector/stable_vector deque list/slist set/multiset/flat_set/flat_multiset map/mutlimap/flat_map/flat_multiap array unordered_set/unordered_multiset unordered_map/unordered_multimap

7 Major Difference STL Container CoW しない 全ての操作が例外安全の基本保証を満たす Qt Container CoW を行う 例外安全に関しての規定が無い

8 std::vector QVector boost::container::vector 要素を連続的に格納するいわゆる 可変長配列 各要素のルックアップは定数時間 末尾に対する挿入 削除は償却定数時間 Stroustrup 曰く コンテナが必要な場合 特に理由が無ければ vector を使おう と std::vector<bool> トラップに注意

9 std::vector QVector boost::container::vector Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_back amortized O(1) Strong if T's ctor does not throw or Basic Guarantee insert(pos,...) O((N-pos)) Strong if T's ctor does not throw or Basic Guarantee pop_back O(1) No-fail erase O((N-pos)) No-fail if T's ctor does not throw or Basic Guarantee indexed access ( op[], at ) O(1) No-fail

10 QList boost::container::stable_vector 間接ベクタ list である必要はないけど T のコピーが重い時に sizeof(t) <= sizeof(t *) の場合は QVector と同じように振る舞う

11 std::deque boost::container::deque 要素をポインタを介して半連続的に格納 イメージ的には間接リングバッファ あるいはページコンテナ 各要素のルックアップは定数時間 (2 段間接参照 ) 先頭 末尾に対する挿入 削除は定数時間 ほとんどの操作は vector のほうが微妙に速い

12 std::deque boost::container::deque Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front/push_back O(1) Strong if T's ctor does not throw or Basic Guarantee insert(pos,...) O(N) Strong if T's ctor does not throw or Basic Guarantee pop_front/pop_back O(1) No-fail erase O(N) No-fail if T's ctor does not throw or Basic Guarantee indexed access ( op[], at ) O(1) No-fail

13 std::array boost::array 固定長配列 T[N] の代わり initializer_list のある C++0x では組み込みの配列は全て std::array に置き換え可能

14 std::array boost::array Operation Complexity Exception Safe Copy / Assign O(N) Basic Guarantee Range Copy / Assign O(N) Basic Guarantee push_front/push_back N/A N/A insert(pos,...) N/A N/A pop_front/pop_back N/A N/A erase N/A N/A indexed access ( op[], at ) O(1) O(1)

15 std::list QLinkedList boost::container::list 双方向リンクリスト 中間への挿入時に要素を動かしたくない時に 10kB 程度のコンテナなら vector のほうが速い そのコードリンクリストを使うけどきっとベクタで必要十分 boost::container::stable_vector も検討しましょう

16 std::list QLinkedList boost::container::list Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front/push_back O(1) Strong Guarantee insert(pos,...) O(1) Strong Guarantee pop_front/pop_back O(1) No-fail erase O(1) No-fail indexed access ( op[], at ) N/A N/A

17 std::forward_list boost::container::slist 単方向リンクリスト 特殊用途 通常は list を使いましょう インタフェースが少々特殊

18 std::forward_list boost::container::slist Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front O(1) Strong Guarantee insert_after(pos,...) O(1) Strong Guarantee pop_front O(1) No-fail erase_after O(1) No-fail indexed access ( op[], at ) N/A N/A

19 std::map QMap boost::container::map いわゆるディクショナリ ハッシュ とは違う ( 使い方は一緒 ) 要素は常に Key でソートされている ほとんどの操作が O(log N) 使えるなら unordered_map/qhash を使おう

20 std::map QMap boost::container::map Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N log N) Strong Guarantee insert O(log N) Strong Guarantee erase(key) O(log N) No-fail erase(pos) O(1) No-fail indexed access ( op[], at ) O(log N) Strong Guarantee

21 std::unordered_map QHash boost::unordered::unordered_map こっちが本当の ハッシュコンテナ ルックアップは平均的に定数時間 ハッシュ関数の用意が面倒 STL の実装によっては hash_map という名前で独自に用意されていることも

22 std::unordered_map QHash boost::unordered::unordered_map Operation Complexity Exception Safe Copy / Assign O(N), worst O(N^2) Strong Guarantee Range Copy / Assign O(N), worst O(N^2) Strong Guarantee insert O(1), worst O(N) Strong Guarantee erase O(1), worst O(N) No-fail indexed access ( op[], at ) O(1), worst O(N) N/A

23 boost::container::flat_map ソート済み vector の wrapper 挿入 削除時に要素の移動が発生してもよければ flat_map を検討しましょう

24 std::set boost::container::set 二分木 ( 多くは赤黒木 ) コンテナ 正直使い道が ソート済みベクタで大体事足りる

25 std::unordered_set QSet boost::unordered::unorderd_set std::set のハッシュテーブル版 使い道が

26 boost::container::flat_set ソート済み vector で実装された set やっぱり使い道が

27 で 結局どれ使えばいいの? Java 形式のイテレータが不要なら STL コンテナを使いましょう 例外安全に関する規定 パフォーマンス特性に関する規定が Qt コンテナには欠けている CoW はマルチコアでスケールしない Boost 内部にも STL コンテナの実装があります 必要に応じてアロケータを指定できます

28 で 結局どれ使えばいいの? 辞書的に使いたいなら( unordered_)map<key, T> 基本は vector<t> 末尾以外への挿入 削除が多いなら deque<t> 要素がでかい(256 B 以上 ) なら list<t> または boost::container::stable_vector<t> 挿入 削除時にイテレータ 参照を壊したくないなら list<t> 10kB 程度のコンテナなら何も考えずに vector<t>

29 実装の話 参照実装 libstdc Qt Boost 1.47 参考文献 オライリーいろいろ C++ In-Depth Series

30 std::vector template <typename T> class vector { T *start; T *finish; T *end_of_storage; /* */ }; 要素の先頭 要素の終端 ストレージの終端を指すポインタを保持 サイズの拡張は 2倍になるように行われる 最良のメモリ効率 vector<bool> トラップに注意

31 boost::container::vector template <typename T> class vector { T *start; size_t size; size_t capacity; }; std::vector と同じ vector<bool> トラップが無い VC++ で使うと vector<t>::iterator が T * であることを要求しているクソコードをあぶりだせる

32 QVector tempate <typename T> struct QVectorData { QAtomicIntRef ref; int alloc, size; uint sharable: 1; uint capacity: 1; T array[1]; /* */ }; template <typename T> class QVector { QVectorData<T> *d; /* */ }; Qt の可変長配列コンテナ C の 可変長構造体 で実装されている

33 boost::container::stable_vector template <typename T> struct node_type { void *up; T value; }; template <typename T> class stable_vector { vector<t> impl; /* */ }; vector と違い iterator が複雑 使い勝手は deque に近い

34 QList struct QListData { QBasicAtomicInt ref; int alloc, begin, end; bool sharable; void *array[1]; /* */ }; template <typename T> class QList { QListData *p; /* */ }; Data::array の型が T から void * に変わっている以外は QVector とほぼ同じ For most purposes, QList is the right class to use. 案外優秀な子

35 std::deque boost::container::deque template <typename T> struct deque_iterator { T *cur, *first, *last; T **node; }; ページ を管理する 有効なページ範囲は [ first, last) node ( ) は マップ後述 の要素を指している ( array<t *>::iterator の役割 )

36 std::deque boost::container::deque template <typename T> class deque { T **map; size_t map_size; iterator start, finish; /*...*/ }; map の マップ の先頭 ( array<t*, map_size>) の役割 [start, finish) は使用中のページ領域 [start, finish) は map の中央部分から使い 前後に伸長する

37 std::list boost::container::list template <typename T> struct list_node { list_node *next, prev; T data; }; template <typename T> struct list { list_node *list; }; 典型的な双方向リンクリスト 実際は code bloat を抑えるための thin wrapper idiom 等で複雑なコードに

38 QLinkedList struct QLinkedListData { QLinkedListData *n, *p; QBasicAtomicInt ref; int size; bool sharable; }; template <typename T> struct QLinkedListNode { QLinkedListNode *n, *p; T t; }; template <typename T> class QLinkedList { union { QLinkedListData *d; QLinkedListNode<T> *e; }; }; 参照カウントのためにおかしなデータ構造になっている 何をやっているのか正直よくわからない

39 std::array boost::array template < typename T, size_t N > class array { T data_[n]; /* */ }; ただの固定長配列 C++0x では完全に組み込み配列を駆逐可能 固定長なのでいろいろ制限は多い

40 map, set, hash Red-Black Tree とかハッシュとかよくわからんので勘弁してください むしろ誰か代わりに語ってください

41 まとめ コンテナの種類大杉 例外安全とマルチコアのパフォーマンスを気にしない かつ Java 形式の Iterator が要るなら QList を そうでなければ std::vector をまず検討する 基本は vector です deque や set, list は本当に必要な時だけ使う 自前での再実装だけは絶対にやめよう

スライド 1

スライド 1 今 此処にある C++ ~ テンプレートと STL~ テンプレートの解説 コンテナ イテレータ アルゴリズム アジェンダ テンプレートとは 型を外部から変更可能にした構文 通常の構文 int max(int a, int b){ return a > b? a : b; テンプレートを使った構文 template T max(t a, T b){ return a > b?

More information

Qt (Generic Containers) Java STL <QtAlgorithms> STL (Generic Algorithms) QList<T>, QLinkedList<T>, QVector<T>, QStack<T>, QQueue<T> QMap<Key,

Qt (Generic Containers) Java STL <QtAlgorithms> STL (Generic Algorithms) QList<T>, QLinkedList<T>, QVector<T>, QStack<T>, QQueue<T> QMap<Key, 1 5 5.1 Qt (Generic Containers) Java STL STL (Generic Algorithms) QList, QLinkedList, QVector, QStack, QQueue QMap, QMultiMap. QHash, QMultiHash

More information

memo

memo 計数工学プログラミング演習 ( 第 5 回 ) 2017/05/09 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 文字列 双方向リスト ハッシュ 2 文字列 文字列は char の配列 char name[] = ABC ; name は ABC を格納するのに十分な長さの配列 長さは, 文字列の長さ + 1 ( 終端記号用 ) char name[4]

More information

Microsoft PowerPoint - Pro110111

Microsoft PowerPoint - Pro110111 本日の到達目標 : コレクション プログラミング III 及び実習 1. コレクションとは 2. コレクションの種類 3. 使用方法 第 13 回コレクション 1 2 配列 ( 第 3 回 10 月 13 日 ) 演習 2 ファイル Bubble1.java は, 交換ソート ( バブルソート ) のプログラム ( 途中 ) である. プログラムを完成させ, 正しく実行できることを確かめなさい. /edu/g/po3_09/bubble1.java

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 プログラミングを 余談 : 教えることの難しさ 丁寧に説明しないと分かってもらえない 説明すると 小難しくなる学生が目指すべきところプログラム例を説明されて理解できる違うやり方でも良いので自力で解決できる おっけー 動けば良い という意識でプログラミング 正しく動くことのチェックは必要 解答例と自分のやり方との比較が勉強になる 今日のお題 再帰的構造体

More information

PowerPoint Template

PowerPoint Template プログラミング演習 Ⅲ Linked List P. Ravindra S. De Silva e-mail: ravi@cs.tut.ac.jp, Room F-413 URL: www.icd.cs.tut.ac.jp/~ravi/prog3/index_j.html 連結リストとは? 一つひとつの要素がその前後の要素との参照関係をもつデータ構造 A B C D 連結リストを使用する利点 - 通常の配列はサイズが固定されている

More information

memo

memo 計数工学プログラミング演習 ( 第 4 回 ) 2016/05/10 DEPARTMENT OF MATHEMATICA INFORMATICS 1 内容 リスト 疎行列 2 連結リスト (inked ists) オブジェクトをある線形順序に並べて格納するデータ構造 単方向連結リスト (signly linked list) の要素 x キーフィールド key ポインタフィールド next x->next:

More information

Microsoft PowerPoint - 6.pptx

Microsoft PowerPoint - 6.pptx 6. データ構造入門 6-1. 連結リスト (Linked List) 6-2. スタック (Stack) 6-. キュー (Queue) 6-4. デク (Double-Ended-Queue) 6-. 抽象データ型 (Abstract Data Type) データ構造とは データの保存を効率的に行うもの 1 ito 2.712.14 suzuki データ構造 1 2 6-1. 連結リスト (Linked

More information

(STL) STL 1 (deta structure) (algorithm) (deta structure) 2 STL STL (Standard Template Library) 2.1 STL STL ( ) vector<int> x; for(int i = 0; i < 10;

(STL) STL 1 (deta structure) (algorithm) (deta structure) 2 STL STL (Standard Template Library) 2.1 STL STL ( ) vector<int> x; for(int i = 0; i < 10; (STL) STL 1 (deta structure) (algorithm) (deta structure) 2 STL STL (Standard Template Library) 2.1 STL STL ( ) vector x; for(int i = 0; i < 10; ++i) x.push_back(i); vector STL x.push_back(i) STL

More information

Microsoft Word - 第5回 基本データ構造2(連結リスト).doc

Microsoft Word - 第5回 基本データ構造2(連結リスト).doc 第 5 回基本データ構造 2 連結リストとその操作 第 5 回 Page 1 5-1. リスト構造 データ部 と ポインタ部 で構成され ポインタをたどることによりデータを扱うことができる構造 5-2. 単方向リストとその操作 5-2-1. 単方向リスト 次のデータへのポインタを 1 つだけ持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) データ部 ポインタ部 ノード リストを構成する要素のことを

More information

cpp2.dvi

cpp2.dvi 2018 c 2 C++ (2) STL, C++ 21 string 22 STL 23 21 string C, \0, (, ), (, ), /,,,, C++,,, string string,,,,,, include,,, int, > >>,,,, getline(, string ), [List 21] 2: #include 3: 4:

More information

Boost.Preprocessor でプログラミングしましょう DigitalGhost

Boost.Preprocessor でプログラミングしましょう DigitalGhost Boost.Preprocessor でプログラミングしましょう DigitalGhost http://d.hatena.ne.jp/digitalghost/ http://twitter.com/decimalbloat 私のこと hatena のプロフィールとか 見てください とりあえず FizzBuzz 書いてみた #define FIZZBUZZ_OP(z, n, d) \ FIZZBUZZ_OP_I(

More information

Microsoft PowerPoint - algo ppt [互換モード]

Microsoft PowerPoint - algo ppt [互換モード] ( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる

More information

Microsoft Word - no206.docx

Microsoft Word - no206.docx 3.2 双方向リスト 今までのリストは 前から順にたどることしかできませんでした 今度は逆にもたどることができる 双方向リストを扱います この場合は 構造体には次を表すポインタの他に前を表すポインタを持つ ことになります 今回は最初と最後をポインタを使うと取り扱いが面倒になるので 最初 (start) と最後 (end) を どちらとも構造体 ( 値は意味を持たない ) を使うことにします こうすることによって

More information

20分でわかる Purely Functional Data Structures

20分でわかる Purely Functional Data Structures 20 分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ 遅デいータ構造は イミュータブル Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題 : キュー (Queue) FIFO (First-In First-Out)

More information

発表タイトル: Rhetorical Programming

発表タイトル: Rhetorical Programming Boost.Intrusive Boost.MultiIndex k.inaba ( 稲葉一浩 ) http://www.kmonos.net/ Boost. 勉強会 Dec 12, 2009 k.inaba といいます 2/68 こんなことやってます 今日お話したい内容 3/68 僕は データ構造 が好きです Boost のすごいデータ構造 その 1 Boost.MultiIndex 日本語で言うと

More information

第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先

第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先 第 3 回 Java 講座 今回の内容 今週の Java 講座はコレクション 拡張 for 文, ガベージコレクションについて扱う. 今週の Java 講座は一番内容が薄いも のになるだろう. コレクション コレクションとは大きさが決まっていない配列だと考えればよい. コレクションには List 先頭の要素要素から最後までが直線的に直結している構造 Set 同じものは含まないという構造. 要素間につながりはない

More information

第2回

第2回 第 4 回基本データ構造 1 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 1 配列 スタック キューとその操作 4-1. 配列とその操作 配列型 同じ型の変数を並べたもの 配列にする型は 基本型 配列型 構造体 ポインタいずれでもよい 要素の並べ方を 次元 という 1 次元配列 ( 直線状 ) 2 次元配列 ( 平面状 ) 3 次元配列 ( 立体状 ) a[5]

More information

プログラミングI第10回

プログラミングI第10回 プログラミング 1 第 10 回 構造体 (3) 応用 リスト操作 この資料にあるサンプルプログラムは /home/course/prog1/public_html/2007/hw/lec/sources/ 下に置いてありますから 各自自分のディレクトリにコピーして コンパイル 実行してみてください Prog1 2007 Lec 101 Programming1 Group 19992007 データ構造

More information

RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用

RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用 RX ファミリ用 C/C++ コンパイラ V.1.00 Release 02 ご使用上のお願い RX ファミリ用 C/C++ コンパイラの使用上の注意事項 4 件を連絡します #pragma option 使用時の 1 または 2 バイトの整数型の関数戻り値に関する注意事項 (RXC#012) 共用体型のローカル変数を文字列操作関数で操作する場合の注意事項 (RXC#013) 配列型構造体または共用体の配列型メンバから読み出した値を動的初期化に用いる場合の注意事項

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 前回の出席確認演習 #include int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0;

More information

1.3 ( ) ( ) C

1.3 ( ) ( ) C 1 1.1 (Data Base) (Container) C++ Java 1.2 1 1.3 ( ) ( ) 1. 2. 3. C++ 2 2.1 2.2 2.3 2 C Fortran C++ Java 3 3.1 (Vector) 1. 2. ( ) 3.2 3 3.3 C++ C++ STL C++ (Template) vector vector< > ; int arrayint vector

More information

第3回 配列とリスト

第3回 配列とリスト 連結リスト Algorithms and Data Structures on C この回の要点 連結リストによるリスト 連結リストの構造 連結リストの利点と欠点 C 言語による連結リストの実現 ヘッダファイルによるソースファイルの分割 連結リスト (linked list) リストの実現の一種 リストに含まれる各要素をリンクによって連結した構造 リンクとは 他のデータへの参照のこと 各要素は 自分から次のデータへのリンクを持つ

More information

Microsoft PowerPoint - 06.pptx

Microsoft PowerPoint - 06.pptx アルゴリズムとデータ構造第 6 回 : 探索問題に対応するデータ構造 (2) 担当 : 上原隆平 (uehara) 2015/04/22 内容 スタック (stack): 最後に追加されたデータが最初に取り出される 待ち行列 / キュー (queue): 最初に追加されたデータが最初に取り出される ヒープ (heap): 蓄えられたデータのうち小さいものから順に取り出される 配列による実装 連結リストによる実装

More information

4-3- 基 C++ に関する知識 オープンソースシステムのソースを解読する上で C++ の知識は必須であるといえる 本カリキュラムでは まずオブジェクト指向に関する Ⅰ. 概要理解を深め クラスの扱い方について学習し STL を使用してアルゴリズムとデータ構造を実装する方法を学習する Ⅱ. 対象専

4-3- 基 C++ に関する知識 オープンソースシステムのソースを解読する上で C++ の知識は必須であるといえる 本カリキュラムでは まずオブジェクト指向に関する Ⅰ. 概要理解を深め クラスの扱い方について学習し STL を使用してアルゴリズムとデータ構造を実装する方法を学習する Ⅱ. 対象専 4-3- 基 C++ に関する知識 1 4-3- 基 C++ に関する知識 オープンソースシステムのソースを解読する上で C++ の知識は必須であるといえる 本カリキュラムでは まずオブジェクト指向に関する Ⅰ. 概要理解を深め クラスの扱い方について学習し STL を使用してアルゴリズムとデータ構造を実装する方法を学習する Ⅱ. 対象専門分野職種共通 Ⅲ. 受講対象者 本カリキュラムの 4-2-

More information

Microsoft PowerPoint - 05.pptx

Microsoft PowerPoint - 05.pptx アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明

More information

バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科

バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科 バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科 ポインタ変数の扱い方 1 ポインタ変数の宣言 int *p; double *q; 2 ポインタ変数へのアドレスの代入 int *p; と宣言した時,p がポインタ変数 int x; と普通に宣言した変数に対して, p = &x; は x のアドレスのポインタ変数 p への代入 ポインタ変数の扱い方 3 間接参照 (

More information

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード] 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2 0.

More information

COMET II のプログラミング ここでは機械語レベルプログラミングを学びます 1

COMET II のプログラミング ここでは機械語レベルプログラミングを学びます 1 COMET II のプログラミング ここでは機械語レベルプログラミングを学びます 1 ここでは機械命令レベルプログラミングを学びます 機械命令の形式は学びましたね機械命令を並べたプログラムを作ります 2 その前に プログラミング言語について 4 プログラミング言語について 高級言語 (Java とか C とか ) と機械命令レベルの言語 ( アセンブリ言語 ) があります 5 プログラミング言語について

More information

memo

memo 数理情報工学演習第一 C プログラミング演習 ( 第 5 回 ) 2015/05/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 課題 : 疎行列 2 プロトタイプ宣言 3 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int

More information

Microsoft PowerPoint - kougi9.ppt

Microsoft PowerPoint - kougi9.ppt C プログラミング演習 第 9 回ポインタとリンクドリストデータ構造 1 今まで説明してきた変数 #include "stdafx.h" #include int _tmain(int argc, _TCHAR* argv[]) { double x; double y; char buf[256]; int i; double start_x; double step_x; FILE*

More information

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル 概略設計書 作成者築山修治作成日 2012 年 10 月 1 日 概要 ( どのような入力に対して, どのような出力をするかの概要説明 ) * 木 T および質問点対の集合 P が与えられたとき, 各質問点対 p = (v,w) P の最下位共通先祖 ( すなわち木 T において点 v と w の共通の先祖 a で,a の真の子孫には v と w の共通の先祖が無いような点 ) を見出す関数である.

More information

Taro-リストⅢ(公開版).jtd

Taro-リストⅢ(公開版).jtd リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題 問題 1 問題 2-1 - 2. 基本的な操作 2. 1 リストから要素の削除 まず 一般的な処理を書き つぎに 特別な処理を書く 一般的な処理は 処理 1 : リスト中に 削除するデータを見つけ 削除する場合への対応 特別な処理は 処理 2 : 先頭のデータを削除する場合への対応

More information

JAVA入門

JAVA入門 JAVA 入門 3 配列とコレクション 配列 1. 配列とは? 簡単 JAVA 説明 11 配列 同じ型の値を複数まとめて記憶する という機能を持つもの ということですが イメージとしては 同じ型の入れ物を複数用意する というイメージです int int int 簡単 JAVA 説明 11 配列の準備 2. 配列の準備 行うことは次の 2 つです 1 配列の宣言 2 配列要素の確保 簡単 JAVA

More information

PowerPoint Presentation

PowerPoint Presentation 算法数理工学 第 2 回 定兼邦彦 クイックソート n 個の数に対して最悪実行時間 (n 2 ) のソーティングアルゴリズム 平均実行時間は (n log n) 記法に隠された定数も小さい in-place ( 一時的な配列が必要ない ) 2 クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング. 部分問題への分割 : 配列 A[p..r] を 2 つの部分配列 A[p..q]

More information

memo

memo 計数工学プログラミング演習 ( 第 6 回 ) 2016/05/24 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い

More information

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1 4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる

More information

文字列操作と正規表現

文字列操作と正規表現 文字列操作と正規表現 オブジェクト指向プログラミング特論 2018 年度只木進一 : 工学系研究科 2 文字列と文字列クラス 0 個以上の長さの文字の列 Java では String クラス 操作 文字列を作る 連結する 文字列中に文字列を探す 文字列中の文字列を置き換える 部分文字列を得る 3 String クラス 文字列を保持するクラス 文字列は定数であることに注意 比較に注意 == : オブジェクトとしての同等性

More information

リファレンス,配列 例外処理

リファレンス,配列 例外処理 リファレンス, 配列, 例外処理 その他演習に役立つこと 2004 年 7 月 21 日 海谷治彦 1 リファレンス ま, 改め紹介しなくても Java 遣いなら誰でもつかってる. インスタンスをプログラム中から識別 ( 捕獲 ) するためのラベルのようなもの. C でいうところのポインタ変数に相当. Java では, あるインスタンスを参照するリファレンスが 1 つもなくなると, 勝手にインスタンスは消去される.

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 部内向けスキルアップ研修 組込み OS 自作入門 2014 年 2 月 10st ステップ担当 : 中村 目次 はじめに OSの役割 メモリ管理 メモリ管理実装 プログラムの実行 まとめ はじめに 前回やったこと OS の原型を作成 今回やること 9th ステップでは CPU 時間 という資源管理 本ステップでは メモリ という資源管理 10.1 OS の役割 10.1.1 コンピュータの 3 大要素

More information

JAVA入門

JAVA入門 JAVA 入門 3 配列とコレクション 配列 1. 配列とは? 簡単 JAVA 説明 11 配列 同じ型の値を複数まとめて記憶する という機能を持つもの ということですが イメージとしては 同じ型の入れ物を複数用意する というイメージです int int int 簡単 JAVA 説明 11 配列の準備 2. 配列の準備 行うことは次の 2 つです 1 配列の宣言 2 配列要素の確保 簡単 JAVA

More information

O(N) ( ) log 2 N

O(N) ( ) log 2 N 2005 11 21 1 1.1 2 O(N) () log 2 N 1.2 2 1 List 3-1 List 3-3 List 3-4? 3 3.1 3.1.1 List 2-1(p.70) 1 1 10 1 3.1.2 List 3-1(p.70-71) 1 1 2 1 2 2 1: 1 3 3.1.3 1 List 3-1(p.70-71) 2 #include stdlib.h

More information

Microsoft Word _VBAProg1.docx

Microsoft Word _VBAProg1.docx 1. VBA とマクロ 1.1 VBA とは VBA(Visual Basic for Applications) は 1997 年に Microsoft 社がマクロを作成するために開発された言語である Windows 対応のアプリケーションを開発するためのプログラミング言語 Visual Basic をもとにしているため 次のような特徴がある 1 VBA は Excel Word, Access,

More information

Prog1_15th

Prog1_15th 2017 年 7 月 27 日 ( 木 ) 実施 応用プログラム (3) キー検索 コレクションには, ハッシュテーブルと呼ばれるものがある これは, キー (key) と値 (value) とを組として保持しているものである 通常の配列が添字により各要素にアクセス出来るのに比べて, ハッシュテーブルではキーを用いて各値にアクセスすることが出来る キー及びそのキーから連想される値の組を保持していることから,

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 基幹 7 ( 水 5) 13: 構造体 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2016-07-06 1 例題 : 多角形の面積 n = 5 (5 角形 ) の例 n 1 n 1 1 p 1 T 0 S = i=0 p 0 T i = i=0 2

More information

02: 変数と標準入出力

02: 変数と標準入出力 C プログラミング入門 総機 1 ( 月 1) 13: 構造体 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2015-07-06 1 例題 : 多角形の面積 n = 5 (5 角形 ) の例 n 1 n 1 p 1 S = T i = 1 2 p i p i+1 i=0 i=0

More information

論理と計算(2)

論理と計算(2) 情報科学概論 Ⅰ アルゴリズムと計算量 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 亀山担当分の話題 アルゴリズムと計算量 Fibonacci 数列の計算を例にとり アルゴリズムと計算量とは何か 具体的に学ぶ 良いアルゴリズムの設計例として 整列 ( ソーティング ) のアルゴリズムを学ぶ 2 Fibonacci 数 () Fibonacci 数 (2) = if

More information

Microsoft PowerPoint - IntroAlgDs pptx

Microsoft PowerPoint - IntroAlgDs pptx アルゴリズムとデータ構造入門 -3 04 年 月 4 日 大学院情報学研究科知能情報学専攻 http://wiie.kuis.kyoto-u.ac.jp/~okuo/lecture//itroalgds/ okuo@i.kyoto-u.ac.jp,okuo@ue.org if mod( 学籍番号の下 3 桁,3) 0 if mod( 学籍番号の下 3 桁,3) if mod( 学籍番号の下 3 桁,3).

More information

SuperH RISC engineファミリ用 C/C++コンパイラパッケージ V.7~V.9 ご使用上のお願い

SuperH RISC engineファミリ用 C/C++コンパイラパッケージ V.7~V.9 ご使用上のお願い ツールニュース RENESAS TOOL NEWS 2014 年 02 月 01 日 : 140201/tn1 SuperH RISC engine ファミリ用 C/C++ コンパイラパッケージ V.7~V.9 ご使用上のお願い SuperH RISC engine ファミリ用 C/C++ コンパイラパッケージ V.7~V.9の使用上の注意事項 4 件を連絡します 同一ループ内の異なる配列要素に 同一の添え字を使用した場合の注意事項

More information

大容量情報検索論

大容量情報検索論 リスト構造 プログラミング演習 Ⅱ (9) 中村, 小松, 菊池 1. List 構造 配列 データが並んでいるデータ構造 静的 ( 配列長を後から変更できない ) リスト構造 次のデータを示す で構成される. 動的 ( 配列長を変更可能 ) 0 1 2 データ 次 データ 次 A[0] A[1] A[2] 10 30 データ 次 null 20 List クラスの例 ListNames.pde ListNames.pde

More information

Taro-リストⅠ(公開版).jtd

Taro-リストⅠ(公開版).jtd 0. 目次 1. 再帰的なデータ構造によるリストの表現 1. 1 リストの作成と表示 1. 1. 1 リストの先頭に追加する方法 1. 1. 2 リストの末尾に追加する方法 1. 1. 3 昇順を保存してリストに追加する方法 1. 2 問題 問題 1 問題 2-1 - 1. 再帰的なデータ構造によるリストの表現 リストは データの一部に次のデータの記憶場所を示す情報 ( ポインタという ) を持つ構造をいう

More information

アルゴリズムとデータ構造

アルゴリズムとデータ構造 講義 アルゴリズムとデータ構造 第 3 回基本的なデータ構造 ( リスト スタック キュー ) 大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室喜田拓也 講義資料 2018/5/23 今日の内容 基本的なデータ構造リスト : 最も基本的なデータ集合の表現 配列 / 連結リスト / 双連結リストによる実装 スタック : 積み上げ式のデータ格納方式キュー : 入れた順に取り出せるデータ格納方式

More information

memo

memo 計数工学プログラミング演習 ( 第 3 回 ) 2016/04/26 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 ポインタ malloc 構造体 2 ポインタ あるメモリ領域 ( アドレス ) を代入できる変数 型は一致している必要がある 定義時には値は不定 ( 何も指していない ) 実際にはどこかのメモリを指しているので, #include

More information

(2) 構造体変数の宣言 文法は次のとおり. struct 構造体タグ名構造体変数名 ; (1) と (2) は同時に行える. struct 構造体タグ名 { データ型変数 1; データ型変数 2;... 構造体変数名 ; 例 : struct STUDENT{ stdata; int id; do

(2) 構造体変数の宣言 文法は次のとおり. struct 構造体タグ名構造体変数名 ; (1) と (2) は同時に行える. struct 構造体タグ名 { データ型変数 1; データ型変数 2;... 構造体変数名 ; 例 : struct STUDENT{ stdata; int id; do 8 構造体と供用体 ( 教科書 P.71) 構造体は様々なデータ型,int 型,float 型や char 型などが混在したデータを一つのまとまり, 単位として扱える.( 配列は一つのデータ型しか扱えない.) 構造体は柔軟なデータ構造を扱えるので, プログラムを効率よく開発できる. つまり構造体を使用すると, コード量を抑え, バグを少なくし, 開発時間を短くし, 簡潔なプログラムが作れる. 共用体は,

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 講座準備 講座資料は次の URL から DL 可能 https://goo.gl/jnrfth 1 ポインタ講座 2017/01/06,09 fumi 2 はじめに ポインタはC 言語において理解が難しいとされる そのポインタを理解することを目的とする 講座は1 日で行うので 詳しいことは調べること 3 はじめに みなさん復習はしましたか? 4 & 演算子 & 演算子を使うと 変数のアドレスが得られる

More information

人工知能入門

人工知能入門 藤田悟 黄潤和 探索とは 探索問題 探索解の性質 探索空間の構造 探索木 探索グラフ 探索順序 深さ優先探索 幅優先探索 探索プログラムの作成 バックトラック 深さ優先探索 幅優先探索 n 個の ueen を n n のマスの中に 縦横斜めに重ならないように配置する 簡単化のために 4-ueen を考える 正解 全状態の探索プログラム 全ての最終状態を生成した後に 最終状態が解であるかどうかを判定する

More information

Microsoft Word - Cプログラミング演習(12)

Microsoft Word - Cプログラミング演習(12) 第 12 回 (7/9) 4. いくつかのトピック (5)main 関数の引数を利用したファイル処理 main 関数は, 起動する環境から引数を受け取ることができる 例えば 次に示すように,main 関数に引数を用いたプログラムを作成する 01 /* sample */ 02 /* main 関数の引数 */ 03 #include 04 05 main(int argc, char

More information

Prog1_10th

Prog1_10th 2012 年 6 月 20 日 ( 木 ) 実施ポインタ変数と文字列前回は, ポインタ演算が用いられる典型的な例として, ポインタ変数が 1 次元配列を指す場合を挙げたが, 特に,char 型の配列に格納された文字列に対し, ポインタ変数に配列の 0 番の要素の先頭アドレスを代入して文字列を指すことで, 配列そのものを操作するよりも便利な利用法が存在する なお, 文字列リテラルは, その文字列が格納されている領域の先頭アドレスを表すので,

More information

program7app.ppt

program7app.ppt プログラム理論と言語第 7 回 ポインタと配列, 高階関数, まとめ 有村博紀 吉岡真治 公開スライド PDF( 情報知識ネットワーク研 HP/ 授業 ) http://www-ikn.ist.hokudai.ac.jp/~arim/pub/proriron/ 本スライドは,2015 北海道大学吉岡真治 プログラム理論と言語, に基づいて, 現著者の承諾のもとに, 改訂者 ( 有村 ) が加筆修正しています.

More information

Microsoft Word - no202.docx

Microsoft Word - no202.docx 1.4 ポインタと配列 ポインタ変数は前回説明したように 値の入っているアドレスを示す変数です では 配列はどの ようにメモリ上に格納されるか調べてみましょう ex07.c /* ポインタと配列の関係 */ int a[3]={1, 2, 3; /* int 型の大きさ 3 の配列として宣言 */ int *i; /* int 型へのポインタとして宣言 */ double x[3] = {1.0,

More information

Microsoft PowerPoint - kougi11.ppt

Microsoft PowerPoint - kougi11.ppt C プログラミング演習 中間まとめ 2 1 ソフトウエア開発の流れ 機能設計 外部仕様 ( プログラムの入力と出力の取り決め ) 構成設計 詳細設計 論理試験 内部データ構造や関数呼び出し方法などに関する取り決めソースプログラムの記述正しい入力データから正しい結果が得られるかテスト関数単位からテストをおこなう 耐性試験 異常な入力データに対して, 異常を検出できるかテスト異常終了することはないかテスト

More information

7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 1

7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 1 7 ポインタ (P.61) ポインタを使うと, メモリ上のデータを直接操作することができる. 例えばデータの変更 やコピーなどが簡単にできる. また処理が高速になる. 7.1 ポインタの概念 変数を次のように宣言すると, int num; メモリにその領域が確保される. 仮にその開始のアドレスを 10001 番地とすると, そこから int 型のサイズ, つまり 4 バイト分の領域が確保される.1

More information

デジタル表現論・第4回

デジタル表現論・第4回 デジタル表現論 第 4 回 劉雪峰 ( リュウシュウフォン ) 2016 年 5 月 2 日 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 4 回 2016 年 5 月 2 日 1 / 14 本日の目標 Java プログラミングの基礎 出力の復習 メソッドの定義と使用 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 4 回 2016 年 5 月 2 日 2 / 14 出力 Systemoutprint()

More information

24th Embarcadero Developer Camp

24th Embarcadero Developer Camp 17 Th Developer Camp B4 Delphi/C++Builder テクニカルワークショップ Delphi / C++Builder 旧バージョンアプリケーションの移行 エンバカデロ テクノロジーズサポートチーム with 高橋智宏 1 17 Th Developer Camp Delphi Q1 2 midas.dll Q. 別々のバージョンで作成したデータベースアプリケーションがあります

More information

Microsoft PowerPoint - ca ppt [互換モード]

Microsoft PowerPoint - ca ppt [互換モード] 大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習

More information

構造体

構造体 構造体 Byte 配列 構造体とコピーする方法 構造体とバイト配列の変換を行うには System.Runtime.InteropServices 名前空間をインポートして置くと便利で有る Imports System.Runtime.InteropServices using System.Runtime.InteropServices; 下記の 3 種類の構造体にバイト配列の値を格納した場合に付いて検証する

More information

概要 プログラミング論 変数のスコープ, 記憶クラス. メモリ動的確保. 変数のスコープ 重要. おそらく簡単. 記憶クラス 自動変数 (auto) と静的変数 (static). スコープほどではないが重要.

概要 プログラミング論 変数のスコープ, 記憶クラス. メモリ動的確保. 変数のスコープ 重要. おそらく簡単. 記憶クラス 自動変数 (auto) と静的変数 (static). スコープほどではないが重要. 概要 プログラミング論 変数のスコープ, 記憶クラス. メモリ動的確保. 変数のスコープ 重要. おそらく簡単. 記憶クラス 自動変数 (auto) と静的変数 (static). スコープほどではないが重要. http://www.ns.kogakuin.ac.jp/~ct13140/progc/ C-2 ブロック 変数のスコープ C 言語では, から をブロックという. for( ) if( )

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 2 回文字列とポインタ 先週のパズルの解説 答え : 全部 p a 1 図の書き方 : p+1 は式であって その値を格納する記憶場所を考えないので 四角で囲まない 2 p+1 同じものを表すいろいろな書き方をしてみましたが パズル以上の意味はありません プログラム中に書くときは p+1 が短くていいんじゃないかな p+1 は 2 の記憶場所 p[1] は 2 に格納されている値

More information

プログラミングI第5回

プログラミングI第5回 プログラミング 第 5 回 ポインタ () -- ポインタ演算 配列のアドレス ポインタ演算 ( 前期教科書 P77~) ポインタと配列 ( 同上 P8) 文字列定数と文字列配列 ( 同上 P85) この資料にあるサンプルプログラムは /home/course/rog/ublc_html/7/hw/lec/sources/ 下に置いてありますから 各自自分のディレクトリにコピーして コンパイル 実行してみてください

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プロシージャ プロシージャの種類 Subプロシージャ Functionプロシージャ Propertyプロシージャ Sub プロシージャ Subステートメント~ステートメントで囲まれる 実行はするけど 値は返さない 途中で抜けたいときは Exit Sub を行なう Public Sub はマクロの実行候補に表示される Sub プロシージャの例 Public Sub TestSubProc() Call

More information

第2回

第2回 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 第 回基本データ構造 連結リストとその操作 -. リスト構造 データ部 と ポインタ部 で構成され ポインタをたどることによりデータを扱うことができる構造 -. 単方向リストとその操作 --. 単方向リスト 次のデータへのポインタを つだけ持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) データ部

More information

スライド 1

スライド 1 東北大学工学部機械知能 航空工学科 2015 年度 5 セメスター クラス D 計算機工学 6. MIPS の命令と動作 演算 ロード ストア ( 教科書 6.3 節,6.4 節 ) 大学院情報科学研究科鏡慎吾 http://www.ic.is.tohoku.ac.jp/~swk/lecture/ レジスタ間の演算命令 (C 言語 ) c = a + b; ( 疑似的な MIPS アセンブリ言語 )

More information

Microsoft PowerPoint - kougi10.ppt

Microsoft PowerPoint - kougi10.ppt C プログラミング演習 第 10 回二分探索木 1 例題 1. リストの併合 2 つのリストを併合するプログラムを動かしてみる head1 tail1 head2 tail2 NULL NULL head1 tail1 tail1 があると, リストの併合に便利 NULL 2 #include "stdafx.h" #include struct data_list { int data;

More information

6-1

6-1 6-1 (data type) 6-2 6-3 ML, Haskell, Scala Lisp, Prolog (setq x 123) (+ x 456) (setq x "abc") (+ x 456) ; 6-4 ( ) subtype INDEX is INTEGER range -10..10; type DAY is (MON, TUE, WED, THU, FRI, SAT, SUN);

More information

デジタル表現論・第6回

デジタル表現論・第6回 デジタル表現論 第 6 回 劉雪峰 ( リュウシュウフォン ) 2016 年 5 月 16 日 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 6 回 2016 年 5 月 16 日 1 / 16 本日の目標 Java プログラミングの基礎配列 ( 復習 関数の値を配列に格納する ) 文字列ファイルの書き込み 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 6 回 2016 年

More information

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき

More information

微分方程式 モデリングとシミュレーション

微分方程式 モデリングとシミュレーション 1 微分方程式モデリングとシミュレーション 2018 年度 2 質点の運動のモデル化 粒子と粒子に働く力 粒子の運動 粒子の位置の時間変化 粒子の位置の変化の割合 速度 速度の変化の割合 加速度 力と加速度の結び付け Newtonの運動方程式 : 微分方程式 解は 時間の関数としての位置 3 Newton の運動方程式 質点の運動は Newton の運動方程式で記述される 加速度は力に比例する 2

More information

alg2015-3r3.ppt

alg2015-3r3.ppt 1 アルゴリズムとデータ 構造 第 3 回基本的なデータ構造 ( リスト スタック キュー ) プログラミング で学ぶところ 授業で学ぶデータ構造の範囲 機械語のデータ型 レジスタ値とその番地 基本データ型 char, int, large int, double, 構造データ型 配列 (array), 構造体 (struct) 基本的データ構造 リスト (linked list), スタック (stack),

More information

C 言語経験者のための C++ 入門

C 言語経験者のための C++ 入門 C 言語経験者のための C++ 入門 金森由博 kanamori@cs.tsukuba.ac.jp 2013/4/19 第 1.2 版 2011/7/19 第 1 版 この資料は下記 URL から入手できます http://kanamori.cs.tsukuba.ac.jp/index-ja.html#for_students 1 内容 C++ を学び始めに引っかかりそうなところを概説 この資料の目標は

More information

HashMapからConcurrentHashMapへの移行

HashMapからConcurrentHashMapへの移行 HashMap から ConcurrentHashMap への移行 レガシー アプリケーションにおける注意点 2012 年 1 月 4 日橋口雅史 1. はじめにアプリケーションでは キーと値のマッピングが多用されます 例えば ユーザー名 というキーにユーザーの 情報 をマッピングするといった用途で java.util.map インタフェースは広く使われています 特に ハッシュテーブルに基づいて高速にマップを検索

More information

RX600 & RX200シリーズ アプリケーションノート RX用仮想EEPROM

RX600 & RX200シリーズ アプリケーションノート RX用仮想EEPROM R01AN0724JU0170 Rev.1.70 MCU EEPROM RX MCU 1 RX MCU EEPROM VEE VEE API MCU MCU API RX621 RX62N RX62T RX62G RX630 RX631 RX63N RX63T RX210 R01AN0724JU0170 Rev.1.70 Page 1 of 33 1.... 3 1.1... 3 1.2... 3

More information

Embarcadero Developer Camp

Embarcadero Developer Camp B5 C++ テクニカルセッション 今さら聞けない (?!)C/C++ ポインター再入門 株式会社日本情報システム筑木真志 アジェンダ ポインタ って何よ? メモリ & ポインタとの付き合いかた 解決法 :C の場合 ~ デバッグ用 malloc 解決法 :C++ の場合 ~ スマートポインタ 2 ポインタって 難しい よね 抽象的 メモリを確保 するってなに? プログラムが落ちる ポインタが絡むとプログラムが落ちる

More information

基礎プログラミング2015

基礎プログラミング2015 応用プログラミング 第 10 回 構造体 2017 年 11 月 22 日 ( 水 ) 第 11 章 構造体 構造体 * 国民の個人情報を管理したい例 : マイナンバー (id), 名前 (na), 年齢 (ag) * 管理する方法は? 配列を用いる方法 ただし, 年齢などでソートするとき面倒 id[0] id[1] id[2] id[3] id[4] na[0] na[1] na[2] na[3]

More information

Microsoft PowerPoint - lec10.ppt

Microsoft PowerPoint - lec10.ppt 今日の内容, とポインタの組み合わせ, 例題 1. 住所録例題 2. と関数とは. を扱う関数. 例題 3. のリスト とポインタの組み合わせ 今日の到達目標 自分で を定義する 自分で定義したについて, 配列やポインタを作成する データ型 基本データ型 char 文字 (1 文字 ) int 整数 double 浮動小数など その他のデータ型配列 データの並び ( 文字列も, 文字の並び ) ポインタ

More information

Introduction Purpose This training course demonstrates the use of the High-performance Embedded Workshop (HEW), a key tool for developing software for

Introduction Purpose This training course demonstrates the use of the High-performance Embedded Workshop (HEW), a key tool for developing software for Introduction Purpose This training course demonstrates the use of the High-performance Embedded Workshop (HEW), a key tool for developing software for embedded systems that use microcontrollers (MCUs)

More information

プログラム言語及び演習Ⅲ

プログラム言語及び演習Ⅲ 平成 28 年度後期データ構造とアルゴリズム期末テスト 各問題中のアルゴリズムを表すプログラムは, 変数の宣言が省略されているなど, 完全なものではありませんが, 適宜, 常識的な解釈をしてください. 疑問があれば, 挙手をして質問してください. 時間計算量をオーダ記法で表せという問題では, 入力サイズ n を無限大に近づけた場合の漸近的な時間計算量を表せということだと考えてください. 問題 1 入力サイズが

More information

スライド 1

スライド 1 Boost とその実装技術 ~Boost の薄い話から濃い話まで ~ 自己紹介 C++ スキー Boost スキー D&E 未読 猫スキー 吉田秀彦モドキ アジェンダ Boost について Boost.SharedPtr Boost.SharedPtr の実装技術 Boost.Spirit Boost.Spirit の実装技術 Boost について Boost とは Wikipedia C++ の先駆的な開発者のコミュニティ

More information

HABOC manual

HABOC manual HABOC manual Version 2.0 takada@cr.scphys.kyoto-u.ac.jp HABOC とは Event by event 解析用の Framework C++ による coding ANL や FULL の C++ 版を目標 ANL/FULL は Object Oriented な設計概念なので C++ と相性が良い Histogram や視覚化には ROOT(http://root.cern.ch)

More information

データ構造

データ構造 アルゴリズム及び実習 7 馬青 1 表探索 定義表探索とは 表の形で格納されているデータの中から条件に合ったデータを取り出してくる操作である 但し 表は配列 ( 連結 ) リストなどで実現できるので 以降 表 の代わりに直接 配列 や リスト などの表現を用いる場合が多い 表探索をただ 探索 と呼ぶ場合が多い 用語レコード : 表の中にある個々のデータをレコード (record) と呼ぶ フィールド

More information

1/8 ページ Java 基礎文法最速マスター Java Javaの文法一覧です 他の言語をある程度知っている人はこれを読めばJavaの基礎をマスターしてJavaを書くことができるようになっています 簡易リファレンスとしても利用できると思いますので これは足りないと思うものがあれば教えてください 1. 基礎 class の作成プログラムはclassに記述します たとえばSampleという名前のclassを作る場合

More information

Microsoft PowerPoint ppt

Microsoft PowerPoint ppt 基礎演習 3 C 言語の基礎 (5) 第 05 回 (20 年 07 月 07 日 ) メモリとポインタの概念 ビットとバイト 計算機内部では データは2 進数で保存している 計算機は メモリにデータを蓄えている bit 1bit 0 もしくは 1 のどちらかを保存 byte 1byte 1bitが8つ集まっている byte が メモリの基本単位として使用される メモリとアドレス メモリは 1byte

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 2 回文字列とポインタ 再掲 プログラミング上達のために 何度か言っていますが 単純な方法があります : 毎日プログラムを書いていれば そのうち慣れます 中身はなんでも構いません 逆にしばらくプログラムを書かずにいると忘れます レポート以降プログラムを書いていないという人は そろそろ忘れている頃かも知れませんね 今後もプログラミングの授業があり 基礎演習の内容が前提となりますので

More information

memo

memo 計数工学プログラミング演習 ( 第 6 回 ) 2017/05/16 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い

More information

Exam : 1z1-809-JPN Title : Java SE 8 Programmer II Vendor : Oracle Version : DEMO Get Latest & Valid 1z1-809-JPN Exam's Question and Answers 1 from Ac

Exam : 1z1-809-JPN Title : Java SE 8 Programmer II Vendor : Oracle Version : DEMO Get Latest & Valid 1z1-809-JPN Exam's Question and Answers 1 from Ac Actual4Test http://www.actual4test.com Actual4test - actual test exam dumps-pass for IT exams Exam : 1z1-809-JPN Title : Java SE 8 Programmer II Vendor : Oracle Version : DEMO Get Latest & Valid 1z1-809-JPN

More information

memo

memo 計数工学プログラミング演習 ( 第 3 回 ) 2017/04/25 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 内容 ポインタの続き 引数の値渡しと参照渡し 構造体 2 ポインタで指されるメモリへのアクセス double **R; 型 R[i] と *(R+i) は同じ意味 意味 R double ** ポインタの配列 ( の先頭 ) へのポインタ R[i]

More information

Microsoft PowerPoint - handout07.ppt [互換モード]

Microsoft PowerPoint - handout07.ppt [互換モード] Outline プログラミング演習第 7 回構造体 on 2012.12.06 電気通信大学情報理工学部知能機械工学科長井隆行 今日の主眼 構造体 構造体の配列 構造体とポインタ 演習課題 2 今日の主眼 配列を使うと 複数の ( 異なる型を含む ) データを扱いたい 例えば 成績データの管理 複数のデータを扱う 配列を使う! 名前学籍番号点数 ( 英語 ) 点数 ( 数学 ) Aomori 1 59.4

More information

Microsoft PowerPoint - 09.pptx

Microsoft PowerPoint - 09.pptx 情報処理 Ⅱ 第 9 回 2014 年 12 月 22 日 ( 月 ) 関数とは なぜ関数 関数の分類 自作関数 : 自分で定義する. ユーザ関数 ユーザ定義関数 などともいう. 本日のテーマ ライブラリ関数 : 出来合いのもの.printf など. なぜ関数を定義するのか? 処理を共通化 ( 一般化 ) する プログラムの見通しをよくする 機能分割 ( モジュール化, 再利用 ) 責任 ( あるいは不具合の発生源

More information

昨年度までの研究紹介 および 研究計画

昨年度までの研究紹介 および 研究計画 第 12 回 ICN 研究会ワークショップ Cefore で キャッシュプラグイン開発 2018 年 8 月 30 日 ( 木 ) キャッシュプラグイン csmgrd は起動時に使用するキャッシュプラグインを指定 Cache plugin: キャッシュデータ保存方式 Cache algorithm: キャッシュ選択 / 置換アルゴリズム Cache Plugin Cache algorithm csmgrd

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 2 回文字列とポインタ 先週のパズルの解説 答え : 全部 p a 1 図の書き方 : p+1 は式であって その値を格納する記憶場所を考えないので 四角で囲まない 2 p+1 同じものを表すいろいろな書き方をしてみましたが パズル以上の意味はありません プログラム中に書くときは p+1 が短くていいんじゃないかな p+1 は 2 の記憶場所 p[1] は 2 に格納されている値

More information

Taro-2分探索木Ⅰ(公開版).jtd

Taro-2分探索木Ⅰ(公開版).jtd 2 分探索木 Ⅰ 0. 目次 1. 2 分探索木とは 2. 2 分探索木の作成 3. 2 分探索木の走査 3. 1 前走査 3. 2 中走査 3. 3 問題 問題 1 問題 2 後走査 4. 2 分探索木の表示 - 1 - 1. 2 分探索木とは 木はいくつかの節点と節点同士を結ぶ辺から構成される 2 つの節点 u,v が直接辺で結ばれているとき 一方を親節点 他方を子節点という ある節点の親節点は高々

More information