使用ts实现顺序表

孙泽辉

发布于：2021年8月19日

字数：605字

时长：3分钟

次浏览

开始学习数据结构了，本来想着用cpp实现来着，实在是太麻烦了，顺便学习一下typescript也不错！

首先定义接口，这是顺序表的数据结构：

// interface/SeqList.ts
export default interface DataType {
    num: number;
    name: string;
    age: number
}

export default interface List {
    data: Array<DataType>;
    length: number;
}

app.ts里将基本的结构搭建起来：

// app.ts
import {List, DataType} from "/interface/SeqList"

class SeqList implements List {
    private Maxsize: number = 100;

    data: Array<DataType>;
    length: number;

    constructor(data = []) {
        this.data = data;
        this.length = data.length;
    }
}

展示列表：

// 展示列表
showList() {
    console.log("data:")
    for (let i = 0; i < this.length; i++) {
        console.log("\t", this.data[i])
    }
    console.log("length:\n\t", this.length)
}

插入元素：

// 插入元素
insertSeqList(x: DataType, index: number) {
    if (index > this.length + 1 || index < 1) {
        throw new Error("下标越界了")
    }
    if (this.length === this.Maxsize) {
        throw new Error("空间不足了")
    }
    for (let i = this.length; i >= index; i--) {
        this.data[i] = this.data[i - 1];
    }
    this.data[index - 1] = x;
    this.length++;
}

首先判断一下边界，然后将最后的一个元素往后挪（因为边界判断了，这里不会越界）

别忘了length自增

删除元素

// 删除元素
DeleteSeqList(index: number) {
    if (index > this.length + 1 || index < 1) {
        throw new Error("下标越界了")
    }
    for (let i = index; i < this.length; i++) {
        this.data[i - 1] = this.data[i];
    }
    this.length--;
}

这里判断完边界之后直接将后一个覆盖到要删除的元素上就可以了，位于最后的那个元素还存在，读取的时候不要读到它，就假装是删除了。

定位元素

// 定位元素
LocateSeqList(x: DataType, key = "num"): number {
    let i = 0;
    // @ts-ignore
    while (i < this.length && this.data[i][key] != x[key]) {
        i++;
    }
    if (i < this.length) return i + 1;
    return -1;
}

就是从头一直找，找到就返回

测试

let l: SeqList = new SeqList();
l.insertSeqList({
    num: 1,
    name: "sunzehui",
    age: 12
}, 1)
l.insertSeqList({
    num: 2,
    name: "sunzehui",
    age: 13
}, 2)
l.insertSeqList({
    num: 4,
    name: "sunzehui",
    age: 13
}, 2)
l.showList()
l.DeleteSeqList(1);
l.showList()
console.log(l.LocateSeqList({
    num: 2,
    name: "sunzehui",
    age: 13
}))

/*
output:
删除前：
data:
         { num: 1, name: 'sunzehui', age: 12 }
         { num: 4, name: 'sunzehui', age: 13 }
         { num: 2, name: 'sunzehui', age: 13 }
length:
         3
         
删除后：  
data:
         { num: 4, name: 'sunzehui', age: 13 }
         { num: 2, name: 'sunzehui', age: 13 }
length:
         2
         
找到的元素位置：  
2


*/

总结

顺序表的物理空间都是连续的，所以用数组实现，low了点，具体多low下次再说。