#include<iostream>
using namespace std;
enum order {no_order,inc_order,dec_order};
template <class type>
class Array{
public:
Array(int=10);
~Array()
{if (elements) delete[]elements;}
int Getsize() //获得数组的最大长度
{return size;}
order GetOrder()
{return myorder;} //获得数组排序状况
int GetUsed() //获得数组实际大小
{return used;}
void Sort();
void ReOrder();
int Search(type & x);
void Insert(type & x);
bool Delete(type & x);
bool Delete(int i);
void SwapElem(int i,int j);
bool Expand(int); //动态内存再分配
Array<type> & operator =(Array<type> & arr) //重载赋值运算符
{Copy(arr);return *this; }
type &operator [](const int i) //重载下标运算符
{return elements[i];}
friend ostream & operator << <>(ostream &,Array<type> &); //此处特别注意（http://blog.csdn.net/lxmuyu/article/details/7313830）
friend istream & operator >> <>(istream &,Array<type> &);
protected:
int size; //数组最大长度
int used; //数组的实际长度
type* elements; //用于存放数组元素
order myorder; //当前数组的排序情况
int LineSearch(type & x); //线性查找函数，适用于没有排序的数组
int BinSearch(type & x); //二分查找函数，适用于升序排列的数组
Array<type> & Copy(Array <type> & arr);
};
struct term{
int coef; //系数
int exp; //指数
bool operator !=(term & t)
{return coef!=t.coef||exp!=t.exp;}
bool operator >(term & t2)
{return exp>t2.exp;}
friend ostream & operator << (ostream & out,term &t)
{ out<<t.coef<<"x"<<t.exp<<" ";return out;}
friend istream & operator >> (istream & in,term &t)
{ in>>t.coef>>t.exp;return in;}
};
#include "stdafx.h"
#include"arr.h"
#include<assert.h>
template <class type>
Array<type>::Array(int arraysize){
myorder=no_order;
size=(arraysize>10)?arraysize:10;
elements=new type[size];
used=0;
assert(elements);
}
template <class type>
void Array<type>::Sort()
{
int i,j,offset=used;
type temp;
if(myorder==inc_order) return;
if(myorder==dec_order){ReOrder();return;}
while(offset>1)
{
offset=offset/2;
do
{
myorder=inc_order;
for(i=0,j=offset;i<used-offset;i++,j++)
{
if((*this)[i]>(*this)[j])
{
temp=(*this)[i];
(*this)[i]=(*this)[j];
(*this)[j]=temp;
myorder=no_order;
}
}
}while(myorder!=inc_order);
}
}
//反序函数 将第一个数与最后一个数兑换
template <class type>
void Array<type>::ReOrder()
{
for(int i=0,j=used-1;i<j;i++,j--)
SwapElem(i,j);
switch(myorder)
{
case inc_order:myorder=dec_order;break;
case dec_order:myorder=inc_order;break;
default:myorder=no_order;
}
}
template <class type>
void Array<type>::SwapElem(int i, int j)
{
type temp;
assert(!(i>=size||j>=size));
temp=(*this)[i];
(*this)[i]=(*this)[j];
(*this)[j]=temp;
}
//线性查找
template <class type>
int Array<type>::LineSearch(type &x)
{
int index=0;
bool notfound=true;
while(index<used&¬found)
{
if((*this)[index]!=x)
index++;
else
notfound=false
}
if(notfound)
return -1;
else
return index;
}
template <class type>
int Array<type>::Search(type &x)
{
if(myorder==no_order)
return LineSearch(x);
else if(myorder==dec_order)
ReOrder();
return BinSearch(x);
}
//二分查找函数
template <class type>
int Array<type>::BinSearch(type &x)
{
type temp;
int low=0,high=used-1,mid;
bool notfound=true;
while(low<high&¬found)
{
mid=(low+high)/2;
temp=(*this)[mid];
if(temp>x)
high=mid-1;
else if(temp<x)
low=mid+1;
else notfound=false;
}
if(notfound) return -1;
else return mid;
}
template <class type>
void Array<type>::Insert(type &x)
{
if(used==size)
Expand(size+100);
elements[used]=x;
used++;
if(myorder==inc_order)
{
myorder=no_order;
Sort();
}
if(myorder==dec_order)
{
myorder=no_order;
Sort();
ReOrder();
}
}
template <class type>
bool Array<type>::Delete(type &x)
{
int index;
index=Search(x);
if(index=-1)return false;
for(int i=index;i<used-1;i++)
{
elements[i]=elements[i+1]; //后面元素前移一位
}
used--;
return true;
}
template <class type>
bool Array<type>::Delete(int i)
{
if(i>used) return false;
for(int j=i;j<used-1;j++)
{
elements[j]=elements[j+1];
}
used--;
return true;
}
//动态内存再分配
template <class type>
bool Array<type>::Expand(int newsize)
{
type*p,*q;
p=new type[newsize];
assert(p);
memmove(p,elements,sizeof(type)*size);
q=elements;
elements=p;
delete []q;
size=newsize;
return true;
}
template <class type>
Array<type>& Array<type>::Copy(Array<type> &arr) //拷贝函数
{
if(elements)
delete []elements;
myorder=arr.myorder;
size=arr.size;
used=arr.used;
elements=new type[size];
assert(elements);
memmove(elements,arr.elements,sizeof(type)*size);
return *this;
}
//重载输出运算符
template <class type>
ostream & operator<<(ostream & output,Array<type>&arr)
{
output<<"\nsize:"<<arr.size<<"used:"<<arr.used<<"order:";
switch(arr.myorder)
{
case no_order:cout<<"无序数组\n";break;
case inc_order:cout<<"升序数组\n";break;
case dec_order:cout<<"降序数组\n";break;
}
for (int i=0;i<arr.used;i++)
output<<arr.elements[i]<<" ";
output<<"\n";
return output;
}
//重载输入运算符
template <class type>
istream & operator >>(istream &in,Array<type> & arr)
{
type x;
int n;
cout<<"要输入多少元素：";
in>>n;
for(int i=0;i<n;i++)
{
in>>x;
arr.Insert(x);
}
return in;
}
实例：
一元多项式的加法
#include "stdafx.h"
#include"arr.cpp"
void main(){
Array<term>polya,polyb,polyc; //定义三个数组
term ta,tb,t;
int na,nb; //na表示多项式a的长度
int i,j;
cout<<"多项式a共有多少项：";
cin>>na;
cout<<"按指数由大到小的顺序。\n依次输入各项系数，指数。\n";
for(i=1;i<=na;i++)
{
cout<<"\n第"<<i<<"项：";
cin>>t;
polya.Insert(t);
}
cout<<"多项式b共有多少项：";
cin>>nb;
cout<<"按指数由大到小的顺序。\n依次输入各项系数，指数。\n";
for(i=1;i<=nb;i++)
{
cout<<"\n第"<<i<<"项：";
cin>>t;
polyb.Insert(t);
}
cout<<"\npolya:";
cout<<polya;
cout<<"\npolyb";
cout<<polyb;
i=0;j=0;
ta=polya[i];
tb=polyb[j];
int k=0;
while(i<na&&j<nb)
{
if(ta.exp>tb.exp)
{
i++;
polyc.Insert(ta);
k++;
if(i<na)ta=polya[i]; //取数组a中下一项
}
else if(tb.exp>ta.exp)
{
j++;
polyc.Insert(tb);
k++;
if(j<nb)tb=polyb[j];
}
else
{
t.coef=ta.coef+tb.coef;
t.exp=ta.exp;
if(t.coef)
polyc.Insert(t);
i++;j++;k++;
if(i<na&&j<nb)
{
ta=polya[i];
tb=polyb[j];
}
}
}
while(i<na) //若a未取完，将数组a中剩余部分插入数组c
{
t=polya[i];
polyc.Insert(t);
i++;k++;
}
while(j<nb)
{
t=polyb[j];
polyc.Insert(t);
j++;k++;
}
cout<<"\nNew Poly\n";
cout<<polyc;
system("pause");
}