vector.cpp

包含字符串处理

{
	unsigned int max=date.length();
	unsigned int index=binarysearch(value);
	date.setsize(max+1);
	for(unsigned int i=max;i>index;i--)
		date[i]=date[i-1];
	date[index]=value;
}
template<class t>void orderedvector<t>::remove(t value)
{
	unsigned int max=date.length();
	unsigned int index=binarysearch(value);
	date.setsize(max-1);
	for(unsigned int i=max;i>index;i--)
		date[i-1]=date[i];
	date[index]=value;
}

/////////////////////////////////////////////////插入排序
template<class t>void insertionsort(vector<t>&vec)
{
	int n=vec.length(),j,next,count=0;
	t temp;
	for(next=1;next<n;next++)
	{
		temp=vec[next];
		for(j=next-1;j>=0&&temp<vec[j];j--)
		{
			vec[j+1]=vec[j];
			count++;
		}
		vec[j+1]=temp;
	}
	cout<<count<<endl;
}
////////////////////////////////////////起泡排序
template<class t>void swap(vector<t>&vec,int i,int j)
{
	t temp=vec[i];
	vec[i]=vec[j];
	vec[j]=temp;

}
template<class t>void bubblesort(vector<t>&vec)
{
	int top,i,count=0;
	for(top=vec.length()-1;top>0;top--)
	{
		for(i=0;i<top;i++)
		{
			if(vec[i+1]<vec[i])
			{
				swap(vec,i+1,i);
				count++;
			}
		}
	}
	cout<<count<<endl;
}
////////////////////////////////////////选择排序
template<class t>void selectionsort(vector<t>&vec)
{
	int largest,top,count=0,j=1;
	for(top=vec.length()-1;top>0;top--)
	{
		for(largest=0,j=1;j<=top;j++)
		{
			if(vec[largest]<vec[j])
			{
				largest=j;
				count++;
			}
		}
		if(top!=largest)
		{
			swap(vec,top,largest);
			count++;
		}
	}
	cout<<count<<endl;
}
//////////////////////////////////////////快速排序
template<class t>intpartition(vector<t>&vec,int low,int high)
{
	t pivot=v[low];
	while(low<high)
	{
		while(low<high&&v[high]>=pivot)
			high--;
		if(low<high)
		{
			v[low]=v[high];
			low++;
			count++;
		}
		while(low<high&&v[high]>=pivot)
			low++;
		if(low<high)
		{
			v[high]=v[low];
			high--;
			count++;
		}
	}
	v[high]=pivot;
	cout<<count<<endl;
	return high;
}
template<class t>void quicksort(vector<t>&vec,int low,int high)
{
	if(low>=high)return;
	int mindex=partition(v,low,high);
	quicksort(v,low,mindex-1);
	quicksort(v,mindex+1,high);
}
template<class t>void quicksort(vector<t>&v)
{
	quicksort(v,0,v.length()-1);
}
//////////////////////////////////////////list类
template<class t>class list
{
	public:
		list();
		list(const list<t>&source);
		virtual ~list();
		virtual void add(t value);
		virtual void deleteallvalues();
		t firstelement()const;
		virtual int includes(t value)const;
		int isempty()const;
		virtual void removefirst();
//		t takeout(int n);
		list<t>*duplicate()const;
		list<t>* bcopy(list<t>&l1);
	private:
		link<t>*ptrtofirstlink;
		friend class listiterator<t>;
};
template<class t>void list<t>::removefirst()
{
	assert(ptrtofirstlink!=0);
	link<t>*p=ptrtofirstlink;
	ptrtofirstlink=p->ptrtonextlink;
	delete p;
}
template<class t>list<t>::list():ptrtofirstlink(NULL)
{}
template<class t>int list<t>::isempty()const
{
	return ptrtonextlink==0;
}
template<class t>void list<t>::add(t val)
{
	ptrtofirstlink=new link<t>(val,ptrtofirstlink);
	assert(ptrtofirstlink!=0);
}
template<class t>t list<t>::firstelement()const
{
	assert(ptrtofirstlink!=0);
	return ptrtofirstlink->value;
}
template<class t>int list<t>::includes(t v)const
{
	for(link<t>*p=ptrtofirstlink;p;p=p->ptrtonextlink)
	{
		if(v==p->value)return 1;
	}
	return 0;
}
template<class t>void list<t>::deleteallvalues()
{
	link<t>*next;
	for(link<t>*p=ptrtofirstlink;p!=0;p=next)
	{
		next=p->ptrtonextlink;
		p->ptrtonextlink=0;
		delete p;
	}
	ptrtofirstlink=0;
}
template<class t>list<t>*list<t>::duplicate()const
{
	list<t>*newlist=new list<t>;
	assert(newlit!=0);
	if(ptrtonextlink)
		newlist->ptrtonextlink=ptrtonextlink->duplicate();
	return newlist;
}
template<class t>list<t>::list(const list<t>&source)
{
	if(source.isempty)
		ptrtonextlink=0;
	else
	{
		link<t>*firstlink=source.ptrtonextlink;
		ptrtonextlink=firstlink->duplicate();
	}
}
template<class t>list<t>::~list()
{
	deleteallvalues();
}
////////////////////////////////////////link类
template<class  t>class  link
{
private:
    t  value; //存储数据
    link<t> * ptrtonextlink; //存储后继结点的指针
    //表类内部使用的函数
    link(t  linkV, link<t>  *nextptr); //构造
    link(const link<t> &source); //拷贝构造
    link<t>  *duplcate()const; //复制
    friend  class  list<t>; //表类友元
	friend  class  listiterator<t>; //遍历器友元
public:
	link<t>*  insert(t val); //插入
};

