”365算法每日学计划”：02打卡-线性表（赠书活动第①期预告）

好好学java

发布于 2018-07-02 15:31:21

3770

发布于 2018-07-02 15:31:21

[通知] 首先感谢小伙伴们的长期的关注和支持，为了回馈小伙伴们，预定本周四（21:10）--赠书活动第①期，送出算法书籍《Java常用算法手册》，敬请期待~~~

一、线性表

一个线性表（Linear List）是由n(n≥0)个数据元素（结点，它可以是一个字母，数字，记录或更复杂的信息）所构成的有限序列。线性表逻辑地表示为：（a0,a1,…,an-1)。其中，n为线性表的长度，n=0时为空表。称i为ai在线性表中的位序号。

然后，我们对顺序存储结构用图来做一个理解。

1.1 顺序存储结构理解

顺序储存结构是用数组来保存数据的。如下图：

这里写图片描述

说明：线性表也就是数组的一种特殊储存方式：从头到尾依次储存数据。

下面这种情况就不是线性表：

这里写图片描述

1.2 插入数据

1. 线性表为空的情况

这里写图片描述

很简单，当线性表为空时，将数据放到0的位置上就可以了

2. 插入到末尾

这里写图片描述

说明：1和2是一种情况，都是将数据直接添加到线性表的末尾。

3. 一般情况

这里写图片描述

说明：简单来理解，就是腾出地方，然后插入,即：将要插入的位置的元素的位置之后的元素往后移动一个位置。

1.3 移除数据

1. 末尾的数据移除

这里写图片描述

说明：很简单，直接置空就可以了。

2.一般情况

这里写图片描述

说明：跟插入的一般操作相反，先移除，再把坑填上,即：把后面的元素往前移动一个位置。

看完上面的理解之后，我们再来看java的具体实现，这个也是ArrayList的实现方式。

二、线性表的抽象数据类型

首先，我们给出线性表的抽象数据类型。

1、线性表的置空操作：	clear()
2、线性表判空操作：	isEmpty()
3、求线性表的长度：	length( )
4、取元素操作：	get( i )
5、插入操作：	insert( i, x )
6、删除操作：	remove( i)
7、查找操作：	indexOf(x )
8、输出操作：	display()

线性表抽象数据类型的Java接口描述：

 1 public interface IList {  
 2        public void clear(); // 将一个已经存在的线性表置成空表  
 3        public boolean isEmpty(); // 判断当前线性表中的数据元素个数是否为0,若为0则函数返回true，否则返回false  
 4        public int length(); // 求线性表中的数据元素个数并由函数返回其值  
 5        public Object get(int i) throws Exception;// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常  
 6        public void insert(int i, Object x) throws Exception;// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x  
 7        public void remove(int i) throws Exception;// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常  
 8        public int indexOf(Object x);// 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1  
 9        public void display();// 输出线性表中的数据元素  
10    }

三、线性表的顺序存储

线性表它包括顺序表，链式表，这篇文章先介绍介绍顺序表。

1、概念

顺序存储指用一组地址连续的存储单元依次存放线性表中的数据元素的存储结构。用顺序存储的线性表就称为顺序表，所有数据元素的存储位置均取决于第一个数据元素的存储位置。

2、特点

逻辑上相邻的数据元素，赋以相邻的存储位置；
存储密度高；
便于随机存取；
不便于插入、删除操作。

好了，看完啦这些基本的概念之后，相信小伙伴们对于线性表的顺序存储肯定有了一定的了解，如果学过数据结构的小伙伴，那就更不用说了，下面我们自己动手写一个顺序表的接口。

