顺序表类定义 2.2顺序表一向量 onst int Max length=100;∥假定最大长度为100 用定长的一维数组存储结构 ■主要特性: ∥顺序最大长度 t curr len;∥顺序表当前长度 元素的类型相同 ELEM* nodelist;∥私有变量,存储顺序表实例的向量 元素顺序地存储在连续存储空间 以下列出成员函数〔顺序表的函数集) 中 int curr;∥当前下标,顺序表的公共变量 list(const int size);∥ constructor函数创建新表 ■通过下标读写即可指定位置元素 ∥ destructor函数,将该表实例删去 id clear0;/清除内容,成为空表 新有,食究 北大举张铭写 意叔有 k-1 mske oid setFirst0;∥第一个元素位量赋予当前下标curr nodelist oid nexto ∥urr下移一格,即curr+1 miZ void prev(: 将cu上移一格,即cur-1 bool islnListo;∥若curr位量有值时,返回 (a)在t位置插入元素item oid append( onst EleM&);∥在表尾增添新元素 void insert(const ELEM&);∥在当前下标cur插入 ELEM remove0;/返回curr的位置元章值,并删除 maize bool is Empty 肖线性表为空时,返回true ELEM curr Value0; ∥返回ur位的元素值 ∥返回此表的当前实际长度 中ad (b)删除t位置的元素 匙盒大管皇歌张节写 新有,聊邮究 插入算法执行时间 删除算法时间代价 元素总个数为n,各个位置插入 与插入操作相似,O(m) 的概率相等为p=1/n ■平均移动元素次数为 顺序表存取元素方便,时间代价 为O(1) ∑1/n·(n-1) 但插入、删除操作则付出时间代 价O(m) ■总时间开销估计为O(n) back 真大带酱张储 北大管息歌张帖习2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 2.2 顺序表—向量 „ 采用定长的一维数组存储结构 „ 主要特性: „ 元素的类型相同 „ 元素顺序地存储在连续存储空间 中 „ 通过下标读写即可指定位置元素 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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(); //清除内容，成为空表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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(); // 返回此表的当前实际长度 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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 位置的元素 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 back next 插入算法执行时间 „ 元素总个数为n，各个位置插入 的概率相等为p＝1/n „ 平均移动元素次数为 „ 总时间开销估计为O（n） n-1 i 0 1/ ( - ) 2 n n ni = ∑ • ≈ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 back next 删除算法时间代价 „ 与插入操作相似，O(n) „ 顺序表存取元素方便，时间代价 为O(1) „ 但插入、删除操作则付出时间代 价O(n)