//#ifndef _STRUCTS_H
//#define _STRUCTS_H
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
//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;
virtual bool InsertSort()=0;
virtual bool create()=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;
bool InsertSort();
bool create();
};
class AList:public UList //矩陣操作類
{
Data *arr; // holds the dynamic Array
int num; // cells filled so far
public:
static 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;
bool InsertSort();
bool create();
};
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;};
};
//#endif
// structs.h end
//structs.cpp Begin
//#include"structs.h"
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<<endl<<"unknown option"<<endl;
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<place-1;++i) // forward till list(place-1)
tmp=tmp->next;
holder=tmp->next;
tmp->next=new Node(x);
tmp->next->next=holder;
}
++num;
return true;
}
bool PList::InsertSort() //鏈表的排序插入
{ Data D0;
int a;
cout<<"請輸入要插入的數"<<endl;
cin>>D0;
Node *tmp,*D1,*D2;
while(a==1){
if (begin==NULL)
{ tmp=begin;
begin=new Node(D0);
begin->next=tmp;
if (num==0) // in case is the only item in the list
{
end=begin;
end->next=NULL;
}
}
else
{ D1=begin;
while(D0<D1->item)
{ D2=D1;D1=D1->next; }
if(D1->next!=NULL)
{ tmp=new Node(D0);
D2->next=tmp;
tmp->next=D1->next;
}
else
{ tmp=new Node(D0);
D2->next=tmp;
tmp->next=NULL;
}
}
cout<<"是否繼續插入：1.Yes 2.No"<<endl;
cin>>a;
}
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<place-1;++i)
tmp=tmp->next;
delete end;
end=tmp;
end->next=NULL;
}
else
{
Node *holder;
for(int i=1;i<place-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<place;++i)
tmp = tmp->next;
ret = tmp->item;
return true;
}
bool PList::create() //創建鏈表
{ Node *p1,*p2;
p1=new Node(8);
cout<<"輸入數字：(輸入0結束)"<<endl;
cin>>p1->item;
while(p1->item!=0)
{ if(begin==NULL)
begin=p1;
else
p2->next=p1;
p2=p1;
p1=new Node(8);
cout<<"請輸入數字：(輸入0結束)"<<endl;
cin>>p1->item;
}
p2->next=NULL;
return true;
}
void PList::Print(void)const{ //輸出鏈表
if (num==0) return;
cout<<"head";
for(Node *tmp=begin;tmp!=NULL;tmp=tmp->next){
cout<<"->"<<tmp->item;
}
cout<<endl;
return;
}
bool AList::Insert(const Data &x,int place=1) //矩陣插入壹元素
{
if (num==MAX_SIZE) // if the array is full
for(int i=0;i<=num;i++)
{ Data *tmp;
tmp=new Data[MAX_SIZE+1];
tmp[i]=arr[i];
//delete []arr;
arr=tmp;
}
if((place<=0)||(place>num+1))
return false;
for(int i=num-1;i>=place-1;--i)
arr[i+1]=arr[i];
arr[place-1]=x;
++num;
++MAX_SIZE;
return true;
}
bool AList::InsertSort() //矩陣排序插入
{
if(num==MAX_SIZE)
{
Data *temp;
for(int i=0;i<=num;i++)
{ temp=new Data[MAX_SIZE+1];
temp[i]=arr[i];
}
MAX_SIZE++;
num++;
arr=temp;
}
Data D;
int a;
cout<<"輸入要插入的code:"<<endl;
cin>>D;
while(a==1){
for(int m=0;m<num;m++)
if(D>=arr[m])
{ for(int j=num;j>m+1;j--)
{ arr[j]=arr[j-1];
arr[m]=D;
}
arr[m+1]=D;
}
cout<<"是否繼續插入？1.Yes 2.No"<<endl;
cin>>a;
}
return true;
}
bool AList::Remove(int place) //矩陣移出壹元素
{
if((place<=0)||(place>num+1))
return false;
for(int i=place-1;i<num;++i)
arr[i]=arr[i+1];
--num;
return true;
}
int AList::Find(const Data &x) //矩陣查找壹元素
{
int i=0;
while((i<num)&&(arr[i]!=x)) ++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;
}
bool AList::create() //創建矩陣
{
int m;
cout<<"input name and code:"<<endl;
cin>>arr[0];
num++;
for(int i=1;i<4;i++)
{cout<<"是否繼續創建？"<<endl;
cout<<"1.Yes 2.No"<<endl;
cin>>m;
if (m==2)break;
else
{ cout<<"input name and code:"<<endl;
cin>>arr[i];
num++;
MAX_SIZE++;
}
}
cout<<"create successfully"<<endl;
return true;
}
void AList::Print()const //輸出矩陣
{
cout<<"head";
for(int i=0;i<num;++i) cout<<"->"<<arr[i];
cout<<endl;
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;
}
//structs.cpp End
//#include"structs.h"
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;
int max=AList::MAX_SIZE;
for(int i=0;i<max+1;++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_InsertSort(Kind k)
{
bool res=true;
UList *tmp=init_list(k);
if (!tmp->InsertSort())
{
cerr << "Failure on InsertSort test no. 1 - insert into a valid cell number" << endl;
res = false;
}
else
cout << "Success on InsertSort test no. 1 - insert into a valid cell number" << endl;
return true;
}
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<AList::MAX_SIZE+1;++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;
}
void Test_output(Kind k)
{
UList *tmp=init_list(k);
tmp->Print();
cout << "Success on output test no. 1 - Normal output" << endl;
}
void Test_outputstack(Kind k)
{
UStack *tmp = new UStack(k);
tmp->Print();
}
bool Test_create(Kind k)
{ UList *tmp=init_list(k);
tmp->create();
cout<<"Success on create test"<<endl;
return true;
}
int main()
{
while (1)
{
int ch;
Kind k;
cout<<"choose Kind"<<endl<<"1. Array"<<endl<<"2. Pointers"<<
endl<<"any other no. to exit"<<endl;
cin>>ch;
switch(ch){
case 1:
k=Array;
break;
case 2:
k=Pointers;
break;
default:
cout<<"bye bye"<<endl;
exit(0);
}
cout<<"choose test"<<endl<<"1. insert (LIST)"<<endl<<"2. remove (LIST)"<<endl
<<"3.insertsort(LIST)"<<endl<<"4.output (List)"<<endl<<"5.push (Stack)"<<endl
<<"6. pop (STACK)"<<endl<<"7.output (Stack)"<<endl<<"8.create (List)"<<endl<<"any other no. to exit"<<endl;
cin>>ch;
switch(ch){
case 1:
if(Test_insert(k))
cout<<endl<<"insert test seccessful"<<endl;
break;
case 2:
if(Test_remove(k))
cout<<endl<<"remove test seccessful"<<endl;
break;
case 3:
if(Test_InsertSort(k))
cout<<endl<<"insertsort test seccessful"<<endl;
break;
case 4:
Test_output(k);
break;
case 5:
if(Test_push(k))
cout<<endl<<"push test seccessful"<<endl;
break;
case 6:
if(Test_pop(k))
cout<<endl<<"pop test seccessful"<<endl;
break;
case 7:
Test_outputstack(k);
break;
case 8:
Test_create(k);
cout<<endl<<"create test seccessful"<<endl;
break;
default:
cout<<"goodbye"<<endl;
exit(0);
}
cout << endl << endl;
}
return 0;
}
//main.cpp end