第一篇：数据结构课程设计-五子棋
姓 名： 刘旭
学 院： 计算机与通信学院
班 级： 通信工程101班
指导老师： 文志诚
目录
一、需求分析..................................................................................................................................3 1.1 开发背景....................................................................................................................................3 2.2 功能简介....................................................................................................................................3
二、系统设计..................................................................................................................................4 2.1 函数一览....................................................................................................................................4 2.2 “封面”的设计........................................................................................................................4 2.3 二维数组与控制台....................................................................................................................5 2.4 键盘操作....................................................................................................................................6 2.5判定.............................................................................................................................................7 2.6 悔棋的实现................................................................................................................................8
三、调试运行..................................................................................................................................9 3.1 进入界面....................................................................................................................................9 3.2 棋盘的初始状态......................................................................................................................10 3.3 激战中……..............................................................................................................................10 3.4 游戏结束..................................................................................................................................11
四、解决问题的关键....................................................................................................................11
五、课设总结................................................................................................................................11
六、附录........................................................................................................................................12 6.1 画图代码..................................................................................................错误！未定义书签。6.2 初始化......................................................................................................错误！未定义书签。6.3 Play函数..................................................................................................错误！未定义书签。
一、需求分析
1.1 开发背景
学习了数据结构该门课程，对于枯燥无味的理论知识，我们是否能够通过所学的知识在课程设计中做出有趣味东西，然后让我们对于数据结构更加的感兴趣呢？于是我和我的室友陈明建开始酝酿着写些什么东西。上个学期就已经写了通讯录那之类的链式结构，这次我们决心有所改变，我们学习了栈、队列、树、图，字典树有人选了，我们就来写一个基于图的小程序，五子棋，对，图的简单应用，于是我们开始着手来写这个小小的程序，祝我们好运！
2.2 功能简介
既然是五子棋，我们要做的是时时刻刻的将整个图（以下称为棋局）的状态呈现出来，那么界面就是必不可少的。MFC不会？没关系，我们就用基于控制台的字符输出来构建这个棋局吧，当然这只是第一步，详细如下： 1拥有一个良好的进入界面，以及必要的选项； ○2拥有一个二维的数组来记录和更新实时的状态，并且能够有一种方法在DOS界面下绘制○出整个棋局的实时状态（包括棋盘和棋子）；
3能够通过键盘上的按键完成所选位置的移动和选定操作； ○4能够在每一次的走棋后判定是否游戏结束（棋盘走满或者是一方胜出）； ○5能够完成悔棋的功能，并保证这之间的棋局绘图能够与二维数组数据同步，做到真正意○义上的悔棋。
二、详细设计
2.1 函数一览
2.2 “封面”的设计
首先还是讲些题外话，该程序由于与控制台有密切的关系，于是在代码中使用了不少 conio.h 中的函数，当然在显示时又使用了windows.h 中的 Sleep()函数，正是有了这些函数的使用，程序才得以顺利完成，尤其是后面频繁使用的gotoxy()函数。
进入正题，由于是一个小的程序，因此将每一个功能分成一个一个的函数，这样将在以后的修改和完成进度上都有很大的帮助。由上面的函数一览可以知道这个“封面”就是在Logo()函数里面实现的，函数实现过程中使用了Sleep()函数，使之有动态效果：
void Logo(){
char Wel[30]= { “Made By Lyush&& Mirs Chen” };
printf(“ttt
欢迎试用五子棋系统n”);
printf(“tt
”);
for(int i= 0;i< strlen(Wel);++i)
{
putchar(Wel[i]);
Sleep(200);// 可使字符一个一个的输出
}
putchar(10);// 换行对应的 ASCII 码值为十进制的 10 }
2.3 二维数组与控制台
二维数组是用来使得整个棋盘的信息全部记录下来，因此在结构体中二维数组的声明是最关键的。
struct {
int Status[MAX/2+2][MAX/2+2];
int MINBOX;
int Step;
char Graph[3][3];
char *FillGraph[9];
Sta Stack;} ChessBoard;
声明全局变量是为了使得各函数能够更方便地使用到这个结构体，现假设某点的坐标为(1, 1)，那么如何在屏幕上打印这个点呢？这就利用到了ChangeCoordinates()与gotoxy()函数，前者使坐标进行转换，后者让光标走到所指的那个点，其实主要还是因为类似“┣、╋、●、○”在横向上所占都是两个英文字母的距离，因此在控制台上反映的就是和数组下标倍数关系了。部分代码如下：
HANDLE hConsole= GetStdHandle(STD_OUTPUT_HANDLE);
void ChangeCoordinates(int _X, int _Y, int *X, int *Y){
*X=(_X-1)* 2;
*Y=(_Y-1)* 4;}
void gotoxy(int x, int y)//这是光标的函数 {
COORD coord;
coord.Y= x;
// 在实际的应用过程中发现交换x与y的赋值
coord.X= y;
// 更好理解，即横行位x，纵行为y。
SetConsoleCursorPosition(hConsole, coord);
}
2.4 键盘操作
在刚开始写这个五子棋的时候是以坐标来确定玩家的每一步棋，但后来发现这样操作性实在是差，键盘操作是更好的选择。这里又要用到一个函数 getch(),其作用是无回显的接受从键盘输入的字符，让屏幕不会出现你输入的字符且等待着按回车确定…… 有了这个宝贝函数，马上得到 “↑” 对应的ASCII码为-32和72 两个连着的数值，依次可得其他对应的ASCII码。后面在使玩家一和玩家二分离操作，玩家一则是利用 W、S、A、D + space来操作，玩家二则是 上下左右+ enter。配合ChangeCoordinates()与gotoxy()函数，完成对走棋的控制。部分代码如下：
if(Opreat[0]== 13&& Ply== 2|| Opreat[0]== 32&& Ply== 1){ if(ChessBoard.Status[Move_X][Move_Y]== 0)
{
int TTop= ++ChessBoard.Stack.Top;ChessBoard.Status[Move_X][Move_Y]= Ply;ChessBoard.Stack.Record[TTop][0]= Move_X;ChessBoard.Stack.Record[TTop][1]= Move_Y;printf(“%s”, Graph);return true;// 该次走棋操作有效
} else { … } } if(Opreat[0]==-32&& Opreat[1]== 72|| Opreat[0]== 'w'|| Opreat[0]== 'W'){// 凡是接受了“上操作”，则Move_X的值减一，if(Currect(Move_X-1, Move_Y))
{
Move_X-= 1;
} } else if(…){ … }
// 这是接下来的转换操作
ChangeCoordinates(Move_X, Move_Y, &Temp_X, &Temp_Y);Gotoxy(Temp_X, Temp_Y);
2.5判定
对于每次走棋后，首先应该做的就是判定一否有五个棋子已经连成一线，也是一个简单的搜索过程，由于每次走的点不一定是最外部的点，因此从每次走的点的两头同时搜索，当遇到两端同时结束时，搜索结束。当满足五子时游戏结束。当然，当棋盘被走满时，游戏亦结束。代码如下： bool Legal(int Point){
if(Point< 1|| Point> MAX/ 2+ 1)
return false;
else
return true;}
//搜索45度角是否为满足ChessBoard.MINBOX 以X正轴为参考轴
if(!Flag){ Count= 1;for(int i1= X-1, j1= Y+ 1, i2= X+ 1, j2= Y-1;Legal(i1)&& Legal(j1)|| Legal(i2)&& Legal(j2);i1--, j1++, i2++, j2--){
int LastCount= Count;
if(Legal(i1)&& Legal(j1)&& ChessBoard.Status[i1][j1]== Ply)
{
Count++;
}
if(Legal(i2)&& Legal(j2)&& ChessBoard.Status[i2][j2]== Ply)
{
Count++;
}
if(LastCount== Count)
break;
if(Count== ChessBoard.MINBOX){
Flag= 1;
return true;
} } }
2.6 悔棋的实现
虽说下棋悔棋是一种不道义的行为，但是如果双方约定好了，未尝不可。在没写悔棋之前，只是记录了“上一次”的位置，声明了Last_X，Last_Y;当然既然要求悔棋，那么直接调用栈顶元素，即可定位上次走棋的位置。那么悔棋呢，取出“上一次”的位置，判定位置（不同的位置对应不同的填充图形类型）在二维数组中撤销走棋时所赋予的 Ply 值（玩家一走时，其值为1，玩家二走时，其值为2），重新将 ChessBoard.Status[ Last_X ][ Last_Y ] 赋为0。代码如下：
int GetFillType(int X, int Y){
if(X== 1)
{
if(Y== 1)
return 0;
else if(Y== 16)
return 2;
else
return 1;
}
else if(X== 16)
{
if(Y== 1)
return 6;
else if(Y== 16)
return 8;
else
return 7;
}
else
{
if(Y== 1)
return 3;
else if(Y== 16)
return 5;
else
return 4;
} }
bool Retract(int *X, int *Y){
int Temp_X, Temp_Y, TTop, FillType;
if(!StackEmpty())
{
TTop= ChessBoard.Stack.Top--;
*X= ChessBoard.Stack.Record[TTop][0];
*Y= ChessBoard.Stack.Record[TTop][1];
ChessBoard.Status[*X][*Y]= 0;// 将该点置为真正意义上的空点
FillType= GetFillType(*X, *Y);
ChangeCoordinates(*X, *Y, &Temp_X, &Temp_Y);
Gotoxy(Temp_X, Temp_Y);
printf(“%s”, ChessBoard.FillGraph[FillType]);
return true;
}
else
{
Gotoxy(9, 65);
printf(“您已不能悔棋”);
Sleep(300);
Gotoxy(9, 65);
printf(“
”);
return false;
} }
三、调试运行
3.1 进入界面
3.2 棋盘的初始状态
3.3 激战中……
3.4 游戏结束
四、解决问题的关键
这个五子棋的程序并没有什么复杂的算法，只是利用了简单的图知识和一个栈的应用，在这里主要的关键问题就是如何将程序有条理的写下来，有一个好的逻辑思维。将程序分成了多个功能函数，尽量的让一个函数的功能单一，只是在内部调用了其他的函数以辅助改函数功能的实现，比如判定坐标是否越界，坐标是否合法，悔棋的点的位置状态…… 这样便能做到各个击破，程序的形成也就变得畅通许多了。
五、课设总结
刚开始写这个程序，认为一定要用到 graphics.h, 无奈电脑TC不兼容，因此只好强行来画这个界面了，使用输入法里面的制表符，效果还不错，通过一长串的if … else … 最好还是画出来了，这个时候觉得控制台的简单图形还是能够画出来的，并且可以尽量去美化它的界面。后面的附录中将给出画棋盘和棋子的源代码。在程序设计的过程中，尤其是为源程序加上悔棋的功能，这期间总是有许多意想不到的错误，比如加上后，有时走了5个连子棋，但是程序并没有判定输赢，而是可以继续走、有时没有五个却已经结束了，光标没有复位，悔棋后，玩家的走棋顺序没有跟着改变……通过后来的一步步修改终于使得这些问题都一一解决了，比如说对 Prompt（提示）函数引进了返回值，判断该次操作是否成功，如果下了棋则为 true，如果是悔棋就是 false 了，这样便使得后面的操作更规范了和统一了。
六、附录
#include
HANDLE hConsole= GetStdHandle(STD_OUTPUT_HANDLE);
void HideCursor(){ CONSOLE_CURSOR_INFO cursor_info = {1, 0};
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);}
typedef struct {
int Record[260][2];
int Base;
int Top;} Sta;
struct {
int Status[MAX/2+2][MAX/2+2];
int MINBOX;
int Step;
char Graph[3][3];
char *FillGraph[9];
Sta Stack;
} ChessBoard;
void Gotoxy(int x, int y)//这是光标的函数 {
COORD coord;
coord.Y= x;
coord.X= y;
SetConsoleCursorPosition(hConsole, coord);
}
void Logo(){
char Wel[30]= { “Made By Lyush&& Mirs Chen” };
printf(“ttt
欢迎试用五子棋系统n”);
printf(“tt
”);
for(int i= 0;i< strlen(Wel);++i)
{
putchar(Wel[i]);
Sleep(200);
}
putchar(10);}
int Login(){
int Mode, Skip= 0;
char Request;
if(!Skip)
{
printf(“nn在这儿你能DIY(Do it youself!)你的棋子，每个棋子接受一个汉字”);
printf(“ Y Orz Nn”);
scanf(“%c”, &Request);
if(Request== 'Y'|| Request== 'y')
{
printf(“玩家一的 DIY 棋子-->”);
scanf(“%s”, ChessBoard.Graph[1]);
ChessBoard.Graph[1][2]= ' ';
printf(“玩家二的 DIY 棋子-->”);
scanf(“%s”, ChessBoard.Graph[2]);
ChessBoard.Graph[2][2]= ' ';
}
}
printf(“nn请选择先手玩家:___ nn”);
printf(“nntttttt1 对应 玩家一对应 玩家二n”);
if(Request== 'Y'|| Request== 'y')
Gotoxy(10, 16);//原函数是 第一个参数为列，后一个参数为行，把Gotoxy函数做了更改
else
Gotoxy(8, 16);
scanf(“%d”, &Mode);
if(Mode!= 1&& Mode!= 2)
return Mode% 2+ 1;
else
return Mode;}
void InitChessBiard(){
int TTop= ChessBoard.Stack.Top;
fflush(stdin);
ChessBoard.Step= 0;
ChessBoard.Stack.Top= 0;
ChessBoard.Stack.Base= 0;
ChessBoard.Stack.Record[TTop][0]= 8;// 栈的0号位存储初始化的棋盘位置
ChessBoard.Stack.Record[TTop][1]= 8;
ChessBoard.MINBOX= 5;
ChessBoard.FillGraph[0]=“┏”;
ChessBoard.FillGraph[1]=“┳”;
ChessBoard.FillGraph[2]=“┓”;
ChessBoard.FillGraph[3]=“┣”;
ChessBoard.FillGraph[4]=“╋”;
ChessBoard.FillGraph[5]=“┫”;
ChessBoard.FillGraph[6]=“┗”;
ChessBoard.FillGraph[7]=“┻”;
ChessBoard.FillGraph[8]=“┛”;
strcpy(ChessBoard.Graph[1], “○”);
strcpy(ChessBoard.Graph[2], “●”);
memset(ChessBoard.Status, 0, sizeof(ChessBoard.Status));}
bool Legal(int Point){
if(Point< 1|| Point> MAX/ 2+ 1)
return false;
else
return true;}
bool Currect(int X, int Y){
if(Legal(X)&& Legal(Y))
return true;
else
return false;}
void ChangeCoordinates(int _X, int _Y, int *X, int *Y){
*X=(_X-1)* 2;
*Y=(_Y-1)* 4;}
void Draw(){
// 画棋盘
for(int i= 1;i<= MAX;++i)
{
for(int j= 1;j<=MAX;++j)
{
if(i== 1)
{
if(j== 1)
printf(“┏”);
else if(j== MAX)
printf(“┓n”);
else if(j%2)
printf(“┳”);// 横向占两个坐标位，竖向占一个坐标位
else
printf(“━”);
}
else if(i== MAX)
{
if(j== 1)
printf(“┗”);
else if(j== MAX)
printf(“┛n”);
else if(j%2)
printf(“┻”);
else
printf(“━”);
}
else
{
if(j== 1)
{
if(i% 2)
printf(“┣”);
else
printf(“┃”);
}
else if(j== MAX)
{
if(i% 2)
printf(“┫n”);
else
printf(“┃n”);
}
else
{
if(i% 2)
{
if(j% 2)
printf(“╋”);
else
printf(“━”);
}
else
{
if(j% 2)
printf(“┃”);
else
printf(“ ”);
}
}
}
}
}
// 画棋子
for(int i= 1;i<= MAX/ 2+ 1;++i)
{
for(int j= 1;j<= MAX/ 2+ 1;++j)
{
int Temp_X, Temp_Y;
ChangeCoordinates(i, j, &Temp_X, &Temp_Y);
if(ChessBoard.Status[i][j]== 1)
{
Gotoxy(Temp_X, Temp_Y);
printf(“○”);
}
else if(ChessBoard.Status[i][j]== 2)
{
Gotoxy(Temp_X, Temp_Y);
printf(“●”);
}
}
} }
int GetFillType(int X, int Y){
if(X== 1)
{
if(Y== 1)
return 0;
else if(Y== 16)
return 2;
else
return 1;
}
else if(X== 16)
{
if(Y== 1)
return 6;
else if(Y== 16)
return 8;
else
return 7;
}
else
{
if(Y== 1)
return 3;
else if(Y== 16)
return 5;
else
return 4;
} }
bool StackEmpty()
{
if(ChessBoard.Stack.Top== ChessBoard.Stack.Base)
return true;
else
return false;}
bool Retract(int *X, int *Y){
int Temp_X, Temp_Y, TTop, FillType;
if(!StackEmpty())
{
TTop= ChessBoard.Stack.Top--;
*X= ChessBoard.Stack.Record[TTop][0];
*Y= ChessBoard.Stack.Record[TTop][1];
ChessBoard.Status[*X][*Y]= 0;// 将该点置为真正意义上的空点
FillType= GetFillType(*X, *Y);
ChangeCoordinates(*X, *Y, &Temp_X, &Temp_Y);
Gotoxy(Temp_X, Temp_Y);
printf(“%s”, ChessBoard.FillGraph[FillType]);
return true;
}
else
{
Gotoxy(9, 65);
printf(“您已不能悔棋”);
Sleep(300);
Gotoxy(9, 65);
printf(“
”);
return false;
} }
bool Prompt(int Ply, int Last_X, int Last_Y){
int Move_X= Last_X, Move_Y= Last_Y;
int Temp_X, Temp_Y;
char Opreat[2];
char *Graph= ChessBoard.Graph[Ply];
Gotoxy(1, 65);
printf(“按退格键悔棋”);
Gotoxy(3, 65);
if(Ply== 1)
{
printf(“玩家一走棋：”);
Gotoxy(5, 65);
printf(“通过w s a d”);
}
else
{
printf(“玩家二走棋：”);
Gotoxy(5, 65);
printf(“通过↑↓←→”);
}
Gotoxy(7, 65);
printf(“按空格或回车”);
ChangeCoordinates(Move_X, Move_Y, &Temp_X, &Temp_Y);
Gotoxy(Temp_X, Temp_Y);
while(1)
{
Opreat[0]= getch();
if(Opreat[0]== 8)
{
if(Retract(&Move_X, &Move_Y))
return false;// 该次操作为伪操作
else
{
Gotoxy(Temp_X, Temp_Y);
continue;
}
}
else
{
if(Opreat[0]== 13&& Ply== 2|| Opreat[0]== 32&& Ply== 1)
{
if(ChessBoard.Status[Move_X][Move_Y]== 0)
{
int TTop= ++ChessBoard.Stack.Top;
ChessBoard.Status[Move_X][Move_Y]= Ply;
ChessBoard.Stack.Record[TTop][0]= Move_X;
ChessBoard.Stack.Record[TTop][1]= Move_Y;
printf(“%s”, Graph);
return true;// 该次走棋操作有效
}
else
{
Gotoxy(9, 65);
printf(“此步无效”);
Sleep(300);
Gotoxy(9, 65);
printf(“
”);
Gotoxy(Temp_X, Temp_Y);
continue;
}
}
if(Ply== 2)
{
if(Opreat[0]!=-32)
continue;
Opreat[1]= getch();
}
if(Opreat[0]==-32&& Opreat[1]== 72|| Opreat[0]== 'w'|| Opreat[0]== 'W')
{
if(Currect(Move_X-1, Move_Y))
{
Move_X-= 1;
}
}
else if(Opreat[0]==-32&& Opreat[1]== 80|| Opreat[0]== 's'|| Opreat[0]== 'S')
{
if(Currect(Move_X+ 1, Move_Y))
{
Move_X+= 1;
}
}
else if(Opreat[0]==-32&& Opreat[1]== 75|| Opreat[0]== 'a'|| Opreat[0]== 'A')
{
if(Currect(Move_X, Move_Y-1))
{
Move_Y-= 1;
}
}
else if(Opreat[0]==-32&& Opreat[1]== 77|| Opreat[0]== 'd'|| Opreat[0]== 'D')
{
if(Currect(Move_X, Move_Y+ 1))
{
Move_Y+= 1;
}
}
ChangeCoordinates(Move_X, Move_Y, &Temp_X, &Temp_Y);
Gotoxy(Temp_X, Temp_Y);
}
} }
bool Win(int Ply, int X, int Y)
{
// 先找上下的是否存在一条直线连成ChessBoard.MINBOX个
int Count= 1, Flag= 0;
for(int i= X-1, k= X+ 1;Legal(i)|| Legal(k);i--, k++)
{
int LastCount= Count;
if(Legal(i)&& ChessBoard.Status[i][Y]== Ply)
{
Count++;
}
if(Legal(k)&& ChessBoard.Status[k][Y]== Ply)
{
Count++;
}
if(LastCount== Count)
break;
if(Count== ChessBoard.MINBOX)
{
Flag= 1;
return true;
}
}
// 左右查找是否满足条件
if(!Flag)
{
Count= 1;
for(int i= Y-1, k= Y+ 1;Legal(i)|| Legal(k);i--, k++)
{
int LastCount= Count;
if(Legal(i)&& ChessBoard.Status[X][i]== Ply)
{
Count++;
}
if(Legal(k)&& ChessBoard.Status[X][k]== Ply)
{
Count++;
}
if(LastCount== Count)
break;
if(Count== ChessBoard.MINBOX)
{
Flag= 1;
return true;
}
}
}
//搜索45度角是否为满足ChessBoard.MINBOX 以X正轴为参考轴
if(!Flag)
{
Count= 1;
for(int i1= X-1, j1= Y+ 1, i2= X+ 1, j2= Y-1;Legal(i1)&& Legal(j1)|| Legal(i2)&& Legal(j2);i1--, j1++, i2++, j2--)
{
int LastCount= Count;
if(Legal(i1)&& Legal(j1)&& ChessBoard.Status[i1][j1]== Ply)
{
Count++;
}
if(Legal(i2)&& Legal(j2)&& ChessBoard.Status[i2][j2]== Ply)
{
Count++;
}
if(LastCount== Count)
break;
if(Count== ChessBoard.MINBOX)
{
Flag= 1;
return true;
}
}
}
// 搜索135度角是否满足ChessBoard.MINBOX
if(!Flag)
{
Count= 1;
for(int i1= X-1, j1= Y-1, i2= X+ 1, j2= Y+ 1;Legal(i1)&& Legal(j1)|| Legal(i2)&& Legal(j2);i1--, j1--, i2++, j2++)
{
int LastCount= Count;
if(Legal(i1)&& Legal(j1)&& ChessBoard.Status[i1][j1]== Ply)
{
Count++;
}
if(Legal(i2)&& Legal(j2)&& ChessBoard.Status[i2][j2]== Ply)
{
Count++;
}
if(LastCount== Count)
break;
if(Count== ChessBoard.MINBOX)
{
Flag= 1;
return true;
}
}
}
return false;}
void Play(int Fir){
system(“cls”);
Draw();
//SetConsoleTextAttribute(hConsole, FOREGROUND_RED| FOREGROUND_INTENSITY);
int CurPly=Fir;
while(1)
{
int TTop= ChessBoard.Stack.Top;
if(ChessBoard.Step>= 256)
{
Gotoxy(11,65);
printf(“游戏结束”);
}
if(Prompt(CurPly, ChessBoard.Stack.Record[TTop][0], ChessBoard.Stack.Record[TTop][1]))
{
TTop= ChessBoard.Stack.Top;
if(Win(CurPly, ChessBoard.Stack.Record[TTop][0], ChessBoard.Stack.Record[TTop][1]))
{
Gotoxy(11, 65);
if(CurPly== 1)
printf(“玩家一胜利n”);
else
printf(“玩家二胜利n”);
break;
}
CurPly= CurPly% 2+1;
ChessBoard.Step++;
}
else if(ChessBoard.Step)
{
CurPly= CurPly% 2+1;
ChessBoard.Step--;
}
} }
char Reset(){
char Decide;
Gotoxy(15, 65);
printf(“是否重玩？”);
Gotoxy(17, 65);
printf(“'y' Orz 'n'n”);
Gotoxy(19, 65);
Decide= getchar();
return Decide;}
int main(){
system(“mode con cols=80 lines=33”);
Loop :
//system(“color 2f”);
InitChessBiard();
Logo();
Play(Login());
if(Reset()== 'Y'|| Reset()== 'y')
{
system(“cls”);
goto Loop;
}
system(“pause”);
return 0;}
第二篇：数据结构课程设计
课 程 设 计 任 务 书
信息 学院 信息管理与信息系统 专业 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 八、心得体会 通过这次课程设计，我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要勤动手，多实践。真正将这个程序做出来很不容易，但只要只要用心去做，总会有收获,特别是当我遇到问题时，通过向同学请教,最后终于找到方法时,并理解代码的含义时，心中是无比喜悦的。编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。第五篇：数据结构课程设计
![下载数据结构课程设计-五子棋[★]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 