《C语言程序设计》课程设计.doc

软件工程10-2班 c语言程序设计课程设计题目1 一元稀疏多项式的运算 问题描述：设有两个带头指针的单链表表示两个一元稀疏多项式a、b，实现两个一元稀疏多项式的处理。实现要求： 输入并建立多项式； 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列； 多项式a和b相加，建立多项式a+b，输出相加的多项式； 多项式a和b相减，建立多项式a-b，输出相减的多项式； 多项式a和b相乘，建立多项式ab，输出相乘的多项式； 设计一个菜单，至少具有上述操作要求的基本功能。测试数据：(1) (2x+5x8-3.1x11)+(7-5x8+11x9)(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)(3)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)2 成绩排序假设某年级有4个班，每班有45名同学。本学期有5门课程考试，每门课程成绩是百分制。假定每个同学的成绩记录包含：学号、姓名各门课程的成绩共7项，其中学号是一个10位的字符串，每个学生都有唯一的学号，并且这4个班的成绩分别放在4个数组中，完成以下操作要求： 编写一个成绩生成函数，使用随机数方法，利用随机函数生成学生的各门课程的成绩（每门课程的成绩都是0100之间的整数），通过调用该函数生成全部学生的成绩； 编写一个平均成绩计算函数，计算每个同学的平均成绩并保存在成绩数组中； 用冒泡排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序； 用选择排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序； 对已按平均成绩排好序的4个班的同学的构造一个所有按平均成绩的以非递增方式排列的新的单链表； 设计一个菜单，至少具有上述操作要求的基本功能。（本题由2人完成）3 迷宫问题 问题描述： 以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实现要求： 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 编写递归形式的算法，求得迷宫中所有可能的通路； 以方阵形式输出迷宫及其通路。测试数据迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。4 栈及其操作 问题描述：栈(stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出lifo (last in first out)或先进后出filo (first in last out)线性表。栈顶(top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。设栈s=(a1，a2，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，an的次序进栈，退栈的第一个元素应为栈顶元素an。即栈的修改是按后进先出的原则进行的。栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。链栈的基本形式如下：top空链栈topan a3 a2 a1 非空链栈实现要求： 链栈基本操作的实现：栈的初始化，生成一个空栈；压栈，即元素进栈；弹栈，即元素出栈； 十进制整数n向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。转换法则：该转换法则对应于一个简单算法原理：n=(n div d)*d+n mod d 其中：div为整除运算，mod为求余运算 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回flase。5航班信息管理问题描述：飞机航班系统的数据包括两部分： 航班信息：航班号、最大载客数、起飞地点、起飞时间、降落地点、降落时间，单价； 乘客信息：航班号、身份证号码、姓名、性别、出生年月、座位号。乘客订票的主要方式是：乘客提出航班号、起飞地点、起飞时间、降落地点、订票数等订票要求，根据事先保存的航班数据决定乘客能否订票？只有全部满足了乘客的订票要求并且所订航班有足够的未订座位之后才能完成订票处理，并且修改该航班的未订座位数（每个航班的未订座位数的初始值就是该航班的最大载客数）；否则，订票失败，并且给出不能订票的原因。要求将航班数据保存在数据文件中，在处理时按航班的起飞地点建立不同的链表。功能要求 ： 增加航班记录。将新的航班记录增加到原有的航班数据文件中。在进行处理时必须检查所要增加的航班记录是否存在，如果已经存在，应给出提示信息后停止增加； 航班取消。如果某次航班的乘客数太少（已订票的少于本次航班最大载客数的10%），将取消该航班，但该航班的记录仍然保存在原有的航班数据文件中； 航班查询。应该有以下几种基本的查询方式：按航班号、按起飞地点和起飞时间、按降落地点，按起飞地点和降落地点； 航班订票。按上述问题描述中的乘客订票方式完成航班订票处理。 设计一个菜单，至少具有上述操作要求的基本功能。 6 运动会管理系统问题描述：校际运动会管理系统。设有n个学校参加校际运动会，共有男子竞赛项目数m，女子竞赛项目数w。每个学校可以参加所有竞赛项目，也可以只参加部分竞赛项目，每个学校对每个项目的参赛运动员不能超过4人，每个运动员最多只能参加3项单项比赛，团体赛不受限制。各项目名次取法有如下几种：用户自定义：（各名次权值由用户指定） 参赛人数超过6人，取前5名：第1名得分 7，第2名得分 5，第3名得分3，第4名得分2，第5名得分 1；参赛人数不超过6人，取前3名：第1名得分 5，第2名得分 3，第3名得分2； 团体项目的名次取法和上面相同，但分数加倍。功能要求 ： 运动员报名登记，以学校为单位进行运动员报名登记，登记的限制要求按问题描述的要求； 参赛信息查询，查看参赛学校信息和比赛项目信息； 竞赛检录，每项比赛开始前完成参赛运动员的检录； 竞赛成绩登记，填写比赛名次，然后根据竞赛检录的运动员人数和上述的记分方式自动完成各学校的成绩登记并实时生成各学校的团体总分； 比赛成绩查询，可以按竞赛项目、参赛学校、参赛运动员查看比赛成绩； 竞赛成绩排序，以学校为单位，按总成绩的高低，分别排序输出每个学校的总成绩、男子总成绩、女子总成绩； 设计一个菜单，至少具有上述操作要求的基本功能。（本题由2人完成）7集合运算问题描述：设有两个用单链表表示的集合a、b，其元素类型是int且以非递减方式存储，其头结点分别为a、b。要求下面各问题中的结果集合同样以非递减方式存储，结果集合不影响原集合。实现要求： 编写集合元素测试函数in_set，如果元素已经在集合中返回0，否则返回1； 编写集合元素输入并插入到单链表中的函数insert_set，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中； 编写集合元素输出函数，对建立的集合链表按非递增方式输出； 编写求集合a、b的交c=ab的函数，并输出集合c的元素； 编写求集合a、b的并d=ab的函数，并输出集合d的元素； 求集合a与b的对称差e=(a-b)(b-a) 的函数，并输出集合d的元素； 设计一个菜单，具有输入集合元素、求集合a、b的交c、求集合a、b的并d、求集合a与b的对称差e、退出等基本的功能。测试数据：由读者自定，但集合a、b的元素个数不得少于16个。8 矩阵的操作设有两个矩阵a=(aij)mn，b=(bij)pq。实现要求： 编写矩阵输入函数input_mat，通过该函数完成矩阵的输入并返回保存矩阵的三元组（不能使用全局变量）； 编写矩阵输出函数output_mat，通过该函数完成矩阵的输出，输出的形式是标准的矩阵形式（即二维数组的形式）； 求矩阵的转置，矩阵的转置a=(aji)nm，转置前输出原矩阵，转置后输出转置矩阵； 求矩阵a、b的和。矩阵a和b能够相加的条件是：m=p，n=q；矩阵a和b如果不能相加，请给出提示信息；若能够相加，则求和矩阵c并输出c；c=a+b=(cij)mn，其中cij=aij+bij 求矩阵a、b的差。矩阵a和b能够相减的条件是：m=p，n=q；矩阵a和b如果不能相减，请给出提示信息；若能够相减，则求差矩阵c并输出c；c=a-b=(cij)mn，其中cij=aij-bij 求矩阵a、b的积。矩阵a和b能够相乘的条件是：p=n；矩阵a和b如果不能相乘，请给出提示信息；若能够相乘，则求积矩阵d并输出d；d=ab=(dij)mq，其中dij=aikbkj，k=1,2,n 设计一个菜单，具有求矩阵的转置、求矩阵的和、求矩阵的积、退出等基本的功能。在求矩阵的和或求矩阵的积时要求能够先提示输入两个矩阵的，然后再进行相应的操作。9 数据汇总 问题描述：在数据处理中经常需要对大量数据进行汇总，将相同关键字记录的某些数据项的值叠加起来，生成一个分类汇总表。假设某超级市场销售有m种商品（假设商品的编号为1，2，3，m），有n台前台收款机（假设收款机的编号为1，2，3，n）进行收款，以记录的形式提供给计算机，每个记录表示某台收款机的一种商品一次交易的数量和销售额。记录由4个域组成：收款机编号、商品编号、销售数量、销售金额。构造一个结构体类型，每次销售数据以一个结构体变量保存在一个数据文件中。实现要求： 编写实现将数据记录插入到数据文件的最后的函数； 编写以收款机为单位的数据分类处理函数。构造n个单链表，每个链表保存一台收款机的销售记录，这n个单链表的头指针存放在一个指针数组中，通过数组的下标就可以知道是哪台收款机。读取数据文件的记录，将所有的销售记录(数据文件中的全部记录)分解插入到n个单链表； 编写以商品为单位的数据分类处理函数。构造m个单链表，每个链表保存一种商品的销售记录，这m个单链表的头指针存放在一个指针数组中，通过数组的下标就可以知道是哪种商品。读取数据文件的记录，将所有的销售记录(数据文件中的全部记录)分解插入到m个单链表； 统计每台收款机的销售总额； 以收款机为单位，将所有收款机按销售总额的非递减顺序构造一个单链表并输出； 以商品为单位，统计每种商品的销售总额； 以商品为单位，将所有销售的商品按销售总额的非递减顺序构造一个单链表并输出； 设计一个菜单，具有上述要求的所有功能、退出系统等最基本的功能。10 joseph环 题目之一：问题描述：编号是1，2，n的n个人按照顺时针方向围坐一圈，一开始任选一个正整数作为报数上限（开始）值m(mn)，从第s(sn)个人开始沿顺时针方向顺序报数，报到m时停止报数，报m的人出列，然后在从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。实现要求： 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。输出形式：建立一个输出函数，将正确的序列输出。 利用顺序表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。输出形式：建立一个输出函数，将正确的序列输出。测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？题目之二：问题描述：编号是1，2，n的n个人按照顺时针方向围坐一圈，一开始任选一个正整数作为报数上限（开始）值m(mn)，从第s(sn)个人开始沿逆时针方向顺序报数，报到m时停止报数，报m的人出列，然后在从他在逆时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。实现要求： 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。输出形式：建立一个输出函数，将正确的序列输出。 利用顺序表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。输出形式：建立一个输出函数，将正确的序列输出。测试数据：m的初值为31，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？11 背包问题的求解 题目之一：问题描述：假设有一个能装入总体积为t的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=t，要求找出所有满足上述条件的解。例如：当t=10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。问题提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解，或者无解。题目之二：问题描述：假设有n件物品，这些物品的重量分别是w1 , w2 , , wn，物品的价值分别是v1，v2， ，vn。求从这n件物品中选取一部分物品的方案，使得所选中的物品的总重量不超过限定的重量w（wwi, i=1