1 #ifndef SINGLE_LIST_H  2 #define SINGLE_LIST_H  3   4 #ifndef INT_MAX  5 #define INT_MAX 2147483647  6 #define INT_MIN (-INT_MAX - 1)  7 #endif  8 #define ERROR INT_MIN  9 #define OK 0 10 #ifndef NULL 11 #define NULL 0 12 #endif 13 template<class T> 14 struct ListNode { 15     T var; 16     ListNode<T> *next; 17     ListNode() : next(NULL) { } 18     ListNode(T v, ListNode<T> *p = NULL) { 19         var = v; 20         next = p; 21     } 22 }; 23  24 template<class T> 25 class Mylist { 26 public: 27     Mylist(); 28     ~Mylist(); 29      30     int size(); 31     bool empty(); 32      33     int insert(int i, T t); 34     int append(T t); 35     int insert_first(T t); 36      37     T get(int i); 38      39     int erase(int i); 40  41 private: 42     ListNode<T> *head;     43     int len; 44 }; 45 template<class T> 46 Mylist<T>::Mylist() { 47     len = 0; 48     head = new ListNode<T>(); 49 } 50 template<class T> 51 Mylist<T>::~Mylist() { 52     if(head) { 53         int i = 0; 54         ListNode<T> *p = NULL; 55         while(i++ < len) {  56             p = head->next;  57             head->next = p->next; 58             delete p; 59         } 60     } 61     delete head; 62 } 63 template<class T> 64 int Mylist<T>::size() { 65     return len; 66 } 67 template<class T> 68 bool Mylist<T>::empty() { 69     return 0 == len; 70 } 71 template<class T> 72 int Mylist<T>::insert(int i, T t) { 73     if(i < 1 || i > len && len) return ERROR; 74  75     ListNode<T> *p = head; 76     int j = 1; 77     while(p && j++ < i) { p = p->next; } 78      79     ListNode<T> *s = p->next; 80     p->next = new ListNode<T>(t); 81     p->next->next = s;  82      83     len++; 84     return OK; 85 } 86 template<class T> 87 int Mylist<T>::append(T t) { 88     ListNode<T> *p = head; 89     int j = 0; 90     while(p && j++ < len) { p = p->next; } 91     p->next = new ListNode<T>(t); 92     len++; 93     return OK; 94 } 95 template<class T> 96 int Mylist<T>::insert_first(T t) { 97     return insert(1, t);  98 } 99 template<class T>100 T Mylist<T>::get(int i) {101     if(i < 1 || i > len) return ERROR;102     ListNode<T> *p = head->next;103     int j = 1;104     while(p && j < i) { p = p->next; j++; }105     return p->var;106 }107 template<class T>108 int Mylist<T>::erase(int i) {109     if(i < 1 || i > len) return ERROR;110     ListNode<T> *p = head;111     int j = 1;112     while(p && j < i) { p = p->next; j++; }113     114     ListNode<T> *s = p->next;115     p->next = s->next;116     delete s;117     118     len--;119     return OK;120 }121 122 #endif

  1 #ifndef BI_LINK_H  2 #define BI_LINK_H  3   4 #ifndef INT_MAX  5 #define INT_MAX 0x8fffffff  6 #define INT_MIN (-INT_MAX - 1)  7 #endif  8 #define ERROR INT_MIN  9 #define OK 0 10 #ifndef NULL 11 #define NULL 0 12 #endif 13  14 template<class T> 15 struct BLinkNode { 16     T var; 17     BLinkNode<T> *prev; 18     BLinkNode<T> *next; 19     BLinkNode() : prev(NULL), next(NULL) { } 20     BLinkNode(T v, BLinkNode<T> *p = NULL, BLinkNode<T> *n = NULL) : var(v), prev(p), next(n) { } 21 }; 22  23 template<class T> 24 class Bilink { 25 public: 26     Bilink(); 27     ~Bilink(); 28      29     int size(); 30     bool empty(); 31  32     T get(int index); 33     T get_first(); 34     T get_last(); 35  36     int insert(int index, T t); 37     int insert_first(T t); 38     int append_last(T t); 39  40     int erase(int index); 41     int erase_first(); 42     int erase_last(); 43 private: 44     int len; 45     BLinkNode<T> *head; 46 }; 47  48 template<class T> 49 Bilink<T>::Bilink():len(0) { 50     head = new BLinkNode<T>(); 51     head->prev = head->next = head; 52 } 53 template<class T> 54 Bilink<T>::~Bilink() { 55     BLinkNode<T> *p = NULL; 56     int i = 0; 57     while(i++ < len) { 58         p = head->next; 59         head->next = p->next; 60         delete p; 61     } 62     delete head; 63 } 64 template<class T> 65 int Bilink<T>::size() { 66     return len; 67 } 68 template<class T> 69 bool Bilink<T>::empty() { 70     return 0 == len; 71 } 72 template<class T> 73 T Bilink<T>::get(int index) { 74     if(index < 1 || index > len) return head->var; 75     int i = 0; 76     BLinkNode<T> *p = head; 77     while(i++ < index) { 78         p = p->next; 79     } 80     return p->var; 81 } 82 template<class T> 83 T Bilink<T>::get_first() { 84     if(len) { 85         return head->next->var; 86     } 87     return head->var; 88 } 89 template<class T> 90 T Bilink<T>::get_last() { 91     if(len) { 92         return head->prev->var; 93     } 94     return head->var; 95 } 96 template<class T> 97 int Bilink<T>::insert(int index, T t) { 98     if(index < 1 || index > len && len) return ERROR; 99     if(index == 1) return insert_first(t);100     int mid = (len + 1) >> 1;101     BLinkNode<T> *p = head;102     BLinkNode<T> *s = new BLinkNode<T>(t);103     int i = 1;104     if(index <= mid) {105         while(i++ < index) { p = p->next; }106         s->prev = p;107         s->next = p->next;108         p->next->prev = s;109         p->next = s;110     }111     else {112         while(i++ <= index) { p = p->prev; }113         s->next = p;114         s->prev = p->prev;115         p->prev->next = s;116         p->prev = s;117     }118     len++;119     return OK;120 }121 template<class T>122 int Bilink<T>::insert_first(T t) {123     BLinkNode<T> *s = new BLinkNode<T>(t);124     BLinkNode<T> *p = head;125     s->prev = p;126     s->next = p->next;127     p->next->prev = s;128     p->next = s;129     len++;130     return OK;131 }132 template<class T>133 int Bilink<T>::append_last(T t) {134     BLinkNode<T> *s = new BLinkNode<T>(t);135     BLinkNode<T> *p = head;136     s->prev = p->prev;137     s->next = p;138     p->prev->next = s;139     p->prev = s;140     len++;141     return OK;142 }143 template<class T>144 int Bilink<T>::erase(int index) {145     if(index < 1 || index > len) { return ERROR; }146     BLinkNode<T> *p = head;147     int mid = len >> 1;148     int i = 1;149     if(index <= len) {150         while(i++ < index) { p = p->next; }151         BLinkNode<T> *s = p->next;152         s->next->prev = p;153         p->next = s->next;154         delete s;155     }156     else {157         while(i++ < index) { p = p->prev; }158         BLinkNode<T> *s = p->prev;159         s->prev->next = p;160         p->prev = s->prev;161         delete s;162     }163     len--;164     return OK;165 }166 template<class T>167 int Bilink<T>::erase_first() {168     if(!len) return ERROR;169     BLinkNode<T> *p = head;170     BLinkNode<T> *s = p->next;171     s->next->prev = p;172     p->next = s->next;173     len--;174     return OK;175 }176 template<class T>177 int Bilink<T>::erase_last() {178     if(!len) return ERROR;179     BLinkNode<T> *p = head;180     BLinkNode<T> *s = p->prev;181     s->prev->next = p;182     p->prev = s->prev;183     len--;184     return OK;    185 }186 187 #endif