Вставить n значений в пустой двусвязный список (псевдокод) - PullRequest
Новая
       45

Вставить n значений в пустой двусвязный список (псевдокод)

0 голосов
/ 26 сентября 2018

Может ли кто-нибудь помочь мне проверить, правильно ли работает мой псевдокод, поэтому представленная функция добавляет в список n чисел?

Мне нужна помощь с заданием на первом курсе по науке о данных.

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

"Назначение 1: Пусть список S пуст для начала. Теперь введите n (натуральные числа, например: 1, 2, 3 ...) по одному за раз. Когдапоследнее число n помещается в список, список будет отсортированным списком, содержащим числа n. Опишите, почему мы получим отсортированное число n за O (n ^ 2) времени. "

Мой ответ на задание написан ниже, и я действительно не уверен, правильно ли он. 

// Our nodes will consist of 3 cells in each object.
// key  = a number (int)
// prev = address pointer to previous node 
// next = address pointer til next node

// This function creates an empty list
function emptyList()
   L = new List{head = nil, size = 0}
   return L

// This function creates a node.
function makeNode(val)
  node = new Node{prev = NIL, key = val, next = NIL}
  return node

// This function inserts n amount of nodes to an empty list
function InsertNodes(n)

    // Create an empty list, S.
    emptyList()

    // Initiate the first node
    S.head  = makeNode(1) 

    for i = 2 to n-1

        prevNode = makeNode(i-1)
        newNode  = makeNode(i)

        while newNode.prev == NIL do

            // connect addresses of nodes
            prevNode.next = newNode.prev
            newNode.prev  = prevNode.next

Курс посвящен алгоритмам и дискретной математике

1 Ответ

0 голосов
/ 27 сентября 2018 
// Our nodes will consist of 3 cells in each object.
// key  = a number (int)
// prev = address pointer to previous node 
// next = address pointer til next node

// This function creates an empty list
function emptyList()
   L = new List{head = nil, size = 0}
   return L

// This function creates a node.
function makeNode(val)
  node = new Node{prev = NIL, key = val, next = NIL}
  return node

// This function inserts n amount of nodes to an empty list
function InsertNodes(n)

    // Create an empty list, S.
    emptyList()

    // Initiate the first node
    S.head  = makeNode(1) 

    //tail keeps the last node
    tail = head
    for i = 2 to n

        tail.next = makeNode(i)
        tail.next.prev = tail
        tail = tail.next
...