• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sortowanie listy dwukierunkowej przez scalanie - rozdzielanie listy

VPS Starter Arubacloud
0 głosów
725 wizyt
pytanie zadane 6 grudnia 2019 w Algorytmy przez Mariusz M Obywatel (1,670 p.)
Zaproponuj algorytm rozdzielania listy dwukierunkowej

ze szczególnym uwzględnieniem przypadków brzegowych

 

Myślę z pozostałymi funkcjami potrzebnymi do realizacji sortowania przez scalanie bym sobie

poradził choć chciałbym poznać wasz pomysł na konkatenacje bo

występuje ona podczas scalania

 

Scalanie dwóch posortowanych list

Scalanie(L,A,B)

      L=NIL

     dopóki lista A jest niepusta oraz lista B jest niepusta wykonuj

            Jeżeli klucz pobrany z głowy listy A jest mniejszy bądź równy kluczowi pobranemu z głowy listy B to

                              Usuń węzeł z głowy listy A i zapamiętaj go w lokalnej zmiennej

              w przeciwnym przypadku

                              Usuń węzeł z głowy listy B i zapamiętaj go w lokalnej zmiennej

              Wstaw zapamiętany węzeł na koniec listy L

     /* Teraz co najmniej jedna lista powinna być pusta ale nie wiemy która więc

         łączymy obie listy A oraz B z listą L  przy czym łączenie to redukuje się do tzw konkatenacji */

     Połącz listę L z listą A

     Połącz  listę L z listą B

 

Sortowanie(L)

      Jeżeli głowa listy L nie pokazuje na NIL oraz następnik głowy listy L nie pokazuje na NIL to

                 Rozdziel listę L na połowę

                 Posortuj rekurencyjnie obydwie połowy

                 Scal posortowane połowy

2 odpowiedzi

0 głosów
odpowiedź 7 grudnia 2019 przez niezalogowany

taki prototypik dla jedno kierunkowej // ale bez kompilacji

list * new_list (list * N_element){
        list * temp = new list;
        temp=N_element->next;
        N_element->next=nullptr;
        return temp;
}

 

komentarz 7 grudnia 2019 przez mmarszik Mądrala (7,390 p.)
Ja bym tak spróbował: Rozdzielamy listy na dwie połówki. Wywołujemy rekurencyjnei dla każdej połówki. Jak połówka jest krótka, to sortujemy inaczej, np. gdy ma dwa elementy, to robimy swap. Pewności nie mam, ale powinno zadziałać. Można też zwalić do wektora, posortować wektor i odbudować listę.

Można upewnić się, czy std::sort (nie)działa dla listy dowiązywanej.
komentarz 7 grudnia 2019 przez niezalogowany

może bzdura, ale 24h powisi taki prototypik

Scalanie dwóch posortowanych list

http://wklejto.pl/790509

komentarz 7 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)

@fisker,

 


struct Node 
{
      struct Node *prev;
      int key;
      struct Node *next;
};

struct List
{
        struct Node *head;
        struct Node *tail;
};



void Split(struct Node *x,struct List L,struct List *L1,struct List *L2)
{
      // x to węzeł za którym należy rozdzielić listę 
      // L lista którą należy rozdzielić 
      // L1, L2 listy powstałe po rozdzieleniu listy L

     /* Jak należałoby taką listę rozdzielić 
       z uwzględnieniem przypadków brzegowych 
    Mile widziana gotowa funkcja lub przynajmniej 
    pseudokod w postaci listy kroków */
}

Wątpię czy twój prototypik będzie działał , nie uwzględniasz przypadków brzegowych

komentarz 7 grudnia 2019 przez niezalogowany
Porzuć listę dwukierunkową z metodami samosprawdzającymi add  .... Głową ogonem to się pobawię. Cała dwukierunkowa to trochę klepania. Jedno  kierunkową mam, ale to taka trochę niestandardowa to i tak nie pomoże.

Sam się uczę na przykładach tutaj podanych wiec to co pisze może być mało profesjonalne.

