数据结构什么的早就不是问题,就当自己巩固一下基础吧,后期同学们也要一个一个细节问啊问怎么搞,任务本来就要求写一个就好了,鬼知道我的学号对应的是最简单的,无趣,那么还是全部做一遍吧,供同学们参考一些细节呀,千万要独立思考,不要抄袭啊QWQ,不然以后还是不会做的。全部代码都在GCC 9.2.0通过。安装一个Dev c++即可以运行代码,有些可能要一点的gcc版本哦!
熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。
在本次实践专题过程中要求学生:
(1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务;
(2)按照实践专题的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者本次实践专题课程成绩皆以零分计。凡发现实验报告或源程序雷同,涉及的全部人员本次实践专题的课程成绩皆以零分计。
(3)认真撰写实践专题报告。
1、问题分析和任务定义;
2、数据类型和系统设计;
3、编码实现;
4、上机调试;
5、总结和整理课程设计报告。
考核分为两个部分:
问题描述:
设有两个带头结点的单循环链表存储的集合A、B,其元素类型是int且以非递减方式存储,其头结点分别为ha、hb。要求下面各问题中的结果集合同样以非递减方式存储,结果集合不影响原集合。
实现要求:
测试数据: 由同学们自定,但集合A、B的元素个数不得少于16个。
#include<bits/stdc++.h> using namespace std; const int N=1000; struct SET{ struct Node{ int val; int prev,nex; }node[N];//数组模拟链表 int head,tail; int tot=0; SET(){tot=0;init();} void init(){ tot=2; head=1,tail=2; node[head].nex=tail; node[tail].prev=head; } void insert(int p,int val){//指定位置插入 int q=++tot; node[q].val=val; node[node[p].nex].prev=q; node[q].nex=node[p].nex; node[p].nex=q; node[q].prev=p; } void insert(int val){//插入 for(int i=node[head].nex;i!=tail;i=node[i].nex){ if(node[i].val>val){ insert(node[i].prev,val); return; } } insert(node[tail].prev,val); } void remove(int p){//删除 node[node[p].prev].nex=node[p].nex; node[node[p].nex].prev=node[p].prev; } void clear(){//清空 memset(node,0,sizeof(node)); head=tail=0; } bool in_set(int val){//是否存在 for(int i=node[head].nex;i!=tail;i=node[i].nex){ if(node[i].val==val) return true; } return false; } void output(){ for(int i=node[head].nex;i!=tail;i=node[i].nex) printf("%d ",node[i].val); puts(""); } SET operator | (const SET &A) const {//集合的并 SET C; for(int i=A.node[head].nex;i!=A.tail;i=A.node[i].nex) C.insert(A.node[i].val); for(int i=node[head].nex;i!=tail;i=node[i].nex){ if(!C.in_set(node[i].val)){ C.insert(node[i].val); } } return C; } SET operator & ( SET &A) const {////集合的交 SET C; for(int i=node[head].nex;i!=tail;i=node[i].nex){ if(A.in_set(node[i].val)){ C.insert(node[i].val); } } return C; } SET operator - ( SET &A) const {//集合的差 SET C; for(int i=node[head].nex;i!=tail;i=node[i].nex){ if(!A.in_set(node[i].val)){ C.insert(node[i].val); } } return C; } }; void menu(){ printf("1.输入集合A,B\n"); printf("2.A与B的并\n"); printf("3.A与B的交\n"); printf("4.A与B的差\n"); printf("5.A与B的对称差\n"); printf("0.退出\n"); printf("输入选择:"); } void run(){ int ch; SET A,B,C; do{ menu(); cin>>ch; switch(ch){ case 1: int n; printf("输入集合A的元素个数:"); cin>>n; for(int i=1;i<=n;i++){ int val;cin>>val; if(!A.in_set(val)) A.insert(val); } printf("集合A:");A.output(); printf("输入集合B的元素个数:"); cin>>n; for(int i=1;i<=n;i++){ int val;cin>>val; if(!B.in_set(val)) B.insert(val); } printf("集合B:");B.output(); break; case 2:printf("A|B: ");C=A|B;C.output();break; case 3:printf("A&B: ");C=A&B;C.output();break; case 4:printf("A-B: ");C=A-B;C.output();break; case 5:printf("A对称差B: "); C=(A-B)|(B-A);C.output(); break; } }while(ch); } int main(){ run(); return 0; }
问题描述
假设某年级有4个班,每班有n(n>40)名同学。本学期有5门课程考试,每门课程成绩是百分制。假定每个同学的成绩记录包含:学号、各门课程的成绩共6项,其中学号是一个12位的字符串(参照同学们的学号),每个学生都有唯一的学号,并且这4个班的成绩分别放在4个数组中,完成以下操作要求:
实现要求:
测试数据:
由同学们自己输入。
#include<bits/stdc++.h> using namespace std; const int N=10000; #define pb push_back struct Person { long long id; int ma,en,sc,bg,ph,sum; double avg; }p[N]; //随机数 int random(){ return (long long)rand()*rand()%101; } //产生学生成绩 void create_student(int m,int n){ long long id=201841404100; for(int i=1;i<=n*m;i++){ p[i].id=++id; if((id%100)>=n) id=(id/100+1)*100; p[i].bg=random(); p[i].en=random(); p[i].ma=random(); p[i].ph=random(); p[i].sc=random(); p[i].sum=p[i].bg+p[i].en+p[i].ma+p[i].ph+p[i].sc; p[i].avg=1ll*p[i].sum/5; } } //希尔排序 void shellsort(int n){ for(int len=n/2;len;len>>=1) for(int i=len+1;i<n;i++){ Person tmp=p[i]; int j=i; if(p[j].avg>p[j-len].avg){ for(;tmp.avg>p[j-len].avg&&j-len>0;j-=len){ p[j]=p[j-len]; } p[j]=tmp; } } } //堆排序 void heapify(int n,int i){ if(i>=n) return; int c1=i<<1; int c2=i<<1|1; int maxn=i; if(c1<n&&p[c1].avg<p[maxn].avg) maxn=c1; if(c2<n&&p[c2].avg<p[maxn].avg) maxn=c2; if(maxn!=i){ swap(p[maxn],p[i]); heapify(n,maxn); } } void build_heap(int n){ int last=n; int pa=n/2; for(int i=pa;i>=1;i--) heapify(n,i); } void heapsort(int n){ build_heap(n); for(int i=n;i;i--){ swap(p[i],p[1]); heapify(i,1); } } //快速排序 void quicksort(int l,int r){ if(l<r){ int i=l,j=r; Person tmp=p[l]; while(i<j){ while(i<j&&p[j].avg<=tmp.avg) j--; if(i<j) p[i++]=p[j]; while(i<j&&p[i].avg>=tmp.avg) i++; if(i<j) p[j--]=p[i]; } p[i]=tmp; quicksort(l,i-1); quicksort(i+1,r); } } void dispaly(int x,int n){ printf("第%d班的成绩表如下:\n",x); for(int i=1;i<=n;i++){ if((p[i].id)%1000/100==x) printf("%13lld %4d %4d %4d %4d %4d %5.2lf\n",p[i].id,p[i].bg,p[i].en,p[i].ma,p[i].ph,p[i].sc,p[i].avg); } } //基数排序 void radixsort(int n){ int maxn=p[1].sum; for(int i=1;i<=n;i++) if(maxn<p[i].sum) maxn=p[i].sum; int exp=1; while(maxn/exp){ vector<Person> box[11]; for(int i=1;i<=n;i++) box[(p[i].sum/exp)%10].pb(p[i]); for(int k=0,j=9;j>=0;j--) for(auto e:box[j]) p[++k]=e; exp*=10; } } void menu(){ printf("1.希尔排序\n"); printf("2.堆排序\n"); printf("3.快速排序\n"); printf("4.基数排序\n"); printf("5.打印某班成绩信息\n"); printf("输入你的选择:"); } void run(int m,int n){ int ch; int x; do{ menu(); cin>>ch; switch(ch){ case 1: shellsort(n*m);break; case 2: heapsort(n*m); break; case 3: quicksort(1,n*m);break; case 4: radixsort(n*m); break; case 5: printf("输入班级:"); cin>>x; dispaly(x,n*m); break; } }while(ch); } int main(){ int n,m; printf("请输入班级个数,以及班级人数:"); cin>>m>>n; create_student(m,n); run(m,n); return 0; }
题目描述:
二叉树的操作。
基本要求:
定义实现以下二叉树操作的函数(要求用非递归方式)
#include<bits/stdc++.h> using namespace std; const int N=1000; int at[N]; int n; void menu(){ printf("\n1.根据二叉链表表示的树计算该二叉树中值最大的第1个结点的指针及最大值\n"); printf("2.计算二叉树的高度\n"); printf("3.计算二叉树的宽度\n"); printf("4.交换每个节点的两个子节点\n"); printf("5.输出二叉树序列\n"); printf("0.退出\n"); printf("输入你的选择:"); } //高度 int h(int n){ if(n==8) return 4; //计算机表示不了? 计算机log(8)/log(2)+1居然等于3? return log(n)/log(2)+1; } //最大宽度 int b(int n){ if(n==1) return 1; if(n==(1<<h(n))-1) return 1<<(h(n)-1); else{ if(n-((1<<(h(n)-1))-1)>((1<<(h(n)-2)))) return n-((1<<(h(n)-1))-1); else return (1<<(h(n)-2)); } } //交换左右节点 (不是交换左右子树) //非递归版 void SW(){ for(int i=1;i<=n;i++){ if(at[i<<1|1]&&at[i<<1]) swap(at[i<<1],at[i<<1|1]); } } //递归版(供给大家理解) void SWAP(int p){ if(at[p<<1]) SWAP(p<<1); if(at[p<<1|1]) SWAP(p<<1|1); if(at[p<<1|1]&&at[p<<1]) swap(at[p<<1],at[p<<1|1]); } //输出序列 void output(){ printf("AT:"); for(int i=1;i<=n;i++) printf("%d ",at[i]); puts(""); } //寻找最大 int findmax(){ int maxid=1,maxn=at[1]; for(int i=1;i<=n;i++) if(maxn<at[i]){ maxid=i; maxn=at[i]; } return maxid; } void run(){ int ch; int id; do{ menu(); cin>>ch; switch(ch){ case 1: id=findmax(); printf("最大值为:%d 及其左指针:%d,右指针:%d\n",at[id],id<<1,id<<1|1); break; case 2: printf("高度为%d\n",h(n));break; case 3: printf("宽度为%d\n",b(n));break; case 4: SW();break; case 5: output();break; } }while(ch); } int main(){ printf("输入节点个数:"); cin>>n; printf("输入节点内容:"); for(int i=1;i<=n;i++) cin>>at[i]; run(); return 0; }
基本要求:
#include<bits/stdc++.h> using namespace std; const int N=1000; #define poly vector<int> #define pb push_back struct parent{ int pa; string dat; }p[N]; int vis[N]; int deg[N];//度数 poly g[N]; int root;//根节点 int n;//结点总数+1; void add(int u,int v){g[u].pb(v);deg[v]++;} //层次遍历 void bfs(int root){ memset(vis,0,sizeof(vis)); queue<int> q; q.push(root); while(!q.empty()){ int x=q.front();q.pop(); vis[x]=1; cout<<p[x].dat<<" "; for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(!vis[y]){ vis[y]=1; q.push(y); } } } puts(""); } //双亲表示法 void outputPa(){ printf("数组下标 data parent\n"); for(int i=0;i<=n;i++) cout<<i<<" "<<p[i].dat<<" "<<p[i].pa<<endl; } //孩子表示法 void ouputson(){ printf("孩子表示法:\n"); for(int x=0;x<=n;x++){ cout<<p[x].dat<<": "; for(int i=0;i<g[x].size();i++) printf("%d ",g[x][i]); puts(""); } } //输出度数 void outputDeg(){ for(int i=0;i<=n;i++) cout<<p[i].dat<<"的度数为:"<<deg[i]<<endl; } //先序 void Firorder(int x){ vis[x]=1; cout<<p[x].dat<<" "; for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(!vis[y]){ Firorder(y); } } } //后序 void Lasorder(int x){ vis[x]=1; for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(!vis[y]){ Lasorder(y); } } cout<<p[x].dat<<" "; } void menu(){ printf("\n1.双亲表示法\n"); printf("2.孩子兄弟表示法\n"); printf("3.树的先序遍历\n"); printf("4.树的后序遍历\n"); printf("5.树的层次遍历\n"); printf("6.节点度数统计\n"); printf("输入你的选择:"); } void run(){ int ch; do{ menu(); cin>>ch; switch(ch){ case 1: outputPa();break; case 2: ouputson();break; case 3: memset(vis,0,sizeof(vis)); Firorder(root); puts(" "); break; case 4: memset(vis,0,sizeof(vis)); Lasorder(root); break; case 5:bfs(root);break; case 6:outputDeg();break; } }while(ch); } int main(){ int u,v; string val; while(1){ printf("输入结点编号,结点数据,父亲结点编号(当输入-999中断):"); cin>>v; if(v==-999) break; cin>>val;cin>>u; p[v]={u,val}; n=max(n,max(u,v));//记录最大结点编号 if(u==-1){ root=v; continue; } add(u,v); add(v,u); } run(); } //测试数据 /* 0 R -1 1 A 0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 -999 */
问题描述:
利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道 (即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。
基本要求:
一个完整的系统应具有以下功能:
实现提示
根据题目要求把程序划成5个模块,设计成菜单方式,每次执行一个模块后返回菜单。
除了初始化(I)过程外,在每次执行时都经过一次读取磁盘文件数据。这是为了如果在程序执行后一直没有进行初始化(I)过程,为了能使后面的操作顺利进行,可以通过读取旧的数据来进行工作。比如:如果程序的工作需要的字符集和权值数据是固定的,只要在安装程序时进行一次初始(I)化操作就可以了。再在次运行程序时,不管进行哪项操作都可以把需要的数据读入到内存。
测试数据
根据实验要求,在tobetrans.dat中输入"THIS PROGRAM IS MY FAVORITE",字符集和其频度如下:(”一”表示空格 )
#include<bits/stdc++.h> using namespace std; #define pic pair<int,char> const int N=1000; pic p[N]; #define lc T[p].l #define rc T[p].r struct Huffman{ int l,r;//左右孩子 int dat;//频数 char c;//字符 string id;//每个字符的编码id }T[N]; int root; map<pic,int> ID; int tot=0; //分配下标 int getid(pic a){ if(ID.find(a)!=ID.end()) return ID[a]; ID.insert({a,++tot}); return ID[a]; } map<char,string> mp; //建立huffman树 void build(int n){ priority_queue<pic> q; int ans=0; for(int i=1;i<=n;i++) q.push({-p[i].first,p[i].second}); while(q.size()>1){ pic a=q.top();q.pop(); pic b=q.top();q.pop(); ans=-a.first-b.first; if(a.first<b.first) swap(a,b); q.push({-ans,'#'}); int pid=getid({-ans,'#'}); int aid=getid(a); int bid=getid(b); T[pid].dat=ans;T[pid].c='#';T[pid].l=aid;T[pid].r=bid; T[aid].dat=-a.first;T[aid].c=a.second; T[bid].dat=-b.first;T[bid].c=b.second; } root=getid(q.top()); } //形成每个字符编码 void dfs(int p){ if(lc) { T[lc].id=T[p].id+'0'; dfs(lc); } else{ mp.insert({T[p].c,T[p].id}); } if(rc){ T[rc].id=T[p].id+'1'; dfs(rc); } else{ mp.insert({T[p].c,T[p].id}); } } //如果想知道具体的哪个字符编码可以用这个输出 void output(int n){ for(int i=1;i<=n;i++) cout<<T[i].dat<<" "<<T[i].c<<" "<<T[i].id<<endl; } //给字符串编码 string coding(string str){ int len=str.length(); string ans=""; for(int i=0;i<len;i++) ans=ans+mp[str[i]]; return ans; } //解码 //其实就是按照01码左右递归huffman树 void Decode(int p,string s,int i,int len){ if(i==len) return; if(!lc&&!rc) printf("%c",T[p].c); if(s[i+1]=='0'){ if(lc) Decode(lc,s,i+1,len); else Decode(root,s,i+1,len); } if(s[i+1]=='1'){ if(rc) Decode(rc,s,i+1,len); else Decode(root,s,i+1,len); } } #undef lc #undef rc void menu(){ printf("1.编码\n"); printf("2.打印编码\n"); printf("0.退出\n"); printf("输入选择:"); } void run(){ int ch; string code; char str[1000]; do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入你要编码的内容:"); getchar(); gets(str); code=str; cout<<"编码后:"<<coding(code)<<endl; break; case 2: printf("输入你要解码的内容:"); cin>>code; printf("解码后:"); Decode(root,code,0,code.length()); puts(""); break; } }while(ch); } int main(){ int n; printf("请输入要读入的字符数:"); cin>>n; printf("输入字符,以及频数\n"); for(int i=1;i<=n;i++){ char ch; int a; cin>>ch>>a; if(ch=='-'){ p[i]={a,' '}; } else p[i]={a,ch}; } build(n); T[root].id='0'; dfs(root); //output(tot); run(); return 0; } //测试数据: /* 27 - 186 A 64 B 23 C 22 D 32 E 103 F 21 G 15 H 47 I 57 J 1 K 5 L 32 M 20 N 20 O 56 P 19 Q 2 R 50 S 51 T 55 U 30 V 10 W 11 X 2 Y 21 Z 2 */ //编码内容 /* THIS PROGRAM IS MY FAVORITE */ //对应的解码内容 /* 0011101111001001001100000110100011111010000101001011111010110110110000010010011000001101100110111000011100001011011100100100001111101001001110010 */
问题描述:
给出n个学生的m门课程的成绩表,每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计分析,并打印统计表。
基本要求:
#include<bits/stdc++.h> using namespace std; const int N=1000; int stunum=0; struct Student{ string id; string s; int sc[4]; int sum; double avg; }p[N]; bool cmp_avg(Student A,Student B){ return A.avg>B.avg||(A.avg>B.avg&&A.id<B.id); } bool cmp_ma(Student A,Student B){ return A.sc[1]>B.sc[1]||( A.sc[1]==B.sc[1]&&A.id<B.id); } bool cmp_en(Student A,Student B){ return A.sc[2]>B.sc[2]||( A.sc[2]==B.sc[2]&&A.id<B.id); } bool cmp_co(Student A,Student B){ return A.sc[3]>B.sc[3]||( A.sc[3]==B.sc[3]&&A.id<B.id); } void cal_course(int x){//x表示那个学科 int cnt[5];//不及格,60~69,70~79,80~89,90以上 memset(cnt,0,sizeof(cnt)); int max_sc=p[1].sc[x],min_sc=p[1].sc[x]; double avg_sc=0; for(int i=1;i<=stunum;i++){ max_sc=max(max_sc,p[i].sc[x]); min_sc=min(min_sc,p[i].sc[x]); avg_sc+=p[i].sc[x]; if(p[i].sc[x]<60) cnt[0]++; else if(p[i].sc[x]<70) cnt[1]++; else if(p[i].sc[x]<80) cnt[2]++; else if(p[i].sc[x]<90) cnt[3]++; else if(p[i].sc[x]<=100) cnt[4]++; } printf("%s成绩分布如下:\n",x==1?"数学":x==2?"英语":"计算机"); printf("最高分:%d\n",max_sc); printf("最低分:%d\n",min_sc); printf("平均分:%.2lf\n",1ll*avg_sc/stunum); printf("不及格人数:%d\n",cnt[0]); printf("60~69分人数:%d\n",cnt[1]); printf("70~79分人数:%d\n",cnt[2]); printf("80~89分人数:%d\n",cnt[3]); printf("90以上人数:%d\n",cnt[4]); } void input(){ //当输入#结束 string id; char s[30]; int sc[4]; printf("%5s %4s %4s %4s %4s %15s","学号","姓名","数学","英语","计算机","(当输入#结束)\n"); while(1){ cin>>id; if(id[0]=='#') break; cin>>s>>sc[1]>>sc[2]>>sc[3]; p[++stunum].id=id; p[stunum].s=s; p[stunum].sc[1]=sc[1]; p[stunum].sc[2]=sc[2]; p[stunum].sc[3]=sc[3]; p[stunum].sum=sc[1]+sc[2]+sc[3]; p[stunum].avg=1ll*p[stunum].sum/3; } printf("%5s %4s %4s %4s %4s","学号","姓名","数学","英语","计算机\n"); } void output(){ printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n"); for(int i=1;i<=stunum;i++){ cout<<p[i].id<<" "<<p[i].s<<" "; printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg); } puts(""); } void search_name(char *name){ bool find=0; for(int i=1;i<=stunum;i++){ if(name==p[i].s){ find=1; printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n"); cout<<p[i].id<<" "<<p[i].s<<" "; printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg); } } if(!find) printf("不存在!\n"); puts(""); } void search_id(char *str){ bool find=0; for(int i=1;i<=stunum;i++){ if(str==p[i].id){ find=1; printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n"); cout<<p[i].id<<" "<<p[i].s<<" "; printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg); } } if(!find) printf("不存在!\n"); puts(""); } void menu(){ printf("1.通过键盘输入各学生的多门课程的成绩\n"); printf("2.按各门课程成绩排序\n"); printf("3.计算每人的平均成绩,按平均成绩排序\n"); printf("4.求出各门课的成绩情况\n"); printf("5.根据姓名或者成绩查询某人的成绩\n"); printf("0.退出\n"); printf("输入选择:"); } void run(){ int ch; do{ menu(); cin>>ch; switch(ch){ case 1:input();break; case 2:printf("1.数学,2.英语,3.计算机\n"); int x;cin>>x; if(x==1) {sort(p+1,p+1+stunum,cmp_ma);output();} else if(x==2) {sort(p+1,p+1+stunum,cmp_en);output();} else if(x==3) {sort(p+1,p+1+stunum,cmp_co);output();} break; case 3: sort(p+1,p+1+stunum,cmp_avg);output();break; case 4:printf("1.数学,2.英语,3.计算机\n"); cin>>x;cal_course(x);break; case 5 :printf("1.学号,2.姓名\n"); cin>>x; if(x==1){ char s[30]; printf("输入学号:"); scanf("%s",s); search_id(s); } else if(x==2){ char s[30]; printf("输入名字:"); scanf("%s",s); search_name(s); } break; } }while(ch); } int main(){ run(); return 0; } /* 001 王放 78 70 90 002 张强 89 67 88 003 李浩 56 67 78 004 黄鹂兵 89 86 85 005 李浩 67 88 76 006 陈利风 45 54 67 007 尚晓 78 76 70 */
问题描述:
在数据处理中经常需要对大量数据进行汇总,将相同关键字记录的某些数据项的值叠加起来,生成一个分类汇总表。
假设某超级市场销售有m种商品,商品的基本信息保存在一个顺序表中,每件商品的基本信息包括:商品编号(为随机生成的[1000,9999]之间的4位数字字符)、商品名称(不超过12位的字符串)、单价。
该超级市场有n台前台收款机(假设收款机的编号为1,2,3,┅┅,n)进行收款,以记录的形式提供给计算机,每个记录表示某台收款机的一种商品一次交易的数量和销售额。收款记录由5个数据项组成:收款机编号、商品编号(输入并且必须在商品信息表中存在)、销售数量(输入)、单价、销售金额。构造一个结构体类型,每次销售数据以一个结构体变量保存在一个数据文件中。
实现要求:
#include<bits/stdc++.h> using namespace std; const int N=10000; //随机数 int random(){ return ((long long)rand()*rand()+1000)%10000; } int n; //商品信息 struct Product{ int id; string name; int price; }pdat[N]; map<string,int> pro;//商品映射商品编号 //商品是否存在 int is_exist(string a){ return pro.find(a)==pro.end()?0:1; } //分配商品编号 int getid(string a){ if(pro.find(a)!=pro.end()) return pro[a]; pro.insert({a,random()}); return pro[a]; } //添加商品 void addpro(int id,string na,int price){ pdat[id].id=id;pdat[id].name=na; pdat[id].price=price; } //输出商品信息 void output(int id){ cout<<"商品编号:"<<id<<" 商品名称:"<<pdat[id].name<<" 单价:"<<pdat[id].price<<endl; } //交易单信息 struct Pay{ int id,pid;//收款机id,商品id int price,times,cost; }py[N]; int head[N],nex[N],tot=0;//链表 int gain[N];//收款机总额 int procost[N];//商品总额 int Head[N],Nex[N];//链表 //新增交易单 void add(int id,int pid,int times){ nex[++tot]=head[id]; py[tot].id=id; py[tot].times=times,py[tot].pid=pid; py[tot].price=pdat[pid].price; py[tot].cost=times*pdat[pid].price; head[id]=tot; procost[pid]+=py[tot].cost; Nex[tot]=Head[pid]; Head[pid]=tot; gain[id]+=py[tot].cost; /***/ } //输出具体单信息 void outputPy(int i){ int x=py[i].pid; cout<<"收款机编号:"<<py[i].id<<"商品编号:"<<x<<" 商品名称:"<<pdat[x].name<<" 单价:"<<pdat[x].price<<" 总价:"<<py[i].cost<<endl; } //以收款机输出交易记录 void DisByMac(int x){ printf("交易记录:\n"); for(int i=head[x];i;i=nex[i]){ outputPy(i); } } //以商品输出交易记录 void DisByPro(int x){ printf("交易记录:\n"); for(int i=Head[x];i;i=Nex[i]){ outputPy(i); } } void menu(){ printf("\n\n1.新增商品基本信息生成和输入\n"); printf("2.交易一次\n"); printf("3.统计收款机的销售总额\n"); printf("4.以商品为单位,统计每种商品的销售总额。\n"); printf("5.商品销售记录\n"); printf("6.收款机交易记录\n"); printf("0.退出\n"); printf("输入你的选择:"); } void run(){ int ch; int m,price,times; string na; memset(head,0,sizeof(head)); memset(Head,0,sizeof(Head)); memset(gain,0,sizeof(gain)); memset(procost,0,sizeof(procost)); do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入你要添加的商品的个数:"); cin>>m; printf("输入商品名字,单价\n"); for(int i=1;i<=m;i++){ cin>>na>>price; addpro(getid(na),na,price); output(getid(na)); } break; case 2: printf("在那台机器交易(1~%d):",n); cin>>m; if(1<=m&&m<=n){ printf("购买商品名字,数量:"); cin>>na>>times; if(is_exist(na)){ add(m,getid(na),times); } else{ printf("不存在该商品!\n"); } } else{ printf("不存在该机器!\n"); } break; case 3: printf("输入收款机编号:"); cin>>m; if(1<=m&&m<=n){ printf("%d号收款机交易额:%d\n",m,gain[m]); } else{ printf("不存在该机器!\n"); } break; case 4: printf("购买商品名字"); cin>>na; if(is_exist(na)){ cout<<"商品"<<na<<"交易额:"<<procost[getid(na)]<<endl; } else{ printf("不存在该商品!\n"); } break; case 5: printf("购买商品名字"); cin>>na; if(is_exist(na)){ DisByPro(getid(na)); } else{ printf("不存在该商品!\n"); } break; case 6: printf("输入收款机编号:"); cin>>m; if(1<=m&&m<=n){ DisByMac(m); } else{ printf("不存在该机器!\n"); } break; } }while(ch); } int main(){ printf("请输入收款机数量:"); cin>>n; run(); return 0; }
问题描述: 设计散列表实现电话号码查找系统。
基本要求:
测试数据:
取班级较熟悉的30个同学记录。
{选作内容}
#include<bits/stdc++.h> using namespace std; const int N=1000; const int mod=99; int head[N],nex[N]; int tot; string Name[N]; string Phone[N]; int h(string na){ int len=na.length(); int ans=1; for(int i=0;i<len;i++) ans=(ans*131+na[i]-'a')%mod; return ans; } int H(string ph){ int len=ph.length(); int ans=0; for(int i=0;i<len;i++) ans=(ans*10+ph[i]-'0')%mod; return ans; } bool insertByna(string na,string ph){//以名字作为地址插入 int val=h(na); for(int i=head[val];i;i=nex[i]){ if(Name[i]==na) return 1; } ++tot; Name[tot]=na; Phone[tot]=ph; nex[tot]=head[val]; head[val]=tot; return 0; } bool insertByph(string na,string ph){//以名字作为地址插入 int val=H(ph); for(int i=head[val];i;i=nex[i]){ if(Phone[i]==ph) return 1; } ++tot; Name[tot]=na; Phone[tot]=ph; nex[tot]=head[val]; head[val]=tot; return 0; } int FindPh(string na){//查找电话 int val=h(na); for(int i=head[val];i;i=nex[i]){ if(Name[i]==na) return i; } return 0; } int FindNa(string ph){//查找名字 int val=H(ph); for(int i=head[val];i;i=nex[i]){ if(Phone[i]==ph) return i; } return 0; } void output(int x){ cout<<"名字:"<<Name[x]<<" 电话:"<<Phone[x]<<endl; } void menu(){ printf("1.输入记录\n"); printf("2.根据姓名查询\n"); printf("3.根据电话查询\n"); printf("0.退出\n"); printf("输入你的选择:"); } void run(){ int ch; string name,phone; int x; do{ menu(); cin>>ch; switch(ch){ case 1: int n; printf("需要插入记录的数:");cin>>n; printf("输入姓名和电话:"); for(int i=1;i<=n;i++){ cin>>name>>phone; insertByna(name,phone); insertByph(name,phone); } break; case 2: printf("输入姓名:"); cin>>name; if((x=FindPh(name))){ output(x); } else{ printf("不存在!\n"); } break; case 3: printf("输入姓名:"); cin>>phone; if((x=FindNa(phone))){ output(x); } else{ printf("不存在!\n"); } break; } }while(ch); } int main(){ run(); return 0; }
问题描述:
设某个旅游区共有n个旅游景点(n≥10),每个旅游景点都和相邻的m个旅游景点(m≥2,m<n)有直接的道路(有对应的距离)相通,请设计一个简易的旅游区导游系统。
以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图,其中:Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离;该旅游景点图采用邻接矩阵存储结构。
基本要求:
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define piii pair<pii,int> const int N=1000; int head[N],nex[N],to[N],edge[N],tot; int pa[N]; int n,m; int vis[N]; int dist[N]; void add(int u,int v,int w){//邻接链表 to[++tot]=v,nex[tot]=head[u],edge[tot]=w; head[u]=tot; } void menu(){ printf("1.旅游景点图的输出\n"); printf("2.相邻景点查询\n"); printf("3.景点路线查询\n"); printf("4.景点路线综合查询\n"); printf("5.最佳旅游路线确定\n"); printf("0.退出\n"); printf("请输入你的选择:"); } void dijkstra(int st,int flag){//dijkstra算法 priority_queue<pii> q; q.push({0,st}); memset(dist,0x3f3f3f3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[st]=0; while(!q.empty()) { pii pt=q.top();q.pop(); int u=pt.second; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=nex[i]){ int v=to[i]; if(dist[v]>=dist[u]+edge[i]){ dist[v]=dist[u]+edge[i]; pa[v]=u; q.push({-dist[v],v}); if(flag){ printf("%d->%d",st,v); printf("路径:\n"); for(int j=v;j;j=pa[j]){ printf("%d%s",j,j==st?" ":"<-"); } printf(" 长度:%d\n",dist[v]); } } } } } int ans=100000000; int endp; int dir[N]; int a[N]; //开辟路径 int len; //因为空间有限,开不了多维数组,采用二进制表示状态 //s是状态 第几位为1表示去过了,为0没去过 void dfs(int s,int u,int dist,int q){ if((s==(1<<n)-1)){ if(ans>dist){ //比当前短,保存下来 ans=dist; //保存路径长度 memcpy(dir,a,sizeof(dir)); //保存路径 endp=u; //保存最后到的点 len=q; //保存路径上的点个数 } return; } for(int i=head[u];i;i=nex[i]){ int v=to[i]; a[q]=v; if(vis[v]==2) continue;//只能去两次 vis[v]++; //把s右v-1位跟1与,如第v-1位为1则ture,否则false if(s>>(v-1)&1) dfs(s,v,dist+edge[i],q+1);//去过了v点,不用改变状态 else dfs(s^(1<<(v-1)),v,dist+edge[i],q+1);//把s的第v-1为变为1 vis[v]--; } } int Edge[N][N] ; void to_EDGE(){ memset(Edge,-1,sizeof(Edge)); for(int i=1;i<=n;i++) for(int j=head[i];j;j=nex[j]){ Edge[i][to[j]]=edge[j]; } } void run(){ int ch; do{ menu(); cin>>ch; switch(ch){ int st,en; case 1: to_EDGE(); printf("邻接矩阵:\n"); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%3d%c",Edge[i][j],j==n?'\n':' '); puts(""); printf("邻接表:\n"); for(int i=1;i<=n;i++){ printf("%d:",i); for(int j=head[i];j;j=nex[j]){ printf("%3d ",to[j]); } puts(" "); } break; case 2: printf("输入起点:"); cin>>st; for(int i=head[st];i;i=nex[i]) printf("%d -> %d : %d\n",st,to[i],edge[i]); break; case 3: printf("输入起点:"); cin>>st; dijkstra(st,1); break; case 4: printf("输入起点,终点:"); cin>>st>>en; memset(pa,0,sizeof(pa)); dijkstra(st,0); printf("路径:\n"); for(int i=en;i;i=pa[i]){ printf("%d ",i); } puts(""); break; case 5: printf("输入起点:"); cin>>st; memset(pa,0,sizeof(pa)); dijkstra(st,0); memset(vis,0,sizeof(vis)); dfs((1<<(st-1)),st,0,1); dir[0]=st; printf("路径:\n"); for(int i=0;i<len;i++) printf("%d ",dir[i]); for(int i=endp;i;i=pa[i]){ if(i==endp) continue; printf("%d ",i); } printf("\n长度:%d\n",ans+dist[endp]); break; } }while(ch); } int main(){ printf("输入点数,边数:"); cin>>n>>m; printf("输入起点 终点 路径长度:\n"); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } run(); return 0; } //测试数据 /* 4 4 1 4 1 1 2 4 2 4 5 2 3 3 */
问题描述
用无向网表示东莞理工学院的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
基本要求
选作内容
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define piii pair<pii,int> const int N=1000; int head[N],nex[N],to[N],edge[N],tot; int pa[N]; int n,m; int vis[N]; int dist[N]; void add(int u,int v,int w){//邻接链表 to[++tot]=v,nex[tot]=head[u],edge[tot]=w; head[u]=tot; } int ans=100000000; int endp; int dir[N]; int a[N]; //开辟路径 int len; int sta=0; void dijkstra(int st){//dijkstra算法 priority_queue<pii> q; q.push({0,st}); memset(dist,0x3f3f3f3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[st]=0; while(!q.empty()) { pii pt=q.top();q.pop(); int u=pt.second; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=nex[i]){ int v=to[i]; if(dist[v]>=dist[u]+edge[i]){ dist[v]=dist[u]+edge[i]; pa[v]=u; q.push({-dist[v],v}); } } } } //因为空间有限,开不了多维数组,采用二进制表示状态 //s是状态 第几位为1表示去过了,为0没去过 void dfs(int s,int u,int dist,int q){ if((s|sta)==s){ if(ans>dist){ //比当前短,保存下来 ans=dist; //保存路径长度 memcpy(dir,a,sizeof(dir)); //保存路径 endp=u; //保存最后到的点 len=q; //保存路径上的点个数 } return; } for(int i=head[u];i;i=nex[i]){ int v=to[i]; a[q]=v; if(vis[v]==2) continue;//只能去两次 vis[v]++; //把s右v-1位跟1与,如第v-1位为1则ture,否则false if(s>>(v-1)&1) dfs(s,v,dist+edge[i],q+1);//去过了v点,不用改变状态 else dfs(s^(1<<(v-1)),v,dist+edge[i],q+1);//把s的第v-1为变为1 vis[v]--; } } void DFS(int u,int ed,int dist,string path){ if(u==ed) { cout<<path<<" 长度为"<<dist<<endl; return; } for(int i=head[u];i;i=nex[i]){ int v=to[i]; if(!vis[v]){ vis[v]=1; DFS(v,ed,dist+edge[i],path+"->"+to_string(v)); vis[v]=0; } } } void search(int x){ printf("%d景点附近景点:\n",x); for(int i=head[x];i;i=nex[i]){ printf("---%d景点距离为%d\n",to[i],edge[i]); } } void menu(){ printf("\n1.查询景点信息\n"); printf("2.查询两点之间最短路径\n"); printf("3.查询途中两个景点所有路径\n"); printf("4.增加道路\n"); printf("5.删除道路\n"); printf("6.更新道路信息\n"); printf("7.求多个景点的最佳(最短)游览路径\n"); printf("输入选择:"); } void update(int u,int v,int w){ for(int i=head[u];i;i=nex[i]){ if(to[i]==v){ edge[i]=w;break; } } for(int i=head[v];i;i=nex[i]){ if(to[i]==u){ edge[i]=w;break; } } } void del(int u,int v){ int q=head[u]; if(to[q]==v){ head[u]=nex[q]; } for(int i=head[u];i;i=nex[i]){ if(to[i]==v){ nex[q]=nex[i]; break; } q=i; } q=head[v]; if(to[q]==u){ head[v]=nex[q]; } for(int i=head[v];i;i=nex[i]){ if(to[i]==u){ nex[q]=nex[i]; break; } q=i; } } void run(){ int ch,st,en,x; int u,v,w; do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入你要查询的景点:"); int x;cin>>x; search(x); break; case 2: printf("输入起点,终点:"); cin>>st>>en; memset(pa,0,sizeof(pa)); dijkstra(st); printf("路径:\n"); for(int i=en;i;i=pa[i]){ printf("%d ",i); } puts(""); break; case 3: printf("输入起点,终点:"); memset(vis,0,sizeof(vis)); cin>>st>>en; vis[st]=1; DFS(st,en,0,to_string(st)); break; case 4: printf("输入起点,终点,长度"); cin>>u>>v>>w; add(u,v,w); add(v,u,w); break; case 5: printf("输入起点,终点"); cin>>u>>v; del(u,v); break; case 6: printf("输入起点,终点,长度\n"); cin>>u>>v>>w; update(u,v,w); break; case 7: printf("请输入经过的点的个数:"); int sn;cin>>sn; printf("请输入经过的点:"); for(int i=1;i<=sn;i++){ int a; cin>>a; sta|=1<<(a-1); } memset(vis,0,sizeof(vis)); for(int st=1;st<=n;st++){ a[0]=st; dfs((1<<(st-1)),st,0,1); } cout<<ans<<endl; printf("路径:\n"); for(int i=0;i<len;i++) printf("%d ",dir[i]); break; } }while(ch); } int main(){ printf("输入点数,边数:"); cin>>n>>m; printf("输入起点,终点,长度\n"); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } run(); } //测试数据 /* 4 4 1 4 1 1 2 4 2 4 5 2 3 3 */
问题描述: 设计一个系统,实现地图的管理和最短路径查询
基本要求:
数据结构:
设计合适的数据结构组织数据,设计算法实现需求
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define piii pair<pii,int> const int N=1000; int head[N],nex[N],to[N],edge[N],tot; int pa[N]; int n,m; int vis[N]; int dist[N]; map<string,int> city; map<int,string> ct; int ccnt; int get(string c){ if(city.find(c)!=city.end()) return city[c]; city[c]=++ccnt; ct[ccnt]=c; return city[c]; } void add(int u,int v,int w){//邻接链表 to[++tot]=v,nex[tot]=head[u],edge[tot]=w; head[u]=tot; } void dijkstra(int st){//dijkstra算法 priority_queue<pii> q; q.push({0,st}); memset(dist,0x3f3f3f3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[st]=0; while(!q.empty()) { pii pt=q.top();q.pop(); int u=pt.second; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=nex[i]){ int v=to[i]; if(dist[v]>=dist[u]+edge[i]){ dist[v]=dist[u]+edge[i]; pa[v]=u; q.push({-dist[v],v}); } } } } void menu(){ printf("1.查询两点之间最短路径\n"); printf("2.添加路径\n"); printf("3.删除路径\n"); printf("4.更新路径\n"); printf("0.退出"); printf("输入你的选择:"); } void update(int u,int v,int w){ for(int i=head[u];i;i=nex[i]){ if(to[i]==v){ edge[i]=w;break; } } for(int i=head[v];i;i=nex[i]){ if(to[i]==u){ edge[i]=w;break; } } } void del(int u,int v){ int q=head[u]; if(to[q]==v){ head[u]=nex[q]; } for(int i=head[u];i;i=nex[i]){ if(to[i]==v){ nex[q]=nex[i]; break; } q=i; } q=head[v]; if(to[q]==u){ head[v]=nex[q]; } for(int i=head[v];i;i=nex[i]){ if(to[i]==u){ nex[q]=nex[i]; break; } q=i; } } void run(){ int ch; string st,en; int w; do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入起点,终点:"); cin>>st>>en; memset(pa,0,sizeof(pa)); dijkstra(get(st)); printf("路径:\n"); for(int i=get(en);i;i=pa[i]){ cout<<ct[i]<<" "; } printf("长度:%d\n",dist[get(en)]); puts(""); break; case 2: printf("输入起点,终点,长度"); cin>>st>>en>>w; add(get(st),get(en),w); add(get(en),get(st),w); break; case 3: printf("输入起点,终点"); cin>>st>>en; del(get(st),get(en)); break; case 4: printf("输入起点,终点,长度\n"); cin>>st>>en>>w; update(get(st),get(en),w); break; } }while(ch); } int main(){ printf("输入点数,边数:"); cin>>n>>m; string a,b; printf("输入起点,终点,长度\n"); for(int i=1;i<=m;i++){ int w; cin>>a>>b>>w; add(get(a),get(b),w); add(get(b),get(a),w); } run(); } //测试数据 /* 25 28 广州 深圳 140 广州 株洲 675 株洲 柳州 672 株洲 武汉 509 株洲 南昌 367 株洲 贵阳 902 柳州 南宁 255 柳州 贵阳 607 贵阳 昆明 639 贵阳 成都 1100 武汉 郑州 534 南昌 福州 622 南昌 上海 825 上海 徐州 651 郑州 徐州 349 郑州 西安 511 郑州 北京 695 徐州 田径 674 西安 兰州 676 兰州 西宁 216 兰州 乌鲁木齐 1892 兰州 呼和浩特 1145 呼和浩特 北京 668 天津 北京 137 天津 沈阳 704 沈阳 长春 305 沈阳 大连 397 长春 哈尔滨 242 */
问题描述
若要在下图中的13个城市之间建设通信网络,只需要敷设12条线路即可,边上的数字为两个城市之间建设线路的花费,单位:拾万元。如何以最低的经济代价建设这个通信网,是一个网的最小生成树的问题。
基本要求
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> const int N=1000; int head[N],to[N],nex[N],tot=0; int G[100][100];//邻接矩阵 int n,m; int vis[N]; int d[N]; void add(int a,int b){ to[++tot]=b,nex[tot]=head[a];head[a]=tot; } struct rec{int x,y,z;}Edge[N]; bool cmp(rec a,rec b){return a.z<b.z;} int fa[N],ans; int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}//并查集 void output(){ for(int x=1;x<=n;x++){ printf("%3d:",x); for(int i=head[x];i;i=nex[i]) printf("%3d ",to[i]); puts(""); } } void kruskal(){ memset(head,0,sizeof(head)); tot=0; sort(Edge+1,Edge+1+m,cmp); for(int i=1;i<=n;i++) fa[i]=i; ans=0; for(int i=1;i<=m;i++){ int x=get(Edge[i].x); int y=get(Edge[i].y); if(x==y) continue; fa[x]=y; add(Edge[i].x,Edge[i].y); add(Edge[i].y,Edge[i].x); ans+=Edge[i].z; } cout<<" 最小生成树如下:"<<endl;output(); cout<<" 总的造价:"<<ans<<endl; } void prime(){ memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); pii ed[N];//存最小生成树的边 tot=0; d[1]=0; for(int i=1;i<n;i++){ int x=0; for(int j=1;j<=n;j++) if(!vis[j]&&(x==0||(d[j]<d[x]))) x=j; vis[x]=1; int idx; for(int y=1;y<=n;y++) if(!vis[y]){ if(d[y]>G[x][y]){ d[y]=G[x][y]; ed[y]={x,y}; } } } ans=0; for(int i=2;i<=n;i++){ ans+=d[i]; add(ed[i].first,ed[i].second); add(ed[i].second,ed[i].first); } cout<<" 最小生成树如下:"<<endl;output(); cout<<" 总的造价:"<<ans<<endl; } void MatoEdge(){ memset(head,0,sizeof(head)); tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(G[i][j]!=0&&G[i][j]!=0x3f3f3f3f) add(i,j); } void menu(){ printf("1.以邻接链表输出图的数据\n"); printf("2.邻接矩阵方式输出图的数据\n"); printf("3.Prim求最小生成树\n"); printf("4.Kruskal算法求最小生成树\n"); printf("0.退出\n"); printf("输入你的选择:"); } void run(){ int ch; do{ menu(); cin>>ch; switch(ch){ case 1:MatoEdge();output();break; case 2: for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(G[i][j]!=0x3f3f3f3f)printf("%3d ",G[i][j]); else printf(" * "); puts(""); } break; case 3: prime();break; case 4: kruskal();break; } }while(ch); } int main(){ printf("输入点数,边数:"); cin>>n>>m; printf("输入起点,终点,长度\n"); memset(G,0x3f,sizeof(G)); for(int i=1;i<=n;i++) G[i][i]=0; int x,y,z; for(int i=1;i<=m;i++){ cin>>x>>y>>z; Edge[i].x=x,Edge[i].y=y,Edge[i].z=z; G[x][y]=z,G[y][x]=z; } run();return 0; } //测试数据 /* 13 25 1 2 17 1 5 32 2 3 24 2 4 22 2 7 36 5 6 12 2 12 98 3 9 78 3 7 28 4 7 19 6 7 35 6 8 54 6 12 68 7 9 46 7 8 22 8 9 23 8 10 31 8 11 24 8 12 42 9 13 54 9 10 21 10 13 14 11 13 42 11 12 12 12 13 55 */
问题描述
人们在日常生活中经常需要查找某个人或某个单位的电话号码,本实验将实现一个简单的个人电话号码查询系统,根据用户输入的信息(例如姓名等)进行快速查询。
基本要求
在外存上,用文件保存电话号码信息;
在内存中,设计数据结构存储电话号码信息;
提供查询功能:根据姓名实现快速查询;
提供其他维护功能:例如插入、删除、修改等;
按电话号码进行排序。
设计思想
由于需要管理的电话号码信息较多,而且要在程序运行结束后仍然保存电话号码信息,所以电话号码信息采用文件的形式存放到外存中。在系统运行时,需要将电话号码信息从文件调入内存来进行查找等操作,为了接收文件中的内容,要有一个数据结构与之对应,可以设计如下结构类型的数组来接收数据:
const int max=10; struct TeleNumber { string name; //姓名 string phoneNumber; //固定电话号码 string mobileNumber; //移动电话号码 string email; //电子邮箱 } Tele[max];
为了实现对电话号码的快速查询,可以将上述结构数组排序,以便应用折半查找,但是,在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作,可以考虑采用二叉排序树组织电话号码信息,则查找和维护都能获得较高的时间性能。更复杂地,需要考虑该二叉排序树是否平衡,如何使之达到平衡。
#include<bits/stdc++.h> using namespace std; const int N=10000; #define lc a[p].l #define rc a[p].r struct BST{ int l,r; int dat; string name; string phone; }a[N]; int tot,root,n; int New(string val,string na){ a[++tot].phone=val; a[tot].name=na; a[tot].dat=rand();//随机数据为了使二叉树尽量平衡 return tot; } //初始化 void build(){ New(" "," ");New("99999999999"," "); root=1,a[1].r=2; } //查找 int Get(int p,string val){ if(p==0) return 0;//检索失败 if(val==a[p].phone) return p;//检索成功 return val<a[p].phone?Get(lc,val):Get(rc,val); } //左旋 void zig(int &p){ int q=a[p].l; a[p].l=a[q].r;a[q].r=p; p=q; } //右旋 void zag(int &p){ int q=a[p].r; a[p].r=a[q].l,a[q].l=p; p=q; } //插入 void Insert(int & p,string val,string na){ if(p==0) { p=New(val,na);return;} if(val==a[p].phone) return; if(val<a[p].phone){ Insert(lc,val,na); if(a[p].dat<a[lc].dat) zig(p); } else{ Insert(rc,val,na); if(a[p].dat<a[rc].dat) zag(p); } } //删除 void Remove(int &p,string val){ if(p==0) return; if(val==a[p].phone){ if(lc||rc){ if(rc==0||a[lc].dat>a[rc].dat) zig(p),Remove(rc,val); else zag(p),Remove(lc,val); } else p=0; return; } val<a[p].phone?Remove(lc,val):Remove(rc,val); } //暴力查找名字 int GetByName(string na){ for(int i=1;i<=tot;i++){ if(na==a[i].name) { return i; } } return 0; } void menu(){ printf("1.插入电话信息与姓名\n"); printf("2.根据姓名查询\n"); printf("3.删除电话信息\n"); printf("4.修改电话信息\n"); printf("5.打印所有信息(按照电话排序)\n"); printf("0.退出\n"); printf("输入选择:"); } void output(int p){ cout<<"姓名: "<<a[p].name<<" 联系电话: "<<a[p].phone<<endl; } //先序遍历 void display(int p){ if(lc) display(lc); output(p); if(rc) display(rc); } #undef lc #undef rc void run(){ int ch; do{ string na,phone,newphone; menu(); cin>>ch; switch(ch){ case 1: printf("输入姓名 电话:"); cin>>na>>phone; Insert(root,phone,na); break; case 2: printf("输入要查询姓名:"); cin>>na; int x; if((x=GetByName(na))==0) { printf("不存在!\n"); } else{ output(x); } break; case 3: printf("输入删除的电话:"); cin>>phone; Remove(root,phone); break; case 4: printf("输入你要修改的手机号:"); cin>>phone; printf("输入你要新的手机号:"); cin>>newphone; if(Get(root,phone)==0){ printf("不存在!\n"); } else{ Insert(root,newphone,a[Get(root,phone)].name); Remove(root,phone); } break; case 5:display(root); break; } }while(ch); } int main(){ run(); return 0; }
问题描述:
设计一个系统,对图书信息进行管理,信息描述:有关该系统基本信息的描述,如:图书名称、图书编号、单价、作者、存在状态、借书人姓名、性别、学号等。
基本要求:
基本功能:
#include<bits/stdc++.h> using namespace std; const int N=1000; int tot=0;//馆藏 int lencnt=0;//借出书 //图书信息 struct Book{ string bookname; string bookid; int price; bool exist; string autor; string broswer; string sex; string stuid; }; struct Person{ string name; string sex; string stuid; }; map<string,Person> persondat;//个人数据库 map<string,Book> bookdat;//图书数据库 //该书是否在馆 bool isbook(string bookid){ return bookdat.find(bookid)==bookdat.end()?0:1; } //撤销书籍 void del(string bookid){ if(!isbook(bookid)){ printf("图书馆没有此书!\n"); return; } auto p=bookdat.find(bookid); bookdat.erase(p); tot--; } //添加书籍 void add(string bookname,string bookid,int price,string autor){ bookdat.insert({bookid,{bookname,bookid,price,1,autor,"","",""}}); tot++; } //还书 void reback(string bookid){ if(!isbook(bookid)){ printf("图书馆没有此书!\n"); return; } bookdat[bookid].exist=true; lencnt--; } //借书 void lentbook(string bookid){ if(!isbook(bookid)){ printf("图书馆没有此书!\n"); return; } if(bookdat[bookid].exist){ bookdat[bookid].exist=false; lencnt++; } else{ printf("该书已经被人借出!\n"); } } //注册 void Register(string name,string id,string sex){ persondat.insert({id,{name,sex,id}}); } //用户是否存在 bool is_exist(string stuid){ return persondat.find(stuid)==persondat.end()?0:1; } //输出图书信息 void output(string p){ cout<<"书名:"<<bookdat[p].bookname<<" 编号:"<<bookdat[p].bookid<<" 作者:"<<bookdat[p].autor<<" 价格:"<<bookdat[p].price; printf(" 在馆状态:%s\n",bookdat[p].exist==1?"在":"不在"); } void menu(){ printf("1.新进图书\n"); printf("2.图书基本信息的查询\n"); printf("3.撤销图书信息\n"); printf("4.为借书人办理注册\n"); printf("5.办理借书手续\n"); printf("6.办理还书手续\n"); printf("7.统计图书库存、已借出图书数量。\n"); printf("0.退出\n"); printf("输入你的选择:"); } void run(){ int ch; string bookname,bookid,autor; string name,sex,stuid; int price; do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入书名,编号,价格,作者:"); cin>>bookname>>bookid>>price>>autor; add(bookname,bookid,price,autor); break; case 2: printf("输入要查询的书的编号:"); cin>>bookid; if(!isbook(bookid)){ printf("图书馆没有此书!"); } else{ output(bookid); } break; case 3: printf("输入要撤销的书的编号:"); cin>>bookid; del(bookid); break; case 4: printf("输入注册人的姓名,性别,学号\n"); cin>>name>>sex>>stuid; Register(name,stuid,sex); break; case 5: printf("输入你的学号:"); cin>>stuid; if(is_exist(stuid)){ cout<<" 你好,"<<persondat[stuid].name; printf("%s",persondat[stuid].sex=="男"?"男士":persondat[stuid].sex=="女"?"女士":"同学"); printf("输入要查询的书的编号:"); cin>>bookid; lentbook(bookid); } else{ printf("不存在该会员,请办理会员!\n"); } break; case 6: printf("输入你的学号:"); cin>>stuid; if(is_exist(stuid)){ cout<<" 你好,"<<persondat[stuid].name; printf("%s",persondat[stuid].sex=="男"?"男士":persondat[stuid].sex=="女"?"女士":"同学"); printf("输入要还的书的编号:"); cin>>bookid; reback(bookid); } else{ printf("不存在该会员,请办理会员!\n"); } break; case 7: printf("图书库存:%d 已借出图书数量:%d\n",tot,lencnt); } }while(ch); } int main(){ run(); return 0; }
简单商品销售管理系统: 设计一个系统,对某个商店的商品销售进行管理.
需求描述:
#include<bits/stdc++.h> using namespace std; //商品信息 struct Product{ string id; string name; int num; int price; }; //会员信息 struct Person{ string pid; string name; string phone; string addres; int tot; }; map<string,Product>Pro; map<string,Person>Per; map<string,string> A;//商品到标号 map<string,string>B;//人名到编号 map<string,vector<string>> repro;//从会员记录买单 map<string,vector<string>> reper;//从商品记录买单 void add(string id,string na,int num,int pr){ Pro.insert({id,{id,na,num,pr}}); A.insert({na,id}); } //商品是否存在 bool isproduct(string id){ return Pro.find(id)==Pro.end()?0:1; } //会员是否存在 bool isperson(string pid){ return Per.find(pid)==Per.end()?0:1; } //删除商品 void delproduct(string id){ if(isproduct(id)){ Pro.erase(Pro.find(id)); } else{ printf("该商品不存在!\n"); } } //显示商品 void output(string id){ cout<<"商品名称:"<<Pro[id].name<<" 商品编号:"<<Pro[id].id<< " 商品库存:"<<Pro[id].num<<" 商品价格:"<<Pro[id].price<<endl; } //新增会员 void addperson(string na,string pid,string ph,string addres){ Per.insert({pid,{pid,na,ph,addres}}); } //删除会员 void delperson(string pid){ if(isperson(pid)){ Per.erase(Per.find(pid)); } else{ printf("该会员不存在!\n"); } } //购买商品 void BuyPro(string id,string pid){ if(isproduct(id)){ if(Pro[id].num){ Pro[id].num--; repro[id].push_back(Per[pid].name);//商品记录 reper[pid].push_back(Pro[id].name);//会员记录 } else{ printf("购买失败,该商品不没库存了!\n"); } } else{ printf("该商品不存在!\n"); } } //显示会员名称 void display(string id){ cout<<" 会员名字:"<<Per[id].name<<" 会员编号:"<<Per[id].pid<<" 会员地址:"<<Per[id].addres<<" 会员手机:"<<Per[id].phone<<endl; } //修改商品信息 void changpro(string id){ if(isproduct(id)){ output(id); string na; int price,cnt; printf("输入要修改后的名称,库存,单价:"); cin>>na>>cnt>>price; A.erase(A.find(Pro[id].name)); Pro[id].name=na;Pro[id].price=price;Pro[id].num=cnt; A.insert({na,id}); } else{ printf("该商品不存在!\n"); string na,ph,addres; printf("输入要修改后的会员名称,手机号,地址:"); cin>>na>>ph>>addres; Per[id].name=na;Per[id].phone=ph;Per[id].addres=addres; } } //修改会员信息 void changper(string id){ if(isperson(id)){ display(id); } else{ printf("该用户不存在!\n"); } } //显示会员购买了啥 void DisplayByPer(string id){ if(isperson(id)){ for(int i=0;i<reper[id].size();i++) cout<<"购买了"<<reper[id][i]<<endl; } else{ printf("该会员不存在!\n"); } } //显示哪个会员购买了该商品 void DisplayByPro(string id){ if(isproduct(id)){ for(int i=0;i<repro[id].size();i++) cout<<repro[id][i]<<"买单了。。。"<<endl; } else{ printf("该商品不存在!\n"); } } void menu(){ printf("1.新商品信息\n"); printf("2.根据商品编号查询\n"); printf("3。根据商品名称查询\n"); printf("4.删除商品信息\n"); printf("5.修改商品信息\n"); printf("6.注册会员\n"); printf("7.删除会员\n"); printf("8.修改会员信息\n"); printf("9.购买商品\n"); printf("10.更具会员查看销售记录\n"); printf("11.商品查询销售记录\n"); printf("输入你的选择:"); } void run(){ int ch; string id,pid,name,ph,addres; int num,price; do{ menu(); cin>>ch; switch(ch){ case 1: printf("输入新增的产品的名字,编号,数量,单价:"); cin>>name>>id>>num>>price; add(id,name,num,price); break; case 2: printf("输入商品编号:"); cin>>id; if(isproduct(id)){ output(id); } else{ printf("该商品不存在!\n"); } break; case 3: printf("输入商品名称:"); cin>>name; if(A.find(name)==A.end()){ printf("该商品不存在!\n"); } else{ output(A[name]); } break; case 4: printf("输入你要删除的商品编号:"); cin>>id; delproduct(id); break; case 5: printf("输入你修改的商品编号:"); cin>>id; changpro(id); break; case 6: printf("输入注册的名字,编号,电话,地址:"); cin>>name>>id>>ph>>addres; addperson(name,id,ph,addres); break; case 7: printf("输入你要删除的会员编号:"); cin>>id; delperson(id); break; case 8: printf("输入你修改的会员编号:"); cin>>id; changper(id); break; case 9: printf("输入你的会员编号:"); cin>>pid; if(isperson(pid)){ printf("输入要购买的商品编号:"); cin>>id; BuyPro(id,pid); } else{ printf("该用户不存在!"); } break; case 10: printf("输入会员编号:"); cin>>pid; DisplayByPer(pid); break; case 11: printf("输入商品编号:"); cin>>id; DisplayByPro(id); break; } }while(ch); } int main(){ run(); return 0; }
最后还是希望这篇文章能够帮助到大家吧!欢迎提问!