用C++完成的双链表源代码.zip_双链表

// LinkList.cc // author: Ke Song based C source from pp Sister XiuJie Chen ;) // http://kesongemini.diy.163.com #include "stdafx.h" #include <iostream.h> #include <stdlib.h> // exit #include "LinkList.h" void LinkList_T:: init( void ) { _top = (LinkListNode_T *)this; _bottom = (LinkListNode_T *)this; _current= (LinkListNode_T *)this; } void LinkList_T:: prepend( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("prepend: new failed"); } else { pNode->prev = (LinkListNode_T *)this; pNode->next = _top; if( _bottom == (LinkListNode_T *) this ) _bottom = pNode; _top->prev = pNode; _top = pNode; // I don't want bearing operands' order in mind // So don't use " A = B = C " pNode->contents = contents; } } void LinkList_T:: append( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("append: new failed"); } else { pNode->prev = _bottom; pNode->next = (LinkListNode_T *)this; if (_top == (LinkListNode_T *)this) _top = pNode ; _bottom->next = pNode; _bottom = pNode; pNode->contents = contents; } } CONTENTS LinkList_T:: deleteFirst( void ) { LinkListNode_T *pNode = _top; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _top = pNode->next; _top->prev = (LinkListNode_T *)this; if (_current == pNode) _current = pNode->next; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } CONTENTS LinkList_T:: deleteLast( void ) { LinkListNode_T *pNode = _bottom; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _bottom = pNode->prev; _bottom->next = (LinkListNode_T *)this; if (_current == pNode) _current = pNode->prev; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } CONTENTS LinkList_T:: deleteCurrent( void ) { LinkListNode_T *pNode = _current; CONTENTS contents; if (pNode == (LinkListNode_T *)this) return ((CONTENTS)NULL); _current = pNode->next; pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; contents = pNode->contents; delete pNode; pNode = NULL; return contents; } void LinkList_T:: append2current( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("append2Current: new failed"); } else { pNode->prev = _current; pNode->next = _current->next; pNode->contents = contents; _current->next->prev = pNode; _current->next = pNode; } } void LinkList_T:: prepend2current( CONTENTS contents ) { LinkListNode_T *pNode = new LinkListNode_T; if (pNode == NULL) { panic("prepend2Current: new failed"); } else { pNode->prev = _current->prev; pNode->next = _current; pNode->contents = contents; _current->prev->next = pNode; _current->prev = pNode; } } void LinkList_T:: deleteAll( void ) { while (!isEmpty()) deleteFirst(); } void LinkList_T:: freeAll( void ) { while (!isEmpty()) delete deleteFirst(); } void LinkList_T:: freeCurrent( void ) { delete deleteCurrent(); } bool LinkList_T:: freeMatch ( CONTENTS contents ) { LinkListNode_T *pNode; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next) { if (pNode->contents == contents) { freeNode(pNode); return true; } } return false; } LinkListNode_T* LinkList_T:: findMatch(CONTENTS contents) { LinkListNode_T *pNode; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next) { if (pNode->contents == contents) return pNode; } return (LinkListNode_T *)NULL; } int LinkList_T:: index ( CONTENTS contents ) { LinkListNode_T *pNode; int index = 0; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next, index++) { if (pNode->contents == contents) return index; } return -1; } CONTENTS LinkList_T:: contents( int index ) { LinkListNode_T *pNode; int count = 0; for(pNode = _top; pNode != (LinkListNode_T *)this; pNode = pNode->next, count++) { if (count == index) return pNode->contents; } return (CONTENTS)NULL; // (CONTENTS)-1 //old } void LinkList_T:: freeNode(LinkListNode_T *pNode) { delete deleteNode(pNode); } CONTENTS LinkList_T:: deleteNode(LinkListNode_T *pNode) { CONTENTS contents; if (pNode == (LinkListNode_T *)this) { return ((CONTENTS)NULL); } else if (pNode == _current) { return deleteCurrent(); } else { pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; contents = pNode->contents; delete pNode; return contents; } } void LinkList_T:: panic ( char *s ) //static { cout<<s<<endl; exit(1); }