template<class t>link<t>::link(t val,link<t> *nxt)
:value(val),ptrtonextlink(nxt)
{}

template<class t>link <t>::link(const link<t>& source)
:value(source.value),ptrtonextlink(source.ptrtonextlink)
{}

template <class t> 
link<t> *link<t>::duplcate() const
{
	link <t> *newlink;
	if(ptrtonextlink!=0)
		newlink=new link<t>(value ,ptrtonextlink->duplcate());
	else
		newlink=new link<t>(value,0);
	assert(newlink !=0);
	return newlink;
}
template<class t>link<t>*link<t>::insert(t val)
{
	ptrtonextlink=new link<t>(val,ptrtonextlink);
	assert(ptrtonextlink!=0);
	return ptrtonextlink;
}
/////////////////////////////////listiterator类/////////////////////////
template<class t>class listiterator:public iterator<t>
{
	public:
		listiterator(list<t> &alist);
		virtual int init();
		virtual t operator()();
		virtual int operator!();
		virtual int operator++();
		virtual void operator=(t value);
		void removecurrent();
		void addbefore(t newvalue);
		void addafter(t newvalue);
	protected:
		link<t>*currentlink;
		link<t>*previouslink;
		list<t>&thelist;
};
template<class t>listiterator<t>::listiterator(list<t>  & alist):thelist(alist)
{
	init();
}
template<class t>int listiterator<t>::init()
{
	previouslink=0;
	currentlink=thelist.ptrtofirstlink;
	return currentlink!=0;
}
template<class t>t listiterator<t>::operator()(){
	if (currentlink!=NULL) 	return  currentlink->value;
	else 
		if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL) 
			return  previouslink->ptrtonextlink->value;
		else if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
			return thelist.ptrtofirstlink->value;
		
		assert(previouslink!=NULL&&previouslink->ptrtonextlink!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}
