C/C++数据结构题[2023-05-08]

1、简单数学问题（难度等级B）

[问题描述]
实现多个简单数学问题的求解。本题的第4项功能，“移动的三角形”，需要画图，请安装EasyX，并在程序中用include包含"conio.h"和 "graphics.h"头文件。同时，由于EasyX只适用于C++源程序，因此，程序最前面的部分应做如此处理：

然后将该程序保存为后缀为.cpp的源文件即可。虽然是.cpp文件，程序中依然使用我们的C语言就可以。
[基本要求]
（1） 程序运行后有菜单显示：
1.相邻数对
2.方程求解
3.排列组合
4.移动的三角形
5.数据读写
0.退出
请输入0-5：
（2） 若输入的是0-5以外的任何符号，程序不做任何相应；只要输入的是0-5以内的数字，则程序执行相对应的功能，结束后依然返回主菜单，可以继续选择做其它操作。
（3） 相邻数对：
提示用户输入数据规模N，然后利用rand()函数随机生成N个正整数（要求所有整数均小于10000），输出其中包含的所有相邻数对（数值相差为1的两个整数）以及相邻数对的总数。例如，若N=7，随机生成7个数据{2,0,3,6,1,0,4}，其中一共包括4个相邻数对，那么应该输出：
（1,0）、（1,2）、（2,3）和（4,3） 一共4个相邻数对。
注意，（0,1）和（1,0）是相同的相邻数对，不要重复统计和输出显示。
要求：不允许使用双重循环穷举的方式查找相邻数对。
（4） 方程求解；
提示用户输入三个系数(实型)作为一元二次方程 中的三个系数。根据输入的三个数据，求解并输出方程的根。注意要考虑全部可能的情况，即只有一个实根、两个不同的实根、两个相同的实根、两个虚根。
（5） 排列组合：
在整数值1——N中，选取M个数据的所有可能。提示用户输入两个整数N和M，M必须小于等于N，输入若不符合要求，提示用户输入错误，重新输入；若输入正确，则输出所有可能的M个数据的组合方式，同时输出组合的总数量。例如，若N=5，M=4，表示从1,2,3,4,5中，选取4个数据的所有可能组合。应该是5种，即输出：
（1 2 3 4）
（1 2 3 5）
（1 2 4 5）
（1 3 4 5）
（2 3 4 5）
一共5种组合方式。
注意，（1 2 3 4）和（1 3 2 4）属于同一种组合，不要重复选择！！
算法提示：可以利用递归的思想，一个一个的选取数据，当选取的数据总量等于M时，说明已经选取了一种组合，输出并累加统计。例如，利用穷举的方式在1——N之间选第i个数据，要求第i个数据必须比之前选的第i-1个数据要大，每选择一个数据，将其保存在一个数组A[i]中，若i已经等于M，则可以输出数组的A[1]---A[M]，并累加记录这是当前已经被选取的第k种组合。
（6） 移动的三角形：
利用“” 连续在屏幕指定位置画出指定边长的等腰三角形，形成动画的效果。
首先利用initgraph(M, N)函数，将屏幕初始化为M列、N行的显示屏，屏幕的左上角为原点，坐标（0,0）；然后从键盘输入一个数值linesize表示等腰三角形的底边长和高，根据屏幕大小以及三角形边长，随机生成一个坐标值start_x和start_y，作为三角形起始点，如下图所示。要求随机生成的坐标start_x和start_y不得使三角形画出屏幕之外。
根据三角形的起始点（start_x, start_y），以及三角形的边长和高linesize，用””将这个等腰三角形画出来。即利用outtextxy(x,y,"")函数，在指定的位置（x,y）显示,即可显示出该三角形；利用Sleep(200)函数，使得每个三角形显示保持200毫秒，然后利用cleardevice()函数清屏；随后再继续随机生成一个起始点坐标（start_x, start_y），根据这个起始位置再画出边长和高为linesize的等腰三角形；重复上述步骤，即可形成同一个三角形在屏幕中移动的效果。可以设定，画完50个三角形后，结束，利用closegraph()函数退出画图页面，返回主界面。

