（四）顺序表上的基本操作实现
1. 插入&算法
需要：在顺序表第i个位置处插入一个新元素。
顺序表插入操作：将第i个数据元素及其之后的所有的数据元素，后移一个存储位置，再将新元素插入到i处。
注：接上述代码书写具体操作方法
插入操作算法
package data.updateORadd; public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //在线性表的第i个数据元素之前插入一个值为x的数据元素 @Override /** * @Param i 第i个位置 * @Param x 需要插入的数据 */ public void insert(int i, Object x) { //0.1 满校验：存放实际长度 和 数组长度 一样 if(curLen == listElem.length) { throw new Exception("已满"); } //0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素 if(i < 0 || i > curLen) { throw new Exception("位置非法"); } //1 将i及其之后后移 for(int j = curLen ; j > i; j --) { listElem[j] = listElem[j-1]; } //2 插入i处 listEle[i] = x; //3 记录长度 curLen ++; } }
插入时间复杂度：O(n)
2. 删除&算法
需求：将第i位置处元素删除
删除操作：将第i个数据元素ai之后的所有数据元素向前移一个存储位置
package data.updateORadd; public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //删除并返回线性表中的第i个数据 @Override public void remove(int i ) throws Exception { // 0.1 校验非法数据 if(i < 0 || i > curLen - 1 ) { throw new Exception("位置非法"); } // 1 将i之后向前移动 for(int j = i ; j < curLen - 1 ; j ++ ) { listElem[j] = listElem[j+1]; } // 2 长度减一 curLen--; } }
删除时间复杂度：O(n)
3. 查找&算法
需求：查找指定数据的索引号
算法1：循环遍历已有数据，进行判断，如果有返回第一个索引号，如果没有返回-1
package data.updateORadd; public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1 @Override public int indexOf(Object x) { //遍历线性表 for(int i = 0; i < curLen ; i ++) { //判断线性表中的数据元素是否存在指定的元素 if(listElem[i].equals(x)) { return i; } } return -1; } }
算法2：使用变量记录没有匹配到索引
package data.updateORadd; public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1 @Override public int indexOf(Object x){ int j = 0 ; //用于记录索引信息 //while循环，循环条件是：j 小于线性表的长度， // 并且第j个数不等于要查找的数据，都满足才可进行循环。 while (j < curLen && !listElem[j].equals(x)){ //进行循环对其j进行++ j ++ ; } // j 记录索引的数量 if (j < curLen) { return j ; }else { return -1 ; } } }
查询时间复杂度：O(n)
4. 顺序表的应用实例
编程实现：建立一个顺序表('a','z','d','m','z'),然后查询顺序表中第一次出现字母'z' 的数据元素，并输出其在线性表中的位置。
线性表接口：
package data.updateORadd; public interface IList { public void clear() ; //清空 public boolean isEmpty(); //判断是否为空 public int length(); // 表的长度 public Object get(int i) throws Exception; //获取元素的值 public void insert(int i , Object x) throws Exception; //在指定位置，插入指定元素 public void remove(int i ) throws Exception; //删除指定元素 public int indexOf(Object x) ; //查找指定元素第一次出现的位置 public void display() ; //输出元素的值 }
线性表接口实现类：顺序表类
package data.updateORadd; public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表 public SqList(int maxSize) { curLen = 0 ; //置顺序表的当前长度为0 listElem = new Object[maxSize]; //为顺序表分配maxSize个存储单元 } //将一个一存在的线性表置为空表 @Override public void clear() { curLen = 0 ; //置顺序表的当前长度为0 } //判断线性表的数据元素的个数是否为0 ，若为0则返回true,反之返回false @Override public boolean isEmpty() { return curLen == 0; } //求线性表中的数据元素的个数并返回值 @Override public int length() { return curLen; } //读取到线性表中的第i个数据元素并有函数返回其值。其中i的取值范围为：0 <= i <= length()-1 //若i 值不在此范围则抛出异常 @Override public Object get(int i) throws Exception { if (i < 0 || i > curLen -1 ) { //i 小于或者大于表长-1 throw new Exception("第"+i+"个元素不存在"); //抛出异常 }else { return listElem[i] ; //返回顺序表中的第i个元素 } } //在线性表的第i个数据元素之前插入一个值为x的数据元素 @Override public void insert(int i, Object x) throws Exception { //0.1 满校验：存放实际长度 和 数组长度 一样 if(curLen == listElem.length) { throw new Exception("已满"); } //0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素 if(i < 0 || i > curLen) { throw new Exception("位置非法"); } //1 将i及其之后后移 for(int j = curLen ; j > i; j --) { listElem[j] = listElem[j-1]; } //2 插入i处 listElem[i] = x; //3 记录长度 curLen ++; } //删除并返回线性表中的第i个数据 @Override public void remove(int i) throws Exception { // 0.1 校验非法数据 if(i < 0 || i > curLen - 1 ) { throw new Exception("位置非法"); } // 1 将i之后向前移动 for(int j = i ; j < curLen - 1 ; j ++ ) { listElem[j] = listElem[j+1]; } // 2 长度减一 curLen--; } //返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1 @Override public int indexOf(Object x) { for(int i = 0; i < curLen ; i ++) { if(listElem[i].equals(x)) { return i; } } return -1; } //输出线性表中的数据元素 @Override public void display() { for (int i = 0; i < curLen; i++) { //输出 System.out.println(listElem[i]+" "); } } }
案例代码实现
package data.updateORadd.test; import data.updateORadd.SqList; public class Demo01 { public static void main(String[] args) throws Exception { //构造一个含有10个存储单元的存储空间的空顺序表 SqList L = new SqList(10); //初始化顺序表中前5个数据元素 //在顺序表中指定位置插入指定元素 L.insert(0,'a'); L.insert(1,'z'); L.insert(2,'d'); L.insert(3,'m'); L.insert(4,'z'); //在顺序表中查找值元素为'z'的数据元素 int order = L.indexOf('z'); //判断顺序表中是否包含值为'z'的数据元素 if (order != -1 ){ System.out.println("顺序表中第一次出现值为z的数据元素的位置为："+order); }else { System.out.println("此顺序表中不包含值为z的数据元素"); } } }
(五) 每日一练
17. 线性表是有 n 个（ ）的有限序列。
A.数据表
B.字符
C.数据元素
D.数据项
--------------------------------------------------------------------------------------------
18. 线性表是一个（ ）。
A.有限序列，可以为空
B.有限序列，不可以为空
C.无限序列，可以为空
D.无限序列，不可以为空
--------------------------------------------------------------------------------------------
19. 以下（ ）是一个线性表。
A.由 n 个实数组成的集合
B.由 100 个字符组成的序列
C.由所有整数组成的序列
D.所有奇数组成的序列
--------------------------------------------------------------------------------------------
20. 在线性表中，除了开始元素外，每个元素（ ）。
A.只有唯一的前驱元素
B.只有唯一的后即元素字符
C.有多个前驱元素
D.有多个后继元素
--------------------------------------------------------------------------------------------
21. 顺序表的最大有优点是( )。
A.存储密度大
B.插入运算方便
C.删除运算方便
D.可以方便地用于各种逻辑的存储表示
--------------------------------------------------------------------------------------------
22. 对于顺序表，访问编号为 i 的元素的时间复杂度为（ ）。
A. O(n)
B. O(1)
C.O(nlog2n)
D.O(log2n)
顺序表具有，可高效的进行随机存取，所有题干是访问编号为i的元素，所有可以直接通过下标索引访问到，索引复杂度O(1)
--------------------------------------------------------------------------------------------
23. 对于顺序表，在编号为 i 处插入一个新元素的间复杂度为（ ）。
A. O(n)
B. O(1)
C.O(nlog2n)
D.O(log2n)
--------------------------------------------------------------------------------------------
24. 采用顺序查找法对长度为 n 的线性表进行查找（不采用表尾设监视哨的方法），最坏的
情况下要进行（ ）次元素间的比较。
A．n+2
B．n
C．n-1
D．n/2
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
