南京林业大学数据结构课程设计报告专业：计算机科学与技术课程名称：数据结构姓名：学号：090801126指导老师：时间: 2011年1月目录要点：一.具体内容（题目） (1)二.需求分析（功能要求） (2)三.概要设计（程序设计思想） (3)四.详细设计（源代码） (6)五.调试分析（运行结果显示及说明） (31)六．课设总结 (34)具体内容：题目1: 运动会分数统计**任务：参加运动会有n个学校，学校编号为1……n。

比赛分成m个男子项目，和w个女子项目。

项目编号为男子1……m，女子m+1……m+w。

不同的项目取前五名或前三名积分；取前五名的积分分别为：7，5，3，2，1，取前三名的积分分别为：5，3，2，；哪些取前五名或前三名由学生自己设定。

（m〈=20，n〈=20）；题目2：一元多项式**任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加，相减，并将结果输入；题目4：迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；题目5：文章编辑**功能：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；题目6：Joseph环任务：编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m 时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有的人出列为止。

设计一个程序来求出出列的顺序。

题目7:猴子选大王**任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

题目8：建立二叉树，层序、先序遍历（用递归或非递归的方法都可以） **任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；题目9:纸牌游戏**任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？需求分析:运动会分数统计1）可以输入前三名或前五名的成绩；2）能统计各学校总分；3）可以按学校编号，学校总分，男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询查询取得前三名或前五名的学校。

规定：输入数据形式和范围：20以内的整数输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求；一元多项式计算能够完成两个多项式的相加，相减，并将结果输入；迷宫求解要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；文章编辑（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数并输出该次数，用函数letter_num()，figure_num（），space_num（），total_num（）来实现。

（3）删除某一子串，并将后面的字符前移,用delstr()来实现。

存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；Joseph环利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

输入数据：建立输入处理数据，输入m的初值，n，输入每个人的密码，建立单循环链表。

输出是什么：建立一个输出函数，将正确的输出序列；猴子选大王输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能；首先用一个数组来存放猴子的编号,从1到m,然后用hzxdw()按题目要求,用两个双重循环来实现猴子大王的选举.建立二叉树typedef struct node 是定义二叉树的存储结构creat(bitree *bt)是用来建立二叉树的输入的levelorder(bitnode *bt,int m)是用来建立层序遍历序列的preorder(bitree bt)是用来实现非递归先序遍历的main是主函数纸牌游戏直接用函数main()按照题目要求的规则,只使用数组和用几个循环来实现.概要设计：运动会分数统计：先分配存储的空间；输入运动项目个数、参加的学校的个数、男子比赛项目的个数、女子比赛项目的个数；循环每个项目的输入；自行选择取前三名还是前五名，循环输入姓名、成绩、学校；通过调用子函数进行计算；输出结果。

一元多项式计算：通过typedef struct polynode来定义单链表存储多项式的结点结构。

利用尾插法建立一元多项式的链表，先建立多项式的头结点，当表不为空的时候，申请新的结点，并分配存储空间，在当前的尾表做插入，最后将表的最后一个结点的next置NULL，以表示结束。

两个多项式的相加：当两个多项式均未扫描结束时若指数不等则到下一个结点，若指数相等且不为零时，相应的系数相加，若系数都为零时，则删除接点p与q，并将指针指向下一个结点，否则将q结点加入到和多项式中。

若多项式A中还有剩余，则将剩余的结点加入到和多项式中否则，将B中的结点加入到和多项式中。

两个多项式的相减与相加类似；总流程图：文章编辑:用串来存放一篇文章,文章录入以#作为结束,然后统计文章各种数据,直到#号为止,查找用户要统计的和删除的字符都是一样的思想,删除某一子串，并将后面的字符前移。

Joseph环：建立单循环链表，依次根据提示输入m，n，及code值。

猴子选大王：猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的：typedef struct Mnode{ int data;struct Mnode *next;}Mnode;根据题目要求，要让这M只猴子顺序围坐一圈，那就得用循环链表king(Linklist L,int n)在主函数中，根据提示先输入猴子的总的数量m，再输入数的数n，最后调用子函数进行选择，输出猴子王的编号。

建立二叉树：在typedef struct node中定义二叉树bitree的左右结点分别为lchild、rchild。

