数据结构课程设计由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计全”。
课 程 设 计 任 务 书
信息 学院 信息管理与信息系统 专业 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={|ai-1,ai∈d,i=2,„n} 基本操作：的初始化S GetTop(S,&e)素
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={|ai-1,aij∈D i=1,„,m+2,j=1,„,n+2}
第1页
操作结果
构造一个空栈，完成栈用e返回栈S的栈顶元将新的元素e压入栈顶 删除栈顶元素，并用eInitStack(&S)
山东科技大学学生课程设计
Col={|aijaij-1∈D}
基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件：已知目前迷宫状态, 传过起始位置，和终止位置 操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }ADT MAZE
三、详细设计：
#include #include #include #define OVERFLOW-2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 //存储空间初始量 #define STACK_INCREMENT 10//存储空间初始增量
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.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i
for(j=1;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 Pa(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;}//Pa
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
printf(“%4d”,i);//输出列数
printf(“n”);for(i=0;i
printf(“%d”,i);//输出行数
for(j=0;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(Pa(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
设定当前位置为该新方向上的邻位
{
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 #include typedef struct node
//定义节点类型 { 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 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页
