Home BIT-study

# 数据结构实验

# 实验要求

# 采用单向环表实现约瑟夫环

  • 从键盘输入整数 m，通过 create 函数生成一个具有 m 个结点的单向环表。环表中的结点编号依次为 1，2，……，m
  • 从键盘输入整数 s（1<=s<=m）和 n，从环表的第 s 个结点开始计数为 1，当计数到第 n 个结点时，输出该第 n 结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到 n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止
  • 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。

# 简单计算器

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求

  • 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志

  • 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整

  • 例如，输入：4+2*5= 输出：14

    输入：(4+2)*(2-10)= 输出：-48

# 遍历二叉树

  • 请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出中序和后序遍历序列
  • 按层次遍历二叉树

# 排序算法

输入 10 个数，编程实现插入排序、快速排序、选择排序三类算法

# 开始实验

# 实验一：单向环表实现约瑟夫环

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
cpp复制代码#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* next;
} NODE;

NODE* create(int m) {
    NODE *head = NULL;
    NODE *p = NULL;
    NODE *q = NULL;

    head = (NODE*)malloc(sizeof(NODE));
    head->data = 1;
    p = head;
    for (int i = 2; i <= m; i++) {
        q = (NODE*)malloc(sizeof(NODE));
        q->data = i;
        p->next = q;
        p = q;
    }
    p->next = head;
    return head;
}

void josephus_circle(NODE* head, int s, int n) {
    NODE *pre = head;
    NODE *p = NULL;

    for (int i = 1; i < s; i++) {
        pre = pre->next;
    }

    while (pre->next != pre) {
        for (int i = 1; i < n; i++) {
            p = pre;
            pre = pre->next;
        }
        printf("%d ", pre->data);
        p->next = pre->next;
        free(pre);
        pre = p->next;
    }
    printf("%d\n", pre->data);
    free(pre);
}

int main() {
    int m, s, n;
    printf("请输入整数m：\n");
    if (scanf("%d", &m) != 1 || m <= 0) {
        printf("m输入错误——你应该输入大于零的自然数\n");
        return 1;
    }
    printf("请输入整数s\n");
    if (scanf("%d", &s) != 1 || s < 1 || s > m) {
        printf("s输入错误，请输入在1~m间的整数s\n");
        return 1;
    }
    printf("请输入整数n\n");
    if (scanf("%d", &n) != 1 || n < 1 || n > m) {
        printf("n输入错误，请输入在1~m间的整数n\n");
        return 1;
    }

    NODE *head = create(m);
    josephus_circle(head, s, n);
    return 0;
}

文档

  • 需求分析：实现一个单向环表，输入 m、s、n，按约瑟夫环规则输出节点编号。
  • 概要设计：创建节点结构，定义创建和输出函数。
  • 详细设计：详述了结构体、创建函数、输出函数及主函数的实现步骤。
  • 调试分析：处理无输出问题和头结点地址更改问题。
  • 测试结果：成功输出预期结果。

# 实验二：简单计算器

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
cpp复制代码#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

typedef struct {
    char *data;
    int size;
    int top;
} Stack;

void initStack(Stack *stack, int maxSize) {
    stack->data = (char *)malloc(sizeof(char) * maxSize);
    stack->size = maxSize;
    stack->top = -1;
}

void push(Stack *stack, char c) {
    if (stack->top < stack->size - 1) {
        stack->data[++stack->top] = c;
    }
}

char pop(Stack *stack) {
    if (stack->top >= 0) {
        return stack->data[stack->top--];
    }
    return '\0';
}

bool isBalanced(char *expression) {
    Stack stack;
    initStack(&stack, 100);

    for (int i = 0; expression[i] != '\0'; i++) {
        char currentChar = expression[i];
        if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
            push(&stack, currentChar);
        } else if (currentChar == ')' || currentChar == ']' || currentChar == '}') {
            char poppedChar = pop(&stack);
            if ((currentChar == ')' && poppedChar != '(') ||
                (currentChar == ']' && poppedChar != '[') ||
                (currentChar == '}' && poppedChar != '{')) {
                free(stack.data);
                return false;
            }
        }
    }

    free(stack.data);
    return stack.top == -1;
}

int Priority(char a) {
    switch (a) {
        case '^':
            return 3;
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        default:
            return 0;
    }
}

int temporary_result(char a, int b, int c) {
    switch (a) {
        case '+':
            return b + c;
        case '-':
            return b - c;
        case '*':
            return b * c;
        case '/':
            return b / c;
        case '^':
            return pow(b, c);
        default:
            return 0;
    }
}

int main() {
    // Code to implement the calculator logic
}

