書籍

C言語プログラミングハーベイ M.ダイテル (著), ポール J.ダイテル (著), 小嶋隆一 (翻訳)
- https://www.amazon.co.jp/dp/4894710293?ref=ppx_yo2ov_dt_b_fed_asin_title
開発環境
- VSCode

12.6: 2つの連結リスト(データは文字)を結合

C言語

#include <stdio.h>
#include <conio.h>

typedef struct list{
   struct list *next;
   char cData;
}List;

void printList(List *);
List *concatenate(List *, List *);

int main()
{
    List a, b, c, d;
    List *con;

    printf("リスト1\n");
    a.cData = 'X';
    a.next = &b;

    b.cData = 'Y';
    b.next = NULL;
    printList(&a);

    printf("リスト2\n");
    c.cData = 'Z';
    c.next = &d;

    d.cData = '!';
    d.next = NULL;
    printList(&c);
    
    printf("連結後\n");
    con = concatenate(&a, &c);
    printList(con);
    
    getch();
    return 0;
}

void printList(List *headPtr)
{
     while (headPtr != NULL)
     {
             printf("%c\n", headPtr -> cData);
             headPtr = headPtr -> next;
     }
}

List *concatenate(List *a, List *c)
{
     List *headPtr;

     headPtr = a;
     while(a -> next != NULL)
     {
       a = a -> next;
     }

     a -> next = c;

     return headPtr;
}

Python

12.7: 2つの順序リスト(データは整数)を結合

C言語

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

typedef struct list{
   struct list *next;
   int iData;
}List;

void printList(List *);
List *merge(List *, List *);

int main()
{
    List a, b, c, d;
    List *mer;

    printf("リスト1\n");
    a.iData = 100;
    a.next = &b;
   
    b.iData = 200;
    b.next = NULL;
    printList(&a);

    printf("リスト2\n");
    c.iData = 50;
    c.next = &d;

    d.iData = 300;
    d.next = NULL; 
    printList(&c);

    getch();
    
    printf("併合後\n");
    mer = merge(&a, &c);
    printList(mer);
    
    getch();
    return 0;
}

void printList(List *headPtr)
{
     while (headPtr != NULL)
     {
          printf("%d\n", headPtr -> iData);
          headPtr = headPtr -> next;
     }
}

List* merge(List* a, List* c) 
{
    List tentative;
    List* tail = &tentative;
    tentative.next = NULL;
    
    while (a != NULL && c != NULL) 
    {
        if (a -> iData <= c -> iData)
        {
            tail -> next = a;
            a = a -> next;
        } 
        else 
        {
            tail -> next = c;
            c = c -> next;
        }
        tail = tail -> next;
    }
    
    if (a != NULL)
    {
        tail -> next = a;
    }
    else 
    {
        tail -> next = c;
    }
    
    return tentative.next;
}

Python

12.8: 25個の乱数を連結リストに昇順に挿入(各ノードの合計と浮動小数点平均も計算)

12.7で作った関数mergeを使うのも手

C言語

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

// ノードの構造体を定義
struct Node {
    int data;
    struct Node* next;
};

// 新しいノードを作成する関数
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        fprintf(stderr, "メモリの確保に失敗しました。\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// リストに昇順でノードを挿入する関数
int insertInOrder(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (newNode == NULL) {
        return 0; // メモリの確保に失敗した場合
    }
    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
    } else {
        struct Node* current = *head;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
    return 1;
}

// リストを表示する関数
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// リストのメモリを解放する関数
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    struct Node* head = NULL;
    int sum = 0;
    srand(time(0));

    for (int i = 0; i < 25; i++) {
        int randNum = rand() % 101; // 0から100の乱数を生成
        if (insertInOrder(&head, randNum)) {
            sum += randNum;
        } else {
            // メモリの確保に失敗した場合、メモリを解放して終了
            freeList(head);
            return 1;
        }
    }

    float average = sum / 25.0;

    printf("連結リスト (昇順):\n");
    printList(head);

    printf("ノードの値の合計: %d\n", sum);
    printf("ノードの値の平均: %.2f\n", average);

    // メモリの解放
    freeList(head);

    return 0;
}

Python

import random

# define node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# A function to insert nodes into a list in ascending order
def insert_in_order(head, data):
    new_node = Node(data)
    if head is None or head.data >= data:
        new_node.next = head
        return new_node
    else:
        current = head
        while current.next is not None and current.next.data < data:
            current = current.next
        new_node.next = current.next
        current.next = new_node
    return head

# A function to print list
def print_list(head):
    current = head
    while current is not None:
        print(f'{current.data} -> ', end='')
        current = current.next
    print('None')

# A function to free the memory of a list
def free_list(head):
    while head is not None:
        temp = head
        head = head.next
        del temp

def main():
    head = None
    total_sum = 0

    for _ in range(25):
        rand_num = random.randint(0, 100)
        head = insert_in_order(head, rand_num)
        total_sum += rand_num

    average = total_sum / 25.0

    print('連結リスト (昇順):')
    print_list(head)

    print(f'ノードの値の合計: {total_sum}')
    print(f'ノードの値の平均: {average:.2f}')

    # free memory
    free_list(head)

if __name__ == '__main__':
    main()

12.9: 10個のノードからなる連結リスト(データは文字)を生成し、最初のリストとは逆の順序で2つ目のリストを生成

C言語

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

// ノードの構造体を定義
struct Node {
    char data;
    struct Node* next;
};

// 新しいノードを作成する関数
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// リストの末尾にノードを追加する関数
void appendNode(struct Node** head, char data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// リストを表示する関数
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%c -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// リストを逆順にする関数
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// メモリを解放する関数
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 連結リストを生成
    struct Node* head = NULL;
    char data[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};

    for (int i = 0; i < 10; i++) {
        appendNode(&head, data[i]);
    }

    printf("元のリスト:\n");
    printList(head);

    // 逆順のリストを生成
    struct Node* reversedHead = reverseList(head);

    printf("逆順のリスト:\n");
    printList(reversedHead);

    // メモリの解放
    freeList(reversedHead);

    return 0;
}

Python

12.10: 入力された1行のテキストをスタックを使って逆向きにプリント

C言語

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

typedef struct stackNode{
  char data;
  struct stackNode *nextPtr;
}StackNode;

void push(StackNode **, char);
char pop(StackNode **);

int main()
{ 
    StackNode *stackPtr;
    char string[100];
    int i = 0;

    printf("文字列を入力してください\n");
    fgets(string, sizeof(string), stdin);

    while (string[i] != '\n' && string[i] != '\0')
    {
        push(&stackPtr, string[i]);
        i++;
    }

    while (i > 0)
    {
        printf("%c", pop(&stackPtr));
        i--;
    }
    getch();
    return 0;
}

void push(StackNode **topPtr, char info)
{
    StackNode *newPtr;

    newPtr = (StackNode *)malloc(sizeof(StackNode));

    if (newPtr != NULL)
    {
        newPtr -> data = info;
        newPtr -> nextPtr = *topPtr;
        *topPtr = newPtr;
    }
    else
    {
        printf("空きメモリがないので %d は挿入できません\n");
    }
}

char pop(StackNode **topPtr)
{
    StackNode *tempPtr;
    char popValue;

    tempPtr = *topPtr;
    popValue = (*topPtr) -> data;
    *topPtr = (*topPtr) -> nextPtr;
    free(tempPtr);
    
    return popValue;
}

Python

12.11: スタックを使い文字列が回文(前から見ても後ろから見ても同じスペルの文字列)か判定

スペースや句点は無視

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define SIZE 100

typedef struct stackNode{
    char data;
    struct stackNode *nextPtr;
} StackNode;

void push(StackNode **, char);
char pop(StackNode **);
void removePunctuation(char *, char *);