在输入函数中，把输入‘.’代表空；若输入不为空，则分配存储空间，并使其产生左右结点。

在层序遍历函数中，先定义一个数组，然后遍历他的左孩子结点，若不为空就放到数组中，再遍历右孩子结点，若不为空也放到数组中。

二叉树的层序遍历是由上至下一层一层地遍历的。

主函数中，先提示输入一个树调用二叉树输入函数，然后调用层序遍历函数，再调用递归先序遍历函数。

纸牌游戏:通过循环和连续乘-1进行翻牌，把值为1的定义为朝上的牌。

先定义52个牌；把每个牌都赋值为1；通过循环（52张牌的循环和基数的循环），并判断基数，每翻一次牌都乘-1，最后为1的数就是朝上的牌。

时间复杂度为o[1]；程序实现思想:首先必须确定实现这个课程设计的主算法是使用链式存储结构还是栈又或是数组和广义表。

根据题目要求需要实现的功能有：1、数据录入：输入各种数据；此处即创建链表的过程，调用一个成员函数负值。

在此处还有一个方法实现，即先输入数据，然后再调用构造实现。

2、数据统计：存储方式的选择，是使用链式存储结构还是栈又或是数组和广义表；遵守先定义后调用的原则；数组定义时注意下标的起始值和上限；链表定义时注意结点中的项；准确运用结点。

3、数据输出：按要求的格式打印调用do循环和for循环，通过遍历链表实现输出，用printf语句输出。

4、查找,修改,删除：这三个功能的核心是寻找成员，先遍历链表，然后寻找对应的ID号来找到结点，然后再对结点实行删除，修改操作。

