12种常用数据结构 无向图 有向图 （邻接链表实现） 链表 环链表 最小堆 栈 最小生成树 栈 UFSets集合

#include <iostream> #include <string> #include <stdlib.h> template <class Type> class List; template <class Type> class ListNode { friend class List <Type>; public: ListNode ( ); ListNode ( const Type& item ); Type data; ListNode<Type> *link; }; template <class Type> class List { public: List() { first=last=NULL; } List ( const Type & value ) { first = new ListNode<Type>( value ); last=first; } ~List ( ); void MakeEmpty ( ); int Length ( ) const; ListNode<Type> *Find ( int i ); int Insert ( Type value, int i ); int Append ( Type value ); int Append ( ListNode<Type>* node); Type Remove ( int i ); ListNode<Type>* Cut(int i); Type Get ( int i ); int GetPosition(Type value); void Print(); ListNode<Type>* first; ListNode<Type>* last; }; template <class Type> ListNode<Type> :: ListNode ( ) : link (NULL) { } template <class Type> ListNode<Type>::ListNode( const Type& item ) :data (item), link (NULL) { } template <class Type> List<Type> :: ~List ( ) { MakeEmpty ( ); //delete first; } template <class Type> void List<Type> :: MakeEmpty ( ) { ListNode<Type> *q; while ( first != NULL ) { q = first; first= q->link; delete q; } last=NULL; } template <class Type> int List<Type>::Length ( ) const { ListNode<Type> *p = first; int count = 0; while ( p != NULL ) { p = p->link; count++; } return count; } template <class Type> ListNode<Type> *List<Type> :: Find ( int i ) { if ( i < 1 ) return NULL; if (i>Length()) return NULL; ListNode<Type> *p = first; int j = 1; while ( p != NULL && j < i ) { p = p->link; j = j++; } return p; } template <class Type> int List<Type> :: Insert ( Type value, int i ) { ListNode<Type> *p = Find ( i-1 ); if ( p == NULL ) return 0; if (p==last) { return Append(value); } else { ListNode<Type> *newnode = new ListNode<Type> (value); newnode->link=p->link; p->link = newnode; return 1; } } template <class Type> int List<Type> :: Append ( Type value ) { ListNode<Type> *newnode = new ListNode<Type> ( value); if (last==NULL && first==NULL) { first=newnode; last=newnode; } else { last->link= newnode; last=newnode; } return 1; } template <class Type> Type List<Type>::Remove ( int i ) { ListNode<Type> *q; if (i==1) { q=first; first=first->link; Type value =q->data; delete q; return value; } else { ListNode<Type> *p = Find (i-1); if ( p == NULL || p==last) return NULL; q = p->link; p->link = q->link; Type value =q->data; if ( q == last ) last = p; delete q; return value; } } template <class Type> Type List<Type>::Get ( int i ) { ListNode<Type> *p = Find ( i ); if ( p == NULL ) return NULL; else return p->data; } template <class Type> int List<Type>::Append(ListNode<Type> *node) { if (node==NULL) return 0; if (last==NULL && first==NULL) { first=node; last=node; node->link=NULL; } else { last->link=node; node->link=NULL; last=node; } return 1; } template <class Type> ListNode<Type> * List<Type>::Cut(int i) { if (i>Length() || i<1) return NULL; if(i==1) { ListNode<Type>* temp=first; first=first->link; return temp; } ListNode<Type> *p = Find ( i-1 ); ListNode<Type> *q=p->link; p->link=q->link; if (q==last) { last=p; } return q; } template <class Type> void List<Type>::Print() { ListNode<Type>* temp=first; while (temp!=NULL) { cout<<temp->data<<endl; temp=temp->link; } } template <class Type> int List<Type>::GetPosition(Type value) { ListNode<Type>* temp=first; int i=1; bool flag=false; while (temp!=NULL) { if (temp->data==value) { flag=true; break; } else { temp=temp->link; i++; } } if (flag==true) { return i; } else { return -1; } }