实验四:最短路径
实验4 最短路径实验时间4课时。
实验目的
练习结对编程。
掌握图的存储结构。
掌握Dijkstra算法或Floyd算法。
问题描述给定全国铁路网,对于任意一对城市,找出它们之间的最短路径经过哪些城市,并输出最短路径的长度。 铁路网的信息以文本形式给出,其格式为: 城市A编号 城市B编号 距离 其中城市编号和城市名称信息也是以文本形式给出,其格式为: 编号 城市名称 这两个文本文件可以在下方zip文件处与源码一起下载。
实验内容
两人一对,提交一份实验报告和源代码。
求出下列城市之间的最短路径:沈阳至西安、呼和浩特至成都、上海至乌鲁木齐。
从铁路网中删除一些城市(例如郑州),再重新计算上述城市之间的最短路径。
实现提示图的存储结构可使用邻接矩阵(较为简单)或邻接表。
源代码下载源代码
main.cpp mgraph.h mgraph.cpp
若程序显示无法打开文件,请在mgraph.cpp第10行和第27行自行修改文件路径名;
本程序使用Floyd算法实现。
main.cpp12345678910111213141516171819202122232425 ...
数据结构实验七-选做-话费统计问题
实验7 统计话费实验时间选做。
实验目的综合运用所学知识,为实际问题设计高效算法。
问题描述给定一份通话记录文件,包含约10万用户一天共计约100万条通话记录。文件是纯文本格式,每行为一条记录,格式如下: 手机号码(11位)、呼叫类型(2位,00表示主叫,01表示被叫)、通话时长(4位,以秒为单位)、呼叫发生小区(4位)、换行符(2位,即’\r\n’) 例如,文件的第一行:13955191490010225JQHK 表示手机号码为13955191490的用户在JQHK小区被叫,时长为225秒。 计费规则如下:
通话时长以分钟为单位计费,不足一分钟按一分钟计算。
主叫每分钟0.40元(40分)、被叫每分钟0.20元(20分)。
请生成话费账单,输出一份文件,要求输出文件是纯文本格式,每行为一条记录,格式如下: 手机号码(11位)、总费用(8位,以分为单位)、换行符(2位,即’\r\n’) 如输出文件的第一行:1395519149000001240 表示手机号码为13955191490的用户费用是12.40元。
实验内容请设计计算复杂度尽可能低的算法。**提交程序运行时间最短的5名 ...
HuffmanCoding
实验3 Huffman编码和解码实验时间4课时。
实验目的
掌握二叉树的存储结构和常用算法。
熟练掌握递归程序设计方法。
问题描述Huffman编码是二叉树的典型应用之一。给定一个文本文件,对其进行编码和解码,计算压缩比,从而了解数据压缩的基本原理。 待编码的文本文件是C语言的标准库头文件stdio.h。
实验内容
对文本文件统计各个字符的出现频率,构造Huffman树。
以图形化的方式打印Huffman树,例如可以逆时针旋转90度打印,如下图所示,或者自己设计打印图形。
以Huffman树对文本文件进行编码,统计编码后的比特数,除以8得到字节数。用原文件的大小(字节数)除以编码后的字节数,即求得压缩比。
将编码后的比特流再进行解码,写入一个新的文本文件,与原文件比较,是否完全一致?比较文件可使用Windows命令行工具fc。
源代码下载源代码
main.cpp HuffmanTree.h HuffmanTree.cpp Queue.h Queue.cpp
main.cpp123456789101112131415161718192 ...
玩转Linux操作系统
玩转Linux操作系统
说明:本文中对Linux命令的讲解都是基于名为CentOS的Linux发行版本,我自己使用的是阿里云服务器,系统版本为CentOS Linux release 7.6.1810。不同的Linux发行版本在Shell命令和工具程序上会有一些差别,但是这些差别是很小的。
操作系统发展史只有硬件没有软件的计算机系统被称之为“裸机”,我们很难用“裸机”来完成计算机日常的工作(如存储和运算),所以必须用特定的软件来控制硬件的工作。最靠近计算机硬件的软件是系统软件,其中最为重要的就是“操作系统”。“操作系统”是控制和管理整个计算机硬件和软件资源、实现资源分配和任务调配、为系统用户以及其他软件提供接口和环境的程序的集合。
没有操作系统(手工操作)在计算机诞生之初没有操作系统的年代,人们先把程序纸带(或卡片)装上计算机,然后启动输入机把程序送入计算机,接着通过控制台开关启动程序运行。当程序执行完毕,打印机输出计算的结果,用户卸下并取走纸带(或卡片)。第二个用户上机,重复同样的步骤。在整个过程中用户独占机器,CPU等待手工操作,资源利用率极低。
批处理系统首先启动计算机上的一个 ...
马尔科夫模型调研
不会打字
正文:马尔科夫模型调研
数据结构实验二(栈)
表达式求值问题描述表达式求值:计算一个算术表达式的值。
实验内容
基本功能:计算一个语法正确的、仅有四则运算(带括号)且操作数全部为正数的算术表达式的值。
可选做的高级功能:(1)对表达式的语法进行分析,若语法错误则提示;(2)允许输入的操作数为负数;(3)增加更多的运算,如乘方、开方、三角函数、对数函数等;(4)计算多项式表达式的值,即“操作数”都是多项式的表达式,计算结果也是多项式。
源代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513 ...
数据结构实验二(队列)
银行排队系统仿真问题描述银行排队系统仿真:模拟一个银行排队系统一天的运行情况。
实验内容
基本功能:模拟一个单队列、多窗口的银行排队系统一天的运行情况,随机生成顾客的到达时间和办理业务所需时间等数据。一天结束后,统计顾客的平均等待时间和窗口的平均占用率。
可选做的高级功能:(1)改变顾客办理业务所需时间或银行的窗口数,观察顾客平均等待时间和窗口平均占用率如何变化;(2)假设每位顾客有一个容忍时间,等待超过容忍时间之后顾客将离开,统计顾客的离开率;(3)假设银行有两个队列,其中一个是VIP队列,另一个是普通队列,窗口服务的规则改为:若VIP队列不空,则优先服务VIP,否则服务普通顾客,统计VIP和普通顾客的平均等待时间有多大的差别。
源代码下载源代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888 ...
数据结构实验一
一元多项式实验报告问题描述要求程序能够完成如下功能:(1)创建多项式;(2)打印显示多项式;(3)销毁多项式;(4)复制多项式;(5)求两个多项式的和;(6)求两个多项式的差;(7)求两个多项式的积;(8)求一个多项式的n次幂;(9)计算一个多项式在x=a处的值;(10)求两个多项式的商和余式;(11)求两个多项式的最大公约式和最小公倍式;(12)求一个多项式的n阶导函数;(13)求一个多项式的不定积分;(14)求一个多项式在区间[a, b]上的定积分。
程序输入输出是在命令行中完成的。用户选择所需功能,并输入数据进行运算。输入错误数据时会要求重新输入或打印错误信息,但不会终止程序。直到用户选择退出,程序结束。
实验内容存储结构示意图:
程序中使用的主要数据结构是以链表存储的多项式,其定义为
12345typedef struct lnode { float coef; // 系数 int expn; // 指数 struct lnode* next;}lnode, * polynomial;
程序中的主要函数及函数原型为:
123456789101 ...