数据对象：D={aiai∈ElemSet,i=l,2,.,n,n≥0 /数据元素的集合，数据元素可以是整型、字符串型、结构类型 数据关系：Rl={Kai-l,ai)ai-l,ai∈D,i=2,3,.,n /ai-1和ai之间是一个有序关系，二者不能互换 基本操作： 几点说明： (1)基本操作是定义于逻辑结构上的基本操作，向外界提供一个与其通讯的接口。 还没有用具体的某种程序语言写出具体的算法，而操作的实现只有在存储结构确立之后。 针对不同的存储结构，实现的方法也不一样。 (2)定义多少种基本操作和什麽样的基本操作要跟据实际需要而定，没有硬性规 定。 (3)操作名、参数和返回值可以有所变化 1、求长度：Count0 初始条件：线性表存在： 操作结果：返回线性表中所有数据元素的个数。 2、清空操作：C1ear0 初始条件：线性表存在且有数据元素： 操作结果：从线性表中清除所有数据元素，线性表为空。 3、判断线性表是否为空：IsEmpty 初始条件：线性表存在： 操作结果：如果线性表为空返回true,否则返回false。 4、附加操作：Append(T item) 初始条件：线性表存在且未满 操作结果：将值为item的新元素添加到表的末尾。 5、插入操作：Insert(T item,inti) 初始条件：线性表存在，插入位置正确(0(1≤i≤n+1,n为插入前的表长)。 操作结果：在线性表的第1个位置上插入一个值为itm的新元素，这样使得原序号 为i,i+1,.,n的数据元素的序号变为i+1,i+2,.,n+1,插入后表长=原表长+1。 6、删除操作：Delete(inti) 初始条件：线性表存在且不为空，别除位置正确(1≤i≤n,n为别除前的表长)。 操作结果：在线性表中删除序号为1的数据元素，返回删除后的数据元素。删除后 使原序号为i+1,i+2,.,n的数据元素的序号变为i,i+1,.,n-1,删除后表长=原表长-1。 7、取表元：GetElem(inti) 初始条件：线性表存在，所取数据元素位置正确(1≤i≤n,n为线性表的表长)： 操作结果：返回线性表中第ⅰ个数据元素。 8、按值查找：Locate(T value) 初始条件：线性表存在。 操作结果：在线性表中查找值为value的数据元素，其结果返回在线性表中首次出 现的值为value的数据元素的序号，称为查找成功：否则，在线性表中未找到值为value 6】
16 数据对象：D={ai|ai∈ElemSet,i=1,2,.，n,n≥0} //数据元素的集合，数据元素可以是整型、字符串型、结构类型 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3,.,n} //ai-1 和 ai 之间是一个有序关系，二者不能互换 基本操作： 几点说明： （１）基本操作是定义于逻辑结构上的基本操作，向外界提供一个与其通讯的接口。 还没有用具体的某种程序语言写出具体的算法，而操作的实现只有在存储结构确立之后。 针对不同的存储结构，实现的方法也不一样。 （２）定义多少种基本操作和什麽样的基本操作要跟据实际需要而定，没有硬性规 定。 （３）操作名、参数和返回值可以有所变化。 1、求长度：Count() 初始条件：线性表存在； 操作结果：返回线性表中所有数据元素的个数。 2、清空操作：Clear() 初始条件：线性表存在且有数据元素； 操作结果：从线性表中清除所有数据元素，线性表为空。 3、判断线性表是否为空：IsEmpty() 初始条件：线性表存在； 操作结果：如果线性表为空返回 true，否则返回 false。 4、附加操作：Append(T item) 初始条件：线性表存在且未满； 操作结果：将值为 item 的新元素添加到表的末尾。 5、插入操作：Insert(T item, int i) 初始条件：线性表存在，插入位置正确()(1≤i≤n+1,n 为插入前的表长)。 操作结果：在线性表的第 i 个位置上插入一个值为 item 的新元素，这样使得原序号 为 i,i+1,.,n 的数据元素的序号变为 i+1,i+2,.,n+1，插入后表长=原表长+1。 6、删除操作：Delete(int i) 初始条件：线性表存在且不为空，删除位置正确(1≤i≤n,n 为删除前的表长)。 操作结果：在线性表中删除序号为 i 的数据元素，返回删除后的数据元素。删除后 使原序号为 i+1,i+2,.,n 的数据元素的序号变为 i,i+1,.,n-1，删除后表长=原表长-1。 7、取表元：GetElem(int i) 初始条件：线性表存在，所取数据元素位置正确（1≤i≤n，n 为线性表的表长）； 操作结果：返回线性表中第 i 个数据元素。 8、按值查找：Locate(T value) 初始条件：线性表存在。 操作结果：在线性表中查找值为 value 的数据元素，其结果返回在线性表中首次出 现的值为 value 的数据元素的序号，称为查找成功；否则，在线性表中未找到值为 value
的数据元素，返回一个特殊值表示查找失败。 }ADT List 还可以定义更复杂的操作：将两个或两个以上的线性表合并成一个线性表、把一个线 性表拆开成两个或两个以上的线性表、重新复制一个线性表。 2.2线性表的顺序存储和基本操作的实现 2.2.1顺序存储 线性表的顺序存储即把线性表的数据元素放在一组地址连续的存储单元中。在这种存储 方式中，以元素在计算机存储器内的物理位置来体现互为前驱和后继的逻辑关系，线性表中 相邻的元素在存储器内也相邻。 假设每个元素占用1个存储单元，线性表中第一个元素的存储地址是LOC(al)Fb,那麽 线性表中第i个元素的存储地址是LOC(a1)=b+(i-1)1,如图2-1所示： 存储地址 内存状态 数据元素在线性表中的位序 b al 1 b+1 a2 2 b+(i-1)1 ai 年 b+(m-1)1 n btnl 空闲 空闲 b+(maxlen-1) 空闲 线性表的顺序存储结构示意图 图2-】线性表的顺序存储结构示意图 因为本教材不是利用机器语言讨论线性表的顺序存储，而是利用JAVA语言讨论线性表 的顺序存储，而在JAVA语言中，存储单元的编号即地址对用户来说是透明的，不可见的。 在JAVA虚拟处理器中，一维数组占用的就是一组地址连续的存储单元，所以，在JAVA虚 拟处理器中，认为线性表的顺序存储是把线性表的数据元素放在一维数组中，数据元素在数 组中相邻就表示它们在线性表中互为前驱和后继。 在抽象数据类型的定义中讲过：定义于逻辑结构上的基本操作只是向外界提供一个接口， 存储结构确定了之后才能实现。接下来讨论在顺序存储结构下基本操作的实现。因为插入和 删除操作较为重要，相对来说也比较复杂，先重点分析一下插入和删除两种操作。 17
17 的数据元素，返回一个特殊值表示查找失败。 }ADT List 还可以定义更复杂的操作：将两个或两个以上的线性表合并成一个线性表、 把一个 线 性表拆开成两个或两个以上的线性表、重新复制一个线性表。 2.2 线性表的顺序存储和基本操作的实现 2.2.1 顺序存储 线性表的顺序存储即把线性表的数据元素放在一组地址连续的存储单元中。在这种存储 方式中，以元素在计算机存储器内的物理位置来体现互为前驱和后继的逻辑关系，线性表中 相邻的元素在存储器内也相邻。 假设每个元素占用 l 个存储单元，线性表中第一个元素的存储地址是 LOC(a1)=b，那麽 线性表中第 i 个元素的存储地址是 LOC(a1)=b+（i-1）l ，如图 2-1 所示 ： 图 2-1 线性表的顺序存储结构示意图 因为本教材不是利用机器语言讨论线性表的顺序存储，而是利用 JAVA 语言讨论线性表 的顺序存储，而在 JAVA 语言中，存储单元的编号即地址对用户来说是透明的，不可见的。 在 JAVA 虚拟处理器中，一维数组占用的就是一组地址连续的存储单元，所以，在 JAVA 虚 拟处理器中，认为线性表的顺序存储是把线性表的数据元素放在一维数组中，数据元素在数 组中相邻就表示它们在线性表中互为前驱和后继。 在抽象数据类型的定义中讲过：定义于逻辑结构上的基本操作只是向外界提供一个接口， 存储结构确定了之后才能实现。接下来讨论在顺序存储结构下基本操作的实现。因为插入和 删除操作较为重要，相对来说也比较复杂，先重点分析一下插入和删除两种操作
2.2.2顺序存储结构下基本操作分析 l、在线性表的第i个位置上插入数据元素item即Insert(T item,inti) 该操作在JVA虚拟处理器中，等价于在数组的第i个位置上插入数据元素item:首先 把第i个位置腾出来：即从最后一个元素即第n个直至第i个元素依次后移一位：然后在第i 个位置上插入数据元素c:如图2-2所示： ao 时 ao a1 ar a a2+ a2 a2 思 i→ item. a3 a3 as a4 a4 6 09 as n+1 1 n+1 a6 图22线性表顺序存储下的插入操作 插入数据元素到线性表（即数组）的第ⅰ个位置上，从第个数据元素到第ⅰ个数据元 素都需往后移动一位，共需做-+1次数据元素移动。 因为每一个位置上都有可能插入数据元素，平均移动次数是多少呢？第一个位置上需做 n次数据元素移动，第二个位置上需做-1次数据元素移动，第三个位置上需做-2次数据元 素移动，第+1个位置上需做0次数据元素移动，所以平均移动次数为： jnn+ n子月 平均移动次数=可 上述是假设插入到每个位置的概率相等的情况下，平均移动次数是2，有些情况下插 入到每个位置的概率不一定相等，这些情况下所需移动元素次数的期望值为： E= P(n+1-i) 18
18 2.2.2 顺序存储结构下基本操作分析 1、在线性表的第 i 个位置上插入数据元素 item 即 Insert(T item, int i) 该操作在 JAVA 虚拟处理器中，等价于在数组的第 i 个位置上插入数据元素 item；首先 把第 i 个位置腾出来：即从最后一个元素即第 n 个直至第 i 个元素依次后移一位；然后在第 i 个位置上插入数据元素 e；如图 2-2 所示： 图 2-2 线性表顺序存储下的插入操作 插入数据元素到线性表（即数组）的第 i 个位置上，从第 n 个数据元素到第 i 个数据元 素都需往后移动一位，共需做 n- i+1 次数据元素移动。 因为每一个位置上都有可能插入数据元素，平均移动次数是多少呢？第一个位置上需做 n 次数据元素移动，第二个位置上需做 n-1 次数据元素移动，第三个位置上需做 n-2 次数据元 素移动，.，第 n+1 个位置上需做 0 次数据元素移动，所以平均移动次数为： 2 n n 1 2 n(n 1) n 1 j n j 1 平均移动次数 上述是假设插入到每个位置的概率相等的情况下，平均移动次数是 n/2，有些情况下插 入到每个位置的概率不一定相等，这些情况下所需移动元素次数的期望值为： n 1 i 1 i E is P (n 1 i)
其中：B为插入到每个位置的概率，满足”P:1 例1：假设插入到第一个位置的概率是12，其余位置是12，请计算所需移动元素次数 的期望值。 解：根据题意，可以列出下式： E.=觉Pa+1-D= 1 -×>(n+1-i) 2n 2、删除线性表L的第i个数据元素：该操作在JAVA虚拟处理器中，等价于删除数组的 第i个数据元素：即令=第i个位置数据元素，然后从第i+1个元素直至第n个元素依次前 移一位：如图2-3所示 ao ao ao a a a1 a2 a2 1 X a3 a3 a4 a4 a4 as as as a6 a6 图2,3线性表顺序存储下的到除操作 删除线性表（即数组）的第i个数据元素，从第+1个数据元素到第n个数据元素都需 往前移动一位，共需做i次数据元素移动。 因为每一个位置上的数据元素都有可能被删除，平均移动次数是多少呢？删除第一个数 据元素需要n-1次，第二个数据元素需要n-2次，第三个位置上n-3次，依次类推，第n个位 置上0次，所以平均移动次数为： n(n-1) 平均移动次数 j=0 2 n-1 n n 2 9
19 其中： Pi 为插入到每个位置的概率，满足 例 1：假设插入到第一个位置的概率是 1/2，其余位置是 1/2n，请计算所需移动元素次数。 的期望值。 解：根据题意，可以列出下式： 2、删除线性表 L 的第 i 个数据元素；该操作在 JAVA 虚拟处理器中，等价于删除数组的 第 i 个数据元素；即令 e=第 i 个位置数据元素，然后从第 i+1 个元素直至第 n 个元素依次前 移一位；如图 2-3 所示: 图 2-3 线性表顺序存储下的删除操作 删除线性表（即数组）的第 i 个数据元素，从第 i+1 个数据元素到第 n 个数据元素都需 往前移动一位，共需做 n- i 次数据元素移动。 因为每一个位置上的数据元素都有可能被删除，平均移动次数是多少呢？删除第一个数 据元素需要 n-1 次，第二个数据元素需要 n-2 次，第三个位置上 n-3 次，依次类推，第 n 个位 置上 0 次，所以平均移动次数为： 2 n - 1 n 2 n ( n - 1 ) n j n -1 j 0 平均移动次数 n 1 i 1 n 1 i 2 i is (n 1-i) 2n 1 n 2 1 E P (n 1 i) P 1 n 1 i 1 i
上述是假设删除每个数据元素的概率相等的情况下即pi=1n,平均移动次数是(n-1)2, 有些情况下删除每个数据元素概率不一定相等，这些情况下所需移动元素次数的期望值为： E4=P,a-) 其中：为删除第个数据元素的概率，满足 P,=1 例1：假设删除第一个数据元素概率是12，其余位置是2(-)，求所需移动元素次数 的期望值。 解： EN=>P(n-i)= 2×(n-)+ 1 2(n-1) i)=3n-4 4 上面分析了顺序表中插入、删除操作的基本思路以及插入、别除操作所需移动元素次数 的期望值，下面讨论这些操作在JVA语言中如何实现。 2.2.3源码实现 1.说明问题 (1)定义线性表接口IListDS<T>;也可不定义接口，直接定义类。 interface IListDS<T> int Count();/求长度 void clear();/清空操作 boolean IsEmpty();/判断线性表是否为空 void Append(T item);/附加操作 void Insert(T item,inti);/插入操作 T Delete(inti);/删除操作 T GetElem(inti);/取表元 int Locate(T value);/按值查找 1 (2)顺序表类SeqList<-T>,实现接口IListDS<>。 顺序表类SeqList<-个>的实现说明如下所示。 public class SeqList<T>implements IListDS<T>
20 上述是假设删除每个数据元素的概率相等的情况下即 pi=1/n，平均移动次数是（n-1）/2， 有些情况下删除每个数据元素概率不一定相等，这些情况下所需移动元素次数的期望值为： n i 1 i E id P (n i) 其中： Pi 为删除第 i 个数据元素的概率，满足 例 1：假设删除第一个数据元素概率是 1/2，其余位置是 2 ( n 1) 1 ，求所需移动元素次数 的期望值。 解 ： 4 3 4 (n - i) 2(n - 1) 1 ( n - 1) 2 1 E P (n i) n i 1 n i 2 i id n 上面分析了顺序表中插入、删除操作的基本思路以及插入、删除操作所需移动元素次数 的期望值，下面讨论这些操作在 JAVA 语言中如何实现。 2.2.3 源码实现 1．说明问题： （1）定义线性表接口 IListDS<T>;也可不定义接口，直接定义类。 interface IListDS<T> { int Count(); //求长度 void Clear(); //清空操作 boolean IsEmpty();//判断线性表是否为空 void Append(T item);//附加操作 void Insert(T item, int i);//插入操作 T Delete(int i); //删除操作 T GetElem(int i); //取表元 int Locate(T value);//按值查找 } （2）顺序表类 SeqList<T>，实现接口 IListDS<T>。 顺序表类SeqList<T>的实现说明如下所示。 public class SeqList<T> implements IListDS<T> { P 1 n i 1 i