visual c++ 课程设计 案例精选与编程指导 8-1答案

#include
#include
//using namespace std;
//---------------------------------------------------
typedef enum Kind {Array, Pointers} Kind;
typedef int Data;
//---------------------------------------------------
class UList //基类
{
public:
virtual int Size()=0;
virtual bool Insert(const Data&,int)=0;
virtual bool Remove(int)=0;
virtual int Find(const Data&)=0;
virtual bool Get(int, Data&)=0;
virtual void Print()const=0;
};
//-------------------------------------------------------------------------------------
class PList:public UList //链表操作类
{
class Node{
Data item;
Node *next;
public:
Node(const Data &dat):item(dat),next(NULL){} //初始化数据
Node(const Node &nod):item(nod.item),next(NULL){} //
friend class PList;
};
Node *begin; //指向头的指针
Node *end; //指向尾的指针
int num;
public:
PList():begin(NULL),end(NULL),num(0){}
~PList(){
Node *tmp=begin;
while(num>0){
begin=begin->next;
delete tmp;
tmp=begin;
}
}
/*函*/ int Size(){return num;}
/*数*/ bool Insert(const Data&,int);
/*伸*/ bool Remove(int);
int Find(const Data&);
bool Get(int, Data&);
/*明*/ void Print()const;
};
//----------------------------------------------------------------------------------
class AList:public UList //矩阵操作类
{
Data *arr; // holds the dynamic Array
int num; // cells filled so far
public:
static const int MAX_SIZE; // max_size beginning value
AList():arr(new Data[MAX_SIZE]),num(0){}
~AList(){delete[] arr;}
int Size(){return num;}
bool Insert(const Data&,int);
bool Remove(int);
int Find(const Data&);
bool Get(int, Data&);
void Print()const;
};
//--------------------------------------------------------------------
UList* init_list(Kind);
//--------------------------------------------------------------------
class UStack //堆栈操作类
{
UList *stk;
public:
UStack(Kind k) : stk(init_list(k)){};
bool Push(const Data&);
bool Top(Data&) const;
bool Pop(Data&);
void Print()const{stk->Print();return;};
};
//----------------------------------------------------------------------------
const int AList::MAX_SIZE = 4;
//----------------------------------------------------------------------------
UList* init_list(Kind k) //初始化函数
{
UList *tmp;
switch(k){
case Array:
tmp=new AList;
break;
case Pointers:
tmp=new PList;
break;
default:
cout< return NULL;
}
return tmp;
}
//----------------------------------------------------------------------------
bool PList::Insert(const Data &x,int place) //链表插入操作
{
Node *tmp;
if ((place<=0)||(place>num+1))
return false;
if (place==1) // insert at the begining of the list
{ //在链表头插入
tmp=begin;
begin=new Node(x);
begin->next=tmp;
if (num==0) // in case is the only item in the lis
{ //就一个数据
end=begin;
end->next=NULL;
}
}
else if (place==num+1) // insert at the end of list
{ //插到链表尾
tmp=end;
end=new Node(x);
end->next=NULL;
tmp->next=end;
}
else
{
Node *holder;
tmp=begin;
for(int i=1;i tmp=tmp->next; //链表倒数第二个
holder=tmp->next;
tmp->next=new Node(x);
tmp->next->next=holder;
}
++num;
return true;
}
//--------------------------------------------------------------------------------------
bool PList::Remove(int place) //链表移出操作
{
Node *tmp=begin;
if((place<=0)||(place>num+1))
return false;
if(place==1) // remove the 1st item
{ //删除第一个数据
begin=begin->next;
delete tmp;
}
else if(place==num) // remove the last item
{ //删除最后一个数据
for(int i=1;i tmp=tmp->next;//从头找到尾
delete end;
end=tmp;
end->next=NULL;
}
else
{
Node *holder;
for(int i=1;i tmp=tmp->next;
holder=tmp->next;
tmp->next=holder->next;
delete holder;
}
if(num==1)
end=begin=NULL;
--num;
return true;
}
//---------------------------------------------------------------------------------
int PList::Find(const Data &x) //链表节点查找
{
Node *tmp=begin;
int i=1;
while((tmp!=NULL)&&(tmp->item!=x))
{
++i;
tmp=tmp->next;
}
if (tmp==NULL)
return 0;
return i;
}
//---------------------------------------------------------------------------------
bool PList::Get(int place, Data &ret) //得到节点数据
{
Node *tmp=begin;
if((place<=0)||(place>num+1))
return false;
for(int i=1;i tmp = tmp->next;
ret = tmp->item;
return true;
}
//-----------------------------------------------------------------------------------
void PList::Print(void)const{ //输出链表
if (num==0) return;
cout<<"head";
for(Node *tmp=begin;tmp!=NULL;tmp=tmp->next){
cout<<"->"<item;
}
cout< return;
}
//------------------------------------------------------------------------------------------------
bool AList::Insert(const Data &x,int place=1) //矩阵插入一元素
{
if (num==MAX_SIZE) // if the array is full
return false;
if((place<=0)||(place>num+1))
return false;
for(int i=num;i>=place-1;--i)
arr[i+1]=arr[i];
arr[place-1]=x;
++num;
return true;
}
//---------------------------------------------------------------------------------------------
bool AList::Remove(int place) //矩阵移出一元素
{
if((place<=0)||(place>num+1))
return false;
for(int i=place-1;i arr[i]=arr[i+1];
--num;
return true;
}
//-------------------------------------------------------------------------------------------
int AList::Find(const Data &x) //矩阵查找一元素
{
int i=0;
while((i if (i==num) i=-1; // we got to the end of the array
return i+1;
}
//--------------------------------------------------------------------------------------------
bool AList::Get(int place, Data &ret) //得到元素值
{
if((place<=0)||(place>num+1))
return false;
ret = arr[place-1];
return true;
}
//-------------------------------------------------------------------------------------------
void AList::Print()const //输出矩阵
{
cout<<"head";
for(int i=0;i"< cout< return;
}
//-------------------------------------------------------------------------------------------
bool UStack::Push(const Data &dat) //压栈操作
{
return stk->Insert(dat,stk->Size()+1);
}
//-------------------------------------------------------------
bool UStack::Top(Data &ret)const //栈顶操作
{
int n=stk->Size();
if (n<=0) return false;
(void)stk->Get(n, ret);
return true;
}
//-------------------------------------------------------------
bool UStack::Pop(Data &ret) //出栈操作
{
int n=stk->Size();
if (n<=0) return false;
(void)stk->Get(n, ret);
(void)stk->Remove(n);
return true;
}
//-------------------------------------------------------------
// all the test functions return false if one of the tests fail or true if all the tests succeeded
// the function reports failures to the standard error output device
bool Test_insert (Kind k) //测试插入
{
bool res = true;
UList *tmp=init_list(k);
if (!tmp->Insert(5,1))
{
cerr << "Failure on Insert test no. 1 - insert into a valid cell number" << endl;
res = false;
}
else
cout << "Success on Insert test no. 1 - insert into a valid cell number" << endl;
if (tmp->Insert(3,tmp->Size()+2))
{
cerr << "Failure on Insert test no. 2 - insert into upper cell number" << endl;
res = false;
}
else
cout << "Success on Insert test no. 2 - insert into upper cell number" << endl;
if (tmp->Insert(3,0))
{
cerr << "Failure on Insert test no. 3 - insert into lower cell number" << endl;
res = false;
}
else
cout << "Success on Insert test no. 3 - insert into lower cell number" << endl;
if (k==Array)
{
bool ares=true;
for(int i=0;i {
ares=tmp->Insert(i,1);
}
if (ares)
{
cerr << "Failure on Insert test no. 4 - Array is full" << endl;
res = false;
}
else
cout << "Success on Insert test no. 4 - Array is full" << endl;
}
return res;
}
//-------------------------------------------------------------------------------------------
bool Test_remove (Kind k) //测试删除
{
bool res = true;
UList *tmp=init_list(k);
for (int i=0; i<10; ++i) // filling the list
{
(void)tmp->Insert(i, 1);
}
if (!tmp->Remove(5))
{
cerr << "Failure on Remove test no. 1 - remove from valid cell number" << endl;
res = false;
}
else
cout << "Success on Remove test no. 1 - remove from valid cell number" << endl;
if (tmp->Remove(12))
{
cerr << "Failure on Remove test no. 2 - remove from upper cell number" << endl;
res = false;
}
else
cout << "Success on Remove test no. 2 - remove from upper cell number" << endl;
if (tmp->Remove(0))
{
cerr << "Failure on Remove test no. 3 - remove from lower cell number" << endl;
res = false;
}
else
cout << "Success on Remove test no. 3 - remove from lower cell number" << endl;
return res;
}
//-------------------------------------------------------------------------------------------
bool Test_push (Kind k) //测试压栈
{
bool res = true;
UStack *tmp = new UStack(k);
if (!tmp->Push(7))
{
cerr << "Failure on Push test no. 1 - Normal push" << endl;
res = false;
}
else
cout << "Success on Push test no. 1 - Normal push" << endl;
if (k==Array)
{
bool ares=true;
for(int i=0;i {
ares=tmp->Push(i);
}
if (ares)
{
cerr << "Failure on Push test no. 2 - Array is full" << endl;
res = false;
}
else
cout << "Success on Push test no. 2 - Array is full" << endl;
}
return res;
}
//-------------------------------------------------------------------------------------------
bool Test_pop (Kind k) //测试弹出
{
bool res = true;
UStack *tmp = new UStack(k);
Data ret; // for testing purpuses
(void)tmp->Push(2);
if (!tmp->Pop(ret))
{
cerr << "Failure on Pop test no. 1 - Normal pop" << endl;
res = false;
}
else
cout << "Success on Pop test no. 1 - Normal pop" << endl;
if (tmp->Pop(ret))
{
cerr << "Failure on Pop test no. 2 - Pop from empty stack" << endl;
res = false;
}
else
cout << "Success on Pop test no. 2 - Pop from empty stack" << endl;
return res;
}
//------------------------------------------------------------------------------------------
int main()
{
while (1) //多次循环
{
int ch;
Kind k;
cout<<"choose Kind"< endl<<"any other no. to exit"< cin>>ch;
switch(ch){ //选择类型
case 1: //
k=Array; //
break; //
case 2: //
k=Pointers; //
break; //
default: //
cout<<"bye bye"< exit(0); //
} //
cout<<"choose test"< <<"3. push (STACK)"< cin>>ch;
switch(ch){
case 1:
if(Test_insert(k))
cout< break;
case 2:
if(Test_remove(k))
cout< break;
case 3:
if(Test_push(k))
cout< break;
case 4:
if(Test_pop(k))
cout< break;
default:
cout<<"goodbye"< exit(0);
}
cout << endl << endl;
}
return 0;
}