int main() { 
    StackNode *stackPtr = NULL;
    char string[SIZE];
    char cleanedString[SIZE];
    char reverse[SIZE];
    int i; 
    int count = 0;
    
    printf("回文であるかを判定します\n");
    printf("文字列を入力してください\n");
    gets(string);
    printf("入力文字列: %s\n", string);

    // 句読点を取り除いた文字列を作成
    removePunctuation(string, cleanedString);
    printf("句読点を取り除いた文字列: %s\n", cleanedString);

    // スタックに文字列をつめていく
    for (i = 0; cleanedString[i] != '\0' && cleanedString[i] != '\n'; i++) {
        push(&stackPtr, cleanedString[i]);
        count++;
    }

    // スタックから文字列を取り出す
    for (i = 0; i < count; i++) {
        reverse[i] = pop(&stackPtr);
    }
    reverse[i] = '\0';
    printf("逆転した文字列: %s\n", reverse);

    // 結果表示
    if (strcmp(cleanedString, reverse) == 0) {
        printf("回文です\n");
    } else {
        printf("回文ではありません\n");
    }

    getch();
    return 0;
}

void push(StackNode **topPtr, char info) {
    StackNode *newPtr = (StackNode *)malloc(sizeof(StackNode));

    if (newPtr != NULL) {
        newPtr->data = info;
        newPtr->nextPtr = *topPtr;
        *topPtr = newPtr;
    } else {
        printf("空きメモリがないので %d は挿入できません\n", info);
    }
}

char pop(StackNode **topPtr) {
    StackNode *tempPtr;
    char popValue;

    tempPtr = *topPtr;
    popValue = (*topPtr)->data;
    *topPtr = (*topPtr)->nextPtr;
    free(tempPtr);
    
    return popValue;
}

void removePunctuation(char *source, char *destination) {
    int j = 0;
    for (int i = 0; source[i] != '\0'; i++) {
        if (isalnum(source[i])) {
            destination[j++] = source[i];
        }
    }
    destination[j] = '\0';
}

Python

12.12: 1桁の整数を使った中置算術式を後置記法に変換

中置: (6 + 2) * 5 - 8 / 4
後置: 6 2 + 5 * 8 4 / -

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// スタックのノードを表す構造体
typedef struct stackNode{
  char data;
  struct stackNode *nextPtr;
}StackNode;

// d 
void push(StackNode **, char);

// e 
char pop(StackNode **);

// b
int isOperator(char);

// f 
char stackTop(StackNode **);

// h
void printStack(StackNode **);

// c
int precedence(char, char);

// g スタックが空であるかを判定する関数
int isEmpty(StackNode **);      

// a
void convertToPostfix(char [], char []);

int main()
{ 
    char infix[100];
    char postfix[100];  
 
   
    printf("中間式を入力してください\n");
    fgets(infix, sizeof(infix), stdin);
    
    convertToPostfix(infix, postfix);

    printf("%s\n", postfix);
  
    getch(); 

    return 0;
}

void push(StackNode **topPtr, char info)
{
    StackNode *newPtr;

    newPtr = (StackNode *)malloc(sizeof(StackNode));

    if (newPtr != NULL)
    {
        newPtr -> data = info;
        newPtr -> nextPtr = *topPtr;
        *topPtr = newPtr;
    }
    else
    {
        printf("空きメモリがないので %d は挿入できません\n");
    }
}

char pop(StackNode **topPtr)
{
    StackNode *tempPtr;
    char popValue;

    tempPtr = *topPtr;
    popValue = (*topPtr) -> data;
    *topPtr = (*topPtr) -> nextPtr;
    free(tempPtr);
    
    return popValue;
}

int isOperator(char c)
{
    if (c == '+')
    {
        return 1;
    }
    else if (c == '-')
    {
        return 1;
    }
    else if (c == '*')
    {
        return 1;
    }
    else if (c == '/')
    {
        return 1;
    }
    else if (c == '%')
    {
        return 1;
    }
    else if (c == '^')
    {
        return 1;
    }
    return 0;
}

// スタックが空かは呼び出し側で対応
char stackTop(StackNode **topPtr)
{
    return(*topPtr) -> data;
}

// スタックが空であるかを判定する関数
// 引数: topPtr(スタックの先頭位置のアドレスを格納するポインタへのポインタ
// 戻り値: 1 空である 0 空でない
int isEmpty(StackNode **topPtr)
{
    if (*topPtr == NULL)
    {
        return 1;
    }
    return 0;
}

void printStack(StackNode **topPtr)
{
    StackNode *tmpPtr;

    if (*topPtr == NULL)
    {
        printf("スタックは空ですn"); 
        return;
    }
 
    // 先頭データを表示
    printf("%c\n", (*topPtr) -> data);
    tmpPtr = (*topPtr) -> nextPtr;

    while (tmpPtr != NULL)
    {
        printf("%c\n", tmpPtr -> data);
        tmpPtr = tmpPtr -> nextPtr;
    }
    getch();
}

int precedence(char op1, char op2)
{
    static int level[58];
    static int first = 1;
  
    if (first == 1)
    {
       level[0] = 13; // %
       level[5] = 13; // *
       level[6] = 12; // +
       level[8] = 12; // -
       level[10] = 13; // /
       level[57] = 7;  // ^
       first = 0;
    }

    if (level[op1 - '%'] < level[op2 - '%'])
    {
        return -1;
    }
    else if (level[op1 - '%'] == level[op2 - '%'])
    {
        return 0;
    }
    return 1;    
}

void convertToPostfix(char infix[], char postfix[])
{
    StackNode *stackPtr = NULL;
    char c;
    int now = 0;
    int next = 0;

    push(&stackPtr, '(');

    infix[strlen(infix) - 1] =  ')';

    // スタックが空でない間
    while (isEmpty(&stackPtr) == 0 && now < 100)
    {
         // 数字なら
         if (isdigit(infix[now]))
         {
             postfix[next] = infix[now];
             next++;
             postfix[next] = ' ';
             next++;
         }
         // 左括弧なら
         else if (infix[now] == '(')
         {
             push(&stackPtr, infix[now]);
         }
         // 演算子なら
         else if (isOperator(infix[now]))
         {
             // スタックに演算子があるなら
             if (isOperator(stackTop(&stackPtr)))  
             {
                 c = stackTop(&stackPtr);

                 // 取り出したものが演算子でその演算子の優先度が,現在の演算子より
                 // 高いか等しい間
                 while (isOperator(c) && precedence(c, infix[now]) >= 0)
                 {
                      c = pop(&stackPtr);
                      postfix[next] = c;
                      next++;
                      postfix[next] = ' ';
                      next++;
                      c = stackTop(&stackPtr);
                 }
             }
             push(&stackPtr, infix[now]);
         }
         // 右括弧ならば
         else if (infix[now] == ')')
         {
             // スタックの先頭が左括弧でない間
             while (stackTop(&stackPtr) != '(')
             {
                 c = pop(&stackPtr);
                 postfix[next] = c;
                 next++;
                 postfix[next] = ' ';
                 next++;
             }
             pop(&stackPtr);
         }
         // infixの次の要素へ
         now++;
    }
     
    postfix[next] = '\0';
}

Python

12.13: 1桁の数字と演算子からなる後置算術式を評価

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define SIZE 100
#define DEBUG(x) x

// スタックのノードを表す構造体
typedef struct stackNode{
  int data;
  struct stackNode *nextPtr;
}StackNode;

void push(StackNode **, int);
char pop(StackNode **);
int isOperator(char);
int calculate(int, int, char);
int evaluatePostfixExpression(char *, int);

int main()
{ 
    char postfix[100];  
    int result;

   
    printf("後置式を入力してください\n");
    fgets(postfix, sizeof(postfix), stdin);  
    DEBUG(printf("postfix %s\n", postfix));
    
    // 空なら終了(fgets)
    if (postfix[1] ==  '\0')
    {
        return 0;
    }  
    
    result = evaluatePostfixExpression(postfix, 100);

    printf("result %d\n", result);
    getch();
    return 0;
}

void push(StackNode **topPtr, int info)
{
    StackNode *newPtr;

    newPtr = (StackNode *)malloc(sizeof(StackNode));

    if (newPtr != NULL)
    {
        newPtr -> data = info;
        newPtr -> nextPtr = *topPtr;
        *topPtr = newPtr;
    }
    else
    {
        printf("空きメモリがないので %d は挿入できません\n");
    }
}

char pop(StackNode **topPtr)
{
    StackNode *tempPtr;
    char popValue;

    tempPtr = *topPtr;
    popValue = (*topPtr) -> data;
    *topPtr = (*topPtr) -> nextPtr;
    free(tempPtr);
    
    return popValue;
}