提示：根据给定的三角形边长和高，以及随机生成的三角形起始点，该三角形的3个顶点在屏幕中的坐标值是可以计算出来的，那么三角形的三条边的直线方程，即y=kx+b，其斜率k和截距b均可计算得到。只要将画在这三条边的位置上即可。例如要画底边，从起始点开始，所有的位置，y坐标保持start_y不变，只有x不断增加至start_x+linesize；要画左边的这条斜边，y坐标从起始点的start_y开始，一直到start_y-linesize，那么，对应每个y，边上点的x的坐标根据这条边的斜率和截距即可计算出来，然后即可调用outtextxy(x,y,"")画出。
由于每个也会占据若干行和列，为了显示美观，每个星号之间要有一定间距。也就是，比如在画底边时，x坐标要不断累加至start_x+linesize，最好设定x的增长间隔为10，即x=x+10（如果设定x++，画出来的全部连在一起，会变成一条线，看不出来是了）；同理，在画两个斜边时，y坐标要不断递减至start_y-linesize，同样设定y的递减间隔为10，即y=y-10。因此，输入的三角形边长linesize最好是10的倍数，且取值在30——500之间。
（7） 数据读写：
打开指定的数据文件express.txt，里边包含有若干简单的算术运算表达式。所有操作数均为正数。请读取该文件，计算这些表达式，并将计算结果输出显示并存储到数据文件中去。最后用于存储的数据文件后缀是txt，文件名是当前保存的系统时间加自己姓名（例如，若当前时间是17:34，那么存储结果的文件名就应该是1734黄元元.txt）。例如，若express.txt中的内容为：
1+2
3-6
49
9/2
则读取该数据文件后，屏幕输出显示如下：
1+2=3
3-6=-3
4*9=36
9/2=4
若当前系统时间为15:30，则将上述显示的表达式以及计算结果存入1530黄元元.txt文件中去。
（8） 退出：程序结束运行。

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

2、模拟银行排队叫号系统（难度等级A）

[问题描述]
　　模拟实现银行的排队叫号系统。
[基本要求]
（1） 假定银行上午9点开门，下午5点关门，期间每个小时的客流量不超过35人；
（2） 每个客户的基本信息包括：到达银行时间、业务需要办理的时长。这两项数据均由系统随机生成，其中业务办理所需时长定义不超过30分钟。若随机生成的时长等于0，即说明该客户未办理业务，提前离开；根据客户达到银行的时间，为客户发放号码牌（提前离开的客户，由于也已经到达银行，因此也会被发放号码牌）；
（3） 程序运行时，由键盘输入银行的窗口数量，然后输出：第几号客户几点到达，在等待了多少分钟后，在几号窗口办理业务，持续多少分钟；若客户是提前离开的，那对应的输出就是：第几号客户几点到达，提前离开。将8小时内，所有被服务的客户按照上述要求输出基本信息。最后，统计一下，每个窗口分别服务了多少客户，今天一共服务了多少客户；客户最长的等待时间以及客户的平均等待时间；
（4） 提示用户可以继续输入窗口数量，若输入0，程序结束；否则按照上述要求给出相应的输出；
（5） 观察银行的窗口数量与接待客户总量与客户等待时间之间的关系；
[输出样例]

只显示了部分，从1号开始显示的话太长。
[算法提示]
用结构体数组表示客户（每个数组元素包括客户到达时间、业务办理时间等成员），客户的数据利用随机数自动生成，按照他们的到达时间排序；银行的窗口也用数组表示，要记录的是每个窗口当前任务完成后即将空闲的时间，哪个窗口的空闲时间最先出现，就将当前排在最前的客户推送到该窗口；若有一个以上的窗口空闲时间一致，则可以将当前排在最前的客户推送给编号最小的窗口。

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

3、K均值聚类（难度等级A）

