本日の目標
- 自己参照構造体を使ってリスト構造を作ることができる。
- リストへのデータの追加、挿入、削除などの操作をポインタの掛け替えによって実現できる。
- リスト構造を使って探索することができる。
予習・復習
以下のスライドを利用して、予習と復習をしよう。復習では、自分の理解度を確認するために、実際にプログラムを作成し、意図する結果が得られるか確認しよう。本日の講義・演習予定
- リスト構造
- 双方向リスト
- 循環リスト
- 演習問題
- 提出課題
内 容
リスト構造
リストとは
データを順番に並べたデータ構造を連結リストと呼びます。（本稿では単にリストと呼ぶことにします。）配列も順番に並んだデータを扱うデータ構造です。配列との違いは、配列が連続してデータが配置されているの対して、リストは下図のように離れたデータを紐で繋いだような構造をしています。
リストを構成する一つ一つの要素をノード(node)またはセル(cell)と呼びます。ノードは、データとは別にノード間を連結（リンク）するための情報を含む構造体として定義されます。連結情報は連結先のノードの開始アドレスを格納するためのノード型のポインタです。ノードは同じ型のポインタをそのメンバとして持つことから、自己参照構造体と呼ばれます。
ノードの例として、1つのint型からなるデータと連結情報となるポインタからなる構造体は次のように定義されます。
struct node {
int data;
struct node *next;
}
リストの操作
リストへのノードの追加・挿入、リストからのノードの削除といった操作は、図１に示すようにリンクの掛け替え、すなわちポインタの値の変更によって簡単に実現することができます。ノードの新規生成では、その格納領域を実行時に必要に応じて確保(malloc)し、ポインタを使って連結することができます。削除では、リンクの切断はポインタをNULLとして、その領域は解放(free)します。配列がコンパイル時に格納するためのメモリアドレスとそのサイズが決定される静的なデータ構造に対して、リストはメモリの効率的な利用が実現できる動的なデータ構造であると言えます。
| 操作 | リスト | 配列 |
| 追加 | データを格納するために必要なメモリ領域を割り当て、既存のデータとリンクする | あらかじめサイズが決められているので要素数以上の追加は出来ない |
| 挿入 | データを格納するために必要なメモリ領域を割り当て、既存のデータとリンクすると同時に既存のデータ間のリンクを付け替える | 挿入位置から後ろのデータをすべてずらさなければならず、末尾にデータあればそのデータは失われる |
| 削除 | 削除したいデータへのリンクを既存のデータへ付け替え、データからのリンクは削除する。メモリ領域を解放する。 | 削除することで空いた要素を埋めるために、以降のデータをすべて前にずらさなけらばならいことがある |
リスト構造の主な種類
- 単方向リスト
- 双方向リスト
- 循環リスト
単方向リスト
一方向に連結された構造を持つリストを単方向リストと呼びます。ノードにはデータと次のノードを示すポインタ（アドレス）が格納されます。先頭と最後尾のノードはそれぞれ、先頭ノード(head node)、末尾ノード(tail node)と呼ばれます。後続のノードのポインタが先行するノードを示すことで連結（link)を実現します。リストを示すための重要な要素が先頭ノードを示すHEADポインタです。このHEADポインタをたどることで先頭から末尾までのノードを順に参照することができます。
以下に、データにint型の数値とキー、そしてポインタからなる構造体nodeをノードとするリストのサンプルプログラムを示します。
linkedlist.c
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true 1
#define false !true
/* 構造体ノード */
struct node {
int data;
int key;
struct node *next; //リンク
};
typedef struct node Node;
void print_list(void); //リストを表示する
bool is_empty(void); //リストは空か
void insert_first(int key, int data); //先頭にノードを追加する
void delete_first(void); //先頭ノードの削除
bool delete(int key); //keyによるノードの削除
Node *head = NULL; //先頭ポインタ
/* 表示 */
void print_list(void)
{
Node *p = head;
printf("\n[ ");
while(p!=NULL){
printf("(%d,%d) -> ",p->key,p->data);
p = p->next; //次のノード
}
printf("NULL ]\n");
}
/* リストは空か */
bool is_empty(void)
{
return head==NULL;
}
/* 先頭へ新規ノードを追加 */
void insert_first(int key, int data)
{
Node *new = (Node *)malloc(sizeof(Node)); //新規ノードのための領域
if(new != NULL){
new->data = data;
new->key = key;
new->next = head; //旧先頭ノードへリンク
head = new; //先頭ノードを新規ノードに
}
}
/* 先頭ノードの削除 */
void delete_first(void)
{
Node *tmp;
if(is_empty()){ //リスト空の時
fprintf(stderr,"Error: List is empty.\n");
exit(EXIT_FAILURE);
}
tmp = head; //先頭ポインタ退避
head = head->next; //次のノードに付け替え
free(tmp); //先頭ノード領域解放
}
/*
* 指定ノードの削除
* @key 探索キー
*/
bool delete(int key){
Node *current = head; //探索対象ノード
Node *prev = NULL; //探索対象前のノード
if(is_empty()){ //リスト空の時
fprintf(stderr,"Error: List is empty.\n");
exit(EXIT_FAILURE);
}
//探索
while([[空欄ア]]!= key){
if(current->next == NULL) return false; //探索失敗
prev = current;
current = current->next; //探索対象を次のノードへ
}
//削除ノードをバイパス
if(current == head)
head = head->next;
else
[[空欄イ]];
[[空欄ウ]]; //削除ノードの領域解放
return true; //成功
}
int main(void)
{
Node *target;
insert_first(1,100); //先頭に追加
insert_first(2,200);
insert_first(3,300);
insert_first(4,150);
insert_first(5,250);
insert_first(6,500);
puts("Original List: ");
print_list();
puts("\ndelete all item.");
while(!is_empty()){
delete_first();
}
print_list();
insert_first(1,100); //先頭に追加
insert_first(2,200);
insert_first(3,300);
insert_first(4,150);
insert_first(5,250);
insert_first(6,500);
puts("\nRestored List: ");
print_list();
printf("delete(3): ");
delete(3);
print_list();
//printf("find(5) = ");
//target = find(5);
//printf("(%d %d)\n", target->key, target->data);
//printf("sort: ");
//sort();
//print_list();
//printf("reverse: ");
//reverse(&head);
//print_list();
//printf("insert_last");
//insert_last(7,7000);
//print_list();
return 0;
}
OPEN ANSWER
- ア. current->key
- イ. prev->next = current->next
- ウ. free(current)
双方向リスト
双方向リスト(doubly linked list)は、前方のノードへのリンク(ポインタ)と後方のノードへのリンク(ポインタ)の両方向へのリンク(ポインタ)を持つリストです。先頭ノードはポインタheadによって示され、先頭ノードの前方ノードへのリンクはNULLへ接続されます。末尾ノードの後方ノードへのリンクはNULLに接続します。末尾ノードをポインタtailで示すこともできます。ノードの持つデータを前方と後方のどちらかも順に参照することができるリスト構造です。双方向から効率の良い探索が実現できるメリットがある反面、構造が複雑になり、リンクのために多くのメモリが必要になるというデメリットがあります。
サンプルプログラム
doublylinkedlist.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define bool int
#define true 1
#define false !true
#define FORWARD 1
#define BACKWARD 0
struct node {
int data;
int key;
struct node *next; //次のノード
struct node *prev; //前のノード
};
typedef struct node Node;
bool is_empty();
int length(void);
void insert_first(int key, int data);
bool insert_after(int key, int newkey,int data);
Node *delete_first(void);
Node * delete_tail(void);
void print_list(void);
Node *head = NULL; //先頭ポインタ
Node *tail = NULL; //末尾ポインタ
/* 空リスト? */
bool is_empty(void)
{
return head == NULL;
}
/* リストの長さ */
int length(void)
{
Node *current;
int length=0;
for(current=head; current!=NULL; current=current->next) length++;
return length;
}
/* 先頭に追加 */
void insert_first(int key, int data)
{
Node *new = (Node *)malloc(sizeof(Node)); //ノード生成
new->key = key;
new->data = data;
if(is_empty())
tail = new; //空なら末尾参照
else
head->prev = new; //旧先頭ノードの前へ
new->next = head; //新ノードの後ろに旧先頭ノードを接続
new->prev = NULL;
head = new; //新ノードを先頭ノードへ
}
/* 指定ノード後ろに追加 */
bool insert_after(int key, int newkey,int data)
{
Node *current = head;
if(head == NULL) return false;
while(current->key != key){
if(current->next == NULL)
return false;
else
current = current->next;
}
Node *new = (Node *)malloc(sizeof(Node));
new->key = key;
new->data = data;
if(current == tail){
new->next = NULL;
tail = new;
}
else {
new->next = current->next;
current->next->prev = new;
}
new->prev = current;
current->next=new;
return 0;
}
/* 先頭ノードの削除*/
Node *delete_first(void)
{
Node *tmp = head;
if(head->next == NULL)
tail = NULL;
else
head->next->prev = NULL;
head = head->next;
return tmp;
}
/* 最後尾ノードの削除*/
Node * delete_tail(void)
{
Node *tmp = tail;
if(head->next == NULL) head = NULL; else tail->prev->next = NULL;
tail = tail->prev;
return tmp;
}
/*
* リスト表示
*/
void print_list(void)
{
Node *p = head;
printf("\n[ ");
while(p!=NULL){
printf("(%d,%d) ",p->key,p->data);;
p=p->next;
}
printf(" ]\n");
}
/* メイン関数 */
int main(void)
{
insert_first(1,1000);
insert_first(2,2000);
insert_first(3,3000);
insert_first(4,500);
insert_first(5,600);
insert_first(6,5000);
print_list();
return 0;
}
循環リスト
単方向リストの末尾ノードのポインタが先頭ノードを示すようにしたものを循環リスト(circular list）と言います。ポインタheadの移動によって全体の順序をずらすことができたり、先頭ノードに戻って探索し直す必要がないと行ったメリットがあります。一方で、末尾を示すNULLがないため、末尾ノードもしくは先頭ノードを知る手段を用意しなければなりません。
また、双方向リストにおいて、先頭ノードの前方リンクを末尾ノードへ、末尾ノードの後方リンクを先頭ノードへリンクした構造を双方向循環リストと言います。
サンプルリスト
circularlist.c
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true 1
#define false !true
struct node_t {
int key;
int data;
struct node_t *next;
};
typedef struct node_t Node;
void insert_first(int key, int data);
bool delete_first(void);
int length(void);
bool is_empty(void);
void print_list(void);
Node *head = NULL;
/* 先頭へのノード追加 */
void insert_first(int key, int data)
{
Node *new = (Node *)malloc(sizeof(Node)); //先頭へ
new->key = key;
new->data = data;
if(is_empty()){
head = new;
head->next = head; //自身へ循環
}
else {
new->next = head; //旧先頭ノードへリンク
head = new; //先頭ノードへ
}
}
/* 先頭ノードの削除 */
bool delete_first(void)
{
Node *tmp = head;
if(is_empty()) return false;
if(head->next == head)
head = NULL; //Only one
else
head = head->next;
free(tmp);
return true;
}
/* リストの空判定 */
bool is_empty(void)
{
return head == NULL;
}
/* リストの長さ */
int length(void)
{
int len=1;
Node *p=head;
if(is_empty()) return 0;
while(p->next!=p){
len++;
p = p->next;
}
return len;
}
void print_list(void)
{
Node *p = head;
if(is_empty()){
printf("Empty list.\n");
return;
}
printf("\n[");
while(p->next != p){
printf(" %d |",p->data);
p = p->next;
};
printf(" %d ]\n",p->data);
}
int main(void)
{
insert_first(1,1000);
insert_first(2,2000);
insert_first(3,3000);
insert_first(4,4000);
insert_first(5,5000);
print_list();
printf("list length: %d\n",length());
delete_first();
print_list();
return 0;
}
expand_lessBack to TOP
演習問題
- 単方向リストに次の各機能を追加しなさい。また、その動作を確認するためのテストを実行しなさい。
- リストが空であるかどうかを調べる関数bool is_empty(void)を追加しなさい。リストが空の時には１をそうでない時には０を戻り値とします。
- リストの長さ（ノード数）を戻り値とする関数int length(void)を追加しなさい。
- 探したいデータのキーを入力して目的のデータを探し出す関数Node *find(int key)を作成しなさい。
- リストの末尾にノードを追加する関数void insert_last(int key, int data)を追加しなさい。
- ノードを昇順に並べ替える関数void sort(void)を追加しなさい。
- ノードを逆順に並べ替える関数void reverse(Node **head)を追加しなさい。
- 指定のノードを削除する関数void delete(int key)の空欄ア〜ウを埋めて完成させなさい。また、ノードを削除する際のリンクの付け替えの過程を図示しなさい。
- 双方向リストに次の各機能を追加しなさい。また、その動作を確認するためのテストを実行しなさい。
- リストの最後尾にノードを追加する関数void insert_tail(int key, int data)を追加しなさい。
- リストから指定（キー指定）のノードを削除する関数Node * delete(int key)を追加しなさい。
- リストのデータを末尾のノードから順に先頭ノードまで表示する関数void print_list_backword(void)を追加しなさい。
OPEN ANSWER
1.解答例
- リストが空か調べる関数
- リストの長さを調べる関数
- 探索関数
- 末尾へノードを追加する関数
- ソートする関数
- 逆順に並べ換える関数
- 指定ノードの削除
bool is_empty(void)
{
return head==NULL;
}
int length(void)
{
int count = 0;
Node *current = head;
while(current!=NULL){
current = current->next;
}
return count;
}
Node *find(int key){
Node *current = head;
if(head == NULL) return NULL;
while(current->key != key){
if(current->next == NULL) return NULL;
current = current->next;
}
return current;
}
void insert_last(int key, int data)
{
Node *p = head;
Node *new = (Node *)malloc(sizeof(Node));
if(new != NULL){
new->data = data;
new->key = key;
if(is_empty()){
new->next = head;
head = new;
}
else{
while(p->next!=NULL) p=p->next;
new->next = NULL;
p->next = new;
}
}
}
void sort(void)
{
int i,j,tmp,size;
Node *current, *next;
size = length();
for(i=0; i<size-1; i++){
current = head;
next = head->next;
for(j=1; j<size; j++){
if(current->data > next->data){
tmp = current->data; //入れ替え
current->data = next->data;
next->data = tmp;
tmp = current->key;
current->key = next->key;
next->key = tmp;
}
current = current->next;
next = next->next;
}
}
}
void reverse(Node **head)
{
Node *prev = NULL;
Node *current = *head;
Node *next;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
Node* delete(int key){
Node *current = head; //探索対象ノード
Node *prev = NULL; //探索対象前のノード
if(is_empty()){ //リスト空の時
fprintf(stderr,"Error: List is empty.\n");
exit(EXIT_FAILURE);
}
//探索
while(current->key != key){
if(current->next == NULL) return NULL; //探索失敗
prev = current;
current = current->next; //探索対象を次のノードへ
}
//対象ノードをバイパス
if(current == head)
head = head->next;
else
prev->next = current->next;
free(current); //削除ノードの領域解放
return current;
}
2. 解答例
/* 最後尾に追加 */
void insert_tail(int key, int data)
{
Node *new = (Node *)malloc(sizeof(Node)); //ノード生成
new->key = key;
new->data = data;
if(is_empty()){
tail = new; //空なら末尾参照
}
else {
tail->next = new; //旧最後尾ノードから新ノードへ接続
new->prev = tail; //新ノードから旧最後尾ノードへ接続
}
tail = new; //新ノードを最後尾に置き換え
}
/* 指定ノードの削除*/
Node * delete(int key)
{
Node *current = head;
Node *prev = NULL;
if(head==NULL){
return NULL;
}
//キーの探索
while(current->key != key){
if(current->next == NULL){
return NULL;
}
else{
prev = current; //前方を現行に
current = current->next; //現行は次へ
}
}
if(current==head) //先頭にマッチ
head = head->next;
else
current->prev->next = current->next; //前ノードから次ノードへの繫ぎ変え
if(current==tail) //最後尾にマッチ
tail = current->prev;
else
current->next->prev = current->prev; //次ノードから前ノードへの繫ぎ変え
return current;
}
void print_list_backword(void)
{
Node *p = tail;
printf("\n[ ");
while(p!=NULL){
printf("(%d,%d) ",p->key,p->data);;
p=p->prev;
}
printf(" ]\n");
}
expand_lessBack to TOP
今週の確認テスト テスト(PDF)
本日の提出課題
以下のプログラムは、IDと名前を予め単方向リストに追加しておき、そのリストから入力した名前で検索できるようにと作成したものです。しかし、まだ、処理に必要な関数が完成していません。関数を完成させて、正しい結果が得られるようにしなさい。ただし、ソースコードに記述されている２つのヘッダファイル以外は追加できないものとします。
#include <stdio.h>
#include <stdlib.h>
struct node {
int id;
char name[64];
struct node *next;
};
typedef struct node Node;
//プロトタイプ宣言
int match(char s1[], char s2[]); //文字列の一致
void insert_first(int id, char name[]); //リストの先頭への追加
Node* find(char name[]); //探索
void print_list(); //リスト一覧の表示
Node *head = NULL;
int main(void)
{
char name[64];
Node *s;
insert_first(1001,"Momota");
insert_first(1002,"Tamai");
insert_first(1003,"Sasaki");
insert_first(1004,"Akimoto");
insert_first(1005,"Takagi");
printf("検索したい名前> ");
scanf("%s",name); //scanf_s("%s",name,64);
if((s=find(name))!=NULL){
printf("見つかりました。ID:%d NAME:%s\n",s->id,s->name);
}
else{
printf("見つかりませんでした。\n");
print_list();
}
return 0;
}
[実行例1]
検索したい名前> Sasaki 見つかりました。ID:1003 NAME:Sasaki
[実行例2]
検索したい名前> Hayami 見つかりませんでした。 [->(1005,Takagi)->(1004,Akimoto)->(1003,Sasaki)->(1002,Tamai)->(1001,Momota)]
- [提出方法]
- 電子メールの添付ファイルとして提出してください。宛先は指定のアドレスです。
- 表題は、課題５とします。
- メール本文中にはプログラムを作成するにあたり苦労した点を記すこと。
- 添付ファイルは下記の２点です。
- 1) ソースコード・ファイル kadai4-5.c
- 2) 実行結果画面(ウインドウのみ)のハードコピーの画像ファイル kadai4-5.jpg
- [実行結果画面のハードコピーの取り方]
- [メニュー]→[アクセサリ]→Snipping Toolを起動する。ただし、Snipping Toolのウインドウが実行画面に重ならないように、必要に応じてウインドウを移動すること。
- タイトルバーを含めた実行結果画面をマウスドラッグして選択して、キャプチャする。
- メニューから「ファイル」→「名前をつけて保存」を選択する。ファイルの種類にはJPG形式を選択して、保存先フォルダを選び、ファイル名を付けて「保存」する。
- [評価について] プログラムの内容の評価とは別に以下の要件を満たすことを評価の前提とする。
- ソースコードがC言語で記述されていること。
- 提出されたソースコードファイルをコンパイルし、ワーニングやエラーが出力されないこと。scanfをscanf_sとすべきワーニングについては除外する。
- 提出されたソースコードファイルから生成される実行形式ファイルを実行した結果、所定の出力結果が得られること。
- 提出されたソースコードは、インデントや適当な改行が施された見やすい状態であること。
- 変数の利用目的、処理や判定の意味など必要と思われる解説を簡潔にコメント文として付けること。
- 提出された実行結果の画面コピーは、コマンドプロンプトのウインドウのみとすること。
- [提出期限]
- 2019年 １２月２５日（水）午後２時まで