**自主编写Vector类**
作者:一名来自青海大学的硕士研究生(高级数据结构课程实验随笔)
Vector类包含的功能有如下(主人太累了,不想多解释,代码中有详细解释):
(以下代码仅供大家学习使用,大家尽量不要抄袭)
#include<iostream>
#include<cstring>
#include<time.h>
#include<stdlib.h>
#define ll long long int
#define S string
#define C char
using namespace std;
template <class T>
class vector{
private:
ll cnt;
public:
T a[1000005];
//构造函数初始化cnt;
vector()
{
cnt=0;
}
//向vector容器中输入数据类型为T的x;
void push_back(T x)
{
a[cnt]=x;
cnt++;
}
//从容器的尾端移除元素
void pop_back()
{
cnt--;
}
//返回vector容器中元素的个数;
ll size()
{
return cnt;
}
//查找元素在整个容器中第一次出现的位置,有则返回具体位置,否则返回-1(代表容器中没有该元素);
ll findBegin(T x)
{
ll i;
for(i=0;i<cnt;i++)
{
if(a[i]==x)
{
return i+1;
}
}
if(i==cnt)
{
return -1;
}
}
//从整个容器末尾开始查找第一个出现的位置,有则返回具体位置,否则返回-1(代表容器中没有该元素);
ll findEnd(T x)
{
ll i;
for(i=cnt-1;i>=0;i--)
{
if(a[i]==x)
{
return i+1;
}
}
if(i==-1)
{
return -1;
}
}
//查找元素在整个容器中出现的次数,有则返回出现的个数,否则返回0(代表容器中没有该元素);
ll findCount(T x)
{
ll num=0,i;
for(i=0;i<cnt;i++)
{
if(a[i]==x)
{
num++;
}
}
if(i==cnt&&num==0)
{
return 0;
}
else
{
return num;
}
}
//对于顺序元素的查找法:二分查找,有则返回具体位置,否则返回-1(代表容器中没有该元素);
ll search(T x)
{
ll l=0,r=cnt-1,h;
while(l<=r)
{
h=(l+r)/2;
if(a[h]==x)
{
return h+1;
}
else
{
if(a[h]<x)
{
l=h+1;
}
else
{
r=h-1;
}
}
}
if(l>r)
{
return -1;
}
}
//有序表中去重操作
void unique()
{
ll i,count=0;
for(i=1;i<cnt;i++)
{
if(a[i]==a[i-1])
{
removeDestination(i);
i--;
}
}
}
//无序表中去重操作
void disorderUnique()
{
ll i;
for(i=0;i<cnt;i++)
{
removeExcepteBegin(a[i]);
}
}
//插入元素操作
void insert(ll dest,T x)
{
ll i;
cnt++;
for(i=cnt;i>=dest;i--)
{
a[i]=a[i-1];
}
a[dest-1]=x;
}
//移除位置在dest位置的元素
T removeDestination(int dest)
{
ll i;
T value;
value=a[dest-1];
for(i=dest-1;i<cnt;i++)
{
a[i]=a[i+1];
}
cnt--;
return value;
}
//移除从整个容器开头开始向后查询x第一次出现的位置并删除这个位置的元素;
void removeBeginDiscover(T x)
{
ll dest=findBegin(x),i;
if(dest!=-1)
{
for(i=dest;i<cnt;i++)
{
a[i-1]=a[i];
}
cnt--;
}
}
//移除从整个容器结尾开始向前查询x第一次出现的位置并删除这个位置的元素;
void removeEndDiscover(T x)
{
ll dest=findEnd(x),i;
if(dest!=-1)
{
for(i=dest;i<cnt;i++)
{
a[i-1]=a[i];
}
cnt--;
}
}
//移除容器中所有x元素
void removeAll(T x)
{
ll destBegin=findBegin(x),destEnd=findEnd(x),i;
for(i=destBegin-1;i<=destEnd-1;i++)
{
if(a[i]==x)
{
removeDestination(i+1);
destEnd--;
}
}
}
//移除容器中除第一次出现(从前向后数)的所有X元素
void removeExcepteBegin(T x)
{
ll destBegin=findBegin(x),destEnd=findEnd(x),i;
for(i=destBegin;i<=destEnd-1;i++)
{
if(a[i]==x)
{
removeDestination(i+1);
i--;
destEnd--;
}
}
}
//返回容器头元素,如果容器中的元素个数是大于0的,则返回头元素;
T begin()
{
if(cnt>0)
return a[0];
}
//还回容器尾元素,如果容器中的元素个数是大于0的,则返回尾元素;
T end()
{
if(cnt>0)
return a[cnt-1];
}
//快速排序
void quicksort(ll l,ll r)
{
ll i=l,j=r;
T x=a[l];
if(l<r)
{
while(i!=j)
{
while(i<j&&a[j]>=x)
j--;
a[i]=a[j];
while(i<j&&a[i]<=x)
i++;
a[j]=a[i];
}
a[i]=x;
quicksort(l,i-1);
quicksort(i+1,r);
}
}
};
//声明vector变量
vector<ll> vec,vec1[7];
//整型数据测试
void testInteger()
{
ll n,i,testNumber,destination,count1=0;
printf("请你输入您要测试的数据组数:");
scanf("%lld",&n);
srand((ll)time(0));
for(i=0;i<n;i++)
{
vec.push_back(rand()%10);
}
vec1[count1]=vec;
//查看随机生成的元素有哪些;
cout<<"原始容器元素输出:"<<endl;
for(i=0;i<vec.size();i++)
printf("%lld ",vec.a[i]);
cout<<endl;
cout<<"复制容器元素输出:"<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
//测试容器的头元素值并返回;
cout<<"容器的头元素为: "<<vec1[count1].begin()<<endl;
//测试容器的尾元素值并返回;
cout<<"容器的尾元素为: "<<vec1[count1].end()<<endl;
//测试容器的大小并返回;
cout<<"容器的大小为: "<<vec1[count1].size()<<endl;
//find测试;
testNumber=rand()%10;
cout<<"testNumber = "<<testNumber<<endl;
destination=rand()%n;
cout<<"destination = "<<destination<<endl;
cout<<"testNumber "<<testNumber<<" 从前向后数第一次出现的位置:"<<vec1[count1].findBegin(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 从后向前数第一次出现的位置:"<<vec1[count1].findEnd(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 在容器中一共出现多少次: "<<vec1[count1].findCount(testNumber)<<endl;
//插入位置在destination,插入元素为testNumber;
vec1[count1].insert(destination,testNumber);
//查看插入后容器元素;
cout<<"查看插入后容器元素: "<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
//移除位置在destination的元素;
cout<<"对于插入后的容器再删除位置为"<<destination<<"的元素值为:";
cout<<vec1[count1].removeDestination(destination)<<endl;
//查看移除后容器元素;
cout<<"移除位置在destination的元素 , 查看移除后容器元素: "<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
count1++;
vec1[count1]=vec;
//移除从头到尾第一次出现的元素testNumber;
vec1[count1].removeBeginDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从头到尾第一次出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
count1++;
vec1[count1]=vec;
//移除从尾到头第一次出现的元素testNumber;
vec1[count1].removeEndDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从尾到头第一次出现的元素testNumber,查看移除后容器元素: "<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
count1++;
vec1[count1]=vec;
//移除从容器中所有出现的元素testNumber;
vec1[count1].removeAll(testNumber);
//查看移除后容器元素;
cout<<"移除从容器中所有出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
count1++;
vec1[count1]=vec;
//无序表去重;
vec1[count1].disorderUnique();
//查看移除后容器元素;
cout<<"无序表去重 , 查看移除后容器元素:" <<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
count1++;
vec1[count1]=vec;
//排序
vec1[count1].quicksort(0,n-1);
//查看排序后的序列
cout<<"排序 , 查看排序后的序列:"<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
//有序表去重;
vec1[count1].unique();
//查看移除后容器元素;
cout<<"有序表去重 , 查看移除后容器元素"<<endl;
for(i=0;i<vec1[count1].size();i++)
printf("%lld ",vec1[count1].a[i]);
cout<<endl;
}
//字符串型数据测试
//测试样例:
/*
13
map Map map destination Destination map destination nihao Nihua Nihub the The the
*/
vector<S> vec2,vec3[7];
void testString()
{
ll n,i,destination,count1=0;
S testNumber,x;
printf("请你输入您要测试的数据组数:");
scanf("%lld",&n);
srand((ll)time(0));
for(i=0;i<n;i++)
{
cin>>x;
vec2.push_back(x);
}
vec3[count1]=vec2;
//查看容器中元素有哪些;
cout<<"原始容器元素输出:"<<endl;
for(i=0;i<vec2.size();i++)
cout<<vec2.a[i]<<' ';
cout<<endl;
cout<<"复制容器元素输出:"<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
//测试容器的头元素值并返回;
cout<<"容器的头元素为: "<<vec3[count1].begin()<<endl;
//测试容器的尾元素值并返回;
cout<<"容器的尾元素为: "<<vec3[count1].end()<<endl;
//测试容器的大小并返回;
cout<<"容器的大小为: "<<vec3[count1].size()<<endl;
//find测试;
testNumber="map";
cout<<"testNumber = "<<testNumber<<endl;
destination=rand()%n;
cout<<"destination = "<<destination<<endl;
cout<<"testNumber "<<testNumber<<" 从前向后数第一次出现的位置:"<<vec3[count1].findBegin(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 从后向前数第一次出现的位置:"<<vec3[count1].findEnd(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 在容器中一共出现多少次: "<<vec3[count1].findCount(testNumber)<<endl;
//插入位置在destination,插入元素为testNumber;
vec3[count1].insert(destination,testNumber);
//查看插入后容器元素;
cout<<"原始容器元素输出:"<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
//移除位置在destination的元素;
cout<<"对于插入后的容器再删除位置为"<<destination<<"的元素值为:";
cout<<vec3[count1].removeDestination(destination)<<endl;
//查看移除后容器元素;
cout<<"移除位置在destination的元素 , 查看移除后容器元素: "<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
count1++;
vec3[count1]=vec2;
//移除从头到尾第一次出现的元素testNumber;
vec3[count1].removeBeginDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从头到尾第一次出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
count1++;
vec3[count1]=vec2;
//移除从尾到头第一次出现的元素testNumber;
vec3[count1].removeEndDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从尾到头第一次出现的元素testNumber,查看移除后容器元素: "<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
count1++;
vec3[count1]=vec2;
//移除从容器中所有出现的元素testNumber;
vec3[count1].removeAll(testNumber);
//查看移除后容器元素;
cout<<"移除从容器中所有出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
count1++;
vec3[count1]=vec2;
//无序表去重;
vec3[count1].disorderUnique();
//查看移除后容器元素;
cout<<"无序表去重 , 查看移除后容器元素:" <<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
count1++;
vec3[count1]=vec2;
//排序
vec3[count1].quicksort(0,vec3[count1].size()-1);
//查看排序后的序列
cout<<"排序 , 查看排序后的序列:"<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
//有序表去重;
vec3[count1].unique();
//查看移除后容器元素;
cout<<"有序表去重 , 查看移除后容器元素"<<endl;
for(i=0;i<vec3[count1].size();i++)
cout<<vec3[count1].a[i]<<' ';
cout<<endl;
}
//字符型数据测试
vector<C> vec4,vec5[7];
C x[63]={"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"};
void testChar()
{
ll n,i,destination,count1=0;
C testNumber;
printf("请你输入您要测试的数据组数:");
scanf("%lld",&n);
srand((ll)time(0));
for(i=0;i<n;i++)
{
vec4.push_back(x[rand()%62]);
}
vec5[count1]=vec4;
//查看容器中元素有哪些;
cout<<"原始容器元素输出:"<<endl;
for(i=0;i<vec4.size();i++)
cout<<vec4.a[i]<<' ';
cout<<endl;
cout<<"复制容器元素输出:"<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
//测试容器的头元素值并返回;
cout<<"容器的头元素为: "<<vec5[count1].begin()<<endl;
//测试容器的尾元素值并返回;
cout<<"容器的尾元素为: "<<vec5[count1].end()<<endl;
//测试容器的大小并返回;
cout<<"容器的大小为: "<<vec5[count1].size()<<endl;
//find测试;
testNumber=x[rand()%62];
cout<<"testNumber = "<<testNumber<<endl;
destination=rand()%n;
cout<<"destination = "<<destination<<endl;
cout<<"testNumber "<<testNumber<<" 从前向后数第一次出现的位置:"<<vec5[count1].findBegin(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 从后向前数第一次出现的位置:"<<vec5[count1].findEnd(testNumber)<<endl;
cout<<"testNumber "<<testNumber<<" 在容器中一共出现多少次: "<<vec5[count1].findCount(testNumber)<<endl;
//插入位置在destination,插入元素为testNumber;
vec5[count1].insert(destination,testNumber);
//查看插入后容器元素;
cout<<"原始容器元素输出:"<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
//移除位置在destination的元素;
cout<<"对于插入后的容器再删除位置为"<<destination<<"的元素值为:";
cout<<vec5[count1].removeDestination(destination)<<endl;
//查看移除后容器元素;
cout<<"移除位置在destination的元素 , 查看移除后容器元素: "<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
count1++;
vec5[count1]=vec4;
//移除从头到尾第一次出现的元素testNumber;
vec5[count1].removeBeginDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从头到尾第一次出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
count1++;
vec5[count1]=vec4;
//移除从尾到头第一次出现的元素testNumber;
vec5[count1].removeEndDiscover(testNumber);
//查看移除后容器元素;
cout<<"移除从尾到头第一次出现的元素testNumber,查看移除后容器元素: "<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
count1++;
vec5[count1]=vec4;
//移除从容器中所有出现的元素testNumber;
vec5[count1].removeAll(testNumber);
//查看移除后容器元素;
cout<<"移除从容器中所有出现的元素testNumber , 查看移除后容器元素: "<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
count1++;
vec5[count1]=vec4;
//无序表去重;
vec5[count1].disorderUnique();
//查看移除后容器元素;
cout<<"无序表去重 , 查看移除后容器元素:" <<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
count1++;
vec5[count1]=vec4;
//排序
vec5[count1].quicksort(0,vec5[count1].size()-1);
//查看排序后的序列
cout<<"排序 , 查看排序后的序列:"<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
//有序表去重;
vec5[count1].unique();
//查看移除后容器元素;
cout<<"有序表去重 , 查看移除后容器元素"<<endl;
for(i=0;i<vec5[count1].size();i++)
cout<<vec5[count1].a[i]<<' ';
cout<<endl;
}
int main()
{
testInteger();
testString();
testChar();
return 0;
}