时间戳

首页 > 解决方案 > 为什么我的链表排序不正确？

python - 为什么我的链表排序不正确？

问题描述

我正在尝试将按日期排序的新约会插入到链接列表中，但是当我去测试它时，总是有一个实例没有正确排序。目前这是我的代码：

from datetime import datetime

class VaccList:
    class Appointment:
        def __init__(self, name, age, city, date):
            assert type(name) is str, 'name variable must be a string'
            assert type(age) is int, 'age variable must be a integer'
            assert type(city) is str, 'city variable must be a string'
            assert type(date) is datetime, 'date variable must be a datetime object'
            assert name != None, 'name variable cannot be empty'
            assert age >= 18 and age <= 100, 'age must be between 18 and 100'
            #   ADD 6 asserts.  4 for the types and name cannot be empty, 
            #   and age must be between 18 and 100

            self.name = name
            self.age = age
            self.city = city
            self.date = date
            self.confirmed = False
            self.next = None

        def __str__(self):
            s = "Appointment for " + self.name + " on " + str(self.date) + " age:" + str(self.age) + "  city:" + self.city
            if self.confirmed:
                s += " (confirmed)"
            else:
                s += " (unconfirmed)"
            return s

    def __init__(self):
        self.head = None
        self.tail = None
    
    def print(self):       #YOU WRITE THIS (EASY)
        '''
        Print all the appointments, one per line.  Print a blank line after the last one.
        If the list is empty, print a line saying the Appointment List is empty.
        '''
        runner = self.head
        while runner != None:
            print(runner)
            runner = runner.next
    

    def insertByDate(self, newAppt):          #### YOU WRITE (HARD)
        ''' Given a pointer to an Appointment object, put it into the list so that the list remains sorted by date.
           Obviously the linked list may be empty, which is easy.  But inserting the newAppt in sorted order
           may mean putting it at the front if the newAppt's date is less than the first.  Or at the end, or in
           the middle.
        '''
        assert type(newAppt) is VaccList.Appointment, 'insertByDate requires a pointer to an appointment object'
        newnode = newAppt

        if self.head is None:
            self.head = newAppt
        elif newAppt.date < self.head.date:
            newAppt.next = self.head
            self.head = newAppt
        else:
            current = self.head
            while current.next != None and current.date < newAppt.date:
                current = current.next
            newAppt.next = current.next
            current.next = newAppt

这是我试图运行的测试代码：

active =VaccList()

appt = VaccList.Appointment("Henry", 72, "Buffalo", datetime(2021,5,1,12,0,0))
active.insertByDate(appt)
appt = VaccList.Appointment("John", date=datetime(2021,3,10,12,0,0), age=75, city="Buffalo")
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 3, 5, 8, 0, 0), name="Mary", city="Buffalo", age=65)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 4, 28, 13, 30, 0), name="Alvin", city="New York City", age=39)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 4, 21, 14, 0, 0), name="Sheila", city="New York City", age=50)
active.insertByDate(appt)
appt = VaccList.Appointment(date = datetime(2021, 3, 12, 18, 0, 0), name="Melvin", city="New York City", age=80)
active.insertByDate(appt)

active.print()

但是，每次我运行此命令时，“亨利”下的约会都会被错误地排序。我迷路了，因为它似乎对其余的约会进行了很好的排序，除了“亨利”不合适。任何想法/解决方案都非常感谢，因为这是我的第一个 python 项目之一。

Appointment for Mary on 2021-03-05 08:00:00 age:65  city:Buffalo (unconfirmed)
Appointment for John on 2021-03-10 12:00:00 age:75  city:Buffalo (unconfirmed)
Appointment for Henry on 2021-05-01 12:00:00 age:72  city:Buffalo (unconfirmed)
Appointment for Melvin on 2021-03-12 18:00:00 age:80  city:New York City (unconfirmed)
Appointment for Sheila on 2021-04-21 14:00:00 age:50  city:New York City (unconfirmed)
Appointment for Alvin on 2021-04-28 13:30:00 age:39  city:New York City (unconfirmed)

标签： pythonsortinglinked-list

解决方案

在该else块中，您的循环正在查找一个current节点，使其日期在您要插入的节点的日期之后。但是要意识到这会给您带来一个节点太远...您将在之后 current插入新节点，因此current必须仍然是一个日期早于您要插入的节点的节点。

所以改变这个：

 while current.next != None and current.date < newAppt.date:

至：

 while current.next != None and current.next.date < newAppt.date:
 #                                     ^^^^^

推荐阅读