LoginSignup
0
0

More than 1 year has passed since last update.

@hu-yu

[CS50] week5 - Data structures part2

Posted at

初めに

前回の続きです。

単方向リスト（Singly linked list）

反転（Reverse）

反転された値を格納する配列

リストにアクセスして値をコピーし、配列の最後尾から最初まで値を入れていく。リストの順はそのままです。

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

typedef struct Node
{
  int data;
  struct Node *next;
} demoNode;

// note: don't know why use static here?
static void reverse(demoNode **headRef)
{
  demoNode *current = *headRef;
  int size = 0;

  while (current != NULL)
  {
    size++;
    current = current->next;
  }

  int arr[size];
  int count = size - 1;

  current = *headRef;
  while (current != NULL)
  {
    arr[count--] = current->data;
    current = current->next;
  }

  current = *headRef;
  count = 0;
  while (current != NULL)
  {
    current->data = arr[count++];
    current = current->next;
  }
}

void display(demoNode *node)
{
  printf("List: ");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;
  demoNode *node4 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));
  node4 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 12;
  node2->next = node3;
  node3->data = 3;
  node3->next = node4;
  node4->data = 25;
  node4->next = NULL;

  display(head);
  reverse(&head);
  display(head);

  return 0;
}
// List: 10 12 3 25
// List: 25 3 12 10

複雑なことを考えなくても反転した要素を出力するメソッドですが、データタイプが違っている場合はたぶん通用しないと思います。

（こういったときには、ポインタ配列なら解決できそうかな...？やったことないのでアイディアとして残ります。）

リストノードを逆順に出力する

// form the last node to the first node
void display(demoNode *node)
{
  if (node == NULL)
  {
    return;
  }
  display(node->next);
  printf("%d ", node->data);
}

int main(void)
{
  demoNode *previous = NULL;
  demoNode *head = NULL;
  demoNode *current = NULL;
  int size;

  printf("Enter size of linked list: ");
  scanf("%d", &size);
  for (int i = 0; i < size; i++)
  {
    current = (demoNode *)malloc(sizeof(demoNode));

    printf("Enter the data: ");
    scanf("%d", &(current->data));
    current->next = NULL;

    if (head == NULL)
    {
      head = current;
    }
    else
    {
      previous->next = current;
    }
    previous = current;
  }
  display(head);
  printf("\n");
  return 0;
}
// Enter size of linked list: 3
// Enter the data: 1
// Enter the data: 2
// Enter the data: 3
// 3 2 1

リストノードを反転する

膨大なデータの入力では、ノードがいつも最初の位置に挿入したら、ループで最後の位置を探さずすぐに入れれるのが効率的ですが、入力順とは逆になってしまって不便なこともあります。なのでリストを反転するのがとても重要だと思います。

void reverseLinkedList(demoNode **head)
{
  demoNode *previous = NULL;
  demoNode *next = NULL;
  demoNode *current = *head;

  // not empty list
  while (current != NULL)
  {
    // store second node address first
    next = current->next;
    // point to the previous node address
    // head node points to NULL
    current->next = previous;
    // the previous node moves one position ahead
    previous = current;
    // the current node also moves on
    current = next;
    // note: head(first node)->
  }
  *head = previous;
}

