数据结构与算法的实验内容

发布网友发布时间：2022-05-01 17:30

共1个回答

热心网友时间：2022-06-20 08:01

第一题用python写的，第二题用c++写的。

在http://pat.zju.e.cn测试通过

# 第一题
def main():
    text = raw_input()
    n = int(text[0:text.find(' ')])
    m = int(text[text.find(' ')+1:])

    root = build(n)
    check(root, m)

def build(n):
    raw_name = raw_input()
    name = raw_name.strip()
    root = {}
    root['name'] = name
    root['layer'] = 0
    root['child'] = {}
    root['sibling'] = {}

    pre_node = root
    for i in range(1,n):
        raw_name = raw_input()
        name = raw_name.strip()
        cur_layer = raw_name.index(name)/2
        cur_node = {}
        cur_node['name'] = name
        cur_node['layer'] = cur_layer
        cur_node['child'] = {}
        cur_node['sibling'] = {}
        if cur_layer == pre_node['layer']:
            pre_node['sibling'] = cur_node
        elif cur_layer == pre_node['layer']+1:
            pre_node['child'] = cur_node
        elif cur_layer == pre_node['layer']+1:
            print 'error!\n'
            break
        elif cur_layer < pre_node['layer']:
            path = getpath(root, pre_node['name'])
            pre_subling = {}
            for p in path:
                if p['layer'] > cur_layer:
                    break
                else:
                    pre_subling = p
            pre_subling['sibling'] = cur_node
        pre_node = cur_node

    return root

def check(root, m):
    #X is a child of Y
    #X is the parent of Y
    #X is a sibling of Y
    #X is a descendant of Y
    #X is an ancestor of Y
    for i in range(0,m):
        text = raw_input()
        X = text[0:text.find(' ')]
        Y = text[text.rfind(' ')+1:]
        if 'child' in text:
            path = getpath(root, X)
            if len(path)>=2 and path[-2]['name'] == Y:
                print True
            else:
                print False
        if 'parent' in text:
            path = getpath(root, Y)
            if len(path)>=2 and path[-2]['name'] == X:
                print True
            else:
                print False
        if 'sibling' in text:
            pathX = getpath(root, X)
            pathY = getpath(root, Y)
            if len(pathX)>=2 and len(pathY)>=2 and pathX[-2]['name'] == pathY[-2]['name']:
                print True
            else:
                print False
        if 'descendant' in text:
            path = getpath(root, X)
            for p in path:
                if p['name'] == Y:
                    break
            if p['name'] == Y:
                print True
            else:
                print False
        if 'ancestor' in text:
            path = getpath(root, Y)
            for p in path:
                if p['name'] == X:
                    break
            if p['name'] == X:
                print True
            else:
                print False

def getpath(root, node_name):
    path = [root]
    next_node = root['child']
    while True:
        while next_node != {}:
            path.append(next_node)
            if next_node['name'] == node_name:
                return path
            next_node = next_node['child']

        next_node = path.pop()
        if path == []:
            return path
        else:
            next_node = next_node['sibling']

if __name__ == "__main__":
    main()

// 第二题
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 224;
typedef struct
{
    int index;
    double no;
    int range;
}ELEM;
int cmp_des( const ELEM &a, const ELEM &b ){
    return a.no>b.no; // 降序
}
int cmp_aes( const ELEM &a, const ELEM &b ){
    return a.index<b.index; // 升序
}
int main()
{
    int n,m;
    cin>>n>>m;

    double data[5][MAX];
    int paiming[5][MAX];
    ELEM tmp[MAX];
    int country[MAX];
    int i,j;
    for (i=0;i<n;i++)
    {
        cin>>data[1][i]>>data[2][i]>>data[0][i];
        data[3][i] = data[1][i]/data[0][i];
        data[4][i] = data[2][i]/data[0][i];
    }
    for (i=0;i<m;i++)
        cin>>country[i];

    for (i=1;i<=4;i++)
    {
        for (j=0;j<n;j++)
        {
            tmp[j].index = j;
            tmp[j].no = data[i][j];
        }
        sort(tmp,tmp+n,cmp_des);
        for (j=0;j<n;j++)
        {
            if (j>0 && tmp[j].no==tmp[j-1].no)
                tmp[j].range = tmp[j-1].range;
            else
                tmp[j].range = j+1;
        }
        sort(tmp,tmp+n,cmp_aes);
        for (j=0;j<n;j++)
        {
            paiming[i][j] = tmp[j].range;
        }
    }

    int top_12,top_34,top_1234;
    for (i=0;i<m;i++)
    {
        top_12 = paiming[1][country[i]]<=paiming[2][country[i]]?1:2;
        top_34 = paiming[3][country[i]]<=paiming[4][country[i]]?3:4;
        top_1234 = paiming[top_12][country[i]]<=paiming[top_34][country[i]]?top_12:top_34;
        printf("%d:%d",(int)paiming[top_1234][country[i]],(int)top_1234);
        if (i<m-1)
            printf(" ");
    }

    return 0;
}