2021-06-16

2023-11-29 08:13:04

数据结构第七次上机实验

一、序列调度：

2021-06-16

2021-06-16

题意：借助一个有限容量的栈来实现序列A向其他等长序列变换，若能输出YES,若不能输出NO。（序列A只能从前往后调度一次）。

思路：本题为栈模拟问题，本题我用数组a储存目标序列，并采用pointer来模拟对A序的遍历，当pointer值小于当前a[i]值时，pointer入栈，直至pointer于当前的a[i]值相同 ，此时判断栈内元素是否大于容器的规定容量，是则跳出，输出“NO”反之继续模拟。然后后出栈栈顶元素，若出栈后栈顶元素小于pointer值说明压栈时压入的元素个数>1且此时所有元素均小于刚出栈的元素,按照栈先入后出的规则若此时栈顶元素不等于a[i],按照栈先入后出的规则,无法实现目标序列，跳出循环。

代码：

#include <iostream>
#include<stack>

using namespace std;


const int max0=10005;

int continer;//栈的规定容量
stack<int>D;//模拟用的栈
int a[max0];//存储目标序列
int n;//序列长度
int T;//访问组数
int pointer=0;//A序列的（形式）遍历指针
int flag=0;//标志


int main()
{
 scanf("%d%d",&T,&continer);

 for(int i=0;i<T;i++)
 {
        scanf("%d",&n);

        pointer=1;
        flag=0;
        int j=0;
    for(int j=0;j<n;j++)
     {
        scanf("%d",&a[j]);
       
     }
     
        for(int j=0;j<n;j++)//若此循环执行n次则调度完成。flag=0
         {
            if(!D.empty()&&D.top()==a[j])//当前元素成功模拟，弹出即可
            {
                D.pop();
                continue;
            }
            if(a[j]<pointer)
            /*  第一个触发点
                此时模拟弹栈，检查a[j]此时元素是否符合
                弹栈的顺序，不符合则无法调度，退出循环
            */
            {
                if(a[j]!=D.top())
                    {
                        flag=1;
                        break;
                    }
                D.pop();
            }
            while(pointer<=n)
            {
                D.push(pointer);
                if(pointer==a[j])
                {
                    pointer++;
                    break;
                }
               pointer++;
            }
            /*压栈压至栈顶元素与此时目标序列的元素相同*/
            if(D.size()>continer)
                {flag=1;break;}
                D.pop();
            /*又一个触发点，若压栈的元素个数大于容量，则跳出循环，flag=1;*/
            if(flag==1) break;
           

        }
if(!D.empty()) flag=1;
/*最后触发点，若此时栈内不为空，说明调度的序列元素个数<n  */
     if(flag==1) printf("No\n");
     else printf("Yes\n");
while(!D.empty()) D.pop();//每进行完一组后清空栈内元素

     }
 return 0;
}

 

 二、最大最小差。

2021-06-16

题意：给定一个序列，进行n-1次a*b+1变换,在所有这种操作下求最大最小值的差。

思路：开两个优先队列，分别保存该序列，一个单调递增，一个单调递减。每次从每个队列头取两个元素，进行a*b+1变换后，再重新放入队中。进行n-1次操作后，分别取队首，相减即可。

代码：

#include<bits/stdc++.h>
#include<deque>
using namespace std;

priority_queue<long long int> q1;
priority_queue<long long int ,vector<long long int>,greater<long long int>> q2;
int main()
{

    long long int n,x;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {   scanf("%lld",&x);
        q1.push(x);
        q2.push(x);
    }
    for(int i=0;i<n-1;i++)
    {
        long long int x=q1.top();
        q1.pop();
        long long int y=q1.top();
        q1.pop();
        q1.push(x*y+1);
         x=q2.top();
        q2.pop();
         y=q2.top();
         q2.pop();
        q2.push(x*y+1);

    }
    printf("%lld",q2.top()-q1.top());

        return 0;
}

三、二叉树最短路径长度

2021-06-16

2021-06-16

题意：二叉树的每个结点都赋予权值，计算从根结点到所有结点的最短路径长度.

思路：先根据先根序列和中根序列建树，后采用层次遍历，每遍历一层结点，下一层的结点权值根据上一层结点权值更新。

代码：

关键代码：

1.递归建树

