Blog - wingsico

要实现顺序表和链表,首先我们需要知道的是,何为顺序表何为链表。

顺序表

这个很简单,在JS中,数组就是顺序表的实例,它具有顺序表的一切性质:

  1. 存放在连续的内存当中,物理位置相邻,换句话说,其数据元素都是用一组地址连续的存储单元以此存储在线性表当中;
  2. 只要确定了存储线性表的起始位置,顺序表中任一数据元素都可以随机存取;
  3. 具有线性表的性质(关于线性表,这里不作介绍,可以在这里了解线性表

所以,在JS,要初始化一个空的顺序表是十分简单的:

// 方式一
var ary1 = [] // []
// 方式二
var ary2 = new Array() // []
// 神经病方式
var ary3 = [...''] // []
var ary4 = [...new Set()] // []
var ary5 = [...new Map()] // []
var ary6 = [...new String()] // []
var ary7 = ''.split('') // []
var ary8 = Array.prototype.slice.call('') // []
// 终极神经病方式
var obj = {}
var ary9 = [...obj[Symbol.iterator]] // []

既然是自己实现顺序表,自然不能使用js数组中自带的方法啦,一般来说,顺序表有以下几个基本方法:

  1. createList()
  2. initList(L)
  3. getLength(L)
  4. insertList(L, i, e)
  5. deleteList(L, i , e)
  6. getListElem(L, i)
  7. getElemIndex(L, e)

So, 接下来一个个实现吧~


 //createList
function createList():any[] {
  var array = new Array() // []
  return array
}

// initList(L)
function initList(list: any[]): number[] {
  if (list instanceof Array) {
    var length = 15 // 由于js本身不能自己输入值,所以采用自己赋值来初始化一个顺序表
    for (let i = 0; i < length; i++) { list[i] = i + 1 } return list 
  }
} 

// getLength(L) 
function getLength(list: number[]): number{ 
  let len: number = 0; 
  while(L[len] !== undefined) { // 循环遍历每一个数据元素, 一个不为空则计数器加一 
    len++ 
  }
  return len 
} 

// insertList(L, i, e) 
function insertList(list: number[], index:number, item: number): number[] {
  let i: number
  let len = getLength(list)
  for (i = len - 1; i >= index - 1; i--){
     list[i+1] = list[i] // 位置index之后的元素(包括index)全部往后移一个单元
  }
  list[index - 1] = item
  return list
}

// deleteList(L, i)
function deleteList(list: number[], index: number): number {
  if (index > getLength(list) + 1 || index < 1) {
    return -1
  }
  let i: number = index - 1
  let len: number = getLength(list)
  let e = list[i]
  for (; i < len; i++){
    list[i] = list[i + 1] // index之后的每一个元素往前移一个单元
  } 
  list.length-- // 长度减1
  return e 
} 

// getListElem 
function getListElem(list: number[], index: number):number {
  if (index > getLength(list) + 1 || index < 1) {
    return -1
  }
  return list[index - 1]
}

// getElemIndex(L, e)
function getIndex(list: number[], value: number): number {
  let i: number = 0
  for (; i < getLength(list); i++) {
    if (list[i] === value) {
      return i
    }
  }
}

最后再用一个test函数测试:

function test():void {
  let sqList = createList()
  console.log('创建空顺序表:' + sqList)
  initList(sqList)
  console.log('初始化一个数字类型顺序表:' + sqList)
  let elem = getListElem(sqList, 5)
  console.log('获取第五个元素:' + elem)
  let index = getListIndex(sqList, 6)
  console.log('获取值为6的游标:' + index)
  insertList(sqList, 4, 999)
  console.log('在第四个位置插入999:' + sqList)
  let e = deleteList(sqList, 4)
  console.log('删除第四个位置的元素:' + sqList, '被删除的元素:' + e)
  console.log('表长为:' + getLength(sqList))
  console.log('所有元素为:')
  consAll(sqList) // 输出所有元素
}
test()

一个简单的顺序表就完成了~,接下来介绍链表。

链表

先介绍以下何为链表 链表也是线性表中的一元,它也是一个连续的表,不过相比于顺序表,它不要求物理位置上相邻,但要求的是逻辑位置上相邻,因此他没有顺序表所具有的弱点——删除、插入等需要移动大量的数据元素,但是也失去了顺序表随机存储的优点。我们先来看一下链表的结构: 链表 从上图可以清晰的看出,对于一个数据元素,我们这里把它叫做结点好了,一个结点(Node)中包含两个域,一个是存储自身信心的数据域,另一个是指向下一个结点的指针域,由于js里没有指针,那么我暂且称之为链域,指向的是该结点的下一个结点。从上图我们还发现了一个head结点,我们把它称之为 头指针,他的数据域可以不存储任何数据,也可以存储像表长等信息,其链域中存储的是指向链表的第一个结点的链。可能现在会对头指针的存在产生一个疑惑,那么我举个例子就明白了,试想一下,如果没有头指针,我们如何在第一个结点前再插入一个结点呢?这个操作很简单,就是把你新创建的结点的链域指向第一个结点,但是如果你不是插入到链表的最前面呢?你要先创建一个结点,然后让想插入的那个位置的前一个结点的链域指向你新创建的结点,再让你的链域指向你想插入的位置的那个结点。发现了吗?插入第一个和插入中间其他位置的操作是不相同的,为了简化和统一像这样的操作,于是引入头指针。链表的最后一个结点之后没有结点的存在,因此让他的链指向NULL 在传统语言如c/c++中,因为有指针的存在,可以很明确的创建一个链表,而js中是没有指针的(this应该不算吧),那我们要如何去实现一个链表的结点呢?一开始想到用对象Object实现,但是对象复制有一些麻烦,于是转而选择了类function,看以下代码:

function LNode() :void{
  this.data = null;
  this.next = null;
}

用公用属性data当作结点的数据域,用公有属性next当作链域,当新建一个结点的时候只需要 new LNode()即可,比较方便,当然,也可以使用es6的class,代码如下:

class LNode {
  constructor() {
    this.data = null;
    this.next = null;
  }
}

由于typescirpt用的有一些生疏,以及class用的不太熟练,先用es5实现那些方法。 代码如下:

function LNode() :void{
  this.data = null;
  this.next = null;
}

function createLink(head: any, n: number): void{
  let i: number;
  head.data = n
  for (i = n; i > 0; i--) {
    let newNode = new LNode()
    newNode.data = Math.floor(Math.random() * 10 + 1)
    newNode.next = head.next
    head.next = newNode
  }
}

function getElem(LinkList: any, i: number): number {
  if (!LinkList.next) {
    return
  }
  let p: any = LinkList.next
  let j: number = 1
  while (p && j < i) { p = p.next ++j } if (!p || j > i) {
    return
  }
  return p.data
}

function getIndexs(LinkList: any, value: number): number[] {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList.next
  let indexs: number[] = new Array()
  let len = 0
  let i: number = 1
  while (p) {
    if (p.data === value) {
      indexs[len] = i
      len++
    }
    p = p.next
    i++
  }

  return indexs
}

function insertElem(LinkList: any, pos: number, e: number): void {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList
  let i: number = 0

  while (p && i < pos - 1) { p = p.next i++ } if (!p || i > pos - 1) {
    return
  }

  let s = new LNode()
  s.data = e
  s.next = p.next
  p.next = s
  LinkList.data++
}

function consAll(LinkList: any): void {
  let list: String = ''
  let p: any = LinkList.next
  while (p) {
    list += p.data + ', '
    p = p.next
  }
  console.log(list)
}

function deleteElem(LinkList: any, i: number): number {
  if (!LinkList.next) {
    return
  }

  let p: any = LinkList.next
  let j: number = 1
  let e: number
  let q

  while (p && j < i - 1) { p = p.next ++j } if (!p || j > i - 1) {
    return 
  }

  q = p.next
  p.next = q.next
  // 由于js的垃圾回收机制,不需要手动释放内存
  LinkList.data--
  return e
}

function getLenth(LinkList: any): number{
  if (!LinkList.next) {
    return 0
  }
  let p = LinkList.next
  let j = 0
  while (p) {
    p = p.next
    j++
  }
  return j
  // 由于我把表长存在头结点的data中,所以可以直接 return LinkList.data
}

function test(): void {
  var L = new LNode()
  createLink(L, 10)
  consAll(L)
  console.log(getIndexs(L, 5))
  console.log(getElem(L, 4))
  insertElem(L, 3, 999)
  consAll(L)
  deleteElem(L, 7)
  consAll(L)
  console.log(getLenth(L))
}

test()

结语

用js实现数据结构比C/C++更容易,为了更加靠近,我在这里使用了一部分typescript,最近还学习了kmp算法,快排,栈,图,队列,广度优先算法,狄克斯特拉算法等等,将在今后的博客一一列出。

参考资料

《数据结构》 严蔚敏 (PS: 这本书。。不好)