线性结构：
- 除了外，每个元素都有它的前趋和后继
- 每个元素,它的前驱是,它的后继是
- 只有后继，没有前驱；只有前驱，没有后继
线性表的抽象类
- 创建一个空的线性表create()----C++中一般用构造函数解决
- 清除一个线性表clear()----删除线性表的所有数据元素
- 求线性表的长度Length()----也就是求目前线性表中的元素个数
增加insert(i,x)
- 在线性表第i个位置插入元素x----
删除remove(i)
- 删除线性表第i个位置的元素
查
- 查索引search(x)-----给定元素x，查找是否存在，存在返回x的位置
- 访问元素visit(i)-----给定索引，访问该位置的元素
- 遍历元素traverse()-----顺序访问元素的所有位置
template
class list{
public:
//少了create函数，因为在具体实现时，构造函数可以满足该功能
virtual void clear()=0;
virtual int Length() const=0;
virtual void insert(int i,const elemType& x)=0;
virtual void remove(int i)=0;
virtual int search(const elemType& x) const=0;
virtual elemType visit(int i) const=0;
virtual void traverse() const=0;
virtual ~list(){};//析构函数，delete指针，防止内存泄露
}; 顺序表-----线性表的顺序实现注意，这里基本 *** 作加上virtual原因，是希望其继承类必须实现该函数功能
有关查的 *** 作，如果不希望改变或者不能改变传参的值，要加上const关键字
顺序表类用动态数组去实现
数据成员----
- 线性表第一个元素的起始地址的指针----data
- 数组规模maxsize----也就是目前的数组容量上限
- 数组中当前的元素个数----curLength
template
class seqList:public list{
private:
elemType* data;
int maxsize;
int curLength;
public:
seqList(int initSize=10);//构造函数，默认初始化长度为10
void clear(){ curLength=0;}
int Length() const{ return curLength;}
void insert(int i,const elemType& x);
void remove(int i);
int search(const elemType& x) const;
elemType visit(int i) const{
if(i 为了解决插入元素的容量不足问题，即---curLength==maxsize
需要做一个隐式扩容 *** 作，即容量满后，私有函数去进行扩容，用户无需知道，给用户造成数组永远不会满的假象
private void doublespace();
具体实现---保存在seqList.h文件
#ifndef MY_seqlist
#define MY_seqlist
#include"list.h"
template
class seqList:public list{
private:
elemType* data;
int maxsize;
int curLength;
void doublespace();
public:
seqList(int initSize=10);//构造函数，默认初始化长度为10
void clear(){ curLength=0;}
int Length() const{ return curLength;}
void insert(int i,const elemType& x);
void remove(int i);
int search(const elemType& x) const;
elemType visit(int i) const{
return data[i];
}
void traverse() const;
~seqList(){delete[] data;}
};
//私有扩容 *** 作
template
void seqList::doublespace(){
elemType* tmp=data;
maxsize*=2;
data=new elemType[maxsize];
for(int i=0;i
seqList::seqList(int initSize){
data =new elemType[initSize];
maxsize=initSize;
curLength=0;
}
//查元素
template
int seqList::search(const elemType& x) const{
int i;
for(i=0;i
void seqList::insert(int i,const elemType& x){
//是否需要扩容？
if(curLength==maxsize){
doublespace();
}
//当前第i个位置直到最后的元素右移一位，把第i个位置空出来
for(int j=curLength;j>i;j--){
data[j]=data[j-1];
}
//x放到当前索引位置i，然后表长+1
data[i]=x;
++curLength;
}
//删除
template
void seqList::remove(int i){
for(int j=i;j
using namespace std;
template
void seqList::traverse() const{
for(int i=0;i 插入函数也可以这样写
template
int seqList::search(const elemType& x) const{
int i;
/* for(i=0;i 主程序的测试用例程序---maintest.cpp
#include"list.h"
#include
using namespace std;
int main(){
seqList seq;
seq.insert(0,19);
seq.insert(1,18);
seq.insert(2,88);
seq.insert(3,6);
seq.traverse();
cout< 最初的list.h文件
#ifndef MY_list
#define MY_list
template
class list{
public:
//少了create函数，因为在具体实现时，构造函数可以满足该功能
virtual void clear()=0;
virtual int Length() const=0;
virtual void insert(int i,const elemType& x)=0;
virtual void remove(int i)=0;
virtual int search(const elemType& x) const=0;
virtual elemType visit(int i) const=0;
virtual void traverse() const=0;
virtual ~list(){};//析构函数，delete指针，防止内存泄露
};
#include"seqList.h"
#endif 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）