Struktur Data JavaScript dan Senarai Terpaut Algoritma_Pengetahuan Asas

Pengenalan kepada senarai terpaut

Senarai terpaut ialah struktur data biasa dan juga senarai linear, tetapi ia tidak menyimpan data dalam susunan linear. Sebaliknya, dalam setiap nod, penunjuk ke nod seterusnya disimpan. Anda boleh faham dengan melihat gambar. (Mereka yang mempunyai latar belakang bahasa C mungkin lebih mudah memahaminya).
Penggunaan struktur senarai terpaut boleh mengatasi kekurangan tatasusunan yang memerlukan saiz data diketahui terlebih dahulu (tatasusunan dalam bahasa C memerlukan panjang yang telah ditetapkan Struktur senarai terpaut boleh menggunakan sepenuhnya ruang memori komputer dan mencapainya). pengurusan memori dinamik yang fleksibel.
Seterusnya, kami akan memperkenalkan dua senarai terpaut biasa: senarai terpaut sehala dan pelaksanaan senarai terpaut dua kali dalam JavaScript.

Senarai terpaut sehala

Bentuk paling ringkas bagi senarai terpaut ialah senarai terpaut sehala Nod dalam senarai terpaut mengandungi dua bahagian. Bahagian pertama menyimpan maklumatnya sendiri, dan bahagian kedua menyimpan penunjuk ke nod seterusnya. Nod terakhir menghala ke NULL:

Pelaksanaan senarai terpaut sehala dalam JavaScipt

Pertama, buat pembina.

/**
 * 单向链表构造函数
 */
function LinkedList() {
 /**
  * 单向链表中节点的构造函数
  * @param {Any} element 要传入链表的节点
  */
 var Node = function(element) {
  this.element = element;
  //下个节点的地址
  this.next = null;
 }

 //单向链表的长度
 var length = 0;
 //单向链表的头结点，初始化为NULL
 var head = null;
}

Tidak sukar untuk melihat bahawa pembina senarai terpaut sehala jauh lebih rumit daripada tindanan dan baris gilir.
Senarai terpaut sehala memerlukan kaedah berikut:

1. tambah(elemen): Tambahkan elemen pada penghujung senarai terpaut
2. masukkan(kedudukan,elemen): Masukkan elemen ke kedudukan tertentu dalam senarai terpaut sehala
3. indexOf(element): Cari kedudukan elemen dalam senarai terpaut sehala
4. alih keluar(elemen): Alih keluar elemen yang diberikan
5. removeAt(position): Alih keluar elemen pada kedudukan tertentu dalam senarai terpaut sehala
6. getHead(): Dapatkan ketua senarai terpaut sehala
7. isAmpty(): Semak sama ada senarai terpaut sehala kosong, kembali benar jika kosong
8. toString(): Keluarkan semua kandungan senarai terpaut sebagai rentetan
9. size(): Mengembalikan panjang senarai terpaut sehala
   

tambah kaedah:

Penerangan: Tambahkan elemen pada penghujung senarai terpaut sehala.
Pelaksanaan:

/**
 * 向单向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 当前项等于链表头部元素.
  // while循环到最后一个，从而将该节点加入链表尾部。
  current = head;
  // 当next为null时，判定为false。退出循环。
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

kaedah sisip:

Penerangan: Masukkan elemen ke kedudukan tertentu dalam senarai terpaut sehala.
Pelaksanaan:

/**
 * 向单向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @param {Any} element 要插入的元素
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

kaedah indeks:

Penerangan: Cari kedudukan elemen dalam senarai terpaut sehala.
Pelaksanaan:

/**
 * 寻找某个元素在单向链表中的位置
 * @param {Any} element 要寻找的元素
 * @return {Number}     返回值>=0则代表找到相应位置
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

kaedah alih keluar:

Penerangan: Alih keluar elemen yang diberikan.
Pelaksanaan:

/**
 * 移除给定的元素
 * @param {Any} element 要移除的元素
 * @return {Number}     返回值>=0表示移除成功
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

kaedah removeAt:

Penerangan: Alih keluar elemen pada kedudukan tertentu dalam senarai terpaut sehala.
Pelaksanaan:

/**
 * 移除单向链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}     移除成功返回被移除的元素，不成功则返回NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
   // 核心概念在于链表前后全靠指针链接，而非数组一般。
   // 所以只需要改变head的元素。
   head = current.next;
  } else {
   while (index++ < position) {
    // previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

kaedah getHead:

Penerangan: Dapatkan ketua senarai terpaut sehala.
Pelaksanaan:

/**
 * 获取单向链表的头部
 * @return {Any} 单向链表的头部
 */