void init(int sp,int ep,int so,int eo,node *&p){//建立二叉树
	if(sp>ep||so>eo) return;
	int i,j;
	for(i=sp,j=so;i<=ep;++i,++j)
		if(ord[j]==prv[sp])
			break;
	p=new node;
	p->l=p->r=NULL;//注意每一次在申请空间之后，左右子节点都要变成空节点，否则会RE
	p->val=prv[sp];
	p->cost=dialq[p->val];
	init(sp+1,i,so,j-1,p->l);//递归
	init(i+1,ep,j+1,eo,p->r);
}

2.层次遍历边遍历边更新结点的权值，并用xcost数组保存对应点的权值。

void LevelorderTraversal( BinTree BT )
{   BinTree q[20005];
    int f=0,r=0;
    BinTree p=BT;
    if(p!=NULL)
    q[r++]=p;
    else return ;
    while(f!=r)
    {   int ccost;
        p=q[f++];
//        cout<<p->cost;
       ccost=p->cost;
        if(p->l!=NULL)
         {
                q[r++]=p->l;
                 p->l->cost+=ccost;
                 dialq[p->l->val]=p->l->cost;
                 
         }
        if(p->r!=NULL)
            {   q[r++]=p->r;
                p->r->cost+=ccost;
                dialq[p->r->val]=p->r->cost;
                
            }
    }


}

3.关键代码

