題目2: リスト

ソースコードのひな型および実行例

実験1: 関数printList

ソースコードのひな型

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node* next;
};

/* 実験 1 で作成 */
void printList( struct node* head ) {
  /* 内容は自分で作る */
}

int main(void){
  struct node* head;
  struct node* p;

  /* 最初にダミーノードを用意しておく */
  head = (struct node*) malloc(sizeof(struct node));
  head->next = NULL;

  /* 1 個目のノードを作成 */
  p = (struct node*) malloc(sizeof(struct node));
  p->data = 16;
  head->next = p;  

  /* 2 個目のノードを 1 個目のノードの後ろに作成 */
  p->next = (struct node*) malloc(sizeof(struct node));
  p = p->next;
  p->data = 28;

  /* 3 個目のノードを 2 個目のノードの後ろに作成 */
  p->next = (struct node*) malloc(sizeof(struct node));
  p = p->next;
  p->data = 100;

  /* 3 個目のノードでおしまいなので，next を NULL にする */
  p->next = NULL;

  /* リストの内容が順番に表示される */
  printList(head);

  /* 確保したメモリを解放する */
  while (head) {
    p = head->next;
    free(head);
    head = p;
  }

  return 0;
}

実行例

$ ./a.out
16 28 100

実験2: 関数search

ソースコードのひな型

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node* next;
};

/* 実験 2 で作成 */
int search( struct node* head, int x ){
  /* 内容は自分で作る */
}

int main(void){
  struct node* head;
  struct node* p;
  int n, x;

  /* 最初にダミーノードを用意しておく */
  head = (struct node*) malloc(sizeof(struct node));
  head->next = NULL;

  /* 1 個目のノードを作成 */
  p = (struct node*) malloc(sizeof(struct node));
  p->data = 16;
  head->next = p;  

  /* 2 個目のノードを 1 個目のノードの後ろに作成 */
  p->next = (struct node*) malloc(sizeof(struct node));
  p = p->next;
  p->data = 28;

  /* 3 個目のノードを 2 個目のノードの後ろに作成 */
  p->next = (struct node*) malloc(sizeof(struct node));
  p = p->next;
  p->data = 100;

  /* 3 個目のノードでおしまいなので，next を NULL にする */
  p->next = NULL;

  /* x を読み込み，それがリスト内の何番目にあるか調べる */
  printf("目的の値を入力して下さい > ");
  scanf("%d", &x);

  n = search(head, x);
  if ( -1 == n ){
     printf("%d は見つかりませんでした\n", x);
  }
  else{
     printf("%d は %d 番目に見つかりました\n", x, n);
  }

  /* 確保したメモリを解放する */
  while (head) {
    p = head->next;
    free(head);
    head = p;
  }

  return 0;
}

実行例

$ ./a.out
目的の値を入力して下さい > 28
28 は 2 番目に見つかりました

実験3: 関数append

ソースコードのひな型

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node* next;
};

/* 実験 1 で作成 */
void printList( struct node* head ) {
  /* 内容は自分で作る */
}

/* 実験 3 で作成 */
void append( struct node* head, int x ){
  /* 内容は実験テキストを参照 */
}


int main(void){
  struct node* head;
  int x;
  struct node* p;

  /* 最初にダミーノードを用意しておく */
  head = (struct node*) malloc(sizeof(struct node));
  head->next = NULL;

  printf("値を繰り返し入力して下さい（-1で終了）: \n");
  /* 内容は自分で作る： */
  /*  scanf で値を読み込みながら append でその値をリストに追加 */
  /* （ヒント）while 文で繰り返す */


  /* 確保したメモリを解放する */
  while (head) {
    p = head->next;
    free(head);
    head = p;
  }

  return 0;
}

実行例

$ ./a.out
値を繰り返し入力して下さい（-1で終了）:
1
2
3
4
5
-1
1 2 3 4 5

実験4: 関数delete

ソースコードのひな型

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node* next;
};

/* 実験 1 で作成 */
void printList( struct node* head ){
  /* 内容は自分で作る */
}

/* 実験 3 で作成 */
void append( struct node* head, int x ){
  /* 内容は実験テキストを参照 */
}

/* 実験 4 で作成 */
void delete( struct node* head ) {
  /* 内容は自分で作る */  
}

int main(void){
  struct node* head, *p;

  /* 最初にダミーノードを用意しておく */
  head = (struct node*) malloc(sizeof(struct node));
  head->next = NULL;

  append( head, 16 );
  append( head, 28 );
  append( head, 100 );
  
  printf("== 初期状態 ==\n");
  printList( head );

  printf("\n== delete 1 回目 ==\n");
  delete( head );
  printList( head );

  printf("\n== delete 2 回目 ==\n");
  delete( head );
  printList( head );

  printf("\n== delete 3 回目 ==\n");
  delete( head );
  printList( head );

  printf("\n== delete 4 回目 ==\n");
  delete( head );
  printList( head );

  /* 確保したメモリを解放する */
  while (head) {
    p = head->next;
    free(head);
    head = p;
  }

  return 0;
}

実行例

$ ./a.out
== 初期状態 ==
16 28 100 

== delete 1 回目 ==
16 28 

== delete 2 回目 ==
16 

== delete 3 回目 ==


== delete 4 回目 ==
 *** エラー： リストは空です ***