第一篇：信管软件11级数据结构课程设计
11级软件、信管课程设计
要求：
本课程设计要求在17-18周完成，课程设计题目如附件所示，共有46题，题目分配方案如下：学号1号和16、31号可做1、16、31题，2号和17、32号可做2、17、32题„依此类推，每人可3选1做。信管1101、02、软件1101班19周星期一下午15:00-17:00在我办公室2501答辩（按学号来），课程设计的源程序学习委员将其汇总起来，然后一个班刻录成一个光盘答辩时给我交过来，答辩人则只需带好课程设计报告和演示程序过来。课程设计报告规范见另外一个文件，请大家重视这次课程设计，我会根据你的课程设计报告和答辩情况当时给该门课程的成绩，不再另外安排时间接收课程设计报告的答辩要求，谢谢配合！
（光盘名字命名为软件1101数据结构课程设计（每个同学一个文件夹，文件夹命名规则 学号+姓名+课题名））
-戴成秋 2012-12-27 课程设计题目：
1.运动会分数统计（难度***）
任务：参加运动会有10个学校，学校编号为1„„10。比赛分成18个男子项目，和12个女子项目。项目编号为男子1„„18，女子19„„30。不同的项目取前三名积分，前三名的积分分别为：5、3、2。
功能要求：
1)可以输入各个项目的前三名的成绩； 2)能统计各学校总分；
3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)数据存入文件并能随时查询
5)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称
输出形式：有中文提示，各学校分数为整型
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在java语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：测试数据及测试结果请在上交的资料中写明；
2.飞机订票系统（难度****）
任务：通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
3.退票： 可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
文章编辑（难度***）
功能：从键盘输入一页文字，静态存储在一个文件中 要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；
（2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”（3）输出删除某一字符串后的文章；
4.哈希表设计[问题描述]
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
[基本要求]
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
[测试数据]
取读者周围较熟悉的30个人名。
[选作内容]
（1）从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
（2）研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
（3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
5.宿舍管理查询软件（难度**）
任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
（1）建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)（2）实现如下查询功能: 按姓名查询 按学号查询 按房号查询
（3）打印任一查询结果（可以连续操作）
6.校园导航问题（难度**）
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
7.图书借阅管理系统（难度***）
主要分为两大功能：
1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)； 2)会员管理(增加会员、查询会员、删除会员、借书信息)；
8.学生成绩管理（难度***）
实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。
9.活期储蓄帐目管理（难度***）
活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：
1)能比较迅速地找到储户的帐户，以实现存款、取款记账；
2)能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。
10.二叉排序树的实现（难度**）
用顺序和二叉链表作存储结构
1)以回车('n')为输入结束标志,输入数列L，生成一棵二叉排序树T； 2)对二叉排序树T作中序遍历，输出结果；
3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
11.最小生成树问题（难度**）
设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
12.通讯录的制作（难度***）设计目的：用〈〈数据结构〉〉中的双向链表作数据结构，结合java语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：
1)输入信息——enter();2)显示信息———display();3)查找以姓名作为关键字 ———search();4)删除信息———delete();5)存盘———save();6)装入———load();设计要求：
1)每条信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项
2)作为一个完整的系统，应具有友好的界面和较强的容错能力 3)上机能正常运行，并写出课程设计报告
13.哈夫曼编码/译码器（难度**）【问题描述】
设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】
1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)2)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码；
5)设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1
14.图书管理系统（难度****）【问题描述】
设计一个计算机管理系统完成图书管理基本业务。【基本要求】
1)每种书的登记内容包括书号、书名、著作者、现存量和库存量； 2)对书号建立索引表（线性表）以提高查找效率； 3)系统主要功能如下：
*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
*归还：注销对借阅者的登记，改变该书的现存量。
15.走迷宫游戏（难度***）
程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：
1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2)迷宫的墙足够结实，老鼠不能穿墙而过；
3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4)找出走出迷宫的所有路径，以及最短路径。
16.顺序结构、动态链表结构下的一元多项式加法的实现。（难度**）
设有一元多项式Am(x)和Bn(x).123m Am(x)=A0+A1x+A2x+A3x+„ +Amx
123n Bn(x)=B0+B1x+B2x+B3x+„ +Bnx
请实现求M(x)= Am(x)+Bn(x)要求：
1)结果M(x)中无重复阶项和无零系数项； 2)要求输出结果的升幂和降幂两种排列情况
17.利用栈求表达式的值，可供小学生作业，并能给出分数。（难度*）要求：（1）判断表达式是否正确，主要是括号问题
（2）题目涉及加减乘除，带括弧的混合运算
18.二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（难度*）要求：遍历的内容应是千姿百态的。
19.敢死队问题（难度**）
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
20.猴子吃桃子问题（难度**）
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
要求：
1)采用数组数据结构实现上述求解 2)采用链数据结构实现上述求解 3)采用递归实现上述求解
21.数制转换问题（难度**）
将一个十进制数转换为二、八、十六进制数
22.排序综合（难度**）
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：
1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
23.最小生成树求解实现（难度**）要求：
1)先任意创建一个图；
2)设计克鲁斯卡尔类，求出该图的最小生成树
24.线索二叉树的应用（难度**）要求：建立线索树。
25.稀疏矩阵应用（难度**）
要求：实现三元组下的稀疏矩阵的乘法。
26.树的应用（难度**）
要求：实现树与二叉树的转换的实现。
27.HTML文档标记匹配算法（难度**）
要求：输入一段HTML代码，判断该代码是否符合HTML的语法
提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为
:节的头部
HTML语言有合理的嵌套，如
第二篇：数据结构课程设计
课 程 设 计 任 务 书
信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目： 迷宫求解、一元多项式
课程设计主要参考资料： 数据结构（C语言版）严蔚敏、吴伟民 编著
数据结构题集（C语言版）严蔚敏、吴伟民、米宁 编著
数据结构课件
三、设计应解决下列各主要问题：
1.实现迷宫的路径求解，并输出最终路径，标记走过却未选择的路径和最终选择的路径
2.对一元多项式实现加法，减法，乘法，求导的计算，并按指数由大到小排序输出
四、课程设计相关附件（如：图纸、软件等）：
五、命题发出日期：2011-3-15 设计应完成日期： 2010-6-20
设计指导教师（签章）：
系主任（签章）：
指导教师对课程设计的评语
指导教师（签章）：
年 月 日
山东科技大学学生课程设计
课程设计1 迷宫问题
一、需求分析：
1.2.3.4.以二维数组Maze[][]表示迷宫
用户输入迷宫的数据：构建迷宫，行数m，列数n 迷宫的入口位置和出口位置可由用户随时设定
若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。
5.本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数做小量修改，便可求得全部路径。
二、概要设计：
抽象数据类型线性表的定义如下： ⒈ 设计栈的抽象数据类型定义：
ADT Stack { 数据对象：D={ai:|ai∈PositionSet,i=1„n,n≥0} 数据关系：R1={
Push(&S,e)Pop(&S,e)
返回其值 }ADT Stack；
⒉ 迷宫的抽象数据类型定义： ADT Maze{ 数据对象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0}
数据关系：R={ROW.COL} Row={
第1页
操作结果
构造一个空栈，完成栈用e返回栈S的栈顶元将新的元素e压入栈顶 删除栈顶元素，并用eInitStack(&S)
山东科技大学学生课程设计
Col={
基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件：已知目前迷宫状态, 传过起始位置，和终止位置 操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }ADT MAZE
三、详细设计：
#include
typedef int Status;
typedef struct { int r;int c;}PostType;//坐标位置
迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号
PostType seat;//通道块的当前坐标位置
int di;//通道块指向下一通道块的方向 }SElemType;//栈元素的类型 typedef struct { SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈的最大容量 }Stack;//栈的类型
第2页 山东科技大学学生课程设计
Status InitStack(Stack &S)//初始化栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)
exit(OVERFLOW);//存储分配失败;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStack
Status StackEmpty(Stack S)//判断栈是否为空,如果为空返回TRUE,否则返回FALSE { if(S.top==S.base)
return TRUE;
return FALSE;}//StackEmpty
Status Push(Stack &S,SElemType e)//插入元素为e的栈顶元素 { if(S.top-S.base>=S.stacksize){
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;} *S.top++=e;return OK;}//Push
Status Pop(Stack &S,SElemType &e)//删除栈顶元素存入e { if(S.top==S.base)
return ERROR;e=*--S.top;
第3页 山东科技大学学生课程设计
return OK;}//Pop
Status DestroyStack(Stack &S)//销毁栈 { free(S.base);S.top=S.base;return OK;}//DestroyStack
//maze.cpp #define MAXLEN 20//迷宫包括外墙最大行列数目 typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType;
//迷宫类型
Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j,k=1;
printf(“输入迷口的行数和列数: ”);
scanf(“%d%d”,&maze.r,&maze.c);//迷宫行和列数
for(i=0;i<=maze.c+1;i++){//迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++){//迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宫
printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
while(m!=0)
{
if(m>maze.r || n>maze.c)//越界
第4页 山东科技大学学生课程设计
exit(ERROR);
maze.adr[m][n]='#';//迷宫障碍用'#'标记
printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);
scanf(“%d%d”,&m,&n);
k++;
}
return OK;}//InitMaze
Status Pass(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;}//Pass
Status FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]='*';//“*”表示可通
return OK;}//FootPrint
PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){
//1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1;break;
case 2 : cpos.r+=1;break;
case 3 : cpos.c-=1;break;
case 4 : cpos.r-=1;break;
default: exit(ERROR);
}
return cpos;}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){ //曾走过但不是通路标记并返回OK
第5页 山东科技大学学生课程设计
maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走过但不通
return OK;}//MarkPrint
void PrintMaze(MazeType &maze)//将最后标记好的迷宫输出 { int i,j;printf(“n输出迷宫的路径:n”);for(i=0;i<=maze.c+1;i++)
printf(“%4d”,i);//输出列数
printf(“n”);for(i=0;i<=maze.r+1;i++){
printf(“%d”,i);//输出行数
for(j=0;j<=maze.c+1;j++)
printf(“%4c”,maze.adr[i][j]);//输出迷宫
printf(“n”);} }//PrintMaze
Status MazePath(MazeType &maze,PostType start,PostType end)//若迷宫从入口start到end的通道则求得一条存放在栈中 { Stack S;//初始化栈
PostType curpos;int curstep;SElemType e;InitStack(S);curpos=start;curstep=1;do {
if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹
{
FootPrint(maze,curpos);
e.ord=curstep;e.seat=curpos;e.di=1;
Push(S,e);//加入栈路径中
if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE
{
第6页 山东科技大学学生课程设计
if(!DestroyStack(S))
exit(OVERFLOW);
else return TRUE;
}
else
{
curpos=NextPos(curpos,1);//下一位置是当前位置
curstep++;//探索下一步
}
}//if
else//当前位置不能通过
{
if(!StackEmpty(S))
{
Pop(S,e);//提取前一位置
while(e.di==4 &&!StackEmpty(S))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过
{
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di<4)//换下一个方向探索
设定当前位置为该新方向上的邻位
{
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}
}//if
} }while(!StackEmpty(S));if(!DestroyStack(S))
exit(ERROR);else return FALSE;}//MazePath
int main(){ MazeType maze;PostType start,end;char c;
第7页 山东科技大学学生课程设计
do {
printf(“**********迷宫求解**********n”);
if(!InitMaze(maze))
{
printf(“n 初始化迷宫失败！!”);
exit(ERROR);
}
do
{
printf(“n请输入入口的坐标:”);
scanf(“%d%d”,&start.r,&start.c);//输入入口坐标
if(start.r>maze.r || start.c>maze.c)
printf(“n输入错误,请重新输入入口的坐标！n”);
continue;
}
while(start.r>maze.r || start.c>maze.c);
do
{
printf(“n请输入出口的坐标:”);//输入出口的坐标
scanf(“%d%d”,&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c)
printf(“n输入错误,请重新输入出口坐标！n”);
continue;
}
while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf(“n不能找到一条路径！!n”);
else PrintMaze(maze);//输出迷宫
printf(“是否要继续?(y/n):”);
scanf(“%s”,&c);} while(c=='y' || c=='Y');}。测试结果：
第8页
四、山东科技大学学生课程设计
课程设计2 一元多项式
一、需求分析：
第9页 山东科技大学学生课程设计
1.2.3.首先定义一个结构体，其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域；
然后一一罗列每个在主程序中用到的函数，并一一实现； 最后在主程序中主要完成用户的输入和相关函数的调用。
二、概要设计：
void insert(PLOYList *head,PLOYList *input)
//查找位置插入新链节的函数，且让输入的多项式呈降序排列 PLOYList *creat(char ch)//输入多项式
PLOYList *add(PLOYList *head,PLOYList *pre)//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头
PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减
PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式相乘
PLOYList *der(PLOYList *head)//多项式求导
void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 void start()//用户选择界面
三、详细设计：
#include
//定义节点类型 { float coef;
//多项式的系数
int expn;
//多项式的指数
struct node * next;//结点指针域 }PLOYList;void insert(PLOYList *head,PLOYList *input)
//查找位置插入新链节的函数，且让输入的多项式呈降序排列 {
PLOYList *pre,*now;
int signal=0;
pre=head;
第10页 山东科技大学学生课程设计
if(pre->next==NULL){pre->next=input;} //如果只有一个头结点，则把新结点直接连在后面
else {
now=pre->next;//如果不是只有一个头结点，则设置now指针
while(signal==0)
{
if(input->expn < now->expn)
{
if(now->next==NULL)
{
now->next=input;
signal=1;
}
else
{
pre=now;
now=pre->next;//始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面
}
}
else if(input->expn > now->expn)
{
input->next=now;
pre->next=input;
signal=1;
}//若新结点中指数比最后一个结点即now中的指数大，则插入now之前
else//若指数相等则需合并为一个结点，若相加后指数为0则释放该结点
{
now->coef=now->coef+input->coef;
signal=1;
free(input);
if(now->coef==0)
{
pre->next=now->next;
free(now);
}
}//else } //while
第11页 山东科技大学学生课程设计
}//else }//void
PLOYList *creat(char ch)
//输入多项式 {
PLOYList *head,*input;
float x;
int y;
head=(PLOYList *)malloc(sizeof(PLOYList));
//创建链表头
head->next=NULL;
scanf(“%f %d”,&x,&y);//实现用户输入的第一个项，包括其指数和系数
while(x!=0)
{
input=(PLOYList *)malloc(sizeof(PLOYList));//创建新链节
input->coef=x;
input->expn=y;
input->next=NULL;
insert(head,input);//每输入一项就将其排序，是的链表中多项式呈降序排列
scanf(“%f %d”,&x,&y);
} return head;}
PLOYList *add(PLOYList *head,PLOYList *pre)
//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 {
PLOYList *input;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//若该链表为空，则无需进行加法运算，跳出循环
else
{
pre=pre->next;
input=(PLOYList *)malloc(sizeof(PLOYList));
第12页 山东科技大学学生课程设计
input->coef=pre->coef;
input->expn=pre->expn;
input->next=NULL;
insert(head,input);// 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x)
}
} return head;}
PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 {
PLOYList *input;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;
else
{
pre=pre->next;
input=(PLOYList *)malloc(sizeof(PLOYList));
input->coef=0-pre->coef;//将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法
input->expn=pre->expn;
input->next=NULL;
insert(head,input);
}
} return head;}
PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式项乘 { PLOYList *hf,*pf,*qa,*qb;
qa = head-> next;
qb = pre-> next;//定义指针指向表头后一个元素，即链表中第一个元素
hf =(PLOYList *)malloc(sizeof(PLOYList));//新创建一个结点，当做表头
hf-> next = NULL;for(;qa;qa = qa-> next)
第13页 山东科技大学学生课程设计
{
for(qb = pre-> next;qb;qb= qb-> next)//用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并
{
pf =(PLOYList *)malloc(sizeof(PLOYList));
pf-> coef = qa-> coef * qb-> coef;//系数相乘
pf-> expn = qa-> expn + qb-> expn;//指数相加
pf-> next = NULL;
insert(hf,pf);
} } return hf;}
PLOYList *der(PLOYList *head)//多项式求导 { PLOYList *p;p = head-> next;while(p){
p-> coef = p-> coef * p-> expn;
p-> expn = p-> expn--;
p = p-> next;} return head;}//将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导
void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 {
PLOYList *printing;
int flag=0;
printing=fun->next;
if(fun->next==NULL)//若为空表，则无需输出
{
printf(“0n”);
return;
}
while(flag==0)
{
第14页 山东科技大学学生课程设计
if(printing->coef>0&&fun->next!=printing)
printf(“+”);
if(printing->coef==1);
else if(printing->coef==-1)
printf(“-”);
else
printf(“%f”,printing->coef);
if(printing->expn!=0)printf(“x^%d”,printing->expn);
else if((printing->coef==1)||(printing->coef==-1))
printf(“1”);
if(printing->next==NULL)
flag=1;
else
printing=printing->next;
} printf(“n”);}
void start()//用户选择界面 { printf(“
#n”);
printf(“
用户选择界面
n”);
printf(“ ************************************n”);
printf(“ *
*n”);
printf(“ *
1.两个一元多项式相加
*n”);
printf(“ *
2.两个一元多项式相减
*n”);
printf(“ *
3.两个一元多项式相乘
*n”);
printf(“ *
4.对一个一个一元多项式求导 *n”);
printf(“ *
0.退出系统
*n”);
printf(“ *
*n”);
printf(“ ************************************n”);
printf(“
n”);
printf(“ 注释：输入多项式格式（可无序）：系数1 指数1 系数2 指数2 „„，并以0 0 结束：n”);
printf(“
n”);
printf(“ 请选择操作: ”);}
int main(){ PLOYList *f,*g,*pf,*hf,*p;
第15页 山东科技大学学生课程设计
int sign=-1;
start();
while(sign!=0)
{
scanf(“%d”,&sign);
switch(sign)
{
case 0:
break;
case 1://多项式相加
{
printf(“ 你选择的操作是多项式相加:n”);
printf(“ 请输入第一个多项式f(x)：”);
f=creat('f');
printf(“ 第一个多项式为：f(x)=”);
print(f);
printf(“ 请输入第二个多项式g(x)：”);
g=creat('g');
printf(“ 第二个多项式为：g(x)=”);
print(g);
printf(“ 结果为：F(x)=f(x)+g(x)=”);
f=add(f,g);
print(f);
printf(“nn”);
printf(“ 继续请选择相应操作，退出请按0.break;
}
case 2://多项式相减
{
printf(” 你选择的操作是多项式相减:n“);
printf(” 请输入第一个多项式f(x)：“);
f=creat('f');
printf(” 第一个多项式为：f(x)=“);
print(f);
printf(” 请输入第二个多项式g(x)：“);
g=creat('g');
printf(” 第二个多项式为：g(x)=“);
print(g);
printf(” 结果为：F(x)=f(x)-g(x)=“);
f=sub(f,g);
print(f);
”);第16页
山东科技大学学生课程设计
printf(“nn”);
printf(“ 继续请选择相应操作，退出请按0.”);
break;
}
case 3://多项式相乘
{
printf(“ 你选择的操作是多项式相乘:n”);
printf(“ 请输入第一个多项式f(x)：”);
f=creat('f');
printf(“ 第一个多项式为：f(x)=”);
print(f);
printf(“ 请输入第二个多项式g(x)：”);
g=creat('g');
printf(“ 第二个多项式为：g(x)=”);
print(g);
printf(“ 结果为：F(x)=f(x)* g(x)=”);
pf=mul(f,g);
print(pf);
printf(“nn”);
printf(“ 继续请选择相应操作，退出请按0.”);
break;
}
case 4://多项式求导
{
printf(“您选择的是对一个一元多项式求导：n”);
printf(“请输入一个一元多项式：”);
f = creat('f');
printf(“这个多项式为：f(x)= ”);
print(f);
printf(“求导结果为：F(x)=f'(x)= ”);
f=der(f);
print(f);
printf(“nn”);
printf(“ 继续请选择相应操作，退出请按0.”);
break;
}
}//swith
}//while }//void
四、测试结果：
第17页 山东科技大学学生课程设计
第18页
第三篇：数据结构课程设计
南京航空航天大学金城学院
《数据结构》 课程设计报告
题目：一元多项式的加减乘法运算
班级： 20100232 学号： 2010023220 姓名： 祁博 成绩：
指导教师： 叶延风
完成日期： 2012年 2月18 日
课程设计的主要内容 需求分析
1.1课程设计题目
用线性表实现一元多项式的加法减法与乘法。
1.2课程设计的任务及要求
任务：利用所学线性表知识来完成计算器中一元多项式的加法减法与乘法的运算。要求：能自己创建线性表，能自主的进行线性表的有关插入删除操作，并且可以在此基础上实现线性表之间的加减乘除运算。
1.3课程设计思想
首先要定义一个结构体，其中定义一元多项式的两个参数，系数和指数和链表中的指针域，然后一一罗列每个在主程序中得到的函数，并一一实现，最后在主程序中主要完成用户的输入和相关程序的调用。
1.4软件开发的环境
VC++6.0。
2.程序源代码
#include
typedef struct node{//定义节点类型
float coef;int expn;
struct node * next;}Ployn;
void menu()//用户选择界面
{
printf(“************************************n”);
printf(“ 两个一元多项式的相加/相减，相乘:n”);
printf(“************************************n”);
printf(“请选择操作:n”);
printf(“0.退出n”);
printf(“1.两个一元多项式相加n”);
printf(“2.两个一元多项式相乘n”);
printf(“3.两个一元多项式相减n”);
}
void insert(Ployn *head,Ployn *inpt)//查找位置插入新链节程序
{
Ployn *pre,*now;
int signal=0;
pre=head;//pre定义为现在的前一个链节
if(pre->next==NULL){pre->next=inpt;}
else {now=pre->next;while(signal==0){
if(inpt->expn>now->expn)//当新链节小于现在的连接时向后移一个链节
{
if(now->next==NULL)
{
now->next=inpt;
signal=1;
}
else
{
pre=now;
now=pre->next;
}
}
else if(inpt->expn
{
inpt->next=now;
pre->next=inpt;
signal=1;
}
else
{
now->coef=now->coef+inpt->coef;
signal=1;
free(inpt);//与当前链节相等指数
if(now->coef==0)
{
pre->next=now->next;
free(now);
}
} } } }
Ployn *creat(char ch)//输入多项式
{
Ployn *head,*inpt;
float x;
int y;
head=(Ployn *)malloc(sizeof(Ployn));//创建链表头
head->next=NULL;
printf(“请输入一元多项式%c:(格式是：系数 指数；以0 0 结束！)n”,ch);
scanf(“%f %d”,&x,&y);
while(x!=0)
{
inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节
inpt->coef=x;
inpt->expn=y;
inpt->next=NULL;
insert(head,inpt);//不然就查找位置并且插入新链节
printf(“请输入一元多项式%c的下一项:(以0 0 结束！)n”,ch);
scanf(“%f %d”,&x,&y);
}
return head;}
Ployn *addPloyn(Ployn *head,Ployn *pre)//多项式相加
{
Ployn *inpt;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//当现在指向空时跳出循环
else
{
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节
inpt->coef=pre->coef;
inpt->expn=pre->expn;
inpt->next=NULL;
insert(head,inpt);
}//否则把当前“g(x)”的链节插入到“y(x)”中
}
return head;}
Ployn *minusPloyn(Ployn *head,Ployn *pre)//多项式相加
{
Ployn *inpt;
int flag=0;
while(flag==0)
{
if(pre->next==NULL)
flag=1;//当现在指向空时跳出循环
else
{
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节
inpt->coef=0-pre->coef;
inpt->expn=pre->expn;
inpt->next=NULL;
insert(head,inpt);
}//否则把当前“g(x)”的链节插入到“y(x)”中
}
return head;}
Ployn *byPloyn(Ployn *head1,Ployn *head2)//多项式相乘
{
Ployn *inpt,*res,*pre;
int flag=0;
res=(Ployn *)malloc(sizeof(Ployn));//创建链表头
res->next=NULL;
head1=head1->next;
pre=head2;
while(flag==0)
{
if(pre->next==NULL)
{
pre=head2;//当现在指向空时跳出循环
head1=head1->next;
continue;
}
if(head1==NULL)
{
flag=1;//当现在指向空时跳出循环
continue;
}
pre=pre->next;
inpt=(Ployn *)malloc(sizeof(Ployn));//创建新链节
inpt->coef=pre->coef*head1->coef;
inpt->expn=pre->expn+head1->expn;
inpt->next=NULL;
insert(res,inpt);//把当前“g(x)”的链节插入到“y(x)”中
}
return res;}
void print(Ployn *fun)//输出多项式
{
Ployn *printing;
int flag=0;
printing=fun->next;//正在被打印的链节
if(fun->next==NULL)//如果函数为空打印0
{
printf(“0n”);
return;}
while(flag==0)
{
if(printing->coef>0 && fun->next!=printing)
printf(“+”);//为正数且不为第一项时打印“+”号
if(printing->coef==1);//如果为“1”就不用打印系数了
else if(printing->coef==-1)
printf(“-”);//如果为“-1”就打印“-”号就行了
else
printf(“%f”,printing->coef);//其余情况都得打印
if(printing->expn!=0)//如果指数为“0”不打印指数项
{ if(printing->expn==1)printf(“x”);
else printf(“x^%d”,printing->expn);
}
else if((printing->coef==1)||(printing->coef==-1))
printf(“1”);
if(printing->next==NULL)
flag=1;//如果现在的链节没有下一个就结束
else
printing=printing->next;
}
printf(“n”);}
void main(){
Ployn *f,*g;
int sign=-1;//设置标志
menu();
while(sign!=0)
{
scanf(“%d”,&sign);
switch(sign){
case 0: break;//退出
case 1:
{
printf(“你选择的操作是多项式相加:n”);
f=creat('f');//输入多项式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//输入多项式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)+g(x)=”);
f=addPloyn(f,g);//两个多项式相加
print(f);
sign=-1;//复位标志
menu();//回复用户选择界面
break;
}
case 2:
{
printf(“你选择的操作是多项式相乘:n”);
f=creat('f');//输入多项式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//输入多项式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)*g(x)=”);
f=byPloyn(f,g);//两个多项式相加
print(f);
sign=-1;//复位标志
menu();//回复用户选择界面
break;
}
case 3:
{
printf(“你选择的操作是多项式相减:n”);
f=creat('f');//输入多项式f(x)
printf(“f(x)=”);
print(f);
g=creat('g');//输入多项式g(x)
printf(“g(x)=”);
print(g);
printf(“F(x)=f(x)-g(x)=”);
f=minusPloyn(f,g);//两个多项式相加
print(f);
sign=-1;//复位标志
menu();//回复用户选择界面
break;
}
default:
{
printf(“输入有误!请重新选择操作!n”);//选择错误,返回选择界面
menu();
break;
}
}
} }
3.心得体会
每次做课设都有很大的收获。课设不仅是对课本知识的理论实践，更是对自我的一种挑战。
这次课设过程中，遇到很多的问题，让我有种无从下手的感觉，但是办法总比困难多，于是，在老师、同学的帮助下，以及自己在翻书、上网找资料的情况下，顺利解决问题。于是，我又上课的认识到，团队的重要性。
第四篇：数据结构课程设计
河海大学计算机与信息学院（常州）
数据结构课程设计
课程设计题目：
多 项 式 问 题
专业、年级：计算机科学与技术09级 学
号：
0962810226
姓
名：
王
超
目 录
一、问题描述-------------3
二、需求分析-------------4
三、概要设计-------------4 1.概要设计目的与要求--4 2.概要设计内容--------4 3.功能算法描述与数据结构说明-------------------------5
四、详细设计-------------5
五、系统测试-------------8
六、使用说明-------------9
七、总结及心得体会-----10
多项式问题
一．问题描述
给你九个整数，这九个整数分别是x的8次方至0次方的系数，请你按照多项式的一半形式合理地构造（去除不必要的）。例如九个系数分别是为0,0，0,1,22，-333,0,1，-1，你要构造并输出一行多项式：x^5 + 22x^4 – 333x^3 + x – 1。
它的格式规则如下：
1.多项式的项必须按其指数从高到低排列。2.指数必须跟在符号“^”后显示。3.有常数的只显示常数项（无需跟x^0）。
4.只显示系数不为0的项；若系数全为0，需显示常数项。
5.在多项式中唯一需要空格的地方是项与项之间的加号或减号的两边需加上空格。
6.如果首项的系数是正数，则系数前不加符号；如果首项的系数是负数，则符号与数字之间不加空格，就如：-3x^2 +-2x。
7.系数为1，指数为0时，系数的1才显示（推广到系数为-1）。
输入/输出说明
1.输入/输出方式为文件方式，输入文件有一行或多行的系数，系数之间有空格分隔。
2.每行共有九个系数，每个系数的绝对值为小于1000的整数。输出文件包含构造完地多项式，每行一个多项式。
输入范例
0 0 0 1 22-333 0 1-1 0 0 0 0 0 0-55 5 0
输出范例
x^5 + 22x^4 – 333x^3 + x – 1-55x^2 + 5x
二．需求分析
2.1可行性研究
该程序主要从技术的角度来分析可行性。技术上的可行性研究主要分析技术条件能否顺利完成开发工作，硬、软件能否满足开发者的需要等。该系统采用了Windows 7操作系统结合Visual C++ 6.0等软件开发平台已成熟可行。硬件方面，科技飞速发展的今天，硬件更新的速度越来越快，容量越来越大，可靠性越来越高，其硬件平台也比较能满足此系统的需要。
2.2结构与主要功能模块
从实现多项式输出过程的角度来分析，至少需要这样一些子功能模块。如： 1.多项式创建功能；
2.多项式输出功能；
3.释放多项式功能；
4.操作界面显示功能；
三．概要设计
1.概要设计目的与要求
通过多项式程序设计，使我们进一步掌握和利用C++语言进行结构化程序设计的能力；进一步理解和运用结构化程设计的思想和方法；初步掌握开发一个小型系统程序设计的基本方法；学会调试一个较长程序的基本方法；以及掌握书写课程设计开发文档的能力（书写课程设计报告）。总之，通过本课程设计加深对《C++语言》及《数据结构》课程所学知识的理解，进一步巩固C++语言语法规则，在程序中体现出算法的思想，提高程序的运行效率。学会编制结构清晰、风格良好、数据结构适当的C++语言程序，从而具备解决综合性实际问题的能力。
2.概要设计内容
多项式输出程序具有以下基本功能：
1．创建多项式。接收输入的数据，并保存到链表中。
2．Txt文档输入输出功能。
3． 清除内存内容，释放创建的链表，退出程序。
3.功能算法描述与数据结构说明
该多项式程序除了main()函数外，主要有以下函数：
node *CreatePolyn()
void firstnode(node *p)
void othernode(node *p)
void PrintPolyn(node *Pa)
void deletechain(node *h)
下面对这些函数逐一介绍。①.main（）函数
main函数主要调用其他函数，用来实现输入、显示功能。
在main（）函数中，定义一维数组p[]用来保存多项式的系数，Pa定义程序所需链表的头指针。在程序开始要求输入多项式的系数，随后创建链表以保存多项式，再显示出构建的符合要求的多项式。②.node *CreatePolyn()该函数功能是创建新的多项式链表。使用for语句，控制输入多项式的每一项。
③.void firstnode(node *p)该函数功能是判断输出多项式第一项。对于第一项的系数为1或-1，指数为0或-1等五种情况进行讨论。④.void othernode(node *p)该函数功能是判断输出多项式除第一项外的其它项。对于第一项的系数为1或-1，指数为0或-1等五种情况进行讨论。⑤.void PrintPolyn(node *Pa)该函数功能：显示构造的符合要求的多项式链表。在该函数中调用③、④函数，进行多项式的输出。⑥.void deletechain(node *h)该函数的功能是释放掉创建的链表，释放内存。
四．详细设计
下面讨论重要函数具体实现过程：
1.node *CreatePolyn()定义int i=9计数，当i>0时，for语句反复提示用户输入该多项式的每一项的指数。当i=1时，输入完毕，该链表也创建完毕。详细的实现过程如下：
node *CreatePolyn(){ node *head,*pa,*s;int i;
pa=head=new node;//创建一个新的结点
head->next=NULL;
for(i = 9;i >0;i--)// 依次输入9项
{
s=new node;
s->next=NULL;
s->coef = p[9-i];
s->exp=i-1;//x指数从8递减到0
if(s->coef!=0)//系数不为零时，结点p链接s
{
pa->next=s;
pa=s;
} } return head;} 2.void firstnode(node *p)对多项式第一项输出可能性进行多种分类讨论。
void firstnode(node *p)//输出多项式第一个结点 { //指数不为1且不为0,系数绝对值不为1（正常的输出）if(p->exp!=1&&p->exp&&fabs(p->coef)!=1)
{
if(p->coef>0)
{
outfile<
coef<<“X^”<
exp;
}
else
{
outfile<
coef<<“X^”<
exp;
} } if(p->exp==0)//指数为0，即常数项
{
if(p->coef>0)
{
outfile<
coef;
}
else
{
outfile<
coef;
} }
//指数大于0且不为1，系数绝对值为1 if(p->exp>0&&fabs(p->coef)==1&&p->exp!=1){
if(p->coef>0)
{
outfile<<“X^”<
exp;
}
else
{
outfile<<“-X^”<
exp;
} } if(p->exp==1&&fabs(p->coef)!=1)//指数为1且系数绝对值不为1 {
if(p->coef>0&&p->coef!=1)
{
outfile<
coef<<“X”;
}
if(p->coef<0&&p->coef!=-1)
{
outfile<
coef<<“X”;
} } if(p->exp==1&&fabs(p->coef)==1)//指数为1且系数绝对值为1 {
if(p->coef==1)
outfile<<“X”;
else
outfile<<“-X”;} }
3.void PrintPolyn(node *Pa)该函数有一个参数，该指针指向多项式链表的头指针，以下是实现插入的关键代码： void PrintPolyn(node *Pa){ node *p;if(Pa->next==NULL)//首项判断，如果首项无，则显示“0”
outfile<<“0”;
return;else {
firstnode(Pa->next);} p=Pa->next->next;//定义指针p指向Pa的下下个指针
while(p!=NULL){
othernode(p);
p=p->next;
//将p指向下个一个结点
}
outfile< 五．系统测试 该程序在VC6.0中调试通过，没有错误和警告，运行结果经过检验为正确。以下图为该程序运行结果效果图： 图5-1 范例 图5-2 一行输出 图5-3 多行输出 六．使用说明 1．打开1.txt文件，在里面任意输入9个整数，每个数字间要有空格，可以输入一行或者多行，输入多行的时候需要换行。 2.编译运行后，打开2.txt文件，即可看到输出的符合要求的多项式。 七．总结及心得体会 通过这次课程设计练习，使我更深刻地理解了C++语言的精髓-----指针的使用。完成整个程序设计有很大的收获，对指针掌握的更加熟练。 同时通过直接对单链表的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。 经过这次课程设计，我深刻认识到算法在程序设计中的重要性，如何让程序简单、易读是这个课程设计的难点。程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。 编程是一件枯燥乏味工作，但是只要认真专研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。 计算多项式的输出-----该程序虽然不是很大，但是自己独立完成这一任务也遇到不少的困难。另外也需要提出的是，非常感谢老师对我们的耐心指导，尤其是上机的时候给了我很多锻炼的机会。所以这次课程设计我才能够顺利的完成。 一、课程题目：一元稀疏多项式计算器 二、需求分析 1、一元稀疏多项式简单计算器的功能是： 1.1 输入并建立多项式； 1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,„„„cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.3多项式a和b相加，建立多项式a+b； 1.4 多项式a和b相减，建立多项式a-b。 2、设计思路: 2、设计思路： 2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式 2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令； 根据相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。 3、程序执行的命令包括： 1）输入多项式a；2）输入多项式b;3）求a+b;4)求a-b；5）求a*b；6）求a的导数；7）求b的导数；8）退出程序。 4、测试数据： 1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); 2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x); 3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); 4、(x+x^3)+(-x-x^3)=0; 5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200); 6、(x+x^2+x^3)+0=x+x^2+x^3.7、互换上述测试数据中的前后两个多项式 三、概要设计 为了实现上述功能需用带表头结点的单链表存储多项式。为此需要两个抽象的数据类型：线性表和多项式。 1.有序表的抽象数据类型定义为： ADT List{ 数据对象：D={ai|ai∈Elemset,i=1,2,„，n,n≥0} 数据关系：R1={ 2、多数据类型定义为： ADT Polynomial { 数据对象:D={ai,bi|ai为不为0的实数，bi为整数，i=2,„,n} 数据关系:R1={ai，bi} 基本操作： PrintPolyn(Polyn p)操作结果:输出多项式p。DestroyPolyn(Polyn p)操作结果:销毁多项式p。 Polyn CreatePolyn(Polyn head,int m)操作结果:创建一个m项的多项式。Polyn AddPolyn(Polyn pa,Polyn pb)初始条件:多项式链表pa,pb存在。 操作结果:创建一新多项式链表p，其结点为pa，pb相加。Polyn SubtractPolyn(Polyn pa,Polyn pb)初始条件:多项式链表pa，pb存在。 操作结果:创建一新多项式链表p，其结点为怕pa，pb相减。ValuePolyn(Polyn head,int x)操作结果:输入x值，计算并返回多项式的值 }ADT Polynomial 四、详细设计 1、元素类型、结点类型和指针类型 typedef int Status;typedef struct{ int coef;int expn;}Term;typedef Term ElemType;typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指针域 }LNode,* LinkList; 2、主函数和其他函数 void main(){ int m,n,a,x;int flag;Polynomial pa,pb,pc;printf(“ 欢迎使用多项式操作程序n”); //输出菜单 printf(“n 1: 创建多项式a n”);printf(“n 2: 创建多项式b n”);printf(“n 3: 输出多项式a n”);printf(“n 4: 输出多项式b n”);printf(“n 5: 输出a+b n”);printf(“n 6: 输出a-b n”);printf(“n 7: 输出a的导数 n”);printf(“n 8: 输出b的导数 n”);printf(“n 9: 代入x的值计算a n”);printf(“n 10: 代入x的值计算b n”);printf(“n 11: 输出a*b n”);printf(“n 12:退出程序 n”);while(a){ printf(“n请选择操作：”);scanf(“ %d”,&flag); switch(flag) { case 1 : { printf(“请输入a的项数:”);scanf(“%d”,&m);CreatePolyn(pa,m); break; } case 2 : { printf(“请输入b的项数:”);scanf(“%d”,&n);CreatePolyn(pb,n); break; } case 3 : { printf(“n 多项式a=”); PrintPolyn(pa); break; } case 4 : { printf(“n 多项式b=”); PrintPolyn(pb); break; } case 5 : { AddPolyn(pa,pb,pc);printf(“n a+b=”); PrintPolyn(pc); break; } case 6 : { SubtractPolyn(pa,pb,pc);printf(“n a-b=”); PrintPolyn(pc); break; } case 7 : { Polynomial_derivatePolyn(pa,pc); printf(“n 多项式a的导函数为：a'=”); PrintPolyn(pc); break; } case 8 : { Polynomial_derivatePolyn(pb,pc); printf(“n 多项式b的导函数为：b'=”); PrintPolyn(pc); break; } case 9 : { printf(“输入x的值：x=”); scanf(“%d”,&x); printf(“n x=%da=%.3fn”,x,ValuePolyn(pa,x)); break; } case 10 : { printf(“输入x的值：x=”); scanf(“%d”,&x); printf(“n x=%d，时 时b=%.3fn”,x,ValuePolyn(pb,x)); break; } case 11 : { MultiplyPolyn(pa,pb,pc);printf(“n a*b=”); PrintPolyn(pc); break; } case'12': { printf(“n 感谢使用此程序！n”); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; } default: printf(“n 您的选择错误，请重新选择!n”); } } } 3、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点 Status CreatePolyn(Polynomial &head,int m){ //建立一个头指针为head、项数为m的一元多项式 int i;LNode *p;p=head=(Polynomial)malloc(sizeof(struct LNode));head->next=NULL;for(i=0;i printf(“请输入第%d项的系数与指数:”,i+1);scanf(“%d %d”,&p->data.coef,&p->data.expn);Insert(p,head);//调用Insert函数插入结点 } return OK;}//CreatePolyn 4、求解并建立多项式a+b Status AddPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a+b，返回其头指针 LNode *qa=pa->next;LNode *qb=pb->next;LNode *headc,*hc,*qc;hc=(Polynomial)malloc(sizeof(struct LNode));//建立头结点 hc->next=NULL;headc=hc;while(qa||qb){ qc=(Polynomial)malloc(sizeof(struct LNode));switch(compare(qa,qb)){ case 1: { qc->data.coef=qa->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;break; } case 0: { qc->data.coef=qa->data.coef+qb->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;qb=qb->next;break; } case-1: { qc->data.coef=qb->data.coef;qc->data.expn=qb->data.expn;qb=qb->next;break; } } if(qc->data.coef!=0) { qc->next=hc->next;hc->next=qc;hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } pc=headc;return OK;} 5、求解并建立多项式a-b Status SubtractPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a-b，返回其头指针 LNode *h=pb;LNode *p=pb->next;LNode *pd,*pf;while(p){ //将pb的系数取反 p->data.coef*=-1;p=p->next;} AddPolyn(pa,h,pf);pd=pf;for(p=h->next;p;p=p->next)//恢复pb的系数 p->data.coef*=-1;pc=pd;return OK;} float ValuePolyn(Polynomial head,int x){ //输入x值，计算并返回多项式的值 LNode *p;int i,t;float sum=0;for(p=head->next;p;p=p->next){ t=1;for(i=p->data.expn;i!=0;) { if(i<0){t/=x;i++;} //指数小于0，进行除法 else{t*=x;i--;} //指数大于0，进行乘法 } sum+=p->data.coef*t;} return sum;} 6、求解并建立导函数多项式 Status Polynomial_derivatePolyn(Polynomial P,Polynomial &pc)//求导 { LNode *p,*pf,*ph;//用于遍历结点 p=P->next; ph=(Polynomial)malloc(sizeof(struct LNode)); ph->next=NULL; //pre=P; while(p!=NULL) { pf=(Polynomial)malloc(sizeof(struct LNode)); if(p->data.expn==0) { p=p->next; //free(p); //p=pre->next; } else { pf->data.coef=p->data.coef*p->data.expn; pf->data.expn=p->data.expn-1; Insert(pf,ph); p=p->next; } } pc=ph;return OK;} 7、求解并建立多项式a*b Status MultiplyPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a*b，返回其头指针 LNode *hf,*pf;LNode *qa=pa->next;LNode *qb=pb->next;hf=(Polynomial)malloc(sizeof(struct LNode));//建立头结点 hf->next=NULL;for(;qa;qa=qa->next){ for(qb=pb->next;qb;qb=qb->next) { pf=(Polynomial)malloc(sizeof(struct LNode));pf->data.coef=qa->data.coef*qb->data.coef;pf->data.expn=qa->data.expn+qb->data.expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } pc=hf;return OK;} 8、函数的调用关系图 主函数Pa pb pc数meadreturn headc*h项回*h 建立链表Polyn CreatePolyn(Polyn head,int m)多项式相加Polyn AddPolyn(Polyn pa,Polyn pb)返回*hc返输出多项式While{Printf(“”); 四、调试分析 5.1 运行该程序的操作平台： 5.1.1 硬件要求： 此程序需在一台PC机上运行,要用INTER或AMD的CPU,其他没多大要求。5.1.2 软件要求： 本程序能在Visual C++ 6.0下运行。5.2 错误分析： 1、函数名拼写错误 2、括号匹配错误 3、变量类型名定义错误 4、分号没有在英文环境下输出，导致运行出错 5、参数表出现语法错误，函数调用的一组参数之间没有以逗号隔开，并以一个右括号结束 六、用户手册 1、本程序的执行文件为：Cpp1.exe。 2、进入演示程序后即显示文本方式的用户界面。 3、根据提示数字执行操作。如输入数字“1” 4、执行相应命令后显示操作结果。 七、测试结果 1、最初的界面 2、选择操作“1”、“2”“3”、“4”，输入数字得到的结果，即创建多项式a和b 3、a+b 4、a-b 5、a*b 6、求导 7、带入x值求a，b 八、心得体会 通过这次课程设计，我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要勤动手，多实践。真正将这个程序做出来很不容易，但只要只要用心去做，总会有收获,特别是当我遇到问题时，通过向同学请教,最后终于找到方法时,并理解代码的含义时，心中是无比喜悦的。编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。第五篇：数据结构课程设计
点击咨询 