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); } }
|