数据结构C++算法

p6dp

贡献于2014-04-26

字数:89577 关键词: C/C++开发 C/C++

目 录 目 录 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<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->rear"< 数据结构算法实现 2008-9-3 using namespace std; #include "LinkQueue.h" int main(){ LinkQueue queue; int init[10]={1,3,6,8,9,2,0,5,4,7}; for(int i=0;i<10;i++){ queue.Append(init[i]); } queue.Print(); queue.Delete(); 数据结构算法实现 2008-9-3 queue.Print(); cout< class PriorityQueue; template class QueueNode{ private: friend class PriorityQueue; QueueNode(const Type item,QueueNode *next=NULL) :m_data(item),m_pnext(next){} private: Type m_data; QueueNode *m_pnext; }; 数据结构算法实现 2008-9-3 Compare.h template class Compare{ //处理一般比较大小 public: static bool lt(Type item1,Type item2); }; template bool Compare::lt(Type item1, Type item2){ return item1 class PriorityQueue{ //Cmp is Designed for compare public: PriorityQueue():m_prear(NULL),m_pfront(NULL){} ~PriorityQueue(){ MakeEmpty(); } void MakeEmpty(); //make the queue empty void Append(const Type item); //insert data 数据结构算法实现 2008-9-3 Type Delete(); //delete data Type GetFront(); //get data void Print(); //print the queue bool IsEmpty() const{ return m_pfront==NULL; } private: QueueNode *m_prear,*m_pfront; }; template void PriorityQueue::MakeEmpty(){ QueueNode *pdel; 数据结构算法实现 2008-9-3 while(m_pfront){ pdel=m_pfront; m_pfront=m_pfront->m_pnext; delete pdel; } } template void PriorityQueue::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); } } 数据结构算法实现 2008-9-3 template Type PriorityQueue::Delete(){ if(IsEmpty()){ cout<<"There is no elements!"< *pdel=m_pfront,*pmove=m_pfront; while(pmove->m_pnext){ //get the minimize priority's data //cmp:: lt is used for compare the two data, if the front one // is less than the back, then return 1 if(Cmp::lt(pmove->m_pnext->m_data,pdel->m_pnext->m_data)){ pdel=pmove; } pmove=pmove->m_pnext; 数据结构算法实现 2008-9-3 } pmove=pdel; pdel=pdel->m_pnext; pmove->m_pnext=pdel->m_pnext; Type temp=pdel->m_data; delete pdel; return temp; } template Type PriorityQueue::GetFront(){ if(IsEmpty()){ cout<<"There is no elements!"< *pdel=m_pfront,*pmove=m_pfront->m_pnext; while(pmove){ //get the minimize priority's data if(Cmp::lt(pmove->m_data,pdel->m_data)){ pdel=pmove; } pmove=pmove->m_pnext; } return pdel->m_data; } template void PriorityQueue::Print(){ QueueNode *pmove=m_pfront; cout<<"front"; while(pmove){ 数据结构算法实现 2008-9-3 cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->rear"< #include using namespace std; #include "PriorityQueue.h" 数据结构算法实现 2008-9-3 int main(){ PriorityQueue > queue; int init[10]={1,9,3,5,0,8,2,4,6,7}; for(int i=0;i<10;i++){ queue.Append(init[i]); } queue.Print(); queue.Delete(); queue.Print(); system("pause"); system("cls"); 数据结构算法实现 2008-9-3 PriorityQueue spe_queue; int init2[5][2]={{34,2},{64,1},{18,3},{24,2},{55,4}}; SpecialData data[5]; for(int i=0;i<5;i++){ data[i].m_npir=init2[i][1]; data[i].m_ntenor=init2[i][0]; } for(int i=0;i<5;i++){ spe_queue.Append(data[i]); } spe_queue.Print(); cout<(const CMyString cmp_str) const; bool operator!() const{ return m_ncurlen==0; } CMyString& operator=(const CMyString ©); CMyString& operator+=(const CMyString &add); char& operator[](int i); friend ostream& operator<<(ostream& ,CMyString&); friend istream& operator>>(istream& ,CMyString&); private: void Next(); private: int m_ncurlen; char *m_pstr; 数据结构算法实现 2008-9-3 int *m_pnext; }; MyString.cpp #include #include using namespace std; #include "MyString.h" CMyString::CMyString(){ //create empty string 数据结构算法实现 2008-9-3 m_pstr=new char[MAXSIZE+1]; if(!m_pstr){ cerr<<"Allocation Error"<m_ncurlen=0; m_pstr[0]='\0'; } CMyString::CMyString(const char *init){ //initialize the string with char* m_pstr=new char[MAXSIZE+1]; if(!m_pstr){ cerr<<"Allocation Error"<m_ncurlen=strlen(init); strcpy(m_pstr,init); } CMyString::CMyString(const CMyString ©){ //initialize the string with string m_pstr=new char[MAXSIZE+1]; if(!m_pstr){ cerr<<"Allocation Error"<m_ncurlen=copy.m_ncurlen; strcpy(m_pstr,copy.m_pstr); } int CMyString::Find(CMyString part) const{ //string match :KMP 数据结构算法实现 2008-9-3 int posP=0,posT=0; int lengthP=part.m_ncurlen,lengthT=this->m_ncurlen; part.Next(); while(posPm_pstr[posT]){ posP++; posT++; } else{ if(posP==0){ posT++; } else{ posP=part.m_pnext[posP-1]; 数据结构算法实现 2008-9-3 } } } delete[] part.m_pnext; if(posPm_ncurlen; this->m_pnext=new int[length]; 数据结构算法实现 2008-9-3 this->m_pnext[0]=0; for(int i=1;im_pnext[i-1]; while(*(this->m_pstr+i)!=*(this->m_pstr+j)&&j>0){ j=this->m_pnext[j-1]; } if(*(this->m_pstr+i)==*(this->m_pstr+j)){ this->m_pnext[i]=j+1; } else{ this->m_pnext[i]=0; } } // for(int i=0;im_pstr; } CMyString& CMyString::operator()(int pos, int len){ //get len char with the begining of pos CMyString *temp=new CMyString; //dangerous operation if(pos<0||pos+len-1>MAXSIZE||len<0){ temp->m_ncurlen=0; temp->m_pstr[0]='\0'; } else{ if(pos+len-1>=m_ncurlen){ 数据结构算法实现 2008-9-3 len=m_ncurlen-pos; } temp->m_ncurlen=len; for(int i=0,j=pos;im_pstr[i]=m_pstr[j]; } temp->m_pstr[len]='\0'; } return *temp; } bool CMyString::operator==(const CMyString cmp_str) const{ if(this->m_ncurlen!=cmp_str.m_ncurlen){ return 0; } 数据结构算法实现 2008-9-3 for(int i=0;im_ncurlen;i++){ if(this->m_pstr[i]!=cmp_str.m_pstr[i]) return 0; } return 1; } bool CMyString::operator!=(const CMyString cmp_str) const{ if(*this==cmp_str) return 0; return 1; } bool CMyString::operator<(const CMyString cmp_str) const{ if(this->m_ncurlen!=cmp_str.m_ncurlen){ //Perhaps here it is also compared not by length but by order in dictonary. Hanlian 20100117 数据结构算法实现 2008-9-3 /************************hanlian fix start*********************/ #ifdef HAN_FIX int shortter = this->m_ncurlenm_pstr[index] == cmp_str.m_pstr[index]) { continue; } else if (this->m_pstr[index] < cmp_str.m_pstr[index]) { return 1; } else 数据结构算法实现 2008-9-3 { return 0; } } if (index == shortter) //the long string starts with the short string. { if (flag_cmp == 2) { return 0; } else { returen 1; } 数据结构算法实现 2008-9-3 } #endif /************************hanlian fix stop*********************/ return this->m_ncurlenm_ncurlen;i++){ if(this->m_pstr[i]!=cmp_str.m_pstr[i]){ return this->m_pnext[i](const CMyString cmp_str) const{ if(*thism_pstr; this->m_pstr=new char[copy.m_ncurlen+1]; strcpy(this->m_pstr,copy.m_pstr); return *this; } CMyString& CMyString::operator+=(const CMyString &add){ //字符串追加 int length=this->m_ncurlen+add.m_ncurlen; int n=this->m_ncurlen; CMyString temp(*this); delete[] this->m_pstr; this->m_pstr=new char[length+1]; 数据结构算法实现 2008-9-3 for(int i=0;im_pstr[i]=temp[i]; } for(int i=n;im_pstr[i]=add.m_pstr[i-n]; } this->m_pstr[length]='\0'; return *this; } char& CMyString::operator[](int i){ //取元素 if(i<0||i>=this->m_ncurlen){ cout<<"out of boundary!"<m_pstr[i]; 数据结构算法实现 2008-9-3 } ostream& operator<<(ostream& os,CMyString& str){ os<>(istream& is,CMyString& str){ is>>str.m_pstr; return is; } test.cpp #include 数据结构算法实现 2008-9-3 using namespace std; #include "MyString.h" int main(){ CMyString test1("babc"); CMyString test2("abababcdefb"); cout<test2){ cout<"< class BinaryTree; 数据结构算法实现 2008-9-3 template class BinTreeNode{ public: friend class BinaryTree; BinTreeNode():m_pleft(NULL),m_pright(NULL){} BinTreeNode(Type item,BinTreeNode *left=NULL,BinTreeNode *right=NULL) :m_data(item),m_pleft(left),m_pright(right){} Type GetData() const; //get thd data BinTreeNode *GetLeft() const; //get the left node BinTreeNode *GetRight() const; //get the right node void SetData(const Type data); //change the data void SetLeft(const BinTreeNode *left); //change thd left node void SetRight(const BinTreeNode *right); //change the right node 数据结构算法实现 2008-9-3 void InOrder(); //inorder the tree with the root of the node void PreOrder(); //perorder the tree with the root of the node void PostOrder(); //postoder the tree with the root of the node int Size(); //get size int Height(); //get height BinTreeNode *Copy(const BinTreeNode *copy); //copy the node void Destroy(){ //destroy the tree with the root of the node if(this!=NULL){ this->m_pleft->Destroy(); this->m_pright->Destroy(); delete this; } } 数据结构算法实现 2008-9-3 friend bool equal(const BinTreeNode *s,const BinTreeNode *t); //is equal? private: BinTreeNode *m_pleft,*m_pright; Type m_data; }; template Type BinTreeNode::GetData() const{ return this!=NULL?m_data:-1; } template BinTreeNode* BinTreeNode::GetLeft() const{ return this!=NULL?m_pleft:NULL; 数据结构算法实现 2008-9-3 } template BinTreeNode* BinTreeNode::GetRight() const{ return this!=NULL?m_pright:NULL; } template void BinTreeNode::SetData(const Type data){ if(this!=NULL){ m_data=data; } } template void BinTreeNode::SetLeft(const BinTreeNode *left){ if(this!=NULL){ m_pleft=left; 数据结构算法实现 2008-9-3 } } template void BinTreeNode::SetRight(const BinTreeNode *right){ if(this!=NULL){ m_pright=right; } } template BinTreeNode* BinTreeNode::Copy(const BinTreeNode *copy){ if(copy==NULL){ return NULL; } 数据结构算法实现 2008-9-3 BinTreeNode *temp=new BinTreeNode(copy->m_data); temp->m_pleft=Copy(copy->m_pleft); temp->m_pright=Copy(copy->m_pright); return temp; } template bool equal(const BinTreeNode *s,const BinTreeNode *t){ if(s==NULL&&t==NULL){ return 1; } if(s&&t&&s->m_data==t->m_data&&equal(s->m_pleft,t->m_pleft)&&equal(s->m_pright,t->m_pright)){ return 1; } return 0; 数据结构算法实现 2008-9-3 } template void BinTreeNode::InOrder(){ if(this!=NULL){ this->m_pleft->InOrder(); cout<<"--->"<m_data; this->m_pright->InOrder(); } } template void BinTreeNode::PreOrder(){ if(this!=NULL){ cout<<"--->"<m_data; this->m_pleft->PreOrder(); this->m_pright->PreOrder(); 数据结构算法实现 2008-9-3 } } template void BinTreeNode::PostOrder(){ if(this!=NULL){ this->m_pleft->PostOrder(); this->m_pright->PostOrder(); cout<<"--->"<m_data; } } template int BinTreeNode::Size(){ if(this==NULL){ return 0; } 数据结构算法实现 2008-9-3 return 1+this->m_pleft->Size()+this->m_pright->Size(); // this line has protential danger. Hanlian, should be fixed. } template int BinTreeNode::Height(){ if(this==NULL){ return -1; } int lheight,rheight; lheight=this->m_pleft->Height(); rheight=this->m_pright->Height(); return 1+(lheight>rheight?lheight:rheight); } 数据结构算法实现 2008-9-3 BinaryTree.h #include "BinTreeNode.h" template class BinaryTree{ public: BinaryTree():m_proot(NULL){} BinaryTree(const Type stop):m_stop(stop),m_proot(NULL){} BinaryTree(BinaryTree& copy); virtual ~BinaryTree(){ m_proot->Destroy(); } virtual bool IsEmpty(){ //is empty? return m_proot==NULL; } 数据结构算法实现 2008-9-3 virtual BinTreeNode *GetLeft(BinTreeNode *current); //get the left node virtual BinTreeNode *GetRight(BinTreeNode *current);//get the right node virtual BinTreeNode *GetParent(BinTreeNode *current);//ghe thd parent const BinTreeNode *GetRoot() const; //get root virtual bool Insert(const Type item); //insert a new node virtual BinTreeNode *Find(const Type item) const; //find thd node with the data void InOrder(); void PreOrder(); void PostOrder(); int Size(); //get size int Height(); //get height 数据结构算法实现 2008-9-3 BinaryTree& operator=(const BinaryTree copy); //evaluate node friend bool operator== (const BinaryTree s,const BinaryTree t);//is equal? friend ostream& operator<< (ostream& ,BinaryTree&); //output the data friend istream& operator>> (istream& ,BinaryTree&); //input the data private: Type m_stop; //just using for input the data; BinTreeNode *m_proot; //find the parent of current in the tree with the root of start BinTreeNode *GetParent(BinTreeNode *start,BinTreeNode *current); void Print(BinTreeNode *start,int n=0); //print the tree with the root of start 数据结构算法实现 2008-9-3 }; template BinaryTree::BinaryTree(BinaryTree& copy){ if(copy.m_proot){ this->m_stop=copy.m_stop; } m_proot=m_proot->Copy(copy.m_proot); } template BinTreeNode* BinaryTree::GetLeft(BinTreeNode *current){ return m_proot&¤t?current->m_pleft:NULL; } template BinTreeNode* BinaryTree::GetRight(BinTreeNode *current){ 数据结构算法实现 2008-9-3 return m_proot&¤t?current->m_pright:NULL; } template const BinTreeNode* BinaryTree::GetRoot() const{ return m_proot; } template BinTreeNode* BinaryTree::GetParent(BinTreeNode *start, BinTreeNode *current){ if(start==NULL||current==NULL){ return NULL; } if(start->m_pleft==current||start->m_pright==current){ return start; } 数据结构算法实现 2008-9-3 BinTreeNode *pmove; if((pmove=GetParent(start->m_pleft,current))!=NULL){//find the parent in the left subtree return pmove; } else{ return GetParent(start->m_pright,current); //find the parent in the right subtree } } template BinTreeNode* BinaryTree::GetParent(BinTreeNode *current){ return m_proot==NULL||current==m_proot?NULL:GetParent(m_proot,current); } 数据结构算法实现 2008-9-3 template bool BinaryTree::Insert(const Type item){ BinTreeNode *pstart=m_proot,*newnode=new BinTreeNode(item); if(m_proot==NULL){ m_proot=newnode; return 1; } while(1){ if(item==pstart->m_data){ cout<<"The item "<m_data){ if(pstart->m_pleft==NULL){ pstart->m_pleft=newnode; return 1; 数据结构算法实现 2008-9-3 } pstart=pstart->m_pleft; //if less than the node then insert to the left subtree } else{ if(pstart->m_pright==NULL){ pstart->m_pright=newnode; return 1; } pstart=pstart->m_pright;//if more than the node then insert to the right subtree } } } template BinTreeNode* BinaryTree::Find(const Type item) const{ BinTreeNode *pstart=m_proot; 数据结构算法实现 2008-9-3 while(pstart){ if(item==pstart->m_data){ return pstart; } if(itemm_data){ pstart=pstart->m_pleft; //if less than the node then find in the left subtree } else{ pstart=pstart->m_pright;//if more than the node then find in the right subtree } } return NULL; } template void BinaryTree::Print(BinTreeNode *start, int n){ 数据结构算法实现 2008-9-3 if(start==NULL){ for(int i=0;im_pright,n+1); //print the right subtree for(int i=0;i=0){ cout<m_data<<"--->"<m_pleft,n+1); //print the left subtree 数据结构算法实现 2008-9-3 } template BinaryTree& BinaryTree::operator=(const BinaryTree copy){ if(copy.m_proot){ this->m_stop=copy.m_stop; } m_proot=m_proot->Copy(copy.m_proot); return *this; } template ostream& operator<<(ostream& os,BinaryTree& out){ out.Print(out.m_proot); return os; } 数据结构算法实现 2008-9-3 template istream& operator>>(istream& is,BinaryTree& in){ Type item; cout<<"initialize the tree:"<>item; while(item!=in.m_stop){ //m_stop is the end of input in.Insert(item); is>>item; } return is; } template bool operator==(const BinaryTree s,const BinaryTree t){ return equal(s.m_proot,t.m_proot); } 数据结构算法实现 2008-9-3 template void BinaryTree::InOrder(){ this->m_proot->InOrder(); } template void BinaryTree::PreOrder(){ this->m_proot->PreOrder(); } template void BinaryTree::PostOrder(){ this->m_proot->PostOrder(); } template int BinaryTree::Size(){ return this->m_proot->Size(); 数据结构算法实现 2008-9-3 } template int BinaryTree::Height(){ return this->m_proot->Height(); } Test.cpp #include using namespace std; #include "BinaryTree.h" 数据结构算法实现 2008-9-3 int main(){ BinaryTree tree(-1); // int init[10]={3,6,0,2,8,4,9,1,5,7}; int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8 ,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25}; for(int i=0;i<30;i++){ tree.Insert(init[i]); } //cin>>tree; cout<GetData()<GetRight()->GetData()< class ThreadInorderIterator; template class ThreadTree{ public: friend class ThreadInorderIterator; ThreadTree():m_proot(new ThreadNode()){} ThreadInorderIterator.h #include "ThreadTree.h" template class ThreadInorderIterator{ public: 数据结构算法实现 2008-9-3 ThreadInorderIterator(ThreadTree &tree):m_ptree(tree),m_pcurrent(tree.m_proot){ //InThread(m_ptree.m_proot->m_pleft,m_ptree.m_proot); } ThreadNode *First(); ThreadNode *Prior(); ThreadNode *Next(); void Print(); void Print(ThreadNode *start, int n=0); void InOrder(); void InsertLeft(ThreadNode *left); void InsertRight(ThreadNode *right); ThreadNode *GetParent(ThreadNode *current); 数据结构算法实现 2008-9-3 private: ThreadTree &m_ptree; ThreadNode *m_pcurrent; void InThread(ThreadNode *current,ThreadNode *pre); }; template void ThreadInorderIterator::InThread( ThreadNode *current, ThreadNode *pre){ if(current!=m_ptree.m_proot){ InThread(current->m_pleft,pre); if(current->m_pleft==NULL){ current->m_pleft=pre; current->m_nleftthread=1; } 数据结构算法实现 2008-9-3 if(pre->m_pright==NULL){ pre->m_pright=current; pre->m_nrightthread=1; } pre=current; InThread(current->m_pright,pre); } } template ThreadNode* ThreadInorderIterator::First(){ while(m_pcurrent->m_nleftthread==0){ m_pcurrent=m_pcurrent->m_pleft; } return m_pcurrent; 数据结构算法实现 2008-9-3 } template ThreadNode* ThreadInorderIterator::Prior(){ ThreadNode *pmove=m_pcurrent->m_pleft; if(0==m_pcurrent->m_nleftthread){ while(0==pmove->m_nrightthread){ pmove=pmove->m_pright; } } m_pcurrent=pmove; if(m_pcurrent==m_ptree.m_proot){ return NULL; } return m_pcurrent; } 数据结构算法实现 2008-9-3 template ThreadNode* ThreadInorderIterator::Next(){ ThreadNode *pmove=m_pcurrent->m_pright; if(0==m_pcurrent->m_nrightthread){ while(0==pmove->m_nleftthread){ pmove=pmove->m_pleft; } } m_pcurrent=pmove; if(m_pcurrent==m_ptree.m_proot){ return NULL; } return m_pcurrent; } 数据结构算法实现 2008-9-3 template void ThreadInorderIterator::InOrder(){ ThreadNode *pmove=m_ptree.m_proot; while(pmove->m_pleft!=m_ptree.m_proot){ pmove=pmove->m_pleft; } m_pcurrent=pmove; cout<<"root"; while(pmove!=m_ptree.m_proot&&pmove){ cout<<"--->"<m_data; pmove=this->Next(); } cout<<"--->end"; } template void ThreadInorderIterator::InsertLeft(ThreadNode *left){ 数据结构算法实现 2008-9-3 left->m_pleft=m_pcurrent->m_pleft; left->m_nleftthread=m_pcurrent->m_nleftthread; left->m_pright=m_pcurrent; left->m_nrightthread=1; m_pcurrent->m_pleft=left; m_pcurrent->m_nleftthread=0; if(0==left->m_nleftthread){ m_pcurrent=left->m_pleft; ThreadNode *temp=First(); temp->m_pright=left; } m_pcurrent=left; } template void ThreadInorderIterator::InsertRight(ThreadNode *right){ 数据结构算法实现 2008-9-3 right->m_pright=m_pcurrent->m_pright; right->m_nrightthread=m_pcurrent->m_nrightthread; right->m_pleft=m_pcurrent; right->m_nleftthread=1; m_pcurrent->m_pright=right; m_pcurrent->m_nrightthread=0; if(0==right->m_nrightthread){ m_pcurrent=right->m_pright; ThreadNode *temp=First(); temp->m_pleft=right; } m_pcurrent=right; } 数据结构算法实现 2008-9-3 template ThreadNode* ThreadInorderIterator::GetParent( ThreadNode *current){ ThreadNode *pmove=current; while(0==pmove->m_nleftthread){ pmove=pmove->m_pleft; } pmove=pmove->m_pleft; if(pmove==m_ptree.m_proot){ if(pmove->m_pleft==current){ return NULL; } } if(pmove->m_pright==current){ return pmove; } 数据结构算法实现 2008-9-3 pmove=pmove->m_pright; while(pmove->m_pleft!=current){ pmove=pmove->m_pleft; } return pmove; } template void ThreadInorderIterator::Print(ThreadNode *start, int n){ if(start->m_nleftthread&&start->m_nrightthread){ for(int i=0;i=0){ cout<m_data<<"--->"<m_nrightthread==0){ Print(start->m_pright,n+1); } for(int i=0;i=0){ cout<m_data<<"--->"<m_nleftthread==0){ Print(start->m_pleft,n+1); 数据结构算法实现 2008-9-3 } } template void ThreadInorderIterator::Print(){ Print(m_ptree.m_proot->m_pleft); } test.cpp #include using namespace std; #include "ThreadInorderIterator.h" 数据结构算法实现 2008-9-3 int main(){ ThreadTree tree; ThreadInorderIterator threadtree(tree); int init[10]={3,6,0,2,8,4,9,1,5,7}; for(int i=0;i<10;){ threadtree.InsertLeft(new ThreadNode(init[i++])); threadtree.InsertRight(new ThreadNode(init[i++])); } threadtree.Print(); cout< *m_proot; }; 13、堆 MinHeap.h template class MinHeap{ public: MinHeap(int size):m_nMaxSize(size > defaultsize ? size : defaultsize) ,m_pheap(new Type[m_nMaxSize]),m_ncurrentsize(0){} MinHeap(Type heap[],int n); //initialize heap by a array ~MinHeap(){ delete[] m_pheap; } 数据结构算法实现 2008-9-3 public: bool Insert(const Type item); //insert element bool Delete(const Type item); //delete element bool IsEmpty() const{ return m_ncurrentsize == 0; } bool IsFull() const{ reutrn m_ncurrentsize == m_nMaxSize; } void Print(const int start=0, int n=0); private: //adjust the elements of the child tree with the root of start from top to bottom void Adjust(const int start, const int end); 数据结构算法实现 2008-9-3 private: static const int defaultsize = 100; const int m_nMaxSize; Type *m_pheap; int m_ncurrentsize; }; template void MinHeap::Adjust(const int start, const int end){ int i = start,j = i*2+1; //get the position of the child of i Type temp=m_pheap[i]; while(j <= end){ if(jm_pheap[j+1]){ //left>right j++; } 数据结构算法实现 2008-9-3 if(temp <= m_pheap[j]){ //adjust over break; } else{ //change the parent and the child, then adjust the child m_pheap[i] = m_pheap[j]; i = j; j = 2*i+1; } } m_pheap[i] = temp; } template MinHeap::MinHeap(Type heap[], int n):m_nMaxSize( n > defaultsize ? n : defaultsize){ m_pheap = new Type[m_nMaxSize]; 数据结构算法实现 2008-9-3 for(int i=0; i=0){ Adjust(pos, n-1); pos--; } } template bool MinHeap::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr<<"Heap Full!"< 0){ //adjust from bottom to top if(m_pheap[i] <= temp){ break; } else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; } } m_pheap[j] = temp; 数据结构算法实现 2008-9-3 m_ncurrentsize++; return 1; } template bool MinHeap::Delete(const Type item){ if(0 == m_ncurrentsize){ cerr<<"Heap Empty!"< void MinHeap::Print(const int start, int n){ if(start >= m_ncurrentsize){ return; } Print(start*2+2, n+1); //print the right child tree for(int i=0; i" << endl; 数据结构算法实现 2008-9-3 Print(start*2+1, n+1); //print the left child tree } test.cpp #include using namespace std; #include "MinHeap.h" int main(){ int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8 ,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25}; 数据结构算法实现 2008-9-3 MinHeap heap(init,30); heap.Print(); cout< class BinaryTree; template void Huffman(Type *, int, BinaryTree &); template class BinTreeNode{ public: friend class BinaryTree; friend void Huffman(Type *, int, BinaryTree &); BinTreeNode():m_pleft(NULL),m_pright(NULL){} BinTreeNode(Type item,BinTreeNode *left=NULL,BinTreeNode *right=NULL) :m_data(item),m_pleft(left),m_pright(right){} void Destroy(){ //destroy the tree with the root of the node 数据结构算法实现 2008-9-3 if(this!=NULL){ this->m_pleft->Destroy(); this->m_pright->Destroy(); delete this; } } Type GetData(){ return m_data; } BinTreeNode *Copy(const BinTreeNode *copy); //copy the node private: BinTreeNode *m_pleft,*m_pright; Type m_data; }; 数据结构算法实现 2008-9-3 template BinTreeNode* BinTreeNode::Copy(const BinTreeNode *copy){ if(copy==NULL){ return NULL; } BinTreeNode *temp=new BinTreeNode(copy->m_data); temp->m_pleft=Copy(copy->m_pleft); temp->m_pright=Copy(copy->m_pright); return temp; } BinaryTree.h 数据结构算法实现 2008-9-3 #include "BinTreeNode.h" template void Huffman(Type *, int, BinaryTree &); template class BinaryTree{ public: BinaryTree(BinaryTree &bt1, BinaryTree &bt2){ m_proot = new BinTreeNode(bt1.m_proot->m_data + bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot); } BinaryTree(Type item){ m_proot = new BinTreeNode(item); } BinaryTree(const BinaryTree ©){ 数据结构算法实现 2008-9-3 this->m_proot = copy.m_proot; } BinaryTree(){ m_proot = NULL; } void Destroy(){ m_proot->Destroy(); } ~BinaryTree(){ // m_proot->Destroy(); } BinaryTree& operator=(BinaryTree copy); //evaluate node friend void Huffman(Type *, int, BinaryTree &); friend bool operator < (BinaryTree &l, BinaryTree & r); 数据结构算法实现 2008-9-3 friend bool operator > (BinaryTree &l, BinaryTree & r); friend bool operator <= (BinaryTree &l, BinaryTree & r); friend ostream& operator<< (ostream& ,BinaryTree&); //output the data private: BinTreeNode *m_proot; void Print(BinTreeNode *start,int n=0); //print the tree with the root of start }; template bool operator <(BinaryTree &l, BinaryTree &r){ return l.m_proot->GetData() < r.m_proot->GetData(); } template bool operator >(BinaryTree &l, BinaryTree &r){ return l.m_proot->GetData() > r.m_proot->GetData(); } 数据结构算法实现 2008-9-3 template bool operator <=(BinaryTree &l, BinaryTree &r){ return l.m_proot->GetData() <= r.m_proot->GetData(); } template void BinaryTree::Print(BinTreeNode *start, int n){ if(start==NULL){ for(int i=0;im_pright,n+1); //print the right subtree 数据结构算法实现 2008-9-3 for(int i=0;i=0){ cout<m_data<<"--->"<m_pleft,n+1); //print the left subtree } template ostream& operator<<(ostream& os,BinaryTree& out){ out.Print(out.m_proot); return os; } template BinaryTree& BinaryTree::operator=(BinaryTree copy){ 数据结构算法实现 2008-9-3 m_proot=m_proot->Copy(copy.m_proot); return *this; } MinHeap.h template class MinHeap{ public: MinHeap(Type heap[],int n); //initialize heap by a array ~MinHeap(){ delete[] m_pheap; } public: bool Insert(const Type item); 数据结构算法实现 2008-9-3 bool DeleteMin(Type &first); private: void Adjust(const int start, const int end); //adjust the elements from start to end private: const int m_nMaxSize; Type *m_pheap; int m_ncurrentsize; }; template void MinHeap::Adjust(const int start, const int end){ int i = start,j = i*2+1; Type temp=m_pheap[i]; 数据结构算法实现 2008-9-3 while(j <= end){ if(jm_pheap[j+1]){ j++; } if(temp <= m_pheap[j]){ break; } else{ m_pheap[i] = m_pheap[j]; i = j; j = 2*i+1; } } m_pheap[i] = temp; } 数据结构算法实现 2008-9-3 template MinHeap::MinHeap(Type heap[], int n):m_nMaxSize(n){ m_pheap = new Type[m_nMaxSize]; for(int i=0; i=0){ Adjust(pos, n-1); pos--; } } template bool MinHeap::DeleteMin(Type &first){ 数据结构算法实现 2008-9-3 first = m_pheap[0]; m_pheap[0] = m_pheap[m_ncurrentsize-1]; m_ncurrentsize--; Adjust(0, m_ncurrentsize-1); return 1; } template bool MinHeap::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr<<"Heap Full!"< 0){ if(m_pheap[i] <= temp){ break; } else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; } } m_pheap[j] = temp; m_ncurrentsize++; return 1; } 数据结构算法实现 2008-9-3 Huffman.h #include "BinaryTree.h" #include "MinHeap.h" template void Huffman(Type *elements, int n, BinaryTree &tree){ BinaryTree first, second; BinaryTree node[20]; for (int i=0; i(elements[i]); } MinHeap > heap(node, n); for (int i=0; iGetData() == second.m_proot->GetData()){ tree = *(new BinaryTree(second, first)); } else { tree = *(new BinaryTree(first, second)); } heap.Insert(tree); } } 数据结构算法实现 2008-9-3 Test.cpp #include using namespace std; #include "Huffman.h" int main(){ BinaryTree tree; int init[10]={3,6,0,2,8,4,9,1,5,7}; Huffman(init,10,tree); cout << tree; tree.Destroy(); return 0; 数据结构算法实现 2008-9-3 } 15、树 QueueNode.h template 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); Type Delete(); Type GetFront(); 数据结构算法实现 2008-9-3 void MakeEmpty(); bool IsEmpty() const{ return m_pfront==NULL; } void Print(); private: QueueNode *m_prear,*m_pfront; }; template void LinkQueue::MakeEmpty(){ QueueNode *pdel; while(m_pfront){ pdel=m_pfront; m_pfront=m_pfront->m_pnext; 数据结构算法实现 2008-9-3 delete pdel; } } 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()){ 数据结构算法实现 2008-9-3 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; } template void LinkQueue::Print(){ QueueNode *pmove=m_pfront; cout<<"front"; while(pmove){ cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->rear"< class Tree; template class TreeNode{ public: friend class Tree; private: Type m_data; TreeNode *m_pfirst,*m_pnext; TreeNode():m_pfirst(NULL), m_pnext(NULL){} TreeNode(Type item, TreeNode *first = NULL, TreeNode *next = NULL) :m_data(item), m_pfirst(first), m_pnext(next){} }; 数据结构算法实现 2008-9-3 Tree.h #include "TreeNode.h" #include "LinkQueue.h" template class Tree{ public: Tree():m_proot(NULL), m_pcurrent(NULL){} public: TreeNode *GetCurrent(){ //Get the current node return m_pcurrent; } void SetCurrent(TreeNode *current){ //set the current node m_pcurrent = current; } 数据结构算法实现 2008-9-3 bool Insert(Type item); //insert an new node to current node void Remove(Type item); //delete the node whose data is equal to item void Remove(TreeNode *current); //delete the node bool Find(Type item); //find the node whose data is equal to item void PrintChild(TreeNode *current); //print the child tree TreeNode *Parent(TreeNode *current); //get the parent void Print(); //print the tree void PreOrder(TreeNode *root); //ordering the tree by visiting the root first void PostOrder(TreeNode *root); //ordering the tree by visiting the root last void LevelOrder(TreeNode *root); //ordering the tree by level void PreOrder(); void PostOrder(); void LevelOrder(); 数据结构算法实现 2008-9-3 private: TreeNode *m_proot,*m_pcurrent; bool Find(TreeNode *root, Type item); void Remove(TreeNode *root, Type item); TreeNode *Parent(TreeNode *root, TreeNode *current); void Print(TreeNode *start, int n=0); }; template bool Tree::Insert(Type item){ TreeNode *newnode = new TreeNode(item); if (NULL == newnode){ cout << "Application Error!" <m_pfirst){ m_pcurrent->m_pfirst = newnode; m_pcurrent = newnode; return 1; } TreeNode *pmove = m_pcurrent->m_pfirst; 数据结构算法实现 2008-9-3 while(pmove->m_pnext){ pmove = pmove->m_pnext; } pmove->m_pnext = newnode; m_pcurrent = newnode; return 1; } template void Tree::Remove(TreeNode *current){ if(NULL == current){ return; } TreeNode *temp = Parent(current); if(NULL == temp){ 数据结构算法实现 2008-9-3 TreeNode *pmove = current->m_pfirst; if(NULL != pmove->m_pfirst){ pmove=pmove->m_pfirst; while(pmove->m_pnext){ pmove = pmove->m_pnext; } pmove->m_pnext = current->m_pfirst->m_pnext; current->m_pfirst->m_pnext = NULL; } else{ pmove->m_pfirst = pmove->m_pnext; } m_proot = current->m_pfirst; } else{ 数据结构算法实现 2008-9-3 if(temp->m_pfirst == current){ TreeNode *pmove = current->m_pfirst; if (pmove){ while (pmove->m_pnext){ pmove = pmove->m_pnext; } pmove->m_pnext = current->m_pnext; } else{ current->m_pfirst = current->m_pnext; } } else{ TreeNode *pmove = temp->m_pfirst; 数据结构算法实现 2008-9-3 while(pmove->m_pnext != current){ pmove = pmove->m_pnext; } pmove->m_pnext = current->m_pnext; while(pmove->m_pnext){ pmove = pmove->m_pnext; } pmove->m_pnext = current->m_pfirst; } } delete current; } template void Tree::Remove(TreeNode *root, Type item){ if(NULL == root){ 数据结构算法实现 2008-9-3 return; } if(root->m_pfirst){ TreeNode *pmove=root->m_pfirst; while(pmove){ Remove(pmove, item); pmove = pmove->m_pnext; } } if(root->m_data == item){ Remove(root); } } template void Tree::Remove(Type item){ 数据结构算法实现 2008-9-3 return Remove(m_proot, item); } template TreeNode* Tree::Parent( TreeNode *root, TreeNode *current){ if(NULL == root){ return NULL; } TreeNode *pmove=root->m_pfirst,*temp; if(NULL != pmove){ while(pmove){ if(pmove == current){ return root; } pmove = pmove->m_pnext; 数据结构算法实现 2008-9-3 } } pmove = root->m_pfirst; while(pmove){ temp = Parent(pmove, current); if(temp){ return temp; } pmove = pmove->m_pnext; } return NULL; } template TreeNode* Tree::Parent(TreeNode *current){ return Parent(m_proot,current); 数据结构算法实现 2008-9-3 } template void Tree::PrintChild(TreeNode *current){ TreeNode *pmove = current->m_pfirst; cout<<"first"; if(NULL != pmove){ cout<<"--->"<m_data; } while(pmove->m_pnext){ cout<<"--->"<m_data; pmove = pmove->m_pnext; } } template bool Tree::Find(TreeNode *root, Type item){ 数据结构算法实现 2008-9-3 if (root->m_data == item){ return 1; } if (NULL == root){ return 0; } TreeNode *pmove=root->m_pfirst; if (NULL == pmove){ return 0; } while (pmove){ if (Find(pmove, item)){ return 1; } pmove = pmove->m_pnext; 数据结构算法实现 2008-9-3 } return 0; } template bool Tree::Find(Type item){ return Find(m_proot,item); } template void Tree::Print(TreeNode *start, int n = 0){ if (NULL == start){ for (int i=0; i *pmove = start->m_pfirst; Print(pmove, n+1); for (int i=0; im_data << "--->" <m_pnext; while (pmove){ Print(pmove, n+1); 数据结构算法实现 2008-9-3 pmove = pmove->m_pnext; } } template void Tree::Print(){ Print(m_proot); } template void Tree::PreOrder(TreeNode *root){ if (NULL == root){ return; } cout << root->m_data; TreeNode *pmove = root->m_pfirst; while (pmove){ 数据结构算法实现 2008-9-3 PreOrder(pmove); pmove = pmove->m_pnext; } } template void Tree::PostOrder(TreeNode *root){ if (NULL == root){ return; } TreeNode *pmove = root->m_pfirst; while (pmove){ PostOrder(pmove); pmove = pmove->m_pnext; } cout << root->m_data; 数据结构算法实现 2008-9-3 } template void Tree::PreOrder(){ PreOrder(m_proot); } template void Tree::PostOrder(){ PostOrder(m_proot); } template void Tree::LevelOrder(TreeNode *root){ //using queue LinkQueue *> queue; TreeNode *pmove, *ptemp; if (root != NULL){ queue.Append(root); 数据结构算法实现 2008-9-3 while (!queue.IsEmpty()){ ptemp = queue.Delete(); cout << ptemp->m_data; pmove = ptemp->m_pfirst; while(pmove){ queue.Append(pmove); pmove = pmove->m_pnext; } } } } template void Tree::LevelOrder(){ LevelOrder(m_proot); } 数据结构算法实现 2008-9-3 test.cpp #include using namespace std; #include "Tree.h" int main(){ Tree tree; int init[10]={3,6,0,2,8,4,9,1,5,7}; for (int i=0; i<10; i++){ tree.Insert(init[i]); if (1 == i % 2){ 数据结构算法实现 2008-9-3 tree.SetCurrent(tree.Parent(tree.GetCurrent())); } } tree.Print(); cout << endl < class BTree; template class BTreeNode{ public: friend BTree; BTreeNode(): m_nMaxSize(0), m_ptr(NULL), m_pparent(NULL){} BTreeNode(int size): m_nsize(0), m_nMaxSize(size), m_pparent(NULL){ 数据结构算法实现 2008-9-3 m_pkey = new Type[size+1]; m_ptr = new BTreeNode *[size+1]; for (int i=0; i<=size; i++){ m_ptr[i] = NULL; m_pkey[i] = this->m_Infinity; } } void Destroy(BTreeNode *root); ~BTreeNode(){ if (m_nMaxSize){ delete[] m_pkey; for (int i=0; i<=m_nMaxSize; i++){ m_ptr[i] = NULL; } } 数据结构算法实现 2008-9-3 } bool IsFull(){ return m_nsize == m_nMaxSize; } Type GetKey(int i){ if (this){ return this->m_pkey[i]; } return -1; } private: int m_nsize; int m_nMaxSize; //the Max Size of key Type *m_pkey; 数据结构算法实现 2008-9-3 BTreeNode *m_pparent; BTreeNode **m_ptr; static const Type m_Infinity = 10000; }; template struct Triple{ BTreeNode *m_pfind; int m_nfind; bool m_ntag; }; template void BTreeNode::Destroy(BTreeNode *root){ if (NULL == root){ return; } 数据结构算法实现 2008-9-3 for (int i=0; im_nsize; i++){ Destroy(root->m_ptr[i]); } delete root; } BTree.h #include "BTreeNode.h" template class BTree{ public: BTree(int size): m_nMaxSize(size), m_proot(NULL){} ~BTree(); 数据结构算法实现 2008-9-3 Triple Search(const Type item); int Size(); int Size(BTreeNode *root); bool Insert(const Type item); //insert item bool Remove(const Type item); //delete item void Print(); //print the BTree BTreeNode *GetParent(const Type item); private: //insert the pright and item to pinsert in the nth place; void InsertKey(BTreeNode *pinsert, int n, const Type item, BTreeNode *pright); void PreMove(BTreeNode *root, int n); //move ahead 数据结构算法实现 2008-9-3 //merge the child tree void Merge(BTreeNode *pleft, BTreeNode *pparent, BTreeNode *pright, int n); //adjust with the parent and the left child tree void LeftAdjust(BTreeNode *pright, BTreeNode *pparent, int min, int n); //adjust with the parent and the left child tree void RightAdjust(BTreeNode *pleft, BTreeNode *pparent, int min, int n); void Print(BTreeNode *start, int n = 0); private: BTreeNode *m_proot; const int m_nMaxSize; 数据结构算法实现 2008-9-3 }; template BTree::~BTree(){ m_proot->Destroy(m_proot); } template Triple BTree::Search(const Type item){ Triple result; BTreeNode *pmove = m_proot, *parent = NULL; int i = 0; while (pmove){ i = -1; while (item > pmove->m_pkey[++i]); //find the suit position if (pmove->m_pkey[i] == item){ result.m_pfind = pmove; 数据结构算法实现 2008-9-3 result.m_nfind = i; result.m_ntag = 1; return result; } parent = pmove; pmove = pmove->m_ptr[i]; //find in the child tree } result.m_pfind = parent; result.m_nfind = i; result.m_ntag = 0; return result; } template void BTree::InsertKey(BTreeNode *pinsert, int n, const Type item, BTreeNode *pright){ 数据结构算法实现 2008-9-3 pinsert->m_nsize++; for (int i=pinsert->m_nsize; i>n; i--){ pinsert->m_pkey[i] = pinsert->m_pkey[i-1]; pinsert->m_ptr[i+1] = pinsert->m_ptr[i]; } pinsert->m_pkey[n] = item; pinsert->m_ptr[n+1] = pright; if (pinsert->m_ptr[n+1]){ //change the right child tree's parent pinsert->m_ptr[n+1]->m_pparent = pinsert; for (int i=0; i<=pinsert->m_ptr[n+1]->m_nsize; i++){ if (pinsert->m_ptr[n+1]->m_ptr[i]){ pinsert->m_ptr[n+1]->m_ptr[i]->m_pparent = pinsert->m_ptr[n+1]; } } 数据结构算法实现 2008-9-3 } } template bool BTree::Insert(const Type item){ if (NULL == m_proot){ //insert the first node m_proot = new BTreeNode(m_nMaxSize); m_proot->m_nsize = 1; m_proot->m_pkey[1] = m_proot->m_pkey[0]; m_proot->m_pkey[0] = item; m_proot->m_ptr[0] = m_proot->m_ptr[1] =NULL; return 1; } Triple find = this->Search(item); //search the position if (find.m_ntag){ cerr << "The item is exist!" << endl; 数据结构算法实现 2008-9-3 return 0; } BTreeNode *pinsert = find.m_pfind, *newnode; BTreeNode *pright = NULL, *pparent; Type key = item; int n = find.m_nfind; while (1){ if (pinsert->m_nsize < pinsert->m_nMaxSize-1){ //There is some space InsertKey(pinsert, n, key, pright); return 1; } int m = (pinsert->m_nsize + 1) / 2; //get the middle item InsertKey(pinsert, n, key, pright); //insert first, then break up 数据结构算法实现 2008-9-3 newnode = new BTreeNode(this->m_nMaxSize);//create the newnode for break up //break up for (int i=m+1; i<=pinsert->m_nsize; i++){ newnode->m_pkey[i-m-1] = pinsert->m_pkey[i]; newnode->m_ptr[i-m-1] = pinsert->m_ptr[i]; pinsert->m_pkey[i] = pinsert->m_Infinity; pinsert->m_ptr[i] = NULL; } newnode->m_nsize = pinsert->m_nsize - m - 1; pinsert->m_nsize = m; for (int i=0; i<=newnode->m_nsize; i++){ //change the parent if (newnode->m_ptr[i]){ newnode->m_ptr[i]->m_pparent = newnode; 数据结构算法实现 2008-9-3 for (int j=0; j<=newnode->m_ptr[i]->m_nsize; j++){ if (newnode->m_ptr[i]->m_ptr[j]){ newnode->m_ptr[i]->m_ptr[j]->m_pparent = newnode->m_ptr[i]; } } } } for (int i=0; i<=pinsert->m_nsize; i++){ //change the parent if (pinsert->m_ptr[i]){ pinsert->m_ptr[i]->m_pparent = pinsert; for (int j=0; j<=pinsert->m_nsize; j++){ if (pinsert->m_ptr[i]->m_ptr[j]){ pinsert->m_ptr[i]->m_ptr[j]->m_pparent = pinsert->m_ptr[i]; } } 数据结构算法实现 2008-9-3 } } //break up over key = pinsert->m_pkey[m]; pright = newnode; if (pinsert->m_pparent){ //insert the key to the parent pparent = pinsert->m_pparent; n = -1; pparent->m_pkey[pparent->m_nsize] = pparent->m_Infinity; while (key > pparent->m_pkey[++n]); newnode->m_pparent = pinsert->m_pparent; pinsert = pparent; } else { //create new root 数据结构算法实现 2008-9-3 m_proot = new BTreeNode(this->m_nMaxSize); m_proot->m_nsize = 1; m_proot->m_pkey[1] = m_proot->m_pkey[0]; m_proot->m_pkey[0] = key; m_proot->m_ptr[0] = pinsert; m_proot->m_ptr[1] = pright; newnode->m_pparent = pinsert->m_pparent = m_proot; return 1; } } } template void BTree::PreMove(BTreeNode *root, int n){ root->m_pkey[root->m_nsize] = root->m_Infinity; for (int i=n; im_nsize; i++){ 数据结构算法实现 2008-9-3 root->m_pkey[i] = root->m_pkey[i+1]; root->m_ptr[i+1] = root->m_ptr[i+2]; } root->m_nsize--; } template void BTree::Merge(BTreeNode *pleft, BTreeNode *pparent, BTreeNode *pright, int n){ pleft->m_pkey[pleft->m_nsize] = pparent->m_pkey[n]; BTreeNode *ptemp; for (int i=0; i<=pright->m_nsize; i++){ //merge the two child tree and the parent pleft->m_pkey[pleft->m_nsize+i+1] = pright->m_pkey[i]; pleft->m_ptr[pleft->m_nsize+i+1] = pright->m_ptr[i]; 数据结构算法实现 2008-9-3 ptemp = pleft->m_ptr[pleft->m_nsize+i+1]; if (ptemp){ //change thd right child tree's parent ptemp->m_pparent = pleft; for (int j=0; j<=ptemp->m_nsize; j++){ if (ptemp->m_ptr[j]){ ptemp->m_ptr[j]->m_pparent = ptemp; } } } } pleft->m_nsize = pleft->m_nsize + pright->m_nsize + 1; delete pright; PreMove(pparent, n); // this->Print(); 数据结构算法实现 2008-9-3 } template void BTree::LeftAdjust(BTreeNode *pright, BTreeNode *pparent, int min, int n){ BTreeNode *pleft = pparent->m_ptr[n-1], *ptemp; if (pleft->m_nsize > min-1){ for (int i=pright->m_nsize+1; i>0; i--){ pright->m_pkey[i] = pright->m_pkey[i-1]; pright->m_ptr[i] = pright->m_ptr[i-1]; } pright->m_pkey[0] = pparent->m_pkey[n-1]; pright->m_ptr[0] = pleft->m_ptr[pleft->m_nsize]; ptemp = pright->m_ptr[0]; if (ptemp){ //change the tree's parent which is moved 数据结构算法实现 2008-9-3 ptemp->m_pparent = pright; for (int i=0; im_nsize; i++){ if (ptemp->m_ptr[i]){ ptemp->m_ptr[i]->m_pparent = ptemp; } } } pparent->m_pkey[n-1] = pleft->m_pkey[pleft->m_nsize-1]; pleft->m_pkey[pleft->m_nsize] = pleft->m_Infinity; pleft->m_nsize--; pright->m_nsize++; } else { Merge(pleft, pparent, pright, n-1); } 数据结构算法实现 2008-9-3 // this->Print(); } template void BTree::RightAdjust(BTreeNode *pleft, BTreeNode *pparent, int min, int n){ BTreeNode *pright = pparent->m_ptr[1], *ptemp; if (pright && pright->m_nsize > min-1){ pleft->m_pkey[pleft->m_nsize] = pparent->m_pkey[0]; pparent->m_pkey[0] = pright->m_pkey[0]; pleft->m_ptr[pleft->m_nsize+1] = pright->m_ptr[0]; ptemp = pleft->m_ptr[pleft->m_nsize+1]; if (ptemp){ //change the tree's parent which is moved ptemp->m_pparent = pleft; for (int i=0; im_nsize; i++){ if (ptemp->m_ptr[i]){ 数据结构算法实现 2008-9-3 ptemp->m_ptr[i]->m_pparent = ptemp; } } } pright->m_ptr[0] = pright->m_ptr[1]; pleft->m_nsize++; PreMove(pright,0); } else { Merge(pleft, pparent, pright, 0); } } template bool BTree::Remove(const Type item){ 数据结构算法实现 2008-9-3 Triple result = this->Search(item); if (!result.m_ntag){ return 0; } BTreeNode *pdel, *pparent, *pmin; int n = result.m_nfind; pdel = result.m_pfind; if (pdel->m_ptr[n+1] != NULL){ //change into delete leafnode pmin = pdel->m_ptr[n+1]; pparent = pdel; while (pmin != NULL){ pparent = pmin; pmin = pmin->m_ptr[0]; } 数据结构算法实现 2008-9-3 pdel->m_pkey[n] = pparent->m_pkey[0]; pdel = pparent; n = 0; } PreMove(pdel, n); //delete the node int min = (this->m_nMaxSize + 1) / 2; while (pdel->m_nsize < min-1){ //if it is not a BTree, then adjust n = 0; pparent = pdel->m_pparent; if (NULL == pparent) { return 1; } 数据结构算法实现 2008-9-3 while (n<= pparent->m_nsize && pparent->m_ptr[n]!=pdel){ n++; } if (!n){ RightAdjust(pdel, pparent, min, n); //adjust with the parent and the right child tree } else { LeftAdjust(pdel, pparent, min, n); //adjust with the parent and the left child tree } pdel = pparent; if (pdel == m_proot){ break; } 数据结构算法实现 2008-9-3 } if (!m_proot->m_nsize){ //the root is merged pdel = m_proot->m_ptr[0]; delete m_proot; m_proot = pdel; m_proot->m_pparent = NULL; for (int i=0; im_nsize; i++){ if (m_proot->m_ptr[i]){ m_proot->m_ptr[i]->m_pparent = m_proot; } } } return 1; } 数据结构算法实现 2008-9-3 template void BTree::Print(BTreeNode *start, int n){ if (NULL == start){ return; } if (start->m_ptr[0]){ Print(start->m_ptr[0], n+1); //print the first child tree } else { for (int j=0; jm_nsize; i++){ //print the orther child tree 数据结构算法实现 2008-9-3 for (int j=0; jm_pkey[i] << "--->" <m_ptr[i+1]){ Print(start->m_ptr[i+1], n+1); } else { for (int j=0; j void BTree::Print(){ Print(m_proot); } template int BTree::Size(BTreeNode *root){ if (NULL == root){ return 0; } int size=root->m_nsize; for (int i=0; i<=root->m_nsize; i++){ if (root->m_ptr[i]){ size += this->Size(root->m_ptr[i]); } } 数据结构算法实现 2008-9-3 return size; } template int BTree::Size(){ return this->Size(this->m_proot); } template BTreeNode* BTree::GetParent(const Type item){ Triple result = this->Search(item); return result.m_pfind->m_pparent; } test.cpp #include #include 数据结构算法实现 2008-9-3 using namespace std; #include "BTree.h" int main(){ BTree btree(3); int init[]={1,3,5,7,4,2,8,0,6,9,29,13,25,11,32,55,34,22,76,45 ,14,26,33,88,87,92,44,54,23,12,21,99,19,27,57,18,72,124,158,234 ,187,218,382,122,111,222,333,872,123}; for (int i=0; i<49; i++){ btree.Insert(init[i]); } 数据结构算法实现 2008-9-3 btree.Print(); cout << endl << endl << endl; Triple result = btree.Search(13); cout << result.m_pfind->GetKey(result.m_nfind) << endl; cout << endl << endl << endl; for (int i=0; i<49; i++){ btree.Remove(init[i]); btree.Print(); cout << endl << endl << endl; } 数据结构算法实现 2008-9-3 return 0; } 17、图 MinHeap.h template class MinHeap{ public: MinHeap(Type heap[],int n); //initialize heap by a array ~MinHeap(){ delete[] m_pheap; } public: bool Insert(const Type item); 数据结构算法实现 2008-9-3 bool DeleteMin(Type &first); private: void Adjust(const int start, const int end); //adjust the elements from start to end private: const int m_nMaxSize; Type *m_pheap; int m_ncurrentsize; }; template void MinHeap::Adjust(const int start, const int end){ int i = start,j = i*2+1; Type temp=m_pheap[i]; 数据结构算法实现 2008-9-3 while(j <= end){ if(jm_pheap[j+1]){ j++; } if(temp <= m_pheap[j]){ break; } else{ m_pheap[i] = m_pheap[j]; i = j; j = 2*i+1; } } m_pheap[i] = temp; } 数据结构算法实现 2008-9-3 template MinHeap::MinHeap(Type heap[], int n):m_nMaxSize(n){ m_pheap = new Type[m_nMaxSize]; for(int i=0; i=0){ Adjust(pos, n-1); pos--; } } template bool MinHeap::DeleteMin(Type &first){ 数据结构算法实现 2008-9-3 first = m_pheap[0]; m_pheap[0] = m_pheap[m_ncurrentsize-1]; m_ncurrentsize--; Adjust(0, m_ncurrentsize-1); return 1; } template bool MinHeap::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr<<"Heap Full!"< 0){ if(m_pheap[i] <= temp){ break; } else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; } } m_pheap[j] = temp; m_ncurrentsize++; return 1; } 数据结构算法实现 2008-9-3 Edge.h template struct Edge{ public: Edge(int dest, DistType cost): m_ndest(dest), m_cost(cost), m_pnext(NULL){} public: int m_ndest; DistType m_cost; Edge *m_pnext; }; Vertex.h 数据结构算法实现 2008-9-3 #include "Edge.h" template struct Vertex{ public: Vertex(): adj(NULL){} NameType m_data; Edge *adj; ~Vertex(); }; template Vertex::~Vertex(){ Edge *pmove = adj; while (pmove){ adj = pmove->m_pnext; delete pmove; 数据结构算法实现 2008-9-3 pmove = adj; } } Graph.h #include "Vertex.h" template class Graph{ public: Graph(int size = m_nDefaultSize); //create the Graph with the most vertex of size ~Graph(); bool GraphEmpty() const{ //Is empty? return 0 == m_nnumvertex; } 数据结构算法实现 2008-9-3 bool GraphFull() const{ //Is full? return m_nMaxNum == m_nnumvertex; } int NumberOfVertex() const{ //get the number of vertex return m_nnumvertex; } int NumberOfEdge() const{ //get the number of edge return m_nnumedges; } NameType GetValue(int v); //get the value of the vth vertex DistType GetWeight(int v1, int v2); //get the weight between v1 and v2 int GetFirst(int v); //get the first neighbor vertex of v int GetNext(int v1, int v2);//get the next neighbor vertex of v1 behind v2 bool InsertVertex(const NameType vertex); //insert vertex with the name of vertex bool Removevertex(int v); //remove the vth vertex 数据结构算法实现 2008-9-3 //insert the edge between v1 and v2 bool InsertEdge(int v1, int v2, DistType weight=m_Infinity); bool RemoveEdge(int v1, int v2); //delete the edge between v1 and v2 void Print(); //print the graph Edge *GetMin(int v, int *visited); //get the min weight of the neighbor vertex of v void Prim(Graph &graph); //get the minimize span tree void DFS(int v, int *visited); //depth first search void DFS(); void Dijkstra(int v, DistType *shotestpath); //get the min weight from v to other vertex 数据结构算法实现 2008-9-3 private: Vertex *m_pnodetable; //neighbor list int m_nnumvertex; const int m_nMaxNum; static const int m_nDefaultSize = 10; //the default maximize vertex static const DistType m_Infinity = 100000; //there is no edge int m_nnumedges; int Getvertexpos(const NameType vertex); //get the vertex's position with the name of vertex }; template Graph::Graph(int size) : m_nnumvertex(0), m_nMaxNum(size), m_nnumedges(0){ m_pnodetable = new Vertex[size]; 数据结构算法实现 2008-9-3 } template Graph::~Graph(){ Edge *pmove; for (int i=0; im_nnumvertex; i++){ pmove = this->m_pnodetable[i].adj; if (pmove){ this->m_pnodetable[i].adj = pmove->m_pnext; delete pmove; pmove = this->m_pnodetable[i].adj; } } delete[] m_pnodetable; } 数据结构算法实现 2008-9-3 template int Graph::GetFirst(int v){ if (v<0 || v>=this->m_nnumvertex){ return -1; } Edge *ptemp = this->m_pnodetable[v].adj; return m_pnodetable[v].adj ? m_pnodetable[v].adj->m_ndest : -1; } template int Graph::GetNext(int v1, int v2){ if (-1 != v1){ Edge *pmove = this->m_pnodetable[v1].adj; while (NULL != pmove->m_pnext){ if (pmove->m_ndest==v2){ 数据结构算法实现 2008-9-3 return pmove->m_pnext->m_ndest; } pmove = pmove->m_pnext; } } return -1; } template NameType Graph::GetValue(int v){ if (v<0 || v>=this->m_nnumvertex){ cerr << "The vertex is not exsit" < int Graph::Getvertexpos(const NameType vertex){ for (int i=0; im_nnumvertex; i++){ if (vertex == m_pnodetable[i].m_data){ return i; } } return -1; } template DistType Graph::GetWeight(int v1, int v2){ 数据结构算法实现 2008-9-3 if (v1>=0 && v1m_nnumvertex && v2>=0 && v2m_nnumvertex){ if (v1 == v2){ return 0; } Edge *pmove = m_pnodetable[v1].adj; while (pmove){ if (pmove->m_ndest == v2){ return pmove->m_cost; } pmove = pmove->m_pnext; } } return m_Infinity; } 数据结构算法实现 2008-9-3 template bool Graph::InsertEdge(int v1, int v2, DistType weight){ if (v1>=0 && v1m_nnumvertex && v2>=0 && v2m_nnumvertex){ Edge *pmove = m_pnodetable[v1].adj; if (NULL == pmove){ //the first neighbor m_pnodetable[v1].adj = new Edge(v2, weight); return 1; } while (pmove->m_pnext){ if (pmove->m_ndest == v2){ break; } pmove = pmove->m_pnext; } if (pmove->m_ndest == v2){ //if the edge is exist, change the weight 数据结构算法实现 2008-9-3 pmove->m_cost = weight; return 1; } else{ pmove->m_pnext = new Edge(v2, weight); return 1; } } return 0; } template bool Graph::InsertVertex(const NameType vertex){ int i = this->Getvertexpos(vertex); if (-1 != i){ this->m_pnodetable[i].m_data = vertex; 数据结构算法实现 2008-9-3 } else{ if (!this->GraphFull()){ this->m_pnodetable[this->m_nnumvertex].m_data = vertex; this->m_nnumvertex++; } else{ cerr << "The Graph is Full" < bool Graph::RemoveEdge(int v1, int v2){ 数据结构算法实现 2008-9-3 if (v1>=0 && v1m_nnumvertex && v2>=0 && v2m_nnumvertex){ Edge *pmove = this->m_pnodetable[v1].adj, *pdel; if (NULL == pmove){ cerr << "the edge is not exist!" <m_ndest == v2){ //the first neighbor this->m_pnodetable[v1].adj = pmove->m_pnext; delete pmove; return 1; } while (pmove->m_pnext){ if (pmove->m_pnext->m_ndest == v2){ pdel = pmove->m_pnext; pmove->m_pnext = pdel->m_pnext; 数据结构算法实现 2008-9-3 delete pdel; return 1; } pmove = pmove->m_pnext; } } cerr << "the edge is not exist!" < bool Graph::Removevertex(int v){ if (v<0 || v>=this->m_nnumvertex){ cerr << "the vertex is not exist!" << endl; return 0; } 数据结构算法实现 2008-9-3 Edge *pmove, *pdel; for (int i=0; im_nnumvertex; i++){ pmove = this->m_pnodetable[i].adj; if (i != v){ //delete the edge point to v if (NULL == pmove){ continue; } if (pmove->m_ndest == v){ this->m_pnodetable[i].adj = pmove->m_pnext; delete pmove; continue; } else { if (pmove->m_ndest > v){ //the vertex more than v subtract 1 pmove->m_ndest--; 数据结构算法实现 2008-9-3 } } while (pmove->m_pnext){ if (pmove->m_pnext->m_ndest == v){ pdel = pmove->m_pnext; pmove->m_pnext = pdel->m_pnext; delete pdel; } else { if (pmove->m_pnext->m_ndest > v){ pmove->m_pnext->m_ndest--; pmove = pmove->m_pnext; } } } 数据结构算法实现 2008-9-3 } else { //delete the edge point from v while (pmove){ this->m_pnodetable[i].adj = pmove->m_pnext; delete pmove; pmove = this->m_pnodetable[i].adj; } } } this->m_nnumvertex--; for (int i=v; im_nnumvertex; i++) //delete the vertex { this->m_pnodetable[i].adj = this->m_pnodetable[i+1].adj; this->m_pnodetable[i].m_data = this->m_pnodetable[i+1].m_data; } 数据结构算法实现 2008-9-3 this->m_pnodetable[this->m_nnumvertex].adj = NULL; return 1; } template void Graph::Print(){ Edge *pmove; for (int i=0; im_nnumvertex; i++){ cout << this->m_pnodetable[i].m_data << "--->"; pmove = this->m_pnodetable[i].adj; while (pmove){ cout << pmove->m_cost << "--->" << this->m_pnodetable[pmove->m_ndest].m_data << "--->"; pmove = pmove->m_pnext; } cout << "NULL" << endl; 数据结构算法实现 2008-9-3 } } template void Graph::Prim(Graph &graph){ int *node = new int[this->m_nnumvertex]; //using for store the vertex visited int *visited = new int[this->m_nnumvertex]; int count = 0; Edge *ptemp, *ptemp2 = new Edge(0, this->m_Infinity), *pmin; int min; for (int i=0; im_nnumvertex; i++){ graph.InsertVertex(this->m_pnodetable[i].m_data); node[i] = 0; visited[i] = 0; } 数据结构算法实现 2008-9-3 visited[0] = 1; while(++count < this->m_nnumvertex){ pmin = ptemp2; pmin->m_cost = this->m_Infinity; //get the minimize weight between the vertex visited and the vertex which is not visited for (int i=0; im_cost > ptemp->m_cost){ pmin = ptemp; min = node[i]; 数据结构算法实现 2008-9-3 } } node[count] = pmin->m_ndest; visited[node[count]] = 1; graph.InsertEdge(pmin->m_ndest, min, pmin->m_cost); graph.InsertEdge(min, pmin->m_ndest, pmin->m_cost); } graph.DFS(); delete ptemp2; delete[] node; delete[] visited; } template void Graph::DFS(int v, int *visited){ 数据结构算法实现 2008-9-3 cout << "--->" << this->GetValue(v); visited[v] = 1; int weight = this->GetFirst(v); while (-1 != weight){ if (!visited[weight]){ cout << "--->" << this->GetWeight(v, weight); DFS(weight, visited); } weight = this->GetNext(v, weight); } } template void Graph::DFS(){ int *visited = new int[this->m_nnumvertex]; 数据结构算法实现 2008-9-3 for (int i=0; im_nnumvertex; i++){ visited[i] = 0; } cout << "head"; DFS(0, visited); cout << "--->end"; } template Edge* Graph::GetMin(int v, int *visited){ Edge *pmove = this->m_pnodetable[v].adj, *ptemp = new Edge(0, this->m_Infinity), *pmin = ptemp; while (pmove){ if (!visited[pmove->m_ndest] && pmin->m_cost>pmove->m_cost){ pmin = pmove; 数据结构算法实现 2008-9-3 } pmove = pmove->m_pnext; } if (pmin == ptemp){ delete ptemp; return NULL; } delete ptemp; return pmin; } template void Graph::Dijkstra(int v, DistType *shotestpath){ int *visited = new int[this->m_nnumvertex]; int *node = new int[this->m_nnumvertex]; for (int i=0; im_nnumvertex; i++){ 数据结构算法实现 2008-9-3 visited[i] = 0; node[i] = 0; shotestpath[i] = this->GetWeight(v, i); } visited[v] = 1; for (int i=1; im_nnumvertex; i++){ DistType min = this->m_Infinity; int u=v; for (int j=0; jm_nnumvertex; j++){ //get the minimize weight if (!visited[j] && shotestpath[j]m_nnumvertex; w++){ //change the weight from v to other vertex DistType weight = this->GetWeight(u, w); if (!visited[w] && weight!=this->m_Infinity && shotestpath[u]+weight using namespace std; #include "Graph.h" int main(){ Graph graph,graph2; int shotestpath[7]; char *vertex[] = {"地大", "武大", "华科", "交大", "北大", "清华", "复旦"}; int edge[][3] = {{0, 1, 43}, {0, 2, 12}, {1, 2, 38}, {2, 3 ,1325} ,{3, 6, 55}, {4, 5, 34}, {4, 6, 248}}; for (int i=0; i<7; i++){ 数据结构算法实现 2008-9-3 graph.InsertVertex(vertex[i]); } graph.Print(); cout << endl << endl <" << graph.GetValue(i) << ": " << shotestpath[i] < class Element{ public: 数据结构算法实现 2008-9-3 Type GetKey(){ return key; } void SetKey(Type item){ key = item; } public: Element& operator =(Element copy){ key = copy.key; return *this; } bool operator ==(Element item){ 数据结构算法实现 2008-9-3 return this->key == item.key; } bool operator !=(Element item){ return this->key != item.key; } bool operator <(Element item){ return this->key < item.key; } bool operator >(Element item){ return this->key > item.key; } 数据结构算法实现 2008-9-3 bool operator >=(Element item){ return this->key >= item.key; } bool operator <=(Element item){ return this->key <= item.key; } private: Type key; }; template class Sort; template class DataList{ 数据结构算法实现 2008-9-3 public: friend class Sort; DataList(int size=m_nDefaultSize): m_nMaxSize(size), m_ncurrentsize(0){ m_pvector = new Element[size]; } DataList(Type *data, int size); bool Insert(Type item); ~DataList(){ delete[] m_pvector; } int Size(){ return this->m_ncurrentsize; 数据结构算法实现 2008-9-3 } void Swap(Element &left, Element &right){ Element temp = left; left = right; right = temp; } void Print(); private: static const int m_nDefaultSize = 10; Element *m_pvector; const int m_nMaxSize; int m_ncurrentsize; }; 数据结构算法实现 2008-9-3 template DataList::DataList(Type *data, int size) : m_nMaxSize(size > m_nDefaultSize ? size : m_nDefaultSize), m_ncurrentsize(0){ this->m_pvector = new Element[size]; for (int i=0; im_pvector[i].SetKey(data[i]); } this->m_ncurrentsize += size; } template bool DataList::Insert(Type item){ if (this->m_ncurrentsize == this->m_nMaxSize){ cerr << "The list is full!" <m_pvector[this->m_ncurrentsize++].SetKey(item); } template void DataList::Print(){ cout << "The list is:"; for (int i=0; im_ncurrentsize; i++){ cout << " " << this->m_pvector[i].GetKey(); } } QueueNode.h #include "QueueNode.h" template class LinkQueue{ 数据结构算法实现 2008-9-3 public: LinkQueue():m_prear(NULL),m_pfront(NULL){} ~LinkQueue(){ MakeEmpty(); } void Append(const Type item); Type Delete(); Type GetFront(); void MakeEmpty(); bool IsEmpty() const{ return m_pfront==NULL; } void Print(); private: 数据结构算法实现 2008-9-3 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; } } template void LinkQueue::Append(const Type item){ if(m_pfront==NULL){ m_pfront=m_prear=new QueueNode(item); 数据结构算法实现 2008-9-3 } 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; 数据结构算法实现 2008-9-3 return temp; } template Type LinkQueue::GetFront(){ if(IsEmpty()){ cout<<"There is no element!"<m_data; } template void LinkQueue::Print(){ QueueNode *pmove=m_pfront; cout<<"front"; while(pmove){ 数据结构算法实现 2008-9-3 cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->rear"< class LinkQueue{ public: LinkQueue():m_prear(NULL),m_pfront(NULL){} ~LinkQueue(){ MakeEmpty(); 数据结构算法实现 2008-9-3 } void Append(const Type item); Type Delete(); Type GetFront(); void MakeEmpty(); bool IsEmpty() const{ return m_pfront==NULL; } void Print(); private: QueueNode *m_prear,*m_pfront; }; template void LinkQueue::MakeEmpty(){ 数据结构算法实现 2008-9-3 QueueNode *pdel; while(m_pfront){ pdel=m_pfront; m_pfront=m_pfront->m_pnext; delete pdel; } } 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); } 数据结构算法实现 2008-9-3 } 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(){ 数据结构算法实现 2008-9-3 if(IsEmpty()){ cout<<"There is no element!"<m_data; } template void LinkQueue::Print(){ QueueNode *pmove=m_pfront; cout<<"front"; while(pmove){ cout<<"--->"<m_data; pmove=pmove->m_pnext; } cout<<"--->rear"< class Sort{ public: void InsertSort(DataList &list, int n=-1); void BinaryInsertSort(DataList &list, int n=-1); void ShellSort(DataList &list, const int gap=-1); void BubbleSort(DataList &list); void QuickSort(DataList &list, int left=0, int right=-3); void SelectSort(DataList &list); 数据结构算法实现 2008-9-3 void HeapSort(DataList &list); void MergeSort(DataList &list); void RadixSort(DataList &list, int m, int d); //just use for integer! private: void BubbleSwap(DataList &list, const int n, int &flag); void SelectChange(DataList &list, const int n); void HeapAdjust(DataList &list, const int start, const int end); void Merge(DataList &list, DataList &mergedlist, const int len); void MergeDouble(DataList &list, DataList &mergedlist, const int start, const int part, const int end); }; template void Sort::InsertSort(DataList &list, int n){ 数据结构算法实现 2008-9-3 if (-1 == n){ for (int i=1; i temp = list.m_pvector[n]; int i; for (i=n; i>0; i--){ if (temp > list.m_pvector[i-1]){ break; } else{ list.m_pvector[i] = list.m_pvector[i-1]; 数据结构算法实现 2008-9-3 } } list.m_pvector[i] = temp; } template void Sort::BinaryInsertSort(DataList &list, int n){ if (-1 == n){ for (int i=1; i temp = list.m_pvector[n]; int left = 0, right = n-1; while(left <= right){ 数据结构算法实现 2008-9-3 int middle = (left + right) / 2; if (temp < list.m_pvector[middle]){ right = middle - 1; } else { left = middle + 1; } } for (int i=n-1; i>=left; i--){ list.m_pvector[i+1] = list.m_pvector[i]; } list.m_pvector[left] = temp; } template void Sort::ShellSort(DataList &list, const int gap){ 数据结构算法实现 2008-9-3 if (-1 == gap){ int gap = list.m_ncurrentsize / 2; while (gap){ ShellSort(list, gap); gap = (int)(gap / 2); } return; } for (int i=gap; i void Sort::BubbleSwap(DataList &list, const int n, int &flag){ 数据结构算法实现 2008-9-3 flag = 0; for (int i=list.m_ncurrentsize-1; i>=n; i--){ if (list.m_pvector[i-1] > list.m_pvector[i]){ list.Swap(list.m_pvector[i-1], list.m_pvector[i]); flag = 1; } } } template void Sort::BubbleSort(DataList &list){ int flag = 1, n = 0; while (++n void Sort::QuickSort(DataList &list, int left=0, int right=-1){ if (-3 == right){ right = list.m_ncurrentsize - 1; } if (left < right){ int pivotpos = left; Element pivot = list.m_pvector[left]; for (int i=left+1; i<=right; i++){ if (list.m_pvector[i] void Sort::SelectChange(DataList &list, const int n){ int j = n; for (int i=n+1; i void Sort::SelectSort(DataList &list){ for (int i=0; i void Sort::HeapAdjust(DataList &list, const int start, const int end){ int current = start, child = 2 * current + 1; Element temp = list.m_pvector[start]; while (child <= end){ if (child= list.m_pvector[child]){ break; } else { list.m_pvector[current] = list.m_pvector[child]; current = child; child = 2 * current + 1; } } list.m_pvector[current] = temp; } template void Sort::HeapSort(DataList &list){ 数据结构算法实现 2008-9-3 for (int i=(list.m_ncurrentsize-2)/2; i>=0; i--){ HeapAdjust(list, i, list.m_ncurrentsize-1); } for (int i=list.m_ncurrentsize-1; i>=1; i--){ list.Swap(list.m_pvector[0], list.m_pvector[i]); HeapAdjust(list, 0, i-1); } } template void Sort::MergeDouble(DataList &list, DataList &mergedlist, const int start, const int part, const int end){ int i = start, j = part + 1, k = start; while (i<=part && j<=end){ if (list.m_pvector[i] <= list.m_pvector[j]){ 数据结构算法实现 2008-9-3 mergedlist.m_pvector[k++] = list.m_pvector[i++]; } else { mergedlist.m_pvector[k++] = list.m_pvector[j++]; } } if (i <= part){ for (int m=i; m<=part && k<=end;){ mergedlist.m_pvector[k++] = list.m_pvector[m++]; } } else { for (int m=j; m<=end && k<=end; m++){ mergedlist.m_pvector[k++] = list.m_pvector[m]; } 数据结构算法实现 2008-9-3 } } template void Sort::Merge(DataList &list, DataList &mergedlist, const int len){ int n = 0; while (n+2*len < list.m_ncurrentsize){ MergeDouble(list, mergedlist, n, n+len-1, n+2*len-1); n += 2*len; } if (n+len < list.m_ncurrentsize){ MergeDouble(list, mergedlist, n, n+len-1, list.m_ncurrentsize-1); } else { for (int i=n; i void Sort::MergeSort(DataList &list){ DataList temp(list.m_nMaxSize); temp.m_ncurrentsize = list.m_ncurrentsize; int len = 1; while (len < list.m_ncurrentsize){ Merge(list, temp, len); len *= 2; Merge(temp, list, len); len *= 2; } } 数据结构算法实现 2008-9-3 template void Sort::RadixSort(DataList &list, int m, int d){ LinkQueue *queue = new LinkQueue[d]; int power = 1; for (int i=0; i using namespace std; #include "Sort.h" int main(){ 数据结构算法实现 2008-9-3 int init[15]={1,3,5,7,4,2,8,0,6,9,29,13,25,11,32}; DataList data(init, 15); Sort sort; data.Print(); cout << endl << endl <

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ]
0 人已下载

下载文档

相关文档