第一篇：数据结构课程设计总结
课程设计总结
通过这次的课程设计，我们对数据结构中图的应用有了更深的理解，并且使我们深刻的认识到实践的重要性，只有理论与实践相结合才能达到很好的学习效果，学到很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。由于刚开始对图的总体结构不熟悉，认真查找了一些资料，才对这次课程设计有了初步的了解。
在我们进行课程设计时，虽然在大体上算法是正确的，但时常会出现一些小问题，使我们不得不花一些时间来查找、修改错误。
这次课程设计，不但让我们学习了很多数据结构的知识和C语言的知，还让我熟悉了我win7的使用，以及用gdb调试程序，让我收获很大。
课程设计完成了，其中的余味我还在体会：数据结构是我们跨进计算机世界的第一个槛。我们虽然已经学完了，但是我们懂得的也只是毛皮，更多专业的知识还等我们去学习，从现在开始我们就得有精神上的紧迫感，在科技日新月异的今天，计算机人才太多了，我们只有让自己学习更精，视野更广，思维更高，理想更远，用知识来武装自己，用能力来证明自己，这样，我们才能在IT行业中做出贡献，实现自身的价值。
计算机科学与技术2012.12.20
第二篇：数据结构课程设计
课 程 设 计 任 务 书
信息 学院 信息管理与信息系统 专业 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 八、心得体会 通过这次课程设计，我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要勤动手，多实践。真正将这个程序做出来很不容易，但只要只要用心去做，总会有收获,特别是当我遇到问题时，通过向同学请教,最后终于找到方法时,并理解代码的含义时，心中是无比喜悦的。编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。第五篇：数据结构课程设计
点击咨询 