int isOperator(char c)
{
    if (c == '+')
    {
        return 1;
    }
    else if (c == '-')
    {
        return 1;
    }
    else if (c == '*')
    {
        return 1;
    }
    else if (c == '/')
    {
        return 1;
    }
    else if (c == '%')
    {
        return 1;
    }
    else if (c == '^')
    {
        return 1;
    }
    return 0;
}

int evaluatePostfixExpression(char * postfix, int size)
{
    int now;
    int x, y;
    int num;
    StackNode *stackPtr = NULL;

    for (now = 0; postfix[now] != '\0' && now < size; now++)
    {
        // 数字なら
        if (isdigit(postfix[now]))
        {
            push(&stackPtr, postfix[now] - '0');
        }
        // 演算子なら
        else if (isOperator(postfix[now]))
        {
            x = pop(&stackPtr);
            y = pop(&stackPtr);

            push(&stackPtr, calculate(y, x, postfix[now]));
        }
    }
    return pop(&stackPtr);
}

int calculate(int y, int x, char c)
{
    if (c == '+')
    {
        return y + x;
    }
    else if (c == '-')
    {
        return y - x;
    }
    else if (c == '*')
    { 
        return y * x;
    }
    else if (c == '/')
    {
        return y / x;        
    }
    else if (c == '%')
    {
        return y % x;
    }
    else if (c == '^')
    {
        return y ^ x;
    }
}

Python

12.14: 12.13の後置式評価プログラムをオペランドが2桁以上の整数でも処理できるように改造

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define SIZE 100
#define DEBUG(x) x

// スタックのノードを表す構造体
typedef struct stackNode{
  int data;
  struct stackNode *nextPtr;
}StackNode;

void push(StackNode **, int);
int pop(StackNode **);
int isOperator(char);
int evaluatePostfixExpression(char *, int);
int calculate(int, int, char);

int main()
{ 
    char postfix[100];  
    int result;

   
    printf("後置式を入力してください\n");
    fgets(postfix, sizeof(postfix), stdin);  
    
    // 空なら終了(fgets)
    if (postfix[1] ==  '\0')
    {
        return 0;
    }  
    
    result = evaluatePostfixExpression(postfix, 100);

    printf("result %d\n", result);
    getch();
    return 0;
}

void push(StackNode **topPtr, int info)
{
    StackNode *newPtr;

    newPtr = (StackNode *)malloc(sizeof(StackNode));

    if (newPtr != NULL)
    {
        newPtr -> data = info;
        newPtr -> nextPtr = *topPtr;
        *topPtr = newPtr;
    }
    else
    {
        printf("空きメモリがないので %d は挿入できません\n");
    }
}

int pop(StackNode **topPtr)
{
    StackNode *tempPtr;
    int popValue;

    tempPtr = *topPtr;
    popValue = (*topPtr) -> data;
    *topPtr = (*topPtr) -> nextPtr;
    free(tempPtr);
    return popValue;
}

int isOperator(char c)
{
    if (c == '+')
    {
        return 1;
    }
    else if (c == '-')
    {
        return 1;
    }
    else if (c == '*')
    {
        return 1;
    }
    else if (c == '/')
    {
        return 1;
    }
    else if (c == '%')
    {
        return 1;
    }
    else if (c == '^')
    {
        return 1;
    }
    return 0;
}

int evaluatePostfixExpression(char * postfix, int size)
{
    int now;
    int x, y;
    int num;
    StackNode *stackPtr = NULL;

    
    for (now = 0; postfix[now] != '\0' && now < size; now++)
    {
        // 数字なら
        if (isdigit(postfix[now]))
        {
            // 文字としての数値を整数値に変換する
            for (num = 0; postfix[now] != ' '; now++)
            {
                num = num * 10 + (postfix[now] - '0');
            }
            push(&stackPtr, num);
        }
        // 演算子なら
        else if (isOperator(postfix[now]))
        {
            x = pop(&stackPtr);
            y = pop(&stackPtr);
            push(&stackPtr, calculate(y, x, postfix[now]));
        }
    }
    return pop(&stackPtr);
}

int calculate(int y, int x, char c)
{
    if (c == '+')
    {
        return y + x;
    }
    else if (c == '-')
    {
        return y - x;
    }
    else if (c == '*')
    { 
        return y * x;
    }
    else if (c == '/')
    {
        return y / x;        
    }
    else if (c == '%')
    {
        return y % x;
    }
    else if (c == '^')
    {
        return y ^ x;
    }
}

Python

12.15: スーパーマーケットのレジの行列をシミュレート

応用: 最適レジ数の導出(顧客の到着間隔、顧客のサービス時間、レジ設置予算などのパラメータのもと)

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>

// デバッグ用
#define DEBUG(x) x

// 到着間隔
#define ARRIVE_INTERVAL 4

// キュー構造体
typedef struct queue{
   int number;              // 何人目の顧客であるか
   int arriveTime;          // レジに到着した時刻
   struct queue *next;
}Queue;


// キューにデータを入れる関数
int enQueue(Queue **, Queue **, int, int);

// キューからデータを取り出す関数
int deQueue(Queue **, Queue **, int *);

// キューが空を調べる関数
int isEmpty(Queue *);

// キューの情報を表示
void printQueue(Queue *);

// キューのデータの個数を求める関数
int checkQueueNum(Queue *);

int main()
{
    int nowTime;           // スタートしてからの経過分
    int number = 1;        // 顧客の番号
    int serviceTime;       // 顧客のサービス時間
    int nextArrivetime;    // 次の顧客の到着時間
    int serviceNum;        // 現在サービスを受けている顧客の番号
    int arriveTime;        // その顧客がレジに到着した時間
    int waitTime;          // その顧客がサービスを受けるまでに待たされた時間
    int maxWaittime = -1;  // 最大何分待たされたか
    int queueNum;          // キューに何人待たされているか
    int maxqueueNum = -1;  // 最大何人待たされたか
    Queue *headPtr = NULL; // キューの先頭を指すポインタ
    Queue *tailPtr = NULL; // キューの最後尾を指すポインタ

    srand(time(NULL));

    // 最初の顧客が到着したことを表示
    printf("%dさんが到着しました\n", number);

    // 最初の顧客の到着時間を求める
    nowTime = rand() % ARRIVE_INTERVAL + 1;

    // 最初の顧客のサービス時間を決める
    serviceTime = rand() % 4 + 1;
    
    // 最初の顧客に対してサービスを開始する
    serviceNum = 1;
    printf("%dさんのサービスを開始します\n", serviceNum);
            
    // 次の顧客の到着時間を求める
    nextArrivetime = nowTime + (rand() % ARRIVE_INTERVAL + 1); 

    // 次に到着する顧客
    number++;

    // 720分間シュミレーションを行う
    while (nowTime < 720)
    { 
        // 次の顧客が到着したら
        if (nowTime >= nextArrivetime)
        {
            // 顧客が到着したことを表示する
            printf("%dさんが到着しました\n\n", number);

            // その顧客をキューにつなぐ
            if ((enQueue(&headPtr, &tailPtr, number, nowTime)) == -1)
            {
                 fprintf(stderr, "メモリ領域の確保に失敗しました\n");
                 // ここに今までに確保したQueueの動的領域を解放する処理を書く
                 return -1;    
            }

            // 次の顧客の到着時間を求める
            nextArrivetime = nowTime + (rand() % ARRIVE_INTERVAL + 1); 
 
            // 次に到着する顧客
            number++;
        }
          
        // 現在の顧客に対するサービスが終了したら
        if (serviceTime <= 0)
        {
            // サービスが完了したことを表示する
            printf("%dさんのサービスが完了しました\n\n", serviceNum);

            // 顧客がいるならば
            if (isEmpty(headPtr) == 0)
            {
                // 次の顧客をキューから取り出して,その顧客に対してサービスを開始する
                serviceNum = deQueue(&headPtr, &tailPtr, &arriveTime);
                printf("%dさんのサービスを開始します\n", serviceNum);

                // 待たされた時間を計算
                waitTime = nowTime - arriveTime;

                DEBUG(printf("\n%dさんはサービスを受けるまで%d分待たされました\n\n", serviceNum, waitTime));

                // 今までで最も待たされた時間ならば
                if (waitTime > maxWaittime)
                {
                    maxWaittime = waitTime; 
                }
                // その顧客のサービス完了時刻を計算する
                serviceTime = rand() % 4 + 1;
            }
        }
 
        // 今現在何人レジに待たされているかを調べる        
        queueNum = checkQueueNum(headPtr);
 
        // 今までで最もレジに人がいるならば
        if (queueNum > maxqueueNum)
        {
            maxqueueNum = queueNum;
        }
       
        DEBUG(printf("時刻%d: \n", nowTime));
        DEBUG(printQueue(headPtr));

        // 1分経過
        nowTime++;
        serviceTime--;
    }

    printf("\n%d人到着しました\n\n", number - 1);
    printf("\n最大%d分待たされました\n\n", maxWaittime);
    printf("\n最大%d人レジで待たされました\n\n", maxqueueNum);

    // ここに今までに確保したQueueの動的領域を解放する処理を書く
    getch();
    return 0;
}

