アルゴリズムとデータ構造 第２回 線形リスト（復習）
本日の講義内容 Cの変数 ポインタ 構造体 線形リスト 他
Cの変数とポインタ int x で何がおきるのか *と& mallocは何故必要か typedef structure ポインタによる連結 ポインタによる連結 線形リスト
int xで何が起きるのか？ メモリー（４バイト=32bit）が確保される。 そのアドレスは &xで知ることができる。 例 int *p=&x; printf(“%x %d\n”,p,*p);
*と& *x xをアドレス（ポインタ）とみなしてそのアドレスの内容を取得する。xにはさまざまな形が許されるが、その値はある型のポインタでないといけない。 &x xは一般に変数名である。xが格納されているアドレス（ポインタ）を取得する。
例 int x=1000,y; y=*x; エラー xはポインタではない。 y=*(int *)x; コンパイラは通る。 実行時エラー（segmentation error)になる。 1000番地は、このプロセスの使用領域ではないから。
ポインタを引数にする ポインタを引く数にすることにより、もとのデータを変更することができる。（アドレス渡し） 構造体を処理するときは、ポインタで渡すのが原則である。
構造体の生成 struct student{ int age; char name[20]; }; struct student s; これは、１個の構造体を作り、その名前をｓとする。
mallocによる構造体の生成 struct student *new_st{ struct student *p; p=malloc(sizeof(struct student)); return p; }; これは、１個の構造体を新しく作り、そのアドレスを返す関数である。
構造体のメンバーの変更 void change_st(struct student *st, int x, char *name){ st-> age=x; strcpy(name,st->name); };
typedef typedefは、新しい型を定義する。 typedef struct _student { int age; char name[20]; struct _student *next; }stu; typedef stu *stuptr;
typedefの効果 struct _student ｓ； -> stu s; struct _student *p; stuptr p; のように、簡潔な表現ができる。
線形リストを作る struct _student *next; に注目しよう。これは、次の_student構造体 されているのである。 つまり、今 見ているカードのポインタ（アドレス）をp とすると p->next が次のカードのポインタを表す。
データ構造 問題をどのように表現するか？ 良い表現は、アルゴリズムをわかりやすくしたり、より効率的にする。
代表的データ構造 配列（１次元、２次元、...) リスト ２分木 ハッシュ表 グラフ
C言語 構造体 リストなどの実現 共用体 ポインタ
トランプのゲームを作りたい カードの山 方法１ int card[53]; 方法２ 53個の線形リストにする。 構造体{種類、数} 簡単な例 トランプのゲームを作りたい カードの山 方法１ int card[53]; 方法２ 53個の線形リストにする。 構造体{種類、数}
シャッフルしたい。-> 乱数の利用 手持ちのカードを整理したい-> ソート 最良の捨て札を見つけたい-> サーチ さらに シャッフルしたい。-> 乱数の利用 手持ちのカードを整理したい-> ソート 最良の捨て札を見つけたい-> サーチ
他の言語 LISP リスト構造が最初からシステムに入っている。 Prolog パターンマッチングによる探索機能が がある。 Java オブジェクトによるデータ表現ができ る。抽象クラス（構造体）。 Pascal アルゴリズム記述でよく使われた。
ノートパソコン 他学系などの学生には MACBOOKの貸し出しなどをします。 OS MACOSX, Linux(Fedora) 他学系などの学生には MACBOOKの貸し出しなどをします。 OS MACOSX, Linux(Fedora) Editor Emacs, vi コンパイラ gcc ( cc)
WindowsのC は基本的に禁止 VC, Borland Cなどは禁止 UNIX C と一部互換でない。 原理がわかりにくい。 コマンドの意識 GUIも実際はコマンドの実行をしている。
質問など 講義・演習では積極的に質問すること。 プログラミングは慣れである。 正しく動作するプログラムは、自分の財産。 なぜそうなるのか、よく考えること。 何をしたいのか、どうすればよいのか？何が必要か？