详细设计（源程序）：1.运动会分数统计：#include <stdio.h>#include <stdlib.h>#include <string.H>#include <IO.H>#include <conio.h>#define MAX 50#define NULL 0typedef struct node1{int school; /*学校编号*/int record; /*项目成绩*/struct node1 *next;}Schools;typedef struct {int item; /*项目编号*/Schools *firstschool;}ITEM;typedef struct {int z; /* 项目总数*/ITEM a[MAX];}ALLitems;typedef struct node2 {int item; /*该学校获奖的项目*/int record; /*项目成绩*/struct node2 *next;}Items;typedef struct {int school; /*学校编号*/int score; /*学校总分*/int boys; /*男团体总分*/int girls; /*女团体总分*/Items *firstitem;}SCHNode;typedef struct {int n; /* 学校总数*/SCHNode b[MAX];}ALLNode;ALLitems *g1;ALLNode *g2;void funct1(ALLitems *g1,ALLNode *g2) /* 输入各个项目成绩*/ { Schools *p1;Items *p2;int i,j,k,m,w,h,x;printf("\n*** enter the information of every item ***\n\n");printf("enter the total number of male-items m:");scanf("%d",&m);if(m<0||m>20){ printf("enter error,m<=20,please enter again:");scanf("%d",&m);}printf("enter the total number of female-items w:");scanf("%d",&w);if(w<0||w>20){ printf("enter error,w<=20,please enter again:");scanf("%d",&w);}printf("enter the total number of schools n:");scanf("%d",&g2->n);if(g2->n<0||g2->n>20){ printf("entr error,n<=20,please enter again:");scanf("%d",&g2->n);}g1->z=m+w;printf("item number for boys 1-%d,girls %d-%d",m,m+1,g1->z);printf("\n\n*** record ***\n(0 stands for ending)");for(k=1;k<=g1->z;k++) /* 对两个邻接表置初态*/ { g1->a[k].item=k;g1->a[k].firstschool=NULL;}for(k=1;k<=g2->n;k++){ g2->b[k].school=k;g2->b[k].firstitem=NULL;g2->b[k].score=g2->b[k].boys=g2->b[k].girls=NULL;}g2->b[0].score=g2->b[0].boys=g2->b[0].girls=NULL;while(i!=0){ printf("\nitem:");scanf("%d",&i);if(i!=0){ printf("1.the three or 2.the five \n");printf("please choose 1 or 2:");scanf("%d",&j);if(j!=1&&j!=2){ printf("enter error,please enter again:");scanf("%d",&j);}if(j==1) /* 该项目只有前三名时执行此语句*/ { h=3;do{ printf("arrange %d:school(school is number)",h);scanf("%d",&x);p1=(Schools *)malloc(sizeof(Schools));p1->school=x;p2=(Items *)malloc(sizeof(Items));p2->item=i;if(h==3) p2->record=p1->record=2;if(h==2) p2->record=p1->record=3;if(h==1) p2->record=p1->record=5;p1->next=g1->a[i].firstschool;g1->a[i].firstschool=p1;p2->next=g2->b[x].firstitem;g2->b[x].firstitem=p2;g2->b[x].score=g2->b[x].score+p2->record; /* 累计总分*/ if(i<=m) g2->b[x].boys=g2->b[x].boys+p2->record; /* 累计男团体总分*/ else g2->b[x].girls=g2->b[x].girls+p2->record; /* 累计女团体总分*/ h--;}while(x!=0&&h!=0);}if(j==2) /* 该项目有前五名时执行此语句*/{ h=5;do{ printf("arrange %d:school(school is number)",h);scanf("%d",&x);p1=(Schools *)malloc(sizeof(Schools));p1->school=x;p2=(Items *)malloc(sizeof(Items));p2->item=i;if(h==5) p2->record=p1->record=1;if(h==4) p2->record=p1->record=2;if(h==3) p2->record=p1->record=3;if(h==2) p2->record=p1->record=5;if(h==1) p2->record=p1->record=7;p1->next=g1->a[i].firstschool;g1->a[i].firstschool=p1;p2->next=g2->b[x].firstitem;g2->b[x].firstitem=p2;g2->b[x].score=g2->b[x].score+p2->record; /* 累计总分*/ if(i<=m) g2->b[x].boys=g2->b[x].boys+p2->record; /* 累计男团体总分*/ else g2->b[x].girls=g2->b[x].girls+p2->record; /* 累计女团体总分*/h--;}while(x!=0&&h!=0);} } }}void save() /* 存储数据文件*/{ FILE *fp1,*fp2;if((fp1=fopen("sports1","wb"))==NULL){ printf("cannot open file.\n");return;}if(fwrite(g1,sizeof(ALLitems),1,fp1)!=1)printf("file write error.\n");fclose(fp1);if((fp2=fopen("sports2","wb"))==NULL){ printf("cannot open file.\n");return;}if(fwrite(g2,sizeof(ALLNode),1,fp2)!=1)printf("file write error.\n");fclose(fp2);}void funct2(ALLNode *g2) /* 输出各学校总分*/ { int k;printf("\n\n*** output the score ***\n");printf("school\t score \n");for(k=1;k<=g2->n;k++)printf("%d\t\t %d\n",k,g2->b[k].score);printf("\n");printf("press any butter to the main menu......");getch();}void funct3(ALLNode *g2) /* 按学校编号排序输出*/ { int k;Items *p2;printf("\n\n*** arranging output by school ***\n");printf("school\t\t\t the grade of item \n");for(k=1;k<=g2->n;k++){ printf("%d\t",k);p2=g2->b[k].firstitem;while(p2!=NULL){ printf("item %d:get the grade of %d ",p2->item,p2->record);p2=p2->next;}printf("\n");}printf("\n");printf("press any butter to the main menu......");getch();}void funct4(ALLNode *g2) /* 按学校总分排序输出*/ { int i,j,k;printf("\n\n*** arranging output by the score ***\n");printf("school\t score \n");for(i=2;i<=g2->n;i++){ g2->b[0].score=g2->b[i].score;g2->b[0].boys=g2->b[i].boys;g2->b[0].girls=g2->b[i].girls;g2->b[0].school=g2->b[i].school;j=i-1;while(g2->b[0].score<g2->b[j].score&&j>0){ g2->b[j+1].score=g2->b[j].score;g2->b[j+1].boys=g2->b[j].boys;g2->b[j+1].girls=g2->b[j].girls;g2->b[j+1].school=g2->b[j].school;j--;}g2->b[j+1].score=g2->b[0].score;g2->b[j+1].boys=g2->b[0].boys;g2->b[j+1].girls=g2->b[0].girls;g2->b[j+1].school=g2->b[0].school;}for(k=1;k<=g2->n;k++)printf("%d \t\t%d\n",g2->b[k].school,g2->b[k].score);printf("press any butter to the main menu......");getch();}void funct5(ALLNode *g2) /* 按男团体总分排序输出*/ { int i,j,k;printf("\n*** arranging output by boys ***\n");printf("school\t boys \n");for(i=2;i<=g2->n;i++){ g2->b[0].score=g2->b[i].score;g2->b[0].boys=g2->b[i].boys;g2->b[0].girls=g2->b[i].girls;g2->b[0].school=g2->b[i].school;j=i-1;while(g2->b[0].boys<g2->b[j].boys&&j>0){ g2->b[j+1].score=g2->b[j].score;g2->b[j+1].boys=g2->b[j].boys;g2->b[j+1].girls=g2->b[j].girls;g2->b[j+1].school=g2->b[j].school;j--;}g2->b[j+1].score=g2->b[0].score;g2->b[j+1].boys=g2->b[0].boys;g2->b[j+1].girls=g2->b[0].girls;g2->b[j+1].school=g2->b[0].school;}for(k=1;k<=g2->n;k++)printf("%d\t\t %d\n",g2->b[k].school,g2->b[k].boys);printf("press any butter to the main menu......");getch();}void funct6(ALLNode *g2) /* 按女团体总分排序输出*/ { int i,j,k;printf("\n*** arranging output by girls ***\n");printf("school\t girls \n");for(i=2;i<=g2->n;i++){ g2->b[0].score=g2->b[i].score;g2->b[0].boys=g2->b[i].boys;g2->b[0].girls=g2->b[i].girls;g2->b[0].school=g2->b[i].school;j=i-1;while(g2->b[0].girls<g2->b[j].girls&&j>0){ g2->b[j+1].score=g2->b[j].score;g2->b[j+1].boys=g2->b[j].boys;g2->b[j+1].girls=g2->b[j].girls;g2->b[j+1].school=g2->b[j].school;j--;}g2->b[j+1].score=g2->b[0].score;g2->b[j+1].boys=g2->b[0].boys;g2->b[j+1].girls=g2->b[0].girls;g2->b[j+1].school=g2->b[0].school;}for(k=1;k<=g2->n;k++)printf("%d\t\t %d\n",g2->b[k].school,g2->b[k].girls);printf("press any butter to the main menu......");getch();}void funct7(ALLNode *g2) /* 按学校编号查询学校某个项目情况*/ { int i,j,k;Items *p2;printf("\n *** look for the grade of a item by school ***\n");printf("enter the school you are looking for:");scanf("%d",&i);printf("enter the item you are looking for:");scanf("%d",&j);p2=g2->b[i].firstitem;while(p2!=NULL){ if(p2->item==j)printf("school:%d\t item:%d\t record:%d\n",i,p2->item,p2->record);p2=p2->next;}printf("\n");printf("press any butter to the main menu......");getch();}void funct8(ALLitems *g1) /* 按项目编号查询取得名次的学校*/ { int i,k;Schools *p1;printf("\n*** look for the win-school by item ***\n");printf("enter the item you are looking for:");scanf("%d",&i);printf("item \t\t\tthe win-school\n");printf("%d\t",i);p1=g1->a[i].firstschool;while(p1!=NULL){ printf(" school %d:get the grade of %d ",p1->school,p1->record);p1=p1->next;}printf("\n\n");printf("press any butter to the main menu......");getch();}void main(){ int t;ALLitems *g1;ALLNode *g2;for(;;){ printf("\t\t the score of the sports \n"); /* 运动会分数统计*/ printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * * * * * * * \n");printf("\t\t \n");printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * * * * * * * \n");printf("\t\t* 1.entering each record and save it *\n"); /* .输入各个项目成绩并存储文件*/printf("\t\t* 2.accumulating the score of each school *\n"); /* 统计各学校总分*/printf("\t\t* 3.arranging output by the school *\n"); /* 按学校编号排序输出*/printf("\t\t* 4.arranging output by the score *\n"); /* 按学校总分排序输出*/printf("\t\t* 5.arranging output by boys *\n"); /* 按男团体总分排序输出*/printf("\t\t* 6.arranging output by girls *\n"); /* 按女团体总分排序输出*/printf("\t\t* 7.looking for the score of a item by school *\n"); /* 按学校编号查询学校某个项目情况*/printf("\t\t* 8.looking for the win-school by item *\n"); /* 按项目编号查询取得名次的学校*/printf("\t\t* 0.exit *\n");printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * * * * * * * \n");printf("\t\t please choose (0-8):");loop:scanf("%d",&t);switch(t){ case 1:funct1(g1,g2);save();break;case 2:funct2(g2);break;case 3:funct3(g2);break;case 4:funct4(g2);break;case 5:funct5(g2);break;case 6:funct6(g2);break;case 7:funct7(g2);break;case 8:funct8(g1);break;case 0:exit(0);default:{ printf("enter error,please enter again:");goto loop;}} }}2.一元多项式计算#include<stdafx.h>#include<stdio.h>#include<stdlib.h>#define LEN sizeof(struct poly)struct poly{ int coef;int index;struct poly * next;};void print_poly(struct poly *head){ struct poly *p1;printf("%d次%d项式：",head->index,head->coef);p1=head->next;while(p1!=NULL){ if(p1->coef>0){ if(p1->index!=1&&p1->index!=0) printf("%dx^%d+",p1->coef,p1->index);else if(p1->index==1) printf("%dx+",p1->coef);else printf("%d+",p1->coef);}else if(p1->coef<0){ if(p1->index!=1&&p1->index!=0) printf("(%d)x^%d+",p1->coef,p1->index);else if(p1->index==1) printf("(%d)x+",p1->coef);else printf("(%d)+",p1->coef);}p1=p1->next;}printf("\b \n");}struct poly * creat_poly(){ struct poly *p1,*p2,*head;head=(struct poly *)malloc(LEN);head->coef=head->index=0;head->next=NULL;printf("请输入要创建的多项式（如A(x)=5x^17+9x^8+3x+7,请输入\"5^17 9^8 3^1 7^0 0^0\":\n");p1=(struct poly *)malloc(LEN);scanf("%d^%d",&p1->coef,&p1->index);while(p1->coef!=0){ p2=head;while(p2->next!=NULL){ if(p2->next->index<p1->index) break;p2=p2->next;}p1->next=p2->next;p2->next=p1;(head->coef)++;if(p1->index>head->index) head->index=p1->index;p1=(struct poly *)malloc(LEN);scanf("%d^%d",&p1->coef,&p1->index);}p1->next=NULL;return(head);}struct poly * add_poly(struct poly *head1,struct poly *head2){ struct poly *p1,*p2,*head3,*p3;p1=head1->next;p2=head2->next;head3=(struct poly *)malloc(LEN);p3=head3;head3->coef=head3->index=0;head3->next=NULL;while(p1!=NULL&&p2!=NULL){ if(p1->index>p2->index){ p3->next=p1;(head3->coef)++;p1=p1->next;p3=p3->next;}else if(p1->index==p2->index){ if(p1->coef+p2->coef!=0){ p3->next=(struct poly *)malloc(LEN);(p3->next)->coef=p1->coef+p2->coef;(p3->next)->index=p1->index;(head3->coef)++;p3=p3->next;}p1=p1->next;p2=p2->next;} else if(p1->index<p2->index){ p3->next=p2;(head3->coef)++;p2=p2->next;p3=p3->next;} }if(p1==NULL) p3->next=p2;else if(p2==NULL) p3->next=p1;p3=p3->next;while(p3!=NULL){ (head3->coef)++;p3=p3->next;}if(head3->next!=NULL) head3->index=head3->next->index; return(head3);}struct poly * sub_poly(struct poly *head1,struct poly *head2) { struct poly *p1,*head3;p1=head2->next;while(p1!=NULL){ p1->coef=0-p1->coef;p1=p1->next;}head3=add_poly(head1,head2);return(head3);}int main(){ struct poly *head1,*head2,*head3;char flag;printf("正在创建多项式一：\n");head1=creat_poly();printf("您创建的多项式为：\n\t");print_poly(head1);printf("\n正在创建多项式二：\n");head2=creat_poly();printf("您创建的多项式为：\n\t");print_poly(head2);do{ printf("\n请选择运算符号(+或-):");getchar();flag=getchar();if(flag!='+'&&flag!='-') printf("\n输入错误！请重新输入!\n");}while(flag!='+'&&flag!='-');switch(flag){ case '+':head3=add_poly(head1,head2);break;case '-':head3=sub_poly(head1,head2);break;}printf("\n计算的结果是:\n");print_poly(head3);printf("\n按[Enter]结束。