データ構造とアルゴリズムの実装

二分木の走査処理

ツリー走査とは、定義された順序に従って木構造の全ノードを漏れなく一度ずつ訪問する処理です。実装手法には主に再帰呼び出しとループ処理があり、再帰を用いる場合は訪問順序によって先序、中序、後序の 3 種類に分類されます。

// ノードデータの表示処理
void displayNode(struct TreeNode* node) {
    if (node->value != '#') {
        printf("%c ", node->value);
    }
}

// 先序走査（根 - 左 - 右）
void traversePreorder(struct TreeNode* node) {
    if (node != NULL) {
        displayNode(node);
        traversePreorder(node->left);
        traversePreorder(node->right);
    }
}

// 中序走査（左 - 根 - 右）
void traverseInorder(struct TreeNode* node) {
    if (node != NULL) {
        traverseInorder(node->left);
        displayNode(node);
        traverseInorder(node->right);
    }
}

// 後序走査（左 - 右 - 根）
void traversePostorder(struct TreeNode* node) {
    if (node != NULL) {
        traversePostorder(node->left);
        traversePostorder(node->right);
        displayNode(node);
    }
}

IP アドレスの正当性検証

IPv4 アドレスは、ドット区切りで接続された 4 つの数値グループで構成され、各数値は 0 から 255 の範囲である必要があります。正規表現を用いて形式を検証する Java の実装例を以下に示します。

public class NetworkUtil {
    public static void main(String[] args) {
        String targetIp = "192.168.0.1";
        String pattern = "((?:(?:25[0-5]|2[0-4]\\d|((1\\d{2})|([1-9]?\\d)))\\.){3}(?:25[0-5]|2[0-4]\\d|((1\\d{2})|([1-9]?\\d))))";
        
        if (targetIp.matches(pattern)) {
            System.out.println("有効なアドレス形式です");
        } else {
            System.out.println("無効なアドレス形式です");
        }
    }
}

C 言語による文字列結合

動的メモリ確保を用いて 2 つの文字列を結合する関数です。メモリリークを防ぐため、返されたポインタは呼び出し元で解放する必要があります。

char* mergeStrings(char *strA, char *strB) {
    // 必要なメモリサイズを計算して確保
    char *buffer = (char *) malloc(strlen(strA) + strlen(strB) + 1);
    if (buffer == NULL) exit(1);
    
    char *head = buffer; // 先頭アドレスを保持
    
    // 1 文字目のコピー
    while (*strA != '\0') {
        *buffer++ = *strA++;
    }
    // 2 文字目のコピー（null ターミネータを含む）
    while ((*buffer++ = *strB++) != '\0') {
        ;
    }
    return head;
}

単方向リンクリストの反転

リンクリストのポインタ方向を逆転させる処理です。3 つのポインタ変数を用いて順次繋ぎ変える手法が一般的です。

LinkedList reverseList(LinkedList head) {
    LinkedList newHead = NULL;
    LinkedList current = head;
    LinkedList nextNode = NULL;
    
    if (head == NULL) {
        return NULL;
    }
    
    while (current != NULL) {
        nextNode = current->next;      // 次ノードを退避
        current->next = newHead;       // 逆向きにポインタ設定
        newHead = current;             // 新ヘッダを更新
        current = nextNode;            // 次へ移動
    }
    
    return newHead;
}

テスト設計とシナリオ

ソーシャル機能「いいね」のテスト観点

• いいね状態の付与および解除が正常に動作するか
• 権限設定により、点赞者が特定のグループに属しているか確認
• 状態変更後の画面表示が即時に反映されるか
• 共通の友人に対して点赞状態が可視化されるか
• 異なる OS や端末機種における UI 表示の整合性
• ネットワーク帯域幅の変動が処理に与える影響
• 表示レイアウト（一行あたりの数）が仕様通りか
• 時系列ソートおよびユーザーアイコンの対応関係
• 通知リストにおけるユーザー名や備考表示の正確性
• 点赞後のコメント投稿など拡張機能との連携
• 未ログイン状態での情報閲覧制限の確認

携帯電話アプリの投稿機能テスト

• 各機能要件が仕様通りに実装されているか
• 投稿完了までのエンドツーエンドフローの検証
• 通話や SMS 受信などによるアプリ中断・復帰テスト
• 端末メモリ不足環境下での動作確認
• 編集中の他アプリ切り替えによる状態保持テスト
• 連続投稿による重複データ発生防止の検証

データベーススキーマ変更の検証

varchar 型の桁数拡張（例：512 から 1024 へ）を行う場合、データベース製品による文字コード扱いの違いに注意が必要です。MySQL では文字種に関わらず桁数扱いですが、SQL Server などでは漢字が複数バイトを占有する場合があります。そのため、英数字および多バイト文字を含む様々なパターンで容量テストを実施します。

HTTPS 移行時のテスト項目

• HTTP から HTTPS への自動リダイレクト機能
• 証明書的有效期限および発行元の検証
• 混合コンテンツ（HTTP リソース）の検出とブロック
• セキュリティヘッダー（HSTS など）の設定確認
• 暗号化通信によるパフォーマンスへの影響測定

システムテストと非機能要件

マルチスレッドログ出力の順序保証

並列処理環境において、ログの発行順序が意図した通りになるかを検証します。複数のスレッドを生成し、連続した番号が出力されるか確認します。

for (int index = 0; index <= 100; index++) {
    Thread worker = new Thread(new LogTask("TASK_" + index));
    worker.start();
}

IM システムの総合テスト

• ユーザー認証：ログインおよび登録フロー
• 連絡先管理：友人リストの追加、削除、編集機能
• 通信機能：メッセージの送受信および到達確認
• セキュリティ：ローカルパスワードの暗号化保存および通信経路の暗号化