Technology Sharing

[Data Structure] Commonly used data structure operations in written tests and interviews

2024-07-12

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

Commonly used data structure operations in written tests and interviews

Sorting and searching

  • Please write a C program to implement bubble sort.
#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
  • Please write a C program to implement selection sort.
#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
  • Please write a C program to implement insertion sort.
#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
  • Please write a C program to implement quick sort.
#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
  • Please write a C program to implement binary search.
#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

Chain stack queue tree

  • Please write a C program to implement the basic operations of linked lists.
#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
  • Please write a C program to implement basic stack operations.
#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

The above program demonstrates how to use linked lists to implement the stack data structure, including push and pop operations. A stack is a last-in-first-out (LIFO)LIFO) data structure, which is often used in programs to solve temporary storage needs, such as function calls, expression evaluation, bracket matching, etc. In this example, we define aStackNodeThe structure represents the nodes of the stack, each node contains aintThe data of the type and a pointer to the next node.pushThe function is used to add a new element to the stack, andpopThe function is used to remove the top element from the stack. If the stack is empty,popThe function will return -1.mainfunction, we demonstrated how to use these functions to push and pop the stack.

  • Please write a C program to implement basic operations of queues.
#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

The above program demonstrates how to use linked lists to implement the queue data structure, including enqueue and dequeue operations. A queue is a first-in-first-out (FIFO)FIFO) data structure, which is often used in programs to solve problems that require orderly processing, such as printing tasks, task scheduling, etc. In this example, we define aQueueNodeThe structure represents the nodes of the queue, each node contains aintThe data of the type and a pointer to the next node.enqueueThe function is used to add a new element to the queue, anddequeueThe function is used to remove the front element from the queue. If the queue is empty,dequeueThe function will return -1.mainIn the function, we demonstrated how to use these functions to perform enqueue and dequeue operations.

  • Please write a C program to implement the basic operations of binary trees.
#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

The above program demonstrates how to use linked lists to implement a binary tree data structure, including insert and inorder operations. A binary tree is a tree data structure where each node has at most two children: a left child and a right child. In this example, we define aTreeNodeStructure to represent the nodes of a binary tree, each node contains aintData of type , a pointer to the left child, and a pointer to the right child.insertThe function is used to add a new element to a binary tree, andinorderThe function is used to print all elements in a binary tree in an in-order traversal.mainIn the function, we demonstrated how to use these functions to insert nodes and print the in-order traversal results of a binary tree.

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail