首页 > 代码库 > 双链表类模板
双链表类模板
双链表链表节点
ListNode.h
1 #include "stdafx.h" 2 #include <iostream> 3 using namespace std; 4 5 template <typename Type>class DoublyList; 6 template <typename Type> 7 // 节点信息 8 class ListNode{ 9 private:10 friend class DoublyList<Type>;11 ListNode():m_pprior(NULL),m_pnext(NULL){}12 ListNode(const Type item , ListNode<Type>*prior=NULL ,13 ListNode<Type>*next=NULL ):m_data(item),m_pprior(prior),m_pnext(next){14 }15 ~ListNode(){16 m_pnext = NULL;17 m_pprior = NULL;18 }19 public:20 Type getData(){return m_data;}21 private:22 Type m_data; // 节点数据23 ListNode *m_pprior; // 前驱24 ListNode *m_pnext; // 后继25 };
双链表链表类
DoublyList.h
1 #include "stdafx.h" 2 #include "ListNode.h" 3 template <typename Type> 4 5 // 双链表类 6 class DoublyList{ 7 public: 8 DoublyList():head(new ListNode<Type>()){ 9 head->m_pnext = head; 10 head->m_pprior = head; 11 } 12 ~DoublyList(){ 13 makeEmpty(); 14 delete head; 15 } 16 public: 17 void makeEmpty(); // 清空 18 int length(); // 长度 19 ListNode<Type>*find(int n =0); // 查找第n个元素 20 ListNode<Type>*findData(Type item); // 查找元素item 21 bool insert(Type item,int n=0); // 插入一个元素 ，默认是第一个元素 22 Type remove(int n =0); // 移除第n个元素 23 Type get(int n =0); // 获取第n个元素 24 void print(); // 打印双链表 25 private: 26 ListNode<Type> *head; 27 }; 28 template <typename Type> 29 void DoublyList<Type>::makeEmpty(){ 30 ListNode<Type>*pmove = head->m_pnext,*pdel; 31 while(pmove!=head){ 32 pdel = pmove; 33 pmove = pmove->m_pnext; 34 delete pdel; 35 } 36 head->m_pnext = head; 37 head->m_pprior = head; 38 } 39 template <typename Type> 40 int DoublyList<Type>::length(){ 41 ListNode<Type> *pmove = head->m_pnext; 42 int count = 0; 43 while(pmove!=head){ 44 count ++; 45 pmove = pmove->m_pnext; 46 } 47 48 /*ListNode<Type>*pprior = head->m_pprior; 49 ListNode<Type>*pnext = head->m_pnext; 50 while(1){ 51 if(pprior->m_pnext==pnext)break; 52 if(pprior==pnext&&pnext!=head){ 53 count++; 54 break; 55 } 56 count+=2; 57 pnext=pnext->m_pnext; 58 pprior=pprior->m_pprior; 59 }*/ 60 return count; 61 } 62 template <typename Type> 63 ListNode<Type>* DoublyList<Type>::find(int n){ 64 if(n<0){ 65 cout << "out of the boundary"<<endl; 66 return NULL; 67 } 68 ListNode<Type>*pmove=head->m_pnext; 69 for(int i = 0 ; i<n ;i++){ 70 pmove=pmove->m_pnext; 71 if(pmove==head){ 72 cout << "out of the boundary"<<endl; 73 return NULL; 74 } 75 } 76 return pmove; 77 } 78 template <typename Type> 79 ListNode<Type> *DoublyList<Type>::findData(Type item){ 80 ListNode<Type>*prior = head->m_pprior; 81 ListNode<Type>*next = head->m_pnext; 82 while(next->m_pnext!=prior&&prior!=next){ 83 if(prior->m_data=http://www.mamicode.com/=item)return prior; 84 if(next->m_data=http://www.mamicode.com/=item)return next; 85 prior = prior->m_pprior; 86 next = next->m_pnext; 87 } 88 cout<<"can‘t find the element"<<endl; 89 return NULL; 90 } 91 template <typename Type> 92 bool DoublyList<Type> ::insert(Type item ,int n){ 93 if(n<0){ 94 cout << "the n is illegal"<<endl; 95 return false; 96 } 97 ListNode<Type>*newNode = new ListNode<Type>(item); 98 ListNode<Type>*pmove = head; 99 for(int i = 0 ; i<n ;i++){100 pmove = pmove->m_pnext;101 if(pmove==head){102 cout << "the n is illegal"<<endl;103 return false;104 }105 }106 newNode->m_pnext = pmove->m_pnext;107 newNode->m_pprior = pmove;108 pmove->m_pnext = newNode;109 newNode->m_pnext->m_pprior = newNode;110 return true;111 }112 template <typename Type>113 Type DoublyList<Type>::remove(int n =0){114 if(n<0){115 cout<< "out of the boundary"<<endl;116 exit(0);117 }118 ListNode<Type>*pdel = find(n);119 if(pdel!=NULL){120 pdel->m_pprior->m_pnext = pdel->m_pnext;121 pdel->m_pnext->m_pprior = pdel->m_pprior;122 Type item = pdel->m_data;123 delete pdel;124 return item;125 }126 }127 template <typename Type>128 Type DoublyList<Type>::get(int n =0){129 if(n<0){130 cout << "out of the boundary"<<endl;131 exit(0);132 }133 ListNode<Type>*pmove = head;134 for(int i = 0 ; i <n ; i++){135 pmove = pmove->m_pnext;136 if(pmove==head){137 cout << "out of the boundary"<<endl;138 exit(0);139 }140 }141 return pmove->m_data;142 }143 template<typename Type>144 void DoublyList<Type>::print(){145 ListNode<Type>*pmove = head->m_pnext;146 cout << "head";147 while(pmove!=head){148 cout << "->" << pmove->m_data;149 pmove= pmove->m_pnext;150 }151 cout << endl <<endl;152 }
测试：
1 #include "stdafx.h" 2 #include "DoublyList.h" 3 4 int _tmain(int argc, _TCHAR* argv[]) 5 { 6 DoublyList<int>list; 7 for(int i = 0 ; i<10 ;i++){ 8 list.insert(i*i,i); 9 }10 list.print();11 cout << list.length() << endl;12 list.remove(0);13 list.print();14 list.remove(list.length()-1);15 list.print();16 return 0;17 }
双链表类模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。