template <typename E> class Link {
public:
E element;
Link* next;
Link(const E& elemval, Link* nextVal = NULL) {
element = elemval;
next = nextVal;
}
Link(Link* nextval = NULL) {
next = nextval;
}
};
template <typename E> class LList : public E::template List
{
private:
/* data */
Link* head;
Link* tail;
Link* curr;
int cnt;
void init() {
curr = tail = head = new Link;
cnt = 0;
}
void removeall() {
while (head != NULL) {
curr = head;
head = head->next;
delete curr;
}
}
public:
LList(int size/* = defaultSize*/) {
init();
}
~LList() {
removeall();
}
void print() const;
void clear() {
removeall();
init();
}
void insert(const E& it) {
curr->next = new Link(it, curr->next);
if (tail == curr) {
tail = curr->next;
}
cnt++;
}
void append(const E& it) {
tail = tail->next = new Link(it, NULL);
cnt++;
}
E remove() {
// Assert(curr->next != NULL, "No element");
E it = curr->next->element;
Link* ltemp = curr->next;
if (tail == curr->next) {
tail = curr;
}
curr->next = curr->next->next;
delete ltemp;
cnt--;
return it;
}
void moveToStart() {
curr = head;
}
void moveToEnd() {
curr = tail;
}
void prev() {
if (curr == head) {
return;
}
Link* temp = head;
while (temp->next != curr) {
temp = temp->next;
}
curr = temp;
}
void next() {
if (curr != tail) {
curr = curr->next;
}
}
int length() const {
return cnt;
}
int currPos() const {
Link* temp = head;
int i;
for (i = 0; curr != temp; i++) {
temp = temp->next;
}
return i;
}
void moveToPos(int pos) {
//assert((pos >= 0) && (pos <= cnt), "Position out of range");
curr = head;
for (int i = 0; i < pos; i++) {
curr = curr->next;
}
}
const E& getValue() const {
// assert(curr->next != NULL, "No value");
return curr->next->element;
}
void reserve() {
int i = 0;
Link* pre = head;
Link* it = head->next;
for (; it->next != NULL; it = it->next, pre = pre->next) {
it = new Link(it->element, pre);
}
Link* temp = tail;
tail->next = it;
tail->element = head->elememt;
head = tail;
}
};
没写main函数?要验证哪些功能?
Link<int>
开始着手做。
参考如下:
int main()
{
LList<int> mylist(5);
cout << "length:"<<mylist.length()<<endl;
mylist.append(100);
cout <<"after append(100):"
mylist.print();
mylist.insert(20);
cout <<"after insert(20):";
mylist.print();
mylist.moveToPos(2);
cout <<"after moveToPos(2): current pos:" << mylist.currPos()<<endl;
mylist.moveToEnd();
cout <<"after moveToEnd: current pos:" << mylist.currPos()<<endl;
mylist.moveToStart();
cout <<"after moveToStart: current pos:" << mylist.currPos()<<endl;
cout << "current value:"<<mylist.getValue()<<endl;
mylist.reserve();
cout << "after reverse:";
mylist.print();
mylist.prev();
cout <<"after prev,current pos:"<<mylist.currPos() <<" , current value:"<<mylist.getValue()<<endl;
return 0;
}