template<class t>void listiterator<t>::operator =(t val)
{
	assert(currentlink!=0);
	currentlink->value=val;
}
template<class t>void listiterator<t>::removecurrent()
{
	link<t> *p;
	if (currentlink!=NULL) {
		if (previouslink==NULL) 
			thelist.ptrtofirstlink=currentlink->ptrtonextlink;
		else
		{
			previouslink->ptrtonextlink=currentlink->ptrtonextlink;
		}
		delete currentlink;
		currentlink=0;
		return ;
	}    //end of currentLink!=NULL
	else 
		if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
		{
			p=previouslink->ptrtonextlink;
			previouslink->ptrtonextlink=p->ptrtonextlink;
			delete p;
			return ;
		}
		else 
			if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
			{
				p=thelist.ptrtofirstlink;
				thelist.ptrtofirstlink=p->ptrtonextlink;
				delete p;
				return ;
			}
			assert(previouslink!=NULL&&previouslink->ptrtonextlink!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}
template<class t>void listiterator<t>::addafter(t val)
{
	if (currentlink!=NULL) currentlink->insert(val);
	else if (previouslink!=NULL) //当前结点空，但前驱非空
		if (previouslink->ptrtonextlink!=NULL) 
			//前的后继非空，在前驱的后继结点后插入
			previouslink->ptrtonextlink->insert(val);
		else 	previouslink->insert(val);
		else  if  (thelist.ptrtofirstlink)	 //表非空，在第一个结点后插入
			thelist.ptrtofirstlink-> insert(val);
		else  thelist./*List<T>::*/add(val); 
		//表空，作为第一个结点插入
}
template<class t>int listiterator<t>::operator ++()
{
	if(currentlink==0)
	{
		if(previouslink==0)
			currentlink=thelist.ptrtofirstlink;
		else
			currentlink=previouslink->ptrtonextlink;
	}
	else
	{
		previouslink=currentlink;
		currentlink=currentlink->ptrtonextlink;
	}
	return currentlink!=0;
}
template<class t>int listiterator<t>::operator !()
{
	if(currentlink!=0)
		return 1;
	if(previouslink!=0)
		return previouslink->ptrtonextlink!=0;
	return thelist.ptrtofirstlink!=0;
}
template<class t>void listiterator<t>::addbefore(t val)
{
	if(previouslink)
		previouslink=previouslink->insert(val);
	else
	{
		thelist.add(val);
		previouslink=thelist.ptrtofirstlink;
	}
}
/////////////////////////////////////////////stackvector
template<class t>class stack
{
	public:
		virtual void deleteallvalues()=0;
		virtual int isempty()const=0;
		virtual t pop()=0;
		virtual void push(t value)=0;
		virtual t top()const=0;
};
template<class t>class stackvector:public stack<t>
{
	public:
		//构造函数
		stackvector(unsigned int size);
		stackvector(const stackvector &v);
		//栈操作
		virtual void deleteallvalues();
		virtual int isempty()const;
		virtual t top()const;
		virtual void push(t value);
		virtual t pop();
		int countstack(const stackvector<t> &st);
	protected:
		vector<t> data;
		unsigned int nextslot;
};
template<class t>stackvector<t>::stackvector(unsigned int size):data(size)
{
	deleteallvalues();
}
template<class t>stackvector<t>::stackvector(const stackvector<t> &v):data(v.data),nextslot(v.nextslot){}
template<class t>void stackvector<t>::deleteallvalues()
{
	nextslot=0;
}
template<class t>t stackvector<t>::top()const
{
	assert(!isempty());
	return data[nextslot-1];
}
template<class t>t stackvector<t>::pop()
{
	assert(!isempty());
	return data[--nextslot];
}
template<class t>int stackvector<t>::isempty()const
{
	return nextslot==0;
}
template<class t>void stackvector<t>::push(t value)
{
	if(nextslot>=data.length())
		data.setsize(data.length()+5);
	data[nextslot++]=value;
}
template<class t>int countstack(const stackvector<t> &st)
{
	stackvector<t> tempst(st);  //辅助栈
	int k=0;
	while(!tempst.isempty())
	{
		tempst.pop();k++;
	}
	return k;
}

////////////////////////////////////////////queuevector
template<class t>class queue
{
	public:
		virtual void deleteallvalues()=0;
		virtual int isempty()const=0;
		virtual t dequeue()=0;
		virtual void enqueue(t value)=0;
		virtual t front()const=0;
};
template<class t>class queuevector:public queue<t>
{
	public:
		queuevector(unsigned int size);
		queuevector(const queuevector &v);
		virtual void deleteallvalues();
		virtual int isempty()const;
		virtual t dequeue();
		virtual void enqueue(t value);
		virtual t front()const;
		int countqueue(const queuevector<t> &qu);
	protected:
		vector<t> data;
		const unsigned int max;
		unsigned int nextslot;
		unsigned int nextuse;
};
template<class t>queuevector<t>::queuevector(unsigned int size):max(size),data(size)
{
	deleteallvalues();
}
template<class t>queuevector<t>::queuevector(const queuevector &v):max(v.max),data(v.data),nextslot(v.nextslot),nextuse(v.nextuse)
{}
template<class t>void queuevector<t>::deleteallvalues()
{
	nextslot=0;
	nextuse=0;
}
template<class t>int queuevector<t>::isempty()const
{
	return nextslot==nextuse;
}
template<class t>void queuevector<t>::enqueue(t val)
{
	data[nextslot++]=val;
	nextslot=nextslot%max;
	assert(nextslot!=nextuse);
}
template<class t>t queuevector<t>::dequeue()
{
	assert(!isempty());
	int dataloc=nextslot;
	nextuse++;
	nextslot=nextslot%max;
	return data[dataloc];
}
template<class t>t queuevector<t>::front()const
{
	assert(!isempty());
	return data[nextuse-1];
}
template<class t>int countqueue(const queuevector<t> &qu)
{
	queuevector<t> tempqu(qu);  //辅助队列
	int k=0;
	while(!tempqu.isempty())
	{
		tempqu.dequeue();
		k++;
	}
	return k;
}
/*////////////////////////////////////////取数
void takeout(listiterator<int> &itr,int n)
{
for(int i=0;i<10;i++,itr++)
if(n==i)
{	
			cout<<itr();
		}
}
/////////////////////////////////////////取反
template<class t>list<t>* list<t>::bcopy(list<t> &l1)
{
	list<t> *newlist=new list<t>;
	assert(newlist!=0);
	while(li->ptrtonextlink)
	{
		newlist->add(l1->value);
	}
	return newlist;
}
////////////////////////////////////////////主函数
void main()
{
	list<int> alist,*p;
	for(int i=0;i<10;i++)
		alist.add(i);
	listiterator<int> itr(alist);
	for(;!itr;++itr)
	{
		cout<<itr()<<" ";
		if(itr()%5==0)
			itr.removecurrent();
	}
	cout<<endl;
	for(itr.init();!itr;++itr)
		cout<<itr();
	int n;
	cin>>n;
	takeout(itr,n);
//	p=bcopy(alist);
//	for(i=0;i<10;i++)
//		cout<<p->firstelement;
}
///////////////////////////////////////菜单驱动
void main()
{
	list<int> l1,l2;
	int val;
	for(unsigned i=0;i<10;i++)
		l2.add(i);
	listiterator<int> itr1(l2);
	int choice,m,n;
	bool flag=true;
	cout<<"输入1:建立有N个结点的单链表（从键盘输入N）"<<endl;
	cout<<"输入2:在该单链表中查找第n个结点（n可从键盘输入）"<<endl;
	cout<<"输入3:在该单链表中查找值为val的结点（val可从键盘输入）"<<endl;
	cout<<"输入4:在单链表中第n个结点前插入m个新结点（n,m可输入，新结点的值可自定）"<<endl;
	cout<<"输入5:在单链表中第n个结点后插入m个新结点（n,m可输入，新结点的值可自定）"<<endl;
	cout<<"输入6:在单链表中删除第n个结点（n可输入）"<<endl;
	cout<<"输入0:退出程序"<<endl;
	while(1)
	{	
		cin>>choice;
		if(choice==0)break;
		switch(choice)
		{
		case 1:{cin>>n;
			for(int i=0;i<n;i++)
				l1.add(i);
			listiterator<int> itr2(l1);
			for(i=0;i<n;i++,++itr2)
				cout<<itr2()<<endl;
			break;
			   }
		case 2:{cin>>n;
			for(int i=0;i<n&&itr1()!=NULL;++itr1,i++)
			{if(i==n){cout<<itr1()<<endl;break;}}
			if(i<n&&itr1()==NULL)cout<<"查找失败!"<<endl;
			break;
			   }
		case 3:{cin>>val;int i=1;
			for(itr1.init();!itr1;++itr1,i++)
			{
				if(val==itr1())
				{cout<<"所查找元素在第"<<i<<"个，值为"<<val<<endl;flag=false;}
			}
			if(flag)cout<<"没找到"<<endl;
			break;
			   }
		case 4:{cin>>n>>m;int i=0;
			for(itr1.init();!itr1;++itr1,i++)
				if(i==(n-1))
				{
					for(int j=0;j<m;j++)
						itr1.addbefore(j);
					break;
				}
				break;
			   }
		case 5:{cin>>n>>m;int i=0;
			for(itr1.init();!itr1;++itr1,i++)
				if(i==(n-1))
				{
					for(int j=0;j<m;j++)
						itr1.addafter(j);
					break;
				}
				break;
			   }
		case 6:{cin>>n;int i=0;
			for(itr1.init();!itr1;++itr1,i++)
				if(i==(n-1))
				{itr1.removecurrent();break;}
				break;
			   }
		}
	}
	}
*/
void main()
{
	stackvector<int> sta(10); //建立可存储10个数据的向量栈
	queuevector <int> que(10); //建立可存储9个数据的向量队列，为什么是9个？
	int  k, temp;
	for(k=0; k<10; k++)
	{
		//cin>>temp;
		//sta.push(temp);
		sta.push(k);
	}
	for(k=0; k<9; k++)
	{ //数据入队列
		//cin>>temp;
		//que.enqueue(temp);
		que.enqueue(k);
	}
	cout<<countstack(sta)<<endl;
	cout<<countqueue(que)<<endl;
}