this.getHead = function() {
 return head;
}

adalahAmpty, toString, kaedah saiz

Pelaksanaan:

/**
 * 判断单向链表是否为空
 * @return {Boolean} 为空则返回true，不为空则返回false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 * 将链表所有内容以字符串输出
 * @return {String} 要输出的字符串
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 * 返回单向链表长度
 * @return {Number} 单向链表的长度
 */
this.size = function() {
 return length;
};

Senarai pautan berganda

Senarai terpaut berganda sangat serupa dengan senarai terpaut sehala. Dalam senarai terpaut sehala, hanya terdapat pautan ke nod seterusnya. Tetapi dalam senarai terpaut berganda, terdapat pautan ke nod sebelumnya, iaitu dua arah.

Pelaksanaan senarai pautan berganda dalam JavaScipt

Pertama, ia masih pembina:

/**
 * 双向链表的构造函数
 */
function DoublyLinkedList() {
 /**
  * 双向链表中节点的构造函数
  * @param {Any} element 要传入链表的元素
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 //双向链表的长度
 var length = 0;
 //双向链表的头结点，初始化为NULL
 var head = null;
 //双向链表的尾结点，初始化为NULL
 var tail = null;
}

Senarai yang dipautkan berganda memerlukan kaedah berikut:

1. tambah(elemen): Tambahkan elemen pada penghujung senarai terpaut berganda
2. masukkan(kedudukan,elemen): Masukkan elemen ke dalam kedudukan tertentu dalam senarai berganda
3. removeAt(position): Alih keluar elemen pada kedudukan tertentu dalam senarai terpaut dua kali
4. showHead(): Dapatkan ketua senarai terpaut berganda
5. showLength(): Dapatkan panjang senarai terpaut berganda
6. showTail(): Dapatkan ekor senarai terpaut berganda
   

tambah kaedah:

Penerangan: Tambahkan elemen pada penghujung senarai terpaut berganda
Pelaksanaan:

/**
 * 向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 * @return {Any}     加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

kaedah sisip:

Penerangan: Masukkan elemen ke kedudukan tertentu dalam senarai berganda.
Pelaksanaan:

/**
 * 向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {

  var node = new Node(element);
  var index = 0;
  var previous;
  var current = head;

  if (position === 0) {

   if (head === null) {
    head = node;
    tail = node;
   } else {
    current.prev = node;
    node.next = current;
    head = node;
   }
  } else if (position === length) {

   current = tail;
   current.next = node;
   node.prev = current;
   tail = node;
  } else {

   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.prev = previous;
   current.prev = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

kaedah removeAt:

Penerangan: Alih keluar elemen pada kedudukan tertentu dalam senarai berganda.
Pelaksanaan:

/**
 * 移除链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}       移除成功返回被移除的元素，不成功则返回false
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var index = 0;
  var previous;

  if (position === 0) {
   head = current.next;

   if (length === 1) {
    tail = null;
    head.prev = null;
   }
  } else if (position === length - 1) {
   current = tail;
   tail = current.prev;
   tail.next = null;
  } else {
   while (index++ < position) {
    previous = current.prev;
    current = current.next;
   }
   previous.next = current.next;
   current.next.prev = previous;
  }

  length--;
  return current.element;
 } else {
  return false;
 }
};

showHead, showLength, kaedah showTail

Pelaksanaan:

/**
 * 获取链表的头部
 * @return {Any} 链表的头部
 */
this.showHead = function() {
 return head;
};

/**
 * 获取链表长度
 * @return {Number} 链表长度
 */
this.showLength = function() {
 return length;
};

/**
 * 获取链表尾部
 * @return {Any} 链表尾部
 */
this.showTail = function() {
 return tail;
};

Tera

Dalam bahagian senarai terpaut ini, pada asasnya semua kod ditulis mengikut keperluan dahulu, dan kemudian dibandingkan dengan buku selepas menulis. Didapati dia menjadi sampah sekelip mata. Terdapat banyak lubang tersembunyi dalam tulisan saya sendiri, dan logiknya juga sangat mengelirukan. Nampaknya dia masih terlalu muda.