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

1、精选优质文档-倾情为你奉上景德镇陶瓷大学数据结构课程设计报告题 目： 3 7 14 16院系名称： 信息工程学院 专业名称： 信息与计算科学班 级： 15信息一班 学生姓名： 孟喜洋学号 ： 1指导教师： 杨利华 设计起止时间：2017.6.52017.6.16题目 3 一元多项式计算 1、实验目的1）、能够按照指数降序排列建立并输出多项式；2）、能够完成两个多项式的相加、相减，并将结果输入。2、实验要求在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。3. 存储结构 Typedef stru

2、ct 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是

3、否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项3、多项式的减法开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项5.源程序#include<iostream> #include<conio.h> #include<stdlib.h> using namespace std; stru

4、ct 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(L

5、ink &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个链表类型

6、结点的项，即创建一个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<<"系数:"

7、 cin>>(newp->data).coef; cout<<"指数:" cin>>(newp->data).exp; if(newp->data.exp<0) cout<<"您输入有误，指数不允许为负值!"<<endl; delete newp; i-; continue; newp->next=NULL; p=L; if(newp->data.coef=0) cout<<"系数为零，重新输入!"<<endl; d

8、elete newp; i-; continue; while(p->next!=NULL)&&(p->next->data).exp<(newp->data).exp) p=p->next; /p指向指数最小的那一个 if(!JudgeIfExpSame( L, newp) newp->next=p->next; p->next=newp; else cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl; delete newp; De

9、stroyLink(L); CreateLink(L,n); /创建多项式没有成功，递归调用重新创建 break; /*判断指数是否与多项式中已存在的某项相同*/ int JudgeIfExpSame(Link L,Link e) Link p;p=L->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->ne

10、xt=NULL) cout<<"该一元多项式为空！"<<endl; else p=L->next; /项的系数大于的种情况 if(p->data).coef>0) if(p->data).exp=0) cout<<(p->data).coef; else if(p->data).coef=1&&(p->data).exp=1) cout<<"x" else if(p->data).coef=1&&(p->data).exp

11、!=1) cout<<"x"<<(p->data).exp; else if(p->data).exp=1&&(p->data).coef!=1) cout<<(p->data).coef<<"x" else cout<<(p->data).coef<<"x"<<(p->data).exp; /项的系数小于的种情况 if(p->data).coef<0) if(p->data).ex

12、p=0) cout<<(p->data).coef; else if(p->data.coef=-1&&p->data.exp=1) cout<<"-x" else if(p->data.coef=-1&&p->data.exp!=1) cout<<"-x"<<p->data.exp; else if(p->data.exp=1) cout<<p->data.coef<<"x" els

13、e cout<<(p->data).coef<<"x"<<(p->data).exp; p=p->next; while(p!=NULL) if(p->data).coef>0) if(p->data).exp=0) cout<<"+"<<(p->data).coef; else if(p->data).exp=1&&(p->data).coef!=1) cout<<"+"<<(p-

14、>data).coef<<"x" else if(p->data).exp=1&&(p->data).coef=1) cout<<"+"<<"x" else if(p->data).coef=1&&(p->data).exp!=1) cout<<"+"<<"x"<<(p->data).exp; else cout<<"+"&l

15、t;<(p->data).coef<<"x"<<(p->data).exp; if(p->data).coef<0) if(p->data).exp=0) cout<<(p->data).coef; else if(p->data.coef=-1&&p->data.exp=1) cout<<"-x" else if(p->data.coef=-1&&p->data.exp!=1) cout<<&qu

16、ot;-x"<<p->data.exp; else if(p->data.exp=1) cout<<p->data.coef<<"x" else cout<<(p->data).coef<<"x"<<(p->data).exp; p=p->next; cout<<endl; /*把一个链表的内容复制给另一个链表*/ void CopyLink(Link &pc,Link pa) Link p,q,r; pc=new L

17、Node; pc->next=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); Cop

18、yLink(p2,pb); pc=new LNode; pc->next=NULL; p=pc; p1=p1->next; p2=p2->next; while(p1!=NULL&&p2!=NULL) if(p1->data.exp<p2->data.exp) p->next=p1; p=p->next; p1=p1->next; else if(p1->data.exp>p2->data.exp) p->next=p2; p=p->next; p2=p2->next; else p1-&

19、gt;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,Lin

20、k 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,

21、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;

