書籍ダイテル C言語プログラミング練習問題解答 12章

Last updated at 2025-03-09Posted at 2024-11-28

書籍

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: 簡易言語

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

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

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

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

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

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

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

書籍 ダイテル C言語プログラミング 練習問題 解答 12章

書籍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12.23: 二分木を探索

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

12.25: 二分木のプリント

12.26: 簡易言語

12.27: コンパイラの制作

参考

12.:

書籍ダイテル C言語プログラミング練習問題解答 12章