Funkcja dodajaca elementy

0

Proszę o pomoc w rozwiązaniu takiego zadania

Napisz funkcje,która dodaje element o kluczu x do posortowanej malejąco niepustej listy.Lista ma nadal byc posortowana malejąco.

typedef struct el_listy 
{
           int klucz;
           struct el_listy *nast;
} LISTA *LISTAWSK
1

tagow nie ma

jezyk nie jest sprecyzowany

vector<int> a = { 1, 45, 54, 71, 76, 12 }; 
sort(a.begin(), a.end(), greater<int>()); 

int number;
cin >> number;

vector.push_back(number);
sort(a.begin(), a.end(), greater<int>()); 

jezeli bardzo chcesz listy to skorzystaj sobie z std::list, ale wynik bedzie ten sam

(tak wiem, ze rozwiazanie nie jest wydajne, ale robi to co jest w poleceniu)

1
fasadin napisał(a):

tagow nie ma

jezyk nie jest sprecyzowany

vector<int> a = { 1, 45, 54, 71, 76, 12 }; 
sort(a.begin(), a.end(), greater<int>()); 

int number;
cin >> number;

vector.push_back(number);
sort(a.begin(), a.end(), greater<int>()); 

jezeli bardzo chcesz listy to skorzystaj sobie z std::list, ale wynik bedzie ten sam

(tak wiem, ze rozwiazanie nie jest wydajne, ale robi to co jest w poleceniu)

Przeciez implementacja o zlozonosci O(n)[tutaj podpowiedz dla OP] jest banalna :p aczkolwiek OP nie wniosl nic od siebie wiec sie nie dziwie ze troche zlosliwe rozwiazanie podales

0

Lista jest niepusta, więc nie musisz tego rozważać.

Pseudokod:

function insert (node head, int key)
{
    allocate_node(new_node, key);

    if (head.key < key) {
        new_node.next = head;
        head = new_node; // update head
        return;
    }

    node temp = head;
    while (temp.next.key > key) {
        temp = temp.next;
    }

    new_node.next = temp.next;
    temp.next = new_node; 
}

Rozwiń o pesymistyczny przypadek w którym node musi być zaalokowany na samym końcu listy (bo wszystkie inne nody są większe).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0