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);
}
}
发表回复