2017年度「アルゴリズムとデータ構造」のページ

練習問題

2017年12月14日出題
  1. 単方向線形リスト(ダミーセルなし)について、以下を行なう関数をそれぞれ書け。 ただし、slist.hに以下の型定義が書かれているものとする。 どの関数についても、関数の第一引数は、struct slist * 型またはconst struct slist * 型とする。 struct slistの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。
    struct scell {
    	struct scell	*next; /* 次のセルを指すポインタ */
    	int		data;
    	};
    struct slist {
    	struct scell	*head; /* 先頭のセルを指すポインタ */
    };
    	    
    リストの初期化は以下の関数slist_init()で行うものとする。
    #include <stdlib.h>
    #include "slist.h"
    
    void
    slist_init(struct slist *list)
    {
    	list->head = NULL;
    }
                
    セルの生成と削除は、以下の課題を通じて整合的なものにすること。 たとえば、以下の方法がある。
    • 新たなセルを確保してそれを指すポインタをpに格納するには:
      	p = malloc(sizeof(struct scell));
      		
    • ポインタpが指すセルを削除するには:
      	free(p);
      		
    1. 先頭のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*slist_first(struct slist *);
      		
    2. 末尾のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*slist_last(struct slist *);
      		
    3. n番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*slist_nth(struct slist *, size_t);
      		
    4. 最後からn番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*slist_nth_last(struct slist *, size_t);
      		
    5. リストを空リストにする。不要なセルは削除する。struct slistの実体は削除しない。
      void	slist_clear(struct slist *);
      		
    6. 第二引数で与えられた値を持つセルを生成し、 先頭に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*slist_insert_head(struct slist *, int);
      		
    7. 第二引数で与えられた値を持つセルを生成し、 末尾に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*slist_insert_tail(struct slist *, int);
      		
    8. (欠番)

    9. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直後に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*slist_insert_after(struct slist *, int, struct scell *);
      		
    10. 先頭のセルを削除する。
      void	slist_remove_head(struct slist *);
      		
    11. 末尾のセルを削除する。
      void	slist_remove_tail(struct slist *);
      		
    12. 第二引数でポインタで指定されたセルの直後のセルを削除する。
      void	slist_remove_after(struct slist *, struct scell *);
      		
    13. 第二引数(int)の値に応じて、以下のようにする。
      0
      リストの要素の総個数を返す。
      1
      リストの要素のうち、奇数の値をもつものの個数を返す。
      2
      リストの要素のうち、偶数の値をもつものの個数を返す。
      その他
      常に0を返す。
      size_t	slist_count_fancy(const struct slist *, int);
      		
    14. 要素の値の総和を返す。
      int	slist_sum(const struct slist *);
      		
    15. 要素の値の絶対値の総和を返す。
      int	slist_abssum(const struct slist *);
      		
    16. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最初のものへのポインタを返す。
      struct scell	*slist_first_min(const struct slist *);
      		
    17. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最後のものへのポインタを返す。
      struct scell	*slist_last_min(const struct slist *);
      		
    18. 要素の値を、一行に一つの書式で、並んでいる順に出力する。
      void	slist_print(const struct slist *);
      		
    19. (欠番)

    20. リストを反転する。
      void	slist_reverse(struct slist *);
      		
  2. 末尾つき単方向線形リスト(ダミーセルなし)について、以下を行なう関数をそれぞれ書け。 ただし、tslist.hに以下の型定義が書かれているものとする。 どの関数についても、関数の第一引数は、struct tslist * 型またはconst struct tslist * 型とする。 struct tslistの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。
    	struct scell {
    		struct scell	*next; /* 次のセルを指すポインタ */
    		int		data;
    	};
    	struct tslist {
    		struct scell	*head; /* 先頭のセルを指すポインタ */
    		struct scell	*tail; /* 末尾のセルを指すポインタ */
    	};
    	    
    リストの初期化は以下の関数tslist_init()で行うものとする。
    #include <stdlib.h>
    #include "tslist.h"
    
    void
    tslist_init(struct tslist *list)
    {
    	list->head = NULL;
    }
                
    セルの生成と削除は、以下の課題を通じて整合的なものにすること。 たとえば、以下の方法がある。
    • 新たなセルを確保してそれを指すポインタをpに格納するには:
      	p = malloc(sizeof(struct scell));
      		
    • ポインタpが指すセルを削除するには:
      	free(p);
      		
    1. 先頭のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*tslist_first(struct tslist *);
      		
    2. 末尾のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*tslist_last(struct tslist *);
      		
    3. n番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*tslist_nth(struct tslist *, size_t);
      		
    4. 最後からn番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct scell	*tslist_nth_last(struct tslist *, size_t);
      		
    5. リストを空リストにする。不要なセルは削除する。struct tslistの実体は削除しない。
      void	tslist_clear(struct tslist *);
      		
    6. 第二引数で与えられた値を持つセルを生成し、 先頭に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*tslist_insert_head(struct tslist *, int);
      		
      ヒント
      tslist_insert_after()を先に作って使うと便利。
    7. 第二引数で与えられた値を持つセルを生成し、 末尾に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*tslist_insert_tail(struct tslist *, int);
      		
      ヒント
      tslist_insert_after()を先に作って使うと便利。
    8. (欠番)

    9. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直後に挿入する。 挿入したセルを指すポインタを返す。
      struct scell	*tslist_insert_after(struct tslist *, int, struct scell *);
      		
    10. 先頭のセルを削除する。
      void	tslist_remove_head(struct tslist *);
      		
      ヒント
      tslist_remove_after()を先に作って使うと便利。
    11. 末尾のセルを削除する。
      void	tslist_remove_tail(struct tslist *);
      		
      ヒント
      tslist_remove_after()を先に作って使うと便利。
    12. 第二引数でポインタで指定されたセルの直後のセルを削除する。
      void	tslist_remove_after(struct tslist *, struct scell *);
      		
    13. 第二引数(int)の値に応じて、以下のようにする。
      0
      リストの要素の総個数を返す。
      1
      リストの要素のうち、奇数の値をもつものの個数を返す。
      2
      リストの要素のうち、偶数の値をもつものの個数を返す。
      その他
      常に0を返す。
      size_t	tslist_count_fancy(const struct tslist *, int);
      		
    14. 要素の値の総和を返す。
      int	tslist_sum(const struct tslist *);
      		
    15. 要素の値の絶対値の総和を返す。
      int	tslist_abssum(const struct tslist *);
      		
    16. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最初のものへのポインタを返す。
      struct scell	*tslist_first_min(const struct tslist *);
      		
    17. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最後のものへのポインタを返す。
      struct scell	*tslist_last_min(const struct tslist *);
      		
    18. 要素の値を、一行に一つの書式で、並んでいる順に出力する。
      void	tslist_print(const struct tslist *);
      		
    19. (欠番)

    20. リストを反転する。
      void	tslist_reverse(struct tslist *);
      		
  3. 末尾つき双方向線形リスト(ダミーセルなし)について、以下を行なう関数をそれぞれ書け。 ただし、dlist.hに以下の型定義が書かれているものとする。 どの関数についても、関数の第一引数は、struct dlist * 型またはconst struct dlist * 型とする。 struct dlistの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。
    struct dcell {
    	struct dcell	*next; /* 次のセルを指すポインタ */
    	struct dcell	*prev; /* 前のセルを指すポインタ */
    	int		data;
    };
    struct dlist {
    	struct dcell	*head; /* 先頭のセルを指すポインタ */
    	struct dcell	*tail; /* 末尾のセルを指すポインタ */
    };
    	    
    リストの初期化は以下の関数dlist_init()で行うものとする。
    #include <stdlib.h>
    #include "dlist.h"
    
    void
    dlist_init(struct dlist *list)
    {
    	list->head = NULL;
    	list->tail = NULL;
    }
                
    セルの生成と削除は、以下の課題を通じて整合的なものにすること。 たとえば、以下の方法がある。
    • 新たなセルを確保してそれを指すポインタをpに格納するには:
      	p = malloc(sizeof(struct dcell));
      		
    • ポインタpが指すセルを削除するには:
      	free(p);
      		
    1. 先頭のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*dlist_first(struct dlist *);
      		
    2. 末尾のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*dlist_last(struct dlist *);
      		
    3. n番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*dlist_nth(struct dlist *, size_t);
      		
    4. 最後からn番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*dlist_nth_last(struct dlist *, size_t);
      		
    5. リストを空リストにする。不要なセルは削除する。struct dlistの実体は削除しない。
      void	dlist_clear(struct dlist *);
      		
    6. 第二引数で与えられた値を持つセルを生成し、 先頭に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*dlist_insert_head(struct dlist *, int);
      		
    7. 第二引数で与えられた値を持つセルを生成し、 末尾に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*dlist_insert_tail(struct dlist *, int);
      		
    8. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直前に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*dlist_insert_after(struct dlist *, int, struct dcell *);
      		
    9. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直後に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*dlist_insert_after(struct dlist *, int, struct dcell *);
      		
    10. 先頭のセルを削除する。
      void	dlist_remove_head(struct dlist *);
      		
    11. 末尾のセルを削除する。
      void	dlist_remove_tail(struct dlist *);
      		
    12. 第二引数でポインタで指定されたセルを削除する。
      void	dlist_remove(struct dlist *, struct dcell *);
      		
    13. 第二引数(int)の値に応じて、以下のようにする。
      0
      リストの要素の総個数を返す。
      1
      リストの要素のうち、奇数の値をもつものの個数を返す。
      2
      リストの要素のうち、偶数の値をもつものの個数を返す。
      その他
      常に0を返す。
      size_t	dlist_count_fancy(const struct dlist *, int);
      		
    14. 要素の値の総和を返す。
      int	dlist_sum(const struct dlist *);
      		
    15. 要素の値の絶対値の総和を返す。
      int	dlist_abssum(const struct dlist *);
      		
    16. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最初のものへのポインタを返す。
      struct dcell	*dlist_first_min(const struct dlist *);
      		
    17. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最後のものへのポインタを返す。
      struct dcell	*dlist_last_min(const struct dlist *);
      		
    18. 要素の値を、一行に一つの書式で、並んでいる順に出力する。
      void	dlist_print(const struct dlist *);
      		
    19. 要素の値を、一行に一つの書式で、並んでいるのとは逆順に出力する。
      void	dlist_print_reverse(const struct dlist *);
      		
    20. リストを反転する。
      void	tslist_reverse(struct dlist *);
      		
  4. 末尾つき双方向線形リスト(ダミーセルなし)について、以下を行なう関数をそれぞれ書け。 ただし、tdlist.hに以下の型定義が書かれているものとする。 どの関数についても、関数の第一引数は、struct tdlist * 型またはconst struct tdlist * 型とする。 struct tdlistの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。
    struct dcell {
    	struct dcell	*next; /* 次のセルを指すポインタ */
    	struct dcell	*prev; /* 前のセルを指すポインタ */
    	int		data;
    };
    struct tdlist {
    	struct dcell	*head; /* 先頭のセルを指すポインタ */
    };
    	    
    リストの初期化は以下の関数tdlist_init()で行うものとする。
    #include <stdlib.h>
    #include "tdlist.h"
    
    void
    tdlist_init(struct tdlist *list)
    {
    	list->head = NULL;
    	list->tail = NULL;
    }
                
    セルの生成と削除は、以下の課題を通じて整合的なものにすること。 たとえば、以下の方法がある。
    • 新たなセルを確保してそれを指すポインタをpに格納するには:
      	p = malloc(sizeof(struct dcell));
      		
    • ポインタpが指すセルを削除するには:
      	free(p);
      		
    1. 先頭のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*tdlist_first(struct tdlist *);
      		
    2. 末尾のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*tdlist_last(struct tdlist *);
      		
    3. n番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*tdlist_nth(struct tdlist *, size_t);
      		
    4. リストを空リストにする。不要なセルは削除する。struct tdlistの実体は削除しない。
      		  
    5. 最後からn番目(0始まり)のセルを指すポインタを返す。存在しないときはNULLを返す。
      struct dcell	*tdlist_nth_last(struct tdlist *, size_t);
      		    
    6. void tdlist_clear(struct tdlist *);
    7. 第二引数で与えられた値を持つセルを生成し、 先頭に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*tdlist_insert_head(struct tdlist *, int);
      		
    8. 第二引数で与えられた値を持つセルを生成し、 末尾に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*tdlist_insert_tail(struct tdlist *, int);
      		
    9. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直前に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*tdlist_insert_after(struct tdlist *, int, struct dcell *);
      		
    10. 第二引数で与えられた値を持つセルを生成し、 第三引数で与えられたポインタで指定されたセルの直後に挿入する。 挿入したセルを指すポインタを返す。
      struct dcell	*tdlist_insert_after(struct tdlist *, int, struct dcell *);
      		
    11. 先頭のセルを削除する。
      void	tdlist_remove_head(struct tdlist *);
      		
    12. 末尾のセルを削除する。
      void	tdlist_remove_tail(struct tdlist *);
      		
    13. 第二引数でポインタで指定されたセルを削除する。
      void	tdlist_remove(struct tdlist *, struct dcell *);
      		
    14. 第二引数(int)の値に応じて、以下のようにする。
      0
      リストの要素の総個数を返す。
      1
      リストの要素のうち、奇数の値をもつものの個数を返す。
      2
      リストの要素のうち、偶数の値をもつものの個数を返す。
      その他
      常に0を返す。
      size_t	tdlist_count_fancy(const struct tdlist *, int);
      		
    15. 要素の値の総和を返す。
      int	tdlist_sum(const struct tdlist *);
      		
    16. 要素の値の絶対値の総和を返す。
      int	tdlist_abssum(const struct tdlist *);
      		
    17. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最初のものへのポインタを返す。
      struct dcell	*tdlist_first_min(const struct tdlist *);
      		
    18. 最小の値を持つセルへのポインタを返す。 ただし、リストが空のときは、NULLポインタを返す。 最小の値を持つセルが複数あるときは、そのうち最後のものへのポインタを返す。
      struct dcell	*tdlist_last_min(const struct tdlist *);
      		
    19. 要素の値を、一行に一つの書式で、並んでいる順に出力する。
      void	tdlist_print(const struct tdlist *);
      		
    20. 要素の値を、一行に一つの書式で、並んでいるのとは逆順に出力する。
      void	tdlist_print_reverse(const struct tdlist *);
      		
    21. リストを反転する。
      void	tslist_reverse(struct tdlist *);
      		

戻る