Ale jak na tygodniu znajdę czas to na pewno zrobię sobie to zadanie ale nie wiem czy to nie będzie za późno.
komentarz 7 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)
Zdaje się że przetłumaczyłem listę dwukierunkową z przykładu znalezionego

w książce Roberta Lafore Struktury danych i algorytmy w Javie

Od siebie dopisałem szablony a gettery i settery wzorowane są na tych

automatycznie  generowanych przez IDE

Przetłumaczonej klasy użyłem do wyznaczenia otoczki wypukłej za pomocą

algorytmu Jarvisa którego opis znalazłem gdzieś na rosyjskiej stronie internetowej
komentarz 7 grudnia 2019 przez mmarszik Mądrala (7,390 p.)
Gratuluję!
komentarz 8 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)
edycja 8 grudnia 2019 przez Mariusz M

@fisker,
 skoro się uczysz to pobaw się tą listą

Dopisz np wstawianie węzła przed podanym elementem,

usuwanie powtórzeń z posortowanej listy

Do wstawiania węzła przed podanym elementem

można wykorzystać już istniejące funkcje jak

insertFirst,

insertLast,

insertAfter

tylko trzeba odpowiednio rozbić tę funkcję na przypadki

 

Lafore ma też wstawianie do jednokierunkowej listy uporządkowanej

Można tę funkcję zmodyfikować aby działała też dla listy dwukierunkowej

jednak kod nie będzie optymalny

 


template<class T>
void DoublyLinkedList<T>::insert(T key,int (*Compare)(T,T))
{
          Link<T>  *newLink = new Link<T> (dd);
          Link<T> *previous = NULL;
          Link<T>  *current  =  getFirst();
          while(current != NULL && Compare(key , current->getData()) > 0)
          {
                 previous = current;
                 current = current->getNext();
          }
         if(previous == NULL)
               setFirst(newLink);
         else
              previous->setNext(newLink);
         newLink->setNext(current);
         // Jak dokończyłbyś wstawianie do uporządkowanej listy dwukierunkowej ?
}

Tutaj funkcja wstawiająca wymaga dokończenia jeśli chcemy aby działała także dla listy dwukierunkowej

Tutaj funkcja po dokończeniu nie będzie optymalna ponieważ lista jest iterowana dwoma wskaźnikami

i nie wykorzystujemy tego że każdy węzeł listy dwukierunkowej zawiera zarówno wskaźnik na następnika jak i wskaźnik na poprzednika

komentarz 8 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)

@fisker, co do twojej propozycji scalania 

to może jednak zanim przystąpimy do scalania zajmiemy się

rozdzielaniem i konkatenacją ?

komentarz 8 grudnia 2019 przez niezalogowany

Wczoraj późno było(kiedyś trzeba spać) dzisiaj zapowiada się że też z czasem krucho.

Proszę rozdzielenie dla poprzedniej

