题目描述
实现一个单链表,链表初始为空,支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “H x”,表示向链表头插入一个数x。
(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。
(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
样例
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;
void init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx++;
}
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main(int argc, const char** argv, const char** envp)
{
int var_m = 0;
cin >> var_m;
init();
while (var_m--)
{
char op;
int x = 0;
int k = 0;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
if (k == 0)
{
head = ne[head];
}
else
{
remove(k - 1);
}
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
int i = head;
while (i != -1)
{
cout << e[i] << " ";
i = ne[i];
}
cout << endl;
}
反汇编代码
.text:00412C20 ; void __cdecl init_0()
.text:00412C20 init_0 proc near ; CODE XREF: initj
.text:00412C20 push ebp
.text:00412C21 mov ebp, esp
.text:00412C23 sub esp, 0C0h
.text:00412C29 push ebx
.text:00412C2A push esi
.text:00412C2B push edi
.text:00412C2C mov edi, ebp
.text:00412C2E xor ecx, ecx
.text:00412C30 mov eax, 0CCCCCCCCh
.text:00412C35 rep stosd
.text:00412C37 mov ecx, offset db_JMC_flag
.text:00412C3C call __CheckForDebuggerJustMyCode
.text:00412C41 mov g_dw_head, -1 ; head = -1;
.text:00412C4B mov g_dw_idx, 0 ; idx = 0;
.text:00412C55 pop edi
.text:00412C56 pop esi
.text:00412C57 pop ebx
.text:00412C58 add esp, 0C0h
.text:00412C5E cmp ebp, esp
.text:00412C60 call __RTC_CheckEsp
.text:00412C65 mov esp, ebp
.text:00412C67 pop ebp
.text:00412C68 retn
.text:00412C68 init_0 endp
----------
.text:00412AC0 add_to_head_0 proc near ; CODE XREF: add_to_headj
.text:00412AC0
.text:00412AC0 x = dword ptr 8
.text:00412AC0
.text:00412AC0 push ebp
.text:00412AC1 mov ebp, esp
.text:00412AC3 sub esp, 0C0h
.text:00412AC9 push ebx
.text:00412ACA push esi
.text:00412ACB push edi
.text:00412ACC mov edi, ebp
.text:00412ACE xor ecx, ecx
.text:00412AD0 mov eax, 0CCCCCCCCh
.text:00412AD5 rep stosd
.text:00412AD7 mov ecx, offset db_JMC_flag
.text:00412ADC call __CheckForDebuggerJustMyCode
.text:00412AE1 mov eax, g_dw_idx
.text:00412AE6 mov ecx, [ebp+x]
.text:00412AE9 mov g_dw_e[eax*4], ecx ; e[idx] = x;
.text:00412AF0 mov edx, g_dw_idx
.text:00412AF6 mov eax, g_dw_head
.text:00412AFB mov g_ne[edx*4], eax ; ne[idx]=head;
.text:00412B02 mov ecx, g_dw_idx
.text:00412B08 mov g_dw_head, ecx
.text:00412B0E mov edx, g_dw_idx
.text:00412B14 add edx, 1
.text:00412B17 mov g_dw_idx, edx ; head = idx++;
.text:00412B1D pop edi
.text:00412B1E pop esi
.text:00412B1F pop ebx
.text:00412B20 add esp, 0C0h
.text:00412B26 cmp ebp, esp
.text:00412B28 call __RTC_CheckEsp
.text:00412B2D mov esp, ebp
.text:00412B2F pop ebp
.text:00412B30 retn
.text:00412B30 add_to_head_0 endp
----------
.text:00412A20 add_0 proc near ; CODE XREF: addj
.text:00412A20
.text:00412A20 k = dword ptr 8
.text:00412A20 x = dword ptr 0Ch
.text:00412A20
.text:00412A20 push ebp
.text:00412A21 mov ebp, esp
.text:00412A23 sub esp, 0C0h
.text:00412A29 push ebx
.text:00412A2A push esi
.text:00412A2B push edi
.text:00412A2C mov edi, ebp
.text:00412A2E xor ecx, ecx
.text:00412A30 mov eax, 0CCCCCCCCh
.text:00412A35 rep stosd
.text:00412A37 mov ecx, offset db_JMC_flag
.text:00412A3C call __CheckForDebuggerJustMyCode
.text:00412A41 mov eax, g_dw_idx
.text:00412A46 mov ecx, [ebp+x]
.text:00412A49 mov g_dw_e[eax*4], ecx ; e[idx]=x;
.text:00412A50 mov edx, g_dw_idx
.text:00412A56 mov eax, [ebp+k]
.text:00412A59 mov ecx, g_ne[eax*4]
.text:00412A60 mov g_ne[edx*4], ecx ; ne[idx]=ne[k];
.text:00412A67 mov edx, [ebp+k]
.text:00412A6A mov eax, g_dw_idx
.text:00412A6F mov g_ne[edx*4], eax
.text:00412A76 mov ecx, g_dw_idx
.text:00412A7C add ecx, 1
.text:00412A7F mov g_dw_idx, ecx ; ne[k]=idx++;
.text:00412A85 pop edi
.text:00412A86 pop esi
.text:00412A87 pop ebx
.text:00412A88 add esp, 0C0h
.text:00412A8E cmp ebp, esp
.text:00412A90 call __RTC_CheckEsp
.text:00412A95 mov esp, ebp
.text:00412A97 pop ebp
.text:00412A98 retn
.text:00412A98 add_0 endp
----------
.text:00412CE0 remove_0 proc near ; CODE XREF: removej
.text:00412CE0
.text:00412CE0 k = dword ptr 8
.text:00412CE0
.text:00412CE0 push ebp
.text:00412CE1 mov ebp, esp
.text:00412CE3 sub esp, 0C0h
.text:00412CE9 push ebx
.text:00412CEA push esi
.text:00412CEB push edi
.text:00412CEC mov edi, ebp
.text:00412CEE xor ecx, ecx
.text:00412CF0 mov eax, 0CCCCCCCCh
.text:00412CF5 rep stosd
.text:00412CF7 mov ecx, offset db_JMC_flag
.text:00412CFC call __CheckForDebuggerJustMyCode
.text:00412D01 mov eax, [ebp+k]
.text:00412D04 mov ecx, g_ne[eax*4]
.text:00412D0B mov edx, [ebp+k]
.text:00412D0E mov eax, g_ne[ecx*4]
.text:00412D15 mov g_ne[edx*4], eax ; ne[k]=ne[ne[k]];
.text:00412D1C pop edi
.text:00412D1D pop esi
.text:00412D1E pop ebx
.text:00412D1F add esp, 0C0h
.text:00412D25 cmp ebp, esp
.text:00412D27 call __RTC_CheckEsp
.text:00412D2C mov esp, ebp
.text:00412D2E pop ebp
.text:00412D2F retn
.text:00412D2F remove_0 endp
.text:00412DB0 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:00412DB0 main proc near ; CODE XREF: j_mainj
.text:00412DB0
.text:00412DB0 m = dword ptr -104h
.text:00412DB0 var_44 = byte ptr -44h
.text:00412DB0 var_dw_i = dword ptr -3Ch
.text:00412DB0 var_dw_x = dword ptr -30h
.text:00412DB0 var_dw_k = dword ptr -24h
.text:00412DB0 var_db_op = byte ptr -15h
.text:00412DB0 var_m = dword ptr -0Ch
.text:00412DB0 var_4 = dword ptr -4
.text:00412DB0 argc = dword ptr 8
.text:00412DB0 argv = dword ptr 0Ch
.text:00412DB0 envp = dword ptr 10h
.text:00412DB0
.text:00412DB0 push ebp ; 保存ebp的值
.text:00412DB1 mov ebp, esp ; 获得栈顶指针的位置
.text:00412DB3 sub esp, 104h ; 提升栈顶
.text:00412DB9 push ebx
.text:00412DBA push esi
.text:00412DBB push edi ; 保护现场
.text:00412DBC lea edi, [ebp-44h] ; 获得刚才分配的空间的栈顶指针
.text:00412DBF mov ecx, 11h ; 将要循环填充的次数
.text:00412DC4 mov eax, 0CCCCCCCCh ; 循环填充的数值
.text:00412DC9 rep stosd ; 循环填充刚才分配的空间
.text:00412DCB mov eax, ___security_cookie ; 保护栈溢出
.text:00412DD0 xor eax, ebp
.text:00412DD2 mov [ebp-4], eax
.text:00412DD5 mov ecx, offset db_JMC_flag
.text:00412DDA call __CheckForDebuggerJustMyCode
.text:00412DDF mov esi, esp
.text:00412DE1 lea eax, [ebp+var_m] ; 局部变量m
.text:00412DE4 push eax
.text:00412DE5 mov ecx, ds:std__cin
.text:00412DEB call ds:operator_dwInput ; cin>>var_m;
.text:00412DF1 cmp esi, esp
.text:00412DF3 call __RTC_CheckEsp
.text:00412DF8 call init ; 对head和idx赋值
.text:00412DFD
.text:00412DFD WHILE_BEGIN: ; CODE XREF: main:ELSE0_ENDj
.text:00412DFD mov eax, [ebp+var_m]
.text:00412E00 mov [ebp+m], eax
.text:00412E06 mov ecx, [ebp+var_m]
.text:00412E09 sub ecx, 1 ; var_m--
.text:00412E0C mov [ebp+var_m], ecx
.text:00412E0F cmp [ebp+m], 0 ; m的值与0比较
.text:00412E16 jz WHILE_END_FOR_INIT ; while(m--)
.text:00412E1C lea eax, [ebp+var_db_op] ; {
.text:00412E1F push eax
.text:00412E20 mov ecx, ds:std__cin
.text:00412E26 push ecx
.text:00412E27 call operator_db_Input ; cin>>op;
.text:00412E2C add esp, 8
.text:00412E2F movsx eax, [ebp+var_db_op]
.text:00412E33 cmp eax, 'H'
.text:00412E36 jnz short IF0_BEGIN ; if(op=='H')
.text:00412E38 mov esi, esp ; {
.text:00412E3A lea eax, [ebp+var_dw_x]
.text:00412E3D push eax
.text:00412E3E mov ecx, ds:std__cin
.text:00412E44 call ds:operator_dwInput ; cin>>x;
.text:00412E4A cmp esi, esp
.text:00412E4C call __RTC_CheckEsp
.text:00412E51 mov eax, [ebp+var_dw_x]
.text:00412E54 push eax
.text:00412E55 call add_to_head ; add_to_head(x);
.text:00412E5A add esp, 4
.text:00412E5D jmp ELSE0_END ; }
.text:00412E62 ; ---------------------------------------------------------------------------
.text:00412E62
.text:00412E62 IF0_BEGIN: ; CODE XREF: main+86j
.text:00412E62 movsx eax, [ebp+var_db_op]
.text:00412E66 cmp eax, 'D'
.text:00412E69 jnz short ELSE0_BEGIN_END ; else if(op=='D')
.text:00412E6B mov esi, esp ; {
.text:00412E6D lea eax, [ebp+var_dw_k]
.text:00412E70 push eax
.text:00412E71 mov ecx, ds:std__cin
.text:00412E77 call ds:operator_dwInput ; cin>>k;
.text:00412E7D cmp esi, esp
.text:00412E7F call __RTC_CheckEsp
.text:00412E84 cmp [ebp+var_dw_k], 0
.text:00412E88 jnz short IF2_BEGIN ; if(k==0)
.text:00412E8A mov eax, g_dw_head ; {
.text:00412E8F mov ecx, g_ne[eax*4]
.text:00412E96 mov g_dw_head, ecx ; head = ne[head];
.text:00412E9C jmp short ELSE1_END ; }
.text:00412E9E ; ---------------------------------------------------------------------------
.text:00412E9E
.text:00412E9E IF2_BEGIN: ; CODE XREF: main+D8j
.text:00412E9E mov eax, [ebp+var_dw_k] ; else{
.text:00412EA1 sub eax, 1
.text:00412EA4 push eax
.text:00412EA5 call remove ; remove(k-1);
.text:00412EAA add esp, 4 ; }
.text:00412EAD
.text:00412EAD ELSE1_END: ; CODE XREF: main+ECj
.text:00412EAD jmp short ELSE0_END
.text:00412EAF ; ---------------------------------------------------------------------------
.text:00412EAF
.text:00412EAF ELSE0_BEGIN_END: ; CODE XREF: main+B9j
.text:00412EAF mov esi, esp ; else{
.text:00412EB1 lea eax, [ebp+var_dw_x]
.text:00412EB4 push eax
.text:00412EB5 mov edi, esp
.text:00412EB7 lea ecx, [ebp+var_dw_k]
.text:00412EBA push ecx
.text:00412EBB mov ecx, ds:std__cin
.text:00412EC1 call ds:operator_dwInput
.text:00412EC7 cmp edi, esp
.text:00412EC9 call __RTC_CheckEsp
.text:00412ECE mov ecx, eax
.text:00412ED0 call ds:operator_dwInput ; cin>>k>>x;
.text:00412ED6 cmp esi, esp
.text:00412ED8 call __RTC_CheckEsp
.text:00412EDD mov eax, [ebp+var_dw_x]
.text:00412EE0 push eax
.text:00412EE1 mov ecx, [ebp+var_dw_k]
.text:00412EE4 sub ecx, 1
.text:00412EE7 push ecx
.text:00412EE8 call add ; add(k-1,x);
.text:00412EED add esp, 8 ; }
.text:00412EF0
.text:00412EF0 ELSE0_END: ; CODE XREF: main+ADj
.text:00412EF0 ; main:ELSE1_ENDj
.text:00412EF0 jmp WHILE_BEGIN ; }
.text:00412EF5 ; ---------------------------------------------------------------------------
.text:00412EF5
.text:00412EF5 WHILE_END_FOR_INIT: ; CODE XREF: main+66j
.text:00412EF5 mov eax, g_dw_head
.text:00412EFA mov [ebp+var_dw_i], eax ; int i = head;
.text:00412EFD jmp short FOR_CMP
.text:00412EFF ; ---------------------------------------------------------------------------
.text:00412EFF
.text:00412EFF FOR_STEP: ; CODE XREF: main+190j
.text:00412EFF mov eax, [ebp+var_dw_i] ; while(1){
.text:00412F02 mov ecx, g_ne[eax*4]
.text:00412F09 mov [ebp+var_dw_i], ecx ; i = ne[i];
.text:00412F0C
.text:00412F0C FOR_CMP: ; CODE XREF: main+14Dj
.text:00412F0C cmp [ebp+var_dw_i], -1
.text:00412F10 jz short FOR_END ; if(i!=-1){
.text:00412F12 push offset const_string ; " "
.text:00412F17 mov esi, esp
.text:00412F19 mov eax, [ebp+var_dw_i]
.text:00412F1C mov ecx, g_dw_e[eax*4]
.text:00412F23 push ecx
.text:00412F24 mov ecx, ds:std__cout
.text:00412F2A call ds:operator_dwOutPut
.text:00412F30 cmp esi, esp
.text:00412F32 call __RTC_CheckEsp
.text:00412F37 push eax
.text:00412F38 call operator_dwOutPut_1 ; cout << e[i] << " ";
.text:00412F3D add esp, 8 ; }
.text:00412F40 jmp short FOR_STEP ; }
.text:00412F42 ; ---------------------------------------------------------------------------
.text:00412F42
.text:00412F42 FOR_END: ; CODE XREF: main+160j
.text:00412F42 mov esi, esp
.text:00412F44 push offset std__endl
.text:00412F49 mov ecx, ds:std__cout
.text:00412F4F call ds:operator_dwOutPut_0 ; cout<<endl;
.text:00412F55 cmp esi, esp
.text:00412F57 call __RTC_CheckEsp ; }
.text:00412F5C xor eax, eax
.text:00412F5E push edx
.text:00412F5F mov ecx, ebp
.text:00412F61 push eax
.text:00412F62 lea edx, dword_412F90
.text:00412F68 call @_RTC_CheckStackVars@8 ; _RTC_CheckStackVars(x,x)
.text:00412F6D pop eax
.text:00412F6E pop edx
.text:00412F6F pop edi
.text:00412F70 pop esi
.text:00412F71 pop ebx
.text:00412F72 mov ecx, [ebp+var_4]
.text:00412F75 xor ecx, ebp
.text:00412F77 call @__security_check_cookie@4 ; __security_check_cookie(x)
.text:00412F7C add esp, 104h
.text:00412F82 cmp ebp, esp
.text:00412F84 call __RTC_CheckEsp
.text:00412F89 mov esp, ebp
.text:00412F8B pop ebp
.text:00412F8C retn
.text:00412F8C main endp