注册 登录
编程论坛 → C++教室

会C++/VC的来,求调试指正

longyushen 发布于 2012-01-01 18:09， 526 次点击
只有本站会员才能查看附件，请 登录
【问题描述】
天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
【基本要求】
(1) 建立模型，设计数据结构；
(2) 设计算法完成放大器的放置；
(3) 分析算法的时间复杂度。
【设计思想】
为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。
****************************
************详情请看附件********************
程序代码：
#include <iostream>
using namespace std;
struct node                 //定义树的元素
{
    struct node *lchild;
    struct node *rchild;
    char data ;
    int weight;
    int D;                //当前衰减量最大值
};
typedef struct node * BTREE ;
typedef enum{L, R} tagtype;
typedef struct
{
    BTREE ptr;
    tagtype tag;
}stacknode;
typedef struct
{
    stacknode Elem[100];
    int top;
} Stack;
stacknode Pop( Stack &S )
{
    stacknode c;
    c=S.Elem[ S.top ];
    S.top = S.top - 1 ;
    return c;
}
void Push ( stacknode x, Stack &S )
{
    S.top = S.top + 1 ;
    S.Elem[ S.top ] = x ;
}
typedef struct
{
    char data, parent, tag ;
    int weight;
} Bnode;
typedef struct           //队列
{
    BTREE ele[100];
    int front,rear;
}Squeue;
void Makenull ( Squeue &Q)
{
    Q.front = 0;
    Q.rear =99;
}
BTREE CreatBT( )                   //按逻辑结构建立二叉树，依次输入结点、父结点、标号、权值
{
    cout<<"请按逻辑结构输入二叉树"<<endl;
    Bnode p;
    Squeue q;
    BTREE root, s;
    root=new node;
    root=NULL;
    Makenull(q);
    cin>>p.data>>p.parent>>p.tag>>p.weight;
    while (p.data!='0')
    {
        s=new node;
        s->data=p.data;
        s->weight=p.weight;
        s->lchild=s->rchild=NULL;
        q.rear=(q.rear+1)%100;
        q.ele[q.rear]=s;
        if (p.parent=='0')
            root=s;
        else
        {
            while (q.rear+1%100!=q.front&&q.ele[q.front]->data!=p.parent)
                q.front=(q.front+1)%100;
            if (q.ele [q.front]->data==p.parent)
            {
                if (p.tag=='L')
                    q.ele[q.front]->lchild=s;
                else
                    q.ele[q.front]->rchild=s;
            }
        }
        cin>>p.data>>p.parent>>p.tag>>p.weight;
    }
    return root;
}
void Amplifier(BTREE sb,int tol)                     //设置信号放大器函数
{
    BTREE t;
    Stack s;
    stacknode x;
    s.top=0;
    t=sb;
    do
    {
        while (t!=NULL)
        {
            x.ptr = t;
            x.tag = L;
            Push(x,s);
            t=t->lchild;
        }
        while (s.top!=0&& s.Elem[s.top].tag==R)
        {
            x = Pop(s);
            t = x.ptr;
            if (t->lchild==NULL&&t->rchild==NULL)
            {
                t->D=0;                          //初始化
            }
            else if (t->lchild==NULL&&t->rchild!=NULL)
            {
                t->D=t->rchild->D+t->rchild->weight;              //只有右子树时当前最大衰减量
                if (t->D>tol)                  //大于容忍值则设置放大器
                {
                    cout<<"应该放置放大器的结点为：";
                    cout<<t->rchild->data<<endl;
                    t->D=t->rchild->weight;
                }
            }
            else if (t->lchild!=NULL&&t->rchild==NULL)      //只有左子树时当前最大衰减量
            {
                t->D=t->lchild->D+t->lchild->weight;
                if (t->D>tol)                  //大于容忍值则放置放大器
                {
                    cout<<"应该放置放大器的结点为：";
                    cout<<t->lchild->data<<endl;
                    t->D=t->lchild->weight;
                }
            }
            else if ((t->lchild->D+t->lchild->weight)>(t->rchild->D+t->rchild->weight))           //左子树衰减量大于右子树
            {
                t->D=t->lchild->D+t->lchild->weight;             //更新最大衰减量
                if (t->D>tol)
                {
                    cout<<"应该放置放大器的结点为：";              //放置放大器
                    cout<<t->lchild->data<<endl;
                    if ((t->rchild->D+t->rchild->weight)>(t->lchild->weight))         //进一步比较
                    {
                        t->D=t->rchild->D+t->rchild->weight;        //更新
                        if (t->D>tol)
                        {
                            cout<<"应该放置放大器的结点为：";
                            cout<<t->rchild->data<<endl;
                            if ((t->rchild->weight)>(t->lchild->weight))                //进一步比较
                                t->D=t->rchild->weight;
                            else
                                t->D=t->lchild->weight;       //更新
                        }
                    }
                    else
                        t->D=t->lchild->weight;        //更新
                }
            }
            else if ((t->rchild->D+t->rchild->weight)>=(t->lchild->D+t->lchild->weight))       //右子树衰减量大于左子树
            {
                t->D=t->rchild->D+t->rchild->weight;
                if (t->D>tol)
                {
                    cout<<"应该放置放大器的结点为：";         //大于容忍值放置放大器
                    cout<<t->rchild->data<<endl;
                    if ((t->lchild->D+t->lchild->weight)>(t->rchild->weight))         //进一步比较
                    {
                        t->D=t->lchild->D+t->lchild->weight;         //更新
                        if (t->D>tol)
                        {
                            cout<<"应该放置放大器的结点为：";
                            cout<<t->lchild->data<<endl;
                            if ((t->rchild->weight)>(t->lchild->weight))                //进一步比较
                                t->D=t->rchild->weight;
                            else
                                t->D=t->lchild->weight;
                        }
                    }
                    else
                        t->D=t->rchild->weight;
                }
            }
        }
        if (s.top!=0)
        {
            s.Elem[s.top].tag =R;
            t=s.Elem[s.top].ptr->rchild;
        }
    }
    while (s.top!=0);
}
int main()                         //主函数
{
    printf("声明：1、输入二叉树信息时请按 当前结点、该结点父结点、左右标号、与父结点权值的顺序输入，均使用大写。\n");
    printf("      2、对于根结点请输入 结点、0、0、0\n");
    printf("      3、输入结束时请输入0、0、0、0\n\n");
    BTREE bt;
    int tolerance;
    bt=CreatBT();
    cout<<"请输入容忍值："<<endl;                //设置容忍值
    cin>>tolerance;
    Amplifier(bt,tolerance);                    //设置放大器函数
    return 0;
}