// キューにデータを入れる関数
// 戻り値 -1以外 正常終了 -1 メモリ領域確保失敗
int enQueue(Queue **headPtr, Queue **tailPtr, int num, int time)
{
    Queue *newPtr;
    
     
    // メモリ領域の確保に失敗したならば
    if ((newPtr = (Queue *)malloc(sizeof(Queue))) == NULL)
    {
         return -1;
    }

    // データの挿入
    newPtr -> number = num;
    newPtr -> next = NULL;
    newPtr -> arriveTime  = time;

    // キューが空ならば
    if (isEmpty(*headPtr))
    {
        // 新しく生成したノードを先頭に登録する
        *headPtr = newPtr;
    }
    else
    {
        // 最後尾の次のノードとして登録する
        (*tailPtr) -> next = newPtr;
    }

    // 最後尾を更新
    *tailPtr = newPtr;

    return 0;
}

// キューの情報を表示
void printQueue(Queue *currentPtr)
{
    if (currentPtr == NULL) 
    {
        printf("レジには誰もいません\n\n");
    }
    else
    {
        printf("サービス待ちの人:\n");

        while (currentPtr != NULL)
        {
            printf("%d -> ", currentPtr -> number);
            currentPtr = currentPtr -> next;
        }

        printf("NULL\n\n");
    }
}

// キューが空を調べる関数
// 戻り値 0以外 空である 0 空でない
int isEmpty(Queue *headPtr)
{
    return headPtr == NULL;
}

// キューからデータを取り出す関数
int deQueue(Queue **headPtr, Queue **tailPtr, int *time)
{
    Queue *tempPtr;
    int value;

    value = (*headPtr) -> number;
    *time = (*headPtr) -> arriveTime;
    tempPtr = *headPtr;
    *headPtr = (*headPtr) -> next;

    if (*headPtr == NULL)
    {
        *tailPtr = NULL;
    }

    free(tempPtr);
    
    return value;
}

// キューのデータの個数を求める関数
// 戻り値 キューに格納されているデータの個数
int checkQueueNum(Queue * currentPtr)
{
    int num = 0;
      
    if (currentPtr == NULL) 
    {
        return 0;
    }
    else
    {
        while (currentPtr != NULL)
        {
            num++;
            currentPtr = currentPtr -> next;
        }
    }
    return num;
    
}

Python

from collections import deque
import random
import time

MAX_ARRIVE_INTERVAL = 4 # maximum arrival interval

customerIdRegister = deque([])   # customers at the register 
arriveTimeRegister = deque([])   # customer's arrival time at the register

def main():

    # Seed the random number generator with the current time
    random.seed(time.time())
    
    # first customer 
    customerId = 1

    # caliculate arrival time of first customer
    nowTime = random.randint(1, MAX_ARRIVE_INTERVAL)
    firstTime = nowTime

    # first customer arrives at the register
    print("時刻 %d" % (firstTime))
    print("%dさんが到着しました" % (customerId))

    # caliculate service time of first customer
    serviceTime = random.randint(1, 4)
    
    # start serving first customer
    customerIdBeingServed = 1
    print("%dさんのサービスを開始します サービス時間は%dです" % (customerIdBeingServed, serviceTime))

    # next arrival customer
    customerId = customerId + 1

     # caliculate arrival time of next customer
    nextArrivetime = nowTime + random.randint(1, MAX_ARRIVE_INTERVAL)

    # initialize the maximum number of minutes someone have to wait
    maxServiceWaitTime = -1

    # initialize the maximum number of people in the register
    maxPeopleAtRegister = -1

    # run a 720 minute simulation(starting point 0)
    while nowTime < 30: # <=720:
           
        if nowTime != firstTime:
           
           print("時刻 %d" % (nowTime))    

        # if the next customer arrives
        if nowTime >= nextArrivetime:
        
            # some customer arrives at the register
            print("%dさんが到着しました" % (customerId))
 
            # register the customer at the register 
            customerIdRegister.append(customerId)
            arriveTimeRegister.append(nowTime)

            # caliculate arrival time of next customer
            nextArrivetime = nowTime + random.randint(1, MAX_ARRIVE_INTERVAL)
 
            # Next arrival customer
            customerId = customerId + 1
        
        # if the current customer service ends
        if serviceTime <= 0:
        
            # display the service is complete
            if serviceTime == 0:
               print("%dさんのサービスが完了しました" % (customerIdBeingServed))

            # if customer is at the register
            if len(customerIdRegister) != 0:
            
                # retrive from register and start serving the customer
                customerIdBeingServed = customerIdRegister.popleft()
                arriveTime = arriveTimeRegister.popleft()

                # calculate the time spent waiting for service
                serviceWaitTime = nowTime - arriveTime

                print("%dさんはサービスを受けるまで%d分待たされました" % (customerIdBeingServed, serviceWaitTime))

                # the longest wait ever for service
                if serviceWaitTime > maxServiceWaitTime:
                
                   maxServiceWaitTime = serviceWaitTime
                    
                # caliculate service time of the customer
                serviceTime = random.randint(1, 4)

                print("%dさんのサービスを開始します サービス時間は%dです" % (customerIdBeingServed, serviceTime))

        # find out how many people are currently waiting at the register      
        peopleAtRegister = len(customerIdRegister)
 
        # if there are more people at the register than ever
        if peopleAtRegister > maxPeopleAtRegister:
        
            maxPeopleAtRegister = peopleAtRegister
        
        print(customerIdRegister)
        print("")

        # one minute passed
        nowTime = nowTime + 1
        serviceTime = serviceTime - 1

    print("")
    print("%d人到着しました" % (customerId - 1))
    print("最大%d分待たされました" % (maxServiceWaitTime))
    print("最大%d人レジで待たされました" % (maxPeopleAtRegister))

if __name__ == '__main__':
     main()

Python版: 実行結果

時刻 3
1さんが到着しました
1さんのサービスを開始します サービス時間は2です
deque([])

時刻 4
2さんが到着しました
deque([2])

時刻 5
1さんのサービスが完了しました
2さんはサービスを受けるまで1分待たされました   
2さんのサービスを開始します サービス時間は2です
deque([])

時刻 6
3さんが到着しました
deque([3])

時刻 7
2さんのサービスが完了しました
3さんはサービスを受けるまで1分待たされました
3さんのサービスを開始します サービス時間は2です
deque([])

時刻 8
deque([])

時刻 9
4さんが到着しました
3さんのサービスが完了しました
4さんはサービスを受けるまで0分待たされました
4さんのサービスを開始します サービス時間は4です
deque([])

時刻 10
5さんが到着しました
deque([5])

時刻 11
6さんが到着しました
deque([5, 6])

時刻 12
deque([5, 6])

時刻 13
7さんが到着しました
4さんのサービスが完了しました
5さんはサービスを受けるまで3分待たされました
5さんのサービスを開始します サービス時間は1です
deque([6, 7])

時刻 14
8さんが到着しました
5さんのサービスが完了しました
6さんはサービスを受けるまで3分待たされました
6さんのサービスを開始します サービス時間は3です
deque([7, 8])

時刻 15
9さんが到着しました
deque([7, 8, 9])

時刻 16
deque([7, 8, 9])

