软件工程10-2班 《C语言程序设计》课程设计题目
1 一元稀疏多项式的运算
问题描述：设有两个带头指针的单链表表示两个一元稀疏多项式A、B，实现两个一元稀疏多项式的处理。 实现要求：
⑴ 输入并建立多项式；
⑵ 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列；
⑶ 多项式A和B相加，建立多项式A+B，输出相加的多项式； ⑷ 多项式A和B相减，建立多项式A-B，输出相减的多项式； ⑸ 多项式A和B相乘，建立多项式A×B，输出相乘的多项式； ⑹ 设计一个菜单，至少具有上述操作要求的基本功能。 测试数据：
(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个数组中，完成以下操作要求：
⑴ 编写一个成绩生成函数，使用随机数方法，利用随机函数生成学生的各门课程的成绩（每门课程的成绩都是0∽100之间的整数），通过调用该函数生成全部学生的成绩；
⑵ 编写一个平均成绩计算函数，计算每个同学的平均成绩并保存在成绩数组中；
⑶ 用冒泡排序法对4个班的成绩按每个同学的平均成绩的以非递增方式
1
软件工程10-2班 《C语言程序设计》课程设计题目
进行班内排序；
⑷ 用选择排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
⑸ 对已按平均成绩排好序的4个班的同学的构造一个所有按平均成绩的以非递增方式排列的新的单链表；
⑹ 设计一个菜单，至少具有上述操作要求的基本功能。
3 迷宫问题
问题描述： 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路
和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
实现要求：
⑴ 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
⑵ 编写递归形式的算法，求得迷宫中所有可能的通路； ⑶ 以方阵形式输出迷宫及其通路。 [测试数据]
迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 实现提示：
2
软件工程10-2班 《C语言程序设计》课程设计题目
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
可以二维数组存储迷宫数据，通常设定入口点的下标为（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。即栈的修改是按后进先出的原则进行的。
栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。链栈的基本形式如下：
3
top 空链栈
? top an ┇ a3 a2 a1 ? 非空链栈
软件工程10-2班 《C语言程序设计》课程设计题目
实现要求：
⑴ 链栈基本操作的实现：栈的初始化，生成一个空栈；压栈，即元素进栈；弹栈，即元素出栈；
⑵ 十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。转换法则：该转换法则对应于一个简单算法原理： n=(n div d)*d+n mod d 其中：div为整除运算，mod为求余运算
⑶ 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?
匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。
算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。
4
软件工程10-2班 《C语言程序设计》课程设计题目
5 用C语言设计一个年历系统
问题描述：
年历系统首先对于输入的任一年，能够给出该年每月的日期及实际周几的对应情况，并与实际的星期数垂直对齐，如下表所示（当输入2004时显示如下）：
Input the year:2004
The calendar of the year 2004.
Januray 1 February 2
============================== ============================== Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12 13 14 11 12 13 14 15 16 17 15 16 17 18 19 20 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29
============================== ============================== March 3 April 4
============================== ============================== Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26 27 28 29 30
============================== ==============================
功能要求 ：
⑴ 输入任一年将显示出该年的所有月份日期，对应的星期，输出的格式如上表要求（注意闰年情况）；
⑵ 输入任意日期（包括年、月、日，格式有yyy/mm/dd、dd/mm/yyyy、mm/dd/yyyy、和yyyy,mm,dd、mm,dd,yyyy、dd,mm,yyyy六种基本情况），要求能够显示出该日期是本年的哪一周，是星期几。
6 航班信息管理
问题描述：
飞机航班系统的数据包括两部分：
5