C/C++自动 21 级(含卓越 211)《软件技术基础》期末大作业

C/C++自动 21 级(含卓越 211)《软件技术基础》期末大作业

一、作业内容

题目一：请你设计一个算法，从顺序表中删除自第 i 个结点开始的 k 个结点。要求先输出整个顺序表，再输出删除自第 i 个结点开始的 k 个结点后的结果。

【编程提示】
假设 a[max]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
i=5;k=5;
输出结果为：
原顺序表：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
删除结点后：1,2,3,4,10,11,12,13,14,15

【上机要求】
要求采用 C/C++语言上机编程实现上述功能，并至少展示两组与所给编程提示不同的输
出结果。

题目二：请你运用数据结构中“栈”的思想，编写一个算法，要求把输入的中缀表达式转换成后缀表达式，并计算该表达式的值。

【编程提示】

1. 用户在键盘上输入表达式时，通常是运算符位于两个操作数之间，即为中缀表达式。
   例如：3*(8+4)。计算时遵循“自左向右计算，先乘除后加减，先括号内后括号外”的规则。因此，中缀表达式的计算需要考虑括号、运算符优先级等诸多因素，比较麻烦。而后缀表达式(即波兰表达式)在格式上已经考虑了运算符优先级，消除了括号，运算时只需处理操作数和运算符，比较简洁。
2. 该问题可分成两个部分：一个为中缀表达式转换为后缀表达式算法的实现；另一个是对后缀表达式求值。

【上机要求】
要求采用 C/C++语言上机编程实现上述功能，运行的输出结果中要包含以下信息：原表达式、后缀表达式及表达式计算结果，运行测试数据至少两组。

题目三：请你设计一个算法，实现文具店定期对销售商品的记录进行统计，要求按商品的单价进行升序排序。

【编程提示】

1. 可以先从数据文件中读出各商品的记录信息，并存储在顺序表中。各商品信息包括：商品名、单价、销售量等。
2. 假设文件 store.txt 的内容如下：

商品名称 单价 销售量
中性笔 2 100
铅笔 1 88
钢笔 15 35
笔记本 10 90
书包 100 10
水彩笔 18 73
……
1
2
3
4
5
6
7
8

3. 编译运行后显示

商品名称 单价 销售量
铅笔 1 88
中性笔 2 100
笔记本 10 90
钢笔 15 35
水彩笔 18 73
书包 100 10
……
1
2
3
4
5
6
7
8

【上机要求】
要求对单价的排序采用冒泡排序法，C/C++语言编程实现。

【扩展功能】
选择其他排序算法(不包含冒泡排序法，如快速排序、堆排序等)，实现对销售量进行排序（升序或降序均可）。（注：本功能为扩展功能，属于加分项）

扩展功能运行结果：

1——按单价排序(升序) 2——按销售量排序（升序） 0——退出
2(回车)
商品名称 单价 销售量
书包 100 10
钢笔 15 35
水彩笔 18 73
铅笔 1 88
笔记本 10 90
中性笔 2 100
1
2
3
4
5
6
7
8
9

题目四：要求利用带头结点的单链表，根据所提供的源代码，实现两个集合的并、交、差运算。

【具体功能描述】
1)要求用带头结点的单链表存储两个集合中的元素和最终的结果。
2)集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即使得链表中没有重复数据。
3)显示两个集合的内容及其并集、交集和差集的内容。
4)要求不改变原来的集合，并集、交集和差集分别另外存放。
【程序源代码】

#include 
#include 
#include 
#include 
using namespace std;
typedef char datatype;

typedef struct LNode
{
    datatype data;
    struct LNode* next;
} LinkList;

void DispList(LinkList* L) {
    LinkList* p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void DestroyList(LinkList*& L) {
    LinkList* p = L->next, * pre = L;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}

LinkList* CreateListF()//尾插法建立单链表
{
    LinkList* head, * p, * r, * s;
    datatype CreateListF_num;
    int n;
    printf("创立一个链表，大小为：");
    scanf("%d", &n);
    head = (LinkList*)malloc(sizeof(LinkList));
    head->next = NULL;
    r = head;
    printf("输入以空格隔开的十进制整数：");
    for (int i = 1, k = 1; i <= n; i++, k++) {
        int flag = 1;
        s = head->next;
        scanf("%d", &CreateListF_num);
        for (int j = 1; j < k; j++, s = s->next) {
            if (CreateListF_num == s->data) {
                flag = 0;
                k--;
                break;
            }
        }
        if (flag) {
            p = (LinkList*)malloc(sizeof(LinkList));
            p->data = CreateListF_num;
            r->next = p;
            r = p;
        }
    }
    r->next = NULL;
    return head;
}

///从小到大排序
void sort(LinkList* L) {
    LinkList* pre, * p, * q;
    if (L->next != NULL) {
        p = L->next->next;
        5
            L->next->next = NULL;
        while (p != NULL) {
            q = p->next;
            pre = L;
            while (pre->next != NULL && pre->next->data < p->data)
                pre = pre->next;
            p->next = pre->next;
            pre->next = p;
            p = q;
        }
    }
}

void Delete(LinkList* head) {
    if (head->next != NULL) {
        LinkList* p = head->next, * r = head, * q;
        while (p->next) {
            if (p->data == p->next->data) {
                q = p->next;
                p->next = q->next;
                free(q);
            } else
                p = p->next;
        }
    }
}

///求集合的并
void Union(LinkList* ha, LinkList* hb, LinkList*& hc) {
    LinkList* pa = ha->next, * pb = hb->next, * pc, * s;
    hc = (LinkList*)malloc(sizeof(LinkList));
    pc = hc;
    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {
            s = (LinkList*)malloc(sizeof(LinkList));
            s->data = pa->data;
            pc->next = s;
            pc = s;
            pa = pa->next;
        } else if (pa->data > pb->data) {
            s = (LinkList*)malloc(sizeof(LinkList));
            s->data = pb->data;
            pc->next = s;
            pc = s;
            pb = pb->next;
        } else {
            s = (LinkList*)malloc(sizeof(LinkList));
            s->data = pa->data;
            pc->next = s;
            pc = s;
            pa = pa->next;
            pb = pb->next;
        }
    }
    if (pb != NULL)
        pa = pb;
    while (pa != NULL) {
        s = (LinkList*)malloc(sizeof(LinkList));
        s->data = pa->data;
        pc->next = s;
        pc = s;
        pa = pa->next;
    }
    pc->next = NULL;
}

