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


(4)后缀表达式求值

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

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)//
{
cout<<"Stack overflow"<<endl;
return;
}
top++;
StackList[top]=item;
cout<<"Now push"<<item<<endl;
return;
}

template<class T>
T Stack<T>::Pop(void)
{
T temp;
if(top==-1)
{
cout<<"Attemp to pop an empty stack"<<endl;
return NULL;
}
temp=StackList[top];
top--;
cout<<"Now pop"<<temp<<endl;
return temp;
}

template<class T>
T Stack<T>::Peek(void) const
{
if(top==-1)
{
cout<<"Attemp to peek an empty stack"<<endl;
return;
}
return StackList[top];
cout<<"Now peek"<<StackList[top]<<endl;
return;
}

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;
}

class Calculator
{
private:
Stack<double> s;
public: void Enter(double operand);
void GetTwoOperand(double & operand1,double & operand2);
void Compute(char op);
void Clear(void);
void Run(void);
};

void Calculator::Enter(double operand)
{
s.Push(operand);
cout<<"A new node is pushed with the value"<<operand<<endl;
}

void Calculator::GetTwoOperand(double & operand1,double & operand2)
{
if(s.StackEmpty())
{
cout<<"No operand to be poped"<<endl;
s.ClearStack();
exit(1);
}
operand1=s.Pop();
if(s.StackEmpty())
{
cout<<"No operand to be poped"<<endl;
s.ClearStack();
exit(1);
}
operand2=s.Pop();
}

void Calculator::Compute(char op)
{
double operand1,operand2,result;
GetTwoOperand(operand1,operand2);
switch(op)
{
case'+':result=operand1+operand2;
break;
case'-':result=operand1-operand2;
break;
case'*':result=operand1*operand2;
break;
case'/':
if(operand2==0)
{
cout<<"Divided by 0!"<<endl;
s.ClearStack();
exit(1);
}
else
result=operand1/operand2;
break;
}
s.Push(result);
}

void Calculator::Clear(void)
{
s.ClearStack();
}

void Calculator::Run(void)
{
char op;
double operand;
cin>>op;
if(op!='=')
while(op!='=')
{
switch(op)
{
case'+':
Compute(op);
break;
case'-':
Compute(op);
break;
case'*':
Compute(op);
break;
case'/':
Compute(op);
break;
default:
cin.putback(op);
cin>>operand;
Enter(operand);
break;
}
cin>>op;
}
cout<<"Succeed"<<endl;
cout<<"The result is"<<s.Pop()<<endl;
Clear();
}

int main()
{
Stack<int> sti;
sti.Push(1);
sti.Push(2);
sti.Push(3);
cout<<"The size of the stack is"<<sti.StackSize()<<endl;
cout<<sti.Pop()<<endl;
cout<<sti.Pop()<<endl;
cout<<sti.Pop()<<endl;
Calculator c;
c.Run();
return 1;
}




(5)结点类及其操作

#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>
template <class T>
class Node
{
private:
Node<T> * next;
public:
T data;
Node(const T & item,Node<T> * ptrnext=NULL);
void InsertAfter(Node<T> * p);
Node<T> * DeleteAfter(void);
Node<T> * NextNode(void) const;
};

template <class T>
Node<T>::Node(const T & item,Node<T> * ptrnext)
{
data=item;
next=ptrnext;
cout<<"A node is created with value"<<data<<endl;
}

template <class T>
void Node<T>::InsertAfter(Node<T> * p)
{
p->next=next;
next=p;
cout<<"A node is inserted with value"<<p->data<<endl;
}

template <class T>
Node<T> * Node<T>::DeleteAfter(void)
{
if(next==NULL)
{
cout<<"Useless delete"<<endl;
return NULL;
}
Node<T> * currptr=next;
next=currptr->next;
cout<<"A node is deleted with value"<<currptr->data<<endl;
return currptr;
}

template <class T>
Node<T> * Node<T>::NextNode(void) const
{
return next;
}

template <class T>//工具函数1(生成结点)
Node<T> * GetNode(const T & item,Node<T> * nextptr=NULL)
{
Node<T> * NewNode;
NewNode=new Node<T>(item,nextptr);
if(NewNode==NULL)
{
cout<<"Momery allocation failure!"<<endl;
exit(1);
}
return NewNode;
}

template <class T>//工具函数2(表头插入)
void InsertFront(Node<T> *& head,T item)
{
Node<T> * ptr=GetNode(item,head);
head=ptr;
}

template<class T>//工具函数3(遍历链表)
void PrintList(Node<T> * head)
{
Node<T> * currptr=head;
int count=0;
while(currptr!=NULL)
{
cout<<currptr->data<<" "<<endl;
count++;
currptr=currptr->NextNode();
}
}

template <class T>//工具函数4(表尾插入)
void InsertRear(Node<T> *& head,const T& item)
{
Node<T> * currptr=head;
if(currptr==NULL)
InsertFront(head,item);
{
while(currptr->NextNode()!=NULL)
currptr=currptr->NextNode();
Node<T> * NewNode;
NewNode=GetNode(item);
currptr->InsertAfter(NewNode);
}
}

int main()
{
Node<int> * head=GetNode(1);
InsertFront(head,2);
InsertRear(head,3);
PrintList(head);
cout<<":)"<<endl;
return 1;
}