题目描述
链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。
输入
输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；“show”之后没有整数。
输出
如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”，否则输出“insert fail”。如果是“show”则输出列表中的所有元素，如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。
样例输入
3 3 2 1 21 show delete 1 show delete 2 show delete 1 show delete 2 insert 2 5 show insert 1 5 show insert 1 7 show insert 2 5 show insert 3 6 show insert 1 8 show get 2
样例输出
1 2 3 delete OK 2 3 delete OK 2 delete OK Link list is empty delete fail insert fail Link list is empty insert OK 5 insert OK 7 5 insert OK 7 5 5 insert OK 7 5 6 5 insert OK 8 7 5 6 5 7
C++代码
1 #include <iostream> 2 using namespace std; 3 #include<stdio.h> 4 #include<cstring> 5 #define OK 1 6 #define ERROR 0 7 typedef int ElemType; 8 9 typedef struct LNode 10 { 11 ElemType data; 12 struct LNode *next; 13 }LNode,*LinkList; 14 15 int GetElem_L(LinkList L,int i,ElemType &e) 16 { 17 LNode *p = L->next; 18 int j = 1; 19 while(p && j < i) 20 { 21 j++; 22 p = p->next; 23 } 24 if(!p || j > i) 25 { 26 return ERROR; 27 } 28 e = p->data; 29 return OK; 30 } 31 int ListInsert_L(LinkList &L,int i,ElemType e) 32 { 33 LNode *p,*s; 34 p = L; 35 int j = 0; 36 while(p && j < i - 1) 37 { 38 j++; 39 p = p->next; 40 } 41 if(!p || j > i - 1) 42 { 43 return ERROR; 44 } 45 s = new LNode; 46 s->next = p->next; 47 s->data = e; 48 p->next = s; 49 return OK; 50 } 51 int ListDelete_L(LinkList &L,int i,ElemType &e) 52 { 53 LNode *p,*q; 54 p = L; 55 int j = 0; 56 while(p->next && j < i - 1) 57 { 58 j++; 59 p = p->next; 60 } 61 if(!(p->next) || j > i - 1) 62 { 63 return ERROR; 64 } 65 q = p->next; 66 p->next = q->next; 67 e = q->data; 68 delete q; 69 return OK; 70 } 71 72 void CreateList_L(LinkList &L,int n) 73 { 74 L = new LNode; 75 L->next = nullptr; 76 for(int i = 0;i < n;i++) 77 { 78 LNode *p = new LNode; 79 scanf("%d",&p->data); 80 p->next = L->next; 81 L->next = p; 82 } 83 } 84 void ShowList_L(LinkList L) 85 { 86 LNode *p = L->next; 87 if(p == nullptr) 88 { 89 printf("Link list is empty "); 90 return ; 91 } 92 while(p) 93 { 94 printf("%d ",p->data); 95 p = p->next; 96 } 97 printf(" "); 98 } 99 int main() 100 { 101 LinkList L; 102 int N,M; 103 scanf("%d",&N); 104 CreateList_L(L,N); 105 scanf("%d",&M); 106 while(M--) 107 { 108 char str[7]; 109 scanf("%s",&str); 110 if(!strcmp(str,"get")) 111 { 112 int n; 113 ElemType e; 114 scanf("%d",&n); 115 if(GetElem_L(L,n,e)) 116 { 117 printf("%d ",e); 118 } 119 else 120 { 121 printf("get fail "); 122 } 123 } 124 else if(!strcmp(str,"insert")) 125 { 126 int n; 127 ElemType e; 128 scanf("%d%d",&n,&e); 129 if(ListInsert_L(L,n,e)) 130 { 131 printf("insert OK "); 132 } 133 else 134 { 135 printf("insert fail "); 136 } 137 } 138 else if(!strcmp(str,"delete")) 139 { 140 int n; 141 ElemType e; 142 scanf("%d",&n); 143 if(ListDelete_L(L,n,e)) 144 { 145 printf("delete OK "); 146 } 147 else 148 { 149 printf("delete fail "); 150 } 151 } 152 else if(!strcmp(str,"show")) 153 { 154 ShowList_L(L); 155 } 156 } 157 return 0; 158 }