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

[通知] 首先感谢小伙伴们的长期的关注和支持,为了回馈小伙伴们,预定本周四(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

原文发布于微信公众号 - 好好学java(SIHAIloveJAVA)

原文发表时间:2018-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[LeetCode]Valid Parentheses 验证括号是否有效闭合 [LeetCode]Valid Parentheses 验证括号是否有效闭合

链接:https://leetcode.com/problems/valid-parentheses/#/description 难度:Easy 题目:...

703
来自专栏吾爱乐享

java之学习集合迭代listiterator的用法及注意事项

893
来自专栏MyBlog

Effective.Java 读书笔记(12)关于Comparable接口

对于Comparable接口来说,其主要方法应该是compareTo方法,可是这个方法并没有在Object里面声明,而是Comparable接口中唯一的方法,这...

552
来自专栏cs

顺序表

764
来自专栏乐百川的学习频道

设计模式(十七) 迭代器模式

迭代器模式是现在使用非常广泛的一种模式,Java、C#等很多语言都是用迭代器创建集合,然后提供for-each语法糖让我们能够方便的遍历集合。如果对Java或C...

1876
来自专栏电光石火

java判断list为空

if(null == list || list.size() ==0 ){ } list.isEmpty()和list.size()==0 没有区别...

1725
来自专栏电光石火

java判断list为空

if(null == list || list.size() ==0 ){ }

1788
来自专栏牛客网

知识总结:Java集合对象排序1.List排序2.Set排序 3.Map排序

1.List排序 这个和数组的排序又不一样了。 其实Java针对数组和List的排序都有实现,对数组而言,你可以直接使用Arrays.sort,对于List和V...

48110
来自专栏Java3y

Collection总览

1385
来自专栏Android知识点总结

Java容器源码攻坚战--第一战:Iterator

631

扫码关注云+社区