软件综合课程设计神秘国度的爱情故事活期储蓄帐目管理二〇一四年六月神秘国度的爱情故事1．问题陈述输入要求：输入由若干组测试数据组成。
每组数据的第1行包含一正整数n（1≤n≤50000），代表神秘国度中小村的个数，每个小村即从0到n-1编号。
接下来有n-1行输入，每行包含一条双向道路的两端小村的编号，中间用空格分开。
之后一行包含一正整数m（1≤m≤500000），代表着该组测试问题的个数。
接下来m行，每行给出a,b,c 三个小村的编号，中间用空格分开。
当n为0时，表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组测试给定的a,b,c，在一行里输出答案，即：如果c在a和b 之间的路径上，输出yes,否则输出no。
2．程序代码//神秘国度的爱情故事代码#include<iostream>using namespace std;#define maxnode 100 //图中顶点的最大个数typedef char elemtype; //顶点的数据类型struct node //定义边的表结点{ int adjvex; //邻接点在顶点向量中的下标 struct node *next; //指向下一邻接点的指针};typedef struct //定义顶点结点{ elemtype vertex; //顶点信息node *firstarc; //指向第一邻接点的指针 }vernode;typedef struct{ vernode vertices[maxnode];//定义邻接表int vexnum,arcnum; //顶点和边的数目}algraph;algraph creatgraph(algraph g){//建立图函数int i,j,k; //i，j，k用于边和顶点的建立 node *p; //用于新生成顶点的指针cout<<输入小村的个数：<<endl;cin>>g.vexnum;g.arcnum=g.vexnum-1;for(i=0;i<g.vexnum;i++){g.vertices[i].firstarc=null;}cout<<输入道路两端小村的编号（<<g.vexnum-1<<次，中间用空格分开）：<<endl;for(k=0;k<g.arcnum;k++){cin>>i>>j;p=(node*)malloc(sizeof(node));p->adjvex=j;p->next=g.vertices[i].firstarc;g.vertices[i].firstarc=p;//用头插法 p=(node*)malloc(sizeof(node));p->adjvex=i;p->next=g.vertices[j].firstarc;g.vertices[j].firstarc=p;}return g;}int visited[maxnode]; //用于深度遍历记住遍历过的顶点algraph g; //全局图int w; //记住c【j】点int count=0; //计数器，深度优先后，保存是否在ab间 int count1=0; //辅助计数器，判断abc是否重复void dfs(algraph g,int a,int b,int c){//g为邻接表存储的图，从第v个顶点出发递归的深度优先遍历函数if(a==c||b==c)count1++; //如果遍历到a或b点辅助计数器加一visited[c]=1; node *p;p=(node*)malloc(sizeof(node)); //为p申请空间p=g.vertices[c].firstarc; //指向c的第1邻接点的指针 while(p!=null){if(!visited[p->adjvex]){ dfs(g,a,b,p->adjvex); } //访问p的顶点向量中的下标if(p->adjvex==w&&count1==1)count=1; //如果辅助计数器为一且遍历返回到c时计数器为一if(count==1)break;p=p->next; //遍历到已被遍历的顶点从此顶点的下一邻接点}}void if(algraph g){ //判断c是否在a和b之间，原理是判断是否在一次探测，还是产生回溯int d; //d为判断的次数cout<<输入测试的次数：<<endl;cin>>d;值 int a[10],b[10],c[10]; //记住每次用于测试a、b、c的cout<<输入a,b,c三个小村的编号（<<d<<次，中间用空格分开）：<<endl;for(int i=0;i<d;i++){ cin>>a[i]>>b[i]>>c[i]; }cout<<显示测试结果：<<endl;for(int j=0;j<d;j++){w=c[j];dfs(g,a[j],b[j],c[j]);if(count==1)cout<<yes恭喜你将找到命中的恋人<<endl;//在遍历a 或b后又重新遍历到cif(count==0)cout<<no你将与她错过 <<endl; //在遍历了a和遍历了b之后又从新遍历到cfor(int k=0;k<=g.vexnum;k++)visited[k]=0;count=0;count1=0; //计数器清0}}void main(){cout<< 《故事背景介绍》\n<<endl;cout<< /* 欢迎来到神秘国度，在神秘国度里你将找到命中的恋人*/\n<<endl;cout<< 。
请按照提示信息寻找爱情。
\n<<endl; g=creatgraph(g);//调用图建立函数if(g);//调用判断函数 }3．运行结果4．设计体会与总结通过此次的课程试验的练习，我有了很大的收获，同时也加深了对数据结构这门课程的理解，比如说：图的邻接表存储，深度优先搜索树等。
在这次课程设计中，我感受最深的是学会了用”二分查找”的方法查找问题。
通过这次课程设计，我对c++编程有了更新的认识。
以前编程只是注重如何编写函数能够完成所需要的功能，凭单纯的意识和简单的语句来堆砌出一段程序。
现在编程有了深刻的感觉。
在编写一个程序之前，自己能够综合考虑各种因素，选取我们需要的数据结构，在编写每一个函数之前，仔细斟酌比对，挑选出最适合当前状况的算法。
这样，即使在完整的程序还没有写出来之前，我们心中已经有了明确的原图了，这样在无形中就提高了我们编写的程序的质量。
另外，还体会到深刻理解数据结构的重要性。
只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。
了解典型数据结构的性质也是非常有用的，而它往往是我们编写程序的关键。
活期储蓄帐目管理1．问题陈述活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：(1)能比较迅速地找到储户的帐户，以实现存款、取款记账；(2)能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。
2．需求分析需要先建立结本程序点类模板，然后使用链表的基本操作应用实现各个程序的实现，头插法先建立链表使之成当前操作数据基础，然后可以使用节点的删除进行储户的销户，结点的插入的应用成为程序的开户(注意：建立新的用户要先确认新建的用户号不可以与之前的用户号码相同, 引起系统错误!本程序应用链表节点的比较改进程序。
)。
储户的存取也是应用节点的比较查找之后进行的账户钱数加减。
程序的执行命令操作：(1)建立节电类模板,构建链表 (2)输入储户信息(3)执行各项操作(数据测试)：①查询储户信息②开户③储户支取信息查询④储户的程序销户⑤程序完成 (4)程序退出3．概要设计（1）结构设计说明1.本程序主要应用数据结构节点类模板，首先构建节点类模板，在建立已有储户数据中对头结点（*head）分配动态存储空间，对头结点的邻接点（head->next）赋初值，循环插入新结点建立储户数据（头插法）。
在账号循环插入中进行账号重复判断。
2.在查找账户的过程中，应用结点下移继续查找，实现账户正确查找应用。
3.在销户过程中，进行结点删除,从而实现储户的销户。
4.在开户过程中，定义新结点，分配新的存储空间，进行结点插入，在账号循环插入中进行账号重复判断，完成开户过程。
5.在存取记录过程中，应用结点下移进行循环查找账户信息，显示账户信息。
6.主函数测试。
（2）程序流程图4．详细设计//活期储蓄帐目管理#include<iostream> #include<string> using namespace std;template<class t>//构建节点类模板string name; cout<<请输入账户号（八位整数）: ;cin>>number; number=number;class node {public:node<t> *next;// t 可省指针 string name; t data;long int number; };template<class t> class savinglist {public:savinglist(){};node<t> * creatsavinglist(); void searchaccount(long int x);node<t> * deleteaccount(long int x);node<t> * insertaccount(long int x);private:node<t> *head; };template<class t> //建立已有储户数据 node<t> * savinglist<t>::creatsavinglist() {head=new node<t>;//初值int k=1;//分配动态空间node<t> *p,*q;head->next=null;// 赋初值 long int number,number; int data;if(!q)cout<<请输入姓名: ; cin>>name;cout<<请输入账户余额: ; cin>>data;while(number/1e7>=1 && number/1e7<=10){ p=new node<t>; q=new node<t>;p->number=number;//节点初值p->name=name; p->data=data;p->next=head->next;//将p插入连中head->next=p;cout<<是否继续输入信息按1继续输入按0退出<<endl; cin>>k; if(k==0) break;cout<<请输入账户号（八位整数）: ;cin>>number; q=head->next;while(q)//账号的重复判断 {if(q->number==number) {cout<<账号已存在 !<<endl;break; } elseq=q->next; }{cout<<请输入姓名: };cin>>name;cout<<请输入账户余额: ;cin>>data; } }return head; }template<class t> //查找账户 voidsavinglist<t>::searchaccount(long int x) { if(x/1e7<1||x/1e7>10) {cout<<您输入的账户不存在<<endl;return ; }node<long> *p; p=head;while(p!=null && {p=p->next;//向下移位继续查找 }if(p==null) {cout<<您输入的账户未找到<<endl; } else {cout<<账户名： <<p->name<<endl;cout<<账户号码： <<p->number<<endl;cout<<账户余额：<<p->data<<元<<endl; }cout<<您的新账户的信息是:<<endl; template<class t> //销户node<t> * savinglist<t>::deleteaccount(long int x) {node<t> *p,*q;//节点类型 p=head;while(p!=null&&p->number!=x) {q=p;p=p->next; }if(p==null) {cout<<您输入的账户已不存在<<endl; } else {q->next=p->next;//将q删掉 }return head; }template<class t> //开户node<t> * savinglist<t>::insertaccount(long int x) {node<t> *p,*q; q=new node<t>; char w[10];//名字 int i; p=head;q->number=x; q->next=p->next;p->next=q;//插入 q(新的账号) cout<<请输入姓名: ;cin>>w;cout<<请输入余额: ; cin>>i; q->name=w; q->data=i; cout<<账户名： <<q->name<<endl;cout<<账户号码： <<q->number<<endl;cout<<账户余额：<<q->data<<元<<endl; return head; }template<class t> //存取款记录void savinglist<t>::record(long <<p->data<<元<<endl; } } }int menu() {int n;cout<<--------------------------menu------------------------int x,int y) {node<t> *p; p=head;while(p!=null && p->number!=x) //循环查找p的相同正确值节点下移 {p=p->next; }if(p==null)cout<<您输入的账户不存在<<endl; else {p->data=p->data+y; if(p->data<0)cout<<余额不足请充值！<<endl; else {cout<<目前您的账户信息：<<endl;cout<<账户名（八位）： <<p->name<<endl;cout<<账户号码： <<p->number<<endl;cout<<账户余额： for(;;) {switch (menu()) {case 1: {cout<<请输入您要查询的账户：;---<<endl;cout<<\t1.查询账户 2.开户\n\n<<endl; cout<<\t3.支出存储记录 4.销户\n\n<<endl; cout<<\t5.退出<<endl;cout<<---------------------------------------------------------;cout<<endl; do {cout<<请输入你的选择(1--5):\n<<endl; cin>>n; }while(n<1||n>5); return n; }int main() {savinglist<long> t; node<long> *head;head=t.creatsavinglist(); long int x; int y,n;cin>>x;t.searchaccount(x); cout<< 是否需要继续进行操作？是请输入1，放弃则输入0: ;cin>>y; if(y==1) {cout<<-----------------------------------------------------\n\n\n;cout<<\t1.支出存入 2.销户\n\n;cout<<-----------------------------------------------------\n\n\n;do {cout<<请输入你选择的操作 : ;cin>>n; }while(n!=1 && n!=2); if(n==1) {cout<<请输入你存取的钱数: ;cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ”<<endl;int a; cin>>a;t.record(x,a); }if(n==2) {cout<<销户请输入 1，不进行操作输入 0 !: ; int b;cin>>b; if(b==1)t.deleteaccount(x); } } }break; case 2:cin>>r;{long int c; node<long> *q; q=head->next; cout<<请输入您的账号（八位）: ;cin>>c; while(q) {if(q->number==c) {cout<<账号已存在 !<<endl;break; } elseq=q->next; }if(!q) {while(c/1e7 <1||c/ 1e7>10) { cout<<输入的位数不正确: ;cin>>c; }t.insertaccount(c); } }break; case 3: {long int r; int t,l;cout<<请输入执行操作的账号: ;cout<<请输入你存取的钱数: ;//cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ” {cout<<输入的位数不正确: ;<<endl;cin>>t;t.record(r,t); cout<<继续操作请输入 1 ，退出输入0:<<endl; cin>>l; while(l==1) {cout<<请输入执行操作的账号: ;cin>>r;cout<<请输入你存取的钱数: ;cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ”<<endl;cin>>t;t.record(r,t); cout<<继续操作请输入1，退出输入0<<endl; cin>>l; } }break; case 4: {long int k; int m;cout<<请输入你想要消掉的账户（请选择以上已有的） : ;cin>>k;while(k/1e7<1||k/1e7>9) 5．程序代码cin>>k; }t.deleteaccount(k);cout<<继续操作请输入1，退出输入0<<endl; cin>>m; while(m==1) {cout<<请输入要销掉的账户: ;cin>>k;while(k/1e7<1||k/1e7>10) {cout<<输入的位数不正确，请你确认后再进行操作！: ;}t.deleteaccount(k);cout<<继续操作请输入1，退出输入0<<endl; cin>>m; } }break; case 5:exit(0); } }return 0; }#include<iostream> #include<string> using namespace std;template<class t>//构建节点类模板 cout<<请输入账户号（八位整数）: ;cin>>number; number=number;class node {public:node<t> *next;// t 可省指针 string name; t data;long int number; };template<class t> class savinglist {public:savinglist(){};node<t> * creatsavinglist(); void searchaccount(long int x);node<t> * deleteaccount(long int x);node<t> * insertaccount(long int x);private:node<t> *head; };template<class t> //建立已有储户数据 node<t> * savinglist<t>::creatsavinglist() {head=new node<t>;//初值int k=1;//分配动态空间node<t> *p,*q;head->next=null;// 赋初值 long int number,number; int data; string name; if(!q) {cout<<请输入姓名: ; cout<<请输入姓名: ; cin>>name;cout<<请输入账户余额: ; cin>>data;while(number/1e7>=1&& number/1e7<=10) {p=new node<t>; q=new node<t>;p->number=number;//节点初值p->name=name; p->data=data;p->next=head->next;//将p插入连中head->next=p;cout<<是否继续输入信息按1继续输入按0退出<<endl; cin>>k; if(k==0) break;cout<<请输入账户号（八位整数）: ;cin>>number; q=head->next;while(q)//账号的重复判断 {if(q->number==number) {cout<<账号已存在 !<<endl; break; } elseq=q->next; }cin>>name;cout<<请输入账户余额: ;cin>>data;}}return head; }template<class t> //查找账户 voidsavinglist<t>::searchaccount(long int x) {if(x/1e7<1||x/1e7>10) {cout<<您输入的账户不存在<<endl;return ; }node<long> *p; p=head;while(p!=null && {p=p->next;//向下移位继续查找 }if(p==null) {cout<<您输入的账户未找到<<endl; } else { cout<<账户名：<<p->name<<endl;cout<<账户号码：<<p->number<<endl;cout<<账户余额：<<p->data<<元<<endl; } }template<class t> //销户node<t> * savinglist<t>::deleteaccount(long int x) {node<t> *p,*q;//节点类型 p=head;template<class t> //存取款记录void savinglist<t>::record(long while(p!=null&&p->number!=x) {q=p;p=p->next; }if(p==null) {cout<<您输入的账户已不存在<<endl; } else{q->next=p->next; }//将q删掉 return head; }template<class t> //开户node<t> * savinglist<t>::insertaccount(long int x) {node<t> *p,*q; q=new node<t>; char w[10];//名字 int i; p=head;q->number=x; q->next=p->next;p->next=q;//插入 q(新的账号) cout<<请输入姓名: ; cin>>w;cout<<请输入余额: ; cin>>i; q->name=w; q->data=i;cout<<您的新账户的信息是:<<endl; cout<<账户名： <<q->name<<endl;cout<<账户号码： <<q->number<<endl;cout<<账户余额：<<q->data<<元<<endl; return head; }int x,int y) {node<t> *p; p=head;while(p!=null && p->number!=x) //循环查找p的相同正确值节点下移 ---;cout<<endl; do {{p=p->next; }if(p==null)cout<<您输入的账户不存在<<endl; else {p->data=p->data+y; if(p->data<0)cout<<余额不足请充值！<<endl; else {cout<<目前您的账户信息：<<endl;cout<<账户名（八位）： <<p->name<<endl;cout<<账户号码： <<p->number<<endl;cout<<账户余额：<<p->data<<元<<endl; } } }int menu() {int n;cout<<--------------------------menu---------------------------<<end l;cout<<\t1.查询账户 2.开户\n\n<<endl; cout<<\t3.支出存储记录 4.销户\n\n<<endl; cout<<\t5.退出<<endl;cout<<------------------------------------------------------2.销户\n\n;cout<<请输入你的选择(1--5):\n<<endl; cin>>n; }while(n<1||n>5); return n; }int main() {savinglist<long> t; node<long> *head;head=t.creatsavinglist(); long int x; int y,n;for(;;) {switch (menu()) {case 1: {cout<<请输入您要查询的账户：;cin>>x;t.searchaccount(x); cout<< 是否需要继续进行操作？是请输入1，放弃则输入0: ;cin>>y; if(y==1) {cout<<-----------------------------------------------------\n\n\n; cout<<\t1.支出存入cout<<-----------------------------------------------------\n\n\n; do {cout<<请输入你选择的操作 : ;cin>>n; }while(n!=1 && n!=2); if(n==1) {cout<<请输入你存取的钱数: ;cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ”<<endl;int a; cin>>a;t.record(x,a); }if(n==2) {cout<<销户请输入 1，不进行操作输入 0 !: ; int b; cin>>b; if(b==1)t.deleteaccount(x); } } }break; case 2: {long int c; node<long> *q; q=head->next;cout<<请输入您的账号（八位）: ;cin>>c;while(l==1) while(q){if(q->number==c) {cout<<账号已存在 !<<endl;break; } elseq=q->next; }if(!q) {while(c/1e7 <1||c/ 1e7>10) { cout<<输入的位数不正确: ;cin>>c; } t.insertaccount(c); } }break; case 3: {long int r; int t,l;cout<<请输入执行操作的账号: ;cin>>r;cout<<请输入你存取的钱数: ;cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ”<<endl;cin>>t;t.record(r,t); cout<<继续操作请输入 1 ，退出输入0:<<endl; cin>>l; {cout<<请输入执行操作的账号: ;cin>>r;cout<<请输入你存取的钱数: ;cout<<存入钱数在前加“ + ”，取出钱数在前加“ - ”<<endl;cin>>t;t.record(r,t); cout<<继续操作请输入1，退出输入0<<endl; cin>>l; } }break; case 4: {long int k; int m;cout<<请输入你想要消掉的账户（请选择以上已有的） : ;cin>>k;while(k/1e7<1||k/1e7>9) {cout<<输入的位数不正确: ;cin>>k; }6．运行结果与测试t.deleteaccount(k);cout<<继续操作请输入1，退出输入0<<endl; cin>>m; while(m==1) {cout<<请输入要销掉的账户: ;cin>>k;while(k/1e7<1||k/1e7>10) {cout<<输入的位数不正确，请你确认后再进行操作！: ;}t.deleteaccount(k);cout<<继续操作请输入1，退出输入0<<endl; cin>>m;} }break; case 5:exit(0); } }return 0; }。