C语言程序设计课程设计题目——软件工程班.docx

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个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
⑷用选择排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
⑸对已按平均成绩排好序的4个班的同学的构造一个所有按平均成绩的以非递增方式排列的新的单链表；
⑹设计一个菜单，至少具有上述操作要求的基本功能。
（本题⑸由2人完成）
3迷宫问题
问题描述：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
实现要求：
⑴实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
⑵编写递归形式的算法，求得迷宫中所有可能的通路；
⑶以方阵形式输出迷宫及其通路。
[测试数据]
迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。
12345678
001000100010001000001101011100100001000001000101011110011100010111000000实现提示：
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。
4栈及其操作
问题描述：
栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。
设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素an。即栈的修改是按后进先出的原则进行的。
栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。链栈的基本形式如下：
top
⋀

空链栈
top
an

a3

a2

a1⋀

┇
非空链栈

实现要求：
⑴链栈基本操作的实现：栈的初始化，生成一个空栈；压栈，即元素进栈；弹栈，即元素出栈；
⑵十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。转换法则：该转换法则对应于一个简单算法原理：
n=(ndivd)*d+nmodd其中：div为整除运算，mod为求余运算
⑶在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?
匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所