連結リストの練習

　先頭ノードへのポインタ（first_p）からリストを順にたどりデータを画面に表示する

/* 連結リストを表示する */
#include <stdio.h>
#include <stdlib.h>

typedef	struct	node{
	int		data;
	struct node	*next;
} NODE, *Nodep;

void	displist(Nodep fp);

Nodep	first_p;	/* 先頭ノードを指すポインタ */

main()
{
	/* [1, 5, 9] というリストを作成 */
	first_p = (Nodep)malloc(sizeof(NODE));
	first_p->data = 1;
	first_p->next = (Nodep)malloc(sizeof(NODE));
	first_p->next->data = 5;
	first_p->next->next = (Nodep)malloc(sizeof(NODE));
	first_p->next->next->data = 9;
	first_p->next->next->next = NULL;

	displist(first_p);
}

void	displist(Nodep fp)
{
	printf("List");
	if( fp == NULL )
	{
		printf(" is empty\n");
		return;
	}
	for( ; fp != NULL; fp = fp->next )
	{
		printf("%5d", fp->data );
	}
	printf("\n");
}
/* end of llist1.c */

　ヘッダノード（first）からリストを順にたどりデータを画面に表示する

/* 連結リストを表示する */
#include <stdio.h>
#include <stdlib.h>

typedef	struct	node{
	int		data;
	struct node	*next;
} NODE, *Nodep;

void	displist(Nodep fp);

NODE	first;	/* 先頭ノードを指すポインタを含むノード */

main()
{
	/* [1, 5, 9] というリストを作成 */
	first.next = (Nodep)malloc(sizeof(NODE));
	first.next->data = 1;
	first.next->next = (Nodep)malloc(sizeof(NODE));
	first.next->next->data = 5;
	first.next->next->next = (Nodep)malloc(sizeof(NODE));
	first.next->next->next->data = 9;
	first.next->next->next->next = NULL;

	displist(&first);
}

void	displist(Nodep fp)
{
	printf("List");
	if( fp->next == NULL )
	{
		printf(" is empty\n");
		return;
	}
	for( fp = fp->next ; fp != NULL; fp = fp->next )
	{
		printf("%5d", fp->data );
	}
	printf("\n");
}
/* end of llist2.c */

連結リストの基本操作をやってみよう！

　ポインタをどのように付け替えたら良いかを考えよう！

  1. リストの先頭要素を削除する関数delhead()を作成せよ
    1. 先頭ノードへのポインタ（first_p）版のdelhead(Nodep *fpp)をllist1.cに組み込んで確認せよ。模範解答へ
    2. ヘッダノード（first）版のdelhead(Nodep fp)をllist2.cに組み込んで確認せよ。模範解答へ
  2. リストの末尾要素を削除する関数deltail()を作成せよ
    1. 先頭ノードへのポインタ（first_p）版のdeltail(Nodep *fpp)を作成してllist1.cに組み込んで確認せよ。
    2. ヘッダノード（first）版のdeltail(Nodep fp)を作成してllist2.cに組み込んで確認せよ。
  3. 以下では、ヘッダノード（first）版のみでよい！
    次のメニューを提示し、操作を選べるようにして、それぞれ実行するようにせよ。
    　A：先頭要素の削除（delhead）
    　B：末尾要素の削除（deltail）
    　Q：リスト操作の終了（quit）
      この終了が選択されるまで、繰り返し選択して操作ができるようにせよ。
    ・全ての要素を削除したらどうなりますか？
    ・空のリストから要素を削除しようとしたらどうなりますか？
  4. 整数データ（val）を受け取り、新規ノードをリストの先頭に追加する関数addhead(Nodep fp, int val)を作成せよ。
  5. 整数データ（val）を受け取り、新規ノードをリストの末尾に追加する関数addtail(Nodep fp, int val)を作成せよ。
  6. 整数データ（val）がリストの中に有るか否かを判定する関数int find(Nodep fp, int val)を作成せよ。
  7. 以下のメニューを追加し、データをキー入力して、それぞれの操作を実行するようにせよ。
    　C：先頭にデータ要素を追加（addhead）
    　D：末尾にデータ要素を追加(addtail)
    　E：リスト中にデータが有るか否か（find）
      有る時は「有ります。」、無い時は「無いです。」と画面に表示すれば良い。
  8. リストに対して上で実現した様々な操作を繰り返し、正しく実行されることを確かめよ。

１．リストの先頭要素の削除

/* リストの先頭要素を削除する
　先頭ノードへのポインタ（first_p）版 */
#include <stdio.h>
#include <stdlib.h>

typedef	struct	node{
	int		data;
	struct node	*next;
} NODE, *Nodep;

void	displist(Nodep fp);
void	delhead(Nodep *fp);

Nodep	first_p;	/* 先頭ノードを指すポインタ */

main()
{
	/* [1, 5, 9] というリストを作成 */
	first_p = (Nodep)malloc(sizeof(NODE));
	first_p->data = 1;
	first_p->next = (Nodep)malloc(sizeof(NODE));
	first_p->next->data = 5;
	first_p->next->next = (Nodep)malloc(sizeof(NODE));
	first_p->next->next->data = 9;
	first_p->next->next->next = NULL;

	displist(first_p);
	delhead(&first_p);
	/* [5, 9] というリストになっているはず */
	displist(first_p);
	delhead(&first_p);
	/* [9] というリストになっているはず */
	displist(first_p);
	delhead(&first_p);
	/* empty リストになっているはず */
	displist(first_p);
	delhead(&first_p);
	/* empty リストのままのはず */
	displist(first_p);
}

void	displist(Nodep fp)
{
	printf("List");
	if( fp == NULL )
	{
		printf(" is empty\n");
		return;
	}
	for( ; fp != NULL; fp = fp->next )
	{
		printf("%5d", fp->data );
	}
	printf("\n");
}

void	delhead(Nodep *fpp)
{
	Nodep	p;

	if( p = *fpp )
	{
		*fpp = p->next;
		free(p);
	}
}
/* end of llist3.c */

/* リストの先頭要素を削除する
　ヘッダノード（first）版 */
#include 
#include 

typedef	struct	node{
	int		data;
	struct node	*next;
} NODE, *Nodep;

void	displist(Nodep fp);
void	delhead(Nodep fp);

NODE	first;	/* 先頭ノードを指すポインタを含むノード */

main()
{
	/* [1, 5, 9] というリストを作成 */
	first.next = (Nodep)malloc(sizeof(NODE));
	first.next->data = 1;
	first.next->next = (Nodep)malloc(sizeof(NODE));
	first.next->next->data = 5;
	first.next->next->next = (Nodep)malloc(sizeof(NODE));
	first.next->next->next->data = 9;
	first.next->next->next->next = NULL;

	displist(&first);
	delhead(&first);
	/* [5, 9] というリストになっているはず */
	displist(&first);
	delhead(&first);
	/* [9] というリストになっているはず */
	displist(&first);
	delhead(&first);
	/* empty リストになっているはず */
	displist(&first);
	delhead(&first);
	/* empty リストのままのはず */
	displist(&first);
}

void	displist(Nodep fp)
{
	printf("List");
	if( fp->next == NULL )
	{
		printf(" is empty\n");
		return;
	}
	for( fp = fp->next ; fp != NULL; fp = fp->next )
	{
		printf("%5d", fp->data );
	}
	printf("\n");
}

void	delhead(Nodep fp)
{
	Nodep	p;

	if( p = fp->next )
	{
		fp->next = p->next;
		free(p);
	}
}
/* end of llist4.c */