Technologieaustausch

[Datenstruktur] Häufig verwendete Datenstrukturoperationen in schriftlichen Interviews

2024-07-12

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

Häufig verwendete Datenstrukturoperationen in schriftlichen Interviews

Sortieren und suchen

  • Bitte schreiben Sie ein C-Programm, um die Blasensortierung zu implementieren.
#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
  • Bitte schreiben Sie ein C-Programm, um die Auswahlsortierung zu implementieren.
#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
  • Bitte schreiben Sie ein C-Programm, um die Einfügungssortierung zu implementieren.
#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
  • Bitte schreiben Sie ein C-Programm, um eine schnelle Sortierung zu implementieren.
#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
  • Bitte schreiben Sie ein C-Programm, um die binäre Suche zu implementieren.
#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

Kettenstapel-Warteschlangenbaum

  • Bitte schreiben Sie ein C-Programm, um die Grundoperationen einer verknüpften Liste zu implementieren.
#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
  • Bitte schreiben Sie ein C-Programm, um die Grundoperationen des Stapels zu implementieren.
#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

Das obige Programm zeigt, wie eine verknüpfte Liste zum Implementieren der Stapeldatenstruktur verwendet wird, einschließlich Push- und Pop-Operationen. Der Stapel ist ein Last-In-First-Out (Last-In-First-Out)LIFO ) Datenstruktur, die häufig in Programmen verwendet wird, um temporäre Speicheranforderungen zu lösen, z. B. Funktionsaufrufe, Ausdrucksauswertung, Klammerabgleich usw.In diesem Beispiel definieren wir aStackNodeDie Struktur stellt die Knoten des Stapels dar. Jeder Knoten enthält einenintGeben Sie Daten und einen Zeiger auf den nächsten Knoten ein.pushDie Funktion wird verwendet, um dem Stapel ein neues Element hinzuzufügen, undpop Funktion zum Entfernen des obersten Elements vom Stapel. Wenn der Stapel leer ist,pop Die Funktion gibt -1 zurück.existierenmainFunktionen: Wir zeigen, wie Sie diese Funktionen verwenden, um den Stapel zu verschieben und zu öffnen.

  • Bitte schreiben Sie ein C-Programm, um die Grundoperationen der Warteschlange zu implementieren.
#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

Das obige Programm zeigt, wie eine verknüpfte Liste zum Implementieren der Warteschlangendatenstruktur verwendet wird, einschließlich Enqueue- und Dequeue-Vorgängen. Die Warteschlange ist ein First-In-First-Out (FIFO ) Datenstruktur, die häufig in Programmen verwendet wird, um Probleme zu lösen, die eine ordnungsgemäße Verarbeitung erfordern, z. B. Druckaufgaben, Aufgabenplanung usw.In diesem Beispiel definieren wir aQueueNodeStruktur zur Darstellung der Knoten der Warteschlange. Jeder Knoten enthält eineintGeben Sie Daten und einen Zeiger auf den nächsten Knoten ein.enqueueDie Funktion wird verwendet, um der Warteschlange ein neues Element hinzuzufügen, unddequeue Funktion zum Entfernen des vordersten Elements aus der Warteschlange. Wenn die Warteschlange leer ist,dequeue Die Funktion gibt -1 zurück.existierenmainFunktionen: Wir zeigen, wie diese Funktionen zum Durchführen von Enqueue- und Dequeue-Vorgängen verwendet werden.

  • Bitte schreiben Sie ein C-Programm, um die Grundoperationen eines Binärbaums zu implementieren.
#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

Das obige Programm zeigt, wie eine verknüpfte Liste verwendet wird, um die Datenstruktur eines Binärbaums zu implementieren, einschließlich Einfügungs- und Durchlaufoperationen (in der Reihenfolge). Ein Binärbaum ist eine Baumdatenstruktur, in der jeder Knoten höchstens zwei untergeordnete Knoten hat: einen linken untergeordneten Knoten und einen rechten untergeordneten Knoten.In diesem Beispiel definieren wir aTreeNodeStruktur zur Darstellung der Knoten des Binärbaums. Jeder Knoten enthält eineintGeben Sie Daten ein, einen Zeiger auf den linken untergeordneten Knoten und einen Zeiger auf den rechten untergeordneten Knoten.insertDie Funktion wird verwendet, um dem Binärbaum ein neues Element hinzuzufügeninorder Die Funktion wird verwendet, um alle Elemente in einem Binärbaum in einer Inorder-Traversierung zu drucken.existierenmainFunktionen zeigen wir, wie Sie diese Funktionen verwenden, um Knoten einzufügen und die Ergebnisse einer In-Order-Traversierung eines Binärbaums auszugeben.