线性表类模板 template <class T> class List i void clear(; ∥置空线性表 bool isEmpty; ∥线性表为空时,返回true bool append( const T value);∥在表尾添加一个元素vaue,表的长度增1 bool insert(const int p, const value); ∥在位置p上插入一个元素vaue,表的长度增1 bool delete(const int p); ∥删除位置p上的元素,表的长度减1 bool getPos(int p, const T value) ∥查找值为vaue的元素并返回其位置 bool getValue(const int p, T& value) ∥把位置p的元素值返回到变量 value中 bool setvalue( const int p, const value);用vaue修改位置p的元素值 bool getPos(int &p, const T value) ∥把值为vaue的元素所在位置返回到变量p中 } “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0D.6。16
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 16 线性表类模板 template <class T> class List { void clear(); // 置空线性表 bool isEmpty(); // 线性表为空时，返回true bool append(const T value); // 在表尾添加一个元素value，表的长度增1 bool insert(const int p, const T value); // 在位置p上插入一个元素value，表的长度增1 bool delete(const int p); // 删除位置p上的元素，表的长度减 1 bool getPos(int & p, const T value) // 查找值为value的元素并返回其位置 bool getValue(const int p, T& value); // 把位置p的元素值返回到变量value中 bool setValue(const int p, const T value);// 用value修改位置p的元素值 bool getPos (int &p, const T value); // 把值为value的元素所在位置返回到变量p中 };
顺序表( array- based list) 采用定长的一维数组存储结构 也称向量 ■主要特性: 口元素的类型相同 口元素顺序地存储在连续存储空间中, 每一个元素有唯一的索引值 口使用常数作为向量长度 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结拘与算法》,高教社,20.6。1
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 17 顺序表（array-based list） ◼ 采用定长的一维数组存储结构 ◼ 也称向量 ◼ 主要特性: ❑ 元素的类型相同 ❑ 元素顺序地存储在连续存储空间中， 每一个元素有唯一的索引值 ❑ 使用常数作为向量长度
顺序表 数组存储 ■读写其元素很方便,通过下标即可指定位置 口只要确定了首地址,线性表中任意数据元素都可 以随机存取。地址计算如下所示 loc(ki)=loc(o)+ c C= sizeof(T) “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。18
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 18 顺序表 ◼ 数组存储 ◼ 读写其元素很方便 ，通过下标即可指定位置 ❑ 只要确定了首地址，线性表中任意数据元素都可 以随机存取。地址计算如下所示： loc(ki ) = loc(k0 ) + c* i c = sizeof(T)
顺序表 逻辑地址数据元素 存储地址数据元素 下标) k Loc(ko) 0 Loc(ko)+( Loc(ko)+i*c ki Loc(ko)+(n-1*c n-1 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。1s
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 19 顺序表 逻辑地址 (下标) 数据元素 存储地址 数据元素 0 k0 Loc(k0 ) k0 1 k1 Loc(k0 )+c k1 … … … … i ki Loc(k0 )+i*c ki … … n-1 kn-1 Loc(k0 )+(n-1)*c kn-1
顺序表类定义 class arrList: public List<T> ∥顺序表,向量 private ∥线性表的取值类型和取值空间 T *aList ∥私有变量,存储顺序表的实例 int max Size; ∥私有变量,顺序表实例的最大长度 int curLen ∥私有变量,顺序表实例的当前长度 int position ∥私有变量,当前处理位置 public ∥顺序表的运算集 arrList(const int size)t ∥创建一个新的顺序表,参数为表实例的最大长度 maxSize= size: alist= new T[ Size]; curLen position =0; -ariSto ∥析构函数,用于消除该表实例 delete I aList; void clear( t ∥将顺序表存储的内容清除,成为空表 delete I aList; curLen= position = 0; aList= new T[maxSize]; int length ∥返回此顺序表的当前实际长度 bool append(const T value) ∥在表尾添加一个元素vaue,表的长度增1 bool insert(const int p, const T value); ∥在位置p上插入一个元素vaue,表的长度增1 bool delete(const int p) ∥删除位置p上的元素,表的长度减1 bool setValue(const int p, const t value;∥用vaue修改位置p的元素值 bool getValue(const int p, T& value ∥把位置p的元素值返回到变量vaue中 bool getPos(int p const T value); ∥查找值为va|ue的元素,并返回第1次出现的位置 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。20
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 20 顺序表类定义 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); // 在表尾添加一个元素value，表的长度增1 bool insert(const int p, const T value); // 在位置p上插入一个元素value，表的长度增1 bool delete(const int p); // 删除位置p上的元素，表的长度减 1 bool setValue(const int p, const T value); // 用value修改位置p的元素值 bool getValue(const int p, T& value); // 把位置p的元素值返回到变量value中 bool getPos(int & p. const T value); // 查找值为value的元素，并返回第1次出现的位置 };