上述顺序表定义中的数据成员 Maxsize是为判断顺序 表是否为满而设,last是为便于判断顺序表是否为空、求 表长、置空表而设 last= Maxsize-1表示顺序表已满,此时再进行插入 操作会导致上溢错误; last=-1表示顺序表为空表,此时再进行删除操作 导致下溢错误; last+1代表顺序表的表长 将last赋值为-1可实现置空表操作。 由上可知:合理地设置数据成员可大大简化算法的设计 及提高算法的效率。顺序表不仅仅包含存放其数据元 素的数组,它还应包括一些有用的数据成员,以及相 应的操作,它们是一个整体 2021222
2021/2/22 11 上述顺序表定义中的数据成员 Maxsize 是为判断顺序 表是否为满而设，last 是为便于判断顺序表是否为空、求 表长、置空表而设： last=Maxsize –1表示顺序表已满，此时再进行插入 操作会导致上溢错误； last=-1 表示顺序表为空表，此时再进行删除操作 会导致下溢错误； last+1 代表顺序表的表长； 将 last 赋值为 –1 可实现置空表操作。 由上可知：合理地设置数据成员可大大简化算法的设计 及提高算法的效率。顺序表不仅仅包含存放其数据元 素的数组，它还应包括一些有用的数据成员，以及相 应的操作，它们是一个整体：
顶序表之整体概念: 数组 变量 操作算法 data Maxsize 初始化操作 last 插入操作 删除操作 last 查找操作 数组下标 排序操作 Maxsize-I 2021222 12
2021/2/22 12 顺序表之整体概念： data 0 1 last Maxsize last 数组下标 数组 变量 操作算法 Maxsize-1 初始化操作 插入操作 删除操作 查找操作 排序操作 . . . . . . . . . . . . . .
顺序表的基本操作(算法) (1)顺序表初始化操作算法 template <class Type> Seqlist<Type>: Seqlist(int sz ∥构造函数,通过指定参数sz定义数组的长度,并将last置为-1 /|置空表 if(sz>0 Maxsize sz ast=-1 ∥/ast+1=0,表明表中无元素,空表 data=new Type[ Maxsize 2021222
2021/2/22 13 顺序表的基本操作（算法） （1）顺序表初始化操作算法 template <class Type> Seqlist<Type>::Seqlist(int sz) //构造函数，通过指定参数sz 定义数组的长度，并将last 置为 –1 //即置空表 { if(sz>0) { Maxsize=sz; last=-1; // last+1=0 , 表明表中无元素，空表 data=new Type[Maxsize]; } }
(2)顺序表查找操作 template <class Type> int Seqlist<Type> Find(Type &x) const /找ⅹ在表中位置,若查找成功,函数返回x的位置 /则返回-1 nt 1=0 while(i<=last && data1!=x)1++ if(last)return -1 else return 1 2021222
2021/2/22 14 （2）顺序表查找操作 template <class Type> int Seqlist<Type>::Find(Type & x) const //查找 x 在表中位置，若查找成功，函数返回 x 的位置 //否则返回－1 { int i=0; while(i<=last && data[i]!=x) i++; if (i>last) return –1; else return i; }
(3)顺序表插入操作 为了把新元素ⅹ插入到i处,必须把从i到last的所 有元素成块向后移动一个元素位置,以空出第i个位 置供ⅹ插入: 先移动后面元素 2021222
2021/2/22 15 （3）顺序表插入操作 为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所 有元素成块向后移动一个元素位置，以空出第 i 个位 置供 x 插入： x 3 2 1 先移动后面元素 0 i-1 i i+1 last . . . . . . . . . . . . . . . . .