void Split(struct Node *x,struct List L,struct List *L1/*wyzerowane*/)
{
     Node* temp=L.head; // ustawiamy wskaźnik równy glowie// temp by głowy nie przesuwać;
    Node* temp2=nullptr;
    
     
    //element na samym poczatku
    if(x->key==L.head->key){
    
        L1->head=L.head;//"przkopiowanie" bez ruszania z miejsca
        L1->tail=L.tail;//"przkopiowanie" bez ruszania z miejsca
        
        //zerwanie wiązaniań listy L
        Node * tempH=new Node();// wyzerowane elementy ale z adresem
        Node * tempL=new Node();// wyzerowane elementy ale z adresem
        L.head=tempH;//by nie pozmieniać L1
        L.tail=tempL;//by nie pozmieniać L1
        L.head=nullptr;//teraz wskazuje na nic
        L.tail=nullptr;//teraz wskazuje na nic
        delete tempH;
        delete tempL;
    }
    // powtarzaj dopóki wartość x bedze różna niż temp
    // i temp jest różne od nullptr założenie tail->next=nullptr
     while (x->key!=temp->key and temp){temp=temp->next;}
     
     if(temp/*temp!=nullptr*/){
         Node* temp2=temp->next;//ustawienie wskaznika na następny element po temp
         temp2->prev=nullptr; // zerwanie wiązania wstecznego;
         temp->next=nullptr; //oderwanie wszystkiego co za temp-key=x->key;
     } else {std::cout<<"Nie znaleziono elemetu\n L1 jest puste\n"<<endl;
         return;
     }
    
        if (temp2)// jesli istnieje /*temp!=nullptr*/
        { L1->push(temp2);// skoro L1 jest pusta to powinno dodać się do głowy push musisz za implemetowac
           // ale to zalezy od implemetaci pusz();
            // da się zrobić i na nie pustej od biedy

        } else {std::cout<<"Lista L1 jest pusta"<<endl;}
     
    
    // x to węzeł za którym należy rozdzielić listę 
      // L lista którą należy rozdzielić 
      // L1, L2 listy powstałe po rozdzieleniu listy L / L2 to niebardzo kumam o co chodzi przy rozdielaniu
 
     /* Jak należałoby taką listę rozdzielić 
       z uwzględnieniem przypadków brzegowych 
    Mile widziana gotowa funkcja lub przynajmniej 
    pseudokod w postaci listy kroków */
}

konkatenacja - dodajesz do next tail pierwszej  head drugiej przez tempa i ok zerujesz listy

0 głosów
odpowiedź 7 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)

Fisker masz przykładową listę dwukierunkową

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

struct Point
{
      int x,y;
      friend std::ostream &operator << (std::ostream &output,const Point &p);
      friend std::istream &operator >> (std::istream &input,Point &p);
};

bool operator == (Point a,Point b)
{
     return (a.x == b.x && a.y == b.y); 
}

std::ostream &operator << (std::ostream &output,const Point &p)
{
        output<<"( "<<p.x<<" , "<<p.y<<" ) ";
        return output;
}



std::istream &operator >> (std::istream &input,Point &p)
{
        input>>p.x>>p.y;; 
        return input;
}


template<class T>
class Link
{
      private:
              T data;
              Link<T> *next;
              Link<T> *previous;
      public:
             Link(T data);
             void displayLink();
             T getData();
             void setData(T data);
             Link<T> *getNext();
             void setNext(Link<T> *next);
             Link<T> *getPrevious();
             void setPrevious(Link<T> *previous);
             template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);

};

template<class T>
Link<T>::Link(T data)
{
     setData(data);
     setNext(NULL);
     setPrevious(NULL);
                
}

template<class T>
void Link<T>::displayLink()
{
     std::cout<<getData()<<" ";
}

template<class T>
T Link<T>::getData()
{
     return data;               
}

template<class T>
void Link<T>::setData(T data)
{
     this->data = data;               
}

template<class T>
Link<T> *Link<T>::getNext()
{
      return next;  
}

template<class T>
void Link<T>::setNext(Link<T> *next)
{
      this->next = next; 
}

template<class T>
Link<T> *Link<T>::getPrevious()
{
      return previous;  
}

template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
      this->previous = previous; 
}


template <class U>  
std::ostream& operator<<(std::ostream& print, Link<U> & L)
{
        print << L.getData();
        return print;
}

template<class T>
class DoublyLinkedList
{
      private:
              Link<T> *first;
              Link<T> *last;
      public:
             DoublyLinkedList();
             ~DoublyLinkedList();
             Link<T> *getFirst();
             void setFirst(Link<T> *first);
             Link<T> *getLast();
             void setLast(Link<T> *first);
             bool isEmpty();
             Link<T> *find(T key);
             void insertFirst(T dd);
             void insertLast(T dd);
             void deleteFirst();
             void deleteLast();
             bool insertAfter(T key,T dd);
             void deleteKey(T key);
             void displayForward();
             void displayBackward();
};