[ 本帖最后由 longyushen 于 2012-1-1 18:24 编辑 ]
3 回复
#2
yb87214862012-01-01 21:15
这么高深！！！新手掠过
#3
longyushen2012-01-02 13:51
怎么没人理的？
#4
longyushen2012-01-03 13:46
程序代码：
#include <iostream>
using namespace std;
struct node                 //定义树的元素
{
    struct node *lchild;
    struct node *rchild;
    char data ;
    int weight;
    int D;                //当前衰减量最大值
};
typedef struct node * BTREE ;
typedef enum{L, R} tagtype;
typedef struct
{
    BTREE ptr;
    tagtype tag;
}stacknode;
typedef struct
{
    stacknode Elem[100];
    int top;
} Stack;
stacknode Pop( Stack &S )
{
    stacknode c;
    c=S.Elem[ S.top ];
    S.top = S.top - 1 ;
    return c;
}
void Push ( stacknode x, Stack &S )
{
    S.top = S.top + 1 ;
    S.Elem[ S.top ] = x ;
}
typedef struct
{
    char data, parent, tag ;
    int weight;
} Bnode;
typedef struct           //队列
{
    BTREE ele[100];
    int front,rear;
}Squeue;
void Makenull ( Squeue &Q)
{
    Q.front = 0;
    Q.rear =99;
}
BTREE CreatBT( )                   //按逻辑结构建立二叉树，依次输入结点、父结点、标号、权值
{
    cout<<"请按逻辑结构输入二叉树"<<endl;
    Bnode p;
    Squeue q;
    BTREE root, s;
    root=new node;
    root=NULL;
    Makenull(q);
    cin>>p.data>>p.parent>>p.tag>>p.weight;
    while (p.data!='0')
    {
        s=new node;
        s->data=p.data;
        s->weight=p.weight;
        s->lchild=s->rchild=NULL;
        q.rear=(q.rear+1)%100;
        q.ele[q.rear]=s;
        if (p.parent=='0')
            root=s;
        else
        {
            while (q.rear+1%100!=q.front&&q.ele[q.front]->data!=p.parent)
                q.front=(q.front+1)%100;
            if (q.ele [q.front]->data==p.parent)
            {
                if (p.tag=='L')
                    q.ele[q.front]->lchild=s;
                else
                    q.ele[q.front]->rchild=s;
            }
        }
        cin>>p.data>>p.parent>>p.tag>>p.weight;
    }
    return root;
}
void Amplifier(BTREE sb,int tol)                     //设置信号放大器函数
{
    BTREE t;
    Stack s;
    stacknode x;
    s.top=0;
    t=sb;
    do
    {
        while (t!=NULL)
        {
            x.ptr = t;
            x.tag = L;
            Push(x,s);
            t=t->lchild;
        }
        while (s.top!=0&& s.Elem[s.top].tag==R)
        {
            x = Pop(s);
            t = x.ptr;
            if (t->lchild==NULL&&t->rchild==NULL)
            {
                t->D=0;                          //初始化
            }
            else if (t->lchild==NULL&&t->rchild!=NULL)
            {
                t->D=t->rchild->D+t->rchild->weight;              //只有右子树时当前最大衰减量
                if (t->D>tol)                  //大于容忍值则设置放大器
                {
                    cout<<"应该放置放大器的结点为：";
                    cout<<t->rchild->data<<endl;
                    t->D=t->rchild->weight;
                }
            }
            else if (t->lchild!=NULL&&t->rchild==NULL)      //只有左子树时当前最大衰减量
            {
                t->D=t->lchild->D+t->lchild->weight;
                if (t->D>tol)                  //大于容忍值则放置放大器
                {
                    cout<<"应该放置放大器的结点为：";
                    cout<<t->lchild->data<<endl;
                    t->D=t->lchild->weight;
                }
            }
            else if ((t->lchild->D+t->lchild->weight)>(t->rchild->D+t->rchild->weight))           //左子树衰减量大于右子树
            {
                t->D=t->lchild->D+t->lchild->weight;             //更新最大衰减量
                if (t->D>tol)
                {
                    cout<<"应该放置放大器的结点为：";              //放置放大器
                    cout<<t->lchild->data<<endl;
                    if ((t->rchild->D+t->rchild->weight)>(t->lchild->weight))         //进一步比较
                    {
                        t->D=t->rchild->D+t->rchild->weight;        //更新
                        if (t->D>tol)
                        {
                            cout<<"应该放置放大器的结点为：";
                            cout<<t->rchild->data<<endl;
                            if ((t->rchild->weight)>(t->lchild->weight))                //进一步比较
                                t->D=t->rchild->weight;
                            else
                                t->D=t->lchild->weight;       //更新
                        }
                    }
                    else
                        t->D=t->lchild->weight;        //更新
                }
            }
            else if ((t->rchild->D+t->rchild->weight)>=(t->lchild->D+t->lchild->weight))       //右子树衰减量大于左子树
            {
                t->D=t->rchild->D+t->rchild->weight;
                if (t->D>tol)
                {
                    cout<<"应该放置放大器的结点为：";         //大于容忍值放置放大器
                    cout<<t->rchild->data<<endl;
                    if ((t->lchild->D+t->lchild->weight)>(t->rchild->weight))         //进一步比较
                    {
                        t->D=t->lchild->D+t->lchild->weight;         //更新
                        if (t->D>tol)
                        {
                            cout<<"应该放置放大器的结点为：";
                            cout<<t->lchild->data<<endl;
                            if ((t->rchild->weight)>(t->lchild->weight))                //进一步比较
                                t->D=t->rchild->weight;
                            else
                                t->D=t->lchild->weight;
                        }
                    }
                    else
                        t->D=t->rchild->weight;
                }
            }
        }
        if (s.top!=0)
        {
            s.Elem[s.top].tag =R;
            t=s.Elem[s.top].ptr->rchild;
        }
    }
    while (s.top!=0);
}
int main()                         //主函数
{
    printf("说明：1、输入二叉树信息时请按 当前结点、该结点父结点、左右标号、与父结点权值的顺序输入，均使用大写。\n");
    printf("      2、对于根结点请输入 结点、0、0、0\n");
    printf("      3、输入结束时请输入0、0、0、0\n\n");
    BTREE bt;
    int tolerance;
    bt=CreatBT();
    cout<<"请输入容忍值："<<endl;                //设置容忍值
    cin>>tolerance;
    Amplifier(bt,tolerance);                    //设置放大器函数
    return 0;
}
正确代码分享
1
©2025, BC-CN.NET
电脑版