アルゴリズムとデータ構造 第２回 線形リスト（復習その２）
本日の講義内容 ポインタと配列 線形リスト スタック
int a[10]で何が起きるのか？ メモリー（４バイト*10=40バイト）が確保される。 その先頭アドレスは a で知ることができる。 例 int a[10]={3,8}; scanf(“%d”,a+2); printf(“%d %d\n”,*a,*(a+1),*(a+2));
構造体の定義 typedef struct _card{ int num; struct _card *next; } card; nextが宣言できない。 typedefにより、 struct _card は、単に cardという型になる。
card のポインタの定義 typedef card *cptr; これで、 card * と書く代わりにcptrと書いてよいことになる。 かえって、わかりにくいと思えば定義しなくても良い。
mallocによる構造体の生成 #include <stdlib.h> cptr new_card(int x){ cptr p; p=(cptr) malloc(sizeof(card)); p->num=x; return p; } これは、１個のcardを新しく作り、そのアドレスを返す関数である。
構造体のメンバーの値の変更 void set_card(cptr ca, int x){ ca-> num=x; return; }
線形リストの先頭と最後 cptr first=NULL; cptr last=NULL; NULLは、整数０またはvoid *としての０である。 使用できない、あるいは未定義を意味する。これは最初の状態。
リストの最後にcardを挿入 void add_card(int x){ cptr new; new=new_card(x); if(last==NULL){ first=new; first->next=NULL; last=first; } else{ last->next=new; new->next=NULL; last=new;
リストの先頭にcardを挿入 void push_card(int x){ cptr new; new=new_card(x); new->next=first; first=new; if(last==NULL) last=new; return; } これは、リストをスタックとして使う。スタックの先頭にデータを入れることをpushという。
POP int pop_card(void){ cptr p; int x; p=first; if(p==NULL) return p; /*** 空リスト **/ first=first->next; if(first==NULL) last=NULL; x=p->num; free(p); return x; } これは、リストの先頭を取り除く。これがPOPである。 この関数は、取り除いた先頭のcardの値を返す。先頭にあったcardのメモリーはfreeで解放される。
すべてのcardの表示 void print_card(void){ cptr p; int x=0; /*** 先頭を0 番とする。 **/ p=first; while(p!=NULL){ printf(“%d: %d\n”,x++,p->num); p=p->next; } ここで、p=p->nextにより次cardを見ている。
n番目のcardの表示 void print_nth(int x){ cptr p; int y=0; /*** 先頭を0 番とする。 **/ p=first; while(p!=NULL){ if(y==x) printf(“%d: %d\n”,x,p->num); y++; p=p->next; }