implate<class ELEM> class list/线性表类模板list,模板参数ELEM listo;∥刨建一个空的新线性表 clist(; ∥/从计算机存储空间删去整个线性表 void clear0;∥将该线性表的全部元素清除,成为空表 void append( ELEM value);∥尾附函数,在表尾加新元素 void insert(int i, ELEM value);∥/插入函数,在第i号位插入 void remove(int 1) ∥删除函数,删去第号元素 baCELEM fetch(int;/读取,返回第i个元素的值 }北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 6
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 back next template<class ELEM> class list //线性表类模板list，模板参数ELEM { list(); // 创建一个空的新线性表 ~list(); // 从计算机存储空间删去整个线性表 void clear() ; // 将该线性表的全部元素清除，成为空表 void append(ELEM value) ; // 尾附函数，在表尾加新元素 void insert(int i, ELEM value) ; // 插入函数，在第i号位插入 void remove(int i); // 删除函数，删去第i号元素 ELEM fetch(int i); //读取，返回第i个元素的值 }
22顺序表一向量 采用定长的一维数组存储结构 ■主要特性: 元素的类型相同 元素顺序地存储在连续存储空间 中 通过下标读写即可指定位置元素 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 7
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 2.2 顺序表—向量 采用定长的一维数组存储结构 主要特性: 元素的类型相同 元素顺序地存储在连续存储空间 中 通过下标读写即可指定位置元素
顺序表类定义 const int max length=100;/假定最大长度为100 class list i ∥顺序表,向量 private Int maize ∥顺序表最大长度 int curr len;∥顺序表当前长度 ELEM* nodelist;∥私有变量,存储顺序表实例的向量 publIc: ∥以下列出成员函数(顺序表的函数集) int curre;∥当前下标,顺序表的公共变量 ist( const int size);∥ constructor函数,创建新表 cristo ∥ destructor函数,将该表实例删去 void clear(;/清除内容,成为空表 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 8
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 back next 顺序表类定义 const int Max_length = 100; // 假定最大长度为100 class list { // 顺序表，向量 private : int msize; // 顺序表最大长度 int curr_len; // 顺序表当前长度 ELEM* nodelist; //私有变量，存储顺序表实例的向量 public: //以下列出成员函数（顺序表的函数集) int curr; //当前下标，顺序表的公共变量 list(const int size) ; // constructor函数,创建新表 ~list(); //destructor函数，将该表实例删去 void clear(); //清除内容，成为空表
void set First(;∥第一个元素位置赋予当前下标curr void nexto; ∥/curr下移一格,即curr+1 void prevo; 将curr上移一格,即curr-1 bool isIn list(O;∥若curr位置有值时,返回true void append( const ELEM&);∥在表尾增添新元素 void insert( const ELEM&);∥在当前下标cur插入 ELEM remove;/返回cur的位置元素值,并删除 bool isEmpty 0; ∥线性表为空时,返回true ELEM currValueo 返回curr位置的元素值 It length ∥返回此表的当前实际长度 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 9
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 back next void setFirst(); // 第一个元素位置赋予当前下标curr void next(); // curr下移一格，即curr+1 void prev(); //将curr上移一格，即curr-1 bool isInList(); // 若curr位置有值时，返回true void append(const ELEM&); //在表尾增添新元素 void insert(const ELEM&); // 在当前下标curr插入 ELEM remove(); //返回curr的位置元素值，并删除 bool isEmpty(); //当线性表为空时，返回true ELEM currValue(); //返回curr位置的元素值。 int length(); // 返回此表的当前实际长度 }
nodelist k-1 maize nodelist仁 Item 01 k maize (a)在t位置插入元素item nodelist k-1 mize nodelist mize (b)删除t位置的元素
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 back next nodelist nodelist i 0 1 t k-1 msize i 0 1 t k msize nodelist nodelist i 0 1 t k-2 msize i 0 1 t k-1 msize (a) 在 t 位置插入元素item (b) 删除 t 位置的元素