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

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;

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

}

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

分享到:
评论

相关推荐

    c++ template中文版

    在标题“C++ Template中文版”以及重复的描述“C++ templatec++ templatec++ template”中,我们可以明确地了解到这份文档是关于C++模板(Template)的详细介绍。C++模板是C++语言中一个非常强大的特性,它允许...

    C++Template

    侯捷老师的《C++Template》一书深入浅出地介绍了C++模板的各个方面,包括基础概念、高级技巧以及实际应用,对于理解和掌握C++模板编程有着极大的帮助。通过阅读这本书,开发者可以更好地利用模板这一强大的工具,...

    C++Template电子书及代码

    这份"C++Template电子书及代码"资源为学习C++模板提供了宝贵的材料,下面我们将深入探讨C++模板的基础知识、应用场景以及一些高级特性。 1. 模板基础: - 函数模板:C++函数模板允许我们创建不依赖于特定数据类型...

    C++ template教程 中文版和英文版

    此外,中文版教程可能还会解释类模板,它是创建通用类的基础,如STL(标准模板库)中的容器(如vector和list)和算法。 英文版的CHM教程则提供了一种不同的学习体验。CHM(Compiled Help Manual)是一种常见的帮助...

    C++ Template STL C++11新特性解析与应用

    接着,STL(Standard Template Library,标准模板库)是C++标准库的重要组成部分,包括容器、迭代器、算法和函数对象。容器如`std::vector`、`std::list`和`std::map`提供了数据结构,用于存储和管理对象。迭代器...

    Tools - Template Sequence list

    这个名为"Tools - Template Sequence list"的压缩包文件似乎包含了一个特定实现或应用这种工具的资源。在这个压缩包中,我们注意到一个名为"Version 2"的子文件,这可能意味着这是一个更新版本或者有多个迭代版本的...

    C++template(c++图书)

    比如,STL(Standard Template Library,标准模板库)中的`vector`、`list`、`map`等容器都是类模板的实例。类模板定义包含模板参数,这些参数在实例化类时会被具体的数据类型替换。例如,`std::vector&lt;int&gt;` 和 `...

    c++ stl list总结

    C++ STL(Standard Template Library,标准模板库)中的`list`是一种双向链表容器,它提供了高效的操作,如插入和删除元素。在这个总结中,我们将深入探讨`list`的特性和使用方法,以及如何在实际编程中充分利用它。...

    [C++][STL] C++ STL 之 List

    C++ Standard Template Library(STL)是C++编程中不可或缺的一部分,它提供了一组高效且可重用的数据结构和算法。其中,`list`容器是STL中的一个核心组件,主要用于处理序列型数据。本文将深入探讨C++ STL中的`list...

    重写C++的list实现增 删 改的功能

    在C++编程中,STL(Standard Template Library,标准模板库)提供了一组高效的数据结构和算法,其中包括`std::list`。`std::list`是一个双向链表,支持快速的插入和删除操作,但随机访问性能相对较弱。在某些情况下...

    标准C++的StringList

    在C++中,我们通常会利用STL(Standard Template Library)中的容器,如`std::vector`或`std::list`,来实现类似的功能,但这些容器可能没有`TStringList`那么直观或方便对于字符串操作。 `TStringList`的特点包括...

    C++ 6.0 Template(模板库)参考手册.zip

    1. 容器(Containers):如`std::vector`、`std::list`、`std::map`等,提供了存储和操作数据的数据结构。 2. 迭代器(Iterators):遍历容器的接口,具有类似指针的行为,如`std::begin`和`std::end`。 3. 算法...

    C++ STL list 遍历删除出错解决方案

    在C++编程中,STL(Standard Template Library,标准模板库)提供了多种容器,如vector、list等,用于高效地存储和操作数据。本篇文章主要探讨的是在使用STL list时遇到的遍历删除元素过程中常见的错误及其解决方案...

    C++标准模板库(The C++ Standard Templete Libray)

    《C++标准模板库(The C++ Standard Template Library)》是一本深入探讨C++标准库的权威书籍,由Nicolai M. Josuttis撰写。本书不仅涵盖了C++标准库的基础概念,还提供了丰富的实例和深入的分析,是编程高手必须熟练...

    C++_标准模板库(STL) pdf 高清版

    - `list`:双向链表,允许在任意位置进行插入和删除,但随机访问较慢。 - `set`和`multiset`:基于红黑树的集合,存储唯一或重复的排序元素。 - `map`和`multimap`:关联容器,通过键值对存储元素,自动保持键的...

    C++ Standard template Library英文版和Effective STL中文版

    C++ Standard Template Library (STL) 是C++编程语言中不可或缺的一部分,它提供了一组高效、可重用的容器、迭代器、算法和函数对象。STL的核心思想是泛型编程,即通过模板来实现代码的复用,使得开发者可以处理不同...

    c模拟c++ stl list

    在C编程环境中,我们通常没有内置的容器类如C++中的STL(Standard Template Library)。STL中的`std::list`是一个双链表容器,它提供了高效的操作,如插入和删除元素,而无需移动元素。然而,为了在C语言中模拟`std:...

    Tools - Template List

    标题“Tools - Template List”指的是一个集合了各种工具模板的资源包,这通常是为了帮助用户在不同的IT项目中快速启动工作。模板可以是代码片段、文档格式、设计模版等,旨在提高效率并确保一致性。这个资源包可能...

Global site tag (gtag.js) - Google Analytics