22、 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() cout<<""<<endl; cout<<endl; cout<<"t=一元多项式的简单运算="<<endl; cout<<"tttttttt

23、"<<endl; cout<<"ttt 1 创建要运算的两个一元多项式tt "<<endl; cout<<"ttt 2 将两个一元多项式相加ttt "<<endl; cout<<"ttt 3 将两个一元多项式相减ttt "<<endl; cout<<"ttt 4 将两个一元多项式相乘ttt "<<endl; cout<<"ttt 5 显示两个一元多项式ttt "<

24、;<endl; cout<<"ttt 6 销毁所创建的二个多项式tt "<<endl; cout<<"ttt 7 退出ttttt "<<endl; cout<<"tttttttt "<<endl; cout<<"t=一元多项式的简单运算="<<endl; cout<<endl;cout<<"tt 请选择:" /判断输入的整数是不是为到的数字 int CompareIfNu

25、m(int i) if(i>0&&i<8) return 0; else return 1; void main() system("color b");/system("pause"); system("color a"); /system("pause"); int n; Link L,La=NULL,Lb=NULL;/La,Lb分别为创建的两个多项式 int choose; while(1) Menu(); /调用菜单函数 cin>>choose; switch(cho

26、ose) case 1: cout<<"请输入你要运算的第一个一元多项式的项数:"<<endl; cin>>n; if(CompareIfNum(n)=1) cout<<"您的输入有误，请重新输入"<<endl; Clear(); break; CreateLink(La,n); cout<<"请输入你要运算的第二个一元多项式的项数:"<<endl; cin>>n; if(CompareIfNum(n)=1) cout<<&qu

27、ot;您的输入有误，请重新输入"<<endl; Clear(); break; CreateLink(Lb,n); Clear(); break; case 2: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; PolyAdd(L,La,Lb); cout<<""<<endl; cout<<"待相加的两个一元多项式为："<<endl; cout<<

28、;""<<endl; cout<<"A的多项式为：" PrintList(La); cout<<""<<endl; cout<<"B的多项式为：" PrintList(Lb); cout<<""<<endl; cout<<"相加后的结果为：" PrintList(L); cout<<""<<endl; Clear(); DestroyLi

29、nk(L); break; case 3: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; PolySubstract(L,La,Lb); cout<<"相减的两个一元多项式为："<<endl; cout<<""<<endl; cout<<"A的多项式为：" PrintList(La); cout<<""<&l

30、t;endl; cout<<"B的多项式为：" PrintList(Lb);cout<<""<<endl; cout<<"相减后的结果为：" PrintList(L); cout<<""<<endl; Clear(); DestroyLink(L); break; case 4: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); b

31、reak; PolyMultiply(L,La,Lb); cout<<"相乘的两个一元多项式为："<<endl; cout<<""<<endl; cout<<"A的多项式为：" PrintList(La); cout<<""<<endl; cout<<"B的多项式为：" PrintList(Lb); cout<<""<<endl; cout<<&

32、quot;相乘后的结果为：" PrintList(L); DestroyLink(L); cout<<""<<endl; Clear(); break; case 5: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; cout<<"一元多项式A为："<<endl; PrintList(La); cout<<""<<endl;

33、cout<<"一元多项式B为："<<endl; PrintList(Lb); cout<<""<<endl; Clear(); break; case 6: if(La&&Lb) DestroyLink(La); DestroyLink(Lb); cout<<"多项式销毁成功！"<<endl; Clear(); else cout<<"多项式不存在，请重新选择"<<endl; Clear(); break

34、; case 7: exit(0); /exit(0)强制终止程序，返回状态码表示正常结束 default: cout<<"您的输入有误，请重新选择操作"<<endl; Clear(); break; /以上两个多项式的项数分别为4和3，所以该算法的时间复杂度为O(4+3)=O(7).6. 测试数据和结果题目 7 建立二叉树，层序、先序遍历1、实验目的要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；2. 实验要求在上交资料中请写明：存储结构、基本算法（可

35、以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。3. 存储结构typedef struct BiTNode TElemType data； Struct BiTNode *lchild，*rchild；BiTNode，*BiTree；4. 基本算法概要设计开始建立二叉树先序遍历 层序遍历结束ABCDEFG5,.源程序#include"stdio.h"#include "stdlib.h"#define maxsize 100typedef struct BTNodechar data;struct BTNode