[问题描述]
K均值聚类是模式识别算法中一种非常经典的分类算法。其主要作用是将相似的样本自动归到一个类别中。
现对Iris数据做聚类。已知有150个四维的数据，若将每个数据看作是4维特征空间里的一个点，按照它们相互之间距离（欧氏距离）的远近，可以将这150个数据分作3类。现利用K均值聚类算法确定这150个数据的类别标签。
K均值聚类算法的基本思想：若已知N个数据分别属于K个不同的类别。首先从N个源数据中随机选取k个数据作为初始聚类中心，代表k个类别。然后计算每个数据到这个k个聚类中心的欧式距离，按照距离远近（某个数据，距离哪个聚类中心最近，该数据就属于哪个类别），确定每个数据所属类别；做完第一次分类后，计算每个类别中所有数据的均值，以该均值作为当前类别的新的聚类中心；将当前的聚类中心与上一次的聚类中心做比较，若当前的k个聚类中心与前一次的k个聚类中心重合，分类结束，当前数据所属类别即它的类别标签，若不重合，那么对N个数据再以当前的聚类中心为准重新做分类，做完分类后再计算当前k个类别的均值，即聚类中心，若与上一次的聚类中心重合，算法结束，否则继续执行上述步骤。若数据确实可分，那么经过有限次迭代，算法一定会收敛。
[基本要求]
（1） 输入要求：读取数据文件Iris中的数据，一共150条数据。利用一个151 4的二维数组存储这些数据，第0行不存放数据，从第1行开始存储数据。例如，定义数组float A[151][4],那第一条数据（5.1 3.5 1.4 0.2）就存放于A[1][0],A[1][1],A[1][2]和A[1][3]中，即数组A的第1行，代表第1条数据，数组A的最后一行，即第150行，代表第150条数据。已知这所有150条数据分属于3个类别；
（2） 输出要求：首先输出本次聚类所选取的初始聚类中心的数据编号（从1到150）。初始聚类中心随机选取或者计算得到，不允许从键盘输入：
 可以从150条数据中随机选取3条数据作为初始聚类中心，这样做难度会被降级，因为实际上，初始聚类中心的选择会影响最终的聚类结果；
 在150个数据中选择彼此距离最远的三条数据作为初始聚类中心。可以首先随机选择第一个聚类中心，然后根据计算，得到其余两个初始聚类中心；
（3） 输出要求：根据选定的初始聚类中心，开始做聚类。聚类结束后，输出本次聚类所需的迭代次数、以及三个类别中分别包含的数据编号（注意只输出数据编号，不要输出显示实际的数据）以及每个类别包含的数据总数；
（4） 输出要求：按照上述的聚类方式，重复做至少5次聚类，观察每次的聚类结果是否均相同；
[输出样例]

[算法提示]
150个4维的数据，可以用一个151*4的二维数组来保存这些数据。即151行，4列，第0行不存放数据，从第1行开始存储数据。这样，数据从1开始计数。例如，定义数组float A[151][4],那第一个数据（5.1 3.5 1.4 0.2）就存放于A[1][0],A[1][1],A[1][2]和A[1][3]中，即数组A的第1行，代表第1个数据。

说明：若两个数据x=( ),y=( )
1、 他们之间的欧氏距离
2、 x和y的均值

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

4、折半查找与哈希查找（难度等级A）

[问题描述]
查找是通过在查找表中做比较来完成的操作。折半查找与哈希查找都是利用数组实现的查找算法。通过本题，可以观察两种查找算法的性能。一般我们用平均查找长度ASL来表示一种查找算法的性能。ASL值越大，表示该查找算法所需的比较次数越多，性能也就越低。ASL的计算公式为：

