チェーンテーブルシリーズ記事(一)

リファレンスhttp://www.cnblogs.com/skywang12345/p/3561803.htmlここでお礼を申し上げます.
C++を採用し、単一チェーンテーブルと双方向循環チェーンテーブルを実現した.
1.単一チェーンテーブル

  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

View Code
 
2.双方向循環チェーンテーブル

  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

View Code
 
私のレベルが限られているため、文章の中でどうしても不当と间违いがあって、みんなの批判と指摘を歓迎して、共に进歩することを望みます!!!