用C++写出自定义链表list[已更新]

by **too wei** July 20th 2015, 01:24

为了简化，只写出了几项简单的功能，如发现任何遗漏之处或bug，欢迎留言

Code:: //list.h #include <iostream> using namespace std; struct node { int data; node * next; node * perior; }; class list { private: node * current; node * head; int size; public: list(); ~list(); void print(); bool is_empty()const {return size==0;} bool insert(const int & item,int pos = 0); //default insert at front bool Delete(const int & pos); //here use Delete not delete because delete is a keyword in c++ const int find(const int & target); const int count(const int & target); const int & length()const {return size;} const int & operator[](int pos); }; ///////////////////////////////////////////////////////////////////////////////////////////////////// list::list():size(0) { current = new node; head = new node; } list::~list() { if(size != 0) { current = head->next; while(current->next != NULL) { current->perior->next = current->next; current->next->perior = current->perior; delete current; current = head->next; } delete current; delete head; } } void list::print() { if(size != 0) //if not empty { current = head; for(int i = 0;i<size;i++) { cout<<i<<". "<<current->data<<endl; current = current->next; } } } bool list::insert(const int & item,int pos) { node * thing = new node; thing->data = item; if(pos>size) pos = size; if(pos ==0) { if(size == 0) { head = thing; head->perior = NULL; head->next = NULL; } else { thing->next = head; head->perior = thing; head = thing; } size++; } else { node * temp = new node; current = head; for(int i = 0;i<pos-1;i++) current = current->next; temp = current->next; current->next = thing; thing->next = temp; thing->perior = current; if(temp != NULL) temp->perior = thing; size++; } return true; } bool list::Delete(const int & pos) { if(pos > size) return false; node * temp = new node; if(pos == 0) //when delete the head { temp = head; head = head->next; head->perior = NULL; delete temp; } else { temp = head; for(int i = 0;i<pos;i++) temp = temp->next; //go to the target current = temp->perior; current->next = temp->next; if(temp->next != NULL) temp->next->perior = current; //means we do not deleting last element delete temp; } size--; return true; } const int list::find(const int & target) { if(size != 0) { int pos = 0; for(current = head;current->next != NULL;current = current->next) { if(current->data == target) return pos; //return the position pos++; } } return -1; //return -1 if no found }; const int list::count(const int & target) { int count = 0; if(size != 0) { for(current = head;current != NULL;current = current->next) { if(current->data == target) count++; } } return count; } const int & list::operator[](int pos) { if(pos > size) pos = size; current = head; if(pos != 0) { for(int i = 0;i<pos;i++) { current = current->next; } } return current->data; }

这是一个拿来测试list的代码

Code:: int main() { list li; if(li.is_empty()) { for(int i = 0;i<8;i++) { li.insert(i*2); } } else { cout<<"The list is not empty!"<<endl; } cout<<"First print out"<<endl; li.print(); cout<<"Integer 6 at position "<<li.find(6)<<endl; cout<<endl; cout<<"Deleting integer at position 3"<<endl; cout<<"Inserting an integer 6 at the last position of list"<<endl; li.Delete(3);//delete position 3 li.insert(6,li.length()); //insert at last and now, got 2 interger 6 cout<<"Second print out"<<endl; li.print(); cout<<"There are "<<li.count(6)<<" integer 6"<<endl; cout<<"The length of list is "<<li.length()<<endl; cout<<"The li[1] is "<<li[1]<<endl; return 0; }