template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
    setFirst(NULL);
    setLast(NULL);                                   
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
    while(!isEmpty())
    {
        deleteFirst();             
    }                                   
}

template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
       return first; 
}

template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
     this->first = first;
}

template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
       return last; 
}

template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
     this->last = last;
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
     return getFirst()==NULL;
}

template<class T>
 Link<T> *DoublyLinkedList<T>::find(T key)
 {
         Link<T> *current = getFirst();
         while(current != NULL && !(current->getData == key))
               current = current->getNext();
         return current;        
 }
 
 template<class T>
 void DoublyLinkedList<T>::insertFirst(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
           setLast(newLink);
      else
          getFirst()->setPrevious(newLink);
      newLink->setNext(getFirst());
      setFirst(newLink);        
 }
 
 template<class T>
 void DoublyLinkedList<T>::insertLast(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
      {
          setFirst(newLink);         
      }
      else
      {
          getLast()->setNext(newLink);
          newLink->setPrevious(getLast());
      }
      setLast(newLink);
 }
 
 template<class T>
 void DoublyLinkedList<T>::deleteFirst()
 {
      if(isEmpty())
           return;
      Link<T> *temp = getFirst();
      if(getFirst()->getNext() == NULL)
            setLast(NULL);
      else
         getFirst()->getNext()->setPrevious(NULL);
      setFirst(getFirst()->getNext());
      delete temp;                            
 }
 
 template<class T> 
 void DoublyLinkedList<T>::deleteLast()
 {
      if(isEmpty())
         return;
      Link<T> *temp = getLast();
      if(getFirst()->getNext() == NULL)
             setFirst(NULL);
      else
          getLast()->getPrevious()->setNext(NULL);
      setLast(getLast()->getPrevious());
      delete temp;                  
 }
 
 template<class T>
 bool DoublyLinkedList<T>::insertAfter(T key,T dd)
 {
      Link<T> *current = find(key);
      if(current == NULL)
             return false;
      Link<T> *newLink = new Link<T>(dd); 
      if(current->getNext() == NULL)
      {
           newLink->setNext(NULL);
           setLast(newLink);                 
      }
      else
      {
          newLink->setNext(current->getNext());
          current->getNext()->setPrevious(newLink);
      }
      newLink->setPrevious(current);
      current->setNext(newLink);
      return true;    
 }
 
 template<class T>
 void DoublyLinkedList<T>::deleteKey(T key)
 {
      Link<T> *current = find(key);
      if(current==NULL)
           return;
      if(current->getPrevious() == NULL)
             setFirst(current->getNext());
      else
             current->getPrevious()->setNext(current->getNext());
      if(current->getNext() == NULL)
             setLast(current->getPrevious());
      else
             current->getNext()->setPrevious(current->getPrevious());
      delete current;
 }
 
 template<class T>
 void DoublyLinkedList<T>::displayForward()
 {
      std::cout<<"List (first-->last): ";
      Link<T> *current = getFirst();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getNext();   
      }
      std::cout<<"\n";
 }
 
 template<class T>
 void DoublyLinkedList<T>::displayBackward()
 {
      std::cout<<"List (last-->first): ";
      Link<T> *current = getLast();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getPrevious();   
      }
      std::cout<<"\n";
 }



int vect(Point a1,Point a2,Point b1,Point b2)
{
    return (a2.x - a1.x)*(b2.y - b1.y) - (b2.x - b1.x)*(a2.y - a1.y);
}

int dist2(Point a1,Point a2)
{
    return (a2.x - a1.x)*(a2.x - a1.x) + (a2.y - a1.y)*(a2.y - a1.y);
}

