#include "stdafx.h"
#include <iostream>
#include <list>
using namespace std;
template<typename T>
class List : private list<T>
{
public:
void pop(){list<T>::pop();}
void push_back(const T&_Val){list<T>::push_back(_Val);}
T front(){ returnlist<T>::front();}
};
int _tmain(int argc, _TCHAR* argv[])
{
List<int> a;
a.push_back(3);
a.push_back(4);
cout<<a.front()<<endl;
return 0;
}
#include "stdafx.h"
#include <iostream>
#include <list>
#include <boost/pool/pool_alloc.hpp>
using namespace std;
template<typename T,typename C =std::allocator<T>>
class List : private list<T>
{
public:
void pop(){list<T>::pop();}
void push_back(const T&_Val){list<T>::push_back(_Val);}
T front(){ returnlist<T>::front();}
};
int _tmain(int argc, _TCHAR* argv[])
{
List<int> a;
a.push_back(3);
a.push_back(4);
cout<<a.front()<<endl;
//用boost::pool
list<double,boost::fast_pool_allocator<double>>b;
b.push_back(4.5);
b.push_back(3.5);
cout<<a.front()<<endl;
return 0;
}
求用STL完成一双向循环链表。名字为Circle
要求:
1、用法和list类一样,要有push_back(), size(), insert(pos), erase(pos), begin()这些函数。
其它更高级的函数可以没有。
begin()相当于这个循环链表有一个内部定义的头。
2、最好在内部封装list类来实现,这样会比较方便。
3、最重要的一点:用法必须和STL标准库中的一样。
例如:
写好后只需要 #include <Circle.h>
即可用: Circle<int> mycircle;来使用。
写完满意后再加100分,一共200分!
回复人:taodm(taodm) ( ) 信誉:100 2006-10-10 15:49:19 得分:0
?
这个,理论上只要接管list::iterator的++/--。
但是实际上这个打破了封装。
而且,它的erase(first, last)等操作就语义混乱了。
如果是习题,建议你自己写。如果是项目需要,建议你更改设计,这些接口集不合理。
Top
回复人:jixingzhong(瞌睡虫·星辰) ( ) 信誉:102 2006-10-10 15:52:58 得分:0
?
仅供参考, 和你的要求有些差距,
手动修改一下吧 :
//SeqList.h 声明类SeqList,文件名为SeqList.h
#ifndef SeqList_H
#define SeqList_H
const int MaxSize=100; //100只是示例性的数据,可以根据实际问题具体定义
template <class T> //定义模板类SeqList
class SeqList
{
public:
SeqList( ); //无参构造函数
SeqList(T a[], int n); //有参构造函数
~SeqList(); //析构函数为空
int Length(); //求线性表的长度
T Get(int i); //按位查找,取线性表的第i个元素
int Locate(T x); //按值查找,求线性表中值为x的元素序号
void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素
T Delete(int i); //删除线性表的第i个元素
void PrintList(); //遍历线性表,按序号依次输出各元素
private:
T data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
#endif
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//SeqList.cpp
#include "SeqList.h"
/*
*前置条件:顺序表不存在
*输 入:无
*功 能:构建一个顺序表
*输 出:无
*后置条件:构建一个顺序表
*/
template <class T>
SeqList<T>:: SeqList( )
{
length=0;
}
/*
*前置条件:顺序表不存在
*输 入:顺序表信息的数组形式a[],顺序表长度n
*功 能:将数组a[]中元素建为长度为n的顺序表
*输 出:无
*后置条件:构建一个顺序表
*/
template <class T>
SeqList<T>:: SeqList(T a[], int n)
{
if (n>MaxSize) throw "参数非法";
for (int i=0; i<n; i++)
data[i]=a[i];
length=n;
}
/*
*前置条件:无
*输 入:无
*功 能:无
*输 出:无
*后置条件:无
*/
template <class T>
SeqList<T>:: ~SeqList( )
{
}
/*
*前置条件:顺序表存在
*输 入:插入元素x,插入位置i
*功 能:将元素x插入到顺序表中位置i处
*输 出:无
*后置条件:顺序表插入新元素
*/
template <class T>
void SeqList<T>::Insert(int i, T x)
{
int j;
if (length>=MaxSize) throw "上溢";
if (i<1 || i>length+1) throw "位置";
for (j=length; j>=i; j--)
data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处
data[i-1]=x;
length++;
}
/*
*前置条件:顺序表存在
*输 入:要删除元素位置i
*功 能:删除顺序表中位置为i的元素
*输 出:无
*后置条件:顺序表删除元素
*/
template <class T>
T SeqList<T>::Delete(int i)
{
int x,j;
if (length==0) throw "下溢";
if (i<1 || i>length) throw "位置";
x=data[i-1];
for (j=i; j<length; j++)
data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标
length--;
return x;
}
/*
*前置条件:顺序表存在
*输 入:无
*功 能:输出顺序表长度
*输 出:顺序表长度
*后置条件:顺序表不变
*/
template <class T>
int SeqList<T>::Length()
{
return length;
}
/*
*前置条件:顺序表存在
*输 入:查询元素位置i
*功 能:按位查找位置为i的元素并输出值
*输 出:查询元素的值
*后置条件:顺序表不变
*/
template <class T>
T SeqList<T>::Get(int i)
{
if (i<1 && i>length) throw"查找位置非法";
else return data[i-1];
}
/*
*前置条件:顺序表存在
*输 入:查询元素值x
*功 能:按值查找值的元素并输出位置
*输 出:查询元素的位置
*后置条件:顺序表不变
*/
template <class T>
int SeqList<T>::Locate(T x)
{
for (int i=0; i<length; i++)
if (data[i]==x)
return i+1 ; //下标为i的元素等于x,返回其序号i+1
return 0; //退出循环,说明查找失败
}
/*
*前置条件:顺序表存在
*输 入:无
*功 能:顺序表遍历
*输 出:输出所有元素
*后置条件:顺序表不变
*/
template <class T>
void SeqList<T>::PrintList()
{
for(int i=0;i<length;i++)
cout<<data[i]<<endl;
}
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//SeQListMain.cpp
#include <iostream.h> //引用输入输出流库函数的头文件
#include "SeqList.cpp" //引用顺序表类SeqList
void main( )
{
SeqList<int>a; //创建一个空的顺序表
cout<<"执行插入操作:"<<endl;
try
{
a.Insert(1,1);
a.Insert(2,3);
a.Insert(3,4);
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"已经插入“1,3,4”"<<endl;
cout<<endl;
cout<<"顺序表a的长度为:";
cout<<a.Length()<<endl; //返回单链表长度
cout<<endl;
cout<<"按位查询第二个元素:"<<endl;
cout<<"第二个元素为:";
cout <<a.Get(2)<<endl; //查找顺序表中第二个元素
cout<<endl;
cout<<"按值查询3:"<<endl;
cout<<"值为3的元素位置为:";
cout<<a.Locate(3)<<endl; //查找元素3,并返回在单链表中位置
cout<<endl;
try
{
if(a.Length()){
cout<<"执行删除第一个元素操作:"<<endl;
cout<<endl;
a.Delete(1); //删除元素1
cout<<"已删除成功,顺序表a的长度为:";
cout<<a.Length()<<endl;
}
else{
cout<<"顺序表a长度为0"<<endl;
}
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<endl;
cout<<"顺序表a中的元素有:"<<endl;
a.PrintList(); //输出所有元素
int r[]={1,2,3,4,5};
SeqList <int> b(r,5); //根据数组创建顺序表
cout<<"执行插入操作前顺序表b为:"<<endl;
b.PrintList(); //输出顺序表所有元素
cout<<"插入前顺序表b的长度为:";
cout<<b.Length()<<endl;
try
{
b.Insert(3,8);
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"执行插入操作后顺序表b为:"<<endl;
b.PrintList(); //输出顺序表b所有元素
cout<<"插入后顺序表b的长度为:";
cout<<b.Length()<<endl;
cout<<endl;
try
{
if(a.Length()){
cout<<"执行删除第一个元素操作:"<<endl;
cout<<endl;
b.Delete(1); //删除b中第一个元素
cout<<"已删除成功,顺序表b的长度为:";
cout<<b.Length()<<endl;
}
else{
cout<<"顺序表b长度为0"<<endl;
}
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"执行插入操作后顺序表b为:"<<endl;
b.PrintList(); //输出顺序表所有元素
}
既然用了STL 直接使用LIST就好了啊
给个C的
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
DuLNode *prior,*next;
}DuLNode,*DuLinkList;
双链循环线性表(存储结构由c2-4.h定义)的基本操作(14个)
Status InitList(DuLinkList &L)
{ // 产生空的双向循环链表L
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
{
L->next=L->prior=L;
return OK;
}
else
return OVERFLOW;
}
Status DestroyList(DuLinkList &L)
{ // 操作结果:销毁双向循环链表L
DuLinkList q,p=L->next; // p指向第一个结点
while(p!=L) // p没到表头
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
return OK;
}
Status ClearList(DuLinkList L) // 不改变L
{ // 初始条件:L已存在。操作结果:将L重置为空表
DuLinkList q,p=L->next; // p指向第一个结点
while(p!=L) // p没到表头
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; // 头结点的两个指针域均指向自身
return OK;
}
Status ListEmpty(DuLinkList L)
{ // 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{ // 初始条件:L已存在。操作结果:返回L中数据元素个数
int i=0;
DuLinkList p=L->next; // p指向第一个结点
while(p!=L) // p没到表头
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType&e)
{ // 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
int j=1; // j为计数器
DuLinkList p=L->next; // p指向第一个结点
while(p!=L&&j<i) // 顺指针向后查找,直到p指向第i个元素或p指向头结点
{
p=p->next;
j++;
}
if(p==L||j>i) // 第i个元素不存在
return ERROR;
e=p->data; // 取第i个元素
return OK;
}
int LocateElem(DuLinkList L,ElemTypee,Status(*compare)(ElemType,ElemType))
{ // 初始条件:L已存在,compare()是数据元素判定函数
// 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在,则返回值为0
int i=0;
DuLinkList p=L->next; // p指向第1个元素
while(p!=L)
{
i++;
if(compare(p->data,e)) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}
Status PriorElem(DuLinkList L,ElemTypecur_e,ElemType &pre_e)
{ // 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
// 前驱,否则操作失败,pre_e无定义
DuLinkList p=L->next->next; // p指向第2个元素
while(p!=L) // p没到表头
{
if(p->data==cur_e)
{
pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L,ElemTypecur_e,ElemType &next_e)
{ // 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,
// 否则操作失败,next_e无定义
DuLinkList p=L->next->next; // p指向第2个元素
while(p!=L) // p没到表头
{
if(p->prior->data==cur_e)
{
next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L,int i) // 另加
{ // 在双向链表L中返回第i个元素的位置指针(算法2.18、2.19要调用的函数)
int j;
DuLinkList p=L;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
Status ListInsert(DuLinkList L,int i,ElemTypee) // 改进算法2.18
{ // 在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1
DuLinkList p,s;
if(i<1||i>ListLength(L)+1) // i值不合法
return ERROR;
p=GetElemP(L,i-1); // 在L中确定第i-1个元素的位置指针p
if(!p) // p=NULL,即第i-1个元素不存在
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e; // 在第i-1个元素之后插入
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
Status ListDelete(DuLinkList L,int i,ElemType&e) // 算法2.19
{ // 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长+1
DuLinkList p;
if(i<1||i>ListLength(L)) // i值不合法
return ERROR;
p=GetElemP(L,i); // 在L中确定第i个元素的位置指针p
if(!p) // p=NULL,即第i个元素不存在
return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
void ListTraverse(DuLinkListL,void(*visit)(ElemType))
{ // 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit()
DuLinkList p=L->next; // p指向头结点
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkListL,void(*visit)(ElemType))
{ // 由双链循环线性表L的头结点出发,逆序对每个数据元素调用函数visit()。另加
DuLinkList p=L->prior; // p指向尾结点
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}
Top
回复人:wanfustudio(雁南飞:为作业社区发扬光大奋斗!) ( ) 信誉:97 2006-10-10 15:56:17 得分:10
?
有难度。。想。。。
链表。<list><stl_list.h>
实现的是双向循环链表
构造函数:
list();
list(size_type n,const value_type&value);
list(size_type n);
list(const list &x);
list(interator start,interator rear);
有关属性的基本方法:
iterator begin(); //rbegin
iterator end(); //rend
reference front();
reference back();
//-------------------------------------------------------
size_type size();
bool empty();
应用的基本方法:
整体运算:(<,<=,>,>=,==,=)
void reverse();
增加元素:
void push_front(const value_type &x);
void push_back(const value_type &x);
iterator insert(iterator __position, constvalue_type& __x);
void insert(iterator __position, size_type__n, const value_type& __x);
void insert(iterator __position,_InputIterator __first, _InputIterator __last);
删除元素:
void pop_front();
void pop_back();
void Clear();
void unique();
void remove(const value_type& __val);
template <class _Predicate>
void remove_if(_Predicate __pred);
iterator erase(iterator position);
iterator erase(iterator __first, iterator__last);
元素访问:
void assign(size_type __n, constvalue_type& __val);
void assign(_InputIterator __first,_InputIterator __last);
//结合,源变空
void splice(iterator __position, list&__x);
void splice(iterator __position, list&,iterator __i);
void splice(iterator __position, list&,iterator __first, iterator __last);
排序:
内存相关:
size_type max_size() const;//可能分配的最大内存
void resize(size_type new_size);
void resize(size_type new_size, constvalue_type& x);
迭代器:
typedef bidirectional_iterator_tagiterator_category;
list<value_type>::interator i;
运算符:=,*,-〉,++,--,+,-,+=,-=
小结:
1.erase删除指定位置的数据,remove删除指定值的数据,clear全删除。
Top
回复人:weijiangshanwww(天气预报:今天会下分,偶尔下几颗星星!) ( )信誉:100 2006-10-10 15:59:09 得分:2
?
答案都差不多了,UP 下了!!!
Top
回复人:weijiangshanwww(天气预报:今天会下分,偶尔下几颗星星!) ( )信誉:100 2006-10-10 15:59:41 得分:2
?
lS的果然速度。
Top
回复人:healer_kx(天降甘草:又要上班了...555 555) ( ) 信誉:98 2006-10-10 16:21:29 得分:50
?
// ffff.cpp : Defines the entry point for theconsole application.
//
#include "stdafx.h"
#include <list>
using namespace std;
template<class T>
class Circle : public list<T>
{
public:
typedef typename list<T>::iteratoriterator;
class iterator_c
{
public:
iterator_c(iterator i)
:i_(i)
{
}
//////////////////////////////////////////////////////////////////////////
//这里自己写++ --的逻辑就可以了。
operator iterator()
{
return i_;
}
private:
iterator i_;
};
Circle()
:list<T>()
{
}
~Circle()
{
}
iterator_c begin()
{
return list<T>::begin();
}
void push_back(T const& value)
{
list<T>::push_back(value);
}
size_t size()
{
return list<T>::size();
}
iterator insert(iterator_c _P, const T&_X = T())
{
return list<T>::insert(_P, _X);
}
private:
iterator end(){ return iterator(); }
};
int main(int argc, char* argv[])
{
Circle<int> c;
c.push_back(1);
Circle<int>::iterator_c i = c.begin();
c.insert(i, 6);
//c.end();
size_t s = c.size();
return 0;
}
Top
回复人:roger_77(roger007-阿生) ( ) 信誉:100 2006-10-10 16:24:02 得分:2
?
up后
再看看
Top
回复人:lj860603(跑吧,键键) ( ) 信誉:100 2006-10-10 16:31:49 得分:2
?
up
Top
回复人:coldwindtang(风) ( ) 信誉:100 2006-10-12 15:41:42 得分:0
?
谢谢大家。我试试,可以的话加分结贴。
PS:这不是作业贴,是我一直不清楚,怎么自己写STL,然后做到可以这样用:
Circle<int> mycircle;
即用<int>来指定元素类型。
Top
回复人:healer_kx(天降甘草:又要上班了...555 555) ( ) 信誉:98 2006-10-12 16:05:39 得分:0
?
楼主学STL的想法看我的帖子,要是学习算法,看别人的帖子。
Top
回复人:weijiangshanwww(天气预报:今天会下分,偶尔下几颗星星!) ( )信誉:100 2006-10-12 16:09:48 得分:2
?
!!!!mark and UP!
Top
回复人:Dugowe(闲看庭前花开花落) ( ) 信誉:100 2006-10-12 17:58:33 得分:2
?
!!!!mark and UP! 后面的排好队形
Top
回复人:helanshan(C++) ( ) 信誉:100 2006-10-12 20:37:42 得分:2
?
那么多分,先顶再说..
Top
回复人:Arthur_(凉咖啡)( ) 信誉:100 2006-10-12 20:44:45 得分:2
?
...
頂有分麼
唉如果當年學習了stl...
Top
回复人:billfrish() ( ) 信誉:100 2006-10-12 21:04:16 得分:2
?
我看到过一本书专门介绍用STL编数据结构,挺好的
Top
回复人:baiyu123(学习JAVAing)( ) 信誉:100 2006-10-12 21:05:27 得分:2
?
up
Top
回复人:coldwindtang(风) ( ) 信誉:100 2006-10-17 16:51:10 得分:0
?
想加100分上去,怎么加啊?=.-
Top
回复人:coldwindtang(风) ( ) 信誉:100 2006-10-17 16:51:44 得分:0
?
想加100分上去,怎么加啊?=.-
Top
回复人:wanfustudio(雁南飞:为作业社区发扬光大奋斗!) ( ) 信誉:97 2006-10-17 18:37:07 得分:2
?
看论坛制度,似乎一班人没有那个权利
不晓得了
Top
回复人:OOPhaisky(异化$渴望成功~~) ( ) 信誉:100 2006-10-17 19:20:54 得分:2
?
楼主可以看看STL中list容器的源代码,SGI STL的list就是“双向循环链表”。
看看高人们是如何实现,应该很有参考价值^_^
Top
回复人:shone_sun() ( ) 信誉:100 2006-10-17 19:37:55 得分:2
?
upup
Top
回复人:wanfustudio(雁南飞:为作业社区发扬光大奋斗!) ( ) 信誉:97 2006-10-17 21:24:31 得分:2
?
帮顶,给多少分
!!!
沉了
再顶!