数据结构与算法--线性表的顺序存储结构

数据结构与算法--线性表的顺序存储结构

线性表是一个序列,可以想象成一群有先后顺序的的元素集合。线性表是有限序列,所以存在一个开头和结尾。开头的元素有且只有一个后继,结尾的元素有且只有一个前驱。中间的元素分别有一个前驱和后继。每个元素都清楚它们的前驱和后继是哪个元素,因此形成了顺序。稍微复杂的线性表,每个元素元素可以由多个数据项组成。比如链表的Node,Node是一个数据元素,每个Node都含有data(存放的数据)和next(指向下一元素的指针)组成,双向链表还有prev(指向上一个元素的指针)。

线性表中存储的元素类型一般相同。比如ArrayList<String>里就只能存String,而且通常我们处理的序列它们元素类型相同的情况居多。为此需要引用泛型,比如用Item表示某一不确定的类型,但是在之后的处理中,只接受Item或者Item的子类(多态)。这样就保证了我们存入的元素是同一类型的。

线性表的顺序存储结构

这里说的顺序,指的是内存空间上的顺序,即划分出一块连续的空间,就好比售票口开设了一个窗口。人们排成一列;而且要求数据元素类型一致(放一本书在那儿替你排队,自己跑去潇洒,谁都不会同意)。这样的数据存储方式我们很容易就想到一维数组。Java中数组的初始化必须指定长度。指定多大的长度呢?由于数据量未知,指定容量过大就浪费空间,容量小了又装不了多少元素。在刚开始初始化时就难住我们了。有一种做法是,如果能估计数据量,那么指定一个最大容量比估计的数据量适当大些,留点余地。最大容量在初始化时指定,如String[] = new String[500],指定了最多装500个元素。用编程语言表达即是capacity = 500;至于究竟装了多少个,用size表示实际存入的元素个数。显然size <= capacity。还有一种做法比较懒,不用操心数组装不下的问题:等到不够了,我立马增大容量;等到空闲的空间太多了,我立马释放一些。由于常常我们面对的数据量未知,这不失为一种好方法。

顺序存储结构,关键是划分一块连续的地址空间,连续意味着什么?假如一个序列从a0到an,每个元素占据c个存储单元。如果我知道了任何一个元素的地址,比如a3处,其在内存中的位置是locate(a3)。那么a8在内存中的位置可以立刻算出为locate(a8) = locate(a3) + (8-3)c,更一般地locate(ai) = locate(a0) + ic。这说明我只需定位第一个元素,后面的元素的位置实际上已经固定下来了。因为这样的结构,我们访问a[0]和a[5]或者a[n]是一样复杂的(或者应该叫简单)。访问a[i] (0 <= i <= size -1)的时间复杂度都是O(1)。

顺序存储结构的特点

想象一个例子,和你住一条街的邻居。以自家为a[0],你可以轻松说出西边第3家a[3]是谁家,你也能直接定位到西边第9家a[9]是谁家——记忆方式是第i家姓a[i]。如果是这样记忆的,那么随便给一个数字,你就能脱口而出那个位置是谁家。访问a[i]时间复杂度为O(1)。

如果新搬来一家,最终落户到你家旁边,成为你家最新的邻居(隔开了你和你原来的邻居),别人在问你第5家是谁家时,你心里想新来了一家,原来的第五家已经成为了第六家。实际上从第一家开始,你之前所有的记忆都不适用了,后面的所有位置都变化了,你需要重新记忆一次,如果时不时搬来一家,脑袋可不爆炸了!有人搬家走了也类似。插入或者移除在最坏情况下所有元素都要移动一次,所以时间复杂度为O(n)。

线性表--顺序存储结构的实现

为了接收多种类型,就像ArrayList那样。使用了泛型,在下面的代码中用Item表示。同时实现了Iterable<Item>使得该类是可迭代的,能使用for-each语句。实现Iterable接口,必须实现它的iterator()方法,该方法返回一个Iterator对象,我使用了匿名内部类的方式,且实现Iterator接口的hasNextnext方法。

由于使用到了一维数组,而且类型为泛型Item,我们知道Java中不能直接创捷泛型数组。下面的写法是错误的

Item[] a = new Item[capacity];

必须先创建Object数组,再向下转型为Item类型。

Item[] a = (Item[]) new Object[capacity];

另外,该数组是可调节容量的,表长度即将超过容量时,自动增大;表长度容量远小于容量时,容量减小。

好,先上全部代码,然后慢慢解释。

package Chap3;

import java.util.Iterator;

// 实现Iterable为了使用for-each语句,同时要实现iterator方法
public class LinearList<Item> implements Iterable<Item> {
    private int N;
    // 初始化为长度为1,方便第一次add的时候可以访问a[0]这个下标
    private Item[] a = (Item[]) new Object[1];

    public LinearList(Item... items) {
        for (int i = 0; i < items.length; i++) {
            add(items[i]);
        }
    }


    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public Item get(int index) {
        checkRange(index);
        return a[index];
    }

    public void set(int index, Item item) {
        checkRange(index);
        a[index] = item;
    }

    // 先判断是不是没有容量了,若不先增容,会越界。移位从最后一个元素开始,仔细想想为什么
    public void insert(int index, Item item) {
        checkRangeForInsert(index);
        if (N == a.length) {
            resize(2 * a.length);
        }
        for (int k = N - 1; k >= index; k--) {
            a[k + 1] = a[k];
        }
        a[index] = item;
        N++;
    }