3、顺序表接口的描述

 1 public class SqList implements IList {  
 2        private Object[] listElem; // 线性表存储空间  
 3        private int curLen; // 当前长度  
 4        // 顺序表的构造函数，构造一个存储空间容量为maxSize的线性表  
 5        public SqList(int maxSize) {  
 6            curLen = 0; // 置顺序表的当前长度为0  
 7            listElem = new Object[maxSize];// 为顺序表分配maxSize个存储单元  
 8        }  
 9        // 将一个已经存在的线性表置成空表  
10        public void clear() {  
11            curLen = 0; // 置顺序表的当前长度为0  
12        }  
13        // 判断当前线性表中数据元素个数是否为0,若为0则函数返回true，否则返回false  
14        public boolean isEmpty() {  
15            return curLen == 0;  
16        }  
17        // 求线性表中的数据元素个数并由函数返回其值  
18        public int length() {  
19            return curLen; // 返回顺序表的当前长度  
20        }  
21        // 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常  
22        public Object get(int i) throws Exception {  
23            if (i < 0 || i > curLen - 1) // i小于0或者大于表长减1  
24                throw new Exception("第" + i + "个元素不存在"); // 输出异常  
25            return listElem[i]; // 返回顺序表中第i个数据元素  
26        }  
27        // 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x  
28        public void insert(int i, Object x) throws Exception {  
29            if (curLen == listElem.length) // 判断顺序表是否已满  
30                throw new Exception("顺序表已满");// 输出异常  
31            if (i < 0 || i > curLen) // i小于0或者大于表长  
32                throw new Exception("插入位置不合理");// 输出异常  
33            for (int j = curLen; j > i; j--)  
34                listElem[j] = listElem[j - 1];// 插入位置及之后的元素后移  
35            listElem[i] = x; // 插入x  
36            curLen++;// 表长度增1  
37        }  
38        // 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常  
39        public void remove(int i) throws Exception {  
40            if (i < 0 || i > curLen - 1) // i小于1或者大于表长减1  
41                throw new Exception("删除位置不合理");// 输出异常  
42            for (int j = i; j < curLen - 1; j++)  
43                listElem[j] = listElem[j + 1];// 被删除元素之后的元素左移  
44            curLen--; // 表长度减1  
45        }  
46        // 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1  
47        public int indexOf(Object x) {  
48            int j = 0;// j为计数器  
49            while (j < curLen && !listElem[j].equals(x))  
50                // 从顺序表中的首结点开始查找，直到listElem[j]指向元素x或到达顺序表的表尾  
51                j++;  
52            if (j < curLen)// 判断j的位置是否位于表中  
53                return j; // 返回x元素在顺序表中的位置  
54            else  
55                return -1;// x元素不在顺序表中  
56        }  
57        // 输出线性表中的数据元素  
58        public void display() {  
59            for (int j = 0; j < curLen; j++)  
60                System.out.print(listElem[j] + " ");  
61            System.out.println();// 换行  
62        }  
63    }

上面我们基本上实现了java版的线性表，但是，有一个问题就是我们的数据只能是int，因此，在上面的基础上，我们再对数据类型进行泛型化。

  1public class SequenceList<T>{
  2    //默认长度
  3    private int DEFAULT_SIZE = 2;
  4    //定义一个数组用于保存线性表的长度
  5    private Object[] elementData;
  6    //用于保存数组长度
  7    private int capacity;
  8    //保存顺序表中当前元素的个数
  9    private int size = 0;
 10    /**
 11     * 构造一个默认长度的空线性表
 12     */
 13    public SequenceList(){
 14        capacity = DEFAULT_SIZE;
 15        elementData = new Object[capacity];
 16    }
 17    /**
 18     * 用一个初始化元素来创建线性表
 19     * @param element 初始化元素
 20     */
 21    public SequenceList(T element){
 22        this();
 23        elementData[0] = element;
 24        size++;
 25    }
 26    /**
 27     * 用一个元素和指定长度来创建线性表
 28     * @param element 元素
 29     * @param initSize 指定长度
 30     */
 31    public SequenceList(T element,int initSize){
 32        capacity = 1;
 33        if(capacity<initSize){
 34            capacity = initSize +2;
 35        }
 36        elementData = new Object[capacity];
 37        elementData[0] = element;
 38        size++;
 39    }
 40    /**
 41     * 向顺序表中插入元素
 42     * @param element   待插入的元素
 43     * @param index 待插入的位置
 44     */
 45    public void insert(T element,int index){
 46        if(index<0||index>size){
 47            throw new IndexOutOfBoundsException("数组越界异常");
 48        }
 49        ensureCapacity(size+1);
 50        //把index以后的元素都后移一位
 51        System.arraycopy(elementData, index, elementData, index+1, size-index);
 52        elementData[index] = element; 
 53        size++;
 54    }
 55    /**
 56     * 表长
 57     * @return
 58     */
 59    public int length(){
 60        return size;
 61    }
 62    /**
 63     * 向表中添加元素
 64     * @param element
 65     */
 66    public void add(T element){
 67        insert(element, size);
 68    }
 69    /**
 70     * 得到线性表存储的对象
 71     * @param index 获得的位置
 72     * @return  得到的结果
 73     */
 74    public T get(int index){
 75        if(index<0||index>size)
 76            throw new IndexOutOfBoundsException("数组越界异常");
 77        return (T)elementData[index];
 78    }
 79    /**
 80     * 判断线性表是否为空
 81     * @return
 82     */
 83    public boolean isEmpty(){
 84        return size==0;
 85    }
 86    /**
 87     * 清空线性表
 88     */
 89    public void clear(){
 90        Arrays.fill(elementData, null);
 91        size = 0;
 92    }
 93    /**
 94     * 获取指定位置的前一个元素
 95     * @param index 线性表位置，若是取线性表最后一个元素，必须index = size,
 96     * size为线性表元素个数
 97     * @return 
 98     */
 99    public T priorElem(int index){
100        if(index>0&&index<size+1)
101            return (T)elementData[index-1];
102        else {
103            throw new IndexOutOfBoundsException("数组越界异常");
104        }
105    }
106    /**
107     * 删除指定位置的元素
108     * @param index
109     */
110    public void delete(int index){
111        if(index<0||index>size-1){
112            throw new IndexOutOfBoundsException("数组越界异常");
113        }else{
114            //把数组前移一位
115            System.arraycopy(elementData, index+1, elementData, index, size-index-1);
116            size--;
117            //清空最后一个元素
118            elementData[size]=null;
119        }
120    }
121    /**
122     * 获取指定线性表位置的后一个元素
123     * @param index 线性表位置，若是取线性表第0个元素，必须index=-1
124     * @return
125     */
126    public T nextElem(int index){
127        if (index==-1) {
128            return (T)elementData[0];
129        }
130        else if (index<size-1&&index>-1) {
131            return (T)elementData[index+1];
132        }else{
133            throw new IndexOutOfBoundsException("数组越界异常");
134        }
135    }
136    /**
137     * 确保数组所需长度大于数组原有长度
138     * @param mCapacity 数组所需长度
139     */
140    private void ensureCapacity(int mCapacity){
141        if(mCapacity>capacity){
142            capacity=mCapacity+2;
143//          System.out.println("capacity:"+capacity);
144            elementData = Arrays.copyOf(elementData, capacity);
145        }
146    }
147}