時刻 17
10さんが到着しました
6さんのサービスが完了しました
7さんはサービスを受けるまで4分待たされました
7さんのサービスを開始します サービス時間は4です
deque([8, 9, 10])

時刻 18
deque([8, 9, 10])

時刻 19
deque([8, 9, 10])

時刻 20
deque([8, 9, 10])

時刻 21
11さんが到着しました
7さんのサービスが完了しました
8さんはサービスを受けるまで7分待たされました
8さんのサービスを開始します サービス時間は1です
deque([9, 10, 11])

時刻 22
12さんが到着しました
8さんのサービスが完了しました
9さんはサービスを受けるまで7分待たされました
9さんのサービスを開始します サービス時間は3です
deque([10, 11, 12])

時刻 23
deque([10, 11, 12])

時刻 24
deque([10, 11, 12])

時刻 25
13さんが到着しました
9さんのサービスが完了しました
10さんはサービスを受けるまで8分待たされました
10さんのサービスを開始します サービス時間は3です
deque([11, 12, 13])

時刻 26
deque([11, 12, 13])

時刻 27
deque([11, 12, 13])

時刻 28
14さんが到着しました
10さんのサービスが完了しました
11さんはサービスを受けるまで7分待たされました
11さんのサービスを開始します サービス時間は1です
deque([12, 13, 14])

時刻 29
11さんのサービスが完了しました
12さんはサービスを受けるまで7分待たされました
12さんのサービスを開始します サービス時間は1です
deque([13, 14])


14人到着しました
最大8分待たされました
最大3人レジで待たされました

12.16: リスト12.7(P465)のプログラムを重複値を含む二分木もなぞれるように変更

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>

#define SIZE 7
typedef struct treeNode{
  struct treeNode *leftPtr;
  int data;
  struct treeNode *rightPtr;
}TreeNode;

void insertNode(TreeNode **, int);
void inOrder(TreeNode *);
void preOrder(TreeNode *);
void postOrder(TreeNode *);

int main()
{
    int i, item;
    TreeNode *rootPtr = NULL;
  
    srand(time(NULL));

    printf("2分木に挿入する値:\n");
     
    for (i = 1; i <= SIZE; i++)
    {
        item = rand() % 15;
        printf("%3d", item);
        insertNode(&rootPtr, item);
    }

    printf("\n\n先順探索の結果:\n");
    preOrder(rootPtr);

    printf("\n\n中順探索の結果:\n");
    inOrder(rootPtr);

    printf("\n\n後順探索の結果:\n");
    postOrder(rootPtr);

    getch();
    return 0;
}

void insertNode(TreeNode **treePtr, int value)
{
    if (*treePtr == NULL)
    {
        *treePtr = (TreeNode *)malloc(sizeof(TreeNode));

        if (*treePtr != NULL)
        {
            (*treePtr) -> data = value;
            (*treePtr) -> leftPtr = NULL;
            (*treePtr) -> rightPtr = NULL;
        } 
        else
        {
            printf("空きメモリがないため %d は挿入できません\n", value);
        }
    }
    else  if (value < (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
    else if (value > (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> rightPtr), value);
    }
    // 同じ値だったら木の左側にデータを挿入
    else
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
}

void inOrder(TreeNode *treePtr)
{
    if (treePtr != NULL)
    {
        inOrder(treePtr -> leftPtr);
        printf("%3d", treePtr -> data);
        inOrder(treePtr -> rightPtr);
    }
}

void preOrder(TreeNode *treePtr)
{
    if (treePtr != NULL)
    {
        printf("%3d", treePtr -> data);
        preOrder(treePtr -> leftPtr);
        preOrder(treePtr -> rightPtr);
    }
}

void postOrder(TreeNode *treePtr)
{
    if (treePtr != NULL)
    {
        postOrder(treePtr -> leftPtr);
        postOrder(treePtr -> rightPtr);
        printf("%3d", treePtr -> data);
    }
}

C言語版実行結果

2分木に挿入する値:
  1  9  6  0  4  0  6

先順探索の結果:
  1  0  0  9  6  4  6

中順探索の結果:
  0  0  1  4  6  6  9

後順探索の結果:
  0  0  6  4  6  9  1

先順探索
中順探索
後順探索

Python

12.17: テキストを1行入力して単語に分解、それらの単語を二分探索木に挿入、それを中順走査、先順走査、後順走査でプリント

C言語

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

#define SIZE 100

// 二分探索木のノード定義
typedef struct TreeNode {
    char *data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// ノードの作成
TreeNode* createNode(char *data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = strdup(data);
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 二分探索木に挿入
TreeNode* insert(TreeNode *root, char *data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (strcmp(data, root->data) < 0) {
        root->left = insert(root->left, data);
    } else if (strcmp(data, root->data) > 0) {
        root->right = insert(root->right, data);
    }
    return root;
}

// 中順走査
void inorderTraversal(TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%s ", root->data);
        inorderTraversal(root->right);
    }
}

// 先順走査
void preorderTraversal(TreeNode *root) {
    if (root != NULL) {
        printf("%s ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 後順走査
void postorderTraversal(TreeNode *root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%s ", root->data);
    }
}

// メモリ解放
void freeTree(TreeNode *root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root->data);
        free(root);
    }
}

int main() {
    char input[SIZE];
    char *token;
    TreeNode *root = NULL;

    printf("文字列を入力してください:\n");
    fgets(input, SIZE, stdin);

    // 改行を削除
    input[strcspn(input, "\n")] = '\0';

    // トークンに分解
    token = strtok(input, " ");
    while (token != NULL) {
        root = insert(root, token);
        token = strtok(NULL, " ");
    }

    // 中順走査
    printf("中順走査: ");
    inorderTraversal(root);
    printf("\n");

    // 先順走査
    printf("先順走査: ");
    preorderTraversal(root);
    printf("\n");

    // 後順走査
    printf("後順走査: ");
    postorderTraversal(root);
    printf("\n");

    // メモリ解放
    freeTree(root);

    return 0;
}

Python

12.18: 1次元配列だけを使い重複値を回避する方法 + 1次元配列・二分探索木による重複値回避の性能比較

回避方法
- 1次元配列の先頭から最後尾まで一つずつ値を比較
性能比較
- 共通
  - 重複値はひとつだけ存在
  - データ数$n$($>=2$)
- 2分探索木
  - 平衡型(バランスがとれている)
  - []: ガウス記号(ある値についてそれを超えない最大の整数値)
- 1次元配列
  - 重複値は配列内のどこかに等確率($\frac{1}{n}$)で存在
  - 平均比較回数(比較回数の期待値)$ = \frac{1}{n} \times 1 + \frac{1}{n} \times 2 + \frac{1}{n} \times 3 + \frac{1}{n} \times 4 ... = \frac{1 + 2 + 3 + 4 ...}{n} = \frac{n(n+1)/2}{n}$

	1次元配列	二分探索木
最小比較回数	1	1
平均比較回数	$\frac{n+1}{2}$	$[log_{2}{n}]$
最大比較回数	$n$	$[log_{2}{n}]$+1

12.19: 二分木を受け取り、それのレベル数を決定

C言語

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

typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int depth(TreeNode* node) {
    if (node == NULL) {
        return 0;
    } else {
        int left_depth = depth(node->left);
        int right_depth = depth(node->right);
        return (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;
    }
}

int main() {
    // 例
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5

    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->value = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->value = 2;
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->value = 4;
    root->left->left->left = NULL;  // 葉ノードにNULLを代入
    root->left->left->right = NULL;  // 葉ノードにNULLを代入
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->value = 5;
    root->left->right->left = NULL;  // 葉ノードにNULLを代入
    root->left->right->right = NULL;  // 葉ノードにNULLを代入
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->value = 3;
    root->right->left = NULL;  // 葉ノードにNULLを代入
    root->right->right = NULL;  // 葉ノードにNULLを代入

    printf("深さ: %d\n", depth(root));  // 出力: 3
    getch();
    
    // メモリ解放
    free(root->left->right);
    free(root->left->left);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Python

12.20: 連結リスト(要素は整数でソートされている)のデータ項目を逆の順序で再帰的に出力

C言語

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

// ノードの定義
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// ノードを作成するヘルパー関数
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// ソートされた位置にノードを挿入する関数
void insertSorted(Node** head, int data) {
    Node* newNode = createNode(data);
    
    // ヘッドがNULLの場合、またはヘッドのデータが新しいノードのデータより大きい場合
    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
    } else {
        // 適切な位置を見つける
        Node* current = *head;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// 逆順に連結リストを出力する再帰関数
void printListBackwards(Node* node) {
    if (node == NULL) return;
    
    printListBackwards(node->next);
    printf("%d ", node->data);
}

int main() {
    // ソートされた連結リストを生成するためのヘッドノード
    Node* head = NULL;
    
    // 挿入するデータの配列
    int arr[] = {3, 1, 4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // データを挿入してソートされた連結リストを生成
    for (int i = 0; i < n; i++) {
        insertSorted(&head, arr[i]);
    }
    
    // 逆順に連結リストを出力
    printListBackwards(head);
    
    getch();
    
    return 0;
}

Python

12.21: リストを再帰的に探索

C言語

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

// 連結リストのノードを定義
struct Node {
    int data;
    struct Node* next;
};

// 新しいノードを作成する関数
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 連結リストにノードを追加する関数
void appendNode(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }
    struct Node* temp = *headRef;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// 再帰的に指定された値を連結リストから探し出す関数
struct Node* searchList(struct Node* head, int target) {
    if (head == NULL) {
        return NULL; // 見つからなかった場合
    }
    if (head->data == target) {
        return head; // 見つかった場合
    }
    return searchList(head->next, target);
}

// メイン関数
int main() {
    struct Node* head = NULL;
    int n, value, target;
    
    printf("連結リストのノード数を入力してください: ");
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        printf("ノード %d の値を入力してください: ", i + 1);
        scanf("%d", &value);
        appendNode(&head, value);
    }
    
    printf("検索したい値を入力してください: ");
    scanf("%d", &target);
    
    struct Node* result = searchList(head, target);
    
    if (result != NULL) {
        printf("値 %d が見つかりました: アドレス %p\n", result->data, (void*)result);
    } else {
        printf("値 %d は見つかりませんでした。\n", target);
    }
    
    // メモリ解放
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
    
    getch();
    
    return 0;
}

Python

12.22: 二分木からデータを削除

書籍で指定されたアルゴリズムに非従順

C言語

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

typedef struct TreeNode {
    int data;
    struct TreeNode* leftPtr;
    struct TreeNode* rightPtr;
} TreeNode;

void insertNode(TreeNode **, int);
void outputTree(TreeNode*, int); 
void inorderTraversal(TreeNode *);
void preorderTraversal(TreeNode *);
void postorderTraversal(TreeNode *); 
TreeNode* deleteNode(TreeNode*, int, int *);
TreeNode* findMax(TreeNode*);

TreeNode* findMax(TreeNode* root) {
    while (root->rightPtr != NULL) {
        root = root->rightPtr;
    }
    return root;
}

TreeNode* deleteNode(TreeNode* root, int data, int* found) {
    if (root == NULL) {
        return root;
    }

    if (data < root->data) {
        root->leftPtr = deleteNode(root->leftPtr, data, found);
    } else if (data > root->data) {
        root->rightPtr = deleteNode(root->rightPtr, data, found);
    } else {
        // ノードが見つかった場合
        *found = 1;
        if (root->leftPtr == NULL) {
            TreeNode* temp = root->rightPtr;
            free(root);
            return temp;
        } else if (root->rightPtr == NULL) {
            TreeNode* temp = root->leftPtr;
            free(root);
            return temp;
        }

        // 両方の子ノードがある場合
        TreeNode* temp = findMax(root->leftPtr);
        root->data = temp->data;
        root->leftPtr = deleteNode(root->leftPtr, temp->data, found);
    }
    return root;
}

void insertNode(TreeNode** root, int data) {
    if (*root == NULL) {
        *root = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->data = data;
        (*root)->leftPtr = NULL;
        (*root)->rightPtr = NULL;
    } else if (data < (*root)->data) {
        insertNode(&(*root)->leftPtr, data);
    } else {
        insertNode(&(*root)->rightPtr, data);
    }
}

void printTree(TreeNode* root) {
    if (root != NULL) {
        printTree(root->leftPtr);
        printf("%d ", root->data);
        printTree(root->rightPtr);
    }
}

// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
    if (root == NULL)
        return;

    // 右のサブツリーをプリント
    outputTree(root->rightPtr, totalSpaces + 5);

    // 現在のノードをプリント
    printf("\n");
    for (int i = 1; i < totalSpaces; i++)
        printf(" ");
    printf("%d(%p)\n", root->data, (void *)root);

    // 左のサブツリーをプリント
    outputTree(root->leftPtr, totalSpaces + 5);
}

// 中順走査
void inorderTraversal(TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->leftPtr);
        printf("%d ", root->data);
        inorderTraversal(root->rightPtr);
    }
}

// 先順走査
void preorderTraversal(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->leftPtr);
        preorderTraversal(root->rightPtr);
    }
}

