private T[]data; /数组，用于存储顺序表中的数据元素 private int maxsize;/顺序表的容量 private int last; /指示顺序表最后一个元素的位置 接口成员方法的实现： 关于属性成员的几点说明： ①JAVA语言中的数组在内存中占用的存储空间就是一组地址连续的存储单元，所以 在JAVA虚拟处理器中考虑问题时，我们就认为线性表的顺序存储就是把线性表的数据元素 存放到数组中： ②maxsize表示数组的容量：数组的容量可以用System.Aray的Length属性即data.length 来表示，但为了说明顺序表的最大长度（顺序表的容量），在SeqList<-T>类中用字段maxsize 来表示。 ③顺序表中的元素由data(0]开始依次顺序存放，由于顺序表中的实际元素个数一般达不 到maxsize,因此，在SeqList<T>类中需要一个字段（属性）last表示顺序表中最后一个数据 元素在数组中的位置。Lst等于顺序表中最后一个数据元素在数组中的下标： 0<=last<=maxsize-1,last=-l表示顺序表为空。 第1章SeqList<-T>类除了可实现接口IListDS-<T>中的方法外，还可实现一些另外的成员 方法。可实现判断顺序表是否己满isfull()等成员方法。 /利用公有方法getdata(int index)获取data中的元素 public T getdata(int index) return data[index]; /利用公有方法setdata(int index,T value)设置data中的元素的值 public void setdata(int index,T value) data[index]=value; /利用公有方法get1ast()获取1ast的值 public int getlast() return last; /利用公有方法set1ast(int value)设置1ast的值 public void setlast(int value) last value; 21
21 private T[] data; //数组，用于存储顺序表中的数据元素 private int maxsize; //顺序表的容量 private int last; //指示顺序表最后一个元素的位置 接口成员方法的实现； } 关于属性成员的几点说明： ①JAVA 语言中的数组在内存中占用的存储空间就是一组地址连续的存储单元，所以， 在 JAVA 虚拟处理器中考虑问题时，我们就认为线性表的顺序存储就是把线性表的数据元素 存放到数组中： ②maxsize 表示数组的容量；数组的容量可以用 System.Array 的 Length 属性即 data.length 来表示，但为了说明顺序表的最大长度（顺序表的容量），在 SeqList<T>类中用字段 maxsize 来表示。 ③顺序表中的元素由 data[0]开始依次顺序存放，由于顺序表中的实际元素个数一般达不 到 maxsize，因此，在 SeqList<T>类中需要一个字段（属性）last 表示顺序表中最后一个数据 元 素 在 数 组 中 的 位 置 。 Last 等 于 顺 序 表 中 最 后 一 个 数 据 元 素 在 数 组 中 的 下 标 ； 0<=last<=maxsize-1，last=-1 表示顺序表为空。 第 1 章 SeqList<T>类除了可实现接口 IListDS<T>中的方法外，还可实现一些另外的成员 方法。可实现判断顺序表是否已满 isfull()等成员方法。 //利用公有方法 getdata(int index)获取 data 中的元素 public T getdata(int index) { return data[index]; } //利用公有方法 setdata(int index,T value)设置 data 中的元素的值 public void setdata(int index,T value) { data[index]=value; } //利用公有方法 getlast()获取 last 的值 public int getlast() { return last; } //利用公有方法 setlast(int value)设置 last 的值 public void setlast(int value) { last = value;
↓ /利用公有方法getMaxsize()获取maxsize的值 public int getMaxsize() return maxsize; //利用公有方法setMaxsize(int value)设置maxsize的值 public void setMaxsize(int value) { maxsize value; /构造器 public SeqList(int size) if (size >=0) data=(T[])new object[size];/建立一个长度为size,类型为T的数组 this.maxsize=s1ze;//顺序表的容量maxsize=size 1ast=-1;/最后一个元素位置1ast=-1:表示顺序表为空 1 else throw new RuntimeException("初始化大小不能小于g:"+size); 2.基本操作的实现 (1)求顺序表的长度 由于数组是0基数组，即数组的最小下标为0，所以，顺序表的长度就是数组中最后一个 元素的下标last加l。 求顺序表长度的算法实现如下： public int Count() r return last 1; (2)清空操作 清除顺序表中的数据元素是使顺序表为空，此时，last等于-l。 清空顺序表的算法实现如下： public void Clear()
22 } //利用公有方法 getMaxsize()获取 maxsize 的值 public int getMaxsize() { return maxsize; } //利用公有方法 setMaxsize(int value)设置 maxsize 的值 public void setMaxsize(int value) { maxsize = value; } //构造器 public SeqList(int size) { if (size >= 0) { data = (T[])new Object[size]; //建立一个长度为 size，类型为 T 的数组 this.maxsize = size; //顺序表的容量 maxsize = size last=-1; //最后一个元素位置 last = -1；表示顺序表为空。 } else throw new RuntimeException("初始化大小不能小于 0：" + size); } 2．基本操作的实现 （1）求顺序表的长度 由于数组是0基数组，即数组的最小下标为0，所以，顺序表的长度就是数组中最后一个 元素的下标last加1。 求顺序表长度的算法实现如下： public int Count() { return last + 1; } （2）清空操作 清除顺序表中的数据元素是使顺序表为空，此时，last等于-1。 清空顺序表的算法实现如下： public void Clear() {
last =-1; (3)判断线性表是否为空 如果顺序表的last为-l,则顺序表为空，返回true,否则返回false。 判断线性表是否为空的算法实现如下： public boolean IsEmpty() 1f(1ast=-1) return true; else return false; 2 (4)判断顺序表是否为满 如果顺序表为满，last等于maxsize-l,则返回true,否则返回false。 判断顺序表是否为满的算法实现如下： public boolean IsFull() r f(1a5t=maxsize-1)/顺序表已满 f return true; else return false; (5)附加操作 附加操作是在顺序表未满的情况下，在表的末端添加一个新元素，然后使顺序表的st 加1。 附加操作的算法实现如下： public void Append(T item) 23
23 last = -1; } （3）判断线性表是否为空 如果顺序表的last为-1，则顺序表为空，返回true，否则返回false。 判断线性表是否为空的算法实现如下： public boolean IsEmpty() { if (last == -1) { return true; } else { return false; } } （4）判断顺序表是否为满 如果顺序表为满，last等于maxsize-1，则返回true，否则返回false。 判断顺序表是否为满的算法实现如下： public boolean IsFull() { if (last == maxsize - 1)//顺序表已满 { return true; } else { return false; } } （5）附加操作 附加操作是在顺序表未满的情况下，在表的末端添加一个新元素，然后使顺序表的last 加1。 附加操作的算法实现如下： public void Append(T item) {
if(1ast=maxsize·1)/顺序表已满 System.out.println("List is full"); /输出顺序表已满信息提示 return;/返回 data[+last]=item;/在表的末端添加一个新元素，使顺序表的1ast加1 (6)插入操作Insert(Titem,inti) 顺序表的插入是指在顺序表的第i个位置插入一个值为itm的新元素，插入后使原表长为 nf的表(al,a2,.,ai-l,ai,ai+l,.,an)成为表长为n+1的表(al,a2,.,ai-l,item,ai,ai+l,.,an)。i的取值 范围为1≤i≤n+1(n为顺序表的表长=last+1)。为n+1(即last+2)时，表示在顺序表的末尾插 入数据元素。 顺序表上插入一个数据元素的步骤如下： ①判断顺序表是否己满和插入的位置是否正确，表满或插入的位置不正确不能插入： ②如果表未满和插入的位置正确，则将an~ai依次向后移动，为新的数据元素空出位 置。在算法中用循环来实现： ③将新的数据元素插入到空出的第ⅰ个位置上： ④修改ast(相当于修改表长)，使它仍指向顺序表的最后一个数据元素。 图2.4为顺序表的插入探作示意图。 插入30 112336458060406. (a)插入前 112336☐458060406. (b)移动 11233630458060406- (c)插入后 图2.4顺序表的插入操作 插入操作的算法实现如下，程序中需要注意的是位置变量的初始值为1而不是0： public void Insert(T item,int i) /判断顺序表是否已满 if (IsFull()) System.out.println("List is full");
24 if(last == maxsize - 1)//顺序表已满 { System.out.println("List is full"); //输出顺序表已满信息提示 return;//返回 } data[++last] = item;//在表的末端添加一个新元素，使顺序表的 last 加 1 } （6）插入操作Insert(T item, int i) 顺序表的插入是指在顺序表的第i个位置插入一个值为item的新元素，插入后使原表长为 n的表(a1,a2,.,ai-1,ai,ai+1,.,an)成为表长为n+1的表(a1,a2,.,ai-1,item,ai,ai+1,.,an)。i的取值 范围为1≤i≤n+1（n为顺序表的表长=last+1）。 i为n+1(即last+2)时，表示在顺序表的末尾插 入数据元素。 顺序表上插入一个数据元素的步骤如下： ① 判断顺序表是否已满和插入的位置是否正确，表满或插入的位置不正确不能插入； ② 如果表未满和插入的位置正确，则将 an～ai 依次向后移动，为新的数据元素空出位 置。在算法中用循环来实现； ③ 将新的数据元素插入到空出的第 i 个位置上； ④ 修改 last（相当于修改表长），使它仍指向顺序表的最后一个数据元素。 图2.4为顺序表的插入操作示意图。 图 2.4 顺序表的插入操作 插入操作的算法实现如下，程序中需要注意的是位置变量i的初始值为1而不是0： public void Insert(T item, int i) { //判断顺序表是否已满 if (IsFull()) { System.out.println("List is full");
return; /判断插入的位置是否正确 /i小于1表示在第1个位置之前插入， /11大于1ast+2表示在最后一个元素后面的第2个位置插入。 if(1<1I川i>1ast+2) System.out.println("Position is error!"); 11元素移动 for (int j=last;j>=i-1;-j) data[j+1]data[j]; /1将新的数据元素插入到第1个位置上 data[i-1]=item; 1/修改表长 ++last; 算法的时间复杂度分析：顺序表上的插入操作，时间主要消耗在数据的移动上，所以可 以把移动操作看作基本操作，在第i个位置插入一个元素，从i到an都要向后移动一个位置 共需要移动n-+1个元素，而i的取值范围为1≤i≤+1，当i等于1时，需要移动的元素个 数最多，为n个：当i为+1时，不需要移动元素。所以，插入操作的时间复杂度为0(n 假设在第i个位置做插入的概率为pi=l/(n+1),则平均移动数据元素的次数为n2。这说明： 在顺序表上做插入操作平均需要移动表中一半的数据元素。 (7)删除操作顺序表的除操作是指将表中第ⅰ个数据元素从顺序表中删除，删除后 使原表长为n的表(al,a2,.,ai-l,a,a+l,.,an)变为表长为n-l的表(al,a2,.,a-l,aitl,.,an)。i 的取值范围为1≤i≤n,i为n时，表示删除顺序表末尾的数据元素。 顺序表上删除一个数据元素的步骤如下： ①判断顺序表是否为空和删除的位置是否正确，表空或别除的位置不正确不能删除： ②如果表未空和除的位置正确，则将ai+1~an依次向前移动。在算法中用循环来实 现： ③修改last(相当于修改表长)，使它仍指向顺序表的最后一个元素。 图2.5为顺序表的删除操作示意图
25 return; } //判断插入的位置是否正确， // i 小于 1 表示在第 1 个位置之前插入， // i 大于 last+2 表示在最后一个元素后面的第 2 个位置插入。 if (i < 1 || i > last + 2) { System.out.println("Position is error!"); return; } //元素移动 for (int j = last; j >= i - 1; -j) { data[j + 1] = data[j]; } //将新的数据元素插入到第 i 个位置上 data[i - 1] = item; //修改表长 ++last; } 算法的时间复杂度分析：顺序表上的插入操作，时间主要消耗在数据的移动上，所以可 以把移动操作看作基本操作，在第 i 个位置插入一个元素，从 ai 到 an 都要向后移动一个位置， 共需要移动 n-i+1 个元素，而 i 的取值范围为 1≤i≤n+1，当 i 等于 1 时，需要移动的元素个 数最多，为 n 个；当 i 为 n+1 时，不需要移动元素。所以，插入操作的时间复杂度为 O（n） 假设在第 i 个位置做插入的概率为 pi=1/（n+1），则平均移动数据元素的次数为 n/2。这说明： 在顺序表上做插入操作平均需要移动表中一半的数据元素。 （7）删除操作 顺序表的删除操作是指将表中第 i 个数据元素从顺序表中删除，删除后 使原表长为 n 的表(a1,a2,.,ai-1,ai, ai+1,.,an)变为表长为 n-1 的表(a1,a2,.,ai-1,ai+1,.,an)。i 的取值范围为 1≤i≤n，i 为 n 时，表示删除顺序表末尾的数据元素。 顺序表上删除一个数据元素的步骤如下： ① 判断顺序表是否为空和删除的位置是否正确，表空或删除的位置不正确不能删除； ② 如果表未空和删除的位置正确，则将 ai+1～an 依次向前移动。在算法中用循环来实 现； ③ 修改 last（相当于修改表长），使它仍指向顺序表的最后一个元素。 图 2.5 为顺序表的删除操作示意图