對鏈接陣列進行排序-有解無憂

語境：

我有一個LinkedList包含并自動以正確順序插入節點的類。注意，這是一個鏈表資料結構（其中的節點/元件被保持表示RAM的陣列，且該指標- ，head，tail以及next和prev在RAM中表示地址（但是在這個例子中，它們是該陣列的索引，其中節點被保留）。

例如

myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0

所以現在當我呼叫我的printInOrder函式時，它會輸出1，然后2，然后停止。

注意：當我插入一個新節點時，它會被推到陣列的末尾，但是它的相鄰節點的指標會發生變化（sonext和prev），因此從head到的類似火車的路徑tail包括所有節點特定順序（默認為升序）。所以被插入的節點總是在最后，只有它的指標表示它的位置。

我的問題：

這是我的問題：（請參閱問題末尾的代碼）

想象一下，我創建了一個默認排序的鏈表（升序），我有值 2、1 和 3。所以當我遍歷串列時，我將收到 1、2、3。現在，我想重新排序鏈表。這意味著，每個節點的索引不會改變，但節點的指標會改變。畢竟，指標是創建訂單的原因。那么我將如何使用一些排序演算法，比如合并或冒泡，來對我的節點進行排序而不實際改變它們的順序，只是它們的nextandprev指標（以及全域headand tail）。

我的代碼

這是目前為止重新排序功能的代碼，該功能目前使用冒泡排序但不起作用：

class LinkedList {
  constructor(sortingFunction) {
    this.head;
    this.tail;
    this.list = [];
    this.sortingFunction = sortingFunction ? ? ((a, b) => {
      return a < b
    });
  }
  sort(sortingFunction) {
    if (!sortingFunction) {
      return false;
    }
    this.head = null;
    this.tail = null;
    const arr = this.list.map(x => x);
    for (let i = 0; i < arr.length; i  ) {
      for (let j = 0; j < arr.length; j  ) {
        if (!arr[j   1] ? .value) {
          console.log("no");
          continue;
        }
        if (sortingFunction(arr[j].value, arr[j   1].value)) {
          let tmp_next = arr[j].next;
          let tmp_prev = arr[j].previous;
          arr[j].next = arr[j   1].next;
          arr[j].previous = arr[j   1].previous;
          arr[j   1].next = tmp_next;
          arr[j   1].previous = tmp_prev;
        }
      }
    }
    this.list = arr;
  }
}

這是我的LinkedList課程的完整代碼，它將允許您重新創建我的問題 - 即節點根本不會自行排序。他們的指標改變了，但不是他們應該改變的方式，我不明白為什么。

class LinkedList {
   constructor(sortingFunction) {
      this.head;
      this.tail;
      this.list = [];
      this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
   }

   some(func) {
      let currentNode = this.list[this.head];
      let index = this.head;
      while(!func(currentNode)) {
         index = currentNode.next;
         currentNode = this.list[index];
         if(index == undefined || index == null) { return -1; }
      }
      return index;
   }
   forEachInOrder(func) {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         func(node);
         current = node.next;
      }
   }
   * iterator() {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         yield node;
         current = node.next;
      }
   }
   
   insert(value) {
      if(!this.list.length) {
         this.head = 0;
         this.tail = 0;
         this.list.push({value, next:null,previous:null});
         return 0;
      }
      let nodeToInsert = {value, next:null,previous:null};
      let indexToInsert = this.head;
      let nthnode = this.list[this.head];
      while(nthnode && this.sortingFunction(nthnode.value, value)) {
         indexToInsert = nthnode.next;
         nthnode = this.list[indexToInsert];
      }
      if(indexToInsert === null) {
         // new tail (biggest)
         nodeToInsert.previous = this.tail;
         this.list[this.tail].next = this.list.length;
         this.tail = this.list.length;
      } else if(indexToInsert === this.head) {
         // new head (smallest)
         nodeToInsert.next = this.head;
         this.list[this.head].previous = this.list.length;
         this.head = this.list.length;
      } else {
         nodeToInsert.next = indexToInsert;
         if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
            this.list[this.list[indexToInsert].previous].next = this.list.length;
         }
         nodeToInsert.previous = this.list[indexToInsert].previous;
         this.list[indexToInsert].previous = this.list.length;
      }
      this.list.push(nodeToInsert);
      return 1;
   }

   reverse() {
      let _temp;
      for(let i = 0; i < this.list.length; i  ) {
         _temp = this.list[i].next;
         this.list[i].next = this.list[i].previous;
         this.list[i].previous = _temp;
      }
      _temp = this.head;
      this.head = this.tail;
      this.tail = _temp;
   }
   sort(sortingFunction) {
      if(!sortingFunction) {return false;}
      this.head = null;
      this.tail = null;
      const arr = this.list.map(x=>x);
      for (let i = 0; i < arr.length; i  ) {
         for (let j = 0; j < arr.length; j  ) {
            if(!arr[j 1]?.value) {continue;}
            if (sortingFunction(arr[j].value, arr[j 1].value)) {
               let tmp_next = arr[j].next;
               let tmp_prev = arr[j].previous;
               arr[j].next = arr[j 1].next;
               arr[j].previous = arr[j 1].previous;
               arr[j 1].next = tmp_next;
               arr[j 1].previous = tmp_prev;
            }
         }
      }
      this.list = arr;
   }

   print() {
      console.log(this.list);
      console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
   }
   printInOrder() {
      let current = this.list[this.head];
      while(current) {
         console.log(current.value);
         current = this.list[current.next];
      }
   }
}


const list = new LinkedList();

list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);



console.log("When each node is sorted when it is inserted:")

list.print();