// 後順走査
void postorderTraversal(TreeNode *root) {
    if (root != NULL) {
        postorderTraversal(root->leftPtr);
        postorderTraversal(root->rightPtr);
        printf("%d ", root->data);
    }
}

int main() {
    TreeNode* root = NULL;
    int eraseData;
    int found = 0;
    int values[] = {9, 3, 7, 2, 10};
    int numValues = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < numValues; i++) {
        insertNode(&root, values[i]);
    }

    printf("ツリーの内容（削除前）: ");
    outputTree(root, 0);
    printf("\n");

    printf("削除するデータを入力して下さい\n");
    scanf("%d", &eraseData);
    root = deleteNode(root, eraseData, &found);

    if (!found) {
        printf("\n指定された値はツリー内に存在しませんでした。\n\n");
    }

    printf("ツリーの内容（削除後）: ");
    outputTree(root, 0);
    printf("\n");

    printf("\n先順走査\n");
    preorderTraversal(root);
    printf("\n中順走査\n");
    inorderTraversal(root);
    printf("\n後順走査\n");
    postorderTraversal(root);

    printf("\n");
    getch();

    return 0;
}

Python

12.23: 二分木を探索

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>

#define SIZE 5

typedef struct treeNode{
  struct treeNode *leftPtr;
  int data;
  struct treeNode *rightPtr;
}TreeNode;

void insertNode(TreeNode **, int);
TreeNode *binaryTreeSearch(TreeNode *, int);
void outputTree(TreeNode*, int); 

int main()
{
    int i, item;
    TreeNode *rootPtr = NULL;
    TreeNode *tmpPtr;
    int key;
  
    srand(time(NULL));

    printf("2分木に挿入する値:\n");
     
    for (i = 1; i <= SIZE; i++)
    {
        item = rand() % 15;
        printf("%3d", item);
        insertNode(&rootPtr, item);
    }

    outputTree(rootPtr, 0);

    printf("\nbinaryTreeSearch:\n");
    printf("探索キーを入力してください: ");
    scanf("%d", &key);

    if ((tmpPtr = binaryTreeSearch(rootPtr, key)) == NULL)
    {
         printf("データはありませんでした\n");
    }
    else
    {
         printf("データ %d アドレス%p\n", tmpPtr -> data, (void *)tmpPtr);
    }

    getch();
    return 0;
}

// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
    if (root == NULL)
        return;

    // 増加する距離
    int count = 5;

    // 右のサブツリーをプリント
    totalSpaces += count;
    outputTree(root->rightPtr, totalSpaces);

    // 現在のノードをプリント
    printf("\n");
    for (int i = count; i < totalSpaces; i++)
        printf(" ");
    printf("%d\n", root->data);

    // 左のサブツリーをプリント
    outputTree(root->leftPtr, totalSpaces);
}

