双向链表的C++实现

转载注明出处http://blog.csdn.net/hongkangwl/article/details/22286469

首先定义节点的结构

struct node { int date; node* prev; node* next; }; 老样子，建立双链表的类

class doublelink { public: int doublelink_insert(doublelink* ptr,int position,int member); int doublelink_erase(doublelink* ptr, int position); void doublelink_display(doublelink* ptr, int num); int doublelink_getlength(doublelink* ptr); doublelink() { root = new node; root->prev = NULL; root->next = NULL; length = 0; } protected: private: int length; node* root; }; 插入元素

int doublelink::doublelink_insert(doublelink *ptr, int position, int member) { node* nodeinsert = new node; nodeinsert->date = member; if (ptr->doublelink_getlength(ptr) == 0) { root->next = nodeinsert; nodeinsert->prev = nodeinsert; nodeinsert->next = nodeinsert; ptr->length++; return 0; } else { if (position == 0) { /* root->next->prev = nodeinsert; nodeinsert->prev = root->next->prev; nodeinsert->next = root->next; root->next->prev = nodeinsert;*/ nodeinsert->prev = root->next->prev; nodeinsert->next = root->next; root->next->prev->next = nodeinsert; root->next->prev = nodeinsert; root->next = nodeinsert; ptr->length++; return 0; } else { node* current = root->next; for (int i = 0; i < position; i++) { current = current->next; } nodeinsert->next = current; nodeinsert->prev = current->prev; current->prev->next = nodeinsert; //nodeinsert->next = nodeinsert; current->prev = nodeinsert; ptr->length++; return 0; } } } 删除一个元素，注意0位置上的

int doublelink::doublelink_erase(doublelink* ptr, int position) { if (ptr->doublelink_getlength(ptr) == 0) { cout<<"链表为空，oop！！"<<endl; return 0; } else { if (ptr->doublelink_getlength(ptr) == 1) { ptr->root->next = NULL; ptr->length--; } else { node* deletenode = root->next; for (int i = 0 ; i < position; i++) { deletenode = deletenode->next; } deletenode->prev->next = deletenode->next; deletenode->next->prev = deletenode->prev; delete deletenode; ptr->length--; } } } 完整实现代码和测试结果

#include <iostream> using namespace std; struct node { int date; node* prev; node* next; }; class doublelink { public: int doublelink_insert(doublelink* ptr,int position,int member); int doublelink_erase(doublelink* ptr, int position); void doublelink_display(doublelink* ptr, int num); int doublelink_getlength(doublelink* ptr); doublelink() { root = new node; root->prev = NULL; root->next = NULL; length = 0; } protected: private: int length; node* root; }; int doublelink::doublelink_erase(doublelink* ptr, int position) { if (ptr->doublelink_getlength(ptr) == 0) { cout<<"链表为空，oop！！"<<endl; return 0; } else { if (ptr->doublelink_getlength(ptr) == 1) { ptr->root->next = NULL; ptr->length--; } else { node* deletenode = root->next; for (int i = 0 ; i < position; i++) { deletenode = deletenode->next; } deletenode->prev->next = deletenode->next; deletenode->next->prev = deletenode->prev; delete deletenode; ptr->length--; } } } void doublelink::doublelink_display(doublelink* ptr, int num) { node* current = root->next; for (int i = 0; i < num; i++) { cout<<current->date<<" "; current = current->next; } cout<<endl; } int doublelink::doublelink_getlength(doublelink* ptr) { return ptr->length; } int doublelink::doublelink_insert(doublelink *ptr, int position, int member) { node* nodeinsert = new node; nodeinsert->date = member; if (ptr->doublelink_getlength(ptr) == 0) { root->next = nodeinsert; nodeinsert->prev = nodeinsert; nodeinsert->next = nodeinsert; ptr->length++; return 0; } else { if (position == 0) { /* root->next->prev = nodeinsert; nodeinsert->prev = root->next->prev; nodeinsert->next = root->next; root->next->prev = nodeinsert;*/ nodeinsert->prev = root->next->prev; nodeinsert->next = root->next; root->next->prev->next = nodeinsert; root->next->prev = nodeinsert; root->next = nodeinsert; ptr->length++; return 0; } else { node* current = root->next; for (int i = 0; i < position; i++) { current = current->next; } nodeinsert->next = current; nodeinsert->prev = current->prev; current->prev->next = nodeinsert; //nodeinsert->next = nodeinsert; current->prev = nodeinsert; ptr->length++; return 0; } } } int main() { doublelink* doublelink_ptr = new doublelink; for (int i = 0; i < 10; i++) { doublelink_ptr->doublelink_insert(doublelink_ptr,0,i); } doublelink_ptr->doublelink_display(doublelink_ptr,20); doublelink_ptr->doublelink_erase(doublelink_ptr,2); doublelink_ptr->doublelink_display(doublelink_ptr,20); return 0; }

测试正确~~

相关资源：敏捷开发V1.0.pptx