///求两个有序集合的交用尾插法
void InterSect(LinkList* ha, LinkList* hb, LinkList*& hc) {
    LinkList* pa = ha->next, * pb, * pc, * s;
    hc = (LinkList*)malloc(sizeof(LinkList));
    pc = hc;
    while (pa != NULL) {
        pb = hb->next;
        while (pb != NULL && pb->data < pa->data)
            pb = pb->next;
        if (pb != NULL && pb->data == pa->data)///B 节点在 A 节点中复制 A 节点
        {
            s = (LinkList*)malloc(sizeof(LinkList));
            s->data = pa->data;
            pc->next = s;
            pc = s;
        }
        pa = pa->next;
    }
    pc->next = NULL;
}

///求两个有序集合的差
void Subs(LinkList* ha, LinkList* hb, LinkList*& hc) {
    LinkList* pa = ha->next, * pb, * pc, * s;
    hc = (LinkList*)malloc(sizeof(LinkList));
    pc = hc;
    while (pa != NULL) {
        pb = hb->next;
        while (pb != NULL && pb->data < pa->data)
            pb = pb->next;
        if (!(pb != NULL && pb->data == pa->data))///B 节点不在 A 节点中复制 A 节点
        {
            s = (LinkList*)malloc(sizeof(LinkList));
            s->data = pa->data;
            pc->next = s;
            pc = s;
        }
        pa = pa->next;
    }
    pc->next = NULL;
}

int main() {
    LinkList* ha, * hb, * hc;
    ha = CreateListF();
    hb = CreateListF();
    printf(" 集合的运算如下:\n");
    printf(" 原集合 A: ");
    DispList(ha);
    printf(" 原集合 B: ");
    DispList(hb);
    sort(ha);
    sort(hb);
    Delete(ha);
    Delete(hb);
    printf(" 有序集合 A: ");
    DispList(ha);
    printf(" 有序集合 A: ");
    DispList(ha);
    Union(ha, hb, hc);
    printf(" 集合的并 C: ");
    DispList(hc);
    InterSect(ha, hb, hc);
    printf(" 集合的交 C: ");
    DispList(hc);
    Subs(ha, hb, hc);
    printf(" 集合的差 C: ");
    DispList(hc);
    DestroyList(ha);
    DestroyList(hb);
    DestroyList(hc);
    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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

【运行结果示例】

【上机要求】

1. 要求修改源代码中的结构名、结构类型名、结构变量以及相关参数，而且命名时要
   包含自己的名字或姓名首字母或学号等信息。
2. 要求至少展示与图 1 所示运行示例不同的三种测试结果，并且要包含一种边界条件的测试结果(如其中一个集合为空)。

源码传送门

传送门：https://pan.baidu.com/s/1JJs9vbZahUCB6cQvXLgAVg?pwd=1111

二、报告要求
大作业中的所有题目都要形成文字材料，具体报告内容要求如下：

1. 要求进行需求分析，陈述要解决的问题及要实现的功能。
2. 所有代码要在报告中体现，同时要求包含以下内容：程序的总体设计，子程序设计，算法流程图，算法分析（如：算法的时间复杂度），使用的数据结构及存储结构，详细说明使用的逻辑结构及存储结构的优缺点。
3. 报告中要包括对测试数据及测试结果的截图及分析。
4. 记录程序调试过程中遇到的主要问题，以及是如何解决的，并截图在报告中展示。
5. 是否有尚未解决的问题？是否考虑了一些应对的策略？如果有，可撰写到报告中。
6. 总结课程学习过程中及完成大作业过程中的收获与心得体会。
7. 报告模板见附件 1。

三、特别说明
1）要求大作业中涉及到的程序，统一存放在以本人学号命名的文件夹中，不得存放在他人电脑中，如发现两人共用一台电脑，此二人均无成绩。对运行结果截图时要包含存储路径，否则无效，具体如图 2 所示：

2）不得复制他人代码，如发现雷同，无论抄与被抄者，均无成绩。