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

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

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

2 本日の講義内容 ポインタと配列 線形リスト スタック

3 int a[10]で何が起きるのか？ メモリー（４バイト*10=40バイト）が確保される。 その先頭アドレスは a で知ることができる。
例 　　int a[10]={3,8}; scanf(“%d”,a+2); printf(“%d %d\n”,*a,*(a+1),*(a+2));

4 構造体の定義 typedef struct _card{ int num; struct _card *next; } card;
　　nextが宣言できない。 　typedefにより、 struct _card は、単に　cardという型になる。

5 card のポインタの定義 typedef card *cptr; これで、 card * と書く代わりにcptrと書いてよいことになる。
かえって、わかりにくいと思えば定義しなくても良い。

6 mallocによる構造体の生成 #include <stdlib.h> cptr new_card(int x){
cptr p; p=(cptr) malloc(sizeof(card)); p->num=x; return p; } これは、１個のcardを新しく作り、そのアドレスを返す関数である。

7 構造体のメンバーの値の変更 void set_card(cptr ca, int x){ ca-> num=x; return; }

8 線形リストの先頭と最後 cptr first=NULL; cptr last=NULL;
NULLは、整数０またはvoid *としての０である。　使用できない、あるいは未定義を意味する。これは最初の状態。

9 リストの最後に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;

10 リストの先頭にcardを挿入 void push_card(int x){ cptr new; new=new_card(x);
new->next=first; first=new; if(last==NULL) last=new; return; } これは、リストをスタックとして使う。スタックの先頭にデータを入れることをpushという。

11 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で解放される。

12 すべての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を見ている。

13 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; }