アルゴリズムとデータ構造 第２回　線形リスト（復習）.

Presentation on theme: "アルゴリズムとデータ構造 第２回　線形リスト（復習）."— Presentation transcript:

1 アルゴリズムとデータ構造 第２回　線形リスト（復習）

2 本日の講義内容 Cの変数 ポインタ 構造体 線形リスト 他

3 Cの変数とポインタ int x で何がおきるのか *と& mallocは何故必要か typedef structure ポインタによる連結
ポインタによる連結　 線形リスト

4 int xで何が起きるのか？ メモリー（４バイト=32bit）が確保される。 そのアドレスは &xで知ることができる。 例
int *p=&x; printf(“%x %d\n”,p,*p);

5 *と& *x xをアドレス（ポインタ）とみなしてそのアドレスの内容を取得する。xにはさまざまな形が許されるが、その値はある型のポインタでないといけない。 &x xは一般に変数名である。xが格納されているアドレス（ポインタ）を取得する。

6 例 int x=1000,y; y=*x; エラー xはポインタではない。 y=*(int *)x; コンパイラは通る。
　　実行時エラー（segmentation error)になる。 1000番地は、このプロセスの使用領域ではないから。

7 ポインタを引数にする ポインタを引く数にすることにより、もとのデータを変更することができる。（アドレス渡し）
構造体を処理するときは、ポインタで渡すのが原則である。

8 構造体の生成 struct student{ int age; char name[20]; }; struct student s;
これは、１個の構造体を作り、その名前をｓとする。

9 mallocによる構造体の生成 struct student *new_st{ struct student *p;
p=malloc(sizeof(struct student)); return p; }; これは、１個の構造体を新しく作り、そのアドレスを返す関数である。

10 構造体のメンバーの変更 void change_st(struct student *st, int x, char *name){
st-> age=x; strcpy(name,st->name); };

11 typedef typedefは、新しい型を定義する。 typedef struct _student { int age;
char name[20]; struct _student *next; }stu; typedef stu *stuptr;

12 typedefの効果 struct _student ｓ； -> stu s; struct _student *p;
stuptr p; のように、簡潔な表現ができる。

13 線形リストを作る struct _student *next; に注目しよう。これは、次の_student構造体
されているのである。 つまり、今　見ているカードのポインタ（アドレス）をp とすると p->next が次のカードのポインタを表す。

14 データ構造 問題をどのように表現するか？ 良い表現は、アルゴリズムをわかりやすくしたり、より効率的にする。

15 代表的データ構造 配列（１次元、２次元、...)‏ リスト ２分木 ハッシュ表 グラフ

16 C言語 構造体　　リストなどの実現 共用体 ポインタ

17 トランプのゲームを作りたい カードの山 方法１ int card[53]; 方法２ 53個の線形リストにする。 構造体{種類、数}
簡単な例 トランプのゲームを作りたい カードの山 方法１　int card[53]; 方法２　53個の線形リストにする。 構造体{種類、数}

18 シャッフルしたい。-> 乱数の利用 手持ちのカードを整理したい-> ソート 最良の捨て札を見つけたい-> サーチ
さらに シャッフルしたい。-> 乱数の利用 手持ちのカードを整理したい-> ソート 最良の捨て札を見つけたい-> サーチ

19 他の言語 LISP リスト構造が最初からシステムに入っている。 Prolog パターンマッチングによる探索機能が がある。
Java 　　オブジェクトによるデータ表現ができ　る。抽象クラス（構造体）。 Pascal　アルゴリズム記述でよく使われた。

20 ノートパソコン 他学系などの学生には MACBOOKの貸し出しなどをします。 OS MACOSX, Linux(Fedora)
　他学系などの学生には 　MACBOOKの貸し出しなどをします。 OS MACOSX, Linux(Fedora)　 　Editor Emacs, vi コンパイラ gcc ( cc)‏

21 WindowsのC は基本的に禁止 VC, Borland Cなどは禁止 UNIX C と一部互換でない。 原理がわかりにくい。
コマンドの意識 GUIも実際はコマンドの実行をしている。

22 質問など 講義・演習では積極的に質問すること。 プログラミングは慣れである。 正しく動作するプログラムは、自分の財産。
なぜそうなるのか、よく考えること。 何をしたいのか、どうすればよいのか？何が必要か？