    // 移除之后再检查是否长度太小需要节约空间,否则先缩小的话,可能导致访问时越界
    public Item remove(int index) {
        checkRange(index);

        Item item = a[index];
        // 这里就需要正向遍历了
        for (int k = index; k < N - 1; k++) {
            a[k] = a[k + 1];
        }
        a[N - 1] = null;
        N--;
        if (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    // 先判断是不是没有容量了,若不先增容,会越界
    public void add(Item item) {
        if (N == a.length) {
            resize(2 * a.length);
        }
        a[N++] = item;
    }


    public int indexOf(Item item) {
        if (item != null) {
            for (int i = 0; i < N; i++) {
                if (item.equals(a[i])) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < N; i++) {
                if (a[i] == null) {
                    return i;
                }
            }
        }

        return -1;
    }

    public boolean contains(Item item) {
        return indexOf(item) >= 0;
    }

    // N=0但是a.length不为0,可以再次add
    public void clear() {
        for (int i = 0; i < N; i++) {
            a[i] = null;
        }
        N = 0;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];

        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        // 将容量大于N的数组传给a
        a = temp;
    }


    // 检查数组下标是否越界,注意是N而不是a.length, 因为a的容量比N大,访问N之后的也不会触发异常
    // insert的时候允许向a[N]处插入,这里==N不会抛出异常
    private void checkRangeForInsert(int index) {
        if (index > N || index < 0) {
            throw new IndexOutOfBoundsException(index + "");
        }
    }

    // 其他情况如remove就不能访问a[N]了
    private void checkRange(int index) {
        if (index >= N || index < 0) {
            throw new IndexOutOfBoundsException(index + "");
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private int i = 0;

            @Override
            public boolean hasNext() {
                return i < N;
            }

            @Override
            public Item next() {
                return a[i++];
            }
        };
    }

    @Override
    public String toString() {
        Iterator<Item> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");

        while (true){
            Item item = it.next();
            sb.append(item);
            if (! it.hasNext()) {
                return sb.append("]").toString();
            }
            sb.append(", ");
        }
    }

    public static void main(String[] args) {
        LinearList<String> b = new LinearList<>();
        b.add("god");
        b.add("yes");
        b.add("no");
        b.add("man");
        b.insert(0, "ffff");
        System.out.println(b.remove(0)); // ffff
        b.set(1, "ggg");
        System.out.println(b.get(1)); // ggg
        System.out.println(b.indexOf("no")); // 2
        System.out.println(b.size()); // 4
        /* now b have:
        god
        ggg
        no
        man
         */
        System.out.println("*******");
        LinearList<Integer> c = new LinearList<>(1, 2, 3, 4, 5);
        System.out.println(c);
        System.out.println(c.contains(5)); // true
        c.clear();
        c.add(66);

    }
}

数组容量的调节由resize(int max)方法处理。该方法的原理就是创建一个长度为max的临时数组,将原数组的所有数据复制到临时数组,然后将临时数组的引用传给原数组。每次要新增元素时,先检查数组容量和表长度是否相等,相等说明已经没有空间存放新来的元素,故增大容量到原来的两倍;类似的,每移除一个元素后,再判断表长度是否只有容量的1/4了,若是就缩小容量到原来的一半。

private Item[] a = (Item[]) new Object[1]之所以指定容量为1,第一是因为容量可自动调节,无需指定得很大,当然不能指定为0。因为第一次添加元素时,看add方法一开始N == a.length就会执行resize(2 * a.length);如果初始化时容量设置为0,resize后还是0。

checkRange方法用来判断数组脚标是否越界,访问的index在[0, N - 1]的范围内不会抛出异常。insert方法中也检查了数组脚标。不过使用的是checkRangeForInsert(index)checkRange不同的是,当index为N时也不会抛出异常,因为我们允许在a[N]的位置插入元素,add方法其实就是insert(N, item)的简写。

接下来看关键方法insert和remove。

插入时,从最后一个元素开始,向后移动一次,接下来倒数第二个元素向后移动一次,直到插入点index处向后移动一次,结束移动。移动的总次数为N - index。现在插入点空着,在插入点安排新元素就OK了。注意必须是从最后一个元素开始移动,如果从插入点开始移动,就会占用别的元素的位置,导致混乱。记住一个原则:始终朝着空闲的地方移动!

移除元素时,也是类似的。先弹出要移除的元素,现在这个位置空闲了,从该位置的下一个位置开始向前移动一次,直到最后一个元素向前移动一次,结束移动。移动的总次数为N - index - 1

clear()可以清空表的所有元素,其实就是将[0, N-1]范围内的所有元素置为null,再将长度置为0。indexOf(Item item),可以查找item第一次出现的位置,也接受null(因为add的时候可以添加null)。原理很简单,遍历查找,找到了就返回当前脚标。contains(Item item)用到了indexOf,显然返回的脚标不为-1,说明存在这个元素。

还重写了toString方法,可以直接将对象以列表形式打印出来。


by @sunhaiyu

2017.7.30

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 194,319评论 5 459
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 81,801评论 2 371
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 141,567评论 0 319
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,156评论 1 263
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,019评论 4 355
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,090评论 1 272
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,500评论 3 381
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,192评论 0 253
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,474评论 1 290
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,566评论 2 309
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,338评论 1 326
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,212评论 3 312
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,572评论 3 298
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,890评论 0 17
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,169评论 1 250
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,478评论 2 341
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 40,661评论 2 335

推荐阅读更多精彩内容