高级语言程序设计指导书

高级语言程序设计指导书（2015.06）Course Design of Advance Language Programming（适用班级：14广播电视工程）一、实习目标C语言程序设计的实训是学生重要的实习环节。上机实训不仅要求学生掌握C语言程序设计的基本知识，更重要的是培养学生掌握程序设计开发的基本素质、思维方法和技能，为学生综合素质的培养打下坚实基础。二、时间地点安排地点：第一实验楼436/124 时间：15.06.13-15.07.10具体安排：见实习任务实施方案三、 实习要求和具体内容要求1、通过对指针、函数、文件等操作的强化训练，在实践中熟练掌握它们，设计出更简洁、紧凑、高效的程序；2. 通过C语言的使用，体会使用C语言进行程序设计的主要方法。掌握C语言开发大型程序的方法，养成良好的编程规范，为今后的软件开发相关课程打下基础；3.通过实习，培养发现问题、认识问题、分析问题及解决问题的能力，提高自学能力和上机动手能力。具体内容实习内容分为基础篇和提高篇l 基础篇：着重训练C语言中指针、函数、文件操作等内容。同学们至少选做其中的4道（最后一道必做）。l 提高篇：内容主要包括数据结构中线性结构、树型结构和图型结构的存储实现与基本操作，同学们须选择其中的1-2道进行编程实现基础篇注：实验1到实验10均要求用指针方法处理。(1) 有n个人围成一圈，顺序排号。从第1个人开始报数（丛1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。(2) 有一个班有4个学生，5门课程。求第一门课程的平均分；找出有2门以上课程不及格的学生，输出他们的学号和全部课程成绩以及平均成绩； 找出平均成绩在90分以上或全部课程成绩在85分以上的学生。分别编3个函数实现以上3个要求。(3) 输入一个字符串，内有数字和非数字字符，例如：a123x456 17960?* 302tab5790 将其中连续的数字作为一个整数，依次存放到一数组a中。例如，123放在a0，456放在a1统计共有多少个整数，并输出这些数。(4) 求线性表的交集。假设有两个按元素值递增次序排列的线性表A和B，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等。比如，A中元素为（1,3,5,8,10,13,18），B中元素为（1,3,6,8,9,10,13,15），则删除元素后A、B里的元素为（1,3,8,10,13）。(5) 设计函数求一元多项式的导数。（注：xn（n为整数）的一阶导数为n*xn-1。）输入格式：以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式：以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是0，但是表示为“0 0”。输入样例：3 4 -5 2 6 1 -2 0输出样例：12 -10 1 6 0(6) 求一批整数中出现最多的个位数字: 一批整数，分析每个整数的每一位数字，求出现次数最多的个位数字。例如给定3个整数1234、2345、3456，其中出现最多次数的数字是3和4，均出现了3次。 输入格式： 输入在第1行中给出正整数N（<=1000），在第2行中给出N个不超过整型范围的正整数，数字间以空格分隔。 输出格式： 在一行中按格式“M: n1 n2 .”输出，其中M是最大次数，n1、n2、为出现次数最多的个位数字，按从小到大的顺序排列。数字间以空格分隔，但末尾不得有多余空格。 输入样例：31234 2345 3456输出样例：3: 3 4(7) 输入2个字符串S1和S2，要求删除字符串S1中出现的所有子串S2，即结果字符串中不能包含S2。输入格式：输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串，对应S1和S2。输出格式：在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。输入样例：Tomcat is a male ccatatcat输出样例：Tom is a male(8) 从键盘输入若干行字符（每行长度不等），输入后把它们存储到一磁盘文件中。再从该文件中读入这些数据，将其中小写字母转换成大写字母后在显示屏上输出。(9) 有一个磁盘文件“employee”，内存放职工的数据，每个职工的数据包括职工姓名、职工号、性别、年龄、住址、工资、健康状况、文化程度。要求将职工名、工资的信息单独抽出来另建一个简明的职工工资文件。从职工工资文件中删去一个职工的数据，再存回原文件。(10) 有5个学生，每个学生有3门课程的成绩，从键盘输入学生数据（包括学号、姓名、3门课成绩），计算出平均成绩，将原有数据和计算出的平均分数存放在磁盘文件“stud”中。(11) 将实验13“stud”文件中的学生数据，按平均分进行排序处理，将已排序的学生数据存入一个新文件“sort”中。并且对“sort”文件进行插入处理。插入一个学生的3门课的成绩，程序先计算新插入学生的平均成绩 ，然后将它按成绩高低顺序插入，插入后建立一个新文件。(12) QQ账号的申请与登陆，用户的QQ号码和密码都保存在文件中，首先从文件中读入所有用户的用户名和密码，然后用户可以进行账号的申请和登陆。若申请账号需要需保证QQ号是不存在的，否则不成功，若申请成功了，用户的账号和密码将保存在文件中（保证QQ号的长度为10位，密码必须是字母和数字的混合且至少8位）。当用户选择登陆功能，需要与当前所有用户名和密码进行匹配，若成功则登陆成功，若错误三次直接退出程序。提高篇提高篇的旨在培养大家用C语言解决实际问题，下面列出的题目至少做一道，做1道以上的同学有加分。大家如果有自己感兴趣的题目也可自拟，实习老师审核同意即可。1、一元多项式的相加和相乘对于任意一个多项式：Pn(x)=P0+P1X1+P2X2+PnXn可以抽象成一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项不是严格递增或递减的。P = (P0, 0), (P1, 1) , (P2, 2) , . , (Pn, n)用单链表表示以上线性结构。typedef struct nodefloat coef;int exp;struct node next;ploynode;(1) 在主函数中设计一个简单的菜单，实现多项式的输入、相加、相乘(2) 给定一个X的值，求多项式的值。2、通讯录管理系统分别用顺序表和单向链表的方式完成通讯录管理系统。系统具有如下功能：l 创建、插入、删除、查询、分组、显示。l 通讯录保存在文件中，每次系统运行时自动从文件加载。l 从通讯录中指定一个联系人模拟发短信和打电话的功能，并将对应的短信和通话记录保存在文件中。能够在系统中查询最近联系人，以及短信和通话记录其中：查询分为按姓名、按分组查询。分组的类型有新人、大学同学、中学同学、其他通讯录中的每个记录包括（姓名、性别、邮箱、手机号、联系地址、分组类型），短信记录包括(对方号码，短信内容，发送时间)，通话记录(3) 在主函数中设计一个简单的菜单，实现以上系统。3、飞机订票系统任务通过此系统可以实现如下功能： 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）。查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况。订票：（订票情况可以存在一个数据文件中，结构自己设定）；可以订票，如果该航班已经无票，可以提供相关可选择航班。退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件 要求：通过命令行菜单的方式让用户自主选择操作类型如：录入航班、查询航班、订票、退票等信息。根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；4、哈希查找设计散列表实现电话号码查找系统。 基本要求： 1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。 扩展要求： 1) 系统功能的完善； 2) 设计不同的散列函数，比较冲突率； 3) 在散列函数确定的前提下，尝试各种类型处理冲突的方法，考察平均查找长度的变化。5、各种排序算法的比较给出一组实验来比较下列排序算法的时间性能： 快速排序、堆排序、希尔排序、冒泡排序、归并排序（其它排序也可以作为比较的对象） 要求： （1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 （2）实验数据应具有说服力，包括： 规模范围要大（如从100到10000）     数据的初始特性类型要多，因而需要具有随机性；     实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。     实验结果要能以清晰的形式给出，如图、表等。 （3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 （5）要给出实验的方案及其分析。6、停车场管理队列的应用问题描述：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。 基本要求： 1） 要求以顺序栈模拟停车场，以链队列模拟便道。 2） 从终端读入汽车到达或离去的数据，每组数据包括三项： I） 是“到达”还是“离去”； II） 汽车牌照号码； III）“到达”或“离去”的时刻。 与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。 7、表达式求值栈的应用问题描述：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“后缀表达式”求算术表达式的值。 基本要求：1）以字符序列的形式从键盘读入一个语法正确的、不含变量的整数表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值。 2）显示在求值过程中运算符栈、操作数栈、输入字符和主要操作的变化过程。 8、校园的最短路径问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地