управлять дубликатами при вставке в связанный список

Я написал алгоритм для вставки в связанный список объектов курса, отсортированных по их number переменной-члену. Это работает хорошо, за исключением случаев, когда я пытаюсь вставить дубликаты, например, два экземпляра 2420. Вывод списка __str__ настоящее время выглядит следующим образом:

cs1400 Introduction to Programming Grade:3.6 Credit Hours: 4 
cs1410 C++ Programming Grade:2.6 Credit Hours: 4 
cs2420 Introduction to Data Structures Grade:3.2 Credit Hours: 4 
cs2810 Computer Architecture Grade:3.8 Credit Hours: 3 

и вот мой код для метода вставки

def insert(self, course=None):
        """Insert the specified Course in Course Number ascending order.""" 
        def insert_helper(cursor, course):

            if course is None:
                return

            if course.number <= self.head.number: # start of the list
                self.head = course
                return

            if cursor.next is None or course.number <= cursor.next.number: # 
                course.next = cursor.next
                cursor.next = course
                return

            insert_helper(cursor.next, course)


        if self.head is None:
            self.head = course
            return
        cursor = self.head
        insert_helper(cursor, course)

Уловка оборачивает мой разум вокруг рекурсивных кадров. Я надеюсь, что скоро это получится лучше.

Всего 1 ответ


Я не верю, что дублированные номера курсов сами по себе являются проблемой.

В вашей программе есть ошибка:

            if course.number <= self.head.number: # start of the list
                self.head = course
                return

Если вы когда-нибудь выполните последние две строки в этом фрагменте кода, ваш список станет одноэлементным списком, содержащим course и ничего больше.

Сравните это со следующим оператором if , где, если условие истинно, вы выполняете

                course.next = cursor.next

Вам нужно установить course.next в обоих местах.

Также обратите внимание, что если course.number <= self.head.number не соответствует true во время первого вызова insert_helper , он также не будет истинным ни для одного из рекурсивных вызовов. Возможно, было бы лучше обработать этот случай до первого вызова этой функции.


Есть идеи?

10000