数据结构与算法实验题答案

A 装箱问题模拟（20）

源码：

#include #include using namespace std;

char box[1010];

int main() {

memset(box,100,sizeof(box)); int N; int t;

int num=0; cin>>N;

int temp = N; while(temp--) {

cin>>t;

for (int i=0;i

int a = box[i]; if (a>=t) {

if (a==100) num++;

box[i] -=t;

cout<

cout<

//system(\ return 0; }

B 表达式转换（25）

源码：

#include #include #include using namespace std;

stack sta;

int main() {

string s;

string anwser; cin>>s;

int i;

bool number = false; bool firstFlag = true; string snum = \

for(i = 0; i < s.length(); ++i) {

if(s[i] >= '0' && s[i] <= '9' || s[i] == '.') {

number = true; snum += s[i]; }

else if(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() != '(') {

int t = sta.top(); if(firstFlag)

firstFlag = false; else

anwser += \ anwser += t; sta.pop(); }

sta.push(s[i]); } }

else if(s[i] == '*' || s[i] == '/') {

while(sta.size() && sta.top() != '(') {

int t = sta.top();

if(t == '-' || t == '+') break; if(firstFlag)

firstFlag = false; else

anwser += \ anwser += sta.top(); sta.pop(); }

sta.push(s[i]); }

else if(s[i] == ')') {

while(sta.size() && sta.top() != '(') {

if(firstFlag)

firstFlag = false; else

anwser += \ anwser += sta.top(); sta.pop();

}

if(sta.size()) sta.pop(); }

else if(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<

C 家谱处理（30）

源码：

#include #include #include using namespace std;

struct Person {

string name; int level; };

int main() {

// freopen(\ ios_base::sync_with_stdio(0); // cin.tie(0);

vector family_tree; int n,m; cin>>n>>m; while(n--) {

if(cin.get()!='\\n') cin.unget(); int s_cnt=0;

while(cin.get()==' ') ++s_cnt; cin.unget(); Person pe_tmp;

pe_tmp.level=s_cnt; cin>>pe_tmp.name;

family_tree.push_back(pe_tmp); }

// for(vector::iterator

it=family_tree.begin();it!=family_tree.end();++it) // {

// cout<name<<' '<level<

string name_a,name_b,relation; while(m--) {

cin>>name_a; int count=6;

while(count--) cin.get(); char ch; cin.get(ch);

if(ch=='c'||ch=='e') {

relation=\ }

else if(ch=='s') relation=\ else {

relation=\ }

cin.ignore(256,'f');

cin>>name_b;

if(ch=='e'||ch=='d') {

name_a.swap(name_b);//or swap(name_a,name_b) in ,but former is better. }

// cout<

if(relation==\ {

vector::iterator it=family_tree.begin(); for(;it!=family_tree.end();++it) {

if(it->name==name_b) break; }

int level_tmp=it->level;

if(it!=family_tree.end()) ++it; bool flag=1;

while(it!=family_tree.end()&&it->level>level_tmp) {

if(it->name==name_a&&it->level==level_tmp+2) {

cout<<\ flag=0; break; } ++it; }

if(flag) cout<<\ }

else if(relation==\ {

vector::iterator it=family_tree.begin(); for(;it!=family_tree.end();++it) {

if(it->name==name_a) break; }

int level_tmp=it->level;

if(it!=family_tree.end()) ++it; bool flag=1;

while(it!=family_tree.end()&&it->level>level_tmp) {

if(it->name==name_b) {

cout<<\ flag=0; break; } ++it; }

if(flag) cout<<\ } else {

vector::iterator it=family_tree.begin(); for(;it!=family_tree.end();++it) {

if(it->name==name_a) break; }

int level_tmp=it->level;

vector::iterator it_tmp=it; if(it!=family_tree.end()) ++it; bool flag=1;

while(it!=family_tree.end()&&it->level>=level_tmp) {

if(it->name==name_b&&it->level==level_tmp) {

cout<<\ 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<<\ flag=0; break; }

--it_tmp; }

}

if(flag) cout<<\ } } }

D 航空公司VIP客户查询（25）

源码：

#include #include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long int lld;//long int

#define rot(v) (((v)>>3)|(((v)&7)<<9))

const int MAX=110000;

const int MOD=100003;

const int INF=1000000000;

struct Node {

int a,b;

char x;

int mile,next;

}node[MAX];

int head[MOD],E;

char buf[22];

int chg(char x) {

if(x=='x')return 10;

return x-'0'; }

int fun(char s[],int &a,int &b,char &x) {

int ret=0,i;

int tmp;

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;//返回取余数的数值 }

void ins(char s[],int mile) {

int a,b;

char x;

int h=fun(s,a,b,x);

int i;

//发生冲突时的处理

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++; }

int query(char s[]) {

int a,b;

char x;

int h=fun(s,a,b,x);

int i;

for(i=head[h];i!=-1;i=node[i].next)

{

if(node[i].x==x&&node[i].a==a&&node[i].b==b)return node[i].mile;

}

return -1; }

void out(int n) {

if(n)

{

out(n/10);

putchar('0'+n);

} }

int main() {

int n,m;

int k,i;

while(scanf(\

{

memset(head,-1,sizeof(head));

E=0;

int mile=0;

while(n--)

{

scanf(\

if(mile

ins(buf,mile);

}

scanf(\

getchar();

while(m--)

{

//scanf(\

gets(buf);

mile=query(buf);

if(mile==-1)puts(\

else

{

out(mile); // cout<

// printf(\

putchar('\\n');

}

}

}

return 0; }

E 社交网络图中结点的“重要性”计算（30） #include #include #include #include

using namespace std; const int N=10005; int n,m,dis[N]; bool used[N]; dequeed[N];

void think(int src) {

fill(used,used+N,false); fill(dis,dis+N,0); queueQ; Q.push(src); used[src]=true; dis[src]=0;

while(!Q.empty()) {

int k=Q.front(); Q.pop();

for(int i=0,_i=ed[k].size();i<_i;++i) {

int tmp=ed[k][i]; if(!used[tmp]) {

dis[tmp]=dis[k]+1; used[tmp]=true; Q.push(tmp); } } }

printf(\ int sum=0,flag=1; for(int i=1;i<=n;++i) {

if(!dis[i]&&i!=src) {flag=0;break;} sum+=dis[i]; }

printf(\}

int main()

{

scanf(\ while(m--) {

int a,b;

scanf(\ ed[a].push_back(b); ed[b].push_back(a); }

scanf(\ while(m--) {

int k;

scanf(\ think(k); }

return 0; }

F 奥运排行榜（25）

源码：

#include

int gold[225],medal[225],population[225]; int list[10];

int fir = 0;//用来判断是否是第一个元素用的 void printresult(int check_number,int n); int main() {

int n,m;

scanf(\for(int i = 0;i < n;i++)

scanf(\for(int i = 0;i < m;i++) {

int check_number;

scanf(\printresult(check_number,n); }

printf(\return 0;

}

void printresult(int check_number,int n) {

for(int i = 0;i < n;i++) {

if(gold[i]>gold[check_number]) list[1]++; }

int result = ++list[1];//这里还要多加一个1，因为数组原来是0 int num = 1;

for(int i = 0;i < n;i++) {

if(medal[i]>medal[check_number]) list[2]++; }

list[2]++;

double gold_per = gold[check_number]*1.0/population[check_number]; for(int i = 0;i < n;i++) {

if((gold[i]*1.0/population[i])>gold_per) list[3]++; }

list[3]++;

double medal_per = medal[check_number]*1.0/population[check_number]; for(int i = 0;i < n;i++) {

if(medal[i]*1.0/population[i]>medal_per) list[4]++; }

list[4]++;

for(int i = 1;i < 5;i++) {

if(list[i]

result = list[i]; num = i; } }

for(int i = 1;i < 5;i++)

list[i] = 0;//对排名数组清零，因为之后要多次调用 if(!fir) {

printf(\首个输入前面不用空格 fir = 1;

} else

printf(\}

本文来源：https://www.bwwdw.com/article/e763.html