IT节程序设计竞赛网络赛（二）

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

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

题目详情：

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

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

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

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

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

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

• 输入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);
    }
}