`
xpp02
  • 浏览: 1013241 次
社区版块
存档分类
最新评论

list c++template

 
阅读更多

以一个现成的模板实现了线性表的顺序结构实现，VC6.0调试OK

请大家以开源的方式来完善这个算法 ，以跟贴方式来添加代码

请大家往这个下面继续添加完整的可以运行的线性表的顺序结构实现代码

/*

线性表的顺序结构实现，数组C++实现法，VC调试OK
线性表可以用顺序结构（是用数组线性表来实现）来实现，也可以用链式结构来实现。
我们以顺序结构为例：
线性表的基本的操作：
(1)创建线性表
(2)初始化线性表SeqList()
(3)插入元素Insert(Type& x ,int i)
(4)删除元素Remove(Type& x)
(5)查找元素
按位置查找对象Get(int i)
按对象查找位置Find(Type& x)
(6)计算表长度Length();

扩展功能：
顺序表满判断IsFull()
顺序表空判断IsEmpty()
输出顺序表的数据PrintList()
输入顺序表的数据InputList()
判断x是否在表中IsIn(Type& x)
寻找x的后继Next(Type& x)
寻找x的前驱Prior(Type& x)
合并两个数组Union(SeqList<Type>& LA,SeqList<Type>& LB)
求两个数组的交集


注意：
(1)插入元素时要把插入位置后的所有元素“从后往前”各向后移动一个位置。
(2)删除元素时要把删除位置后的所有元素“从前往后”各向前移动一个位置。

*/
//SeqList.h
#ifndef SEQLIST_H
#define SEQLIST_H

template< class Type> class SeqList
{
public:
SeqList(int MaxSize=6);//构造函数定义和实现
~SeqList() {delete []data; }//析构函数定义和实现
int Length() const {return last+1;}//计算表长度定义和实现
Type Get(int i)　　　　　　//取第i个元素的值
{if (i<0||i>last)
cerr<<"out of range...";
else
return data[i];
}
int Find(Type& x) const;//定位函数：找x在表中的位置
int Insert(Type& x ,int i);//插入x在表中第i个位置处
int Remove(Type& x);//删除x
//新添加功能
int Next(Type& x);//寻找x的后继
int Prior(Type& x);//寻找x的前驱
int IsEmpty() {return last==-1;}//判断顺序表是否为空，空则返回1；否则返回0
int IsFull() {return last==MaxSize-1;} //判断顺序表满否，满则返回1；否则返回0
int IsIn(Type& x);//判断x是否在表中
void Union(SeqList<Type>& LA,SeqList<Type>& LB);//合并LA,LB,重复元素只留一下
void Intersection(SeqList<Type>& LA,SeqList<Type>& LB);//求LA,LB中的共有元素
void PrintList();//输出顺序表的数据
void InputList();//输入顺序表的数据

private:
Type* data;//存放顺序表的数组
int MaxSize;//顺序表最大可容纳项数
int last;//顺序表当前是已存表项的最后位置
};
//构造函数，通过描写参数sz定义数组的长度。
template <class Type> SeqList<Type>::SeqList(int sz)
{
if(sz>0)
MaxSize=sz;
else
MaxSize=6;
last=MaxSize - 1;
data=new Type[MaxSize];

}

//定位，找x在表中位置 ，若查找成功，函数 返回表项的位置，否则函数返回-1
template <class Type> int SeqList<Type>::Find(Type& x) const
{
int i=0;
while(i<=last&&data[i]!=x)
i++;
if(i>last)
return -1;
else
return i;
}

//判断x是否在表中
template <class Type> int SeqList<Type>::IsIn(Type& x)
{
int i=0,found=0;
while(i<==last&&!found)
if(data[i]!=x)
i++;
else
found=1;
return found;}

//插入x在表中第i个位置处。函数返回插入是否成功的信息，若为0则插入不成功。
template <class Type> int SeqList<Type>::Insert(Type& x,int i)
{
if(i<0||i>last+1||last==MaxSize-1)
return 0;
else
{
last++;
for(int j=last;j>i;j--)
data[j]=data[j-1];
data[i]=x;
return 1;}
}
template <class Type> int SeqList<Type>::Remove(Type& x)
{
int i=Find(x);
if(i>=0)
{
last--;
for(int j=i;j<=last;j++)
data[j]=data[j+1];
return 1;
}
return 0;
}
//寻找x的后继数据
template <class Type> int SeqList<Type>::Next(Type& x)
{
if(i>=0&&i<last)
return i+1;
else
return -1;
}
//寻找x的前驱数据
template <class Type> int SeqList<Type>::Prior(Type& x)
{
int i=Find(x);
if(i>0&&i<=last)
return i-1;
else
return -1;
}

//合并顺序表LA与LB，重复元素只留一下。这个值得深入研究
template <class Type> void SeqList<Type>::Union(SeqList<Type>& LA,SeqList<Type>& LB)
{
int n=LA.Length();
int m=LB.Length();
for(int i=0;i<m;i++)
{
Type x=LB.Get(i);
int k=LA.Find(x);
if(k==-1)
{
LA.Insert(n+1,x);
n++;
}
}
}
//求顺序表LA与LB中的共有元素，其实也是寻找交集元素
template <class Type> void SeqList<Type>::Intersection(SeqList<Type> &LA,SeqList<Type>& LB)
{
int n=LA.Length();
int m=LB.Length();
int i=0;
while(i<n)
{
Type x=LA.Get(i);
int k=LB.Find(x);
if(-1==k)
{
LA.Remove(x);
n--;
}
else
i++;
}
}

//自己写的输出数据方法
template <class Type> void SeqList<Type>::PrintList()
{
int l=Length()-1;
for(int i=0;i<l;i++)
cout<<"list"<<i<<"= "<<data[i]<<endl;;
}
//自己写的输入数据方法
template <class Type> void SeqList<Type>::InputList()
{
int l=Length()-1;
for(int i=0;i<l;i++)
{
cout<<"enter data["<<i<<"]:";
cin>>data[i];
}}
#endif

//调用程序

//seqlist.cpp
/* 测试主程序 * *- */
#include <iostream.h>
#include "SeqList.h"
//const defaultSize=8;
void main()
{
SeqList<int> Intseqlist(8);
cout<<"Intseqlist.length:"<<Intseqlist.Length()<<endl;
cout<<"未初始化的数据是没有规则的如下："<<endl;
Intseqlist.PrintList();

cout<<"输入int到数组:"<<endl;
Intseqlist.InputList();

cout<<"新的数据:"<<endl;
Intseqlist.PrintList();

//add check get(x) code
int tv;
cout<<"Get(x):enter a int:";
cin>>tv;
cout<<"get(x)="<<Intseqlist.Get(tv)<<endl;

//请各位多写测试代码，争取把上面的类的功能都用一次
//这就是一个简单的程序测试工程师的一部分工作内容

}

//欢迎大家从这个线性表的数组实现代码中更加完美

以一个现成的模板实现了线性表的顺序结构实现，VC6.0调试OK

请大家以开源的方式来完善这个算法 ，以跟贴方式来添加代码

请大家往这个下面继续添加完整的可以运行的线性表的顺序结构实现代码

/*

线性表的顺序结构实现，数组C++实现法，VC调试OK
线性表可以用顺序结构（是用数组线性表来实现）来实现，也可以用链式结构来实现。
我们以顺序结构为例：
线性表的基本的操作：
(1)创建线性表
(2)初始化线性表SeqList()
(3)插入元素Insert(Type& x ,int i)
(4)删除元素Remove(Type& x)
(5)查找元素
按位置查找对象Get(int i)
按对象查找位置Find(Type& x)
(6)计算表长度Length();

扩展功能：
顺序表满判断IsFull()
顺序表空判断IsEmpty()
输出顺序表的数据PrintList()
输入顺序表的数据InputList()
判断x是否在表中IsIn(Type& x)
寻找x的后继Next(Type& x)
寻找x的前驱Prior(Type& x)
合并两个数组Union(SeqList<Type>& LA,SeqList<Type>& LB)
求两个数组的交集


注意：
(1)插入元素时要把插入位置后的所有元素“从后往前”各向后移动一个位置。
(2)删除元素时要把删除位置后的所有元素“从前往后”各向前移动一个位置。

*/
//SeqList.h
#ifndef SEQLIST_H
#define SEQLIST_H

template< class Type> class SeqList
{
public:
SeqList(int MaxSize=6);//构造函数定义和实现
~SeqList() {delete []data; }//析构函数定义和实现
int Length() const {return last+1;}//计算表长度定义和实现
Type Get(int i)　　　　　　//取第i个元素的值
{if (i<0||i>last)
cerr<<"out of range...";
else
return data[i];
}
int Find(Type& x) const;//定位函数：找x在表中的位置
int Insert(Type& x ,int i);//插入x在表中第i个位置处
int Remove(Type& x);//删除x
//新添加功能
int Next(Type& x);//寻找x的后继
int Prior(Type& x);//寻找x的前驱
int IsEmpty() {return last==-1;}//判断顺序表是否为空，空则返回1；否则返回0
int IsFull() {return last==MaxSize-1;} //判断顺序表满否，满则返回1；否则返回0
int IsIn(Type& x);//判断x是否在表中
void Union(SeqList<Type>& LA,SeqList<Type>& LB);//合并LA,LB,重复元素只留一下
void Intersection(SeqList<Type>& LA,SeqList<Type>& LB);//求LA,LB中的共有元素
void PrintList();//输出顺序表的数据
void InputList();//输入顺序表的数据

private:
Type* data;//存放顺序表的数组
int MaxSize;//顺序表最大可容纳项数
int last;//顺序表当前是已存表项的最后位置
};
//构造函数，通过描写参数sz定义数组的长度。
template <class Type> SeqList<Type>::SeqList(int sz)
{
if(sz>0)
MaxSize=sz;
else
MaxSize=6;
last=MaxSize - 1;
data=new Type[MaxSize];

}

//定位，找x在表中位置 ，若查找成功，函数 返回表项的位置，否则函数返回-1
template <class Type> int SeqList<Type>::Find(Type& x) const
{
int i=0;
while(i<=last&&data[i]!=x)
i++;
if(i>last)
return -1;
else
return i;
}

//判断x是否在表中
template <class Type> int SeqList<Type>::IsIn(Type& x)
{
int i=0,found=0;
while(i<==last&&!found)
if(data[i]!=x)
i++;
else
found=1;
return found;}

//插入x在表中第i个位置处。函数返回插入是否成功的信息，若为0则插入不成功。
template <class Type> int SeqList<Type>::Insert(Type& x,int i)
{
if(i<0||i>last+1||last==MaxSize-1)
return 0;
else
{
last++;
for(int j=last;j>i;j--)
data[j]=data[j-1];
data[i]=x;
return 1;}
}
template <class Type> int SeqList<Type>::Remove(Type& x)
{
int i=Find(x);
if(i>=0)
{
last--;
for(int j=i;j<=last;j++)
data[j]=data[j+1];
return 1;
}
return 0;
}
//寻找x的后继数据
template <class Type> int SeqList<Type>::Next(Type& x)
{
if(i>=0&&i<last)
return i+1;
else
return -1;
}
//寻找x的前驱数据
template <class Type> int SeqList<Type>::Prior(Type& x)
{
int i=Find(x);
if(i>0&&i<=last)
return i-1;
else
return -1;
}

//合并顺序表LA与LB，重复元素只留一下。这个值得深入研究
template <class Type> void SeqList<Type>::Union(SeqList<Type>& LA,SeqList<Type>& LB)
{
int n=LA.Length();
int m=LB.Length();
for(int i=0;i<m;i++)
{
Type x=LB.Get(i);
int k=LA.Find(x);
if(k==-1)
{
LA.Insert(n+1,x);
n++;
}
}
}
//求顺序表LA与LB中的共有元素，其实也是寻找交集元素
template <class Type> void SeqList<Type>::Intersection(SeqList<Type> &LA,SeqList<Type>& LB)
{
int n=LA.Length();
int m=LB.Length();
int i=0;
while(i<n)
{
Type x=LA.Get(i);
int k=LB.Find(x);
if(-1==k)
{
LA.Remove(x);
n--;
}
else
i++;
}
}

//自己写的输出数据方法
template <class Type> void SeqList<Type>::PrintList()
{
int l=Length()-1;
for(int i=0;i<l;i++)
cout<<"list"<<i<<"= "<<data[i]<<endl;;
}
//自己写的输入数据方法
template <class Type> void SeqList<Type>::InputList()
{
int l=Length()-1;
for(int i=0;i<l;i++)
{
cout<<"enter data["<<i<<"]:";
cin>>data[i];
}}
#endif

//调用程序

//seqlist.cpp
/* 测试主程序 * *- */
#include <iostream.h>
#include "SeqList.h"
//const defaultSize=8;
void main()
{
SeqList<int> Intseqlist(8);
cout<<"Intseqlist.length:"<<Intseqlist.Length()<<endl;
cout<<"未初始化的数据是没有规则的如下："<<endl;
Intseqlist.PrintList();

cout<<"输入int到数组:"<<endl;
Intseqlist.InputList();

cout<<"新的数据:"<<endl;
Intseqlist.PrintList();

//add check get(x) code
int tv;
cout<<"Get(x):enter a int:";
cin>>tv;
cout<<"get(x)="<<Intseqlist.Get(tv)<<endl;

//请各位多写测试代码，争取把上面的类的功能都用一次
//这就是一个简单的程序测试工程师的一部分工作内容

}

//欢迎大家从这个线性表的数组实现代码中更加完美

分享到：
| 为什么我要转载文章？
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Tools - Template Sequence list

    For using，you can open ReadMe file.

    C++ STL 参考手册Cpp_STL_ReferenceManual.pdf

    C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环...

    stl标准库 C++ Standard Library（《C++标准库》中文资料为侯捷译）英文pdf&chm 中文pdf

    To make full use of its components-and to benefit from their power-you need a resource that does far more than list the classes and their functions. The C++ Standard Library not only provides ...

    Practical C++ Programming C++编程实践

    Standard Template Library STL Basics Class List-A Set of Students Creating a Waiting List with the STL List Storing Grades in a STL Map Putting It All Together Practical Considerations When Using the...

    Tools - Template List

    For using，you can open ReadMe file.

    C++栈类模板

    C++栈类模板 template class Stack { public: Stack(void); void Push(const T &item;); //将元素item压入栈 T Pop(void); //将栈顶元素弹出栈 void ClearStack(void); T Peek(void)const; //访问栈顶元素 ...

    The C++ Standard Library 2nd Edition(高清)pdf

    To make full use of its components - and to benefit from their power - you need a resource that does far more than list the classes and their functions. The C++ Standard Library - A Tutorial and ...

    Programming with C++

    Chapter 22: Sequence Containers–vector, list and deque 532 Chapter 23: Associative Containers–set, multiset, map and multimap 559 Chapter 24: Bit Sets 578 Chapter 25: Algorithms 589 REFERENCES 625 ...

    神书-C++ STL源码解析-高清完整版

    To make full use of its components - and to benefit from their power - you need a resource that does far more than list the classes and their functions. The C++ Standard Library - A Tutorial and ...

    C++动态数组类模板

    template class Array { public: Array(int sz = 50); Array(const Array&lt;T&gt; &A); ~Array(void); Array&lt;T&gt;& operator = (const Array&lt;T&gt; &rhs;); //重载=,使数组对象可以整体赋值 T& operator[](int n); //...

    C++标准模板库STL初步(2)

    组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的几个头文件：、、&lt;list&gt;、、、、、、、、、、和。文件中主要介绍了前面八个的使用，并且重点介绍了他们的属性和一些成员函数的使用。

    single-list.rar_single

    Single list of data structure written in C++ template

    C++ Standard Library - A Tutorial and Reference

    To make full use of its components - and to benefit from their power - you need a resource that does far more than list the classes and their functions. The C++ Standard Library - A Tutorial and ...

    C++ for Programmers

    Start with an introduction to C++ using an early classes and objects approach, then rapidly move on to more advanced topics, including templates, exception handling, the Standard Template Library (STL...

    The C++ Standard Library – A Tutorial and Reference, 2nd Edition

    To make full use of its components - and to benefit from their power - you need a resource that does far more than list the classes and their functions. The C++ Standard Library - A Tutorial and ...

    顺序表的C++程序实现

    void ListUnion(SeqList&lt;int&gt; &ListA;,SeqList&lt;int&gt; &ListB;) { cout两个参数对象的顺序表："; ListA.SLPrint(); ListB.SLPrint(); int n,m; int XX,i=0; n=ListA.ListLength(); m=ListB.ListLength(); int ...

    Loki库源码(泛型模式C++库)

    　The library makes extensive use of C++ template metaprogramming and implements several commonly used tools: typelist, functor, singleton, smart pointer, object factory, visitor and multimethods. ...

    The.C++.Standard.Library.A.Tutorial.and.Reference.2nd.Edition

    To make full use of its components–and to benefit from their power–you need a resource that does far more than list the classes and their functions. The C++ Standard Library: A Tutorial and ...

    LinearList.zip

    线性表C++语言实现，包含《数据结构算法与应用-C++语言描述》练习题。 template class LinearList { public: LinearList(int MaxListSize = 10);//构造函数 LinearList(LinearList&lt;T&gt;& L);//复制构造函数 ~Linear...

    C++11 TypeList 妙用

    源码展示: ... template &lt;typename&gt; struct typelist; typedef typelist &lt;int&gt; defaultPolicys; template &lt;typename&gt; struct concat; template struct concat&lt;typelist&gt;， typelist&lt;B&gt; &gt; { typ

Magicbox
Global site tag (gtag.js) - Google Analytics