#include<bits/stdc++.h>
using namespace std;
struct node{//链表
	int val;
	int cost;
	node *l,*r;
};
node *root;
typedef node* BinTree;
int prv[20005],ord[20005];
int dialq[20005];
void LevelorderTraversal( BinTree BT );
void init(int sp,int ep,int so,int eo,node *&p);
int main(){
    int n=0;
    scanf("%d",&n);
//    cout<<n<<endl;
    for(int i=1;i<=n;i++)
        scanf("%d",&prv[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&ord[i]);
	for(int i=1;i<=n;i++)
    {
        scanf("%d",&dialq[i]);

    }
//    for(int i=1;i<=n;i++)
//    {
//      printf ("%d ",dialq[i]);
//
//    }

	init(1,n,1,n,root);
	 LevelorderTraversal( root );
//	 cout<<endl;
     printf("%d",dialq[1]);
	 for(int i=2;i<=n;i++)
     {
         printf(" %d",dialq[i]);
     }
	return 0;
}

void LevelorderTraversal( BinTree BT )
{   BinTree q[20005];
    int f=0,r=0;
    BinTree p=BT;
    if(p!=NULL)
    q[r++]=p;
    else return ;
    while(f!=r)
    {   int ccost;
        p=q[f++];
//        cout<<p->cost;
       ccost=p->cost;
        if(p->l!=NULL)
         {
                q[r++]=p->l;
                 p->l->cost+=ccost;
                 dialq[p->l->val]=p->l->cost;
                 
         }
        if(p->r!=NULL)
            {   q[r++]=p->r;
                p->r->cost+=ccost;
                dialq[p->r->val]=p->r->cost;
                
            }
    }


}
void init(int sp,int ep,int so,int eo,node *&p){//建立二叉树
	if(sp>ep||so>eo) return;
	int i,j;
	for(i=sp,j=so;i<=ep;++i,++j)
		if(ord[j]==prv[sp])
			break;
	p=new node;
	p->l=p->r=NULL;//注意每一次在申请空间之后，左右子节点都要变成空节点，否则会RE
	p->val=prv[sp];
	p->cost=dialq[p->val];
	init(sp+1,i,so,j-1,p->l);//递归
	init(i+1,ep,j+1,eo,p->r);
}

四、方案计数

2021-06-16

2021-06-16

思路：容易看出这是一个拓扑排序的题。关键在于求关键路径数，考试时做此题时，采用课上老师讲的思路，先把拓朴序列求出，再根据此序列求出关键活动，再由关键活动求出

关键路径（重新建图或在原图上打上标志，后用DFS深搜即可，后期尝试时会超时）。后拜读大神算法，理解了一种边拓排边求出关键路径的算法，在此奉上。前面的第一种的代码，

后期再补上。

代码：

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int max0 = 10005;
const int INF = 9999999;
int max1 = -INF;
class highacc
{
int digit;
bool f;
int n[105];
void incripanocostrse()
{
    for (int i = 1;i<=digit/2;i++)
        swap(n[i],n[digit-i+1]);
}

  public:
    highacc();
highacc operator = (const int num)
{
int tmp = num;
    int cnt = 0;
    while (tmp)
    {
        n[++cnt] = tmp%10;
        tmp /= 10;
    }
    digit =cnt;
    incripanocostrse();
    return *this;
}
highacc operator * (const int num)
{
    int tmp = num;
    highacc a;
    for (int i = 1;i<=tmp;i++)
    {
        a = a + *this;
    }
    return a;
}

friend ostream& operator <<(ostream& out,highacc &a)
{
    for (int i = 1;i<=a.digit;i++)
    {
        out<<a.n[i];
    }
    if (a.digit == 0)
        out<<"0";
    return out;
}


    friend highacc operator + (const highacc a,const highacc b);
};

highacc::highacc()
{
    for (int i = 0;i<=105;i++)
        n[i] = 0;
    digit = 0;
    f = 0;
}
/*包装高精度类，重载+，*，<<,等运算符，用于统计关键路径数*/
vector<int>a[max0];//用向量来存储邻接表
long long int  cripanocost[max0];//存储到每个关键活动的路径总权值
int tpo[max0],count0[max0];//tpo用来存储拓扑序列，count0用来存储每个点的入度
long long int  cost[max0];//count0用来存储每个点的权值
highacc node_critical_path[max0];//存储到每个关键活动的关键路径的条数。
int tp(int n);


int main()
{

    int n,m,t1,t;
    cin>>n>>m;
    for (int i = 1;i<=n;i++)
    {
        node_critical_path[i] = 0;
        count0[i] = 0;
    }

    for (int i = 1;i<=n;i++)
    {
        cin>>cost[i];
    }
    for (int i = 1;i<=m;i++)
    {
        cin>>t1>>t;
        a[t1].push_back(t);
        count0[t]++;
    }
    for (int i = 1;i<=n;i++)
    {
        if (!count0[i])
            a[0].push_back(i);
    }
    if (tp(n)==0)
    {
        cout<<"0";
        return 0;
    }

    int sinknode;
    int sinknum = 0;//存储汇点的数目
    for (int i = 1;i<=n;i++)
{
if (max1 == cripanocost[i])
        {
            sinknum++;
        }

       else if (max1<cripanocost[i])
        {
            sinknode = i;
            sinknum = 1;
            max1 = cripanocost[i];
        }

    }
    node_critical_path[sinknode] = node_critical_path[sinknode]*sinknum;
    cout<<cripanocost[sinknode]<<'\n'<<node_critical_path[sinknode];
    return 0;
}
highacc operator + (const highacc a,const highacc b)
{
    highacc c,a1,b1;
    a1 = a;b1 = b;
    int t = 0;
    int len = max(a1.digit,b1.digit);
    a1.incripanocostrse();b1.incripanocostrse();

    for (int i = 1;i<=len;i++)
    {
        c.n[i] = (a1.n[i] + b1.n[i] + t)%10;
        t = (a1.n[i] + b1.n[i] + t)/10;
    }
    c.digit = len;
    if (t)
    {
        c.digit++;
        c.n[c.digit] = t;
    }
    c.incripanocostrse();
    return c;
}
int tp(int n)//一边拓扑排序，一遍求关键路径的条数
{

    int j,sinknum = 0;
    vector<int>ss;
    for (int i = 0;i<=n;i++)
        sort(a[i].begin(),a[i].end());
    for (int i = 0;i<=n;i++)
        cripanocost[i] = 0;
    for (int i = 1;i<=n;i++)
    {
        if (!count0[i])
        {
            ss.push_back(i);
            node_critical_path[i] = 1;
            cripanocost[i] = cost[i];
        }
    }
    sort(ss.begin(),ss.end(),greater<int>());
    for (int i = 1;i<=n;i++)
    {
        if (ss.empty())
            return 0;
        j = ss.back();ss.pop_back();
        tpo[++sinknum] = j;
        for (int k = 0;k<int(a[j].size());k++)
        {
            int t = a[j][k];
            count0[t]--;
            if (count0[t] == 0)
            {
                ss.push_back(t);
            }
            if (cripanocost[t]<cripanocost[j] + cost[t])
            {
                cripanocost[t] = cripanocost[j] + cost[t];
                node_critical_path[t] = node_critical_path[j];
            }
            else if (cripanocost[t] == cripanocost[j] + cost[t])
            {
                node_critical_path[t] = node_critical_path[j] + node_critical_path[t];
            }
        }
    }
    return 1;
}

 

 

 

 

 

 

上一篇：宋浩概率论与数理统计笔记——第七章


下一篇：Leetcode 1449.数位成本和目标值的最大数字