几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)

(6)动态数组

#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>

template <class T>
class Array
{
private:
int FSize;
T * AList;
void Allocate();
public:
Array(int sz=50);
Array(const Array<T> & x);
~Array()
{
delete[] AList;
}
T operator[](int i);
int ListSize(void) const
{
return FSize;
}
void Resize(int NewSize);
void Set(int pos,T item);
};

template <class T>
void Array<T>::Allocate()
{
AList=new T[FSize];
if(AList==NULL)
{
cout<<"Memory allocation fail"<<endl;
return;
}
}

template <class T>
Array<T>::Array(int sz)
{
if(sz<0)
{
cout<<"Invalid array size"<<endl;
return;
}
FSize=sz;
Allocate();
cout<<"Create a new array"<<endl;
return;
}

template <class T>
Array<T>::Array(const Array<T> & x)
{
FSize=x.FSize;
Allocate();
for(int i=0;i<FSize;i++)
AList[i]=x.AList[i];
cout<<"Create a new array using an older one"<<endl;
}

template <class T>
T Array<T>::operator [](int i)
{
if((i<0)||(i>FSize))
{
cout<<"Invalid index."<<endl;
return (T)NULL;
}
return AList[i];
}

template <class T>
void Array<T>::Resize(int NewSize)
{
int a=0;
if(NewSize<0)
{
cout<<"Invalid Array size."<<endl;
exit(1);
}
if(NewSize!=FSize)
{
T * NewArray=new T[NewSize];
if(NewArray==NULL)
{
cout<<"Memory allocation fail."<<endl;
return;
}
int n=(NewSize<=FSize?NewSize:FSize);
for(int i=0;i<n;i++)
NewArray[i]=AList[i];
delete[] AList;
AList=NewArray;
a=FSize;
FSize=NewSize;
}
cout<<"The size of the array is not"<<a<<"but"<<FSize<<endl;
return;
}

template <class T>
void Array<T>::Set(int pos,T item)
{
if((pos<0)||(pos>=FSize))
{
cout<<"Can not do such work"<<endl;
return;
}
AList[pos]=item;
return;
}

