Presentation is loading. Please wait.

Presentation is loading. Please wait.

アルゴリズムとデータ構造 第2回 線形リスト(復習).

Similar presentations


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

1 アルゴリズムとデータ構造 第2回 線形リスト(復習)

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

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

4 int xで何が起きるのか? メモリー(4バイト=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;
これは、1個の構造体を作り、その名前をsとする。

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

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 s; -> stu s; struct _student *p;
stuptr p; のように、簡潔な表現ができる。

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

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

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

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

17 トランプのゲームを作りたい カードの山 方法1 int card[53]; 方法2 53個の線形リストにする。 構造体{種類、数}
簡単な例 トランプのゲームを作りたい カードの山 方法1 int card[53]; 方法2 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 質問など 講義・演習では積極的に質問すること。 プログラミングは慣れである。 正しく動作するプログラムは、自分の財産。
なぜそうなるのか、よく考えること。 何をしたいのか、どうすればよいのか?何が必要か?


Download ppt "アルゴリズムとデータ構造 第2回 線形リスト(復習)."

Similar presentations


Ads by Google