课程设计报告-实现十进制数N和二进制数之间的转换-学生成绩管理-拓扑排序

..第1页上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目数据结构课程设计院系计算机科学与信息工程学院专业游戏软件制作与开发班级姓名学号指导教师日期2016-1-14目的与要求巩固和加深对常见数据结构的理解和掌握掌握基于数据结构进行算法设计的基本方法掌握用高级语言实现算法的基本技能掌握书写程序设计说明文档的能力提高运用数据结构知识及高级语言解决非数值实际问题的能力课程设计内容说明项目一对设计任务内容的概述实现十进制数N和二进制数之间的转换。需求分析或功能描述输入相应的各式正确的数值〔可以是混合小数的形式,程序按照设定的算法执行后,给出相对应的进制数数值,对于输入数据的合法性可以不做检查。采用栈。概要设计或程序流程图内容：利用栈实现十进制和其他任意进制数的任意转换输出问题进制转换原理：N=<Ndivd>*d+Nmodd<其中：div为整除运算,mod为求余运算>步骤：1定义栈数据类型,采用链式存储结构实现2链栈基本操作函数原型声明3初始化栈4输入栈5输出栈6判空栈7自定义实现进制转换函数8数据调试9程序结束开始开始创建栈创建栈数制转换函数数制转换函数输出结果输出结果详细设计或源代码说明#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineERROR0#defineOVERFLOW-2#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<process.h>#include"math.h"typedefintSElemType;typedefstruct{SElemType*base;//在栈构造之前和销毁之后,base的值为NULLSElemType*top;//栈顶指针intStackSize;//当前已分配的存储空间,以元素为单位}SqStack1;voidInitStack<SqStack1*s>//初始化栈{s->base=<SElemType*>malloc<STACK_INIT_SIZE*sizeof<SElemType>>;if<!s->base>exit<OVERFLOW>;s->top=s->base;s->StackSize=STACK_INIT_SIZE;}voidPush<SqStack1*s,SElemTypee>//输入栈{if<s->top-s->base>=s->StackSize>{s->base=<SElemType*>realloc<s->base,<s->StackSize+STACKINCREMENT>*sizeof<SElemType>>;//栈满,追加存储空间if<!s->base>exit<OVERFLOW>;//若内存中没有s->StackSize+STACKINCREMENT个连续空间则分配失败s->top=s->base+s->StackSize;s->StackSize+=STACKINCREMENT;}*s->top++=e;}intPop<SqStack1*s,SElemType*e>//输出栈{if<s->top==s->base>returnERROR;s->top=s->top-1;*e=*s->top;}intStackEmpty<SqStack1s>//判空栈{if<s.top==s.base>return1;elsereturn0;}voidConversion<intN,intm>{SElemTypee;SqStack1s;InitStack<&s>;while<N>{Push<&s,N%m>;N=N/m;}printf<"转换后的%d进制数为：",m>;while<StackEmpty<s>!=1>{Pop<&s,&e>;if<e>=10>printf<"%c",e-10+'A'>;elseprintf<"%d",e>;}printf<"\n">;}voidsqunion<>{intn,m;printf<"请输入一个十进制数:">;scanf<"%d",&n>;printf<"需要转成的进制m：">;scanf<"%d",&m>;Conversion<n,m>;}voidlinkunion<>{inta,i,k=-1,y=0;printf<"\n请输入一个正确的二进制数:">;scanf<"%d",&a>;printf<"\n%d十进制为:",a>;while<a!=0>{i=a%10;k++;y+=i*pow<2,k>;a=a/10;}printf<"%d\n",y>;}voidlist1<>{ inti,flag=1,k; while<flag> { printf<"**************************************\n">; printf<"\t1:十进制转换为任意进制\n">;printf<"\t2:二进制转换为十进制\n">; printf<"\t0:返回\n">; printf<"\t请选择:\n">;printf<"**************************************\n">; while<true> { scanf<"%d",&i>; if<i>=0&&i<=2> break; else printf<"请选择0--2:\n">; } switch<i> { case1:squnion<>;break; case2:linkunion<>;break; case0:{flag=0;break;} } }}程序模块及其接口描述voidInitStack<SqStack1*s>//初始化栈voidPush<SqStack1*s,SElemTypee>//输入栈intPop<SqStack1*s,SElemType*e>//输出栈intStackEmpty<SqStack1s>//判空栈voidConversion<intN,intm>功能是：将十进制转换为其他进制voidlinkunion<>功能是：将二进制转换为十进制程序的输入与输出描述输入要求的整数输出二进制调试分析或程序测试在主界面中选择"1"进入进制转换子界面在子界面中选择"1"进入十进制转换为其他进制的测试,输入：99,转换为二进制,得出：1100011在子界面中选择"2",进行二进制转换为十进制测试。测试结果如下:输入"0",正常返回主界面。尚未解决的问题或改进方向未完善的问题：不能由二进制直接转换为任意进制；在十进制转换过程中不能输入小数。改进方向：界面美化；调整程序,使其可以输入小数。对软件的使用说明根据界面提示选择需要的操作,输入整数,注意二进制只包含"1""0"。项目二对设计任务内容的概述任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储,每个学生记录包含的信息有：学号和各门课程的成绩。存储结构：采用线性链式结构。需求分析或功能描述管理系统中有五个要求：输入查找修改插入删除存储输入要求：能够通过键盘输入和文件输入两种查找要求：能够根据学生号查找单个学生的信息,也可以遍历所有学生信息修改要求：能够根据学生号修改单个学生所有信息插入要求：能够实现头插和尾插删除要求：能够根据学生号删除单个学生信息存储要求：通过链表存储所有信息概要设计或程序流程图首先,分析题目要求划分实现模块,定义基本数据类型,诸如结构体、链表等；其次,针对上述的基本操作实现具体需要进行的操作,具体实现每个环节需要进行的基本操作,即具体编写每个小函数实现功能；最后,编写主函数对每个实现进行按需调用,实现操作。详细设计或源代码说明#include<stdio.h>#include<malloc.h>#include<string.h>structStudent{charname[10];charsubject[10];intnum;intgrade;Student*next;};voidStuMain<>;//学生成绩管理系统的主函数,由main函数调用voidStuInput<Student*>;//学生成绩管理系统的输入函数,由主函数调用voidStuSelect<Student*>;//学生成绩管理系统的查找函数,由主函数调用voidStuAlter<Student*>;//学生成绩管理系统的修改函数,由主函数调用voidStuInsert<Student*>;//学生成绩管理系统的插入函数,由主函数调用voidStuDelect<Student*>;//学生成绩管理系统的删除函数,由主函数调用voidStuSave<Student*>;//学生成绩管理系统的存储函数,由主函数调用voidStuOutput<Student*p>;//输出函数intStuImport<Student*head,Student*p>;//输入函数voidStuOutput<Student*p>//打印函数,将链表的该节点信息输出{printf<"学生__">;printf<"%s",p->name>;printf<"学生号：">;printf<"%d",p->num>;printf<"科目：">;printf<"%s",p->subject>;printf<"学生成绩：">;printf<"%d\n",p->grade>;}intStuImport<Student*head,Student*p>{Student*Opinion=<Student*>malloc<sizeof<Student>>;//用来判断输入节点中学生号是否有重复Opinion=head->next;printf<"学生__\n">;scanf<"%s",p->name>;printf<"学生号：\n">;scanf<"%d",&p->num>;printf<"科目：\n">;scanf<"%s",p->subject>;if<Opinion!=NULL>{if<Opinion->num==p->num&&!strcmp<Opinion->subject,p->subject>>{printf<"该学生这门科目已有成绩,请重新输入\n">;return1;}Opinion=Opinion->next;}printf<"学生成绩：\n">;scanf<"%d",&p->grade>;return0;}voidlist2<>{StuMain<>;}voidStuMain<>{chardecide='y';//定义while变量,函数是否继续进行intnum=1;//定义switch变量,函数跳转到哪个子函数Student*head;//定义链表的头指针head=<Student*>malloc<sizeof<Student>>;//给头指针开辟空间head->next=NULL;//初始化头指针while<decide!='n'>{printf<"***************************************************\n">;printf<"**********1输入2查找3修改4插入********\n">;printf<"**********5删除6存储7退出********\n">;printf<"***************************************************\n">;scanf<"%d",&num>;switch<num>{case1:StuInput<head>;break;case2:StuSelect<head>;break;case3:StuAlter<head>;break;case4:StuInsert<head>;break;case5:StuDelect<head>;break;case6:StuSave<head>;break;default:decide='n';break;}};}voidStuInputHand<Student*head>;//学生成绩管理系统的手动输入函数,由输入函数调用voidStuInputFile<Student*head>;//学生成绩管理系统的文件输入函数,由输入函数调用voidStuInput<Student*head>//学生成绩管理系统的输入函数,由主函数调用{chardecide='y';//定义while变量,函数是否继续进行intnum;//定义switch变量,函数跳转到哪个子函数while<decide!='n'>{printf<"***************************************************\n">;printf<"**1手动输入2文件输入3退出**\n">;printf<"***************************************************\n">;scanf<"%d",&num>;switch<num>{case1:StuInputHand<head>;break;case2:StuInputFile<head>;default:decide='n';break;}}}voidStuInputHand<Student*head>//学生成绩管理系统的手动输入函数,由输入函数调用{if<head->next==NULL>{Student*point=<Student*>malloc<sizeof<Student>>;//链表中最后一个节点,只在该函数中存在point->next=NULL;intdecide=1;while<decide!=0>{Student*p=<Student*>malloc<sizeof<Student>>;p->next=NULL;StuImport<head,p>;if<head->next==NULL>{head->next=p;point=p;}else {point->next=p;point=p;}printf<"是否继续：1/0\n">;scanf<"%d",&decide>;}}elseprintf<"管理系统中已存在信息,若想输入学生信息,请转插入子系统">;}voidStuInputFile<Student*head>//学生成绩管理系统的文件输入函数,由输入函数调用{if<head->next!=NULL>{printf<"学生管理系统中已有信息,请跳转到插入选项\n">;}FILE*fp;printf<"请输入文件名〔包括物理地址\n">;charfilename[10];scanf<"%s",filename>;if<<fp=fopen<filename,"r">>==NULL>{printf<"cannotopenfile\n">;return;}Student*point=<Student*>malloc<sizeof<Student>>;Student*Opinion=<Student*>malloc<sizeof<Student>>;//用来判断输入节点中学生号是否有重复while<!feof<fp>>{Opinion=head->next;Student*p=<Student*>malloc<sizeof<Student>>;p->next=NULL;fread<p,sizeof<Student>,1,fp>;if<Opinion!=NULL>{if<Opinion->num==p->num&&!strcmp<Opinion->subject,p->subject>>{printf<"该文件中有重复学生信息,请验明再传输\n">;head->next=NULL;}Opinion=Opinion->next;}if<head->next==NULL>{head->next=p;point=p;}else{point->next=p;point=p;}};Opinion=head->next;while<Opinion->next!=NULL>{Opinion=Opinion->next;if<Opinion->next->next==NULL>Opinion->next=NULL;};fclose<fp>;printf<"传输成功\n">;}voidStuSelectErg<Student*head>;//学生成绩管理系统的遍历函数,由查找函数调用voidStuSelectNumFind<Student*head>;//学生成绩管理系统的按学号查找函数,由查找函数调用voidStuSelectSubFind<Student*head>;//学生成绩管理系统的按科目查找函数,由查找函数调用voidStuSelect<Student*head>//学生成绩管理系统的查找函数,由主函数调用{chardecide='y';//定义while变量,函数是否继续进行intnum;//定义switch变量,函数跳转到哪个子函数while<decide!='n'>{printf<"***************************************************\n">;printf<"****1遍历2学号查找3科目查找4退出****\n">;printf<"***************************************************\n">;scanf<"%d",&num>;switch<num>{case1:StuSelectErg<head>;break;case2:StuSelectNumFind<head>;break;case3:StuSelectSubFind<head>;break;default:decide='n';break;}}}voidStuSelectErg<Student*head>//学生成绩管理系统的遍历函数,由查找函数调用{Student*p=<Student*>malloc<sizeof<Student>>;p=head->next;inti=1;while<p!=NULL>{printf<"第%d位学生信息：\n",i>;StuOutput<p>;p=p->next;i++;}}voidStuSelectNumFind<Student*head>//学生成绩管理系统的查找子系统,有查找函数调用{intnum;printf<"输入想要查找学生的学生号：\n">;scanf<"%d",&num>;Student*p=<Student*>malloc<sizeof<Student>>;p=head->next;inti=1;while<p!=NULL>{if<num==p->num>{StuOutput<p>;i++;}p=p->next;}if<i==1>printf<"没有该学生信息">;}voidStuSelectSubFind<Student*head>//学生成绩管理系统的按科目查找函数,由查找函数调用{charSub[10];printf<"输入想要查找科目：\n">;scanf<"%s",Sub>;Student*p=<Student*>malloc<sizeof<Student>>;p=head->next;inti=1;while<p!=NULL>{if<!strcmp<Sub,p->subject>>{StuOutput<p>;i++;}p=p->next;}if<i==1>printf<"没有该学生信息">;}voidStuAlter<Student*head>//学生成绩管理系统的修改函数,由主函数调用{intnum;printf<"输入想要查找学生的学生号：\n">;scanf<"%d",&num>;charSub[10];printf<"输入想要查找科目：\n">;scanf<"%s",Sub>;Student*p=<Student*>malloc<sizeof<Student>>;p=head->next;inti=1;while<p!=NULL>{if<num==p->num&&!strcmp<Sub,p->subject>>{printf<"输入修改成绩：\n">;scanf<"%d",&p->grade>;printf<"修改成功\n">;i++;}p=p->next;if<i==1>printf<"没有该学生信息">;}}voidStuInsert<Student*head>//学生成绩管理系统的插入函数,由主函数调用{Student*point=<Student*>malloc<sizeof<Student>>;point=head->next;while<point->next!=NULL>point=point->next;//找到尾结点chardecide='y';//定义while变量,函数是否继续进行intnum;//定义switch变量,函数跳转到哪个子函数while<decide!='n'>{printf<"***************************************************\n">;printf<"****1头插2尾插3退出****\n">;printf<"***************************************************\n">;scanf<"%d",&num>;Student*p=<Student*>malloc<sizeof<Student>>;switch<num>{case1:StuImport<head,p>;p->next=head->next;head->next=p;printf<"插入成功\n">;break;case2:StuImport<head,p>;point->next=p;p->next=NULL;printf<"插入成功\n">;break;default:decide='n';break;}}}voidStuDelect<Student*head>//学生成绩管理系统的删除函数,由主函数调用{intnum;printf<"输入想要删除学生的学生号：\n">;scanf<"%d",&num>;charSub[10];printf<"输入想要删除科目：\n">;scanf<"%s",Sub>;Student*p=<Student*>malloc<sizeof<Student>>;p->next=head->next;inti=1;while<p->next!=NULL>{if<num==p->next->num&&!strcmp<Sub,p->next->subject>>{StuOutput<p->next>;printf<"是否删除：1/0\n">;scanf<"%d",&i>;if<num==head->next->num&&!strcmp<Sub,head->next->subject>>{head->next=head->next->next;}else{p->next=p->next->next;}i=2;printf<"删除成功\n">;break;}p=p->next;}if<i==1>printf<"没有该学生信息\n">;}voidStuSave<Student*head>//学生成绩管理系统的存储函数,由主函数调用{FILE*fp;charfilename[10];printf<"请输入存储文件名〔包括物理地址\n">;scanf<"%s",filename>;Student*p=<Student*>malloc<sizeof<Student>>;p=head->next;if<<fp=fopen<filename,"w">>==NULL>{printf<"cannotopenfile">;return;}printf<"inputdata:/n">;while<p!=NULL>{fwrite<p,sizeof<Student>,1,fp>;/*成块写入文件*/p=p->next;}fclose<fp>;}程序模块及其接口描述voidStuInput<Student*>;//学生成绩管理系统的输入函数,由主函数调用voidStuSelect<Student*>;//学生成绩管理系统的查找函数,由主函数调用voidStuAlter<Student*>;//学生成绩管理系统的修改函数,由主函数调用voidStuInsert<Student*>;//学生成绩管理系统的插入函数,由主函数调用voidStuDelect<Student*>;//学生成绩管理系统的删除函数,由主函数调用voidStuSave<Student*>;//学生成绩管理系统的存储函数,由主函数调用基本操作函数：voidStuOutput<Student*p>;//输出函数intStuImport<Student*head,Student*p>;//输入函数voidStuInputHand<Student*head>;//学生成绩管理系统的手动输入函数,由输入函数调用voidStuInputFile<Student*head>;//学生成绩管理系统的文件输入函数,由输入函数调用voidStuSelectErg<Student*head>;//学生成绩管理系统的遍历函数,由查找函数调用voidStuSelectNumFind<Student*head>;//学生成绩管理系统的按学号查找函数,由查找函数调用voidStuSelectSubFind<Student*head>;//学生成绩管理系统的按科目查找函数,由查找函数调用程序的输入与输出描述输入学生基本信息。输出学生基本信息调试分析或程序测试由主界面进入学生成绩管理界面。手动输入学生基本信息由学号等基本信息查找学生科目成绩修改成绩插入新的学生基本信息删除选择出来的学生信息储存刚才的学生信息尚未解决的问题或改进方向未解决的问题：不能同时输入多科成绩,存储后的文件无法正常查看。改进方向：输入多科成绩。对软件的使用说明操作较为复杂,需要耐心以及根据界面提示做,不可乱输入。项目三对设计任务内容的概述编写函数实现图的拓扑排序。需求分析或功能描述。概要设计或程序流程图开始开始输入顶点及信息输入顶点及信息NN输入符合条件？输入符合条件？YY根据输入信息建立邻接表根据输入信息建立邻接表建栈建栈在邻接表中寻找入度为0的顶点,将其按入栈在邻接表中寻找入度为0的顶点,将其按入栈弹出栈顶,打印,将与栈顶元素邻接的顶点的入度减一弹出栈顶,打印,将与栈顶元素邻接的顶点的入度减一NN栈是否为空栈是否为空YY终止终止。详细设计或源代码说明#include<stdio.h>#include<stdlib.h>#definetrue1#definefalse0#defineMAX_VEXTEX_NUM20#defineM20#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10/*图的邻接表存储结构*/typedefstructArcNode/*弧结点结构类型*/{intadjvex;/*该弧指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/}ArcNode;typedefstructVNode/*邻接表头结点类型*/{intdata;/*顶点信息*/ArcNode*firstarc;/*指向第一条依附于该点的弧的指针*/}VNode,AdjList[MAX_VEXTEX_NUM];/*AdjList为邻接表类型*/typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;/**/voidCreatGraph<ALGraph*G>/*通过用户交互产生一个图的邻接表*/{intm,n,i;ArcNode*p;printf<"=======================================================">;printf<"\n输入顶点数:">;scanf<"%d",&G->vexnum>;printf<"\n输入边数:">;scanf<"%d",&G->arcnum>;printf<"=======================================================">;for<i=1;i<=G->vexnum;i++>/*初始化各顶点*/{G->vertices[i].data=i;/*编写顶点的位置序号*/G->vertices[i].firstarc=NULL;}for<i=1;i<=G->arcnum;i++>/*记录图中由两点确定的弧*/{printf<"\n输入确定弧的两个顶点u,v:">;scanf<"%d%d",&n,&m>;while<n<0||n>G->vexnum||m<0||m>G->vexnum>{printf<"输入的顶点序号不正确请重新输入:">;scanf<"%d%d",&n,&m>;}p=<ArcNode*>malloc<sizeof<ArcNode>>;/*开辟新的弧结点来存储用户输入的弧信息*/if<p==NULL>{printf<"ERROR!">;exit<1>;}p->adjvex=m;/*该弧指向位置编号为m的结点*/p->nextarc=G->vertices[n].firstarc;/*下一条弧指向的是依附于n的第一条弧*/G->vertices[n].firstarc=p;}printf<"=======================================================">;printf<"\n建立的邻接表为:\n">;/*打印生成的邻接表〔以一定的格式*/for<i=1;i<=G->vexnum;i++>{printf<"%d",G->vertices[i].data>;for<p=G->vertices[i].firstarc;p;p=p->nextarc>printf<"-->%d",p->adjvex>;printf<"\n">;}printf<"=======================================================">;}/**/typedefstruct/*栈的存储结构*/{int*base;/*栈底指针*/int*top;/*栈顶指针*/intstacksize;}SqStack;/**/voidInitStack<SqStack*S>/*初始化栈*/{S->base=<int*>malloc<STACK_INIT_SIZE*sizeof<int>>;if<!S->base>/*存储分配失败*/{printf<"ERROR!">;exit<1>;}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}/**/voidPush<SqStack*S,inte>/*压入新的元素为栈顶*/{if<S->top-S->base>=S->stacksize>{S->base=<int*>realloc<S->base,<S->stacksize+STACKINCREMENT>*sizeof<int>>;/*追加新空间*/if<!S->base>/*存储分配失败*/{printf<"ERROR!">;exit<1>;}S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;/*e作为新的栈顶元素*/}/**/intPop<SqStack*S,int*e>/*弹出栈顶,用e返回*/{if<S->top==S->base>/*栈为空*/{returnfalse;}*e=*--S->top;return0;}/**/intStackEmpty<SqStack*S>/*判断栈是否为空,为空返回1,不为空返回0*/{if<S->top==S->base>returntrue;elsereturnfalse;}/**/voidFindInDegree<ALGraphG,intindegree[]>/*对各顶点求入度*/{inti;for<i=1;i<=G.vexnum;i++>/*入度赋初值0*/{indegree[i]=0;}for<i=1;i<=G.vexnum;i++>{while<G.vertices[i].firstarc>{indegree[G.vertices[i].firstarc->adjvex]++;/*出度不为零,则该顶点firstarc域指向的弧指向的顶点入度加一*/G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}}/**/voidTopoSort<ALGraphG>{intindegree[M];inti,k,n;intcount=0;/*初始化输出计数器*/ArcNode*p;SqStackS;FindInDegree<G,indegree>;InitStack<&S>;for<i=1;i<=G.vexnum;i++>{printf<"\n">;printf<"indegree[%d]=%d\n",i,indegree[i]>;/*输出入度*/}printf<"\n">;for<i=1;i<=G.vexnum;i++>/*入度为0的入栈*/{if<!indegree[i]>Push<&S,i>;}printf<"=======================================================">;printf<"\n\n拓扑排序序列为:">;