Как реализовать сортировку по этому связанному списку? - PullRequest
Новая
       13

Как реализовать сортировку по этому связанному списку?

0 голосов
/ 05 ноября 2019

Так что мне нужно, чтобы данные были отсортированы по убыванию. Таким образом, указатель на самое низкое значение будет указывать на следующее самое высокое и так далее, и так далее. Пока что он просто указывает на следующий вставленный независимо от данных.

Мне нужно, чтобы он был отсортирован по мере добавления каждого значения

Код: 

    def AppendNode(self, node):
    if self._isleagl(node):                         #just a error checking method
        if self.list_start == None:                 #checks if list is empty
            self.list_start = node      
            node._set_pointer(None) 
        else:                                       #list not empty
            item = self.list_start
            while item:
                if item == node:                    #Checks for duplicates
                    print("This is not allowed")
                elif item._get_pointer() is None:   #If it is end of the List
                    item._set_pointer(node)
                    node._set_pointer(None)
                    break
                else:                              #incrimets to the next node via pointer
                    item = item._get_pointer()

Текущийвывод: 

 Index   Data   Pointer
   0      1       1
   1      6       2
   2      3       3
   3      7      None

Требуемый вывод: 

 Index   Data   Pointer
   0      1       2
   1      6       3
   2      3       1
   3      7      None

РЕДАКТИРОВАТЬ:

Так что я сделал это, однако она все еще не работает. Я думаю, что это связано с утверждениями elif. 

                elif item.data < node.data:
                    node._set_pointer(item._get_pointer())
                    item = item._get_pointer()
                    break
                elif item.data > node.data:
                    item._set_pointer(node)
                    item._get_pointer()
                    break

Ответы [ 2 ]

1 голос
/ 05 ноября 2019

Если вы хотите сохранить список в отсортированном порядке, вам нужно будет иногда вставлять узлы посередине, а не ставить их в конце: 

# insert node after item
node.set_pointer(item.get_pointer())  # whatever followed item now follows node
item.set_pointer(node)                # node now follows item
0 голосов
/ 05 ноября 2019

Проще написать это с нуля, чем пытаться исправить фрагменты кода - надеюсь, простая демонстрация, демонстрирующая всю концепцию на практике, поможет вашему коду пойти по правильному пути. :) 

from typing import Optional

class SortedList:
    """A list of ints that keeps itself in sorted order on insert."""
    def __init__(self, data: int):
       self.data = data
       self.next: Optional['SortedList'] = None

    def insert(self, data: int) -> 'SortedList':
        """Insert a new node into this list, and return the first node of the list."""
        node = SortedList(data)
        if node.data < self.data:
            # node is now at the head of the list
            node.next = self
            return node
        # Find the list node that will precede the new node.
        prev = self
        while prev.next is not None and prev.next.data < node.data:
            prev = prev.next
        # Insert the new node after prev.
        node.next = prev.next
        prev.next = node
        # Self remains the first node of the list.
        return self

    def print(self) -> None:
        """Print the list starting at this node."""
        print(self.data)
        if self.next:
            self.next.print()

sorted_list = SortedList(9)
sorted_list = sorted_list.insert(6)
sorted_list = sorted_list.insert(1)
sorted_list = sorted_list.insert(3)
sorted_list = sorted_list.insert(7)
sorted_list.print()
# output:
#  1
#  3
#  6
#  7
#  9
...