数据结构-列表

发表于 | 分类于 |
  • 《数据结构与算法JavaScript描述》读书笔记之二
  • 列表
  • 未完

chapter-3 列表

  • 列表是一组有序的数据，每个列表中的数据项称为元素。
  • 在JavaScript中，列表中元素可以是任意数据类型。个数不限，但是使用中受到内存的限制

适合列表的数据结构

  • 数据存储的顺序不重要
  • 不必在一个很长的序列中查找元素
  • 列表中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    ### 特性
    - 空列表（不含元素）
    - 列表的length：包含的元素个数
    - 列表末尾append一个元素，也可以在给定的元素后或起始位置insert一个元素
    - remove删除元素
    - clear清空列表元素
    - toString显示列表中所有元素
    - getElement显示当前元素
    - 描述元素位置的属性：front，end前后
    - next()从当前元素移动到下一个元素
    - prev()从当前元素移动到当前元素的前一个元素
    - moveTo(n)直接移动到指定位置，移动到第N个位置
    - currPos列表当前位置
    ### 抽象数据类型定义
    #### 属性
    - listSize 元素个数
    - pos 当前位置
    #### 方法
    - length 返回元素个数
    - clear 清空列表中的所有元素
    - toString 返回列表字符串形式
    - getElement 返回当前位置元素
    - insert 在现有元素后插入新元素
    - append 列表末尾添加新元素
    - remove 删除某元素
    - front 当前位置移动到第一个元素
    - end 移动到最后一个元素
    - prev 后移一位
    - next 前移一位
    - currPos 返回列表当前位置
    - moveTo 当前位置移动到指定位置
    ### 实现
    ```javascript
    function List () {
        this.listSize = 0;
        this.pos = 0;
        // 保存列表元素
        this.dataStore = [];
    }
    // 实现一个列表
    List.prototype = {
        constructor: List,
        // 清空
        clear: function () {
            delete this.dataStore;
            //创建空数组， 设置新的空列表
            this.dataStore.length = 0;
            this.listSize = this.pos = 0;
        },
        // 辅助方法
        find: function (element) {
            // 是否可以用indexOf代替？？
            for (var i = 0; i < this.dataStore.length;i++){
                if (this.dataStore[i] === element) {
                    return i;
                }
            }
            // 错误校验
            return -1;
        },
        // 显示列表元素
        toString: function () {
            // 目的是显示当前状态
            return this.dataStore;
        },
        // 插入
        insert: function (element, after) {
            var insertPos = this.find(after);
            if (insertPos > -1) {
                this.dataStore.splice(insertPos + 1, 0, element);
                this.listSize++;
                return true;
            }
            return false;
        },
        // 给列表添加元素
        append: function (element) {
            // 新元素就位后，变量listSize加1
            this.dataStore[this.listSize++] = element;
        },
        // 从列表中删除元素
        /*  1. 先找到该元素（find）
            2. 然后删除他，(splice)
            3. 调整底层数组对象以填补删除该元素的空白*/
        remove: function (element) {
            var foundAt = this.find(element);
            if (foundAt > -1) {
                this.dataStore.splice(foundAt, 1);
                this.listSize--;
                return true;
            }
            return false;
        },
        // 移动到第一个元素
        front: function () {
            this.pos = 0;
        },
        // 移动到最后一个元素上
        end: function () {
            this.pos = this.listSize - 1;
        },
        // 向前一个
        prev: function () {
            if (this.pos > 0) {
                this.pos--;
            }
        },
        // 向后移动一个元素
        next: function () {
            if (this.pos < this.listSize - 1) {
                this.pos ++;
            }
        },
        // 元素个数
        length: function () {
            return this.listSize;
        },
        // 返回当前指向
        currPos: function () {
            return this.pos;
        },
        // 移动到某个指向
        moveTo: function (position) {
            this.pos = position;
        },
        // 返回当前指向的元素
        getElement: function () {
            return this.dataStore[this.pos];
        },
        // 判断给定值是否在列表中
        contains: function (element) {
            // indexOf??
            for (var i = 0; i < this.dataStore.length;i++) {
                if (this.dataStore[i] === element) {
                    return true;
                }
                return false;
            }
        },
        // this.pos 是否可以再次加1
        hasNext () {
            return this.pos < this.listSize - 1;
        },
        // this.pos 是否可以再次加1
        hasPrev () {
            return this.pos > 0;
        }
    };

测试结果：

1.jpeg

使用迭代器访问列表

  • front，end，prev，next，currPos实现了cList类的一个迭代器
  • 和数组索引的优点：
    • 访问时不用关心底层数据结构（貌似也是数组？？）
    • 添加元素时，索引值不对了，只要更新列表，不更新迭代器
    • 可以用不同数据类型存储方式实现，访问元素的api是统一的
      -（ ppppps：实在是不理解）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 迭代器访问
// 前向后遍历列表
for (names.front(); names.currPos() < names.length() - 1; names.next()) {
    console.log(names.getElement());
}
// 上面的叫迭代器遍历，下面的叫什么？？
names.front();
while (names.hasNext()) {
    console.log(names.getElement());
    names.next();
}
// 疑问：当列表的listSize和pos的位置不符的时候怎么处理，好奇怪？？
// 后向前遍历
for (names.end(); names.currPos() > 0; names.prev()) {
    console.log(names.getElement());
}
// 
names.end();
while (names.hasPrev()) {
    console.log(names.getElement());
    names.prev();
}