JLU資料結構榮譽課——第六次上機實驗
7-1 高精度數加法 (100 分)
題目分析
高精度加法，逆序存，反向輸出，c++實驗做過，
代碼實作
#include<stdio.h>
#include<string.h>
char a[100000],b[102],c[1000000],sum[1000000];
void jiafa(char *a,char *b)//后面那個長一點
{
int l_a,l_b,i;
int value_a,value_b,value_sum;
int t=0;//判斷進位
l_a=strlen(a);
l_b=strlen(b);
if(l_b<l_a)
{
char m[100000];
strcpy(m,a);
strcpy(a,b);
strcpy(b,m);
}
l_a=strlen(a);
l_b=strlen(b);
for(i=0;i<l_a;i++)
{
value_a=a[i]-'0';
value_b=b[i]-'0';
value_sum=value_a+value_b+t;
if(value_sum>=10)t=1;
else t=0;
b[i]=value_sum%10+'0';
}
for(;i<l_b;i++)
{
if(t==0)break;
else
{
value_b=b[i]-'0'+1;
if(value_b>=10)t=1;
else t=0;
b[i]=value_b%10+'0';
}
}
if(t==1&&b[i]) b[i]=b[i]+1;
if(t==1&&!b[i])
{
b[i]='1';
b[i+1]=0;
}
}
int main()
{
int n;
scanf("%d",&n);
scanf("%s",a);
int la=strlen(a);
for(int i=0;i<=la-1;i++)
{
c[i]=a[la-1-i];
}
// printf("%s",c);
for(int i=0;i<n-1;i++)
{
char d[102];
scanf("%s",d);
int lb=strlen(d);
for(int j=0;j<=(lb-1)/2;j++)
{
int z;
z=d[j];
d[j]=d[lb-1-j];
d[lb-1-j]=z;
}
jiafa(d,c);
}
int l;
l=strlen(c);
for(int i=l-1;i>=0;i--)
printf("%c",c[i]);
}
7-2 二叉樹加權距離 (100 分)
題目分析
把二叉樹當作圖處理，父節點到子節點的權值為2，子節點到父節點的權值為3，
如果用dijstra會超時，換成spfa后就行了，
代碼實作如下
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int name;
int cost;
};
#define Max 100001
vector<Node> Map[Max];
int visited[Max];
int cost[Max];
int path[Max];
queue<Node> que;
int main()
{
int n,i,j,u;
cin>>n;
Node a;
for(i=1;i<=n;i++)
cost[i]=1000001;
for(i=0;i<n-1;i++)
{
int t0,t1;
cin>>t0;
cin>>t1;
a.name=t1;
a.cost=2;
Map[t0].push_back(a);
a.name=t0;
a.cost=3;
Map[t1].push_back(a);
}
int zz1,zz2;
cin>>zz1;
cin>>zz2;
cost[zz1]=0;
visited[0]=1;
a.cost=0;
a.name=zz1;
que.push(a);
while(!que.empty())
{
a=que.front();
que.pop();
visited[a.name]=0;
for(vector<Node>::iterator k = Map[a.name].begin();k!=Map[a.name].end();k++)
{
if(cost[k->name]>cost[a.name]+k->cost)
{
cost[k->name]=cost[a.name]+k->cost;
// path[k->name]=u;
if(!visited[k->name])
{
que.push(*k);
visited[k->name]=1;
}
}
}
}
printf("%d",cost[zz2]);
}
7-3 修輕軌 (100 分)
題目分析
方法一：
最小生成樹問題，這里因為生成后需要延路徑尋找路徑上的最大值，我用的prim（prim生成最小生成樹時能保留路徑），
具體代碼
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int name;
int cost;
bool operator<(const Node& a)const
{
return cost> a.cost;
}
};
priority_queue<Node> q;
#define Max 100001
vector<Node> Map[Max];
int visited[Max];
int cost[Max];
int path[Max];
queue<Node> que;
int main()
{
int m,n,i,j,u;
scanf("%d",&n);
scanf("%d",&m);
Node a;
for(i=1;i<=n;i++)
cost[i]=1000002;
for(i=0;i<m;i++)
{
int t0,t1,cost0;
scanf("%d",&t0);
scanf("%d",&t1);
scanf("%d",&cost0);
a.name=t1;
a.cost=cost0;
Map[t0].push_back(a);
a.name=t0;
Map[t1].push_back(a);
}
visited[1]=1;
cost[1]=0;
for(vector<Node>::iterator k = Map[1].begin();k!=Map[1].end();k++)
{
a.name=k->name;
a.cost=k->cost;
q.push(a);
path[a.name]=1;
cost[a.name]=a.cost;
}
for(j=1;j<n&&!q.empty();j++)
{
int l=1000001;
a=q.top();
q.pop();
while(visited[a.name]&&!q.empty())
{
a=q.top();
q.pop();
}
u=a.name;
if(u==n)break;
// printf("%d",u);
visited[u]=1;
for(vector<Node>::iterator k = Map[u].begin();k!=Map[u].end();k++)
{
int v=k->name;
if(k->cost<cost[v]&&visited[v]==0)
{
a.name=v;
a.cost=k->cost;
q.push(a);
cost[v]=k->cost;
path[v]=u;
}
}
}
int zz,Max_=0;
for(zz=n;zz!=1;zz=path[zz])
{
if(Max_<cost[zz])Max_=cost[zz];
printf("%d\n",zz);
}
printf("%d",Max_);
}
方法二：
還是使用spfa演算法，將 “松弛” 操作改變，每一個點的cost中記錄到次點這條路徑上的最大邊權，到一個新頂點后，將這個頂點的cost與max(上一個頂點的cost，兩頂點間的權值)比較，取較小者，
具體代碼實作如下
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int name;
int cost;
};
#define Max 100001
vector<Node> Map[Max];
int visited[Max];
int cost[Max];
int path[Max];
queue<Node> que;
int main()
{
int m,n,i,j,u;
scanf("%d",&n);
scanf("%d",&m);
Node a;
for(i=1;i<=n;i++)
cost[i]=1000001;
for(i=0;i<m;i++)
{
int t0,t1,cost0;
scanf("%d",&t0);
scanf("%d",&t1);
scanf("%d",&cost0);
a.name=t1;
a.cost=cost0;
Map[t0].push_back(a);
a.name=t0;
Map[t1].push_back(a);
}
cost[1]=0;
visited[1]=1;
a.cost=0;
a.name=1;
que.push(a);
while(!que.empty())
{
a=que.front();
que.pop();
visited[a.name]=0;
for(vector<Node>::iterator k = Map[a.name].begin();k!=Map[a.name].end();k++)
{
if(cost[k->name]>max(cost[a.name],k->cost))
{
cost[k->name]=max(cost[a.name],k->cost);
// path[k->name]=u;
if(!visited[k->name])
{
que.push(*k);
visited[k->name]=1;
}
}
}
}
printf("%lld",cost[n]);
}
7-4 資料結構設計I (100 分)
題目分析
因為取最大值，我想到了使用優先佇列，對于R操作，如果遍歷所有資料取反肯定是行不通的，這里使用一個標記r記錄R操作的次數，如果r為奇數，則進行I操作時取反再壓入，
這樣一來我們就需要維護兩個優先佇列，一個取最大值，一個取最小值（當r為奇數時），
但是同時也會有洗掉操作，這個怎么實作呢？我們不正真地洗掉，而是引入下標，top和rear，洗掉元素，top++，加入元素，rear++，同時在優先佇列中保存數值的同時我們保存他的下標，從優先佇列中取出一個數時，如果其下標小與top代表該數已經被洗掉，回圈彈出，直到數字合法（未被洗掉）
具體代碼實作如下
#include<bits/stdc++.h>
using namespace std;
struct Node1
{
int value;
int num;
bool operator<(const Node1& a)const
{
return value< a.value;
}
};
struct Node2
{
int value;
int num;
bool operator<(const Node2& a)const
{
return value> a.value;
}
};
priority_queue<Node1> q1;//最大值
priority_queue<Node2> q2;//最小值
int top,rear,i,j,k,r,m;
Node1 a1;
Node2 a2;
char ch;
int main()
{
scanf("%d",&m);
getchar();
for(i=0;i<m;i++)
{
scanf("%s",&ch);
if(ch=='I')
{
int t;
scanf("%d",&t);
if(r%2==1)t=-t;
a1.num=rear;
a1.value=t;
q1.push(a1);
a2.num=rear;
a2.value=t;
q2.push(a2);
rear++;
}
else if(ch=='R')
{
r++;
}
else if(ch=='D'&&top<rear)
{
top++;
}
else if(ch=='M'&&top!=rear)
{
if(r%2==0)
{
Node1 zz=q1.top();
while(zz.num<top)
{
q1.pop();
if(q1.empty())break;
zz=q1.top();
}
if(k!=0)
{
printf("\n");
}
k++;
if(!q1.empty())printf("%d",zz.value);
}
else
{
Node2 zz=q2.top();
while(zz.num<top)
{
q2.pop();
if(q2.empty())break;
zz=q2.top();
}
if(k!=0)
{
printf("\n");
}
k++;
if(!q2.empty())printf("%d",-zz.value);
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287466.html
標籤：其他