Question
Your task is to implement a double linked list.
Write a program which performs the following operations:
insert x: insert an element with key x into the front of the list.
delete x: delete the first element which has the key of x from the list. If there is not such element, you need not do anything.
deleteFirst: delete the first element from the list.
deleteLast: delete the last element from the list.
Input
The input is given in the following format:
n
command1
command2
…
commandn
In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:
insert x
delete x
deleteFirst
deleteLast
Output
Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.
Constraints
The number of operations ≤ 2,000,000
The number of delete operations ≤ 20
0 ≤ value of a key ≤ 109
The number of elements in the list does not exceed 106
For a delete, deleteFirst or deleteLast operation, there is at least one element in the list.
Sample Input 1
7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
Sample Output 1
6 1 2
Sample Input 2
9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast
Sample Output 2
1
Meaning
Solution
这题坑我了三四个小时,oj测试数据中的第四组删除一个根本就不存在的数据。所以代码只能ac前面三个测试。用的是教材上面的双向链表。后面经过一个大佬给我修改了一下bug,原本在deleem函数中是不能删除最后一个节点的。但是还是不能ac,很恶心,不想看这一题了。感觉弄了好久啥也没学到。
Coding
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 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 |
//双链表基本运算算法(教材上的) #include <stdio.h> #include <malloc.h> #include<iostream> using namespace std; typedef int ElemType; typedef struct DNode //定义双链表结点类型 { ElemType data; struct DNode* prior; //指向前驱结点 struct DNode* next; //指向后继结点 } DLinkNode; void CreateListF(DLinkNode*& L, ElemType a[], int n) //头插法建双链表 { DLinkNode* s; L = (DLinkNode*)malloc(sizeof(DLinkNode)); //创建头结点 L->prior = L->next = NULL; for (int i = 0; i < n; i++) { s = (DLinkNode*)malloc(sizeof(DLinkNode));//创建新结点 s->data = a[i]; s->next = L->next; //将结点s插在原开始结点之前,头结点之后 if (L->next != NULL) L->next->prior = s; L->next = s; s->prior = L; } } void CreateListR(DLinkNode*& L, ElemType a[], int n) //尾插法建双链表 { DLinkNode* s, * r; L = (DLinkNode*)malloc(sizeof(DLinkNode)); //创建头结点 L->prior = L->next = NULL; r = L; //r始终指向终端结点,开始时指向头结点 for (int i = 0; i < n; i++) { s = (DLinkNode*)malloc(sizeof(DLinkNode));//创建新结点 s->data = a[i]; r->next = s; s->prior = r; //将结点s插入结点r之后 r = s; } r->next = NULL; //尾结点next域置为NULL } void InitList(DLinkNode*& L) { L = (DLinkNode*)malloc(sizeof(DLinkNode)); //创建头结点 L->prior = L->next = NULL; } void DestroyList(DLinkNode*& L) { DLinkNode* pre = L, * p = pre->next; while (p != NULL) { free(pre); pre = p; p = pre->next; } free(pre); } bool ListEmpty(DLinkNode* L) { return(L->next == NULL); } int ListLength(DLinkNode* L) { DLinkNode* p = L; int i = 0; while (p->next != NULL) { i++; p = p->next; } return(i); } void DispList(DLinkNode* L) { DLinkNode* p = L->next; printf("%d", p->data); p = p->next; while (p != NULL) { printf(" %d", p->data); p = p->next; } printf("\n"); } bool GetElem(DLinkNode* L, int i, ElemType& e) { int j = 0; DLinkNode* p = L; if (i <= 0) return false; //i错误返回假 while (j < i && p != NULL) { j++; p = p->next; } if (p == NULL) return false; else { e = p->data; return true; } } int LocateElem(DLinkNode* L, ElemType e) { int n = 1; DLinkNode* p = L->next; while (p != NULL && p->data != e) { n++; p = p->next; } if (p == NULL) return(0); else return(n); } bool ListInsert(DLinkNode*& L, int i, ElemType e) { int j = 0; DLinkNode* p = L, * s; if (i <= 0) return false; //i错误返回假 while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { s = (DLinkNode*)malloc(sizeof(DLinkNode)); //创建新结点s s->data = e; s->next = p->next; //将结点s插入到结点p之后 if (p->next != NULL) p->next->prior = s; s->prior = p; p->next = s; return true; } } bool ListDelete(DLinkNode*& L, int i, ElemType& e) { int j = 0; DLinkNode* p = L, * q; if (i <= 0) return false; //i错误返回假 while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q = p->next; //q指向要删除的结点 if (q == NULL) return false; //不存在第i个结点 e = q->data; p->next = q->next; //从单链表中删除*q结点 if (p->next != NULL) p->next->prior = p; free(q); //释放q结点 return true; } } //在循环双链表L中删除第一个值为x的结点。 bool delelem(DLinkNode*& L, ElemType x) { //DLinkNode* p = L->next; //while (p != L && p->data != x) // p = p->next; //if (p != L) //找到第一个元素值为x的结点 //{ // p->next->prior = p->prior; //删除结点*p // p->prior->next = p->next; // free(p); // return true; //} //else // return false; //下面的某个大佬写的 DLinkNode* p = L; while (p->next->data != x && p->next != NULL)p = p->next; if (p->next == NULL)return false; else { DLinkNode* wait_free = p->next; p->next = p->next->next; free(wait_free); return true; } } int main() { DLinkNode* dl; InitList(dl); int n; scanf("%d",&n); //cin >> n; char name[20]; ElemType e; for (int i = 0; i < n; i++) { scanf("%s",&name); cin >> name; if (name[0] == 'i') { scanf("%d", &e); //cin >> e; ListInsert(dl, 1, e); } else if (name[6] == 'F') { ListDelete(dl, 1, e); } else if (name[6] == 'L') { ListDelete(dl, ListLength(dl), e); } else { //cin >> e; scanf("%d", &e); delelem(dl, e); } } DispList(dl); } |