4

Python で Singly Linked リストをソートする方法を理解するのに少し苦労しています。リンクされたリストを作成してデータをプッシュする方法を理解しましたが、ソートされた形式でプッシュするにはどうすればよいですか (すべてのデータがプッシュされた後にソートするのではありません)、または単にソートする方法はありますか?

目的

ユーザー入力に基づいて、並べ替えられた単方向にリンクされた数字のリストを作成します。プログラム ロジック: 番号を要求し、その番号を並べ替えられた位置のリストに追加し、リストを出力します。数値に -1 を入力するまで繰り返します。

現在のコード

#!/usr/bin/env python

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node


class linked_list:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print(node.data)
            node = node.next


def main():
  ll = linked_list()

  num=int(input("Enter a num to push onto the list, -1 to stop: "))
  while num!=-1:
    data=num
    ll.add_node(data)
    num=int(input("Enter a num to push onto the list, -1 to stop: "))

  print("\n")
  ll.list_print()
main()

私は本当にここで立ち往生しています。助けてくれてありがとう！

4

5 に答える 5

11

これはそれを行う必要があります：

class Node:
  def __init__(self):
    self.data = None
    self.next = None

class LinkedList:
  def __init__(self):
    self.head = None

  def addNode(self, data):
    curr = self.head
    if curr is None:
      n = Node()
      n.data = data
      self.head = n
      return

    if curr.data > data:
      n = Node()
      n.data = data
      n.next = curr
      self.head = n
      return

    while curr.next is not None:
      if curr.next.data > data:
        break
      curr = curr.next
    n = Node()
    n.data = data
    n.next = curr.next
    curr.next = n
    return

  def __str__(self):
    data = []
    curr = self.head
    while curr is not None:
      data.append(curr.data)
      curr = curr.next
    return "[%s]" %(', '.join(str(i) for i in data))

  def __repr__(self):
    return self.__str__()

def main():
  ll = LinkedList()
  num = int(input("Enter a number: "))
  while num != -1:
    ll.addNode(num)
    num = int(input("Enter a number: "))
  c = ll.head
  while c is not None:
    print(c.data)
    c = c.next

与える

>>> main()
Enter a number: 5
Enter a number: 3
Enter a number: 2
Enter a number: 4
Enter a number: 1
Enter a number: -1
1
2
3
4
5
于 2013-10-07T05:52:56.010 に答える
0

4年後ですが、この方法の方が楽だと思います

 def append(self, value):
    new_node = Node(value)
    if self.head is None:
        self.head = new_node
    else:
        current = self.head
        while current is not None and current.value <= value:
            previous = current
            current = current.next
        if current is self.head:
            aux = self.head
            self.head = new_node
            new_node.next = aux
        else:
            previous.next = new_node
            new_node.next = current
    self.size += 1
于 2021-02-24T20:07:24.743 に答える
-1

これはもう少し短くて簡単だと思いました

class Node:
    def __init__(self, data, _next=None):
        self.data = data
        self.next = _next

def main():
    nodes = []
    num = int(input("Enter number: "))
    while num != -1:
        nodes.append(Node(num))
        num = int(input("Enter number: "))

    # If list is empty then just end function
    if len(nodes) == 0: 
        return

    # Let python do the sorting
    nodes = sorted(nodes, key=lambda node: node.data)

    # Link the nodes together and print them while you're at it
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
        print(nodes[i].data)
    # We need to print the last node
    print(nodes[-1].data)
于 2016-05-10T19:06:18.853 に答える