void insertNode(TreeNode **treePtr, int value)
{
    if (*treePtr == NULL)
    {
        *treePtr = (TreeNode *)malloc(sizeof(TreeNode));

        if (*treePtr != NULL)
        {
            (*treePtr) -> data = value;
            (*treePtr) -> leftPtr = NULL;
            (*treePtr) -> rightPtr = NULL;
        } 
        else
        {
            printf("空きメモリがないため %d は挿入できません\n", value);
        }
    }
    else  if (value < (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
    else if (value > (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> rightPtr), value);
    }
    // 同じ値だったら木の左側にデータを挿入
    else
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
}

TreeNode *binaryTreeSearch(TreeNode *treePtr, int key)
{
    if (treePtr == NULL)
    {
        return NULL;
    }

    // データが見つかったならば
    if (treePtr -> data == key)
    {
        return treePtr;
    }
    // keyの値がデータより大きいならば
    else if (treePtr -> data < key)
    {
        return  binaryTreeSearch(treePtr -> rightPtr, key);
    }
    else 
    {
        return  binaryTreeSearch(treePtr -> leftPtr, key);
    }
}

Python

12.24: 二分木のレベル順走査

C言語

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

struct treeNode {
    int data;
    struct treeNode *leftPtr;
    struct treeNode *rightPtr;
};

typedef struct treeNode TREENODE;
typedef TREENODE* TREENODEPTR;

struct queueNode {
    TREENODEPTR treeNode;
    struct queueNode *nextPtr;
};

typedef struct queueNode QUEUENODE;
typedef QUEUENODE *QUEUENODEPTR;

void inOrder(TREENODEPTR);
void printQueue(QUEUENODEPTR);
bool isEmpty(QUEUENODEPTR);
void levelOrder(TREENODEPTR);
void dequeue(QUEUENODEPTR *, QUEUENODEPTR *);
void enqueue(QUEUENODEPTR *, QUEUENODEPTR *, TREENODEPTR);
void outputTree(TREENODEPTR, int); 

// 中順走査
void inOrder(TREENODEPTR root) {
    if (root != NULL) {
        inOrder(root->leftPtr);
        printf("%d ", root->data);
        inOrder(root->rightPtr);
    }
}

// キューにノードを追加する関数
void enqueue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr, TREENODEPTR treeNode) {
    QUEUENODEPTR newPtr;

    newPtr = (QUEUENODEPTR)malloc(sizeof(QUEUENODE));
    if (newPtr != NULL) {
        newPtr->treeNode = treeNode;
        newPtr->nextPtr = NULL;

        if (isEmpty(*headPtr)) {
            *headPtr = newPtr;
        } else {
            (*tailPtr)->nextPtr = newPtr;
        }
        *tailPtr = newPtr;
    } else {
        printf("空きメモリがないため、ノードは挿入できません。\n");
    }
}

// キューからノードを取り出す関数
void dequeue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr) {
    QUEUENODEPTR tempPtr;

    tempPtr = *headPtr;
    *headPtr = (*headPtr)->nextPtr;

    if (*headPtr == NULL) {
        *tailPtr = NULL;
    }

    free(tempPtr);
}

// キューが空かどうかを確認する関数
bool isEmpty(QUEUENODEPTR headPtr) {
    return headPtr == NULL;
}

// レベル順に二分木を走査する関数
void levelOrder(TREENODEPTR root) {
    if (root == NULL) return;

    QUEUENODEPTR queueFront = NULL;
    QUEUENODEPTR queueRear = NULL;

    // 1 ルートノードをキューに入れる
    enqueue(&queueFront, &queueRear, root);

    // 2 キューにノードが残っているあいだ
    while (!isEmpty(queueFront)) {
        // キューから次のノードを取り出す
        TREENODEPTR currentNode = queueFront->treeNode;
        dequeue(&queueFront, &queueRear);

        // そのノード値をプリントする
        printf("%d ", currentNode->data);

        // そのノードの左の子へのポインタがNULLでないなら
        if (currentNode->leftPtr != NULL) {

            // 左の子ノードをキューに入れる
            enqueue(&queueFront, &queueRear, currentNode->leftPtr);
        }

        // そのノードの右の子へのポインタがNULLでないなら
        if (currentNode->rightPtr != NULL) {

            // 右の子ノードをキューに入れる
            enqueue(&queueFront, &queueRear, currentNode->rightPtr);
        }
    }
}

// 新しいノードを作成する関数
TREENODEPTR createNode(int data) {
    TREENODEPTR newNode = (TREENODEPTR)malloc(sizeof(TREENODE));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->leftPtr = NULL;
        newNode->rightPtr = NULL;
    }
    return newNode;
}

// 二分木を目に見える形でプリントする関数
void outputTree(TREENODEPTR root, int totalSpaces) {
    if (root == NULL)
        return;

    // 右のサブツリーをプリント
    outputTree(root->rightPtr, totalSpaces + 5);

    // 現在のノードをプリント
    printf("\n");
    for (int i = 1; i < totalSpaces; i++)
        printf(" ");
    printf("%d(%p)\n", root->data, (void *)root);

    // 左のサブツリーをプリント
    outputTree(root->leftPtr, totalSpaces + 5);
}

int main() {
    // 二分木を作成
    TREENODEPTR root = createNode(1);
    root->leftPtr = createNode(2);
    root->rightPtr = createNode(3);
    root->leftPtr->leftPtr = createNode(4);
    root->leftPtr->rightPtr = createNode(5);

    outputTree(root, 0);
    printf("レベル順走査\n");
    levelOrder(root);
    printf("\n中順走査\n");
    inOrder(root);

    getch();

    return 0;
}

Python

12.25: 二分木のプリント

C言語

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>

#define SIZE 5

typedef struct treeNode{
  struct treeNode *leftPtr;
  int data;
  struct treeNode *rightPtr;
}TreeNode;

void insertNode(TreeNode **, int);
void outputTree(TreeNode*, int); 

int main()
{
    int i, item;
    TreeNode *rootPtr = NULL;
    TreeNode *tmpPtr;
    int key;
  
    srand(time(NULL));

    printf("2分木に挿入する値:\n");
     
    for (i = 1; i <= SIZE; i++)
    {
        item = rand() % 15;
        printf("%3d", item);
        insertNode(&rootPtr, item);
    }
    printf("\n");

    outputTree(rootPtr, 0);

    getch();
    return 0;
}

// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
    if (root == NULL)
        return;

    // 右のサブツリーをプリント
    outputTree(root->rightPtr, totalSpaces + 5);

    // 現在のノードをプリント
    printf("\n");
    for (int i = 1; i < totalSpaces; i++)
        printf(" ");
    printf("%d\n", root->data);

    // 左のサブツリーをプリント
    outputTree(root->leftPtr, totalSpaces + 5);
}