void Solve(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &B)
{
     Link<Point> *p,*q,*m,*min;
     if(!A.isEmpty())
     {
         m = A.getFirst();
         p = m->getNext();
         while(p != NULL)
         {
              if(p->getData().y < m->getData().y)   
                  m = p;
              else if(p->getData().y == m->getData().y && p->getData().x > m->getData().x)              
                   m = p;
              p = p->getNext();
         }
         
         if(m->getPrevious() == NULL)
              A.setFirst(m->getNext());
         else
             m->getPrevious()->setNext(m->getNext());
         if(m->getNext() == NULL)
            A.setLast(m->getPrevious());
         else
             m->getNext()->setPrevious(m->getPrevious());
         
         if(A.isEmpty())
            A.setLast(m);
         else
             A.getFirst()->setPrevious(m);
         m->setNext(A.getFirst());
         m->setPrevious(NULL);
         A.setFirst(m);
         
         B.insertLast(A.getFirst()->getData());
         
         if(A.getFirst()->getNext() != NULL)
             min = A.getFirst()->getNext();
         else
             min = A.getFirst(); 
         
         do
         {
             q = A.getFirst()->getNext();
             while(q != NULL)
             {
                 if((vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) < 0)||
                 (vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) == 0)&&
                 (dist2(B.getLast()->getData(),min->getData()) < dist2(B.getLast()->getData(),q->getData())))
                    min = q;
                 q = q->getNext();    
             }
             B.insertLast(min->getData());
             min = A.getFirst();
         }
         while(!(B.getLast()->getData() == B.getFirst()->getData()));
         B.deleteLast();
     }
}

int main(int argc, char *argv[])
{
    DoublyLinkedList<Point> A;
    DoublyLinkedList<Point> B;
    stringstream ss;
    Point p;
    string line;
    int counter;
    while(getline(cin,line))
    {
       ss.clear();
       ss.str(line);
       counter = 1;
       while(ss)
       {
           try
           {
               switch(counter)
               {
                   case 1:
                   {
                       ss>>p.x;
                       break;
                   }
                   case 0:
                   {
                       ss>>p.y;
                       A.insertLast(p);
                       break;
                   }
               }
           }
           catch(...)
           {
               
           }
           counter = (counter + 1)%2;
       }
        Solve(A,B);
        cout<<"List A \n";
        A.displayForward();
        A.displayBackward();
        cout<<"List B \n";
        B.displayForward();
        B.displayBackward();
        while(!A.isEmpty())
            A.deleteFirst();
        while(!B.isEmpty())
            B.deleteFirst();
    }    
    return EXIT_SUCCESS;
}

Dopisz funkcje realizujące sortowanie przez scalanie

Funkcję porównującą przekaż jako argument funkcji sortującej

Jeżeli będziesz chciał użyć tej klasy tak ja do wyznaczania wypukłej otoczki to

tam funkcja porównująca ma trzy argumenty

 

komentarz 8 grudnia 2019 przez niezalogowany
edycja 8 grudnia 2019
dużo czytania, nic strasznego nie widzę

Edit:: poświęciłem czas którego nie powinienem i poległem na sortowaniu :(
komentarz 8 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)
edycja 8 grudnia 2019 przez Mariusz M
Jeżeli zrezygnowałeś z L2 to przydałoby się przekazać listę L przez wskaźnik

Jakie będą przypadki brzegowe dla rozdzielania listy

 

Znalazłem funkcję rozdzielającą listę jednokierunkową na połówki

i próbowałem zmodyfikować ją tak aby działała także dla listy dwukierunkowej

" Edit:: poświęciłem czas którego nie powinienem i poległem na sortowaniu : "

 

Wcześniej pisałeś że jeszcze się uczysz czyżbyś kłamał ?
komentarz 11 grudnia 2019 przez niezalogowany
edycja 11 grudnia 2019

może trochę późno

"uczę się c++" (tj staram się nie zapomnieć tego co umiem)

i własne wymysły funkcji podziel u mnie błędu nie wywaliło, globalnie bo już nie chciałem kombinować,

///----------------------------------------
using dllp=DoublyLinkedList<Point>;

