読者です 読者をやめる 読者になる 読者になる

はわわーっ

はわわわわっ

配列とリストの線形探索

c

やってみた。
まず配列のほう。

#include <stdio.h>

int *search(int *, size_t, int);

int *
search(int *array, size_t size, int value)
{
  size_t i;

  for (i = 0; i < size; i++) {
    if (array[i] == value) {
      return &array[i];
    }
  }
  return NULL;
}


int
main(void)
{
  int array[] = {3, 1, 4, 5, 9, 2 };
  size_t size = sizeof(array)/sizeof(array[0]);
  int *p;

  p = search(array, size, 3);
  if (p == NULL) {
    printf("not found\n");
  } else {
    printf("found: %d\n", *p);
  }

  p = search(array, size, 7);
  if (p == NULL) {
    printf("not found\n");
  } else {
    printf("found: %d\n", *p);
  }

  return 0;
}

で、リストのほう。
ついでに配列からリストを作る関数も作った。

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

typedef struct List_tag List;
struct List_tag {
  int value;
  List *next;
};

List *from_array(const int *, size_t);
void free_list(List *list);
List *search(List *, int);


List *
from_array(const int *array, size_t size)
{
  size_t i;
  List *list, *elem, *tail;

  list = malloc(sizeof(List));
  if (list == NULL) { return NULL; }
  list->next = NULL;
  tail = list;

  for (i = 0; i < size; i++) {
    elem = malloc(sizeof(List));
    if (elem == NULL) { free_list(list); return NULL; }

    elem->value = array[i];
    elem->next = NULL;
    tail->next = elem;
    tail = elem;
  }

  return list;
}

void
free_list(List *list)
{
  List *p = list->next;

  while (p != NULL) {
    list->next = p->next;
    free(p);
    p = list->next;
  }
  free(list);
}

List *
search(List *list, int x)
{
  List *p = list->next;

  while (p != NULL) {
    if (p->value == x) { return p; }
    p = p->next;
  }
  return NULL;
}


int
main(void)
{
  int array[] = {3, 1, 4, 5, 9, 2 };
  List *list = from_array(array, sizeof(array)/sizeof(array[0]));
  List *p;

  p = search(list, 3);
  if (p == NULL) {
    printf("not found\n");
  } else {
    printf("found: %d\n", p->value);
  }

  p = search(list, 7);
  if (p == NULL) {
    printf("not found\n");
  } else {
    printf("found: %d\n", p->value);
  }

  free_list(list);
  return 0;
}

うーん、こんなんでいいのかな。
よくわからん。。。