数据结构与算法实验题答案.docx
- 文档编号:4658481
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:26
- 大小:18.80KB
数据结构与算法实验题答案.docx
《数据结构与算法实验题答案.docx》由会员分享,可在线阅读,更多相关《数据结构与算法实验题答案.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构与算法实验题答案
A装箱问题模拟(20)
源码:
#include
#include
usingnamespacestd;
charbox[1010];
intmain()
{
memset(box,100,sizeof(box));
intN;
intt;
intnum=0;
cin>>N;
inttemp=N;
while(temp--)
{
cin>>t;
for(inti=0;i { inta=box[i]; if(a>=t) { if(a==100) num++; box[i]-=t; cout< break; } } } cout< //system("pause"); return0; } B表达式转换(25) 源码: #include #include #include usingnamespacestd; stack intmain() { strings; stringanwser; cin>>s; inti; boolnumber=false; boolfirstFlag=true; stringsnum=""; for(i=0;i { if(s[i]>='0'&&s[i]<='9'||s[i]=='.') { number=true; snum+=s[i]; } elseif(number==true) { number=false; if(firstFlag) firstFlag=false; else anwser+=""; if(snum[0]=='+') snum.erase(snum.begin()); anwser+=snum; snum=""; } if(s[i]=='+'||s[i]=='-') { if(i==0|| s[i-1]=='+'||s[i-1]=='-'|| s[i-1]=='*'||s[i-1]=='/'|| s[i-1]=='(') snum+=s[i]; else { while(sta.size()&&sta.top()! ='(') { intt=sta.top(); if(firstFlag) firstFlag=false; else anwser+=""; anwser+=t; sta.pop(); } sta.push(s[i]); } } elseif(s[i]=='*'||s[i]=='/') { while(sta.size()&&sta.top()! ='(') { intt=sta.top(); if(t=='-'||t=='+') break; if(firstFlag) firstFlag=false; else anwser+=""; anwser+=sta.top(); sta.pop(); } sta.push(s[i]); } elseif(s[i]==')') { while(sta.size()&&sta.top()! ='(') { if(firstFlag) firstFlag=false; else anwser+=""; anwser+=sta.top(); sta.pop(); } if(sta.size()) sta.pop(); } elseif(s[i]=='(') sta.push(s[i]); } if(snum! ="") { if(firstFlag) firstFlag=false; else anwser+=""; anwser+=snum; } while(sta.size()) { if(firstFlag) firstFlag=false; else anwser+=""; anwser+=sta.top(); sta.pop(); } cout< return0; } C家谱处理(30) 源码: #include #include #include usingnamespacestd; structPerson { stringname; intlevel; }; intmain() { //freopen("C: \\Users\\FrankWang\\Desktop\\in.txt","r",stdin); ios_base: : sync_with_stdio(0); //cin.tie(0); vector intn,m; cin>>n>>m; while(n--) { if(cin.get()! ='\n')cin.unget(); ints_cnt=0; while(cin.get()=='')++s_cnt; cin.unget(); Personpe_tmp; pe_tmp.level=s_cnt; cin>>pe_tmp.name; family_tree.push_back(pe_tmp); } //for(vector : iteratorit=family_tree.begin();it! =family_tree.end();++it) //{ //cout< //} stringname_a,name_b,relation; while(m--) { cin>>name_a; intcount=6; while(count--)cin.get(); charch; cin.get(ch); if(ch=='c'||ch=='e') { relation="child"; } elseif(ch=='s')relation="sibling"; else { relation="ancestor"; } cin.ignore(256,'f'); cin>>name_b; if(ch=='e'||ch=='d') { name_a.swap(name_b);//orswap(name_a,name_b)in } //cout< if(relation=="child") { vector : iteratorit=family_tree.begin(); for(;it! =family_tree.end();++it) { if(it->name==name_b)break; } intlevel_tmp=it->level; if(it! =family_tree.end())++it; boolflag=1; while(it! =family_tree.end()&&it->level>level_tmp) { if(it->name==name_a&&it->level==level_tmp+2) { cout<<"True\n"; flag=0; break; } ++it; } if(flag)cout<<"False\n"; } elseif(relation=="ancestor") { vector : iteratorit=family_tree.begin(); for(;it! =family_tree.end();++it) { if(it->name==name_a)break; } intlevel_tmp=it->level; if(it! =family_tree.end())++it; boolflag=1; while(it! =family_tree.end()&&it->level>level_tmp) { if(it->name==name_b) { cout<<"True\n"; flag=0; break; } ++it; } if(flag)cout<<"False\n"; } else { vector : iteratorit=family_tree.begin(); for(;it! =family_tree.end();++it) { if(it->name==name_a)break; } intlevel_tmp=it->level; vector : iteratorit_tmp=it; if(it! =family_tree.end())++it; boolflag=1; while(it! =family_tree.end()&&it->level>=level_tmp) { if(it->name==name_b&&it->level==level_tmp) { cout<<"True\n"; flag=0; break; } ++it; } if(flag) { if(it_tmp! =family_tree.begin())--it_tmp; while(it_tmp! =family_tree.begin()&&it_tmp->level>=level_tmp) { if(it_tmp->name==name_b&&it_tmp->level==level_tmp) { cout<<"True\n"; flag=0; break; } --it_tmp; } } if(flag)cout<<"False\n"; } } } D航空公司VIP客户查询(25) 源码: #include #include #include #include #include #include #include #include usingnamespacestd; typedeflongintlld;//longint #definerot(v)(((v)>>3)|(((v)&7)<<9)) constintMAX=110000; constintMOD=100003; constintINF=1000000000; structNode { inta,b; charx; intmile,next; }node[MAX]; inthead[MOD],E; charbuf[22]; intchg(charx) { if(x=='x')return10; returnx-'0'; } intfun(chars[],int&a,int&b,char&x) { intret=0,i; inttmp; a=b=0; for(i=0;i<9;i++) { tmp=s[i]-'0'; a=a*10+tmp;//记录没取余数的数值 ret=ret*10+tmp; } ret%=MOD; for(;i<17;i++) { tmp=s[i]-'0'; b=b*10+tmp;//记录后面没取余数的数值 ret=(ret*10+tmp)%MOD; } x=s[i];//记录最后一位 return(ret*100+chg(s[i]))%MOD;//返回取余数的数值 } voidins(chars[],intmile) { inta,b; charx; inth=fun(s,a,b,x); inti; //发生冲突时的处理 for(i=head[h];i! =-1;i=node[i].next)//head全局变量 { if(node[i].x==x&&node[i].a==a&&node[i].b==b) { node[i].mile+=mile; return; } } node[E].a=a; node[E].b=b; node[E].x=x; node[E].mile=mile; node[E].next=head[h]; head[h]=E++; } intquery(chars[]) { inta,b; charx; inth=fun(s,a,b,x); inti; for(i=head[h];i! =-1;i=node[i].next) { if(node[i].x==x&&node[i].a==a&&node[i].b==b)returnnode[i].mile; } return-1; } voidout(intn) { if(n) { out(n/10); putchar('0'+n%10); } } intmain() { intn,m; intk,i; while(scanf("%d%d",&n,&k)! =EOF) { memset(head,-1,sizeof(head)); E=0; intmile=0; while(n--) { scanf("%s%d",buf,&mile); if(mile ins(buf,mile); } scanf("%d",&m); getchar(); while(m--) { //scanf("%s",buf); gets(buf); mile=query(buf); if(mile==-1)puts("NoInfo"); else { out(mile); //cout< //printf("%d",mile); putchar('\n'); } } } return0; } E社交网络图中结点的“重要性”计算(30) #include #include #include #include usingnamespacestd; constintN=10005; intn,m,dis[N]; boolused[N]; deque voidthink(intsrc) { fill(used,used+N,false); fill(dis,dis+N,0); queue Q.push(src); used[src]=true; dis[src]=0; while(! Q.empty()) { intk=Q.front(); Q.pop(); for(inti=0,_i=ed[k].size();i<_i;++i) { inttmp=ed[k][i]; if(! used[tmp]) { dis[tmp]=dis[k]+1; used[tmp]=true; Q.push(tmp); } } } printf("Cc(%d)=",src); intsum=0,flag=1; for(inti=1;i<=n;++i) { if(! dis[i]&&i! =src) {flag=0;break;} sum+=dis[i]; } printf("%.2f\n",(flag? (double(n-1)/sum): 0)); } intmain() { scanf("%d%d",&n,&m); while(m--) { inta,b; scanf("%d%d",&a,&b); ed[a].push_back(b); ed[b].push_back(a); } scanf("%d",&m); while(m--) { intk; scanf("%d",&k); think(k); } return0; } F奥运排行榜(25) 源码: #include intgold[225],medal[225],population[225]; intlist[10]; intfir=0;//用来判断是否是第一个元素用的 voidprintresult(intcheck_number,intn); intmain() { intn,m; scanf("%d%d",&n,&m); for(inti=0;i scanf("%d%d%d",&gold[i],&medal[i],&population[i]); for(inti=0;i { intcheck_number; scanf("%d",&check_number); printresult(check_number,n); } printf("\n"); return0; } voidprintresult(intcheck_number,intn) { for(inti=0;i { if(gold[i]>gold[check_number]) list[1]++; } intresult=++list[1];//这里还要多加一个1,因为数组原来是0 intnum=1; for(inti=0;i { if(medal[i]>medal[check_number]) list[2]++; } list[2]++; doublegold_per=gold[check_number]*1.0/population[check_number]; for(inti=0;i { if((gold[i]*1.0/population[i])>gold_per) list[3]++; } list[3]++; doublemedal_per=medal[check_number]*1.0/population[check_number]; for(inti=0;i { if(medal[i]*1.0/population[i]>medal_per) list[4]++; } list[4]++; for(inti=1;i<5;i++) { if(list[i] { result=list[i]; num=i; } } for(inti=1;i<5;i++) list[i]=0;//对排名数组清零,因为之后要多次调用 if(! fir) { printf("%d: %d",result,num);//首个输入前面不用空格 fir=1; } else printf("%d: %d",result,num); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 实验 答案