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编写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
| #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);
}
}
|