第一篇：数据结构课程设计 背包问题的求解
2009届 电子信息科学与技术专业 数据结构课程设计
背包问题的求解
摘要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词 背包问题；
递归算法；
1问题描述
1.1问题描述
背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
1.2基本思想
（1）分别输入n件物品的重量和价值。（2）采用递归寻找物品的方案。
（3）输出最佳的装填方案，包括选中的是哪几种物品，总价值为多少。
2问题分析
背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中递归方法是比较简化程序，也比较难理解的一个。
设n件物品的重量分别为w0,w1,„,wn-1,物品的价值分别为v0,v1,„,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组option[],设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop[]，嘉定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，急需考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。2009届 电子信息科学与技术专业 数据结构课程设计 对于第i件物品的选择有两种可能：
（1）物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择；
（2）物品i不被选择，这种可能性仅当不包物品i也有可能会找大价值更大的方案的情况。
就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。
采用option[]和cop[]两个数组，来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。
3数据结构描述
背包问题结构体：
struct{
int weight;
int value;
}a[N];4算法设计
4.1程序流程图
2009届 电子信息科学与技术专业 数据结构课程设计
图4-1 程序流程图
4.2算法设计
根据问题分析中的思想写出递归算法如下：
find（物品当前选择已达到的重量和tw,本方案可能达到的总价值为tv）｛
/*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）｛
将物品i包含在当前方案中；
if(i 以当前方案作为临时最佳方案保存； 恢复物品i不包含状态； ｝ 2009届 电子信息科学与技术专业 数据结构课程设计 /*考虑物品i不包含在当前方案中的可能性*/ if（不包含物品i仅是可考虑的） if(i 以当前方案作为临时最佳方案保存； ｝ void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) /*物品i包含在当前方案的可能性*/ { cop[i]=1;if(i /*物品i不包含在当前方案的可能性*/ if(i opion[k]=cop[k];maxv=tv-a[i].value;} } 5详细程序清单 详细程序清单见附录。 6程序运行结果 背包问题求解界面如图6-1所示。 图6-1 背包问题求解界面 程序调试成功。 在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。 7心得体会 通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。 2009届 电子信息科学与技术专业 数据结构课程设计 在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个思想。 参考文献 [1] 徐孝凯.数据结构课程实验.北京：清华大学出版社，2002:100-132 [2] 张乃笑.数据结构与算法.北京：电子工业出版，2000:3-5 [3] 严蔚敏.数据结构（C语言版）.北京： 清华大学出版社，2002:100-132 [4] 李春葆.数据结构（C语言篇）习题与解析（修订版）.北京：清华大学出版，2000:45-66 Knapsack problem solving Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009届 电子信息科学与技术专业 数据结构课程设计 附录：详细程序清单 #include /*可实现最大总价值*/ int opion[N]，cop[N]; struct{ int weight; int value; }a[N];int n; void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) { cop[i]=1;if(i /*方案的选择*/ /*当前方案的选择*/ /*背包问题结构体*/ /*物品种数*/ /*物品i包含在当前方案的可能性*/ 7 2009届 电子信息科学与技术专业 数据结构课程设计 if(tv-a[i].value>maxv) /*物品i不包含在当前方案的可能性*/ if(i 第%d种物品（重量，价值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的总重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k printf(“最佳装填方案是：n”);for(k=0;k 数据结构课程设计 迷宫求解 学院：湖北工业大学计算机学院 教师：沈华老师 班级：12网络工程1班 学号：1210322118 姓名：饶进阳 时间：2013年12月22日 目 录 问题描述 .........................................................思路解析 .........................................................程序流程 .........................................................核心代码 .........................................................源程序代码........................................................程序运行实例.....................................................课设总结 .........................................................3 4 5 6 12 14 迷宫求解 问题描述： 可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； 要求： 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 比如这是一个迷宫 电脑找出的出路 思 路 设定当前位置的初值为入口位置： do｛ 若当前位置可通，则｛ 将当前位置插入栈顶；} 若该位置是出口位置，则结束； 否则切换当前位置的东邻块为新的当前位置； 否则｛ 若栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；} 若{ 栈不空但栈顶位置的四周均不可通，则删去栈顶位置；} 若{ 栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝ ｝while(栈不空)｛栈空说明没有路径存在｝ PS：类似动态求解方法 程序流程 第一次用visio做程序框图，所以只把程序的大概流程画出来了。 核心代码 //栈相关操作 int initlStack(Stack *S)int pushStack(Stack S, coordinate e)int popStack(Stack S, coordinate *e)int getTop(Stack S, coordinate *e)void show(Stack S) //创建一个迷宫 int creatMaze(Maze *m) //打印出一个迷宫 void showMaze(Maze *m) //求当前结点的下一个通路 coordinate passNext(Maze *m, int i, int j)//求迷宫路径 int solveMaze(Maze *m, Stack S)//模拟出路径 void showRoad(Maze m, Stack S) 程序源码： #include #define MAX 100 #define SIZE sizeof(Node)//**************************** //栈 typedef struct { int x;//行 int y;//列 }coordinate;//坐标 typedef struct node{ coordinate data;struct node *next;}Node, *Stack; //栈的相关操作 //栈初始化 //带头结点的链栈 int initlStack(Stack *S){(*S)=(Node *)malloc(SIZE);if((*S)== NULL){ return 1;}(*S)->next = NULL;return 0;} //入栈 int pushStack(Stack S, coordinate e){ Node *p; p =(Node *)malloc(SIZE);p->data.x = e.x;p->data.y = e.y;p->next = S->next;S->next = p;return 0;} //出栈 int popStack(Stack S, coordinate *e){ Node *p;if(S->next == NULL){ printf(“nStack is empty!n”); return 2;} e->x = S->next->data.x;e->y = S->next->data.y;p = S->next;S->next = p->next;free(p);return 0;} //读取栈顶 int getTop(Stack S, coordinate *e){ e->x = S->next->data.x;e->y = S->next->data.y;return 0;} //显示 void show(Stack S){ Node *p;p = S->next;while(p!= NULL){ printf(“%d %d <-”, p->data.x, p->data.y); p = p->next;} printf(“startn”);} //*************************** //*************************** //迷宫 typedef struct { int row;int col;int arr[MAX][MAX];}Maze; //创建一个迷宫 int creatMaze(Maze *m){ int i, j;printf(“nplease input Maze's row and col:n”);scanf(“%d%d”, &(m->row), &(m->col));printf(“nplease input the Maze's message:(0 is ok),(1 is no)n”);for(i = 0;i <= MAX1;j++){ m->arr[i][j] = 1; } } for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ scanf(“%d”, &(m->arr[i][j])); } } return 0;} //显示迷宫信息 void showMaze(Maze *m){ int i, j;printf(“nthe Maze you hava input:n”);for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ printf(“%d ”, m->arr[i][j]); } printf(“n”);} printf(“nlike this:n”);for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ if(m->arr[i][j]!= 0){ printf(“■ ”); } else { printf(“□ ”); } } printf(“n”);} } //求当前结点的下个通路 //顺时针找 coordinate passNext(Maze *m, int i, int j){ coordinate k;if(m->arr[i][j+1] == 0){//东 k.x = i; k.y = j+1; return k;} if(m->arr[i+1][j] == 0){//南 k.x = i+1; k.y = j; return k;} if(m->arr[i][j-1] == 0){//西 k.x = i; k.y = j-1; return k;} if(m->arr[i-1][j] == 0){//北 k.x = i-1; k.y = j; return k;} else {//不存在 k.x =-1; k.y =-1; return k;} } //求解迷宫 int solveMaze(Maze *m, Stack S){ int i, j;int boolean;coordinate a;i = 1;j = 1;do { if(m->arr[i][j] == 0){ a.x = i; a.y = j; m->arr[i][j] = 2; pushStack(S, a); if(i == m->row && j == m->col){ return 0; } } a = passNext(m, i, j); if(a.x!=-1){ i = a.x; j = a.y; continue; } else if(a.x ==-1){ boolean = popStack(S, &a); if(2 == boolean){ return 0; } getTop(S, &a); i = a.x; j = a.y; } }while(S->next!= NULL);return 0;} //模拟出路径 void showRoad(Maze m, Stack S){ coordinate e;int i, j;if(S->next == NULL){ printf(“nSorry!you can't go out the Maze!n”);} while(S->next!= NULL){ popStack(S, &e); m.arr[e.x][e.y] =-1;} for(i = 1;i <= m.row;i++){ for(j = 1;j <= m.col;j++){ if(m.arr[i][j] >= 0){ printf(“■ ”); } else { printf(“□ ”); } } printf(“n”);} } //*************************** //主函数 int main(){ Maze m;Stack S;printf(“※ 欢迎玩耍迷宫求解游戏 ※n”);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m, S);printf(“nthe root is here:n”);show(S);showRoad(m, S);return 0;} 程序运行结果： 第一步：输入迷宫行列大小 第二步：输入迷宫信息 第四步：程序会自动求出路径 课 设 总 结 敬爱的沈华老师您好，感谢您这半年对我们的教诲，说实话，很喜欢上您的课，您上课的风采深深的吸引了我，每次上您的课，我都听得特别认真。好吧，言归正传，谈谈这次课程设计的感想。 首先看到这道题的时候，真心没多少思路，我抱着试一试的态度，去网上搜索相关的算法。网上资源蛮多的，刚开始就搜索到了，严蔚敏老师的相关算法讲解视频，虽然她讲的是思想（就是他并没有源程序的实现），但是足够让我理解了基本算法流程。 其实先开始都不知道怎么下笔，但是我还是想着从基本栈开始写吧，慢慢写着，程序大概思想框架就成型了，最后在实现求解迷宫路径的时候，着手用笔在草稿纸上面模拟，然后才敲到编译器中，最好几经调试，终于得到了想要的结果。 做完这次课设后，深刻的体会到一些道理，在信息时代，解决问题的最好方法是运用现代的信息资源。并且在实际中，开始没思路的事，慢慢完成小部分，那么你的总体思维会渐渐地成型。 做事做人，平心气和的干，总会得到成功！ 数据结构实验二 求解约瑟夫问题 问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。 问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法： void Josephus(int n, int m,int s) { //生成表头节点，空单循环链表 LNode * HL = new LNode; HL-> next = HL; int i;//生成含有 n 个节点的、节点值依次为1，2……，n的带表头节点的循环单链表 For(i = n;i>=1;i--) { LNode * newptr = new LNode; Newptr-> data = i; newptr-> next = HL-> next; HL-> next = newptr;} //从表头开始顺序查找出第s个节点，对应第一个开始报数的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i ap = cp; cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1个人出列 for(i=1;i //顺序查找出待出列的人，即为循环结束后cp所指向的节点 for(int j=1;j cout << cp->data <<” “;//从单链表中删除cp节点 ap-> next = cp-> next;delete cp;//使cp指向被删除节点的后续节点 cp = ap-> next;//若cp指向了表头节点，则后移ap和cp指针 if(cp = = HL){ ap = HL;cp = HL-> next;} } //使最后一人出列 count << HL->next-> data << end1; //删除表头节点和表头附加节点 delete HL->next; delete HL;} 补充操作系统练习： 1、有一个虚拟存储系统, 每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1 试给出下列情形下的缺页次数: (1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢? 2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下： 最大需求量 已分配资源量 剩余资源量 A B C A B C A B C P1 8 P2 4 P3 10 1 P4 3 P5 5(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？ 3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号 进入时刻 估计运行时间 优先级 JOB1 8：00 90分钟 JOB2 8：10 30分钟 JOB3 8：30 20分钟 JOB4 8：50 15分钟 JOB5 9：20 10分钟 JOB6 9：40 5分钟系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…） （2）试计算出作业的平均周转时间. 分类号编号 华北水利水电大学 North China Institute of Water Conservancy and Hydroelectric Power 课程设计 题目舞伴问题 院系信息工程学院 专业计算机科学与技术 姓名贾宁 指导教师杨彬 第一章需求分析........................................................................................................................2 1.1问题描述......................................................................................................................2 1.2 基本要求.....................................................................................................................2 1.2.1 输入及输出格式..............................................................................................2 1.2.2 程序所完成的功能..........................................................................................2 第二章概要设计........................................................................................................................3 2.1 数据结构.....................................................................................................................3 2.2 程序模块.....................................................................................................................4 2.3 模块调用及算法.........................................................................................................5 第三章详细设计........................................................................................................................7 3.1 操作实现.............................................................................................................7 3.2 算法实现.............................................................................................................8 第四章编码调试......................................................................................................................10 4.1 调试环境...................................................................................................................10 4.2 调试方法...................................................................................................................10 4.3 调试项目及调试结果...............................................................................................10 4.3.1 登陆测试........................................................................................................10 4.3.2 加载学生信息................................................................................................11 4.3.3 学生配对调试................................................................................................12 4.3.4 显示总配对....................................................................................................13 4.3.5 查询配对........................................................................................................13 第五章总结..............................................................................................................................15 参考文献..................................................................................................................................16 附录系统源代码......................................................................................................................17 第一章需求分析 1.1问题描述 一班有m个女生、n个男生(m不等于n), 举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。 1.2 基本要求 1.2.1 输入及输出格式 输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。在读入男女生信息时，可以从文件中直接读取学生的姓名和性别信息。 输出显示时显示每首歌的配对情况，包括对应配对学生的姓名、性别以及编号。可以输出整个舞池配对过程的所有配对情况。将输出显示的内容对应写入到指定的文件中。 1.2.2 程序所完成的功能 从文件或者手动输入班级的学生信息，包括姓名和性别基本信息，根据性别使男女生分别坐在舞池两边的座位上，学生的座位编号顺序生成，且一旦编号确定，将不再发生变化。 每一首歌曲播放时，依次从男女生队列中出来学生进行配对，由于男女生人数不一致，会使某个队列中剩下若干学生配对不成功，配对不成功者等待下首歌时再进行配对。该首歌结束时，配对成功的学生再回到座位上。然后再依次进行配对，未成功者等待下首歌再进行配对。 配对成功时，会显示本首歌的详细配对情况，以及整个过程的配对情况，并且可以将配对情况写入到文件。 根据男女生的姓名或者某首歌曲的名字可以查询到对应的配对情况。 第二章概要设计 2.1 数据结构 学生座位队列： ADT StuQueue{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 数据关系：R={ 操作结果：向Q中循环加入信息 void EnQueue2(StuQueue&Q,FinalStustu)初始条件：循环队列已存在，非首次进循环队列 操作结果：向Q中添加信息 FinalStuDeQueue(StuQueue&Q)初始条件：循环队列已存在 操作结果：使队列头的元素出队列，且返回FinalStu类型值 }ADT StuQueue //学生座位队列 音乐队列： ADTMusicList{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 数据关系：R={ voidInsertMusic(MusicList&MList,char* name)初始条件：该链表已存在 操作结果：向链表中添加数据 }ADT MusicList； 临时队列： ADTTempQList{ 数据对象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 数据关系：R={ voidEnTempQueue(TempQList&TQL,FinalStustu)初始条件：队列TQL已存在操作结果：向TQL中添加信息 FinalStuDeTempQueue(TempQList&TQL)初始条件：队列TQL存在 操作结果：取出队列的对头元素，返回FinalStu类型 }ADT TempQList； 2.2 程序模块 本系统主要包括登陆模块、学生入座、自动配对、显示配对过程以及查询配对信息模块。 登陆：输入正确的用户名以及密码，方可进入系统，连续输入错误三次则禁止进入系统。 学生入座：以不同的方式获取学生信息后，根据学生性别依次进入两个循环队列，并为每个学生唯一编号。 自动配对：每首歌开始时，男女生依次从坐席中出来进行本首歌的配对，配对不成功者等待下首歌继续配对，下首歌时，上首歌未配对成功者本首歌先进行配对。 显示配对过程：在播放歌曲的过程中，显示播放的歌曲信息，以及本首歌的配对信息。 查询配对：根据男女生的姓名查出两人的在哪一首歌进行过配对，根据歌曲名称查询出本首歌的配对信息。 文件操作：将配对情况及学生的座位信息写入文件 根据系统模块的划分，本系统的功能模块图如图2-1所示 舞池配对系统登陆学生入座自动配对显示配对过程查询配对结果 图 2-1 功能模块 2.3 模块调用及算法 登陆成功后进入主界面，进入主界面后，需要先运行学生入座模块，方能进行下边的操作。学生入座后会得到相关的基本信息。之后调用配对模块函数，进行学生的配对。学生配对成功后，才能利用显示配对过程进行显示配对的情况，后续的查询配对模块也必须在配对成功的基础上进行。模块间的调用流程如图2-2所示 主函数登陆函数入座模块配对模块显示配对查询结果 图 2-2 模块调用 在进行配对过程中用到算法，在每首歌配对时，依次从男女生队列中出来一个学生，进入到临时队列，从临时队列中获取配对的情况。在本首歌结束，下首歌开始之前，让临时队列中的男女在分别根据性别入队，依次循环，每次调用配对函数，实现学生的循环配对。 第三章详细设计 3.1 操作实现 本系统包含七个文件。设计分有欢迎界面，登陆系统，入队函数，配对函数，显示函数，查询函数等。登陆界面是整个系统的入口，其主要是让合法人员进入系统，入队函数主要让学生进入男女队列，配对函数主要是根据每首歌曲把男女生进行配对，显示函数主要是显示男女生的配对情况，查询函数主要是根据男女生姓名和歌曲名查找配对情况。 系统首先通过程序调用void main()进入欢迎界面和系统登陆界面，根据用户的帐号和密码登陆成功后进入主菜单。根据用户的选择可分别进入：1.学生就坐；2.每曲配对；3.显示结果；4.查询配对；5.退出。 选择“1.学生就坐”项，会显示学生信息来源，包括“1.按班级获取(推荐)”“2.手动输入...”两项可供选择。其中，1是从文件中获取学生信息，2是用户手动输入学生信息。 选择“2.每曲配对”项，会显示播放歌曲的类型，有“1.流行”“2.复古”两个音乐风格可供选择，当用户选择其中一个风格并确定播放后，会显示出当前播放的歌曲名字和所配对的男女生。 选择“3.显示结果”项，会有“1.学生座位信息”和“2.学生配对信息”两项操作可供选择。当选择1，会把学生就坐后的信息显示出来，选择2，会把每首歌学生的配对情况显示出来。 选择“4.查询配对”项，也有两个操作可供选择，分别是“1.按学生姓名”“按歌曲名”两项。选择1，会根据用户输入的男女生姓名查看他们的配对情况，选择2，会根据用户输入的歌曲名称显示每首歌曲学生的配对情况。 选择“5.退出”项，会出现感谢使用系统界面，并按任意键退出系统。本系统的主流程图如图3-1 所示 开始欢迎和登陆界面主界面1 ？NN2 ？N3 ？N4 ？N5 ？Y结束程序Y学生就坐Y每曲配对Y每曲配对显示Y查询配对情况 图 3-1 主流程 3.2 算法实现 定义学生结构体FinalStu，将学生的信息放到本结构体中，定义两个循环队列Boys和Girls队列，分别存储男女生的座位信息。定义MusicList循环链表，用于存放音乐信息。定义TempQueue队列，用于临时存放从男女生队列中出来的学生信息。创建一个存放每首歌配对情况的数组stuTable[]，用来存放播放该首歌曲时男女生的信息。 每一首歌开始时，男女生依次用Boys和Girls队列中出对，依次进入临时队列TempQueue，从TempQueue中读取男女生的信息，放到stuTable数组中，表示该首歌的 8 配对情况。下首歌开始时，让临时队列中的学生再根据性别依次进入男女循环队列。同时将存放歌曲的MusicList循环链表指针后移，播放下首歌曲，再执行上述操作，便可实现循环配对。 第四章编码调试 4.1 调试环境 硬件环境：Intel 1GHZ处理器（或AMD同类处理器），512M或以上内存容量，10G或以上硬盘容量,可连接互联网的相关设备。 软件环境（软件、操作系统）：Windows XP（或Windows 2003或Windows vista或Windows 7）操作系统，Microsoft Visual Studio 2008。 4.2 调试方法 为了提高测试效率，降低测试成本，本测试方案采用黑盒法设计基本的测试方案，再用白盒法补充一些方案。在黑盒法测试方案中，采用等价划分技术，把所有可能的数据划分成几个等价类。 4.3 调试项目及调试结果 4.3.1 登陆测试 用户根据用户名及密码登陆系统，内置用户为Admin，密码为888888。登陆成功如图4-1所示，登陆失败如图4-2所示 图 4-1 登陆成功 图 4-2 登陆失败 4.3.2 加载学生信息 可以从文件或者手动输入学生信息，从文件中选择时，可以选择不同的文件，其运行结果如图4-2 及图4-3 所示 图 4-3 选择信息来源 图 4-4 显示获取信息 4.3.3 学生配对调试 在进行配对之前，需要先将音乐信息加载到系统中，其加载过程如图4-5所示 图 4-5 加载音乐 学生就位及音乐加载成功后，开始播放音乐，并进行配对，其音乐播放情况及每首歌曲的配对情况如图4- 6、图4-7及图4-8所示 图 4-6 配对开始 图 4-7 播放下一首 图 4-8 循环配对 4.3.4 显示总配对 在整个过程结束后，停止播放音乐，可以显示整个过程的配对情况，其结果如图4-9所示 图 4-9 显示配对结果 4.3.5 查询配对 可以根据男女生的姓名查询两人的配对情况，当输入两个学生姓名时，显示在整个过程中的配对情况，其结果如图 4-10所示 图4-10 姓名查询配对 根据每一首歌曲情况查询在本首歌曲中的配对情况，其结果如图4-11 所示 图 4-11 按歌名查找 第五章总结 这次的课程设计懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的，在构思总体架构时，需要先将需求分析搞清楚，需要在找到了需要解决的问题后，再想办法解决该问题。而不是在设计过程中边想边解决，需要先将所有可能的问题都考虑到，再依次解决。在整个系统设计完成后，如果再遇到新的问题，可以对系统进行适当的更新。 调试时经常会遇到这样那样的错误，有的时候是因为一些最基本的错误，如标点的中英错误，括号的匹配问题，数据的输入错误等。当然，也有很多地方是因为用错了解决方法。在设计的过程中，最能体现出的缺点就是基础不扎实，本可以避免的错误却一再出现。 在实现舞池配对问题过程中，需要使学生循环配对，此程序设计的是当一个光盘的音乐播放结束时，整个配对过程随之结束，而没有让学生再次进去坐席，导致不再从新将学生入座，就无法实现配对。设计的是在每首歌开始之前学生进入队列，可以改为当某个学生坐席为空时，随即让学生再次进入队列，可以解决不能重复换歌曲的问题。 刚开始的时候我直接在开发环境下一边看题一边写代码，瞪了半天什么也没写出来，于是我便先开始在纸上画画写写，将事件的整个过程画下来，然后考虑怎么才能运用代码来实现，一边思考一边写一些粗略的代码，最后从上到下执行代码看看是不是符合题目要求。有没有什么漏洞。等这些完成以后，再在开发环境下将代码完善、编译和调试。虽然说代码还有许多要改进的地方，有的功能还不够完善，可毕竟是自己亲自写出来的，对于程序的条理有了一个清晰的了解，对编程也有了更加深刻的认识。 参考文献 [1] 谭浩强.C程序设计(第三版)[M].北京：清华大学出版社，2005.[2] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，1997.[3] 陆丽娜.软件工程.北京：经济科学出版社，2005.[4] 姚诗斌.数据库系统基础.计算机工程与应用,1981年第8期 附录系统源代码 #include int idCount=1000;//全局变量控制学生id自增 int length;//记录每首歌配对的数量 int index=0;//记录最终配对表的下标 usingnamespace std;//舞池就坐后的学生信息结构体 struct Admin { char name[15];char passWord[15];Admin *next;};Admin *admin;struct FinalStu { char name[15];char sex[3];int id;};FinalStu stu[STU_SIZE];FinalStu stuSeat[STU_SIZE];//用来存放入座后的学生信息 FinalStu stuTable[STU_SIZE][2];//用来存放没收歌曲的配对情况 //舞池座位 struct StuQueue { FinalStu *base;int front;int rear;};StuQueue Boys;//男生队列 StuQueue Girls;//女生队列 //初始化学生坐席 void InitQueue(StuQueue &Q){ Q.base=(FinalStu*)malloc(MAXQSIZE*sizeof(FinalStu));if(Q.base==NULL) return;Q.front=Q.rear=0; } //学生就坐,首次入队，需要获取学生的id void EnQueue(StuQueue &Q,FinalStu stu){ int i=100;if((Q.rear+1)%MAXQSIZE==Q.front) return;strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=idCount++;Q.rear=(Q.rear+1)%MAXQSIZE;} //非首次入队，不需获取学生的id void EnQueue2(StuQueue &Q,FinalStu stu){ strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=stu.id;Q.rear=(Q.rear+1)%MAXQSIZE;} //从坐席上出来 FinalStu DeQueue(StuQueue &Q){ FinalStu stu;if(Q.rear!=Q.front){ stu=Q.base[Q.front];} Q.front=(Q.front+1)%MAXQSIZE;return stu;} //存放音乐信息 struct Music { char M_Name[15];Music *next;};//存放音乐链,循环链表 struct MusicList { Music *head; Music *tail;};MusicList ML;Music *M_p;//初始化指针 void InitMusic(MusicList & MList){ MList.head=MList.tail=(Music *)malloc(sizeof(Music));MList.head->next=NULL;} //向音乐链表中添加音乐 void InsertMusic(MusicList &MList,char* name){ Music *p=(Music*)malloc(sizeof(Music));MList.tail->next=p;strcpy(p->M_Name,name);MList.tail=p;MList.tail->next=MList.head;} //临时队列，用于存放从男女生队列中配对成成功的学生信息 struct TempQueue { FinalStu stu;TempQueue * next;}; struct TempQList { TempQueue *front;TempQueue *rear;};TempQList TempQL;//临时队列，用于存放每次出来的男女生信息 void InitQList(TempQList &TQL){ TQL.front=TQL.rear=(TempQueue *)malloc(sizeof(TempQueue));TQL.front->next=NULL;} void EnTempQueue(TempQList & TQL,FinalStu stu){ TempQueue *p=(TempQueue *)malloc(sizeof(TempQueue));p->stu=stu;p->next=NULL;TQL.rear->next=p;TQL.rear=p;} FinalStu DeTempQueue(TempQList &TQL){ FinalStu stu;TempQueue *p;p=TQL.front->next;if(p==TQL.rear){ stu=p->stu; TQL.rear=TQL.front;} else { stu=p->stu; TQL.front->next=p->next;} free(p);return stu;} //==========配对信息存放=================== struct MatchList { char musicName[20];FinalStu stu[2];};MatchList matchTable[SIZE];//从键盘读入学生信息 void GetInfKey(){ for(int i=0;i cout<<“输入第”< scanf(“%s”,stu[i].name); cout<<“输入第”< scanf(“%s”,stu[i].sex);} } //学生入座 void StudentSit(){ for(int i=0;i if(strcmp(stu[i].sex,“男”)==0) EnQueue(Boys,stu[i]); else EnQueue(Girls,stu[i]);} } //获取就坐后的男女生性别、姓名、编号,stuSeat[] 存放就坐后的学生信息，包括学生编号 void GetStuSeat(){ int i=0; int j=0;i=Boys.front;j=Girls.front; while(i!=Boys.rear){ stuSeat[i]=Boys.base[i]; i++;} while(j!=Girls.rear){ stuSeat[i]=Girls.base[j]; j++; i++;} } //将就座的学生信息写入文件 int InFileStuSeat(){ FILE *fp_Seat;int res=0;if((fp_Seat=fopen(“Seat.txt”,“wt”))==NULL){ cout<<“读取学生座位信息失败！！”; return-1;} fprintf(fp_Seat,“姓名t性别t序号n”);for(int i=0;i fprintf(fp_Seat,“%st%st%d”,stuSeat[i].name,stuSeat[i].sex,stuSeat[i].id); fprintf(fp_Seat,“n”); res++;} fclose(fp_Seat);return res;} void PrintStuSeat(){ cout<<“ttt姓名t性别t序号”< cout<<“ttt”< cout< cout<<“打开文件失败！！”; return;} while(!feof(fp_Admin)){ Admin *p=(Admin *)malloc(sizeof(Admin)); p->next=NULL; fscanf(fp_Admin,“%s%s”,p->name,p->passWord); q->next=p; q=p;} fclose(fp_Admin);} //从文件获取学生信息 void ReadStuFile(int res){ FILE *fp;if(res==1){ if((fp=fopen(“student1.txt”,“rt”))==NULL) { cout<<“打开文件失败！！”< return; } } elseif(res==2){ if((fp=fopen(“student2.txt”,“rt”))==NULL) { cout<<“打开文件失败！！”< return; } } int i=0;while(!feof(fp)) { fscanf(fp,“%s%s”,stu[i].name,stu[i].sex); i++; if(i>=STU_SIZE) break; } fclose(fp);} //加载音乐信息 int LoadMusic(int cd){ char music[5][20];//存放从文件中获取的音乐名称 int res=0;FILE *fp_music;if(cd==1){ if((fp_music=fopen(“music1.txt”,“rt”))==NULL) { cout<<“打开音乐文件失败！！”< return-1; } } elseif(cd==2){ if((fp_music=fopen(“music2.txt”,“rt”))==NULL) { cout<<“打开音乐文件失败！！”< return-1; } } for(int j=0;j<5;j++){ if(fread(music[j],20*sizeof(char),1,fp_music)==1) res++; } fclose(fp_music);InitMusic(ML);for(int i=0;i<5;i++){ InsertMusic(ML,music[i]);} return res;} int InFileMatchTable(){ FILE *fp_MTable;if((fp_MTable=fopen(“matchtable.txt”,“wt”))==NULL){ cout<<“打开文件失败~~~~”< return-1;} fprintf(fp_MTable,“歌曲名称t姓名t性别t序号t姓名t性别t序号n”);for(int i=0;i fprintf(fp_MTable,“%stt%st%st%dt”,matchTable[i].musicName,matchTable[i].stu[0].name,matchTable[i].stu[0].sex,matchTable[i].stu[0].id); fprintf(fp_MTable,“%st%st%dn”,matchTable[i].stu[1].name,matchTable[i].stu[1].sex,matchTable[i].stu[1].id);} fclose(fp_MTable);return 1;} void StudentSitAgain(){ FinalStu stu;while(TempQL.front!=TempQL.rear){ stu=DeTempQueue(TempQL); if(strcmp(stu.sex,“男”)==0) EnQueue2(Boys,stu); else EnQueue2(Girls,stu);} } //播放歌曲 void PlayMusic(){ cout<<“tt正在播放:t”< void NextMusic(){ M_p=M_p->next;if(M_p==ML.head){ M_p=ML.head->next;} } //学生配对 void Match(){ //FinalStu student[STU_SIZE];intstatic i=0;int j=0;length=0;while(Boys.front!=Boys.rear&&Girls.front!=Girls.rear){ EnTempQueue(TempQL,DeQueue(Boys));//从男生队列中出来进入临时队列 EnTempQueue(TempQL,DeQueue(Girls));//从女生队列中出来进入临时队列 length++;//记录每首歌的配对数 } //从临时队列中将信息赋值给表 TempQueue *tem=TempQL.front->next;while(tem){ strcpy(matchTable[index].musicName,M_p->M_Name); strcpy(matchTable[index].stu[0].name,tem->stu.name); strcpy(matchTable[index].stu[0].sex,tem->stu.sex); matchTable[index].stu[0].id=tem->stu.id; //----每曲歌的配对情况 strcpy(stuTable[j][0].name,tem->stu.name); strcpy(stuTable[j][0].sex,tem->stu.sex); stuTable[j][0].id=tem->stu.id; tem=tem->next; //------整个播放过程的配对表 strcpy(matchTable[index].stu[1].name,tem->stu.name); strcpy(matchTable[index].stu[1].sex,tem->stu.sex); matchTable[index].stu[1].id=tem->stu.id; //----每首歌配对表 strcpy(stuTable[j][1].name,tem->stu.name); strcpy(stuTable[j][1].sex,tem->stu.sex); stuTable[j][1].id=tem->stu.id; tem=tem->next; index++; j++;} } //显示每首歌配对情况 void PrintEachMatch(){ cout< //length为每首歌的配对长度 { cout< cout< 1、学生就坐”;cout<<“t”<<“ 2、每曲配对”< 3、显示结果”;cout<<“t”<<“ 4、查询配对”< 5、退出”; } //配对显示 void PrintMatchTable(){ cout<<“歌曲名称t姓名t性别t序号t姓名t性别t序号”< cout< cout< //从文件读取数据 int res; cout<<“请选择班级：”< cout<<“1.三年一班t2.三年二班”< cin>>res; if(res==1) { ReadStuFile(1); } elseif(res==2) { ReadStuFile(2); } break;case 2: cout<<“开始输入....”< GetInfKey(); //键盘键入数据 break;default: cout<<“输入有误，再见”< break;} } void MusicMenu(){ cout<<“请选择要放入的光盘类型：”< i=LoadMusic(1);else i=LoadMusic(2);if(i){ M_p=ML.head->next;//p指向第一首歌 cout<<“歌曲光盘已就位,是否现在播放(Y/N)”< cin>>ch; InitQList(TempQL);//初始化临时队列 if(ch=='Y'||ch=='y') { system(“cls”); PlayMusic(); Match(); PrintEachMatch(); } cout<<“按n进行下一首歌曲、、n”; cout<<“按q停止播放音乐、、”< cin>>ch; while(ch=='n'||ch=='N') { system(“cls”); Next(); cout<<“按n进行下一首歌曲、、n”; cout<<“按q停止播放音乐、、”< cin>>ch; } if(ch=='q'||ch=='Q') return;} } void Welcome(){ cout<<“tttt欢迎进入进入舞池~~~~”< Admin *p=admin->next; cout<<“ttt请输入您的用户名：”; cin>>userName; cout<<“ttt请输入您的密码：”; cin>>key; while(p) { if(strcmp(p->name,userName)==0) break; p=p->next; } if(!p) { system(“cls”); cout<<“ttt输入的用户名不存在~~~~~”< continue; } if(p) { if(strcmp(p->passWord,key)==0) { system(“cls”); cout<<“tttt欢迎回来.”; Sleep(500); system(“cls”); cout<<“tttt欢迎回来..”; Sleep(500); system(“cls”); cout<<“tttt欢迎回来...”; Sleep(500); //system(“cls”); break; } else { system(“cls”); cout<<“ttt输入的密码错误、、、”< continue; } } } if(i>=3){ cout<<“ttt您今天的机会已经用完，再见”; exit(0);} } void ShowMessage(){ system(“cls”);int res;cout<<“ttt选择要操作的信息:”< cout<<“ttt座位信息如下:”< PrintStuSeat(); char ch; cout<<“是否将该信息写入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileMatchTable()) { cout<<“数据已写入文件...”< } } } elseif(res==2){ PrintMatchTable(); char ch; cout<<“是否将该信息写入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileMatchTable()) cout<<“数据已写入文件...”< } Sleep(3000);} } void Quit(){ system(“CLS”); printf(“nnnnnnnnttt ^o^”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使^”); Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使用”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使用^o^”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使用^o^nntttt -----”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使用^o^nntttt -----GoodBye!”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^欢迎下次使用^o^nntttt -----GoodBye!n”);} void CheckByName() //根据姓名查询配对情况 { char boyName[15];char girlName[15];cout<<“请输入男生姓名:”;cin>>boyName;cout<<“请输入女生姓名:”;cin>>girlName;int count=0;for(int i=0;i if(strcmp(matchTable[i].stu[0].name,boyName)==0&& strcmp(matchTable[i].stu[1].name,girlName)==0) { count++; } } if(count==0){ cout<<“未找到配对情况:”;} else { cout<<“ttt查询的学生的配对情况如下:”< cout<<“歌曲名称t姓名t性别t编号t姓名t性别t编号”< for(int j=0;j { if(strcmp(matchTable[j].stu[0].name,boyName)==0&& strcmp(matchTable[j].stu[1].name,girlName)==0) { cout< cout< } } } } void CheckByMusic(){ char MusicName[15];cout<<“请输入歌名:”;cin>>MusicName;int count=0;for(int i=0;i if(strcmp(matchTable[i].musicName,MusicName)==0) { count++; } } if(count==0){ cout<<“未找到该歌曲~~~~”; } else { cout<<“ttt查询的学生的配对情况如下:”< cout<<“歌曲名称t姓名t性别t编号t姓名t性别t编号”< for(int j=0;j { if(strcmp(matchTable[j].musicName,MusicName)==0) { cout< cout< } } } } //主界面选项 void MainChoose(){ int ins;LoadAdmin();while(1){ system(“cls”); MainMenu(); cout< cin>>ins; switch(ins) { case 1: system(“cls”); StudentChose(); InitQueue(Boys); InitQueue(Girls); StudentSit(); //学生分别入座 GetStuSeat();//获取学生座位信息 cout<<“ttt男女生已分别就位....”< cout<<“ttt座位信息如下:”< PrintStuSeat(); char ch; cout<<“是否将该信息写入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileStuSeat()) cout<<“数据已写入文件...”< } Sleep(3000); break; case 2: system(“cls”); cout<<“tttt请先放入歌曲光盘...”< MusicMenu(); break; case 3: ShowMessage(); break; case 4: system(“cls”); cout<<“ttt请选择查询的方式:”< cout<<“ttt1.按学生姓名t2.按歌曲名”< int i; cin>>i; switch(i) { case 1: CheckByName(); break; case 2: CheckByMusic(); break; } //CheckByMusic(); getch(); break; case 5: system(“color FC”); Quit(); exit(0); break; } } } void main(){ MainChoose();} 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间： 一、课程设计题目分析 本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。 二、设计思路 本程序采用C语言来完成课程设计。 1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。 2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。 3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。 4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。 三、设计算法分析 1、相关函数说明： (1)定义数据结构类型为线性表的链式存储结构类型变量 typedef struct Polynomial{} (2)其他功能函数 插入函数void Insert(Polyn p,Polyn h) 比较函数int compare(Polyn a,Polyn b) 建立一元多项式函数Polyn Create(Polyn head,int m) 求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多项式a/b，void Device(Polyn pa,Polyn pb) 输出函数输出多项式，void Print(Polyn P) 销毁多项式函数释放内存，void Destroy(Polyn p) 主函数，void main（） 2、主程序的流程基函数调用说明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。 (2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下： Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式 p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间 p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据 Insert(p,head);调用Insert函数插入结点 这就建立一元多项式的关键步骤 (3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现： 在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。 (5)另一个子函数是输出函数 PrintPolyn（）； 输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。 四、程序新点 通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。 五、设计中遇到的问题及解决办法 首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4 代码编写。 其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。 最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。 六、测试（程序截图） 1.数据输入及主菜单 2.加法和减法模块 3.乘法和除法模块 七、总结 通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。 八、指导老师评语及成绩 附录：（课程设计代码） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系数为0的话释放结点 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系数为0的话释放结点 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指数为新时将结点插入 } 7 } //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;} //销毁多项式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余数是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式A(x):“);Print(pa);*n”); printf(“多项式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多项式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多项式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多项式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);}第二篇：数据结构课程设计-迷宫求解范文
第三篇：数据结构实验二 求解约瑟夫问题
第四篇：数据结构课程设计 舞伴问题
第五篇：2012数据结构课程设计
点击咨询 