list.sort((a, b) => {
  return a > b;
});

console.log("Now, when re-sorted:");

list.print();

uj5u.com熱心網友回復：

這是一個快速而骯臟的解決方案，利用對鏈接陣列進行排序

this.head并this.tail設定為null但永遠不會再次設定為其適當的值。

你的代碼有一個很好的iterator()方法，我想在你的冒泡排序中重用它，但為了避免它使用next最近交換更改過的參考，我建議對該生成器進行微小的更改，這樣它就不會受到影響那：

   * iterator() {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         current = node.next; // <--- move this here!
         yield node; // ...so the consumer can safely alter node.next
      }
   }

現在你的sort方法可以變成：

   sort(sortingFunction) {
      if (!sortingFunction) return;
      
      for (let i = 0; i < this.list.length; i  ) {
         let prevNode = null;
         // Iterate in the current order, so by following the links:
         for (let currNode of this.iterator()) { // Requires the change in the generator 
            if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
               // Get the indexes of the current pair of nodes:
               let currIndex = prevNode.next;
               let prevIndex = currNode.previous;
               // Update links from outer neighbors to these two nodes
               if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
               else this.tail = prevIndex;
               if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
               else this.head = currIndex;
               // Update links from these two nodes to outer neighbors:
               currNode.previous = prevNode.previous;
               prevNode.next = currNode.next;
               // Update links between the two nodes themselves:
               prevNode.previous = currIndex;
               currNode.next = prevIndex;
            } else {
               prevNode = currNode;
            }
         }
      }
   }

這是我無法抗拒在forEachInOrderand 中使用您的生成器函式的整個腳本some：

class LinkedList {
   constructor(sortingFunction) {
      this.head;
      this.tail;
      this.list = [];
      this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
   }

   some(func) {  // I adapted this to use the iterator
      for (const node of this.iterator()) {
         if (func(node)) {
            return node.previous == null ? this.head : this.list[node.previous].next;
         }
      }
      return -1;
   }

   forEachInOrder(func) { // I adapted this to use the iterator
      for (const node of this.iterator()) func(node);
   }

   * iterator() {
      let current = this.head;
      while(current != undefined) {
         const node = this.list[current];
         current = node.next; // <--- move this here!
         yield node;
      }
   }
   
   insert(value) {
      if(!this.list.length) {
         this.head = 0;
         this.tail = 0;
         this.list.push({value, next:null,previous:null});
         return 0;
      }
      let nodeToInsert = {value, next:null,previous:null};
      let indexToInsert = this.head;
      let nthnode = this.list[this.head];
      while(nthnode && this.sortingFunction(nthnode.value, value)) {
         indexToInsert = nthnode.next;
         nthnode = this.list[indexToInsert];
      }
      if(indexToInsert === null) {
         // new tail (biggest)
         nodeToInsert.previous = this.tail;
         this.list[this.tail].next = this.list.length;
         this.tail = this.list.length;
      } else if(indexToInsert === this.head) {
         // new head (smallest)
         nodeToInsert.next = this.head;
         this.list[this.head].previous = this.list.length;
         this.head = this.list.length;
      } else {
         nodeToInsert.next = indexToInsert;
         if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
            this.list[this.list[indexToInsert].previous].next = this.list.length;
         }
         nodeToInsert.previous = this.list[indexToInsert].previous;
         this.list[indexToInsert].previous = this.list.length;
      }
      this.list.push(nodeToInsert);
      return 1;
   }

   reverse() {
      let _temp;
      for(let i = 0; i < this.list.length; i  ) {
         _temp = this.list[i].next;
         this.list[i].next = this.list[i].previous;
         this.list[i].previous = _temp;
      }
      _temp = this.head;
      this.head = this.tail;
      this.tail = _temp;
   }
   
   sort(sortingFunction) {
      if (!sortingFunction) {return false;}
      
      for (let i = 0; i < this.list.length; i  ) {
         let prevNode = null;
         // Iterate in the current order, so by following the links:
         for (let currNode of this.iterator()) { // Requires the change in the generator 
            if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
               // Get the indexes of the current pair of nodes:
               let currIndex = prevNode.next;
               let prevIndex = currNode.previous;
               // Update links from outer neighbors to these two nodes
               if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
               else this.tail = prevIndex;
               if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
               else this.head = currIndex;
               // Update links from these two nodes to outer neighbors:
               currNode.previous = prevNode.previous;
               prevNode.next = currNode.next;
               // Update links between the two nodes themselves:
               prevNode.previous = currIndex;
               currNode.next = prevIndex;
            } else {
               prevNode = currNode;
            }
         }
      }
   }

   print() { // I adapted this a bit to get more condense output and add a call to printInOrder
      console.log(JSON.stringify(this.list));
      console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
      this.printInOrder();
   }
   
   printInOrder() { // I adapted this to use your nice iterator()
      console.log(...Array.from(this.iterator(), node => node.value));
   }
}


const list = new LinkedList();

list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);

console.log("When each node is sorted when it is inserted:")

list.print();

list.sort((a, b) => {
  return a > b;
});

console.log("Now, when re-sorted:");

list.print();

還有一點要注意：您sortingFunction回傳一個布林值（指示兩個給定引數是否按正確順序排列），這與可以傳遞給本機Array#sort方法的比較器函式不同：它期望回傳一個數字，這允許通過回傳負值、0 相等和正值反轉來指示引數是否按正確順序排列。您可能希望在實施中遵循相同的“合同”。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/335759.html

標籤：javascript 数组排序链表

上一篇：使用next.js使用Sanity訪問PostArray中的陣列

下一篇：如何僅使用Scss將display:block更改為display:none？