这个代码是不是简洁多了，这个也是比较接近ArrayList的源码。

我相信，通过上面的介绍，然后小伙伴们把这些代码敲几遍，记住一定要敲出来，这样才能够体会。如果你这样做了，我相信这个你肯定能够掌握了，下面我们做一个线性表的应用。

四、顺序表应用举例：

编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为（a1,a2,…,an-k,an-k+1,…, an），循环向右移动k位后变成（an-k+1,…, an ,a1,a2,…,an-k）。要求时间复杂度为O（n）。

1、编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作（函数如下）。在上面SqList类中加上下面函数，

 1 public void shit(int k) {  
 2            int n=curLen,p=0,i,j,l;  
 3            Object temp;  
 4            for(i=1;i<=k;i++)  
 5              if(n%i==0&&k%i==0) //求n和k的最大公约数p  
 6                  p=i;  
 7            for(i=0;i<p;i++){  
 8               j=i;  
 9               l=(i+n-k)%n;  
10               temp=listElem[i];  
11               while(l!=i){  
12                 listElem[j]=listElem[l];  
13                 j=l;  
14                 l=(j+n-k)%n;  
15               }// 循环右移一步  
16            listElem[j]=temp;  
17            }  
18     }

2、然后我们测试一下

 1 public class Result {  
 2        public static void main(String[] args) throws Exception {  
 3            SqList L = new SqList(10);  
 4            for (int i = 0; i <= 8; i++)  
 5                L.insert(i, i);  
 6            System.out.println("右移前顺序表中的各个数据元素为：");  
 7            L.display();  
 8            L.shit(3);  
 9            System.out.println("右移3位后顺序表中的各个数据元素为：");  
10            L.display();  
11        }  
12    }

结果： 右移前顺序表中的各个数据元素为： 0 1 2 3 4 5 6 7 8 右移3位后顺序表中的各个数据元素为： 6 7 8 0 1 2 3 4 5

注意：如果上面的讲解还有什么疑问的话，欢迎小伙伴们在留言区留言和大家一起探讨学习。

参考文章

https://blog.csdn.net/qq_26411333/article/details/51809550
https://blog.csdn.net/u013293125/article/details/52926611

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-06-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

存储

本文分享自好好学java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

java

存储

登录后参与评论

0 条评论

热度