其中，M表示待查找记录的总数量； 表示，在查找表中，要找到第i条记录，需要的比较次数。将找到各条记录所需的比较次数求累加和，再将该累加和除以数据总量，即表示平均查找长度。
现有M条待查数据，每条数据有一个关键字key（关键字可以唯一的标识一条数据），例如有M条表示学生的数据，每条数据包括学生姓名、学号、所在学院，手机号码等信息。因为每个学生的手机号码均不相同，因此可以用该项数据作为每条记录的关键字key。
（1） 折半查找表的创建。折半查找表是一个表长为M的数组，将所有记录存入数组，然后根据关键字排序即可。
（2） 折半查找。在有序的数组（查找表）中做查找，根据待查关键字，做折半查找即可。
（3） 哈希表的创建。哈希表是一个长度为N的数组，（一般N>M），现要将M条数据逐条放入哈希表，放入的规则，即：
 首先设计哈希函数H（X）；然后根据当前记录的key，即手机号码，将其代入哈希函数，得到k=H(key),这个k即为该条数据放入哈希表的地址，也叫做散列值。k的取值必须在0~N-1之间；
 但是有时候，不同的key通过哈希函数计算得到的k值会相等，这种情况称之为冲突，即当前k所在位置已经放入了某条数据。此时就需要为当前记录重新找个地址存放，称为再散列；
 再散列同样遵循某种规则，例如 ，其中 表示第 次再散列， 表示第 次再散列后得到的地址。再散列过程中， 从1开始，若 的位置为空，那么就可以将当前记录放入该位置。重复上述操作，直到将所有M条数据均放入哈希表，哈希表的创建即可完成。
（4） 哈希查找。在创建好的哈希表中做查找，过程与上述的创建过程类似：
 给定待查找数据的关键字key，将其带入哈希函数，计算其在哈希表中的地址k=H(key)；
 若哈希表中当前k的位置为空，则表示该待查数据不存在，查找结束；
 若哈希表中当前k的位置不为空，则将该位置中数据的关键字key与待查数据的关键字key做比较。若相等，表示查找成功，查找结束；若不相等，那么有可能是产生了冲突，因此按照再散列的规则，计算再散列地址 ，将待查关键字key与再散列地址中的key依次做比较，若待查关键字确实存在，那么经过有限次的再散列，必然会查找成功，反之若待查关键字不存在，那么经过有限次的再散列，再散列地址 必然是一个空位。查找中遇到空位，即表示待查数据不存在，查找不成功，查找结束。
[基本要求]
（1） 现有2437条记录，每条记录包含有下列数据项：手机号码、姓名、性别、所属学院；
（2） 从文件读入所有记录，首先以手机号码为关键字，建立折半查找表，即表长N为2437，并且所有记录以手机号码升序有序；再以手机号码为关键字key建立哈希表，要求哈希表表长N（数组长度）等于2707。根据以下哈希函数和再散列规则创建哈希表：
 哈希函数：手机号共11位，去掉前4位和后3位，取中间的4位作为一个数字计算其平方，将该平方值去掉最高位和最低位，取中间若干位组成的数字与哈希表的表长N求模（求模是确保得到的地址在0—2706之间），得到的结果即为该key对应的记录应该存放的地址（例如，若当前记录的手机号码是13812145677，去掉前4位和后3位后，得到2145，计算2145的平方是4601025，该平方值掐头去尾是60102,60102与表长2707求模，得到的最终结果是548，若哈希表的第548号位置是空的，则关键字13812145677对应的记录应存入哈希表的548号位置）；
 再散列规则：若根据上述哈希函数计算得到的地址k非空，说明产生冲突，则需要再散列。再散列规则： ， 。
 还是以上述关键字13812145677为例，若初始得到的哈希地址548非空，则要做再散列。第1次再散列得到（548+1）%N和（548-1）%N两个地址 ，先判断549的地址，若空，放入；若不空，继续判断547的地址，若空，放入；若不空，则做第2次散列，再得到两个地址(548+4)%N和(548-4)%N，再做上述判断….，直到找到一个空地址可以放入该条记录为止。
 注意，再散列过程中，由于会计算减法，即 ，若该值为负数，则将该负数与表长N相加，一直加到值大于等于0为止，然后再与表长N做求模运算。
