大二下学期数据结构课程设计实验报告

景德镇陶瓷大学数据结构课程设计报告题 目： 3 7 14 16院系名称： 信息工程学院 专业名称： 信息与计算科学班 级： 15信息一班 学生姓名： 孟喜洋学号 ： 1指导教师： 杨利华 设计起止时间：2017.6.52017.6.16题目 3 一元多项式计算 1、实验目的1）、能够按照指数降序排列建立并输出多项式；2）、能够完成两个多项式的相加、相减，并将结果输入。2、实验要求在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。3. 存储结构 Typedef struct PNode； float coef； Int expn； Struct PNode *next；Pnode，*Polynomial；4. 基本算法 1.概要设计1. 功能：将要进行运算的多项式输入输出。2. 数据流入：要输入的多项式的系数与指数。3. 数据流出：合并同类项后的多项式。4. 程序流程图：多项式输入流程图如图所示。5. 测试要点：输入的多项式是否正确，若输入错误则重新输入开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确2、多项式的加法开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项3、多项式的减法开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项5.源程序#include #include #include using namespace std; struct Node float coef;/结点类型 int exp; ; typedef Node polynomial;struct LNode polynomial data;/链表类型 LNode *next; ; typedef LNode* Link; void CreateLink(Link &L,int n); void PrintList(Link L); void PolyAdd(Link &pc,Link pa,Link pb); void PolySubstract(Link &pc,Link pa,Link pb); void CopyLink(Link &pc,Link pa); void PolyMultiply(Link &pc,Link pa,Link pb); int JudgeIfExpSame(Link pa,Link e); void DestroyLink(Link &L); int CompareIfNum(int i); void DestroyLink(Link &L) Link p; p=L-next; while(p) L-next=p-next; delete p; p=L-next; delete L; L=NULL; /创建含有n个链表类型结点的项，即创建一个n项多项式 void CreateLink(Link &L,int n) if(L!=NULL) DestroyLink(L); Link p,newp; L=new LNode; L-next=NULL; (L-data).exp=-1;/创建头结点 p=L; for(int i=1;i=n;i+) newp=new LNode; cout请输入第i项的系数和指数:endl; cout(newp-data).coef; cout(newp-data).exp; if(newp-data.exp0) cout您输入有误，指数不允许为负值!next=NULL; p=L; if(newp-data.coef=0) cout系数为零，重新输入!next!=NULL)&(p-next-data).expdata).exp) p=p-next; /p指向指数最小的那一个 if(!JudgeIfExpSame( L, newp) newp-next=p-next; p-next=newp; else cout输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式next; while(p!=NULL&(e-data.exp!=p-data.exp) p=p-next; if(p=NULL)return 0; else return 1; /*输出链表*/ void PrintList(Link L) Link p; if(L=NULL|L-next=NULL) cout该一元多项式为空！next; /项的系数大于的种情况 if(p-data).coef0) if(p-data).exp=0) coutdata).coef; else if(p-data).coef=1&(p-data).exp=1) coutdata).coef=1&(p-data).exp!=1) coutxdata).exp; else if(p-data).exp=1&(p-data).coef!=1) coutdata).coefx; else coutdata).coefxdata).exp; /项的系数小于的种情况 if(p-data).coefdata).exp=0) coutdata).coef; else if(p-data.coef=-1&p-data.exp=1) coutdata.coef=-1&p-data.exp!=1) cout-xdata.exp; else if(p-data.exp=1) coutdata.coefx; else coutdata).coefxdata).exp; p=p-next; while(p!=NULL) if(p-data).coef0) if(p-data).exp=0) cout+data).coef; else if(p-data).exp=1&(p-data).coef!=1) cout+data).coefdata).exp=1&(p-data).coef=1) cout+data).coef=1&(p-data).exp!=1) cout+xdata).exp; else cout+data).coefxdata).exp; if(p-data).coefdata).exp=0) coutdata).coef; else if(p-data.coef=-1&p-data.exp=1) coutdata.coef=-1&p-data.exp!=1) cout-xdata.exp; else if(p-data.exp=1) coutdata.coefx; else coutdata).coefxdata).exp; p=p-next; coutnext=NULL; r=pc; p=pa; while(p-next!=NULL) q=new LNode; q-data.coef=p-next-data.coef; q-data.exp=p-next-data.exp; r-next=q; q-next=NULL; r=q; p=p-next; /*将两个一元多项式相加*/ void PolyAdd(Link &pc,Link pa,Link pb) Link p1,p2,p,pd; CopyLink(p1,pa); CopyLink(p2,pb); pc=new LNode; pc-next=NULL; p=pc; p1=p1-next; p2=p2-next; while(p1!=NULL&p2!=NULL) if(p1-data.expdata.exp) p-next=p1; p=p-next; p1=p1-next; else if(p1-data.expp2-data.exp) p-next=p2; p=p-next; p2=p2-next; else p1-data.coef=p1-data.coef+p2-data.coef; if(p1-data.coef!=0) p-next=p1; p=p-next; p1=p1-next; p2=p2-next; else pd=p1; p1=p1-next; p2=p2-next; delete pd; if(p1!=NULL) p-next=p1; if(p2!=NULL) p-next=p2; /*将两个多项式相减*/ void PolySubstract(Link &pc,Link pa,Link pb) Link p,pt; CopyLink(pt,pb); p=pt; while(p!=NULL) (p-data).coef=(-(p-data).coef); p=p-next; PolyAdd(pc,pa,pt); DestroyLink(pt); /清屏函数 void Clear() system(pause); system(cls); /*将两个一元多项式相乘*/ void PolyMultiply(Link &pc,Link pa,Link pb) Link p1,p2,p,pd,newp,t; pc=new LNode; pc-next=NULL; p1=pa-next; p2=pb-next; while(p1!=NULL) pd=new LNode; pd-next=NULL; p=new LNode; p-next=NULL; t=p; while(p2) newp=new LNode; newp-next=NULL; newp-data.coef=p1-data.coef*p2-data.coef; newp-data.exp=p1-data.exp+p2-data.exp; t-next=newp; t=t-next; p2=p2-next; PolyAdd(pd,pc,p); CopyLink(pc,pd); p1=p1-next; p2=pb-next; DestroyLink(p); DestroyLink(pd); /菜单函数 void Menu() coutendl; coutendl; coutt=一元多项式的简单运算=endl; couttttttttt endl; coutttt 1 创建要运算的两个一元多项式tt endl; coutttt 2 将两个一元多项式相加ttt endl; coutttt 3 将两个一元多项式相减ttt endl; coutttt 4 将两个一元多项式相乘ttt endl; coutttt 5 显示两个一元多项式ttt endl; coutttt 6 销毁所创建的二个多项式tt endl; coutttt 7 退出ttttt endl; couttttttttt endl; coutt=一元多项式的简单运算=endl; coutendl;cout0&ichoose; switch(choose) case 1: cout请输入你要运算的第一个一元多项式的项数:n; if(CompareIfNum(n)=1) cout您的输入有误，请重新输入endl; Clear(); break; CreateLink(La,n); cout请输入你要运算的第二个一元多项式的项数:n; if(CompareIfNum(n)=1) cout您的输入有误，请重新输入endl; Clear(); break; CreateLink(Lb,n); Clear(); break; case 2: if(La=NULL|Lb=NULL) cout您的多项式创建有误，请重新选择endl; Clear(); break; PolyAdd(L,La,Lb); coutendl; cout待相加的两个一元多项式为：endl; coutendl; coutA的多项式为：; PrintList(La); coutendl; coutB的多项式为：; PrintList(Lb); coutendl; cout相加后的结果为：; PrintList(L); coutendl; Clear(); DestroyLink(L); break; case 3: if(La=NULL|Lb=NULL) cout您的多项式创建有误，请重新选择endl; Clear(); break; PolySubstract(L,La,Lb); cout相减的两个一元多项式为：endl; coutendl; coutA的多项式为：; PrintList(La); coutendl; coutB的多项式为：; PrintList(Lb);coutendl; cout相减后的结果为：; PrintList(L); coutendl; Clear(); DestroyLink(L); break; case 4: if(La=NULL|Lb=NULL) cout您的多项式创建有误，请重新选择endl; Clear(); break; PolyMultiply(L,La,Lb); cout相乘的两个一元多项式为：endl; coutendl; coutA的多项式为：; PrintList(La); coutendl; coutB的多项式为：; PrintList(Lb); coutendl; cout相乘后的结果为：; PrintList(L); DestroyLink(L); coutendl; Clear(); break; case 5: if(La=NULL|Lb=NULL) cout您的多项式创建有误，请重新选择endl; Clear(); break; cout一元多项式A为：endl; PrintList(La); coutendl; cout一元多项式B为：endl; PrintList(Lb); coutendl; Clear(); break; case 6: if(La&Lb) DestroyLink(La); DestroyLink(Lb); cout多项式销毁成功！endl; Clear(); else cout多项式不存在，请重新选择endl; Clear(); break; case 7: exit(0); /exit(0)强制终止程序，返回状态码表示正常结束 default: cout您的输入有误，请重新选择操作data=ch;p-lchild=p-rchild=NULL;if (b=NULL)/*p为二叉树的根结点 b=p;else switch (k)/已建立二叉树根结点 case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;return;/用递归算法的先序遍历函数void PreOrder(BTNode *b)if(b!=NULL)printf (%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);void DispBTNode (BTNode *b) if (b!=NULL)printf (%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL) printf ( );DispBTNode (b-lchild);/递归处理左子树 if (b-rchild!=NULL)printf ( );DispBTNode (b-rchild); /递归处理右子树 printf ( );return;/用非递归算法的层序遍历void LevelOrder (BTNode *b) BTNode *p;BTNode *qu50;/定义环形队列，存放结点指针 int front,rear;/定义队头和队尾指针 front=rear=-1;/置队列为空队列 rear+;qurear=b;/根结点指针进入队列 while (front!=rear) /队列不为空 front=(front+1)%50;p=qufront;/队头出队列 printf (%c ,p-data); /访问结点 if (p-lchild!=NULL)/有左孩子时将其进队 rear=(rear+1)%50;qurear=p-lchild;if (p-rchild!=NULL) /有右孩子时将其进队 rear=(rear+1)%50;qurear=p-rchild;6. 测试数据和结果题目14 拓扑排序1、实验目的拓扑排序可判断AOV网络中是否存在回路，使的所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。2、实验要求（1）在有向图中选一个没有前驱的顶点，输出；（2）从有向图中删除该顶点及其该顶点出发的所有边；（3）重复以上两个步骤，直至全部顶点输出；注：输出所有拓扑排序可加分。3. 存储结构拓扑排序中，有向图采用邻接表存储结构,它是图的一种链式存储结构，图的邻接表存储表示如下：#define MVNum 100Typedef struct ArcNode int adjvex ; struct ArcNode * nextarc; OtherInfo info;ArcNode;typedef struct VNode; VerTexType data; ArcNode *firstarc;VNode, AdjListMVNum；typedef struct AdjList vertices; int vexnum,arcnum;ALGraph；4. 基本算法4.基本算法5.源程序#include #include using namespace std;#define MAXV 50stackmystack;int indegreeMAXV;struct nodeint adjvex; node *next;AdjListMAXV; /邻接表建表函数，n代表定点数，m代表边数void Create(node Adjlist,int n, int m) int i; node *p; for(i=0;i=n-1;i+) AdjListi.adjvex=i; AdjListi.next=NULL; for(i=0;i=m-1;i+) cout请输入第iuv; p=new node; p-adjvex=v; p-next=AdjListu.next; AdjListu.next=p; /邻接表打印函数void print(int n)int i;node *p;for(i=0; i=n-1;i+)p=&AdjListi;while(p!=NULL)coutadjvexnext;coutendl;void TopSort(node Adjlist,int n)int i;node *p;memset(indegree,0,sizeof(indegree);for(i=0;iadjvex+;p=p-next;for(i=0;i=n-1;i+)if(indegreei=0) mystack.push(i);int count=0;while(mystack.size()!=0)i=mystack.top();mystack.pop();coutinext)int k=p-adjvex;indegreek-;if(indegreek=0)mystack.push(k);coutendl;if(countn)cout有回路endl;void main()int n;int m;coutnm;Create(AdjList,n,m);cout输入的邻接表为:endl;print(n);cout拓扑排序结果为:endl;TopSort(AdjList,n);6.测试数据和结果题目16 航空客运订票系统*1、 实验目的航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。设计一个航空客运订票系统，以使上述业务可以借助计算机完成。2、 实验要求1） 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括名字、订票量、舱位等级1、2、3）以及等候替补的客户名单；2） 系统实现的功能如下：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件3、 提示可使用队列实现候补客户名单，航线情况可使用一静态表实现。4.存储结构航线的所有信息存储在一个结构体中，增加，查询，订票，退票等操作按队列的操作来实现。5.基本算法程序流程图：Switch(1)6.源程序#include #include #include #include #define m 4 /3架飞机#define n 5 /每架飞机5张票struct node char name21; char id21; int seat,plane,date; node *next,*pre;struct wait char name21; char id21; char phone8; int seat,plane,date,count; wait *next,*pre;struct piao int seatn+1;void makenull(); void makenull_piao();void makenull_information();void list_menu();void list_piao();void makenull_wait();void list_information();void plane_information(node *head);void book();void add_information(node *head,int x,int y);void add_wait(int x,int y);void search_delete(int x);void write_to_file();void show_wait();bool comp(node *x,node*y);node *head1,*head2,*head3,*q;wait *wait_head,*wait_end;char c;piao am;void main() makenull(); do list_menu(); coutendlc; if (c!=6) switch(c) case 0 : show_wait();break; case 1 : list_piao();book();break; case 2 : search_delete(1);break; case 3 : list_piao();break; case 4 : list_in