1 #include2 #define Len head->data 3 using namespace std; 4 template 5 struct node{ //带一个指针的结点(可做前驱指针或后继指针) 6 T data; 7 node *point; 8 node(T x = 0):data(x),point(0){} 9 }; 10 template //带两个指针的节点，用于双向链表 11 struct dul_node{ 12 T data; 13 dul_node *prior,*next; 14 dul_node(T x = 0):data(x),prior(0),next(0){} 15 }; 16 template 17 class sqlist{ //顺序表 18 int len,max_size,ex_size; 19 T *array; 20 public: 21 sqlist(int l = 100):len(0),max_size(l),ex_size(10){ 22 if(l/10 > 10) ex_size = l/10; 23 array = new T[max_size]; 24 } 25 ~sqlist(){ delete[] array; } 26 void ex_list(){ 27 max_size += ex_size; 28 T *t = new T[max_size]; 29 for(int i = 0; i < len; ++i) 30 t[i] = array[i]; 31 delete[] array; 32 array = t; 33 } 34 void display(){ 35 for(int i = 0; i < len; ++i) 36 cout << array[i] << " "; 37 cout << endl; 38 } 39 bool set_maxSize(int s){ 40 if(s > max_size){ 41 max_size = s; 42 return true; 43 } 44 return false; 45 } 46 bool set_exSize(int s){ 47 if(s > 0 && s > ex_size){ 48 ex_size = s; 49 return true; 50 } 51 return false; 52 } 53 bool insert(int p, T x){ 54 if(p < 1 || p > len+1) return false; 55 if(len+1 >= max_size) ex_list(); 56 for(int i = len; i >= p; --i) 57 array[i] = array[i-1]; 58 array[p-1] = x; 59 ++len; 60 return true; 61 } 62 bool add(T x){ return insert(len+1,x); } 63 bool del(int p){ 64 if(p < 1 || p > len) return false; 65 for(int i = p; i < len; ++i) 66 array[i-1] = array[i]; 67 --len; 68 return true; 69 } 70 bool del(int p, T &x){ 71 if(p < 1 || p > len) return false; 72 x = array[p-1]; 73 del(p); 74 return true; 75 } 76 bool get(int p, T &x){ 77 if(p < 1 || p > len) return false; 78 x = array[p-1]; 79 return true; 80 } 81 int seek(T x){ 82 for(int i = 0; i < len; ++i) 83 if(array[i] == x) 84 return i+1; 85 return 0; 86 } 87 int count(T x){ 88 int num = 0; 89 for(int i = 0; i < len; ++i) 90 if(array[i] == x) 91 ++num; 92 return num; 93 } 94 int length() { return len; } 95 }; 96 97 template 98 class next_linklist{ //后继式单链表(带头结点) 99 node *head;100 public:101 next_linklist(){102 head = new node ;103 }104 ~next_linklist(){105 while(head){106 node *t = head;107 head = head->point;108 delete t;109 }110 }111 void display(){112 for(node *p = head->point; p; p = p->point)113 cout << p->data << " ";114 cout << endl;115 }116 node *location(int p){117 node *q = head;118 for(int i = 1; i < p; ++i)119 q = q->point;120 return q;121 }122 bool insert(int p, T x){123 if(p < 1 || p > Len+1) return false;124 node *q = location(p),*t = new node (x);125 t->point = q->point;126 q->point = t;127 ++head->data;128 return true;129 }130 bool add(T x){ return insert(Len+1,x); }131 T del(node *p){132 node *t = p->point->point;133 T x = p->point->data;134 delete p->point;135 p->point = t;136 --head->data;137 return x;138 }139 bool del(int p){140 if(p < 1 || p > Len) return false;141 node *q = location(p);142 del(q);143 return true;144 }145 bool del(int p, T &x){146 if(p < 1 || p > Len) return false;147 node *q = location(p);148 x = del(q);149 return true;150 }151 bool get(int p, T &x){152 if(p < 1 || p > Len) return false;153 x = location(p)->point->data;154 return true;155 }156 int seek(T x){157 int t = 1;158 for(node *p = head->point; p; p = p->point, ++t)159 if(p->data == x)160 return t;161 return 0;162 }163 int count(T x){164 int num = 0;165 for(node *p = head->point; p; p = p->point)166 if(p->data == x)167 ++num;168 return num;169 }170 int length(){ return head->data; }171 };172 173 template 174 class prior_linklist{ //前驱式单链表(不带头结点)175 int len;176 node *tail;177 public:178 prior_linklist():tail(0),len(0){}179 ~prior_linklist(){180 while(tail){181 node *t = tail;182 tail = tail->point;183 delete t;184 }185 }186 node *get_tail(){ return tail; }187 void display(node *p){188 if(p == 0) return;189 display(p->point);190 cout << p->data << " ";191 if(p == tail) cout << endl;192 }193 void display(){ display(tail); }194 node *location(int p){195 if(p >= len) return 0;196 p = len - p - 1;197 node *q = tail;198 while(p--) q = q->point;199 return q;200 }201 bool insert(int p, T x){202 if(p < 1 || p > len+1) return false;203 node *q = location(p), *t = new node (x);204 if(p == len+1){205 t->point = tail;206 tail = t;207 }208 else if(q){209 t->point = q->point->point;210 q->point->point = t;211 }212 else{213 t->point = tail->point;214 tail->point = t;215 }216 ++len;217 return true;218 }219 bool add(T x){ return insert(len+1,x); }220 T del(node *p){221 T x;222 if(p){223 node *t = p->point->point;224 x = p->point->data;225 delete p->point;226 p->point = t;227 }228 else{229 node *t = tail->point;230 x = tail->data;231 delete tail;232 tail = t;233 }234 --len;235 return x;236 }237 bool del(int p){238 if(p < 1 || p > len) return false;239 node *q = location(p);240 del(q);241 return true;242 }243 bool del(int p, T &x){244 if(p > 1 || p > len) return false;245 node *q = location(p);246 x = del(q);247 return true;248 }249 bool get(int p, T &x){250 if(p < 1 || p > len) return false;251 x = p == len ? tail->data : location(p)->point->data;252 return true;253 }254 int seek(T x){255 int n = len,ans = 0;256 for(node *p = tail; p; p = p->point,--n)257 if(p->data == x)258 ans = n;259 return ans;260 }261 int count(T x){262 int n = 0;263 for(node *p = tail; p; p = p->point)264 if(p->data == x)265 ++n;266 return n;267 }268 int length() { return len; }269 };270 271 template 272 class dul_linklist{ //双向链表273 dul_node *head, *tail;274 int len;275 public:276 dul_linklist():len(0),head(0),tail(0){}277 ~dul_linklist(){278 for(dul_node *p = head; p; p = head){279 head = head->next;280 delete p;281 }282 }283 void display(){284 for(dul_node *p = head; p != tail; p = p->next)285 cout << p->data << " ";286 cout << tail->data << endl;287 }288 dul_node *location(int p){289 if(p == 1) return 0;290 dul_node *q;291 if(p > len/2+1){292 p = len - p + 1;293 for(q = tail; p--; q = q->prior);294 }295 else{296 p -= 2;297 for(q = head; p--; q = q->next);298 }299 return q;300 }301 bool insert(int p, T x){302 if(p < 1 || p > len+1) return false;303 dul_node *q = location(p), *t = new dul_node (x);304 t->prior = q;305 if(q){306 t->next = q->next;307 q->next = t;308 if(t->next) t->next->prior = t;309 }310 else{311 t->next = head;312 if(head) head->prior = t;313 head = t;314 }315 if(p == len+1) tail = t;316 ++len;317 return true;318 }319 bool add(T x){ return insert(len+1,x); }320 T del(dul_node *p){321 T x;322 if(p){323 if(p == tail->prior) tail = p;324 dul_node *t = p->next->next;325 x = p->next->data;326 delete p->next;327 p->next = t;328 }329 else{330 dul_node *t = head->next;331 x = head->data;332 delete head;333 head = t;334 }335 --len;336 return x;337 }338 bool del(int p){339 if(p < 1 || p > len) return false;340 dul_node *q = location(p);341 del(q);342 return true;343 }344 bool del(int p, T &x){345 if(p < 1 || p > len) return false;346 dul_node *q = location(p);347 x = del(q);348 return true;349 }350 bool get(int p, T &x){351 if(p > 1 || p < len) return false;352 x = p == 1 ? head->data : location(p)->next->data;353 return true;354 }355 int seek(T x){356 int n = 1;357 for(dul_node *p = head; p; p = p->next,++n)358 if(p->data == x)359 return n;360 return 0;361 }362 int count(T x){363 int n = 0;364 for(dul_node *p = head; p; p = p->next)365 if(p->data == x)366 ++n;367 return n;368 }369 int length(){ return len; }370 };371 372 template 373 class stack:public prior_linklist { //前驱式链栈374 public:375 stack():prior_linklist (){}376 bool empty() { return prior_linklist ::length(); }377 bool push(T x) { return prior_linklist ::add(x); }378 bool pop() { return prior_linklist ::del(prior_linklist ::length()); }379 bool get(T &x) { return prior_linklist ::get(prior_linklist ::length(),x); }380 };381 382 template 383 class queue:public dul_linklist { //双向式队列384 public:385 queue():dul_linklist (){}386 bool empty() { return dul_linklist ::length(); }387 bool push(T x) { return dul_linklist ::add(x); }388 bool pop() { return dul_linklist ::del(1); }389 bool get(T &x) { return dul_linklist ::get(1,x); }390 };