（3） 创建完毕后，显示该哈希表的ASL；显示折半查找表的ASL
（4） 然后提示用户可以输入手机号码进行查询。待输入手机号码后，对该手机号码分别进行折半查找和哈希查找。若该号码存在，则提示查找成功，并显示折半查找做了几次比较，哈希查找做了几次比较，然后输出显示该号码对应的记录的全部内容，即姓名、性别、手机号码、所属学院；若该号码不存在，则提示查找失败，该号码不存在，再分别显示折半查找做了几次比较，哈希查找做了几次比较。
（5） 当前查找结束后，提示用户可以继续输入，如果输入“#”，则程序结束；否则，继续做上述的查找。
（6） 可以对输入的手机号码做错误判断，例如如果输入的位数不对，提示用户重新输入；
（7） 如果只完成一种查找算法、或者不能实现连续的查找、或者没有显示每次查找所需要的比较次数、或者没有计算ASL，难度都会被降级。
[输出样例]

5、字符串处理（难度等级A）

[问题描述]
以字符串的形式从键盘输入一串数字，比如“89101112131415”，对该字符串做处理，判断其中是否包含一组差值为1的等差序列（序列中至少包含两个数字，序列必须包括字符串中的所有输入符号），若存在，则输出该序列；若不存在，也给出相应的提示信息。例如在上述输入中就包含一组符合要求的等差序列：8、9、10、11、12、13、14、15。有一种特殊情况，比如输入为“810111213”，其中包含的等差序列8、10、11、12、13中漏掉了一个9，如果存在这种情况，即序列中仅仅漏掉了一个数字，也请输出该序列，并提示，漏掉了哪个数字。
[基本要求]
（1） 程序运行后，提示用户输入一串数字（输入的一串数字必须以字符串形式保存），至少2位，最长不超过50位。若输入不和要求，或者其中包含非数字的其它符号，提示用户输入非法，重新输入；若输入为#，程序结束；若输入合法，继续执行下述步骤；
（2） 若输入合法，对该字符串做处理，判断其中是否包含一个差值为1的等差序列或者是否包含一个仅漏掉一个数字的差值为1的等差序列。若有，输出该序列，有漏掉的数字，也请在输出序列的同时，也显示被漏掉的数字；若不存在这样的序列，提示用户不存在符合要求的序列；
（3） 提示用户可以继续输入 ，重复上述步骤。
（4） 将本次程序执行过程中，所有输入序列以及处理结果，写入一个文本文件。文件的后缀是*.txt。文件名是当前保存的系统时间加自己姓名（例如，若当前时间是17:34，那么存储结果的文件名就应该是1734黄元元.txt）。例如，若针对下图中显示的输入以及处理结果，程序结束后，若时间是12:28，则应该生成一个文本文件1228黄元元.txt。该文件中的内容：
字符串：891011121314151617包含序列：
8 9 10 11 12 13 14 15 16 17
字符串1234t578不合法
字符串：979899101102103包含序列：
97 98 99 101 102 103 漏掉100
字符串：56781901234不包含符合要求序列
（5） 若不能对输入做错误判断，或者不能连续输入，或者保存结果的文件名不和要求等，难度会降级
[输出样例]

[算法提示]
可以用穷举的方法，从序列中第一个数是1位数开始，判断是否存在符合要求的序列，若有，本次操作可结束；如无，再从序列中第一个数是2位数开始，再做判断….，因为要求序列中至少包含2个数字，因此如果输入的字符串长度为N，那么序列中第一个数最多只能包含(N/2)位数字。也就是穷举的话，序列中第一个数的位数从1到N/2逐一穷举即可。
要特别注意，序列中的数字从1位数变到2位数，或者2位数变到3位数….等这种情况。

注意：
1、 程序中需要的功能函数可以自己定义。在课设报告中，一定要把除了主函数以外的，所有自定义的函数给出说明，包括：函数的功能、各个参数的意义、若有返回值则返回的是什么等；
2、 不允许使用全局变量！所有变量必须在函数体内定义。可以使用宏定义

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111