//void divdllp(Point P, dllp *A)
void divdllp(Point P, dllp *A,dllp * B)
{


    Link<Point> *temp;

    temp=A->find(P);
    if(temp==nullptr){
        std::cout<<"\n don't find \n";
    }
    else if(temp==A->getFirst()) {
        std::cout<<"\ntemp==A.getFirst()\n";

        B->setFirst(A->getFirst());   // (A->getFirst());
        B->setLast(A->getLast());
        A->setLast(nullptr);
        A->setFirst(nullptr);
        A->setdestructor(0);

    }
    else if(temp==A->getLast()){
                    std::cout<<"\ntemp==A.getLast()\n";

                }
    else {
                    std::cout<<"\ninner element\n";
                    Link<Point> *temp2=temp->getNext();

                    temp2->setPrevious(nullptr);
                    B->setFirst(temp2);   // (A->getFirst());
                    B->setLast(A->getLast());

                    temp->setNext(nullptr);
                    A->setLast(temp);
                }

}

a to reszta twojego kodu. http://wklejto.pl/791751

Postaram się dołączyć resztę funkcji. Jak znajdę chwilę wolnego;

//---------------------------------------------------------------------------------------------------------------

Edit:: sortowanie ogarnięte trochę "trochę po Grubiańsku"

efekt uboczny O(n)vector = O(n) list chyba;

- getdata i delete first musiałem pozmieniać bo mi kompilator psuło;

void sort_dllp (dllp &A){
    std::vector<Point> v;
    Link<Point>* B=A.getFirst();

    while(B) {

        v.push_back(B->getData(B));

        A.deleteFirst();
        B=A.getFirst();
        std::cout<<B->getData(B)<<"|";
    }
    std::cout<<B->getData(B)<<"\n";
    delete B;
    A.setFirst(nullptr);
    A.setLast(nullptr);

    std::sort(begin(v),end(v));

    for(auto &x:v) std::cout<<x<<"|";
    for(auto &x:v) A.insertLast(x);
}

 

komentarz 13 grudnia 2019 przez niezalogowany
No obiecałem to wszystko razem ale nie przez konkatenację.

Pewnie toi znacznie można uprość, ale ten czas:)

24h  http://wklejto.pl/792909
komentarz 14 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)
edycja 14 grudnia 2019 przez Mariusz M
A właśnie co by się stało gdyby do scalania tych resztek chciał użyć konkatenacji  ?

Kiedyś na podstawie opisu algorytmu oraz pseudokodu

przedstawionego przez użytkownika .kassad napisałem sortowanie listy przez łączenie naturalne

Teraz po każdym rozdzielaniu następuje scalanie

Przy czym jedno rozdzielanie musi być wykonane co najmniej raz aby sprawdzić

czy lista jest posortowana

Algorytm można jednak nieco przyspieszyć

Masz na to jakiś pomysł
komentarz 15 grudnia 2019 przez niezalogowany
edycja 15 grudnia 2019

A właśnie co by się stało gdyby do scalania tych resztek chciał użyć konkatenacji  ?

nic więcej pisania bym miał i musiałbym prev ustawiać.

 

przedstawionego przez użytkownika .kassad napisałem sortowanie listy przez łączenie naturalne

nie wiem o jaki algorytm chodzi wiec nie będę się wypowiadał, ale

Algorytm można jednak nieco przyspieszyć

Na początku miałem taki pomysł by dane podmieniać przez wartość i listy nie ruszać, ale coś się wywalało i sobie odpuściłem. bo to parę rzeczy bym musiał sobie przypomnieć.

A tu łączenie dwóch list

#define o(a) #a
void concat1(dllp* A, dllp* B){


    if(!B->getFirst()) {std::cout<<"\nlista "<<o(A)<<" jest pusta\n";
        return;}
    if(!A->getFirst()) {std::cout<<"\nlista "<<o(B)<<" jest pusta\n";
        return;}

    B->getFirst()->setPrevious(A->getLast());
    A->getLast()->setNext(B->getFirst());
    A->setLast(B->getLast());

    B->setFirst(nullptr);
    B->setLast(nullptr);

}

edit:: jakby była funkcja insertLast(LINK<T>*) to by znacznie można by to to uprościć