int main()
{
Array<int> ai(100);
ai.Set(0,0);
ai.Set(1,1);
ai.Set(2,2);
cout<<ai[0]<<endl;
cout<<ai[1]<<endl;
cout<<ai[2]<<endl;
ai.Resize(100);
cout<<ai[0]<<endl;
cout<<ai[1]<<endl;
cout<<ai[2]<<endl;
Array<int> ai2(ai);
cout<<ai2[0]<<endl;
cout<<ai2[1]<<endl;
cout<<ai2[2]<<endl;
return 1;
}
(7)线索二叉树(上）

#include "stdafx.h"
#include <iostream.h>
#include<stdlib.h>

template<class T>
class Queue
{
private:
T QList[50];
int front,rear,count;
public:
Queue(void);
void QInsert(const T & item);
T QDelete(void);
void ClearQueue(void);
T QFront(void) const;
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};

template<class T>
Queue<T>::Queue(void)
{
front=0;
rear=0;
count=0;
}

template<class T>
void Queue<T>::QInsert(const T & item)
{
if(count==50)
return;
count++;
QList[rear]=item;
rear=(rear+1)%50;
return;
}

template<class T>
T Queue<T>::QDelete(void)
{
if(count==0)
exit(1);
T temp;
temp=QList[front];
count--;
front=(front+1)%50;
return temp;
}

template<class T>
void Queue<T>::ClearQueue(void)
{
front=0;
rear=0;
count=0;
return;
}

template<class T>
T Queue<T>::QFront(void) const
{
if(count==0)
exit(1);
T temp;
temp=QList[front];
return QList[front];
}

template<class T>
int Queue<T>::QLength(void) const
{
return count;
}

template<class T>
int Queue<T>::QEmpty(void) const
{
return (count==0);
}

template<class T>
int Queue<T>::QFull(void) const
{
return (count==50);
}

template<class T>
class Stack
{
private:
T StackList[50];
int top;
public:
Stack(void);
void Push(const T& item);
T Pop(void);
void ClearStack(void);
T Peek(void) const;
int StackEmpty(void) const;
int StackFull(void) const;
int StackSize(void);
};

template<class T>
Stack<T>::Stack(void)
{
top=-1;
}

template<class T>
void Stack<T>::Push(const T& item)
{
if(top==49)
return;
top++;
StackList[top]=item;
return;
}

template<class T>
T Stack<T>::Pop(void)
{
T temp;
if(top==-1)
exit(1);
temp=StackList[top];
top--;
return temp;
}

template<class T>
T Stack<T>::Peek(void) const
{
if(top==-1)
exit(1);
return StackList[top];
}

template<class T>
int Stack<T>::StackEmpty(void) const
{
return (top==-1);
}

template<class T>
int Stack<T>::StackFull(void) const
{
return(top==49);
}

template<class T>
void Stack<T>::ClearStack(void)
{
top=-1;
}

template<class T>
int Stack<T>::StackSize(void)
{
return 50;
}

template <class T>
class ThreadTree;

template <class T>
class ThreadI;

template <class T>
class ThreadNode
{
friend class ThreadTree<T>;
friend class ThreadI<T>;
public:
int LeftThread,RightThread;
ThreadNode<T> * left;
ThreadNode<T> * right;
T data;

ThreadNode(T item) { LeftThread=1;RightThread=1;left=NULL;right=NULL;data=item;cout<<"A node is created"<<data<<endl;}
ThreadNode(ThreadNode<T> * temp) { LeftThread=temp->LeftThread;left=temp->left;RightThread=temp->RightThread;right=temp->right;data=temp->data;}
void InsertRight(ThreadNode<T> * & p);
void InsertLeft(ThreadNode<T> * & p);
void DeleteRight();
void DeleteLeft();
};

template <class T>
void ThreadNode<T>::InsertRight(ThreadNode<T> * & p)
{
if(p->right==NULL)
{
p->right=right;
p->RightThread=RightThread;
p->left=this;
p->LeftThread=1;
right=p;
RightThread=0;
cout<<"A node is created with value IR1"<<p->data<<data<<endl;
}
else
{
p->right=right;
p->RightThread=RightThread;
p->left=this;
p->LeftThread=1;
right=p->right;
ThreadNode<T> * temp=this->right;
while(this->LeftThread==0)
temp=temp->left;
temp->left=p;
cout<<"A node is created with the value IR2"<<p->data<<data<<endl;
}
}

template <class T>
void ThreadNode<T>::InsertLeft(ThreadNode<T> * & p)
{
if(p->left==NULL)
{
p->left=left;
p->LeftThread=LeftThread;
p->right=this;
p->RightThread=1;
left=p;
LeftThread=0;
cout<<"A node is created with value IL1"<<p->data<<data<<endl;
}
else
{
p->left=left;
p->LeftThread=LeftThread;
p->right=this;
p->RightThread=1;
right=p->right;
ThreadNode<T> * temp=this->left;
while(this->RightThread==0)
temp=temp->right;
temp->right=p;
cout<<"A node is created with the value IL2"<<p->data<<data<<endl;
}
}

template <class T>
void ThreadNode<T>::DeleteRight()
{
ThreadNode<T> * p=right;
if((RightThread==1)&&(LeftThread==1))
{
cout<<"Empty one "<<endl;
return;
}
if((p->RightThread==1)&&(p->LeftThread==1))
{
right=p->right;
RightThread=p->RightThread;
return;
}
if((p->RightThread==1)&&(p->LeftThread==0))
{
right=p->right;
ThreadNode<T> * temp=p->right;
while(temp->LeftThread==0)
temp=temp->left;
temp->left=this;
return;
}
if((p->RightThread==0)&&(p->LeftThread==1))
{
right=p->left;
ThreadNode<T> * temp=p->left;
while(temp->RightThread==0)
temp=temp->right;
temp->right=p->right;
return;
}
if((p->RightThread==0)&&(p->LeftThread==0))
{
ThreadNode<T> * temp=p->left;
while(temp->RightThread==0)
temp=temp->right;
ThreadNode<T> * temp1=p->right;
while(temp1->LeftThread==0)
temp1=temp1->left;
temp->right=p->right;
temp->RightThread=0;
right=p->left;
temp1->left=temp;
return;
}
return;
}

template <class T>
void ThreadNode<T>::DeleteLeft()
{
ThreadNode<T> * p=left;
if((RightThread==1)&&(LeftThread==1))
{
cout<<"Empty one "<<endl;
return;
}
if((p->RightThread==1)&&(p->LeftThread==1))
{
left=p->left;
LeftThread=p->LeftThread;
return;
}
if((p->RightThread==1)&&(p->LeftThread==0))
{
left=p->left;
ThreadNode<T> * temp=p->left;
while(temp->RightThread==0)
temp=temp->right;
temp->right=this;
return;
}
if((p->RightThread==0)&&(p->LeftThread==1))
{
left=p->right;
ThreadNode<T> * temp=p->right;
while(temp->LeftThread==0)
temp=temp->right;
temp->left=p->left;
return;
}
if((p->RightThread==0)&&(p->LeftThread==0))
{
ThreadNode<T> * temp=p->left;
while(temp->RightThread==0)
temp=temp->right;
ThreadNode<T> * temp1=p->right;
while(temp1->LeftThread==0)
temp1=temp1->left;
temp1->left=p->left;
temp1->LeftThread=0;
left=p->right;
temp->right=temp1;
return;
}
return;
}

[此贴子已经被作者于2006-2-10 0:51:42编辑过]