链表--单链表
线性链表用节点中的指针域表示数据元素之间的逻辑关系,这样逻辑上相邻的两个元素就不要求物理位置也相邻.
LinkList.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | //节点类 template<class ElemType> struct Node{ ElemType data; Node<ElemType>* next; Node(); Node<ElemType Item,Node<ElemType>* link=NULL); }; //线性链表类 template<class ElemType> class LinkList{ protected: Node<ElemType>* head; Node<ElemType>* GetElemPtr(int position) const; Init(); public: LinkList(); ~LinkList(); int Length() const; bool Empty() const; void Clear(); void Traverse(void(*visit)(ElemType&)); Status_code GetElem(int position,ElemType& e) const; Status_code SetElem(int const position,ElemType& e); Status_code Delete(int position,ElemType& e); Status_code Insert(int position,const ElemType& e); LinkList(const LinkList& rhs);
}; |
LinkList.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | template<class ElemType> Node<ElemType>* LinkList<ElemType>::GetElemPtr(int position) const{ Node<ElemType>* tmpPtr=head; int curPt=0; while(tempPtr!=NULL) { tempPtr=tempPtr->next; curPt++; if(curPt==position) return tempPtr; } return null; } template<class ElemType> Node<ElemType>::Node() { next=NULL; } Node<ElemType>::Node<ElemType item,Node<ElemType>* link) { data=item; next=link; } template<class ElemType> void LinkLost<ElemType>::Init(); { head=new Node<ElemType>; } template<class ElemType> void LinkList<ElemType>::LinkList() { Init(); } template<class ElemType> void LinkList<ElemType>::~LinkList() { Clear(); delete head; } template<class ElemType> int LinkList<ElemType>::Length() const{ int count; for(Node<ElemType>* tmp=head->next;tmp!=NULL;tmp=tmp->next){ count++; } return count; } template<class ElemType> bool LinkList<ElemTye>::Empty() const{ return head->next==NULL; } template<class ElemType> void LinkList<ElenType>::Clear() { ElemType tmp; while(Length()>0) Delete(1,tmp); } template<class ElemType> void LinkList<ElemType>::Traverse(coid(*visit)(ElemType&)) { for(Node<ElemType>* tmp=head->next;tmp!=NULL;tmp=temp->next) (*visit)(tmp->data); } template<class ElemType> Status_Code LinkList<ElemType>::GetElem(int position,ElemTypr& e) const{ if(position<1||position>Length()) return RANGE_ERROR; else { e=GetElemPtr(position)->data; return ENTRY_FOUND; } } template<class ElemType> Status_Code LinkList<ElemType>::SetElem(int position,ElemType& e) { if(position<1||position>Length()) return RANGE_ERROR; else { GetElemPtr(position)->data=e; return SUCCESS; } } template<class ElemType> void LinkList<ElemType>::Insert(int position,ElemType& e) { if(position<1||position>Length()) return RANGE_ERROR; else { Node<ElemType>* temp; temp=GetElemPtr(position-1); Node<ElemType>* tempNode; tempNode=new Node<ElemType>(e,temp->next); temp->next=tempNode; return SUCCESS; } } template<class ElemType> void LinkList<ElemType>::Delete(int position,ElemType& e) { if(position<1||position>Length()) return RANGE_ERROR; else { Node<ElemType>* temp=GetElemPtr(position-1); Node<ElemType>* tempNext=temp->next; temp->next=tempNext->next; e=tempNext->data; delete tempnext; return SUCCESS; } } |