Blask
好东西快到老王碗里来
Blask

IT节程序设计竞赛网络赛(二)

2月中旬举办了场代码比赛,拉几道我会写的题目来放放(出题人老二次元了)

题目L 我的数据结构不可能这么难

题目详情:

小明同学最近学了数据结构的链表,他觉得自己无敌厉害,然后他就想加入全院最强的ACM协会。于是会长大人就给他出了一道最简单的题目,给你n(0<=n<=100000)个数据,m(0<=m<=100000)次指令,共有四种指令:

指令1为将数字y(0<=y<=1e9)插入首部;

指令2为删除位置首部数据;

指令3为将数字y插入尾部;

指令4为删除位置尾数据,

要求在限定时间内输出[l,r]区间的结果。(数据保证不会最终结果数组长度小于1)

http://image.blask.cn/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.png
  • 输入T,表示有T组数据(T<=10)。
  • 输入n,表示现有数组长度为n
  • 接下来输入n个数据ai(0<=ai<=100000)
  • 输入m,表示有m次数据插入
  • 接下来m行,每行有一种指令(1,2,3,4其中指令1和3之后还有数字y)。
  • 指令1为将数字y(0<=y<=1e9)插入首部,指令2为删除位置首部数据,指令3为将数字y插入尾部,指令4为删除位置尾数据.
  • 最后输入l r,要求答案输出[l,r]区间的数据

题目分析:

这道题就是一道普通的数据结构链表题目,相信数据结构基础好的能直接ko。

题目代码

C编写

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
typedef int ElemType;

typedef struct Node
{
    ElemType elem;
    Node *next;
}Node;

void InitList(Node **pNode)
{
    *pNode = NULL;
}

Node *CreastList(Node *pHead,int num)
{
    Node *p1;
    Node *p2;
    p1 = p2 = new Node;
    for(int i=0;i<num;i++){
        scanf("%d",&p1->elem);
        p1->next = NULL;
        if (pHead == NULL)
        {
            pHead = p1;
        }
        else
        {
            p2->next = p1;
        }
        p2 = p1;
        p1 = new Node;
    }
    return pHead;
}

void PrintList(Node *pHead,int first,int second)
{
    if(first==1){
        for(int i=0;i<second;i++){
            printf("%d ",pHead->elem);
            pHead = pHead->next;
        }
    }
    else{
        for(int j=0;j<first;j++){
            pHead = pHead->next;
        }
        for(int k=first;k<second;k++){
            printf("%d ",pHead->elem);
            pHead = pHead->next;
        }
    }
    printf("\n");
}


int InsertHeadList(Node **pNode, ElemType insertElem)
{
    Node *pInsert;
    pInsert = new Node;
    pInsert->elem = insertElem;
    pInsert->next = *pNode;
    *pNode = pInsert;
    return 1;
}

int InsertLastList(Node **pNode, ElemType insertElem)
{
    Node *pInsert;
    Node *pHead;
    Node *pTemp;
    pHead = *pNode;
    pTemp = pHead;
    pInsert = new Node;
    pInsert->elem = insertElem;
    pInsert->next = NULL;
    while(pHead->next != NULL)
    {
        pHead = pHead->next;
    }
    pHead->next = pInsert;
    *pNode = pTemp;
    return 1;
}

ElemType DeleteHeadList(Node **pNode)
{
    Node *pTemp = *pNode;
    ElemType elemvalue = pTemp->elem;
    *pNode = pTemp->next;
    delete pTemp;
    return elemvalue;
}

ElemType DeleteLastList(Node **pNode)
{
    Node *pHead;
    Node *pTemp;
    ElemType elemvalue;
    pHead = *pNode;
    pTemp = pHead;
    while(pHead->next != NULL)
    {
        pTemp = pHead;
        pHead = pHead->next;
    }

    elemvalue = pTemp->elem;
    pTemp->next = NULL;
    delete pHead;
    return elemvalue;
}

int main()
{
    Node *pList = NULL;
    InitList(&pList);
    int NumOfData;
    cin >> NumOfData;
    for(int i=0;i < NumOfData;i++){
        Node *pList = NULL;
        InitList(&pList);
        int num;
        cin >> num;
        pList = CreastList(pList,num);
        int selectnum;
        cin >> selectnum;
        for(int j=0;j<selectnum;j++){
            int option,number;
            cin >> option;
            if(option == 1 ){
                cin >> number;
                InsertHeadList(&pList, number);
            }
            else if(option == 2){
                DeleteHeadList(&pList);
            }
            else if(option == 3){
                cin >> number;
                InsertLastList(&pList, number);
            }
            else{
                DeleteLastList(&pList);
            }
        }
        int first,second;
        cin >> first >> second;
        cout << "Case #" << i+1 << ":" << endl;
        PrintList(pList,first,second);
    }
}

没有标签
首页      开发      IT节程序设计竞赛网络赛(二)

发表评论

textsms
account_circle
email

Blask

IT节程序设计竞赛网络赛(二)
2月中旬举办了场代码比赛,拉几道我会写的题目来放放(出题人老二次元了) 题目L 我的数据结构不可能这么难 题目详情: 小明同学最近学了数据结构的链表,他觉得自己无敌厉害,…
扫描二维码继续阅读
2020-05-12