文档

  • 需求分析：实现支持加减乘除、幂运算和括号优先级的简单计算器。
  • 概要设计：定义栈结构和基本操作函数，编写括号匹配、优先级比较和基本运算函数。
  • 详细设计：详细阐述了各函数的设计和实现，包括栈操作、括号匹配和基本运算。
  • 调试分析：解决括号匹配和优先级处理中的错误。
  • 测试结果：实现预期功能，正确处理表达式。

# 实验三：二叉树遍历

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
cpp复制代码#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

int Number(char *tree, int* index) {
    int number = 0;
    while (tree[*index] >= '0' && tree[*index] <= '9') {
        number = number * 10 + (tree[*index] - '0');
        (*index)++;
    }
    return number;
}

struct TreeNode* BuildTree(char* tree, int* index) {
    if (tree[*index] == '\0' || tree[*index] == '#') {
        (*index)++;
        return NULL;
    }

    int num = Number(tree, index);

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->data = num;

    while (tree[*index] == ' ') {
        (*index)++;
    }

    root->left = BuildTree(tree, index);

    while (tree[*index] == ' ') {
        (*index)++;
    }

    root->right = BuildTree(tree, index);

    while (tree[*index] == ' ') {
        (*index)++;
    }

    return root;
}

void midbianli(struct TreeNode* root) {
    if (root != NULL) {
        midbianli(root->left);
        printf("%d ", root->data);
        midbianli(root->right);
    }
}

void lastbianli(struct TreeNode* root) {
    if (root != NULL) {
        lastbianli(root->left);
        lastbianli(root->right);
        printf("%d ", root->data);
    }
}

void levelorderbianli(struct TreeNode* root) {
    if (root == NULL) return;

    struct TreeNode* queue[1000];
    int a = 0, b = 0;
    queue[b++] = root;

    while (a < b) {
        struct TreeNode* temp = queue[a++];
        printf("%d ", temp->data);

        if (temp->left != NULL) {
            queue[b++] = temp->left;
        }
        if (temp->right != NULL) {
            queue[b++] = temp->right;
        }
    }
}

int main() {
    char tree[1000];
    scanf("%[^\n]", tree);
    int index = 0;
    struct TreeNode* root = BuildTree(tree, &index);

    printf("中序遍历为：");
    midbianli(root);
    printf("\n");

    printf("后序遍历为：");
    lastbianli(root);
    printf("\n");

    printf("层次遍历为：");
    levelorderbianli(root);
    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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
cpp复制代码#include <stdio.h>

void print(int arr[10], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void InsertionSort(int arr[10], int n) {
    int j, temp;
    for (int i = 1; i < n; i++) {
        j = i - 1;
        int k = i;
        while (k >= 0 && j >= 0 && arr[k] < arr[j]) {
            temp = arr[k];
            arr[k] = arr[j];
            arr[j] = temp;
            j--;
            k--;
        }
    }
}

void QuickSort(int arr[10], int l, int n) {
    if (l + 1 > n) {
        return;
    }
    int first = l, last = n - 1, key = arr[first];
    while (first < last) {
        while (first < last && arr[last] >= key) {
            last--;
        }
        arr[first] = arr[last];
        while (first < last && arr[first] < key) {
            first++;
        }
        arr[last] = arr[first];
    }
    arr[first] = key;
    QuickSort(arr, l, first);
    QuickSort(arr, first + 1, n);
}

void SelectionSort(int arr[10], int n) {
    int temp, k;
    for (int i = 0; i < 10; i++) {
        temp = i;
        for (int j = i; j < 10; j++) {
            if (arr[temp] > arr[j]) {
                temp = j;
            }
        }
        k = arr[i];
        arr[i] = arr[temp];
        arr[temp] = k;
    }
}

int main() {
    int arr1[10], arr2[10], arr3[10];
    for (int i = 0; i < 10; i++) {
        scanf("%d", &arr1[i]);
        arr2[i] = arr1[i];
        arr3[i] = arr1[i];
    }
    InsertionSort(arr1, 10);
    printf("插入排序为：");
    print(arr1, 10);

    QuickSort(arr2, 0, 10);
    printf("快速排序为:");
    print(arr2, 10);

    SelectionSort(arr3, 10);
    printf("选择排序为：");
    print(arr3, 10);

    return 0;
}

文档

  • 需求分析：实现插入排序、快速排序和选择排序三种算法。
  • 概要设计：定义排序算法函数和打印函数。
  • 详细设计：详细描述了每种排序算法的实现步骤，包括插入排序、快速排序和选择排序。
  • 调试分析：解决选择排序中 temp 值指代错误的问题。
  • 测试结果：成功实现三种排序算法，输出预期结果。