void insert(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

int main(void)
{
  int number;
  int data;
  demoNode *head = NULL;
  printf("Enter the number of nodes: ");
  scanf("%d", &number);
  printf("Enter the data in the nodes: \n");
  for (int i = 0; i < number; i++)
  {
    scanf("%d", &data);
    insert(&head, data);
  }

  printf("Given linked list: ");
  display(head);

  printf("Reversed linked list: ");
  reverseLinkedList(&head);
  display(head);

  return 0;
}
// Enter the number of nodes: 3
// Enter the data in the nodes:
// 2
// 3
// 5
// Given linked list: 5 3 2
// Reversed linked list: 2 3 5

reverseLinkedList()のループではとても短いコードで反転処理を済ませたが、実際はどう行っているかとても気になっていて図を作成してみました。

reverselist1.png

reverselist2.png

reverselist3.png

reverselist4.png

reverselist5.png

reverselist6.png

reverselist7.png

reverselist8.png

reverselist9.png

reverselist10.png

reverselist11.png

reverselist12.png

reverselist13.png

（図ではheadがmain()のheadとして作成されている。reverseLinkedList()の*headと同じものを指している。）

パースの経過も一緒に描いて少し読みづらいかもしれないが、要するにほかに三つのノードを用意しておいて、例えばreverseLinkedList()ではpreviousとcurrentは交換する主要ノードで、previousは初めから今施しているノードまでのリストを保存していて、最終的にcurrentは前のノードpreviousに指させる。nextはcurrentの後のノードリストを把握する。すべてのアドレスを失わせないように最低でも三つのポインタによって保存されなければならない。（もっと賢い方法があるかもしれないがここでの話。）ノードが増えても残りのノードのアドレスをしっかり把握すれば中断されない。

（ポインタheadの中身ではdemoNode1のアドレスを持っているということで、*headはdemoNode1にアクセスできてheadとdemoNode1が同じものだと思われがちですが、ポインタheadとノードdemoNode1とは、生存範囲（storage）も中身に入れるものも全然違います。）

ループ内の手順としてはいつも通り後ろからですね。
nextで次のループで処理するノードアドレスを持たせ、
currentで今指しているノードのnextを、前のノードpreviousに指させ、
previousが今指しているアドレスはcurrent->nextで参照されているからpreviousを移動させ、
currentも次のnextに移動させる。
最後のループが終わったときpreviousが最後のノードに指していて、currentはNULLに指している。
それで一番先頭の*headに最後のノードpreviousを。

Reverse a linked list in groups of given size

指定した数でノードをグループにして反転させる。

例えば参考文章のようにリストの構成要素は、
20 15 64 8 1 53 45 17 58 91があります。
reverse (head, 4)では4つのノードがグループとして処理する。
8 64 15 20, 17 45 53 1, 91 58

reverse()関数のループの中身は上のreverseLinkedList()関数のループは全く一緒で、ループ終了後もし次のノードNULLでなければ次のノードnextが再帰関数のheadとして入れ、そしていつも反転したグループの最後のノードpreviousを返し、連結させる。

demoNode *reverse(demoNode *head, int memberSize)
{
  demoNode *current = head;
  demoNode *next = NULL;
  demoNode *previous = NULL;
  int counter = 0;

  while (current != NULL && counter < memberSize)
  {
    next = current->next;
    current->next = previous;
    previous = current;
    current = next;
    counter++;
  }
  if (next != NULL)
  {
    head->next = reverse(next, memberSize);
  }
  return previous;
}

void insert(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

int main(void)
{
  demoNode *head = NULL;
  insert(&head, 10);
  insert(&head, 55);
  insert(&head, 24);
  insert(&head, 37);
  insert(&head, 45);
  insert(&head, 1);
  insert(&head, 9);
  insert(&head, 15);
  insert(&head, 66);

  printf("Before: \n");
  display(head);
  head = reverse(head, 4);
  printf("After: \n");
  display(head);

  return 0;
}
// Before:
// 66 15 9 1 45 37 24 55 10
// After:
// 1 9 15 66 55 24 37 45 10

サーチ（Search）

指定する値を持つノードをサーチする（Search an element in list）

// loop
// int searchElement(demoNode *head, int target)
// {
//   demoNode *current = head;
//   int index = 0;

//   while (current != NULL)
//   {
//     if (current->data == target)
//     {
//       return index;
//     }
//     current = current->next;
//     index++;
//   }
//   // not found
//   return -1;
// }

// recursion
int searchElement(demoNode *head, int target, int index)
{
  // list doesn't exist or value is not found
  if (head == NULL)
  {
    return -1;
  }

  if (head->data == target)
  {
    return index;
  }

  index++;
  return searchElement(head->next, target, index);
}

int main(void)
{
  int target;

  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;
  demoNode *node4 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));
  node4 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 15;
  node2->next = node3;
  node3->data = 20;
  node3->next = node4;
  node4->data = 25;
  node4->next = NULL;

  printf("Current list: \n");
  display(head);
  printf("Enter value to search: ");
  scanf("%d", &target);

  // int index = searchElement(head, target);
  int index = searchElement(head, target, 0);
  if (index == -1)
  {
    printf("Element not found\n");
  }
  else
  {
    printf("Element found at position: %d\n", index + 1);
  }
  return 0;
}
// Current list:
// 10 15 20 25
// Enter value to search: 25
// Element found at position: 4

// Current list:
// 10 15 20 25
// Enter value to search: 5
// Element not found

真ん中のノードを見つけ出す（Find the middle element）

ループでは倍速と普通の速度で移動するノードをそれぞれ設置し、普通のほうが1/2の速度で移動するので、倍速のほうが最後のノードかNULLを指しているようになったら、普通のほうが真ん中にいるということです。