36、*lchild,*rchild;BINode;void CreateBTNode(BTNode *&b,char str);void PreOrder(BTNode *b);void DispBTNode(BTNode *b); void LevelOrder(BTNode *b);/主函数设计void main ()BTNode *b; CreateBTNode (b,"a(b(d,e),c(f,g) ");printf("(1)输出二叉树:");DispBTNode (b);printf("n");printf("

37、;(2)层次遍历序列：");LevelOrder(b);printf("n");printf("(3)先序遍历序列：");PreOrder(b);printf("n");/建立二叉树void CreateBTNode (BTNode *&b,char str) BTNode *Stmaxsize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;/建立的二叉树初始时为空 ch=strj;while (ch!='0') /str未扫描时循环 switch (ch) case

38、'(':top+;Sttop=p;k=1;break;/为左孩子结点 case')':top-;break;case',':k=2;break;/为孩子结点右结点 default:p=(BTNode *)malloc (sizeof(BTNode);p->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->rchi

39、ld=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 (" ")

40、;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;/根结点指针进入队列

41、 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网络中是否存在回路，使的所有活

42、动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。2、实验要求（1）在有向图中选一个没有前驱的顶点，输出；（2）从有向图中删除该顶点及其该顶点出发的所有边；（3）重复以上两个步骤，直至全部顶点输出；注：输出所有拓扑排序可加分。3. 存储结构拓扑排序中，有向图采用邻接表存储结构,它是图的一种链式存储结构，图的邻接表存储表示如下：#define MVNum 100Typedef struct ArcNode int adjvex ; struct ArcNode * nextarc; OtherInfo info;ArcNode;typedef struct VNode; Ver

43、TexType data; ArcNode *firstarc;VNode, AdjListMVNum；typedef struct AdjList vertices; int vexnum,arcnum;ALGraph；4. 基本算法4.基本算法5.源程序#include <iostream>#include <stack>using namespace std;#define MAXV 50stack<int>mystack;int indegreeMAXV;struct nodeint adjvex; node *next;AdjListMAXV; /

44、邻接表建表函数，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<<"请输入第"<<i<<"条边:" int u,v; cin>>u>>v; p=new node; p->adjvex=v; p->next=AdjListu.n

45、ext; AdjListu.next=p; /邻接表打印函数void print(int n)int i;node *p;for(i=0; i<=n-1;i+)p=&AdjListi;while(p!=NULL)cout<<p->adjvex<<" "p=p->next;cout<<endl;void TopSort(node Adjlist,int n)int i;node *p;memset(indegree,0,sizeof(indegree);for(i=0;i<=n-1;i+)p=AdjListi

46、.next;while(p!=NULL)indegreep->adjvex+;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();cout<<i<<" "count+;for(p=AdjListi.next;p!=NULL;p=p->next)int k=p->adjvex;indegreek-;if(indegreek=0

47、)mystack.push(k);cout<<endl;if(count<n)cout<<"有回路"<<endl;void main()int n;int m;cout<<"请输入顶点数及边数:"cin>>n>>m;Create(AdjList,n,m);cout<<"输入的邻接表为:"<<endl;print(n);cout<<"拓扑排序结果为:"<<endl;TopSort(AdjLis

48、t,n);6.测试数据和结果题目16 航空客运订票系统*1、 实验目的航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。设计一个航空客运订票系统，以使上述业务可以借助计算机完成。2、 实验要求1） 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括名字、订票量、舱位等级1、2、3）以及等候替补的客户名单；2） 系统实现的功能如下：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣

49、，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件3、 提示可使用队列实现候补客户名单，航线情况可使用一静态表实现。4.存储结构航线的所有信息存储在一个结构体中，增加，查询，订票，退票等操作按队列的操作来实现。5.基本算法程序流程图：Switch(1)6.源程序#include <iostream.h>#include

50、<stdio.h>#include <string.h>#include <conio.h>#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 maken

51、ull(); 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()

52、;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(); cout<<endl<<"choose an operation: " cin>>c; if (c!='6') switch(c) case '0' : show_wait();break; case &

53、#39;1' : list_piao();book();break; case '2' : search_delete(1);break; case '3' : list_piao();break; case '4' : list_information();break; case '5' : search_delete(0);break; default : break; while(c!='6'); cout<<"Exit System "void makenull() makenull_piao(); makenull_inform