赞
踩
1,也称向量,采用定长的一维数组存储结构
2.主要特性
- 元素的类型相同
- 元素顺序地存储在连续存储空间中,每一个元素有唯一的索引值
- 使用常数作为向量长度
3.数组存储
4.读写其元素很方便,通过下标即可指定位置
- 只要确定了首地址,线性表中任意数据元素都可以随机存取
5.元素地址计算如下所示:
- Loc(ki) = Loc(k0)+c*i, c = sizeof(ELEM)
- class arrList::public List<T> //顺序表,向量
- {
- private: //线性表的取值类型和取值空间
- T*alist; //私有变量,存储顺序表的实例
- int maxSize; //私有变量,顺序表实例的最大长度
- int curLen; //私有变量,顺序表实例的当前长度
- int position; //私有变量,当前处理位置
- public:
- arrList(const int size) //创建新表,设置表实例的最大长度
- {
- maxSize=size;
- aList=new T[maxSize];
- curLen=position=0;
- }
- ~arrList() //析构函数,用于消除该表实例
- {
- delete []aList;
- }
- void clear() //将顺序表存储的内容清除,成为空表
- {
- delete []aList;
- curLen=position=0;
- aList=new T[maxSize];
- }
- int length(); //返回当前实际长度
- bool append(const T value); //在表尾添加元素v
- bool insert(const int p,const T value); //插入元素
- bool delete(const int p); //删除位置上的元素
- bool setValue(const int p,const T value); //设置元素值
- bool getValue(const int p,T& value); //返回元素
- bool getPos(int &p,const T value); //查找元素
- };
- //设元素的类型为T,aList是存储顺序表的数组,maxSize是其最大长度;
- //p为新元素value的插入位置,插入成功则返回true,否则返回false
- template<class T> bool arrList<T>::insert(const int p,const T value)
- {
- int i;
- if(curLen>=maxSize) //检查顺序表是否溢出
- {
- cout<<"The list is overflow"<<<endl;
- return false;
- }
- if(p<0||p>currLen) //检查插入位置是否合法
- {
- cout<<"insertion point is illegal"<<endl;
- return false;
- }
- for(i=currLen;i>p;i--)
- aList[i]=aList[i-1]; //从表尾curLen-1起往右移动直到p
- aList[p]=value; //位置p出插入新元素
- curLen++; //表的实际长度增1
- return true;
- }
- template<class T> //顺序表的元素类型为T
- bool arrList<T>::delete(const int p)
- {
- int i;
- if(curLen<=0) //检查顺序表是否为空
- {
- cout<<"No element to delete \n"<<endl;
- return false;
- }
- if(p<0||p>curLen-1) //检查删除位置是否合法
- {
- cout<<"deletion is illegal\n"<<endl;
- return false;
- }
- for(i=p;i<curLen-1;i++)
- aList[i]=aList[i+1]; //从位置p开始每个元素右移直到curLen
- curLen--; //表的实际长度减一
- return true;
- }
顺序表插入删除运算的算法分析
1.表中元素的移动
- 插入:移动n-i个
- 删除:移动n-i-1个
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。