目 录 目 录 1 1、顺序表 1 Seqlist.h 1 Test.cpp 7 单链表 9 ListNode.h 9 SingleList.h 11 test.cpp 22 双向链表 25 NodeList.h 25 DoubleList.h 27 Test.cpp 37 循环链表 40 ListNode.h 40 CircularList.h 41 Test.cpp 52 顺序栈 55 SeqStack.h 55 Test.cpp 60 链式栈 61 StackNode.h 62 LinkStack.h 63 Test.cpp 67 7.顺序队列 69 SeqQueue.h 69 Test.cpp 75 8、链式队列 77 QueueNode.h 77 LinkQueue.h 78 Test.cpp 83 9、优先级队列 85 QueueNode.h 85 Compare.h 86 PriorityQueue.h 88 Test.cpp 94 10、串 97 MyString.h 97 MyString.cpp 100 test.cpp 114 11、二叉树 117 BinTreeNode.h 117 BinaryTree.h 125 Test.cpp 138 12、线索二叉树 141 ThreadNode.h 141 ThreadTree.h 143 ThreadInorderIterator.h 143 test.cpp 155 13、堆 157 MinHeap.h 157 test.cpp 165 14、哈夫曼树 166 BinTreeNode.h 166 BinaryTree.h 169 MinHeap.h 174 Huffman.h 180 Test.cpp 182 15、树 183 QueueNode.h 183 LinkQueue.h 184 TreeNode.h 189 Tree.h 190 test.cpp 208 16、B+树 210 BTreeNode.h 211 BTree.h 215 test.cpp 239 17、图 242 MinHeap.h 242 Edge.h 247 Vertex.h 248 Graph.h 250 test.cpp 275 18、排序 278 Data.h 278 QueueNode.h 285 LinkQueue.h 289 Sort.h 294 test.cpp 310 数据结构算法实现 2008-9-3 1、顺序表 Seqlist.h const int DefaultSize=100; template class SeqList{ public: SeqList(int sz=DefaultSize) :m_nmaxsize(sz),m_ncurrentsize(-1){ if(sz>0){ m_elements=new Type[m_nmaxsize]; } } ~SeqList(){ 数据结构算法实现 2008-9-3 delete[] m_elements; } int Length() const{ //get the length return m_ncurrentsize+1; } int Find(Type x) const; //find the position of x int IsElement(Type x) const; //is it in the list int Insert(Type x,int i); //insert data int Remove(Type x); //delete data int IsEmpty(){ return m_ncurrentsize==-1; } int IsFull(){ return m_ncurrentsize==m_nmaxsize-1; } 数据结构算法实现 2008-9-3 Type Get(int i){ //get the ith data return i<0||i>m_ncurrentsize?(cout<<"can't find the element"< int SeqList::Find(Type x) const{ for(int i=0;i int SeqList::IsElement(Type x) const{ if(Find(x)==-1) return 0; return 1; } template int SeqList::Insert(Type x, int i){ if(i<0||i>m_ncurrentsize+1||m_ncurrentsize==m_nmaxsize-1){ cout<<"the operate is illegal"<i;j--){ m_elements[j]=m_elements[j-1]; } m_elements[i]=x; return 1; } template int SeqList::Remove(Type x){ int size=m_ncurrentsize; for(int i=0;i void SeqList::Print(){ for(int i=0;i<=m_ncurrentsize;i++) cout< #include "SeqList.h" using namespace std; int main() { SeqList test(15); int array[15]={2,5,8,1,9,9,7,6,4,3,2,9,7,7,9}; 数据结构算法实现 2008-9-3 for(int i=0;i<15;i++){ test.Insert(array[i],0); } test.Insert(1,0); cout<<(test.Find(0)?"can't be found ":"Be found ")<< 0 << endl< class SingleList; template class ListNode{ private: friend typename SingleList; ListNode():m_pnext(NULL){} ListNode(const Type item,ListNode *next=NULL):m_data(item),m_pnext(next){} ~ListNode(){ m_pnext=NULL; } public: 数据结构算法实现 2008-9-3 Type GetData(); friend ostream& operator<< (ostream& ,ListNode&); private: Type m_data; ListNode *m_pnext; }; template Type ListNode::GetData(){ return this->m_data; } template ostream& operator<<(ostream& os,ListNode& out){ os< class SingleList{ public: SingleList():head(new ListNode()){} ~SingleList(){ MakeEmpty(); delete head; } 数据结构算法实现 2008-9-3 public: void MakeEmpty(); //make the list empty int Length(); //get the length ListNode *Find(Type value,int n); //find thd nth data which is equal to value ListNode *Find(int n); //find the nth data bool Insert(Type item,int n=0); //insert the data in the nth position Type Remove(int n=0); //remove the nth data bool RemoveAll(Type item); //remove all the data which is equal to item Type Get(int n); //get the nth data void Print(); //print the list private: ListNode *head; }; 数据结构算法实现 2008-9-3 template void SingleList::MakeEmpty(){ ListNode *pdel; while(head->m_pnext!=NULL){ pdel=head->m_pnext; head->m_pnext=pdel->m_pnext; delete pdel; } } template int SingleList::Length(){ ListNode *pmove=head->m_pnext; int count=0; while(pmove!=NULL){ pmove=pmove->m_pnext; 数据结构算法实现 2008-9-3 count++; } return count; } template ListNode* SingleList::Find(int n){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head->m_pnext; for(int i=0;im_pnext; } if(pmove==NULL){ 数据结构算法实现 2008-9-3 cout<<"The n is out of boundary"< ListNode* SingleList::Find(Type value,int n){ if(n<1){ cout<<"The n is illegal"< *pmove=head; int count=0; while(count!=n&&pmove){ pmove=pmove->m_pnext; 数据结构算法实现 2008-9-3 if(pmove->m_data==value){ count++; } } if(pmove==NULL){ cout<<"can't find the element"< bool SingleList::Insert(Type item, int n){ if(n<0){ cout<<"The n is illegal"< *pmove=head; ListNode *pnode=new ListNode(item); if(pnode==NULL){ cout<<"Application error!"<m_pnext; } if(pmove==NULL){ cout<<"the n is illegal"<m_pnext=pmove->m_pnext; pmove->m_pnext=pnode; return 1; } template bool SingleList::RemoveAll(Type item){ ListNode *pmove=head; ListNode *pdel=head->m_pnext; while(pdel!=NULL){ if(pdel->m_data==item){ pmove->m_pnext=pdel->m_pnext; delete pdel; pdel=pmove->m_pnext; continue; } 数据结构算法实现 2008-9-3 pmove=pmove->m_pnext; pdel=pdel->m_pnext; } return 1; } template Type SingleList::Remove(int n){ if(n<0){ cout<<"can't find the element"< *pmove=head,*pdel; for(int i=0;im_pnext;i++){ pmove=pmove->m_pnext; } 数据结构算法实现 2008-9-3 if(pmove->m_pnext==NULL){ cout<<"can't find the element"<m_pnext; pmove->m_pnext=pdel->m_pnext; Type temp=pdel->m_data; delete pdel; return temp; } template Type SingleList::Get(int n){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head->m_pnext; for(int i=0;im_pnext; if(NULL==pmove){ cout<<"The n is out of boundary"<m_data; } template void SingleList::Print(){ ListNode *pmove=head->m_pnext; cout<<"head"; 数据结构算法实现 2008-9-3 while(pmove){ cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->over"< using namespace std; #include "SingleList.h" 数据结构算法实现 2008-9-3 int main() { SingleList list; for(int i=0;i<20;i++){ list.Insert(i*3,i); } for(int i=0;i<5;i++){ list.Insert(3,i*3); } cout<<"the Length of the list is "< class DoublyList; template class ListNode{ private: friend class DoublyList; ListNode():m_pprior(NULL),m_pnext(NULL){} ListNode(const Type item,ListNode *prior=NULL,ListNode *next=NULL) :m_data(item),m_pprior(prior),m_pnext(next){} 数据结构算法实现 2008-9-3 ~ListNode(){ m_pprior=NULL; m_pnext=NULL; } public: Type GetData(); private: Type m_data; ListNode *m_pprior; ListNode *m_pnext; }; template Type ListNode::GetData(){ return this->m_data; } 数据结构算法实现 2008-9-3 DoubleList.h #include "ListNode.h" template class DoublyList{ public: DoublyList():head(new ListNode()){ //the head node point to itself head->m_pprior=head; head->m_pnext=head; } ~DoublyList(){ MakeEmpty(); delete head; } 数据结构算法实现 2008-9-3 public: void MakeEmpty(); //make the list empty int Length(); //get the length of the list ListNode *Find(int n=0); //find the nth data ListNode * FindData(Type item); //find the data which is equal to item bool Insert(Type item,int n=0); //insert item in the nth data Type Remove(int n=0); //delete the nth data Type Get(int n=0); //get the nth data void Print(); //print the list private: ListNode *head; }; 数据结构算法实现 2008-9-3 template void DoublyList::MakeEmpty(){ ListNode *pmove=head->m_pnext,*pdel; while(pmove!=head){ pdel=pmove; pmove=pdel->m_pnext; delete pdel; } head->m_pnext=head; head->m_pprior=head; } template int DoublyList::Length(){ ListNode *pprior=head->m_pprior,*pnext=head->m_pnext; int count=0; while(1){ 数据结构算法实现 2008-9-3 if(pprior->m_pnext==pnext){ break; } if(pprior==pnext&&pprior!=head){ count++; break; } count+=2; pprior=pprior->m_pprior; pnext=pnext->m_pnext; } return count; } template ListNode* DoublyList::Find(int n = 0){ 数据结构算法实现 2008-9-3 if(n<0){ cout<<"The n is out of boundary"< *pmove=head->m_pnext; for(int i=0;im_pnext; if(pmove==head){ cout<<"The n is out of boundary"< bool DoublyList::Insert(Type item,int n){ if(n<0){ cout<<"The n is out of boundary"< *newnode=new ListNode(item),*pmove=head; if(newnode==NULL){ cout<<"Application Erorr!"<m_pnext; if(pmove==head){ cout<<"The n is out of boundary"<m_pnext=pmove->m_pnext; newnode->m_pprior=pmove; pmove->m_pnext=newnode; newnode->m_pnext->m_pprior=newnode; return 1; } template Type DoublyList::Remove(int n = 0){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head,*pdel; for(int i=0;im_pnext; if(pmove==head){ cout<<"The n is out of boundary"<m_pprior->m_pnext=pdel->m_pnext; pmove->m_pnext->m_pprior=pdel->m_pprior; Type temp=pdel->m_data; 数据结构算法实现 2008-9-3 delete pdel; return temp; } template Type DoublyList::Get(int n = 0){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head; for(int i=0;im_pnext; if(pmove==head){ cout<<"The n is out of boundary"<m_data; } template void DoublyList::Print(){ ListNode *pmove=head->m_pnext; cout<<"head"; while(pmove!=head){ cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->over"< ListNode* DoublyList::FindData(Type item){ ListNode *pprior=head->m_pprior,*pnext=head->m_pnext; while(pprior->m_pnext!=pnext && pprior!=pnext){ //find the data in the two direction if(pprior->m_data==item){ return pprior; } if(pnext->m_data==item){ return pnext; } pprior=pprior->m_pprior; pnext=pnext->m_pnext; } cout<<"can't find the element"< #include "DoublyList.h" using namespace std; int main() { DoublyList list; for(int i=0;i<20;i++){ list.Insert(i*3,i); } 数据结构算法实现 2008-9-3 cout<<"the Length of the list is "<GetData()< class CircularList; 数据结构算法实现 2008-9-3 template class ListNode{ private: friend class CircularList; ListNode():m_pnext(NULL){} ListNode(const Type item,ListNode *next=NULL):m_data(item),m_pnext(next){} ~ListNode(){ m_pnext=NULL; } private: Type m_data; ListNode *m_pnext; }; 数据结构算法实现 2008-9-3 CircularList.h #include "ListNode.h" template class CircularList{ public: CircularList():head(new ListNode()){ head->m_pnext=head; } ~CircularList(){ MakeEmpty(); delete head; } public: void MakeEmpty(); //clear the list 数据结构算法实现 2008-9-3 int Length(); //get the length ListNode *Find(Type value,int n); //find the nth data which is equal to value ListNode *Find(int n); //find the nth data bool Insert(Type item,int n=0); //insert the data into the nth data of the list Type Remove(int n=0); //delete the nth data bool RemoveAll(Type item); //delete all the datas which are equal to value Type Get(int n); //get the nth data void Print(); //print the list private: ListNode *head; }; template void CircularList::MakeEmpty(){ 数据结构算法实现 2008-9-3 ListNode *pdel,*pmove=head; while(pmove->m_pnext!=head){ pdel=pmove->m_pnext; pmove->m_pnext=pdel->m_pnext; delete pdel; } } template int CircularList::Length(){ ListNode *pmove=head; int count=0; while(pmove->m_pnext!=head){ pmove=pmove->m_pnext; count++; } 数据结构算法实现 2008-9-3 return count; } template ListNode* CircularList::Find(int n){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head->m_pnext; for(int i=0;im_pnext; } if(pmove==head){ cout<<"The n is out of boundary"< ListNode* CircularList::Find(Type value,int n){ if(n<1){ cout<<"The n is illegal"< *pmove=head; int count=0; while(count!=n){ pmove=pmove->m_pnext; if(pmove->m_data==value){ count++; 数据结构算法实现 2008-9-3 } if(pmove==head){ cout<<"can't find the element"< bool CircularList::Insert(Type item, int n){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head; 数据结构算法实现 2008-9-3 ListNode *pnode=new ListNode(item); if(pnode==NULL){ cout<<"Application error!"<m_pnext; if(pmove==head){ cout<<"The n is out of boundary"<m_pnext=pmove->m_pnext; pmove->m_pnext=pnode; 数据结构算法实现 2008-9-3 return 1; } template bool CircularList::RemoveAll(Type item){ ListNode *pmove=head; ListNode *pdel=head->m_pnext; while(pdel!=head){ if(pdel->m_data==item){ pmove->m_pnext=pdel->m_pnext; delete pdel; pdel=pmove->m_pnext; continue; } pmove=pmove->m_pnext; pdel=pdel->m_pnext; 数据结构算法实现 2008-9-3 } return 1; } template Type CircularList::Remove(int n){ if(n<0){ cout<<"can't find the element"< *pmove=head,*pdel; for(int i=0;im_pnext!=head;i++){ pmove=pmove->m_pnext; } if(pmove->m_pnext==head){ cout<<"can't find the element"<m_pnext; pmove->m_pnext=pdel->m_pnext; Type temp=pdel->m_data; delete pdel; return temp; } template Type CircularList::Get(int n){ if(n<0){ cout<<"The n is out of boundary"< *pmove=head->m_pnext; 数据结构算法实现 2008-9-3 for(int i=0;im_pnext; if(pmove==head){ cout<<"The n is out of boundary"<m_data; } template void CircularList::Print(){ ListNode *pmove=head->m_pnext; cout<<"head"; while(pmove!=head){ cout<<"--->"<m_data; 数据结构算法实现 2008-9-3 pmove=pmove->m_pnext; } cout<<"--->over"< #include "CircularList.h" using namespace std; int main() { CircularList list; 数据结构算法实现 2008-9-3 for(int i=0;i<20;i++){ list.Insert(i*3,i); } cout<<"the Length of the list is "< class SeqStack{ public: SeqStack(int sz):m_ntop(-1),m_nMaxSize(sz){ m_pelements=new Type[sz]; if(m_pelements==NULL){ cout<<"Application Error!"< void SeqStack::Push(const Type item){ if(IsFull()){ cout<<"The stack is full!"< Type SeqStack::Pop(){ if(IsEmpty()){ cout<<"There is no element!"< Type SeqStack::GetTop() const{ if(IsEmpty()){ cout<<"There is no element!"< void SeqStack::Print(){ cout<<"bottom"; for(int i=0;i<=m_ntop;i++){ cout<<"--->"<top"< using namespace std; #include "SeqStack.h" int main(){ SeqStack stack(10); int init[10]={1,2,6,9,0,3,8,7,5,4}; for(int i=0;i<10;i++){ stack.Push(init[i]); } stack.Print(); 数据结构算法实现 2008-9-3 stack.Push(88); cout< class LinkStack; template class StackNode{ private: friend class LinkStack; StackNode(Type dt,StackNode *next=NULL):m_data(dt),m_pnext(next){} private: Type m_data; StackNode *m_pnext; }; 数据结构算法实现 2008-9-3 LinkStack.h #include "StackNode.h" template class LinkStack{ public: LinkStack():m_ptop(NULL){} ~LinkStack(){ MakeEmpty(); } public: void MakeEmpty(); //make the stack empty void Push(const Type item); //push the data Type Pop(); //pop the data 数据结构算法实现 2008-9-3 Type GetTop() const; //get the data void Print(); //print the stack bool IsEmpty() const{ return m_ptop==NULL; } private: StackNode *m_ptop; }; template void LinkStack::MakeEmpty(){ StackNode *pmove; while(m_ptop!=NULL){ pmove=m_ptop; 数据结构算法实现 2008-9-3 m_ptop=m_ptop->m_pnext; delete pmove; } } template void LinkStack::Push(const Type item){ m_ptop=new StackNode(item,m_ptop); } template Type LinkStack::GetTop() const{ if(IsEmpty()){ cout<<"There is no elements!"<m_data; 数据结构算法实现 2008-9-3 } template Type LinkStack::Pop(){ if(IsEmpty()){ cout<<"There is no elements!"< *pdel=m_ptop; m_ptop=m_ptop->m_pnext; Type temp=pdel->m_data; delete pdel; return temp; } template void LinkStack::Print(){ 数据结构算法实现 2008-9-3 StackNode *pmove=m_ptop; cout<<"buttom"; while(pmove!=NULL){ cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->top"< using namespace std; 数据结构算法实现 2008-9-3 #include "LinkStack.h" int main(){ LinkStack stack; int init[10]={1,3,5,7,4,2,8,0,6,9}; for(int i=0;i<10;i++){ stack.Push(init[i]); } stack.Print(); cout< class SeqQueue{ public: SeqQueue(int sz):m_nrear(0),m_nfront(0),m_ncount(0),m_nMaxSize(sz){ m_pelements=new Type[sz]; if(m_pelements==NULL){ cout<<"Application Error!"< void SeqQueue::MakeEmpty(){ this->m_ncount=0; this->m_nfront=0; this->m_nrear=0; } template bool SeqQueue::IsEmpty(){ return m_ncount==0; } template bool SeqQueue::IsFull(){ return m_ncount==m_nMaxSize; } 数据结构算法实现 2008-9-3 template bool SeqQueue::Append(const Type item){ if(IsFull()){ cout<<"The queue is full!"< Type SeqQueue::Delete(){ if(IsEmpty()){ cout<<"There is no element!"< Type SeqQueue::Get(){ if(IsEmpty()){ cout<<"There is no element!"< void SeqQueue::Print(){ cout<<"front"; for(int i=0;i"<rear"< using namespace std; #include "SeqQueue.h" 数据结构算法实现 2008-9-3 int main(){ SeqQueue queue(10); int init[10]={1,6,9,0,2,5,8,3,7,4}; for(int i=0;i<5;i++){ queue.Append(init[i]); } queue.Print(); cout< class LinkQueue; template class QueueNode{ private: friend class LinkQueue; QueueNode(const Type item,QueueNode *next=NULL) :m_data(item),m_pnext(next){} private: Type m_data; QueueNode *m_pnext; }; 数据结构算法实现 2008-9-3 LinkQueue.h #include "QueueNode.h" template class LinkQueue{ public: LinkQueue():m_prear(NULL),m_pfront(NULL){} ~LinkQueue(){ MakeEmpty(); } void Append(const Type item); //insert data Type Delete(); //delete data Type GetFront(); //get data void MakeEmpty(); //make the queue empty void Print(); //print the queue 数据结构算法实现 2008-9-3 bool IsEmpty() const{ return m_pfront==NULL; } private: QueueNode *m_prear,*m_pfront; }; template void LinkQueue::MakeEmpty(){ QueueNode *pdel; while(m_pfront){ pdel=m_pfront; m_pfront=m_pfront->m_pnext; delete pdel; 数据结构算法实现 2008-9-3 } } template void LinkQueue::Append(const Type item){ if(m_pfront==NULL){ m_pfront=m_prear=new QueueNode(item); } else{ m_prear=m_prear->m_pnext=new QueueNode(item); } } template Type LinkQueue::Delete(){ if(IsEmpty()){ cout<<"There is no element!"< *pdel=m_pfront; Type temp=m_pfront->m_data; m_pfront=m_pfront->m_pnext; delete pdel; return temp; } template Type LinkQueue::GetFront(){ if(IsEmpty()){ cout<<"There is no element!"<m_data; 数据结构算法实现 2008-9-3 } template void LinkQueue::Print(){ QueueNode *pmove=m_pfront; cout<<"front"; while(pmove){ cout<<"--->"<