下载文档第一篇：计算机实验报告范本
PowerPoint 202_演示文稿制作
1.实验性质：设计性实验
2.所属课程名称：大学计算机基础
3.实验计划学时：4
4.实验目的1)掌握PowerPoint 202_ 的基本界面和文稿基本操作，掌握幻灯片编辑排版基本操作。
2)掌握设置动画和切换效果、设置幻灯片放映方式、超级链接和动作按钮的设置、幻灯片放映、页面设置和打印。
5.实验内容和要求
1)掌握演示文稿的编辑方法，包括文稿的多种创建方法，文稿的插入、移动、复制、删除操作方法。
2)掌握演示文稿的外观设计方法，包括设计模板的使用；应用配色方案；母版的使用。
3)掌握演示文稿中对象的编辑方法，包括文本对象、图片对象、表格对象、组织结构对象、图表对象等。
4)掌握演示文稿的动态控制方法，如动画效果的添加、超链接的创建、动作按钮的使用等。
5)掌握演示文稿的放映方法，如放映方式的设置、幻灯片切换效果的设置、幻灯片的放映和打印。
6.实验主要仪器设备
WindowsXP操作系统；PowerPoint2003
7.实验步骤
8.实验结果
[对实验结果进行总结：
1、是否按时完成实验；
2、是否得到正确结果；
3、有什么遗留问题尚待解决]
9.讨论和分析
[
1、讨论实验过程中所遇到的问题，寻求解决办法；
2、对本实验的各类型知识进行总结、归类]
第二篇：计算机实验报告
课程：大学计算机基础 班级 ： ***** 学号：** 姓名：***组别： 同组者姓名： 仪器编号： 实验日期：
实验 windows 202_ 操作[实验目的]1.掌握windows 202_的启动和退出。熟悉windows 202_的桌面环境，掌握“回收站”、任务栏、帮助菜单的使用。2.掌握windows 202_的窗口、菜单以及对话框的操作。掌握“资源管理器”和“我的电脑”的使用。3.掌握文件与文件夹的创建、移动、复制等基本操作。4.掌握应用程序的安装与删除、移动与退出，快捷方式的创建与删除。5.掌握windows 202_系统的设置，了解windows2000 附件的使用。[实验环境]硬件：pentium 以上的计算机。软件：windows2000 操作系统。[实验内容]
见附件[实验结果]1.建立了如下图所示目录树：d： user new1.cod a user2 b bbb new2.docbbb2.完成了“计算机”快捷方式的创建。3．完成了控制面板中显示、区域选项等属性的设置。实验指导教师（签名）实验成绩 实验报告批改日期： 实验内容：2．（1）打开b文件夹 选中bbb 单击右键后选择“复制”命令 打开user文件夹 在空白处单击右键后选择“粘贴”命令。（2）打开user文件夹 选中b 单击右键后选择“剪切”命令 打开a文件夹 在空白处单击右键后选择“粘贴”命令。（3）打开user文件夹 选中c 单击右键后选择“删除”命令。3．（1）单击“开始”按钮后选择“搜索/文件或文件夹”命令 在搜索对话框的文件名栏中输入“calc.exe” 单击“搜索”按钮 选中找到的程序 单击右键选择“发送到桌面快捷方式”。（2）选中桌面上的“calc.exe”快捷图标 右键单击后选择“重命名” 输入“计算器”。（3）选中桌面“计算器”快捷图标 按鼠标左键拖动到“开始”菜单的“程序”选项中。（4）选中桌面上的“计算器”快捷图标 按鼠标左键拖动到“回收站”图标上 在确认对话框中单击“是”。4．（1）打开“控制面板”窗口 双击显示器图标 单击“屏幕保护程序”选项卡 在“屏幕保护程序”下拉列表框中选择“滚动字幕” 单击设置按钮 出现的对话框分别做相应的设置 单击“应用”按钮 单击“确定”按钮。（2）打开“控制面板”窗口 双击显示器图标 单击“图案”按钮 在图案列表框中选择“clouds” 在“显示图片”列表框中选择“居中” 单击“应用” 单击“确定”。（3）打开“控制面板”窗口 双击“区域选项”图标 单击“货币”选项卡 在“货币符号”下拉列表框中选择“$” 在“货币正数格式”下拉列表框中选择“￥1.1” 在“货币负数格式”下拉列表框中选择“-￥1.1” 单击“应用”按钮 单击“确定”按钮。（4）打开“控制面板”窗口 双击“区域选项”图标 单击“数字”选项卡 在“小数点后面的位数”下拉列表框中选择“2” 在“数字分组符号”下拉列表框中选择“,” 在“组中数字个数”下拉列表框中选择“123,456,789” 单击“应用”按钮 单击“确定”按钮。（5）打开“控制面板”窗口 双击“区域选项”图标 单击“日期”选项卡 在“短日期格式”下拉列表框中选择“yy-mm-dd” 单击“应用”按钮 单击“确定”按钮。（6）单击“时间”选项卡 在“时间格式”下拉列表框中选择“hh:mm:ss” 在“上午格式”下拉列表框中选择“am” 在“下午格式”下拉列表框中选择“pm” 单击“应用”按钮 单击“确定”按钮。（7）打开“控制面板”窗口 双击“任务栏和开始菜单”图标 在“自动隐藏任务栏”单选按钮前打钩 去掉“显示时钟”单选按钮前的钩 单击“应用”按钮 单击“确定”按钮。5．（1）单击“开始”菜单 选择“程序/附件/画图”打开画图程序 按要求画一副风景图。（2）在“画图”窗口中单击“a”按钮 输入文字“这是我的家”（3）单击“文件/保存”菜单 在“文件名”文本框中输入“我的家 ”存盘（4）打开一副图片 按[alt]+[print screen] 打开“画图”程序 单击“文件/新建”菜单 在图纸的空白出单击右键选择“粘贴” 单击“文件/保存”菜单 在“文件名”文本框中输入“截图 ”存盘。
www.teniu.cc【teniu.cc范文网】
第三篇：计算机实验报告
计算机实验报告
课程名称：大学计算机基础。实验名称：演示文稿的操作。实验目的：通过上机实践操作，理解并掌握了演示文稿的创建及基本操作。实验仪器与器材：计算机，U盘。
实验内容：使用“欢天喜地”设计模板创建演示文稿。1‘第一张幻灯片应用“标题幻灯片”板式。2’设置标题为“祝您生日快乐”，字体为“楷体”，“加粗”，“倾斜”，“阴影”，字号为44，颜色为“红色”。3‘在第一张幻灯片的右下方插入一张来自文件的图片。4’插入第二张幻灯片，应用空白版式。5‘在第二张幻灯片插入艺术字“生日快乐”，字体为“宋体”，“加粗”，“倾斜”，字号为80，艺术字的形状为“波形2”，设定为“底部飞入”的动画效果。6’在艺术字下方插入一张剪贴画。
实验步骤：1‘双击POWERPOINT图标打开演示文稿。2‘在“新建演示文稿”任务窗格中单击“根据设计模板”链接，打开“幻灯片设计”任务窗格，单击“欢天喜地”模板，当前幻灯片默认使用标题版式。3’单击文本框输入“祝您生日快乐”，选定输入的文字，右键单击，选中下拉框中的“字体”，设置为“楷体”，字形为“加粗倾斜”，字号为44，勾选效果中的“阴影”，选定颜色下拉框中的“红色”。4‘执行“插入”|“图片”|“来自文件”命令，单击要应用的图片，并将图片拖拽到第一张幻灯片中的右下方。5’执行“插入”|“新幻灯片”，然后执行“格式”|“幻灯片版式”命令，选择“空白”版式。6‘在第二张幻灯片中执行“插入”|“图片”|“艺术字”命令，单击“波形2”艺术字形状，在编辑艺术框中输入“生日快乐”，选定字体为“宋体”，字号为80，“加粗”，“倾斜”，点击确定。右键单击艺术字，选定“自定义动画”，执行“添加效果”|“进入”|“飞入”|“方向”|“自底部”命令。7’执行“插入”|“图片”|“剪贴画”命令，在“剪贴画”窗格下单击“管理剪辑”，选定所应用的剪贴画，并将其拖拽到艺术字下方。8‘点击“保存”后，关闭演示文稿。实验结果及收获：完成了演示文稿的创建及操作，学会了演示文稿的基本应用。
第四篇：《计算机图形学》实验报告
吉林大学
计算机科学与技术学院
《计算机图形学》实验报告
班级： 211923班
学号： 21190928
姓名： 林星宇
202_-202_学年第1学期
实验项目1
边标志算法的实现
实验性质
□演示性实验 验证性实验
□操作性实验 综合性实验
实验地点
计算机楼B212
机器编号
一、实现的功能
编写应用程序，采用鼠标输入顶点的方法确定待填充多边形（多边形最后一点双击）；实现边标志算法完成对该多边形的填充，要求 完成使用自己学号的后四位数字对多边形内部进行填充。
二、采用的图形学算法及实现
（算法的实现函数是什么（函数名，参数，返回值，函数功能等）以及采用了哪些数据结构（数组，链表等））
要求使用边标志算法的原理和实 现方法，所以使用了EdgeMarkFill函数，即边标志算法：
void CMFCDrawTestView::EdgeMarkFill(CDC* pDC, CArray
pDC为设备环境变量指针，plist为多边形点表，color为传入的RGB（）值。
int zima[16][32]为学号后4位二维数组。
X1,x2,y1,y2分别为多边形上的最小最小大,y值
三、采用的交互方式及实现
（采用了哪些交互方式来完成绘制，这些交互方式应用到了哪些系统消息，是如何实现的）
边填充的实现：编写应用程序，采用鼠标输入顶点的方法确定待填充多边形（多边形最后一点双击）；实现边标志算法完成对该多边形的填充，要求 完成使用自己学号的后四位数字对多边形内部进行填充。
易知，在画完多边形后，即双击左键（OnLButtonUp）后，使用EdgeMarkFill函数。
Type=2时，在OnLButtonUp中，调用EdgeMarkFill(pDC,&(obj->points), RGB(r, 0, 0));
四、实验结果
（程序的运行结果）
应用程序运行后，标志算法完成对该多边形的填充的图形结果如下：
五、遇到的问题及解决办法
问题1：（在实现过程中遇到了什么样的问题，及采用了何种解决办法）
在获取下x1,x2,y1,y2时，因为Dos界面x、y大小颠倒的原因，获取时出现了问题。
首先，通过for(int i = 1;i < plist->GetSize();i++){
CPoint p = plist->GetAt(i);
if(x1 > p.x)x1 = p.x;
if(x2 < p.x)x2 = p.x;
if(y1 > p.y)y1 = p.y;
if(y2 < p.y)y2 = p.y;
}
获取x1,x2,y1,y2.在遍历多边形过程中：
int count = plist->GetSize();
for(int i = 0;i < count;i++){
CPoint p1 = plist->GetAt(i);
CPoint p2 = plist->GetAt((i + 1)% count);
if(p1.y == p2.y)
continue;
if(p1.y > p2.y)
{
CPoint p;p = p1;p1 = p2;p2 = p;
}
xs = p1.x;
dxs =(p2.x-p1.x)/(double)(p2.y-p1.y);
//dys = abs(p2.y-p1.y)/(p2.y-p1.y);
for(ys = p1.y;ys!= p2.y;ys += 1)
{
Ixs = int(xs + 0.5);
MARK[ys][Ixs] =!MARK[ys][Ixs];
xs = xs + dxs;
}
黄线处即为处理x1,x2,y1,y2的大小。
问题2：通过数组zima[][]来确定多边形区域填充学号后4位时，zima[y ][x ]未%其字长，即zima[y % 16][x % 32]。后改为：
for(y = y1;y <= y2;y++)
{
bool inside = false;
for(x = x1;x <= x2;x++)
{
if(MARK[y][x])
inside =!inside;
if(inside)
{
if(zima[y % 16][x % 32])
pDC->SetPixel(x, y, RGB(255, 0, 0));
}
}
}
实验项目2
立方体的比例、平移、旋转变换及投影显示
实验性质
□演示性实验 验证性实验
□操作性实验 综合性实验
实验地点
计算机楼B212
机器编号
一、实现的功能
建立立方体的数据模型；编写应用程序，利用菜单和键盘结合的方式完成对立方体的移动、比例和旋转变换，并显示透视或斜二测投影结果。要求应用程序具有如下功能：
1、通过菜单选择的方式，选择对三维空间中的立方体作斜二测投 影或透视投影；
2、通过键盘按键或鼠标移动的方式，完成对三维空间中的立方体 进行平移变换（上下左右前后），比例变换（放大或缩小）以及 旋转变换（绕 x，y，z 轴），并同时显示变换后的投影结果
3、创建对话框，通过对话框设置透视投影时候的投影中心，以及旋转变换时候的旋转轴（可以设置成分别绕 x 轴，y 轴，z 轴进 行旋转）
二、采用的图形学算法及实现
（算法的实现函数是什么（函数名，参数，返回值，函数功能等）以及采用了哪些数据结构（数组，链表等））
题目要求实现立方体的移动、比例和旋转变换，并显示透视或斜二测投影结果。
对要求1：在菜单选TY项中选择斜二测投影（斜二=1）或透视投影(透视=1)。然后在OnDraw中调用Draw_Cubic(CDC* pDC)画出立方体。
对要求2：在OnKeyDown中调用函数，即在键盘上按“S”使立方体变小，“B”使立方体变大，“←”“→”“↑”“↓”使立方体左右上下移动。
对要求3：在菜单XYZ中选择旋转的x,y,z轴，即x=1或y=1或z=1，然后在OnKeyDown中调用函数，即按键盘上的“T”或“P”.
三、采用的交互方式及实现
（采用了哪些交互方式来完成绘制，这些交互方式应用到了哪些系统消息，是如何实现的）
由题目要求1，易知需要一个函数Draw_Cubic(CDC* pDC)画出立方体的斜二测投影或透视投影并且建立一个菜单栏TY(投影)。即在菜单选TY项中选择斜二测投影（斜二=1）或透视投影(透视=1)。然后在OnDraw中调用Draw_Cubic(CDC* pDC)画出立方体。
由题目要求2：易知直接在OnKeyDown函数上添加使立方体变大变小，前后左右平移的功能。即即在键盘上按“S”使立方体变小，“B”使立方体变大，“←”“→”“↑”“↓”使立方体左右上下移动。
由题目要求3：建立一个菜单XYZ决定旋转的轴。
四、实验结果
（程序的运行结果）
斜二测投影：
斜二测投影平移到左上角：
斜二测投影平移到右下角：
斜二测投影变大：
斜二测投影变小：
斜二测投影变为透视投影：
斜二测投影绕z轴旋转：
五、遇到的问题及解决办法
（在实现过程中遇到了什么样的问题，及采用了何种解决办法）
问题1：一开始建立立方体时，没有建立边表，导致投影困难。
后来建立了点表和对应的边表。
问题2：一开始Draw_Cubic中x1, y1,z1, x2, y2,z2定义为了int型。
实验项目3
用矩形窗口对多边形进行裁剪
实验性质
□演示性实验 验证性实验
□操作性实验 综合性实验
实验地点
计算机楼B212
机器编号
一、实现的功能
编写应用程序实现多边形裁剪。要求首先采用鼠标确定裁剪区域（矩形区域），然 后用鼠标输入待裁剪的多边形（可分别使用鼠标左键和右键来确定裁剪区域和待裁剪 的多边形）。多边形绘制完毕后进行裁剪，以不同颜色显示被裁剪对象位于窗口内（此 部分应保证多边形的完整性）及外部的部分。
二、采用的图形学算法及实现
（算法的实现函数是什么（函数名，参数，返回值，函数功能等）以及采用了哪些数据结构（数组，链表等））
因为要编写应用程序实现多边形裁剪。要求首先采用鼠标确定裁剪区域（矩形区域），然 后用鼠标输入待裁剪的多边形（可分别使用鼠标左键和右键来确定裁剪区域和待裁剪 的多边形）。所以要使用多边形裁剪算法，即Cut_Top()，Cut_Bottom()，Cut_Left（），Cut_Right（）四个函数。
Cut()函数为用绿色显示被裁剪对象位于窗口内部分。
存在int type的变量;
当type=1时，在OnLButtonUp中画出矩形框。
当type=2时，画出多边形，在左键双击后，在OnLButtonDblClk中调用如下函数：Cut_Top();Cut_Right();Cut_Bottom();Cut_Left();Cut();
裁剪多边形在，并标出在矩形内部的部分。
三、采用的交互方式及实现
（采用了哪些交互方式来完成绘制，这些交互方式应用到了哪些系统消息，是如何实现的）
编写应用程序实现多边形裁剪。要求首先采用鼠标确定裁剪区域（矩形区域），然 后用鼠标输入待裁剪的多边形（可分别使用鼠标左键和右键来确定裁剪区域和待裁剪 的多边形）。多边形绘制完毕后进行裁剪，以不同颜色显示被裁剪对象位于窗口内（此 部分应保证多边形的完整性）及外部的部分。
根据以上绘制方法，可知需要处理WM_OnLButtonDblClk（左键双击）及WM_LButtonUp（左键抬起）消息，为了绘制橡皮线，还需处理调用WM_MouseMove（鼠标移动）消息。
因为可以用鼠标画出矩形和多边形，所以这么规定，当type=1时画矩形，即：
DDALine(pDC,lx,by,lx,ty,RGB(r, g, b));
DDALine(pDC, lx, by, rx, by, RGB(r, g, b));
DDALine(pDC, rx, by, rx, ty, RGB(r, g, b));
DDALine(pDC, lx, ty, rx, ty, RGB(r, g, b));
当type=2时画多边形，而后裁剪，即：
for(int i = 0;i < pointList.GetSize();i++)
{
p1 = pointList.GetAt(i);
p2 = pointList.GetAt((i+1)% count);
DDALine(pDC, p1.x, p1.y, p2.x, p2.y, RGB(0,255,0));
}
四、实验结果
（程序的运行结果）
裁剪结果如下图所示，黑色为裁剪窗口，红色为多边形被裁剪的部分，绿色为多边形裁剪后的部分：
五、遇到的问题及解决办法
（在实现过程中遇到了什么样的问题，及采用了何种解决办法）
问题1：我在裁剪使一开始对多边形做上下左右裁剪时，这四个步骤是分别对原图形裁剪，而不是对图形接连进行裁剪。后来在裁剪函数上先除去之前图形，然后把已裁剪多边形重新构建。如下：
pointList.RemoveAll();
for(int i = 0;i < m;i++)
pointList.Add(CP[i]);
问题2：在多边形被矩形裁剪的部分显现不同颜色花费了挺多时间，后来我直接让裁剪的部分颜色被覆盖就可以了。如下：
for(int i = 0;i < pointList.GetSize();i++)
{
p1 = pointList.GetAt(i);
p2 = pointList.GetAt((i+1)% count);
DDALine(pDC, p1.x, p1.y, p2.x, p2.y, RGB(0,255,0));
}
第五篇：《计算机实践》 实验报告
《计算机实践》 实验报告 I
—数据结构
班号： 0316102 学号： 031650106
姓名： 郭砚璞 Email： 2755858446@qq.com
签名：
南京航空航天大学
202_年10月21日
目录
目录…………………………………………………………2
实验一：约瑟夫斯问题求解………………………………3
实验二：停车场管理问题…………………………………12
实验三：管道铺设施工的最佳方案问题…………………25
实验四：内部排序算法的实现与比较……………………35
参考资料……………………………………………………44
源程序清单…………………………………………………44
实验一、约瑟夫斯问题求解
一、问题描述
1）问题描述
约瑟夫斯（Josephus）问题的一种描述是：编号为 1，2，…，n 的 n 个人按顺时针方向
围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从
第一个人开始按顺时针方向自 1 开始报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向下一个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。
2）实验目的与基本要求
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3）测试数据
n=7，7 个人的密码依次为：3，1，7，2，4，8，4。m 初值为 6（正确的出列顺序应为
6，1，4，7，2，3，5）。
4）提示
程序运行后，首先要求用户指定初始报数上限 m，然后读取个人的密码。可设 n≤30。注意链表中空表和非空表的界限。
5）输入输出
输入数据：建立输入处理，输入 n 输入以及每个人的密码；m 的初值。
输出形式：建立一个输出函数，输出正确的序列。
6）选作内容
添加采用顺序存储结构实现问题求解的模块。
以上是本实验的题目要求，下面我将介绍我的实现算法，程序调试结果以及编程过程中遇到的具体问题，并且谈谈我的收获和感悟！
二、需求分析
1、本实验用于求出一组排列数的约瑟夫斯出列顺序。
2、程序运行后显示提示信息，提示用户输入人数n和初始报数上限m，程序需判断m与n的大小，如果m>n，需提示用户重新输入n值和m值。
3、m和n输入有效后，程序提示用户继续输入n个数据，作为n个人的密码。
4、用户输入完毕后，程序需自动显示输入的数据，并且按照出列顺序将n个出列者的编号结果显示出来。
三、概要设计
为了实现上述功能，应以循环链表的数据结构存储n个人的编号、密码信息和顺序关系，因此需要一个循环链表的数据类型。
1、循环链表抽象数据类型定义：
ADT CircularLinkList{
数据对象：一个循环链表，每个结点数据域是一个人的编号和密码。
数据关系：一个结点的指针域指向按照编号下一个结点。
基本操作：
CREATE_SL(SLNODE*);//构建顺序链表
ShowOutput(SLNODE *h, int m);//递归程序，按顺序依次输出出列者的编号
}ADT CircularLinkList
2、本程序保护模块
主函数模块
建立链表模块：将输入数据赋给结点数据域，并构建循环链表的数据关系
核心算法模块：按照算法移动指针、删除节点，依次输出出列者的编号。
调用关系：
3、算法流程图
四、详细设计
1.元素类型、结点类型和结点指针类型：
#define ElemType int
#define SLNODE struct sl_node
SLNODE
{
ElemType data[2];
SLNODE *next;
};
2、建立链表的伪码
SLNODE *CREATE_SL(SLNODE *h,int n)//创建一个h为头指针的链表，h指向的结点数据域用不到
{
ElemType data;
int i = 1;
SLNODE *p, *s;
p = h;
while(i<=n)
{
printf(“请输入第%d个元素:t”,i);
scanf_s(“%d”, &data);
s =(SLNODE *)malloc(sizeof(SLNODE));
s->data[0]=i;
s->data[1] = data;
if(h->next == NULL)
{
h->next = s;
}
else
{
p->next = s;
}
p = s;
i++;
}
p->next = h;
return h;
}
3、主函数伪码
int main()
{
int m,n,mistake=1;
SLNODE *Head;
PrintInformation1();//输出程序信息和个人信息
while(mistake)
{
printf(“输入人数n:n”);
scanf_s(“%d”, &n);
printf(“请指定初始报数上限m(m应必须小于等于n):n”);
scanf_s(“%d”, &m);
if(m>n)
{
printf(“输入数据有误，请重新输入n”);
}
else mistake=0;
}
Head =(SLNODE *)malloc(sizeof(SLNODE));
Head->next = NULL;
Head = CREATE_SL(Head,n);
ShowInput(Head,n);
printf(“正确的出列顺序为:rn”);
ShowOutput(Head,m);
PrintInformation2();//程序结束信息
system(“pause”);
return 0;
}
五、调试分析与核心算法解释
程序的调试主要是针对循环链表，所以调试对象明确，按照算法思路来调试，难度不大。
本题在建立好链表以后，开始执行核心程序ShowOutput递归函数，也就是想办法按照约瑟夫斯问题的规则来删除指针指向的结点、移动指针等，从而以一定排列输出n个人的密码。程序刚开始，先由用户依次输入人数n和初始报数上限m，并判断是否m<=n，如果m>n，则显示重新输入（程序并不会结束）。
然后程序建立头指针Head并且执行CREATE_SL函数，创建链表。
执行ShowInput函数，将n个人的密码依次输出。
下面开始执行本程序的关键函数，也是整个算法的核心函数ShowOutput，这也是整个算法的体现：
函数整体是个递归函数，运用递归的思想，效率很高，占用内存小，不需要设置标志位来判断是否某个结点被访问，而是访问到一个应该出列的结点“出列”，然后以此结点为下一次递归的头结点，然后删除本次递归程序充当头结点的那个结点。
图解：
h，p，s均为指向节点的指针，第一次执行此函数时，h指向头结点。
p指针寻找到要“出列”的节点，h指向要出列的结点作为下一次递归的新的头结点。
利用p指针和s指针重新改造循环链表,然后s指针用于记录本次递归的头结点位置，即将用于删除、释放空间。
下面执行free(s),删除所指内存空间，开始下一次递归调用。
后面执行递归函数时，h刚开始指向的是上一次输出的结点（还没删除），程序一开始先让s指向h，等这一趟程序快结束找到下一个要出列的结点时，h指向该结点作为下一次递归函数的头结点，并且让p找到s指向的充当本次头结点的结点，把它删除，再执行此递归程序。
终止条件是p->next=h，说明没有需要输出的节点了，于是便实现了递归。如图所示：
截图如图：
六、使用说明
按照程序界面指示输入即可，逐个整数数字输入，每输入一个数字按一个回车。
七、调试结果
按照测试要求进行了测试，结果如下：
八、遇到的问题及解决方法（程序调试日志）
202_/9/不详
问题：先建立了一个链表实现插入算法的小功能，再进行约瑟夫问题求解，结果程序不停的输出不完整的数据，陷入死循环。
解决：p指针所指空间逻辑上不该释放但被不正确释放，删去free(p)代码，一切正常。
202_/9/不详
问题：递归程序死循环。
解决：单步执行发现递归的终止条件不正确，修改为p->next=h，程序功能实现！
202_/10/20
最后一天，完善程序，将程序中的注释写清楚，百度找到了显示系统时间的方法，按格式输出，截屏、书写报告。
九、实验的收获与感想
个人感想：循环链表虽然不是很容易理解，但是处理约瑟夫斯这样的删除元素的操作真的十分便利，比起数组要方便的多。但是代价是编程要仔细，不要释放错内存空间。
个人方法优点：
1、建立链表时，将头结点和头指针同时运用，使头指针一开始指向头结点，这样操作方便，同时个人的算法要利用s删除上一次h指向的头结点，所以一开始让头指针指向一个头结点对于个人的算法是有一定好处的。
2、本人采用递归的算法，每次找到要出列的点后，先不马上删除结点，而是将h指针指向此结点作为下一次递归的h结点，等下一次递归找到新的出列结点并用h指向来作为头结点后，再将废弃结点删除，这样“改变头结点”，操作简便，很适合递归的条件。
个人方法缺点：本人认为此程序缺点是陌生人刚看到此程序不能马上理解，因为递归程序本身不易理解。所以为了更好给别人使用，本人已将程序注释的很清楚了。
建议：本实验很好，建议像第四题那样，增加一项计算程序空间复杂度和时间复杂度（移动次数）的要求，组织同学进行讨论，展示最优的算法。
十、源程序
见源程序清单。
实验二、停车场管理问题
一、问题描述
1）问题描述
设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n 辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离
开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再
按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳
费用。试为停车场编制按上述要求进行管理的模拟程序。
2）基本要求
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管
理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序
结构实现，队列以链表结构实现。
3）测试数据
设 n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示 1 号牌照车在 5 这个时刻到达，而（‘D’，1，15）表示 1 号牌照车在 15 这个时刻离去。
4）提示
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据
按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号 码和进入停车场的时刻。
5）输入输出:
输入数据：
程序接受 5 个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时 间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。
输出数据：
对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆 离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。
二、需求分析
1、本程序用来模拟停车场进场、进便道、场外等候、出场、收费等操作。
2、程序运行后显示提示信息，提示用户输入停车每小时需缴纳的费用，用户输入后，提示信息提示用户输入命令：驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0。
3、程序需判断用户输入的进场出场时间的有效性，后来输入的时间要大于以前输入的时间。
4、用户输入有效命令后，程序显示汽车进出场信息，若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用。
三、概要设计
为了实现上述功能，需要用栈模拟停车场，用一个备用的栈存储暂时出场的外部汽车，用队列模拟便道。
1、停车场“栈”抽象数据类型定义：
ADT stack{
数据对象：车牌号、进场时间、汽车数量
数据关系：先入后出
基本操作：
*Init_Parking();//置空栈
IsEmpty_Parking(Parking *s);//判空栈
Push_Parking(Parking *s,ElemType license,ElemType timeIn);//入栈
Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn);//出栈
}ADT stack
2、备用存储“栈”抽象数据类型定义：
ADT stack1
{
数据对象：车牌号、进场时间、汽车数量
数据关系：先入后出
基本操作：
*Init_Backup();//置空栈
IsEmpty_Backup(Backup *s);//判空栈
Push_Backup(Backup *s, ElemType license, ElemType timeIn);//入栈
Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn);//出栈
}
3、链式队列抽象数据类型定义：
ADT linkqueue
{
数据对象：车牌号、汽车数量
数据关系：先入先出
基本操作：
*Init_LQueue();//创建一个带头结点的空队
In_LQueue(LinkQueue *q, ElemType license);//入队
IsEmpty_LQueue(LinkQueue *q);//判队空
Out_LQueue(LinkQueue *q, ElemType *license);//出队
}
4、本程序保护模块
主函数模块
进场模块：对于进场的命令进行完善地操作处理并进行状态显示的模块
出场模块：对于出场的命令进行完善地操作处理并进行状态显示的模块
置空栈、置空队、进出栈、进出队、判栈空栈满、判队空队满模块：对栈、备用栈、队列进行的基本操作
调用关系：
5、算法流程图
四、详细设计
1、元素类型、结点类型和结点指针类型：
#define Maxsize 2 //停车场最多能停的车数
#define ElemType int
int Prize;//每停一个时刻收费多少元
static int num = 0;//num用于记录入队的车所在的位置
typedef struct stack //模拟停车场的栈
{
ElemType license[Maxsize];//用于存放车牌号
ElemType timeIn[Maxsize];//用于存放入停车场时间
int top;
}Parking;
typedef struct stack1 //退车时暂时存放
{
ElemType license[Maxsize-1];
ElemType timeIn[Maxsize-1];
int top;
}Backup;
typedef struct road
{
ElemType license;
struct road *next;
}Road;
typedef struct linkqueue//队列模拟便道
{
Road *front,*rear;
}LinkQueue;
2、部分基本操作的伪码类型
//给停车场用的配置函数
Parking *Init_Parking()//置空栈
{
Parking *s;
s=(Parking*)malloc(sizeof(Parking));
s->top=-1;
return s;
}
int IsEmpty_Parking(Parking *s)//判空栈
{
if(s->top==-1)
return 1;
else return 0;
}
int Push_Parking(Parking *s,ElemType license,ElemType timeIn)//入栈
{
if(s->top==Maxsize-1)
return 0;
else
{
s->top++;
s->license[s->top]=license;
s->timeIn[s->top]=timeIn;
return 1;
}
}
int Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn)//出栈
{
if(IsEmpty_Parking(s))
return 0;
else
{
*license = s->license[s->top];
*timeIn = s->timeIn[s->top];
s->top--;
return 1;
}
}
//给备用栈配置的函数
Backup *Init_Backup()//置空栈
{
Backup *s;
s =(Backup*)malloc(sizeof(Backup));
s->top =-1;
return s;
}
int IsEmpty_Backup(Backup *s)//判空栈
{
if(s->top ==-1)
return 1;
else return 0;
}
int Push_Backup(Backup *s, ElemType license, ElemType timeIn)//入栈
{
if(s->top == Maxsize-1)
return 0;
else
{
s->top++;
s->license[s->top] = license;
s->timeIn[s->top] = timeIn;
return 1;
}
}
int Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn)//出栈
{
if(IsEmpty_Backup(s))
return 0;
else
{
*license = s->license[s->top];
*timeIn = s->timeIn[s->top];
s->top--;
return 1;
}
}
//给候车便道链式队列配置的函数
LinkQueue *Init_LQueue()//创建一个带头结点的空队
{
LinkQueue *q;
Road *p;
q =(LinkQueue*)malloc(sizeof(LinkQueue));
p =(Road*)malloc(sizeof(Road));
p->next = NULL;
q->front = q->rear = p;
return q;
}
void In_LQueue(LinkQueue *q, ElemType license)//入队
{
Road *p;
p =(Road*)malloc(sizeof(Road));
p->license = license;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
int IsEmpty_LQueue(LinkQueue *q)//判队空
{
if(q->front == q->rear)
return 1;
else
return 0;
}
int Out_LQueue(LinkQueue *q, ElemType *license)//出队
{
Road *p;
if(IsEmpty_LQueue(q))
{
printf(”队空“);
return 0;
}
else
{
p = q->front->next;
q->front->next = p->next;
*license = p->license;
free(p);
if(q->front->next == NULL)
q->rear = q->front;
return 1;
}
}
3、主函数的伪码
void main()
{
ElemType license, time,timelast=0;//timeInlast是最近一次有车进停车场的时间，提示以后输入的进场时间要大于此数值
char command;//进入A还是离开D
Parking *s;
Backup *s1;
LinkQueue *q;
PrintInformation1();//输出程序信息和个人信息
s = Init_Parking();//停车场
q = Init_LQueue();//便道队列
s1 = Init_Backup();//退车时的备用栈
printf(”请输入停车每小时需交纳的费用（元）rn“);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
scanf(”%d“,&Prize);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
while(1)
{
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
Loop:printf(”请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:n“);
scanf(”%c%d%d“,&command, &license,&time);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
if(command == A)
{
if(time <= timelast)
{
printf(”输入的时间必须大于上一次输入的时间:t“);
printf(”%dt“, timelast);
printf(”请重新输入n“);
goto Loop;
}
else
{
timelast = time;
GetIn(s,q,license,time);
}
}
if(command == D)
{
if(time <= timelast)
{
printf(”输入的时间必须大于上一次输入的时间:t“);
printf(”%dt“, timelast);
printf(”请重新输入n“);
goto Loop;
}
else
{
timelast = time;
GetOut(s, s1, q, license, time);//车开走的函数
}
}
if(command == P)
{
if(license == 0 && time == 0)
printf(”停车场内停了%d辆车n“,s->top+1);//显示停车场车数
}
if(command == W)
{
if(license == 0 && time == 0)
printf(”侯车场内停了%d辆车n“,num);//显示候车场车数
}
if(command == E)
{
if(license == 0 && time == 0)
{
PrintInformation2();//程序结束信息
system(”pause“);
return;
}
}
}
}
五、调试分析与核心算法解释
程序本身是利用栈、队列的进出完成停车场汽车进出场的模拟的，只要按照模块化的函数，按照基本的逻辑编写，调试是比较容易的。
程序一开始会要求用户输入每小时缴纳多少元费用，显示“请输入停车每小时需交纳的费用（元）”。
以栈模拟停车场，以队列模拟车场外的便道，在while循环开始让用户输入命令、车牌号、时间三个变量，对三个变量进行判断，并执行相应函数。
程序显示“请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:”
如果后来输入的时间比之前输入的时间小，程序会提示“输入的时间必须大于上一次输入的时间: xx 请重新输入”。
其中驶入函数先判断是否栈满，如果栈满则执行入队操作，否则入栈，并将车牌号、驶入时间存入栈元素数组，top值加一，用于记录车的数量，用于判断是否栈满。
如果栈不满，程序显示“车牌号为xx的汽车在xx时刻停在xx车位”。
如果栈满，程序显示“xx号车停在候车便道的第xx个位置”。
离开函数先判断是否栈空，如果栈空则输出没有车辆提示，否则进一步比较是否有栈内车牌号元素与命令的离开的车牌号一致，有则出栈，计算停车时间和计价，无则输出没有此车牌号的车的提示。
如果没有命令的车牌号的汽车，则显示“对不起！停车场内没有车牌号为xx的车”。
如果停车场已空，会显示“对不起！停车场已空！”。
如果原先栈满，离开一辆车以后，最早到便道上的一辆车进栈，并显示“xx号汽车此时退出便道，进入停车场最后一个位置”。
队列和栈的top记录了车的数量，可用于输出内部车数，也可用于判断是否栈满。
如果三个变量分别为P,0,0，则输出停车场内车的个数。
如果三个变量分别为E,0,0，则输出便道上车的个数。
如果三个变量分别为E ,0, 0,则结束程序。
六、使用说明
程序接受 5 个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时 间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。
注意：命令字符（A D P W E）用大写，输入的三个数据之间用空格隔开。如A 1 5。代表1号1号汽车在5时刻进场。
七、调试结果
按照测试要求给的数据进行了测试：
八、遇到的问题和解决方法（程序调试日志）
202_/9/不详
问题：程序全部结束，执行时能基本完成功能，但是总是会间隔有一次命令无效，重复输出“请输入命令.......”。
解决方法：后来百度发现，这是因为数据缓存区没有清除的缘故，每次回车都会在数据缓存区遗留下来一个Enter字符，可被char型变量读取，因此在每次输入数据前后加入一个清除数据缓存区的函数setbuf(stdin, NULL)即可解决问题。
202_/10/20
最后一天，完善程序，将程序中的注释写清楚，百度找到了显示系统时间的方法，按格式输出，截屏、书写报告。
九、实验的收获与感想
个人感想：
这道题目和后面的第四道题目都是属于比较透彻的题目，先做了第二题，还是对第二题印象最深，首先这道题很讲究编程的条理性，里面的初始化栈、判栈空、栈满、入栈、出栈以及初始化队列、判队空、队满、入队、出队等函数在书上都有，主要的工作是利用模块化的思想，由整体到局部逐渐求精地去写整个程序，从而把整个停车场的5个命令功能给实现，感觉收获很多，模块化的思想很厉害！
方法的优点：
整体程序思路比较简单，因此个人没有什么更优算法，只是在这里面有一个逻辑，就是后面输入的时间不能比之前输入的时间小，因为这不符合日常逻辑，同时也影响了入栈出栈次序，因此我程序里使用了不常用的goto函数，一般这个函数是不建议用的，它会跳转程序，但是在这里判断后面输入的时间大于之前输入的时间后，goto函数可以让程序跳转到while循环开始的地方，让用户重新输入命令，这里感觉很方便！
建议：
希望多多布置这样的习题，有助于教会学生利用模块化思想，不过希望布置的题目可以是多方向的比如有关界面制作的题目，把模块化的函数给大家，大家进行使用，根据自己爱好设计出相应的模块化功能的程序。
十、源程序
见源程序清单。
实验三、管道铺设施工的最佳方案问题
一、问题描述
1）问题描述
需要在某个城市 n 个居民小区之间铺设煤气管道，则在这 n 个居民小区之间只需要铺设 n-1 条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2）基本要求
在可能假设的 m 条管道中，选取 n-1 条管道，使得既能连通 n 个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3）测试数据
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。
以上是本实验的题目要求，下面我将介绍我的实现算法，程序调试结果以及编程过程中遇到的具体问题，并且谈谈我的收获和感悟！
二、需求分析
1、此程序用来求无向带权网的最小生成树。
2、程序的输入数据放在一个dat格式的文件中，想要修改输入数据，用记事本打开文件直接修改即可。任何时刻想看到结果，点击一下exe文件即可一键解决。
3、输入数据的形式是一个矩阵形式，行和列的元素依次代表A、B、C....，两点之间有边，则数据是一个不为0的数，否则为0。
4、程序运行结果不仅会在控制台显示出来，同时还要在一个新的文件中显示出来，点击一下exe文件即可一键解决，满足用户“即点即看”，输出文件令用户能“随时且长久”看到结果，不必每一次都要运行程序。
三、概要设计
为实现上述功能，应以图的邻接表数据结构，即链表与数组相结合的数据结构。
1、邻接表抽象数据类型定义：
ADT ALGraph{
数据对象：结点A、B、C....数据关系：存储结构上链表式指针相连，物理结构上点之间相连成边
基本操作：CreateALGraph(ALGraph *G);//建立无向图的邻接表存储
}ADT ALGraph
2、文件操作模块
基本操作：
read_data(void);//只读方式打开文件
read_array(double *array,int n1,int n2,FILE *fp);//读取文件中的边值信息
cout_data(void);//只写方式打开或建立文件
cout_array(double *array,int n1,int n2,FILE *fp);//向文件中写入边值信息
3、本程序保护模块
主程序模块
建立无向图模块：根据读入文件的边值信息创建无向图邻接表存储
最小生成树模块：由无向图生成最小生成树
读入数据模块：只读方式读取文件数据
输出结果模块：将结果输出到控制台
输出到文件模块：将结果输出到文件
调用关系：
四、详细设计
需要建立一个无向图的邻接表存储结构，进行最小生成树的提取。
1、元素类型、结点类型和结点指针类型：
#define MaxVertexNum 100 //设置小区数最多为100
#define VertexNum 9
double LeastNum;//用于记录最短边长度
double LongestNum;//用于记录最长边长度，程序过程中不改变
double adjacent[VertexNum][VertexNum];
//邻接矩阵，不用于处理数据，而是用于暂时存储从文件读来的数据
//进而在邻接表存储数据时读取此数组数据即可
//二维数组数据为0的元素说明之间没有通道
//在处理完数据后，此数组会用来暂时存储处理后的数据，并写入到另一个文件中
typedef struct vnode
{//顶点表结点
char vertex;
EdgeNode *firstedge;
}VertexNode;
typedef struct
{
VertexNode adjlist[MaxVertexNum];
int n,e;
}ALGraph;
2、有序表类型：
typedef struct node
{//边表结点
char adjvex;
double weight;//权值
struct node *next;
}EdgeNode;
3、主函数的伪码：
void main()
{
ALGraph *G;
PrintInformation1();
G =(ALGraph*)malloc(sizeof(ALGraph));
G->n = VertexNum;//为G指向的图分配空间，设置点数（小区数）
read_data();
CreateALGraph(G);
MinimumSpanningTree(G);
cout_data();//输出到文件
ResultOutput((double *)adjacent,VertexNum,VertexNum);//输出到控制台
PrintInformation2();
system(”pause“);
}
4、算法流程图
五、调试分析与核心算法解释
此题按照Prim算法，设置一个用于存储点的点集，找短边从一个点向两点、三个....更多逐渐扩张，即可得到最小生成树。
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边
b.将v加入集合Vnew中，将
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
具体可以参考资料：https://baike.baidu.com/redirect/cb1fkztQc2TOscNlcMemKsGZ1fsgTprJsdBq_APeZx74W4q4TzbKXHsvSYW_6aM1DqhF56eTgD8EZLzBCQHKBGa6ExWmgXbju_gm13Qbbu0KxbHuiIS_DxEp2fgT3BU
六、使用说明
输入数据已经在”gyp_program3_Input.dat“中写好，如果想做修改可以在该文件中修改即可，输出的数据既在控制台显示，也会输出到”gyp_program3_Output.dat“。
七、调试结果
输入数据文件：
这是一个矩阵，例如：第2行，第3列代表B，C两点间的边，0代表无边，不为0代表有边。
控制台程序显示：
输出数据到输出文件
八、遇到的问题和解决方法（程序调试日志）
202_/9/不详
问题：一进入建立无向图的函数程序就中止出错。
解决方法：给建立无向图函数传递的形参是指针，而在主函数中G指针没有赋给内存空间，所以函数无法对G所指的空间进行初始化，在主程序中加入这样一句代码就好了：
G =(ALGraph*)malloc(sizeof(ALGraph));
202_/10/17
问题：输出的二维数组只有一位正常，其余全是0。如下图所示：
解决方法：后来发现是里面flag2这个标志位刚开始是1，程序执行过程中被置0用于判断，但是判断以后没有再次重置为1，导致要用很多次的标志位只发挥了一次作用，后面就误判了，在循环结束加入重置1的语句即可。
问题：输出的二维数组输出数据不完整，里面总有最小的边（问题切入点）。
解决方法：单步执行后发现，某一次循环中Leastnum这个变量得到的最小值恰好是所有边中最小的一个，它在发挥完比较作用后，没有被置为一个很大的数（不小于这些边中最大值即可），结果在下一次循环的时候，导致后面的边都比它大，以至于后面的边都被舍去了，解决方法就是每次循环第一句先把原图的最大边赋给leastnum。
问题：直接运行debug文件夹里的exe程序，且debug程序终止，怀疑是文件数据读取失败，无法打开文件，即文件不存在。
解决方法：如果不详细说明文件路径，程序本身会在当前文件夹内找文件，存数据的文件gyp_program3_Input.dat要保存在当前文件中。也就是和源代码在同一个文件夹中，但是这样子的话，只有用编程软件打开代码运行，dat文件才有效，若想在debug里直接运行exe程序，则把存数据的输入文件同名复制到debug文件夹里即可。
九、实验的收获和感想
个人感想：这个程序可以说是算法感十足了，也是我遇到问题最大的一个程序，但是也证明了自己的能力，学到了很多，收获最大的就是：对于用的不止一次的标志位，一定不可能只单方向置位，一定是双向置位，一次循环结束一定要记得置位，否则用了这一次以后，后面的循环就会误判！
Prim算法真的很好用，不仅适合求带球图的最小生成树，还适合寻找一个点到另一点的最短路径。
个人方法优点：输入方便，输出简洁。读取文件中的数据，不用手动输入，想修改数据在文件中修改就可以，另外输出有两种形式，一种是控制台输出，一种是输出到文件，输出的是一个二维数组，行和列都有表头，看起来很清晰，两个点之间若有边，相应二维坐标的元素就是边值，无边则相应的位置为0。
建议：可以要求用顺序表的方法，因为从理解和编程难度角度考虑，图的邻接表找边会很慢每次都要顺着其中一个链表头结点去寻找，不过这也很锻炼人的能力！
十、源程序
见源程序清单。
实验四、内部排序算法的实现与比较
一、问题描述
1）问题描述
在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
2）基本要求
(1)对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序。
(2)利用随机函数产生N（如30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
(3)对结果作出简要分析。
3）测试数据
随机函数产生。
4）提示
主要工作是设法在已知算法中适当位置插入对关键字的比较次数和移动次数的计数操 作。注意采用分块调试的方法。
5）输入输出:
输入数据：参加排序的整数个数 n（如 n=30000）；
输出数据：各种排序方法的关键字比较次数和移动次数（从小到大排列）。
二、需求分析
1、本程序用来比较5种排序的关键字比较次数和关键字移动次数。
2、本程序用srand()和rand()函数产生N个随机数用于排序方法的比较，用户无需输入。
3、运行程序后，程序需按从小到大的顺序分别输出5种排序的关键字比较次数和移动次数。
三、概要设计
为实现上述功能，程序需要产生N个随机数，并且需要写出这5种排序的排序函数。
1、产生N个随机数的方法
srand((unsigned)(time(NULL)));
for(int j = 0;j < N;j++)
{
num0[j] = rand();
}
2、保证每次排序的数据都相同的方法
num0数组用于得到随机数，num数组每次排序前先用num0数组赋值即可。
for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N);3、5种排序函数 void InsertSort(int R[], int n);//插入排序 void SelectSort(int R[], int n);//选择排序 void BubbleSort(int R[], int n);//冒泡排序 void QuickSort(int R[],int low,int high);//快速排序 void ShellInsert(int R[],int m,int n);//快速排序 void Shellsort(int R[],int n);//希尔排序 4、本程序保护模块 主程序模块 排序模块 比较输出模块 调用关系： 4、算法流程图 四、详细设计 1、排序函数基本操作的伪码实现 void InsertSort(int R[], int n)//插入排序 { int i, j; for(i = 2;i <= n;i++) { R[0] = R[i]; MoveNum[0]++; j = i-1; while(R[0] < R[j]) { KeyCompareNum[0]++; R[j + 1] = R[j]; MoveNum[0]++; j--; } R[j + 1] = R[0]; MoveNum[0]++; } } void SelectSort(int R[], int n)//选择排序 { int i, j, k; for(i = 1;i < n;i++) { k = i; for(j = i + 1;j <= n;j++) if(R[j] < R[k]) { k = j; KeyCompareNum[1]++; } if(k!= i) { R[0] = R[k]; R[k] = R[i]; R[i] = R[0]; MoveNum[1]+=3; } } } void BubbleSort(int R[], int n)//冒泡排序 { int i, j, flag = 0; for(i = 1;(i < n && flag == 0);i++) { flag = 1; for(j=1;j if(R[j + 1] < R[j]) { KeyCompareNum[2]++; flag = 0; R[0] = R[j]; R[j] = R[j+1]; R[j + 1] = R[0]; MoveNum[2]+=3; } } } void QuickSort(int R[],int low,int high)//快速排序 { int i,j; i=low; j=high; R[0]=R[i]; MoveNum[3]++; while(i { while((R[j]>=R[0])&&(j>i)) { j--; KeyCompareNum[3]++; } if(j>i) { R[i]=R[j]; MoveNum[3]++; i++; } while((R[i]<=r[0])&&(j>i)) { i++; KeyCompareNum[3]++; } if(j>i) { R[j]=R[i]; MoveNum[3]++; j--; } } R[i]=R[0]; MoveNum[3]++; if(low QuickSort(R,low,i-1); if(i QuickSort(R,j+1,high); } void ShellInsert(int R[],int m,int n) {//一趟希尔排序，按间隔m划分子序列 int temp,j; for(int i=m;i { temp=R[i]; MoveNum[4]++; j=i; while(j>=m && temp { KeyCompareNum[4]++; R[j]=R[j-m]; MoveNum[4]++; j-=m; } R[j]=temp; MoveNum[4]++; } } void Shellsort(int R[],int n)//希尔排序 { int m; m=n/2; while(m>=1) { ShellInsert(R,m,n); m=(m==2?1:(m/2)); } } 2、主函数伪码实现 int main() { //数组设为N+1个是因为有些算法是从数组1到N存储的，0位有的不用，有的用作了哨兵 int num0[N+1];//记录最原先随机产生的N个数字，因为num[N]每排序一次都会改变 int num[N+1];//每次排序前先读入num0[N]数据 //srand函数只增加一次就够了，用系统当前时间设置rand()随机序列种子，保证每次运行随机序列不一样 srand((unsigned)(time(NULL))); for(int j = 0;j < N;j++) { num0[j] = rand(); } PrintInformation1(); for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } SelectSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } BubbleSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } Shellsort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } QuickSort(num,0,N-1); printf(”关键字比较次数按从小到大排列分别是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移动次数按从小到大排列分别是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } 五、调试分析与核心算法解释 程序的5种排序函数可以自己写，也可以百度找源码，总之五种排序函数写完以后，调试的关键是设置计数变量，并在这些函数的合适位置进行加1计数或加3计数，因此注意分块调试，分函数调试，做到这几点调试难度总体不大。 六、使用说明 随机数产生，5种排序用的都是同一组N个随机数，用户无需输入，直接运行程序即可输出运算结果。 七、调试结果 八、遇到的问题和解决方法（程序调试日志） 202_/10/19 问题：第一种排序输出很大，后面输出很小，几乎没作用。 解决方法：每经过一个排序函数，数组已经排好序了，不能直接调用其余的排序函数，而是要在程序一开始就用另一个数组num0[N]记录了随机数产生的数组num[N]，因此只需要在每次排序前，把num0数组中数据重新赋给num数据即可参与排序了。 问题：数据输出个数少于5个，单步执行发现循环不到5次。 解决方案：分析后发现，程序的几个for循环，内层的循环里面的计数加1变量如i，j，和外层循环设置的加1变量用的是一个变量，导致内层循环计数变量的改变会影响外层循环，导致输出个数小于5。将这些变量设置成不同变量就不影响了（相互独立的循环可能不会影响，但内外层关系的两个循环绝对不能用同一个计数变量）。 问题：程序末尾会跳出一个程序中止警告框，说是栈释放的问题。 解决方案：百度发现，这实际上是数组越界的问题，把数组个数设置为N+1大小的，就好了。 九、实验的收获和感想 个人感想：这个程序难度不大，关键在于在合适的位置插入用于记录的变量+1或者+3,真正有技术含量的在于按照从小到大的顺序输出相应数据。收获比较大的一个技巧：相互独立的循环计数变量可能不会影响，但内外层关系的两个循环绝对不能用同一个计数变量，否则程序循环次数就会乱！ 从关键字比较次数和移动次数来看，选择和快速排序都是非常高效的，希尔排序也不错，不要用或少用冒泡排序和直接插入排序。 个人方法的优点：只产生了1次随机数，5次排序的用的都是同一组数据，可以更好地更严谨地比较出这5种算法的优劣。 个人方法的缺点：因为要“长久”保留产生的随机数，因此需多设置一个数组，占用内存空间比较大。 十、源程序 源程序见源程序清单。 参考资料 https://blog.csdn.net/guanyasu/article/details/53153705 https://jingyan.baidu.com/article/49711c616b8a1ffa441b7cdc.html https://zhidao.baidu.com/question/***684.html 源程序清单 实验一、约瑟夫斯问题求解 #include #include #include #define ElemType int #define SLNODE struct sl_node SLNODE { ElemType data[2]; SLNODE *next; }; SLNODE *CREATE_SL(SLNODE*,int); void ShowInput(SLNODE*h,int n);//每个人的密码输入 void ShowOutput(SLNODE*,int);//排列输出 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime();//输出时间 int main() { int m,n,mistake=1; SLNODE *Head; PrintInformation1();//输出程序信息和个人信息 while(mistake) { printf(”输入人数n:n“); scanf_s(”%d“, &n); printf(”请指定初始报数上限m(m应必须小于等于n):n“); scanf_s(”%d“, &m); if(m>n) { printf(”输入数据有误，请重新输入n“); } else mistake=0; } Head =(SLNODE *)malloc(sizeof(SLNODE)); Head->next = NULL; Head = CREATE_SL(Head,n); ShowInput(Head,n); printf(”正确的出列顺序为:rn“); ShowOutput(Head,m); PrintInformation2();//程序结束信息 system(”pause“); return 0; } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验一.约瑟夫斯问题求解rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } SLNODE *CREATE_SL(SLNODE *h,int n) //创建一个h为头指针的链表，h指向的结点数据域用不到 { ElemType data; int i = 1; SLNODE *p, *s; p = h; while(i<=n) { printf(”请输入第%d个元素:t“,i); scanf_s(”%d“, &data); s =(SLNODE *)malloc(sizeof(SLNODE)); s->data[0]=i; s->data[1] = data; if(h->next == NULL) { h->next = s; } else { p->next = s; } p = s; i++; } p->next = h; return h; } void ShowInput(SLNODE *h,int n) { SLNODE *p; p = h; printf(”%d“,n); printf(”个人的密码依次为:“); while((p->next)!= h) { p = p->next; printf(”%dt“, p->data[1]); } printf(”n“); } void ShowOutput(SLNODE *h, int m) { SLNODE *p, *s;//s用于记录上一个节点，从而使p结点找到它将其删除 int j = 0; s = h;//第一次执行此函数时，h指向头结点；后面递归执行时，h刚开始指向的是上一//次输出的结点（还没删除） //都用s来记录，等那一趟程序快结束找到下一个要出列的的点时，h指向那个结点作为头结点，并且让p找到s指向的 //上一个结点，把它删除。 p = h; while(j < m-1) { p = p->next; if(p->next==h)//不能让h所指向的结点（上一次输出的结点，暂时用作头结点所以//还未删除）影响小循环次数 { p=p->next;//所以此处让p多移动一下，等下一次小循环让p顺利移动到下一//个节点（从而忽略掉h指向的结点） } //等找到下一个该出列的结点时，h指向那个结点（充当下一次的头节点），充当上一次头//结点的结点利用s删除 j++; }//此时p指向第m-1个结点 if(p->next == h)//整个程序的终止条件，依次回到上个函数结尾，相当于全部结束了 { return; } h= p->next; p = h;//此时h和p均指向要出列的结点 printf(”%dt“, h->data[0]); j = 0;//j用于while循环，使h指针指向要出列的点的前一个结点，所以及时清零 while(p->next!=s)//找s废弃节点 { p = p->next; } s = p->next; p->next = s->next;//连接新结点 free(s);//释放s所指空间 ShowOutput(h,h->data[1]); } 实验二、停车场管理问题 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define Maxsize 2 //停车场最多能停的车数 #define ElemType int int Prize;//每停一个时刻收费多少元 static int num = 0;//num用于记录入队的车所在的位置 typedef struct stack //模拟停车场的栈 { ElemType license[Maxsize];//用于存放车牌号 ElemType timeIn[Maxsize];//用于存放入停车场时间 int top; }Parking; typedef struct stack1 //退车时暂时存放 { ElemType license[Maxsize-1]; ElemType timeIn[Maxsize-1]; int top; }Backup; typedef struct road { ElemType license; struct road *next; }Road; typedef struct linkqueue//队列模拟便道 { Road *front,*rear; }LinkQueue; void GetIn(Parking *s, LinkQueue *q, ElemType license, ElemType timeIn);//有车进来 void GetOut(Parking *s, Backup *s1, LinkQueue *q, ElemType license, ElemType timeOut);//有车//出去 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验二.停车场管理问题rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } //给停车场用的配置函数 Parking *Init_Parking()//置空栈 { Parking *s; s=(Parking*)malloc(sizeof(Parking)); s->top=-1; return s; } int IsEmpty_Parking(Parking *s)//判空栈 { if(s->top==-1) return 1; else return 0; } int Push_Parking(Parking *s,ElemType license,ElemType timeIn)//入栈 { if(s->top==Maxsize-1) return 0; else { s->top++; s->license[s->top]=license; s->timeIn[s->top]=timeIn; return 1; } } int Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn)//出栈 { if(IsEmpty_Parking(s)) return 0; else { *license = s->license[s->top]; *timeIn = s->timeIn[s->top]; s->top--; return 1; } } //给备用栈配置的函数 Backup *Init_Backup()//置空栈 { Backup *s; s =(Backup*)malloc(sizeof(Backup)); s->top =-1; return s; } int IsEmpty_Backup(Backup *s)//判空栈 { if(s->top ==-1) return 1; else return 0; } int Push_Backup(Backup *s, ElemType license, ElemType timeIn)//入栈 { if(s->top == Maxsize-1) return 0; else { s->top++; s->license[s->top] = license; s->timeIn[s->top] = timeIn; return 1; } } int Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn)//出栈 { if(IsEmpty_Backup(s)) return 0; else { *license = s->license[s->top]; *timeIn = s->timeIn[s->top]; s->top--; return 1; } } //给候车便道链式队列配置的函数 LinkQueue *Init_LQueue()//创建一个带头结点的空队 { LinkQueue *q; Road *p; q =(LinkQueue*)malloc(sizeof(LinkQueue)); p =(Road*)malloc(sizeof(Road)); p->next = NULL; q->front = q->rear = p; return q; } void In_LQueue(LinkQueue *q, ElemType license)//入队 { Road *p; p =(Road*)malloc(sizeof(Road)); p->license = license; p->next = NULL; q->rear->next = p; q->rear = p; } int IsEmpty_LQueue(LinkQueue *q)//判队空 { if(q->front == q->rear) return 1; else return 0; } int Out_LQueue(LinkQueue *q, ElemType *license)//出队 { Road *p; if(IsEmpty_LQueue(q)) { printf(”队空“); return 0; } else { p = q->front->next; q->front->next = p->next; *license = p->license; free(p); if(q->front->next == NULL) q->rear = q->front; return 1; } } void main() { ElemType license, time,timelast=0; //timeInlast是最近一次有车进停车场的时间，提示以后输入的进场时间要大于此数值 char command;//进入A还是离开D Parking *s; Backup *s1; LinkQueue *q; PrintInformation1();//输出程序信息和个人信息 s = Init_Parking();//停车场 q = Init_LQueue();//便道队列 s1 = Init_Backup();//退车时的备用栈 printf(”请输入停车每小时需交纳的费用（元）rn“); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 scanf(”%d“,&Prize); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 while(1) { setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 Loop:printf(”请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:n“); scanf(”%c%d%d“,&command, &license,&time); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 if(command == A) { if(time <= timelast) { printf(”输入的时间必须大于上一次输入的时间:t“); printf(”%dt“, timelast); printf(”请重新输入n“); goto Loop; } else { timelast = time; GetIn(s,q,license,time); } } if(command == D) { if(time <= timelast) { printf(”输入的时间必须大于上一次输入的时间:t“); printf(”%dt“, timelast); printf(”请重新输入n“); goto Loop; } else { timelast = time; GetOut(s, s1, q, license, time);//车开走的函数 } } if(command == P) { if(license == 0 && time == 0) printf(”停车场内停了%d辆车n“,s->top+1);//显示停车场车数 } if(command == W) { if(license == 0 && time == 0) printf(”侯车场内停了%d辆车n“,num);//显示候车场车数 } if(command == E) { if(license == 0 && time == 0) { PrintInformation2();//程序结束信息 system(”pause“); return; } } } } //停车函数 void GetIn(Parking *s, LinkQueue *q,ElemType license, ElemType timeIn) { if(Push_Parking(s, license, timeIn)== 1)//说明成功进入停车场 { printf(”%d号车在%d时刻停在停车场第%d个位置nn“,license,timeIn,s->top+1); } else //栈满，汽车要进入便道，即入队 { num++; In_LQueue(q,license); printf(”%d号车停在候车便道的第%d个位置nn“,license,num); } } void GetOut(Parking *s, Backup *s1,LinkQueue *q, ElemType license, ElemType timeOut) { ElemType *licen, *tim;//两个指针赋给出栈函数，用于读取车牌号和进停车场时间 ElemType ParkTime;//汽车在停车场停留的时间 ElemType Money;//汽车应缴金额 licen =(ElemType*)malloc(sizeof(ElemType)); tim=(ElemType*)malloc(sizeof(ElemType)); if(IsEmpty_Parking(s))//先判断停车场内是否有车 { printf(”对不起！停车场已空！nn“); return; } while(s->license[s->top]!= license) { Pop_Parking(s,licen,tim); Push_Backup(s1, *licen, *tim); if(IsEmpty_Parking(s)==1) { printf(”对不起！停车场内没有车牌号为%d的车nn“,license); while(IsEmpty_Backup(s1)!= 1) { Pop_Backup(s1, licen, tim); Push_Parking(s, *licen, *tim); } return; } } if(s->license[s->top] == license) { ParkTime = timeOut-s->timeIn[s->top]; Money = ParkTime * Prize; printf(”汽车在停车场内停留的时间为%d小时,应缴费%d元nn“,ParkTime,Money); Pop_Parking(s, licen, tim); while(IsEmpty_Backup(s1)!= 1) { Pop_Backup(s1,licen,tim); Push_Parking(s,*licen,*tim); } if(IsEmpty_LQueue(q)!= 1) { Out_LQueue(q,licen); Push_Parking(s,*licen,timeOut); printf(”%d号汽车此时退出便道，进入停车场最后一个位置nn“,*licen); num--; } } } 实验三、管道铺设施工的最佳方案问题 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define MaxVertexNum 100 //设置小区数最多为100 #define VertexNum 9 double LeastNum;//用于记录最短边长度 double LongestNum;//用于记录最长边长度，程序过程中不改变 double adjacent[VertexNum][VertexNum]; //邻接矩阵，不用于处理数据，而是用于暂时存储从文件读来的数据 //进而在邻接表存储数据时读取此数组数据即可 //二维数组数据为0的元素说明之间没有通道 //在处理完数据后，此数组会用来暂时存储处理后的数据，并写入到另一个文件中 typedef struct node {//边表结点 char adjvex; double weight;//权值 struct node *next; }EdgeNode; typedef struct vnode {//顶点表结点 char vertex; EdgeNode *firstedge; }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum]; int n,e; }ALGraph; void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void CreateALGraph(ALGraph *);//将文件中数据导入进来构建无向图邻接表 void MinimumSpanningTree(ALGraph *);//将无向图转化为最小生成树 void ResultOutput(double *array,int n1,int n2);//将数据在控制台显示出来 void read_data(void);//从输入文件读取数据到邻接矩阵 void cout_data(void);//将邻接矩阵中的数据输出到输出文件 void read_array(double *array,int n1,int n2,FILE *fp);//内部函数，用户无需调用 void cout_array(double *array,int n1,int n2,FILE *fp);//内部函数，用户无需调用 void main() { ALGraph *G; PrintInformation1(); G =(ALGraph*)malloc(sizeof(ALGraph)); G->n = VertexNum;//为G指向的图分配空间，设置点数（小区数） read_data(); CreateALGraph(G); MinimumSpanningTree(G); cout_data();//输出到文件 ResultOutput((double *)adjacent,VertexNum,VertexNum);//输出到控制台 PrintInformation2(); system(”pause“); } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验三.管道铺设施工的最佳方案问题rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } void CreateALGraph(ALGraph *G) { //建立无向图的邻接表存储 int i=0,j=0,k=0; EdgeNode *s; for(i = 0;i < G->n;i++) { G->adjlist[i].vertex = 65 + i; printf(”t%c“,(G->adjlist[i].vertex));//控制台输出列表头 G->adjlist[i].firstedge=NULL; } printf(”n“); for(k=0;k { for(j=0;j { if(adjacent[k][j]!=0) { s =(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex = 65+j; s->weight=adjacent[k][j]; s->next = G->adjlist[k].firstedge; G->adjlist[k].firstedge = s; } } } } void read_data(void) { int i,j; FILE *fp; fp=fopen(”gyp_program3_Input.dat“,”r“);// 输入数据文件 read_array((double *)adjacent,VertexNum,VertexNum,fp); fclose(fp); for(i = 0;i < VertexNum;i++) { for(j = 0;j < VertexNum;j++) { if(adjacent[i][j] > LongestNum) { LongestNum = adjacent[i][j];//即给LongestNum设置的初值为最大边边值 } } } } void read_array(double *array,int n1,int n2,FILE *fp) { int i,j; float q; for(i=0;i for(j=0;j { fscanf(fp,”%f“,&q); *array++ =(double)q; } } void cout_data(void) { FILE *fp; fp=fopen(”gyp_program3_Output.dat“,”w“);//输出数据文件 cout_array((double *)adjacent,VertexNum,VertexNum,fp); fclose(fp); } void cout_array(double *array,int n1,int n2,FILE *fp) { int i,j; for(i = 0;i < n2;i++) { fprintf(fp, ”t%c“, 65 + i);//输出文件里打印列表头 } fprintf(fp,”n“); for(i=0;i { fprintf(fp,”%ct“,65+i);//输出文件里打印行表头 for(j=0;j { fprintf(fp,”%.1ft“,*array); array++; } fprintf(fp,”n“); } } void ResultOutput(double *array,int n1,int n2) { int i,j; for(i=0;i { printf(”%ct“,65+i);//控制台输出行表头 for(j=0;j { printf(”%.1ft“,*array); array++; } printf(”n“); } } void MinimumSpanningTree(ALGraph *G) {//将无向图转化为最小生成树 int i, j, k; int flag2=1,point; int start, end; EdgeNode *s; char NowAdjacent[VertexNum]; for(i=0;i { for(j = 0;j < VertexNum;j++) { adjacent[i][j] = 0;//先将邻接矩阵所有值清零 } } NowAdjacent[0]=G->adjlist[0].vertex;//初始点放入点集 for(i=0;i //刚开始只有一个起始点，之后加入剩余的VertexNum个点，即VertexNum-1次循环 { LeastNum = LongestNum;//这一步很重要，每加入一个点，应把LeastNum初始化为//最大值，避免受之前数值的影响 for(j = 0;j < i + 1;j++)//第i次点集里有i+1个点，即比较这i+1个点与生于点边的大//小，找最小边的另一个点 { point = NowAdjacent[j]-A;//用于指示已经存进点集中的点是图的第几个点 s = G->adjlist[point].firstedge; while(s!= NULL) { for(k = 0;k < i + 1;k++) { if(s->adjvex == NowAdjacent[k]) { flag2 = 0;//flag2=0用于指示此时s所指的点已经在点集内 break; } } if(flag2 == 1)//确保仅当s指向的点是不在点集里的点时，才被比较处理 { if((LeastNum > s->weight)&&(s->weight!=0)) { end = s->adjvex-A;//flag用于指示最短边是第几个点 start = point; LeastNum = s->weight; } } s = s->next; flag2 = 1;//标志位有可能已经被清0，必须重设为1，确保不影响下一次 } //启发：对于用的不止一次的标志位，一定不可能只单方向置位，一定是双向置位，//否则用了一次，后面就会误判 } adjacent[start][end] = LeastNum; adjacent[end][start] = LeastNum; NowAdjacent[i + 1] = G->adjlist[end].vertex;//向点集加入新点 } } 实验四、内部排序算法的实现与比较 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ const int N=3000;//随机产生N个随机整数 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime(); void InsertSort(int R[], int n);//插入排序 void SelectSort(int R[], int n);//选择排序 void BubbleSort(int R[], int n);//冒泡排序 void QuickSort(int R[],int low,int high);//快速排序 void ShellInsert(int R[],int m,int n);//快速排序 void Shellsort(int R[],int n);//希尔排序 void KeyCompareNum_pailie(); void MoveNum_pailie(); int KeyCompareNum[5]={0};//分别存储这5种排序的关键字比较次数 int MoveNum[5]={0};//分别存储这5种排序的移动次数 int main() { //数组设为N+1个是因为有些算法是从数组1到N存储的，0位有的不用，有的用作了哨兵 int num0[N+1];//记录最原先随机产生的N个数字，因为num[N]每排序一次都会改变 int num[N+1];//每次排序前先读入num0[N]数据 //srand函数只增加一次就够了，用系统当前时间设置rand()随机序列种子，保证每次运行随机序列不一样 srand((unsigned)(time(NULL))); for(int j = 0;j < N;j++) { num0[j] = rand(); } PrintInformation1(); for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } SelectSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } BubbleSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } Shellsort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } QuickSort(num,0,N-1); printf(”关键字比较次数按从小到大排列分别是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移动次数按从小到大排列分别是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } void KeyCompareNum_pailie()//关键字比较次数排列 { int i,j,k,m; int printnum=0;//用于记录上一次输出的是数组KeyCompareNum的第几个数 int minimum;//用于输出最小的数字 int maximum=0; for(i = 0;i < 5;i++) { if(maximum < KeyCompareNum[i]) maximum = KeyCompareNum[i]; } for(m = 0;m< 5;m++) { minimum = maximum; //minimum在每次输出是都是全新的，不能受之前数值的影响，因此每次输出第一步先//把minimum设为最大值 for(j = 0;j < 5;j++) { if((minimum >=KeyCompareNum[j])&&(KeyCompareNum[j]!= 0)) { minimum = KeyCompareNum[j]; } } for(k = 0;k < 5;k++)//编程时k原先用的还是i,结果i=4这个情况,break以后到紧接//着的外层循环时，i的数值影响到了外层循环，跳了出来，因此换成了k { if(minimum == KeyCompareNum[k]) { KeyCompareNum[k] = 0; printnum = k; break; } } if(printnum == 0) printf(”直接插入排序:%dt“, minimum); if(printnum == 1) printf(”选择排序:%dt“,minimum); if(printnum == 2) printf(”冒泡排序:%dt“, minimum); if(printnum == 3) printf(”快速排序:%dt“, minimum); if(printnum == 4) printf(”希尔排序:%dt“, minimum); } printf(”rn“); } void MoveNum_pailie()//移动次数排列 { int i, j, k, m; int printnum = 0;//用于记录上一次输出的是数组KeyCompareNum的第几个数 int minimum;//用于输出最小的数字 int maximum = 0; for(i = 0;i < 5;i++) { if(maximum < MoveNum[i]) maximum = MoveNum[i]; } for(m = 0;m < 5;m++) { minimum = maximum;//minimum每次输出是都是全新的，不能受之前数值的影响，//因此每次输出第一步先把minimum设为最大值 for(j = 0;j < 5;j++) { if((minimum >= MoveNum[j])&&(MoveNum[j]!= 0)) { minimum = MoveNum[j]; } } for(k = 0;k < 5;k++)//编程时k原先用的还是i,结果i=4这个情况,break以后到紧接//着的外层循环时，i的数值影响到了外层循环，跳了出来 {//因此换成了k if(minimum == MoveNum[k]) { MoveNum[k] = 0; printnum = k; break; } } if(printnum == 0) printf(”直接插入排序：%dt“, minimum); if(printnum == 1) printf(”选择排序：%dt“, minimum); if(printnum == 2) printf(”冒泡排序：%dt“, minimum); if(printnum == 3) printf(”快速排序：%dt“, minimum); if(printnum == 4) printf(”希尔排序：%dt“, minimum); } printf(”rn“); } void InsertSort(int R[], int n)//插入排序 { int i, j; for(i = 2;i <= n;i++) { R[0] = R[i]; MoveNum[0]++; j = i-1; while(R[0] < R[j]) { KeyCompareNum[0]++; R[j + 1] = R[j]; MoveNum[0]++; j--; } R[j + 1] = R[0]; MoveNum[0]++; } } void SelectSort(int R[], int n)//选择排序 { int i, j, k; for(i = 1;i < n;i++) { k = i; for(j = i + 1;j <= n;j++) if(R[j] < R[k]) { k = j; KeyCompareNum[1]++; } if(k!= i) { R[0] = R[k]; R[k] = R[i]; R[i] = R[0]; MoveNum[1]+=3; } } } void BubbleSort(int R[], int n)//冒泡排序 { int i, j, flag = 0; for(i = 1;(i < n && flag == 0);i++) { flag = 1; for(j=1;j if(R[j + 1] < R[j]) { KeyCompareNum[2]++; flag = 0; R[0] = R[j]; R[j] = R[j+1]; R[j + 1] = R[0]; MoveNum[2]+=3; } } } void QuickSort(int R[],int low,int high)//快速排序 { int i,j; i=low; j=high; R[0]=R[i]; MoveNum[3]++; while(i { while((R[j]>=R[0])&&(j>i)) { j--; KeyCompareNum[3]++; } if(j>i) { R[i]=R[j]; MoveNum[3]++; i++; } while((R[i]<=r[0])&&(j>i)) { i++; KeyCompareNum[3]++; } if(j>i) { R[j]=R[i]; MoveNum[3]++; j--; } } R[i]=R[0]; MoveNum[3]++; if(low QuickSort(R,low,i-1); if(i QuickSort(R,j+1,high); } void ShellInsert(int R[],int m,int n) {//一趟希尔排序，按间隔m划分子序列 int temp,j; for(int i=m;i { temp=R[i]; MoveNum[4]++; j=i; while(j>=m && temp { KeyCompareNum[4]++; R[j]=R[j-m]; MoveNum[4]++; j-=m; } R[j]=temp; MoveNum[4]++; } } void Shellsort(int R[],int n)//希尔排序 { int m; m=n/2; while(m>=1) { ShellInsert(R,m,n); m=(m==2?1:(m/2)); } } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验四.内部排序算法的实现与比较rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:"); PrintTime(); }
