Python;Связанный список и прохождение! - PullRequest
Новая
       46

Python;Связанный список и прохождение!

2 голосов
/ 26 августа 2010

Сейчас я начинаю программирование на python в школе, и я не знаю, как решить эту проблему.Есть мысли?

Ввод состоит из целых чисел, разделенных переносами строк.Ваша программа должна отправить их в связанный список, просмотреть связанный список и распечатать наибольшее число.

Что-то, чтобы взять первое число и выполнить действие, которое говорит: «Если следующее число больше, возьмите это, в противном случае сохраните текущее число, а затем переместитесь вниз по списку и повторите»

Затем, когда он достигает конца списка, он печатает имеющееся у него значение. 

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt 
        self.neste = None 

def spor(kubbe):
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    for linje in stdin:
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste

# Calls the solution function and prints the result
print spor(forste)

Ввод: пример 

54
37
100
123
1
54

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

123

Ответы [ 5 ]

5 голосов
/ 26 августа 2010

«Связанные списки» редко используются в Python - обычно используется только list, встроенный список Python, который на самом деле является скорее «динамическим вектором». Так что странно видеть связанный список, указанный как часть ограничений упражнения.

Но главное, код, который вы показываете: уже создает связанный список - заголовок находится в forste, а для каждого узла указатель следующего узла в .neste, полезная нагрузка на .vekt. Итак, по-видимому, это не то, о чем вы спрашиваете, независимо от текста вашего вопроса.

Простой способ перебрать свой связанный список после того, как вы полностью его построили (то есть в конце текущего кода для spor), это 

current = forste
while current is not None:
   ...process current.vekt...
   current = current.neste

В вашем случае логика для части «процесс», конечно же, такова, как в тексте вашего Q уже сказано: 

   if current.vekt > themax:
       themax = current.vekt

Единственная тонкость заключается в том, что вам нужно изначально установить themax, перед тем как этот цикл while станет "наименьшим возможным числом"; в последних версиях Python «минус бесконечность» надежно записывается и сравнивается (хотя только в виде числа с плавающей точкой, он все равно корректно сравнивается с целыми числами), поэтому 

themax = float('-inf')

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

1 голос
/ 27 августа 2010

Вот ответ, основанный на вашем собственном коде и языке.Извините, если новые переменные и имена функций плохо переводятся, так как я не говорю по-норвежски ( Google Language Tools - мой друг).

Комментарий : Как и управление воздушным движением самолета, языком по умолчанию для большинства международных форумов по программированию, например StackOverflow, является английский.Если вы используете его, вы, вероятно, получите быстрее, лучше и больше ответов - и это, вероятно, делает вопрос и связанные с ним ответы полезными для наибольшего числа других людей.Просто мои 2 ёре ...; -) 

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt
        self.neste = None

def spor():
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    while True:
        try:
            linje = raw_input()
        except EOFError:
            break
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste
    return forste

def finne_maksimal(lenketliste):
    storste = None
    if lenketliste is not None:
        storste = lenketliste.vekt
        gjeldende = lenketliste.neste
        while gjeldende is not None:
            if gjeldende.vekt > storste:
                storste = gjeldende.vekt
            gjeldende = gjeldende.neste
    return storste

lenketliste = spor()
storste = finne_maksimal(lenketliste)
if lenketliste is None:
    print "tom liste"
else:
    print "storste er", storste
0 голосов
/ 21 марта 2019

Код ниже будет работать.Класс Node представляет узел LinkedList.Класс LinkedList определяет методы для добавления узла в конец связанного списка, и find_max будет проходить через список и возвращать узел с наибольшим ключом. 

   class Node(object):
        def __init__(self, key, next_node):
            self.key = key 
            self.next_node = next_node

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

        def append(self, key):
            # Create a new Node
            new_node = Node(key, None)
            if (self.head == None):
                self.head = new_node
            else:
                tmp = self.head
                while(tmp.next_node != None):
                    tmp = tmp.next_node
                tmp.next_node = new_node

        def find_max(self):
            tmp = self.head
            max_num = 0 
            while(tmp != None):
                if (tmp.key > max_num):
                    max_num = tmp.key
                tmp = tmp.next_node
            return max_num
0 голосов
/ 26 августа 2010

Похоже, это работает с вашим входом (работает как в Python 2 и 3). Обратите внимание, как Макс работает с утиной типизацией Python!

Эта версия работает с Python3 также из файла. 

import sys
class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt 
        self.neste = None 

def spor():
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    while True:
        linje = sys.stdin.readline().rstrip()
        if not linje:
            break

        forrige_siste, siste = siste, Kubbe(int(linje))
        if forste is None:
            forste = siste
        else:
            forrige_siste.neste = siste
    return forste

def traverse(linkedlist):
    while linkedlist is not None:
        yield linkedlist.vekt
        linkedlist=linkedlist.neste

# Calls the solution function and prints the result
linkedlist=spor()

for item in traverse(linkedlist):
    print(item)

# use builtin max:
print('Maximum is %i' % max(traverse(linkedlist)))
# if not allowed:
m = linkedlist.vekt
for item in traverse(linkedlist.neste):
       if item > m:  m = item 
print(m)
0 голосов
/ 26 августа 2010

В Python есть встроенная функция reduce, которая пересекает список и «сжимает» его с помощью данной функции.То есть, если у вас есть список из пяти элементов [a,b,c,d,e] и функции f, он будет эффективно выполнять 

temp = f(a,b)
temp = f( temp, c )
...

. Вы сможете использовать это, чтобы написать очень аккуратное решение.*

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

...