void findMiddle(demoNode *head)
{
  demoNode *normalSpeed = head;
  demoNode *doubleSpeed = head;

  if (head != NULL)
  {
    while (doubleSpeed != NULL && doubleSpeed->next != NULL)
    {
      doubleSpeed = doubleSpeed->next->next;
      normalSpeed = normalSpeed->next;
    }
    printf("The middle element in the linked list is: %d\n", normalSpeed->data);
  }
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;
  demoNode *node4 = NULL;
  demoNode *node5 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));
  node4 = (demoNode *)malloc(sizeof(demoNode));
  node5 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 33;
  head->next = node2;
  node2->data = 10;
  node2->next = node3;
  node3->data = 5;
  node3->next = node4;
  node4->data = 26;
  node4->next = node5;
  node5->data = 67;
  node5->next = NULL;

  printf("Link: \n");
  display(head);
  findMiddle(head);

  return 0;
}
// Link:
// 33 10 5 26 67
// The middle element in the linked list is: 5

リストの最後尾から指定位置のノードを見つけ出す（Find nth node from the end）

demoNode *findNthFromEnd(demoNode *head, int nth)
{
  demoNode *temp = head;
  int size = 0;

  // move onto the end
  while (temp)
  {
    size++;
    temp = temp->next;
  }

  // when nth is valid in list
  if (size >= nth && nth > 0)
  {
    temp = head;
    for (int i = 0; i < size - nth; i++)
    {
      temp = temp->next;
    }
  }

  return temp;
}

void push(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

int main(void)
{
  int arr[] = {1, 2, 3, 4, 5};
  int length = sizeof(arr) / sizeof(arr[0]);

  demoNode *head = NULL;
  for (int i = 0; i < length; i++)
  {
    push(&head, arr[i]);
  }

  display(head);

  // int nth = 5;
  int nth = 1;
  demoNode *node = findNthFromEnd(head, nth);

  if (node)
  {
    printf("nth node from the end is %d\n", node->data);
  }

  return 0;
}
// 5 4 3 2 1
// nth node from the end is 5
// 5 4 3 2 1
// nth node from the end is 1

最後尾に追加する（Append）と先頭に追加する（Prepend）

先頭に挿入すると最後尾に挿入する（Prepend and append）

前回での最初位置に挿入（InsertStart）と最後位置に挿入（InsertEnd）と同じロジックです。

// insertStart/push/CreateNode...
void prependNode(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

// insertLast
void appendNode(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = NULL;

  if (*head == NULL)
  {
    *head = newNode;
    return;
  }

  demoNode *temp = *head;
  while (temp->next != NULL)
  {
    temp = temp->next;
  }
  temp->next = newNode;
}

int main(void)
{
  demoNode *head = NULL;
  prependNode(&head, 1);
  prependNode(&head, 2);
  prependNode(&head, 3);
  display(head);

  appendNode(&head, 8);
  appendNode(&head, 9);
  appendNode(&head, 10);
  display(head);

  return 0;
}
// List: 3 2 1 
// List: 3 2 1 8 9 10

ノードを最後尾から先頭に移動させる（Move the last node to the beginning）

void push(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

void moveToFront(demoNode **head, int num)
{
  for (int i = 0; i < num; i++)
  {
    if (*head == NULL || (*head)->next == NULL)
    {
      return;
    }
    // the last one
    demoNode *last = *head;
    // the second-to-last one
    demoNode *secondLast = NULL;
    while (last->next != NULL)
    {
      secondLast = last;
      last = last->next;
    }
    // the second-to-last become the last one
    secondLast->next = NULL;
    // connect the original head
    last->next = *head;
    // become the first one
    *head = last;
  }
}

int main(void)
{
  // int num = 2;
  int num = 10;
  demoNode *head = NULL;
  push(&head, 56);
  push(&head, 12);
  push(&head, 31);
  push(&head, 69);
  push(&head, 20);
  push(&head, 75);
  push(&head, 6);
  push(&head, 17);

  printf("Before: \n");
  display(head);
  moveToFront(&head, num);
  printf("After: \n");
  display(head);

  return 0;
}
// Before:
// 17 6 75 20 69 31 12 56
// After:
// 12 56 17 6 75 20 69 31

ソート（Sort）

バブルソート（Bubble sort）

void sortLinkedList(demoNode **head)
{
  demoNode *current = *head;
  demoNode *nextNode = NULL;
  int tempValue = 0;

  if (head == NULL)
  {
    return;
  }

  // bubble sort
  while (current != NULL)
  {
    nextNode = current->next;

    while (nextNode != NULL)
    {
      if (nextNode != NULL && current->data > nextNode->data)
      {
        tempValue = current->data;
        current->data = nextNode->data;
        nextNode->data = tempValue;
      }
      nextNode = nextNode->next;
    }
    current = current->next;
  }
}

int main(void)
{
  demoNode *head = NULL;
  prependNode(&head, 1);
  prependNode(&head, 2);
  prependNode(&head, 3);
  display(head);

  sortLinkedList(&head);
  display(head);

  return 0;
}
// List: 3 2 1
// List: 1 2 3

折り畳み（Fold）

リストを折り返す

使い道はあまりよく分からないので一応参考文章をメモります。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0