技術共有

【データ構造】 筆記面接でよく使われるデータ構造操作

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

書面によるインタビューで一般的に使用されるデータ構造操作

並べ替えて検索する

  • バブルソートを実装するCプログラムを作成してください。
#include <stdio.h>
// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 選択ソートを実装する C プログラムを作成してください。
#include <stdio.h>
// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    // 外循环：遍历数组中的所有元素
    for (i = 0; i < n - 1; i++) {
        // 将当前位置设为最小值的位置
        min_idx = i;
        // 内循环：从i+1到n-1中找到最小元素的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将找到的最小值交换到它应该在的位置
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 挿入ソートを実装するCプログラムを作成してください。
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    // 外循环：从第二个元素开始遍历数组
    for (i = 1; i < n; i++) {
        key = arr[i]; // 当前要插入的元素
        j = i - 1; // 已经排序的最后一个元素的索引
        // 将arr[i]与已排序的数组进行比较，找到插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 向后移动元素
            j = j - 1; // 向前移动指针
        }
        arr[j + 1] = key; // 插入当前元素
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • クイックソートを実装するにはCプログラムを作成してください。
#include <stdio.h>
// 快速排序的分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 较小元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加较小元素的索引
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 找到分区点
        int pi = partition(arr, low, high);
        // 分别对分区点左右的子数组进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 二分探索を実装するCプログラムを作成してください。
#include <stdio.h>
// 二分查找函数
int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2; // 计算中间位置
        // 检查x是否在中间位置
        if (arr[m] == x) {
            return m; // 找到了x，返回它的索引
        }
        // 如果arr[m] < x，则x只能在右半部分
        if (arr[m] < x) {
            l = m + 1;
        } else { // 否则x只能在左半部分
            r = m - 1;
        }
    }
    // 如果没有找到x，返回-1
    return -1;
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1) {
        printf("Element is not present in arrayn");
    } else {
        printf("Element is present at index %dn", result);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

チェーンスタックキューツリー

  • リンクリストの基本操作を実装するCプログラムを作成してください。
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
struct Node {
    int data; // 节点存储的数据
    struct Node *next; // 指向下一个节点的指针
};
// 创建一个新的链表节点
struct Node* newNode(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
// 在链表的末尾添加一个新节点
void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = newNode(new_data);
    struct Node *last = *head_ref; // 用于找到链表的最后一个节点
    // 如果链表为空，新节点就是头节点
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    // 否则，遍历链表找到最后一个节点
    while (last->next != NULL) {
        last = last->next;
    }
    // 将新节点添加到链表的末尾
    last->next = new_node;
}
// 打印链表节点
void printList(struct Node *node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
int main() {
    struct Node* head = NULL; // 初始化链表为空
    // 向链表添加数据
    append(&head, 1);
    append(&head, 3);
    append(&head, 1);
    append(&head, 4);
    append(&head, 1);
    append(&head, 5);
    // 打印链表
    printf("Created linked list: ");
    printList(head);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • スタックの基本操作を実装する C プログラムを作成してください。
#include <stdio.h>
#include <stdlib.h>
// 定义栈节点结构
struct StackNode {
    int data; // 节点存储的数据
    struct StackNode *next; // 指向下一个节点的指针
};
// 判断栈是否为空
int isEmpty(struct StackNode *root) {
    return !root;
}
// 创建一个新的栈节点
struct StackNode* newNode(int data) {
    struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}
// 压栈操作
void push(struct StackNode** root, int data) {
    struct StackNode* stackNode = newNode(data);
    stackNode->next = *root;
    *root = stackNode;
    printf("%d pushed to stackn", data);
}
// 弹栈操作
int pop(struct StackNode** root) {
    if (isEmpty(*root)) {
        return -1;
    }
    struct StackNode* temp = *root;
    *root = temp->next;
    int popped = temp->data;
    free(temp);
    return popped;
}
int main() {
    struct StackNode* root = NULL;
    // 压栈操作
    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    // 弹栈操作
    printf("%d popped from stackn", pop(&root));
    printf("%d popped from stackn", pop(&root));
    printf("%d popped from stackn", pop(&root));
    // 再次尝试弹栈，此时栈为空
    printf("%d popped from stackn", pop(&root));
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

上記のプログラムは、リンク リストを使用して、プッシュおよびポップ操作を含むスタック データ構造を実装する方法を示しています。スタックは後入れ先出し (後入れ先出し) です。LIFO ) データ構造。関数呼び出し、式の評価、括弧の一致など、一時記憶域の要件を解決するためにプログラムでよく使用されます。この例では、StackNode構造体はスタックのノードを表し、各ノードにはintデータ型と次のノードへのポインタ。push関数はスタックに新しい要素を追加するために使用され、popスタックから最上位の要素を削除するために使用される関数。スタックが空の場合、popこの関数は -1 を返します。存在するmain関数。これらの関数を使用してスタックをプッシュおよびポップする方法を示します。

  • キューの基本的な動作を実装するには C プログラムを作成してください。
#include <stdio.h>
#include <stdlib.h>
// 定义队列节点结构
struct QueueNode {
    int data; // 节点存储的数据
    struct QueueNode *next; // 指向下一个节点的指针
};
// 创建一个新的队列节点
struct QueueNode* newNode(int data) {
    struct QueueNode* queueNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    queueNode->data = data;
    queueNode->next = NULL;
    return queueNode;
}
// 队列的入队操作
void enqueue(struct QueueNode** front_ref, struct QueueNode** rear_ref, int data) {
    struct QueueNode* new_node = newNode(data);
    
    // 如果队列为空，新节点即为头节点
    if (*rear_ref == NULL) {
        *front_ref = new_node;
        *rear_ref = new_node;
        return;
    }
    
    // 否则，将新节点添加到队列末尾
    (*rear_ref)->next = new_node;
    *rear_ref = new_node;
}
// 队列的出队操作
int dequeue(struct QueueNode** front_ref) {
    if (*front_ref == NULL) {
        return -1; // 队列为空
    }
    
    struct QueueNode* temp = *front_ref;
    *front_ref = (*front_ref)->next;
    int dequeued = temp->data;
    free(temp);
    
    return dequeued;
}
int main() {
    struct QueueNode* front = NULL;
    struct QueueNode* rear = NULL;
    // 入队操作
    enqueue(&front, &rear, 10);
    enqueue(&front, &rear, 20);
    enqueue(&front, &rear, 30);
    // 出队操作
    printf("%d dequeued from queuen", dequeue(&front));
    printf("%d dequeued from queuen", dequeue(&front));
    printf("%d dequeued from queuen", dequeue(&front));
    // 再次尝试出队，此时队列为空
    printf("%d dequeued from queuen", dequeue(&front));
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

上記のプログラムは、リンク リストを使用して、エンキューおよびデキュー操作を含むキュー データ構造を実装する方法を示しています。キューは先入れ先出し (FIFO ) データ構造。印刷タスクやタスクのスケジュール設定など、順序立てて処理する必要がある問題を解決するプログラムでよく使用されます。この例では、QueueNodeキューのノードを表す構造。各ノードにはintデータ型と次のノードへのポインタ。enqueue関数はキューに新しい要素を追加するために使用されます。dequeueキューから最前面の要素を削除するために使用される関数。キューが空の場合、dequeueこの関数は -1 を返します。存在するmain関数。これらの関数を使用してエンキューおよびデキュー操作を実行する方法を示します。

  • バイナリ ツリーの基本操作を実装する C プログラムを作成してください。
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
struct TreeNode {
    int data; // 节点存储的数据
    struct TreeNode *left; // 指向左子节点的指针
    struct TreeNode *right; // 指向右子节点的指针
};
// 创建一个新的二叉树节点
struct TreeNode* newNode(int data) {
    struct TreeNode* treeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    treeNode->data = data;
    treeNode->left = NULL;
    treeNode->right = NULL;
    return treeNode;
}
// 插入节点到二叉树
void insert(struct TreeNode** root, int data) {
    if (*root == NULL) {
        *root = newNode(data);
        return;
    }
    if (data < (*root)->data) {
        insert(&(*root)->left, data);
    } else if (data > (*root)->data) {
        insert(&(*root)->right, data);
    }
}
// 打印二叉树节点
void inorder(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    printf("%d ", node->data);
    inorder(node->right);
}
int main() {
    struct TreeNode* root = NULL;
    // 插入节点到二叉树
    insert(&root, 50);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 40);
    insert(&root, 70);
    insert(&root, 60);
    insert(&root, 80);
    // 打印二叉树的中序遍历结果
    printf("Inorder traversal of the given tree: n");
    inorder(root);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

上記のプログラムは、リンク リストを使用して、挿入およびトラバーサル (インオーダー) 操作を含むバイナリ ツリーのデータ構造を実装する方法を示しています。バイナリ ツリーは、各ノードが最大 2 つの子ノード (左の子ノードと右の子ノード) を持つツリー データ構造です。この例では、TreeNodeバイナリ ツリーのノードを表す構造。各ノードにはintデータ、左の子ノードへのポインタ、および右の子ノードへのポインタを入力します。insertこの関数はバイナリ ツリーに新しい要素を追加するために使用されます。inorder関数は、インオーダートラバーサルでバイナリツリー内のすべての要素を出力するために使用されます。存在するmain関数では、これらの関数を使用してノードを挿入し、バイナリ ツリーを順番に走査した結果を出力する方法を示します。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、Java、Linux、JavaScript、PHP、CSS などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便