komentarz 15 grudnia 2019 przez Mariusz M Obywatel (1,670 p.)
edycja 15 grudnia 2019 przez Mariusz M

nie wiem o jaki algorytm chodzi wiec nie będę się wypowiadał,

Chodzi mi o algorytm w wątku

https://forum.pasja-informatyki.pl/425346/sortowanie-przez-laczenie-naturalne-mozliwosc-usprawnienia-algorytmu

 

Jakiś czas temu użytkownik .kassad opisał mi ten algorytm

i podał mi pseudokod który niestety musiałem poprawić

 

Poprawiłem pseudokod podany przez użytkownika .kassad

i przystosowałem podany algorytm do sortowania list

Chciałbym ten algorytm trochę usprawnić , przyspieszyć ale .kassad już nie wchodzi na forum a nikt inny się nie zainteresował i nie mam z kim pisać o tym jak przyspieszyć ten kod

 

Na początku miałem taki pomysł by dane podmieniać przez wartość i listy nie ruszać, ale coś się wywalało i sobie odpuściłem

Z tego co jeden koleś z innego forum twierdził to jest to wina destruktora

Destruktor zwalniając pamięć na lokalną kopię zwalnia też pamięć na węzły oryginalnej listy Co o tym myślisz ? Miałoby to sens ?

Jeśli chodzi o konkatenację to przypadek gdy jedna z list jest pusta też przydałoby się obsłużyć .Jeżeli jedna z list jest pusta wynikiem jest ta druga lista a w przypadku gdy obie listy są puste wynikiem jest pusta lista

W przypadku gdy mamy wskaźnik zarówno na głowę jak i ogon można całkiem zgrabny kod dla konkatenacji napisać

 

@fisker

Widziałeś następującą stronę ?

http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna

oraz algorytmy i struktury danych Banachwskiego , Diksa i Ryttera

 

komentarz 15 grudnia 2019 przez niezalogowany
edycja 15 grudnia 2019

tak jak pisałem wcześniej, z czasem różnie. To co wiem to piszę, nie szukam.

Wina destruktora

Ja nie chciałem destruktora wywoływać nie wien czy przez R wartość, wywołuje  się destruktor, Ciałem skopiować podmienić i to wszystko jak w zwykłym swap() ale nie cały węzeł, tylko wartość typu jaki przechowuje.

Destruktor zwalniając pamięć na lokalną kopię zwalnia też pamięć na węzły oryginalnej listy Co o tym myślisz ? Miałoby to sens

na lokalna kopię tak, ale dlatego trzeba włożyć do oryginału. A oryginalnej listy nie zwalnia bo przekazujesz tylko wskaźniki na listę, a nie samą.

co do reszty to poczytam.

edit:: znowu się spieszyłem i wyszło masło maślane, new na stercie to nie jest lokalna kopia i można dołączać. a na stosie to usunie. Ale poczekam jak ogarnę temat to napiszę, bo zaraz, coraz to większe bzdurki będę pisał.

komentarz 16 grudnia 2019 przez niezalogowany

@Mariusz M,

Algorytm można jednak nieco przyspieszyć

pisanie na pewno tak używając STL; http://www.cplusplus.com/reference/list/list/

24h -->http://wklejto.pl/793554;

A co do szybkości w C kiedyś było szybciej chyba a teraz nie wiem?

Podobne pytania

0 głosów
2 odpowiedzi 1,452 wizyt
pytanie zadane 28 stycznia 2017 w C i C++ przez Łukasz Świtaj Użytkownik (520 p.)
+1 głos
1 odpowiedź 801 wizyt
pytanie zadane 5 czerwca 2017 w C i C++ przez mazak12 Nowicjusz (150 p.)
0 głosów
2 odpowiedzi 810 wizyt
pytanie zadane 13 maja 2017 w C i C++ przez Ala123456 Użytkownik (760 p.)

92,839 zapytań

141,780 odpowiedzi

320,855 komentarzy

62,171 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...