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

書籍

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人レジで待たされました

参考

• C言語プログラミング ハーベイ M.ダイテル (著), ポール J.ダイテル (著), 小嶋 隆一 (翻訳)
  • https://www.amazon.co.jp/dp/4894710293?ref=ppx_yo2ov_dt_b_fed_asin_title
• 12.15 Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）
  • https://qiita.com/saba/items/107c4237206e31acdbef
• 12.15 いろんな言語で乱数取得
  • https://qiita.com/gitcho/items/20e47e06c0f1a8e46a06

コマンドメモ

• cd C:\Users\YUTA NAKAMURA\Desktop\色々\書籍\参考書\プログラミング言語\C言語\ダイテルC
• gcc -o .exe .c
• gcc -o .exe .c -fexec-charset=CP932
• .exe
  .

C言語

Python