void insertNode(TreeNode **treePtr, int value)
{
    if (*treePtr == NULL)
    {
        *treePtr = (TreeNode *)malloc(sizeof(TreeNode));

        if (*treePtr != NULL)
        {
            (*treePtr) -> data = value;
            (*treePtr) -> leftPtr = NULL;
            (*treePtr) -> rightPtr = NULL;
        } 
        else
        {
            printf("空きメモリがないため %d は挿入できません\n", value);
        }
    }
    else  if (value < (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
    else if (value > (*treePtr) -> data)
    {
        insertNode(&((*treePtr) -> rightPtr), value);
    }
    // 同じ値だったら木の左側にデータを挿入
    else
    {
        insertNode(&((*treePtr) -> leftPtr), value);
    }
}

Python

12.26: 簡易言語

a

10 rem 整数を三個入力して,それらの平均を求める
15 input i
20 input j
25 input k
30 let   l = (i + j + k) / 3
40 print l
50 end

b

5  rem 番兵値は-9999
10 input j
15 if j == -9999 goto 90
20 let s = s + j
25 goto 10
90 print s
99 end

c

10 rem 平均値を求める
40 input d 
50 let c = d + c
60 let a = a + 1
80 if a < 7 goto 40
90 let c = c / 7
100 print c
110 end

d

10 input x
20 input d
22 rem 今入力したデータが前のデータより小さいなら
30 if d <= e goto 50
40 rem 最大値を更新する
44 let e = d
50 let c = c + 1
60 if c < x goto 20
80 print e
90 end

e

10 input d
20 if d  > e goto 50
30 let e = d
50 let c = c + 1
60 if c < 10 goto 10
90 print e
99 end

f

10 let e = 2
20 let d = d + e
30 let e = e + 2
40 if e < 32 goto 20
50 print d
60 end

g

2  rem 10 15 は初期化
10 let e = 1
15 let d = 1
20 let d = e * d
30 let e = e + 2
40 if e < 11 goto 20
50 print d
60 end

12.27: コンパイラの制作

a: 練習問題7.19で書いたSimpletronシミュレーターをユーザが指定したファイルからSMLコードを入力するように改造

C言語

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

#define DEBUG(name) { printf("\nDEBUG (" #name ") %d\n\n", name); }

// 入出力命令
#define READ  10
#define WRITE 11

// ロード/ストア命令
#define LOAD  20
#define STORE 21

// 算術演算命令
#define ADD         30
#define SUBTRACT    31
#define DIVIDE      32
#define MULTIPLY    33

// 分岐命令
#define BRANCH      40
#define BRANCHENG   41
#define BRANCHZERO  42
#define HALT        43

#define MEMORY_SIZE 100

// レジスタの内容とメモリの内容をダンプする関数
void printDumpToBoth(FILE *, int, int, int, int, int, int []);

int main() { 
    static int memory[MEMORY_SIZE];  // メモリモデル
    int accumulator = 0;             // レジスタ
    int instructionCounter = 0;      // 次に実行する命令が格納されたメモリ番地を格納
    int instructionRegister;         // 次に実行する命令
    int operationCode;               // 現在実行中の命令コードを格納
    int operand = 0;                 // 現在の命令が作用するメモリ番地
    int endFlag = 0;
    char line[256];

    FILE *inputFile = fopen("7.18a.c", "r");
    FILE *outputFile = fopen("12.27aOutput.txt", "w");

    if (inputFile == NULL || outputFile == NULL) {
        fprintf(stderr, "ファイルを開くことができません。\n");
        return 1;
    }

    while (fgets(line, sizeof(line), inputFile)) {
        sscanf(line, "%*d %d", &memory[operand]);
        if (memory[operand] == -9999) {
            endFlag = 1;
            memory[operand] = 0;
        } else if (-9999 <= memory[operand] && memory[operand] <= 9999) {
            operand++;
        } else {
            printf("\n不正な値です -9999 - 9999 までの値を入力してください\n\n");
        }
    }
    fclose(inputFile);

    if (operand <= 0) {
        fprintf(outputFile, "命令はロードされていません\n");
        printf("命令はロードされていません\n");
        endFlag = 1;
    } else {
        fprintf(outputFile, "*** プログラムのロードが完了しました ***\n");
        printf("*** プログラムのロードが完了しました ***\n");
        fprintf(outputFile, "*** プログラムの実行を開始します     ***\n");
        printf("*** プログラムの実行を開始します     ***\n");
        endFlag = 0;
    }

    while (endFlag == 0) {
        // 命令を取り出す
        instructionRegister = memory[instructionCounter];
        DEBUG(instructionRegister)

        // 次の命令にカウンタを更新
        instructionCounter++;

        // 命令レジスタから命令コードを取り出す
        operationCode = instructionRegister / 100;

        // 命令レジスタからオペランドを取り出す
        operand = instructionRegister % 100;

        // 命令判別
        switch (operationCode) {
            // 入力命令
            case READ:
                fprintf(outputFile, "データを入力してください\n");
                printf("データを入力してください\n");
                scanf("%d", &memory[operand]);
                fprintf(outputFile, "%d\n\n", memory[operand]);
                break;

            // 出力命令
            case WRITE:
                fprintf(outputFile, "%+5d\n", memory[operand]);
                printf("%+5d\n", memory[operand]);
                break;

            // ロード命令
            case LOAD:
                accumulator = memory[operand];
                break;

            // ストア命令
            case STORE:
                memory[operand] = accumulator;
                break;

            // 加算命令
            case ADD:
                accumulator += memory[operand];
                if (accumulator < -9999 || accumulator > 9999) {
                    fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
                    printf("*** 演算結果のオーバーフロー ***\n");
                    fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
                    printf("*** Simpletronは異常終了しました ***\n\n");
                    printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                    return -1;
                }
                break;

            // 引き算命令
            case SUBTRACT:
                accumulator -= memory[operand];
                if (accumulator < -9999 || accumulator > 9999) {
                    fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
                    printf("*** 演算結果のオーバーフロー ***\n");
                    fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
                    printf("*** Simpletronは異常終了しました ***\n\n");
                    printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                    return -1;
                }
                break;

            // 割り算命令
            case DIVIDE:
                if (memory[operand] == 0) {
                    fprintf(stderr, "*** ゼロで割ろうとした ***\n");
                    printf("*** ゼロで割ろうとした ***\n");
                    fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
                    printf("*** Simpletronは異常終了しました ***\n\n");
                    printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                    return -1;
                }
                accumulator /= memory[operand];
                break;

            // 掛け算命令
            case MULTIPLY:
                accumulator *= memory[operand];
                if (accumulator < -9999 || accumulator > 9999) {
                    fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
                    printf("*** 演算結果のオーバーフロー ***\n");
                    fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
                    printf("*** Simpletronは異常終了しました ***\n\n");
                    printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                    return -1;
                }
                break;

            // 無条件分岐命令
            case BRANCH:
                instructionCounter = operand;
                break;

            // アキュムレータが負のとき分岐する命令
            case BRANCHENG:
                if (accumulator < 0) {
                    instructionCounter = operand;
                }
                break;

            // アキュムレータが0のとき分岐する命令
            case BRANCHZERO:
                if (accumulator == 0) {
                    instructionCounter = operand;
                }
                break;

            // 停止命令
            case HALT:
                endFlag = 1;
                fprintf(outputFile, "*** Simpletronは終了しました ***\n\n");
                printf("*** Simpletronは終了しました ***\n\n");
                printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                break;

            // 不正な命令
            default:
                fprintf(stderr, "*** 不正な命令コード ***\n");
                printf("*** 不正な命令コード ***\n");
                fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
                printf("*** Simpletronは異常終了しました ***\n\n");
                printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
                return -1;
        }
    }
    fclose(outputFile);

    return 0;
}

// レジスタの内容とメモリの内容をダンプする関数
void printDumpToBoth(FILE *outputFile, int accu, int instructionC, int instructionR, int operation, int operand, int m[]) {
    int i, j;

    fprintf(outputFile, "レジスタ:\n");
    printf("レジスタ:\n");
    fprintf(outputFile, "アキュムレータ %+05d\n", accu);
    printf("アキュムレータ %+05d\n", accu);
    fprintf(outputFile, "命令カウンタ %02d\n", instructionC);
    printf("命令カウンタ %02d\n", instructionC);
    fprintf(outputFile, "命令レジスタ %+05d\n", instructionR);
    printf("命令レジスタ %+05d\n", instructionR);
    fprintf(outputFile, "命令コード %02d\n", operation);
    printf("命令コード %02d\n", operation);
    fprintf(outputFile, "オペランド %02d\n\n", operand);
    printf("オペランド %02d\n\n", operand);
    fprintf(outputFile, "メモリ:\n");
    printf("メモリ:\n");
    fprintf(outputFile, "   ");
    printf("   ");

    for (i = 0; i < 10; i++) {
        fprintf(outputFile, "%5d ", i);
        printf("%5d ", i);
    }
    fprintf(outputFile, "\n");
    printf("\n");

    for (i = 0; i < 100; i += 10) {
        fprintf(outputFile, "%2d ", i);
        printf("%2d ", i);
        for (j = i; j < i + 10; j++) {
            fprintf(outputFile, "%+05d ", m[j]);
            printf("%+05d ", m[j]);
        }
        fprintf(outputFile, "\n");
        printf("\n");
    }
}

Python

b: 練習問題12.12の中置式-後置式変換アルゴリズムを複数桁の整数オペランドと1文字の変数名オペランドを処理できるように改良

C言語

Python

参考

12.15 Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）
- https://qiita.com/saba/items/107c4237206e31acdbef
12.15 いろんな言語で乱数取得
- https://qiita.com/gitcho/items/20e47e06c0f1a8e46a06
12.18【アルゴリズム】二分探索法の平均探索回数と近似値
- https://qiita.com/YouKnow/items/6e1c49421be039c121e8
12.22 二分探索木におけるノードの削除
- https://qiita.com/maebaru/items/a47c2ef675a76e8816ab
【ソースコード・ターミナル】VSCodeの文字化け解消方法まとめ
- https://kumipuro.tech/vscode_garbled_text/

12.:

C言語

Python