第一篇：C++数据结构 大作业课程设计
C++/数据结构 大作业/课程设计——【校园导游咨询】【停车场管理】娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组（谨以此程序供大家参考。运行结果后面有贴图）
目录
【1】校园导游咨询 程序设计源代码 及 截图 【2】停车场管理——方案一 程序设计源代码 及 截图 【3】停车场管理——方案二 程序设计源代码 及 截图
【1】【【校园导游咨询】】
######
(ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【【上海电力学院】】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改)【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】
(1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【选作内容】
(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。**************************【以下为类的定义】******************************** #include
class direction;template
{ friend class MGraph
direction dir;//存放顶点方位信息的direction类的dir。};
class direction { public: int ln;//存放在方向图中的横坐标，表示东西 int col;//存放在方向图中的纵坐标，表示南北 };template
{ public: MGraph();
//构造函数，初始化具有n个顶点的图
void printvexname();//显示所有景点及景点代号
void printvexinf(int i);//显示代号为i景点的名称及信息
void printroad(int i,int j);//显示景点i~j的最短路径方案信息
void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m” VertexNode
void Root(int p,int q);//递归寻找pq间的最短路径
int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度
int Line[MaxSize];//Line存放路径 int kkk;//Line[]数组的标记
private: T vertex[MaxSize];//存放图中顶点的数组
int arc[MaxSize][MaxSize];//存放图中边的数组 };*************************【以下为类的实现 即类函数的定义】*********************************** template
//s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char* b[]={“南门”,“实验楼”,“南图”,“大活”,“睿思楼”,“大礼堂”, “南4教”,“知行楼”,“国交楼”,“南3教”,“南2教”,“南1教”, “北图”,“北3教”,“北4教”,“北2教”,“北1教”,“北门”};char* c[]={“南校区正门”,“物理实验楼”,“南校区图书馆”,“大学生活动中心”, “教师办公楼、医务室及留学生公寓”,“大礼堂，用于举办各种文艺演出”,“南校区第4教学楼”,“实习基地，计算机房等”, “国际交流中心，教职工餐厅”,“南校区第3教学楼”,“南校区第2教学楼”,“南校区第1教学楼”, “北校区图书馆”,“北校区第3教学楼”,“北校区第4教学楼”,“北校区第2教学楼”, “北校区第1教学楼”,“北校区正门”};int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};int i,j;vertexNum=18;arcNum=30;
for(i=0;i for(j=0;j template cout<<“向东”< cout<<“向南”< if(Path[p][q]>0){ Root(p,Path[p][q]);Root(Path[p][q],q);} else { Line[kkk]=q;kkk++;} } template for(q=0;q Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;} cout<<“n=======n”;cout<<“从”< { int choice;cout<<“================”< 【2】【停车场管理系统【方案一 程序】】 ###### （ps：该程序有漏洞，若将要离开的车辆是停于便道上的，则对该车进行驶离操作时程序内部有错误数据，虽然做了函数完成这一功能，但因时间有限，没能及时查找更正，现在懒得改了。。大家将就看吧。不过运行是可以的）【问题描述】 设停车场是一个可停放n辆汽车的 长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】 设n=2，输入数据为：(A，1，5)，（A，2，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。**************************【以下为类的定义】************************************* #include const double price=30;//每小时的费用 //思想：（报告第四页） //我的系统界面，输入信息为：（到达/离开/退出）；车牌号；时刻 //因此，我的停车场类分成车辆到达和车辆离开两个主要的函数实现。//车辆到达，有入栈和入队。车辆离开有出栈，出队和入栈操作。 //因此我又编写入栈的类，队的类。与parkingmanagement进行友元。 //**************************************类定义*********************************************** class car//车的信息类 { public: double time;//计费时间 int number;//车牌号 car *next;//存放car类型元素的数组初始地址 };class carstack//栈（停车场）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carstack();//构造函数，栈的初始化 int empty();//判断栈是否为空 int full();//判断栈是否为满 car *s;//存放car类型栈元素的数组初始地址 int top;//栈顶指针 };class carqueue//队列（便道）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carqueue();//构造函数，队列的初始化 int full();//判断队列是否为满 car *front,*rear;//存放car类型队列元素的数组初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入栈,cs栈内进行调整，返回栈内位置 void popstack(carstack &cs,int cnum);//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber()//将出栈car的time赋值给double popstacktime()，无返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);//入队,队内进行调整，返回队内位置 int popqueue(carqueue &cq);//出队,队内进行调整，返回汽车车牌号 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆到达，//根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆离开，//根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作； //并cout停留时间和收费情况 void deletequeue(carqueue &cq,int i);//删除cq过道中第i辆车 int popstacknumber;//专门存放出栈的时候返回的车牌号 double popstacktime;//专门存放出栈的时候返回的时刻 };**********************************【以下为类的实现】************************************ carstack::carstack()//构造函数，栈的初始化 { top=-1;s=new car[Max];//创建car类型栈元素的数组 if(s==NULL){ cout<<“栈空间分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组(cs.s[cs.top]).time=ctime;//将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组 return(cs.top+1);//返回栈内位置加1，即停车场内车位从1号开始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber //将出栈car的time赋值给double popstacktime，无返回值！{ int i;car p;carstack stemp;//定义一个carstack类型的临时存放出栈元素的栈 for(i=0;i<=cs.top;i++)if((cs.s[i]).number==cnum)break;//当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.s[i];//将要出栈的元素赋给car类型的p存放 while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出栈的元素数组逐个赋给临时栈 popstacknumber=p.number;//将这个车牌号信息传给int popstacknumber()popstacktime=p.time;//将该车的时间信息传给double popstacktime()cs.top--;//栈顶指针回到原来位置 while(stemp.top>=0)cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入队,队内进行调整，返回队内位置 { car *p,*countp;int count(1);//count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;//创建一个car类型的指针 p->number=cnum;p->time=ctime;p->next=NULL;//首先将指向存放car类型元素的数组初始地址置空 if(cq.front==NULL)//第一次入队要判断头结点是否为空 { cq.front=cq.rear=p;} else {//尾插法插入元素 p->next=(cq.rear)->next;(cq.rear)->next=p;cq.rear=(cq.rear)->next;} countp=(cq.front)->next;while(countp!=NULL){ count++;countp=countp->next;}//count即车在过道上的位置，【从1开始计！！】 return count;} int parkingmanagement::popqueue(carqueue &cq)//出队,队内进行调整，返回汽车车牌号 { car p;p.number=((cq.front)->next)->number;//cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.time=((cq.front)->next)->time;//cq队里，从cq.front开始指向下一个元素的时刻 //赋给car类型的车信息 p.next=((cq.front)->next)->next;//cq队里，从cq.front开始指向下一个元素的指针 //赋给car类型的车信息的下一个元素的指针 return p.number;cq.front=(cq.front)->next;} void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime)//车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 { int pos;if(!(cs.full()))//如果栈未满，车辆停入停车场 { int fl(0),i;//定义一个从0开始的标记fl for(i=0;i<=cs.top;i++){ if(cs.s[i].number==cnum)//如果到达的车的车牌号=栈内已有车辆的车牌号 { fl=1;//fl记1 break;} } if(fl==1)//如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<“输入错误！请重新输入！”< cout<<“该停车场还有空位，请到”< { pos=pushqueue(cq,cnum,ctime);//入队，返回车位信息 cout<<“该停车场已满，请将车停到便道”< { popstack(cs,cnum);//出栈操作 hour=ctime-popstacktime;//时间计算 outcarnum=popqueue(cq);//将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);//将便道上的第一辆车，入栈 cout<<“该车在本停车场内停留时间为”< { p=cq.front;while(p!=NULL){ count++;//如果在过道中找到该车，则该车的位置为过道中的第count位置（count从1开始）p=p->next;if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。//后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count);if(count>Max){ cout<<“您的车在便道上的位置为”< car *p,*q;int j(0);p=cq.front;while(p && j ######【3】【停车场管理系统【方案二 程序】】 （ps：本方案与方案一有同样的问题，就是在对 便道上的车 进行驶离操作时，数据错误，同样的理由，没有改正。如果有细心娃娃帮忙指点改正，在此感激啦~） *************************【以下为类定义】************************************ #include struct Node//过道停车的队列所需链式结点 { T carnum;//定义车牌号类型 Node friend class carStack;public: T carnum;//车号 int cartime;//停车时间 }; template int EnQueue(T cnum);//将元素x入队,并返回其在队内的位置（从1开始）T DeQueue();//将队头链式结点出队,并返回汽车车牌号 void deletequeue(int i);//将队内低i个元素删除，即便道上i位置的汽车驶离 bool Empty();//判断链队列是否为空 Node int Popcar(T outcnum,int outctime);//将第cnum辆车出栈，并返回其停车时间（hour）bool full();//判断栈是否为满？满则返回1 carinfo s=new Node front=rear=s;} else { rear->next=s;//将结点s插入到队尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即车在过道上的位置，【从1开始计！！】 return i;} template front=front->next;//将队头元素所在结点摘链 } return p->carnum;delete p;//将出队进栈的车从队列里删除 } template template :top(-1){//建立一个最大尺寸为size的空栈 S=new carinfo { cerr<<“动态存储失败！”< template template void outputpark()//系统功能选择页面，输入泊车信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“请驶入停车场的”< Node 题目：计算表达式的值 1、问题描述 对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。 基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。 提高要求：（1）对于表达式中的简单错误，能够给出提示； （2）不仅提示错误，也能给出错误信息（3）表达式中可以包括单个字母表示的变量（4）能够处理多种操作符（5）实现包含简单运算的计算器 （6）实现一个包含简单运算和函数运算的计算器。 2．需求分析 软件的基本功能：由键盘输入中缀表达式，程序可以将输入的中缀表达式转换成对应的后缀表达式，并计算后缀表达式的值。对于在输入时发生的简单错误，程序可以给出提示。本程序支持整数、小数、多种操作数的处理，可以计算含加、减、乘、除、运算符的表达式，并能判断表达式括号是否匹配。输入/输出形式：用户可以通过控制台，根据输入提示。输入形式： ①正确的不含字母变量的中缀表达式； ②含有简单错误的中缀表达式。 输出形式： ①对于正确的中缀表达式，可以输出其转化后的后缀表达式及表达式的计算结果； ②对于含有简单错误的中缀表达式，程序将自动输出错误提示，并给出错误信息。 测试数据要求：用户可以输入一个符合要求的中缀表达式，也可以输入一个包含简单错误的表达式。表达式中可以包括各种类型的常数以及小数等，操作符包括（+、-、*、/），同时表达式还可以包括各种括号。 3．概要设计 （1）抽象数据类型： 根据题目的要求，考虑用栈类型比较适合。ADT SeqStack Data 栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系 Operation SeqStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈 ~ SeqStack 前置条件：栈已存在输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素 Pop 前置条件：栈已存在输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈顶减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变 Empty 前置条件：栈已存在输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1；否则，返回0 后置条件：栈不变 End ADT 4．详细设计 （1）实现概要设计的数据类型： 采用顺序栈 const int StackSize = 50;template ~SeqStack();//析构函数 void Push(T x);//将元素x入栈 DataType Pop(); //将栈顶元素弹出 DataType GetTop();//取栈顶元素（并不删除） int Empty();//判断栈是否为空 private: DataType data[StackSize];//存放栈元素的数组 int top;//栈顶元素 };（2）主程序以及其它模块的算法描述： 这个函数主要调用了实现功能的各个函数。其步骤为：在用户没有选择退出时，先调用输入函数，输入中缀表达式；然后调用判断表达式，如果中缀表达式错误，则根据返回的值来输出错误提示，不再往下运算；如果中缀表达式正确，则将中缀表达式转换为后缀表达式，然后输出中缀表达式和转换后的后缀表达式；接着，再调用计算函数，计算后缀表达式的结果输出。最后是清屏函数。直至用户选择退出。 5、编码与调试分析 编码与调试过程中遇到的问题及解决办法： 【问题1】程序在判断表达式输入形式有误时，考虑情况不周全。解决办法：尽可能多的将表达式有误的情况考虑在内。以下为现已考虑到并解决的问题：①表达式中出现非数字或非运算符的其他字符； ②表达式中括号不匹配。 【问题2】给变量赋值时出现重定义问题。 解决办法：在定义暂存栈顶元素的变量t时，应该在函数外面定义，在函数里面给变量赋值时不能定义。【问题3】无法处理多位数和小数。 解决办法：在连续的操作数结束之后插入空格到后缀表达式中，以分隔操作数。 解决此问题的核心代码： int i,t=0;float sum=0;for(i=0;i if(a[i]=='.'){ } } t=i;break;if(t!=0){ } else { } return sum; 2.待解决问题： for(i=0;i } i++;for(;i } sum=(a[i]-'0')*pow(0.1,i-t)+sum;if(a[i]=='.')break;sum=(a[i]-'0')*pow(10,n-(n-t)-1-i)+sum;for(i=0;i 6、使用说明 进入菜单，根据提示进行选择。 7、测试结果 （1）含小数、多位数及括号的表达式显示结果： 8、自学知识 在课程设计过程中，特别是在代码编写和调试的过程中，自学了很多新的知识。例如atof()函数，包含于表头文件 #include 自学MFC。还有一个知识点是清屏函数，它也是包含于 9、课程设计心得体会 通过这次课程设计，增强了我的自信心。因为在这次课程设计中，我遇到了一些问题，但是都逐个得解决了，虽然有些问题请教了同学，但是从中学了很多东西，也学到了一些处理问题的方法。在能力上得到了一些提升。同时也养成了独立思考问题，以及和同学一起探索问题的良好习惯。当然，在课程设计过程中，有些细节的处理还是不够完美，需要完善的地方还有很多，还需要继续努力，尽量将程序完善。 在编写程序过程中，得到了部分同学的帮助，如：数据间的分隔问题，得到了***同学的帮助，将中缀表达式转换为后缀表达式的算法思想参考了《数据结构课程设计》（机械工业出版社），然后根据自己的理解，完成基本算法和细节处理，最后完成了转换函数的代码编写。 在将字符串转换为浮点型数字进行运算的思想主要参考了《程序设计引导及在线实践》这本书里面的一道程序，然后加以灵活运用，转换为自己的代码。当然，为此也掌握了一些新的知识。 清屏函数是在百度百科上获取的知识，也属于自学的新知识。 参考书 [1]《c++面向对象程序设计》 清华大学出版社 谭浩强著 [2]《数据结构（C++版）》清华大学出版社 王红梅、胡明、王涛著 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 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);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include typedef struct HTNode //结构体 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把权值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“输入成功！”);} void Coding_H(int n,HTNode *HT) //对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=' '; printf(“************************n”);printf(“Char Codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent) if(HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(HC[k],&cd[sp]); printf(“%c %sn”,HT[k].ch,HC[k]); } printf(“************************n”);free(cd);} void Read(int n,HTNode *HT) //从文件中读出数据 { int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight); } Coding_H(n,HT); fclose(fp);} void Print_H(int m,HTNode *HT) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight Par LCh RCh n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,HT[k].Weight); printf(“ %d”,HT[k].Parent); printf(“ %d”,HT[k].Lchild); printf(“ %dn”,HT[k].Rchild); } printf(“************************n”);} void Decode(int m,HTNode *HT) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=HT[i].Lchild; else i=HT[i].Rchild; if(HT[i].Lchild==0) //HT[i]是叶结点 { printf(“%c”,HT[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2') printf(“ERROR”);} int main() //主函数 { int n,m,c;HTNode HT[N];do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break; case 2:system(“cls”);Save(n,HT);break; case 3:system(“cls”);Print_H(m,HT);break; case 4:system(“cls”);Coding_H(n,HT);break; case 5:system(“cls”);Decode(m,HT);break; case 6:system(“cls”);Read(n,HT);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include //定义成绩信息结构体 { char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} void View()//输出函数 { p_node_score pNodeScore; pNodeScore=headScore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){ PrintScore(pNodeScore->data);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;} } void Add(){ p_node_score pNodeScore;// 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL;} else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱 p1=headScore;if(p1==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char DeleteNumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf(“没有此学号的学生！”);} int Change(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); printf(“成绩已经修改！”); return 0; } pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int Find(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headScore=NULL;int c;do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);Input();break; case 2:system(“cls”);View();break; case 3:system(“cls”);Add();break; case 4:system(“cls”);Change();break; case 5:system(“cls”);Delete();break; case 6:system(“cls”);Find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 课程设计报告的内容 设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、目录、正文.正文包括以下7个内容: 1.需求分析 陈述说明程序设计的任务,强调的是程序要做什么，需要什么结果、所能达到的功能.2.概要设计 说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计 实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析 内容包括: a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想; c.经验和体会等.5.测试结果 列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献 列出参考的相关资料和书籍.封面格式如下： 数据结构课程设计报告 班级：_____ _____ _____ _________ 姓名：____________________ 指导教师：___________________ 成绩：__________________________ 信息工程学院 年月日 目录 1.需求分析 ……………………………………………… 22．概要设计………………………………………………2 3.详细设计 ………………………………………………2 4.调试分析 ………………………………………………2 5.测试结果… ……………………………………………2 参考文献 …………………………………………………6 附录…………………………………………………… 一、需求分析 二、概要设计 三、详细设计 四、调试分析 五、测试结果 六、参考文献 七、附录 附录为程序代码！4第二篇：C++ 数据结构 课程设计报告 计算表达式
第三篇：2012数据结构课程设计
第四篇：数据结构课程设计
第五篇：《数据结构》课程设计文档格式（定稿）
点击咨询 