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

Sortowanie linii w pliku

VPS Starter Arubacloud
0 głosów
645 wizyt
pytanie zadane 24 stycznia 2017 w Algorytmy przez Mariusz M Obywatel (1,640 p.)
Sortowanie pliku

Zaproponować algorytm sortowania linii w pliku który można łatwo przepisać na kod źródłowy
Najlepiej zapisać go w postaci listy kroków

Przed działaniem algorytmu pojedyncze linie w pliku są posortowane

Po pierwszej iteracji ciągi złożone z dwóch linii są posortowanie

Po drugiej iteracji ciągi złożone z czterech linii są posortowanie

itp

Tylko jak zapisać to w pętli ?
komentarz 24 stycznia 2017 przez Wi_ktos Bywalec (2,950 p.)
Czy to ma wyglądać tak :
aab baa

aaab

I po pierwszej iteracji mamy otrzymać :

aaab aab baa

Bo chyba nie do końca zrozumiałem :/?
komentarz 24 stycznia 2017 przez niezalogowany
@Mariusz: Jeżeli podajesz zadania z jakiegoś zbioru, podawaj również źródło pochodzenia tych zadań.
komentarz 25 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)
przeniesione 12 sierpnia 2017 przez Arkadiusz Waluk
Ciąg znaków występujący w jednej linii traktujemy jako jeden element

Separatorem nie jest spacja tylko znak końca linii

Przykład

Przed iteracjami pojedyncze linie są posortowane

Niech przyjaciele moi siądą przy pucharze
I zapiją mój pogrzeb - oraz własną biedę;
Jeżeli będę duchem - to się im pokaże,
Jeśli mię Bóg uwolni od męki - nie przyjdę...
Lecz zaklinam - niech żywi nie tracą nadziei
I przed narodem niosą oświaty kaganiec;
A kiedy trzeba - na śmierć idą po kolei,
Jak kamienie przez Boga rzucane na szaniec!...

Po pierwszej iteracji

Ciągi dwóch linii są posortowane

I zapiją mój pogrzeb - oraz własną biedę;
Niech przyjaciele moi siądą przy pucharze
Jeśli mię Bóg uwolni od męki - nie przyjdę...
Jeżeli będę duchem - to się im pokaże,
I przed narodem niosą oświaty kaganiec;
Lecz zaklinam - niech żywi nie tracą nadziei
A kiedy trzeba - na śmierć idą po kolei,
Jak kamienie przez Boga rzucane na szaniec!...

Po drugiej iteracji

Ciągi czterech linii są posortowane

I zapiją mój pogrzeb - oraz własną biedę;
Jeśli mię Bóg uwolni od męki - nie przyjdę...
Jeżeli będę duchem - to się im pokaże,

Niech przyjaciele moi siądą przy pucharze
A kiedy trzeba - na śmierć idą po kolei,
I przed narodem niosą oświaty kaganiec;

Jak kamienie przez Boga rzucane na szaniec!...
Lecz zaklinam - niech żywi nie tracą nadziei

Po trzeciej iteracji

Ciąg ośmiu linii jest posortowany

A kiedy trzeba - na śmierć idą po kolei,
I przed narodem niosą oświaty kaganiec;
I zapiją mój pogrzeb - oraz własną biedę;
Jak kamienie przez Boga rzucane na szaniec!...

Jeśli mię Bóg uwolni od męki - nie przyjdę...
Jeżeli będę duchem - to się im pokaże,

Lecz zaklinam - niech żywi nie tracą nadziei
Niech przyjaciele moi siądą przy pucharze

Tutaj mieliśmy osiem linii więc sortowanie skończyło się po trzech iteracjach
ale na ogół nie będziemy mieli danej liczby linii w pliku tylko sam plik
Nie wiem czy jest sens zliczać linie w pliku ponieważ liczba linii w pliku może wyjść
poza zakres typu integer a sam plik może nie zmieścić się w pamięci RAM
komentarz 29 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)
przeniesione 12 sierpnia 2017 przez Arkadiusz Waluk
Jakiś tam algorytm znalazłem ale nie bardzo wiem jak zapisać go w postaci kodu źródłowego w

Pascalu lub ostatecznie w C
komentarz 29 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)
To nie jest z jakiegoś zbioru tylko mam dwa pliki i posortowanie przyspieszyłoby wybór pewnych linii z jednego z tych plików
komentarz 29 stycznia 2017 przez niezalogowany

To posortuj je narzędziami systemowymi, bez pisania własnego programu.

Np. tak:

MacBook-Air-mac:~ tristan$ cat kaczka.txt 
kaczka
dziwaczka
badaczka
u maczka
MacBook-Air-mac:~ tristan$ cat kaczka.txt  | sort
badaczka
dziwaczka
kaczka
u maczka
MacBook-Air-mac:~ tristan$ 

 

komentarz 3 lutego 2017 przez Mariusz M Obywatel (1,640 p.)
edycja 3 lutego 2017 przez Mariusz M
Wolałbym nie korzystać z narzędzi systemowych
Wprawdzie pożałowałem dysku na partycję dla linuksa ale
gdybym miał więcej niż jeden system to musiałbym nie tylko ponownie kompilować
kod źródłowy ale i zmieniać go

Załóżmy że mamy plik A oraz plik B i chcemy wypisać te linie

które znajdują się w pliku A ale nie znajdują się w pliku B

Algorytm naiwny jest taki

Dla każdej linii z pliku A przeglądamy plik B i wyszukujemy w nim linii z pliku A

Daje to nam złożoność kwadratową , a konkretnie O(length(A)*length(B))

 

Posortowanie plików da nam złożoność O(nlogn)

pod warunkiem że do posortowania fragmentów pliku w pamięci użyjemy

sortowania stogowego

a następnie będziemy scalać fragmenty które nie zmieściły się w pamięci
komentarz 7 lutego 2017 przez Mariusz M Obywatel (1,640 p.)
przeniesione 12 sierpnia 2017 przez Arkadiusz Waluk
Pomysł polega na tym aby przystosować iteracyjny algorytm sortowania tablic przez scalanie do łączenia plików
Problem jest z jego zapisaniem
komentarz 12 sierpnia 2017 przez Mariusz M Obywatel (1,640 p.)
przeniesione 12 sierpnia 2017 przez Arkadiusz Waluk
#include<iostream>
#include<fstream>
#include<string>

using namespace std;

void LeerElemDetectandoFin(fstream &arch,string &comp,bool &finArch)
{
    finArch=arch.eof();
    if(!finArch)
    {
        getline(arch,comp);
    }
}

void PasarElemDetectandoFin(fstream &archOrigen,fstream &archDestino, string &comp,bool &finArchOrigen)
{
    archDestino<<comp<<"\n";
    LeerElemDetectandoFin(archOrigen,comp,finArchOrigen);
}



void Mezcla(string ruta,fstream &aux1,fstream &aux2,fstream &arch)
{
    string c1,c2;
    string ruta1,ruta2;
    bool finArch1,finArch2;
    size_t posicion;

    posicion=ruta.find(".");
    if(posicion!=string::npos)
    {
        ruta1=ruta.substr(0,posicion)+"_temp001.txt";
        ruta2=ruta.substr(0,posicion)+"_temp002.txt";
    }

    aux1.open(ruta1.c_str(),ios::in);
    aux2.open(ruta2.c_str(),ios::in);
    arch.open(ruta.c_str(),ios::out);

    LeerElemDetectandoFin(aux1,c1,finArch1);
    LeerElemDetectandoFin(aux2,c2,finArch2);
    while(!finArch1 && !finArch2)
        if(c1<c2)
            PasarElemDetectandoFin(aux1,arch,c1,finArch1);
        else
            PasarElemDetectandoFin(aux2,arch,c2,finArch2);
    while(!finArch1)
        PasarElemDetectandoFin(aux1,arch,c1,finArch1);
    while(!finArch2)
        PasarElemDetectandoFin(aux2,arch,c2,finArch2);

    arch.close();
    aux1.close();
    aux2.close();
}

void Division(string ruta,fstream &arch, fstream &aux1,fstream &aux2,bool &esVacio2)
{
    string valorActual,valorAnterior;
    string ruta1,ruta2;
    bool cambio;
    size_t posicion;

    posicion=ruta.find(".");
    if(posicion!=string::npos)
    {
        ruta1=ruta.substr(0,posicion)+"_temp001.txt";
        ruta2=ruta.substr(0,posicion)+"_temp002.txt";
    }

    arch.open(ruta.c_str(),ios::in);
    aux1.open(ruta1.c_str(),ios::out);
    aux2.open(ruta2.c_str(),ios::out);
    cambio=true;
    esVacio2=true;
    if(!arch.eof())
    {
        getline(arch,valorActual);
        aux1<<valorActual<<"\n";
        valorAnterior=valorActual;
    }
    while(!arch.eof())
    {
        getline(arch,valorActual);
        if(valorAnterior>valorActual)
            cambio=!cambio;
        if(cambio)
            aux1<<valorActual<<"\n";
        else
        {
            aux2<<valorActual<<"\n";
            esVacio2=false;
        }
        valorAnterior=valorActual;
    }
    arch.close();
    aux1.close();
    aux2.close();

}


int main()
{
    string ruta;
    bool esVacio2=false;
    fstream arch,aux1,aux2;
    cout<<"Darme ruta de archivo que quieres ordenar\n";
    getline(cin,ruta);

    while(!esVacio2)
    {
        Division(ruta,arch,aux1,aux2,esVacio2);
        if(!esVacio2)
        {
            Mezcla(ruta,aux1,aux2,arch);
        }
    }

}

Zamiast sortować tworzy puste pliki
Co może być nie tak w tym kodzie

2 odpowiedzi

+1 głos
odpowiedź 7 lutego 2017 przez .kassad Gaduła (3,420 p.)
wybrane 8 lutego 2017 przez Mariusz M
 
Najlepsza

Przez serię w pliku będę miał na myśli uporządkowane linie - np. dla 

a
b
c
x
a
h
y
jedną serią będzie a b c x, natomiast drugą a h y.

Najpierw dzielisz plik z tekstem na dwa tymczasowe pliki w następujący sposób (sortowanie rosnące):

  • pobierasz z pliku pierwszą linię i zapisujesz ją do do pierwszego pliku
  • dopóki nie natrafisz na koniec pliku wykonaj:
    • pobierz linię z pliku
      • jeżeli jej wartość jest większa od poprzedniej, zapisujesz ją w tym samym pliku, co poprzednią
      • w przeciwnym zmieniasz plik docelowy na ten drugi, do którego nie zapisałeś poprzedniej linii.

Jak masz już podzielony plik na dwie części, przechodzimy do scalania. To, co trzeba zrozumieć i zwrócić uwagę to fakt, że jak wczytujesz kolejne linie z plików pomocniczych, to rozpoczynasz czytanie nowej serii dopiero jak skończyłeś czytać aktualnie sortowanie serie z obu plików (przynajmniej mi zrozumienie tego przysporzyło sporo kłopotów, może tobie pójdzie łatwiej):

  • pobierz z obu plików pomocniczych ich pierwsze linie;
  • dopóki oba pliki nie będą puste:
    • dopóki aktualnie sortowane serie w pliku nie są przeczytane:
      • wybierz linię o mniejszej wartości i wpisz ją do pliku docelowego;
      • z pliku, z którego pochodziła mniejsza linia pobierz kolejną linię (o ile jeszcze jakaś została - jeżeli nie przepisujesz do pliku docelowego resztę serii z drugiego pliku i zaczynasz wracasz do głównej pętli);
    • pobierz z obu plików nowe linie

Obie te fazy powtarzasz tak długo, aż podczas fazy podziału cała zawartość pliku źródłowego została przepisana tylko do jednego pliku pomocniczego - to znaczy, że masz tylko jedną serię i plik jest posortowany. Co prawda warunek nie jest do końca zogdny z teoretycznimi założeniami algorytmu, ale co działa (y) .

Może przykład pozwoli ci lepiej zrozumieć:

Plik: (N =8) 44 55 | 12 42 94 | 18 | 06 67 (4 serie różnej długości)

Serie są dystrybuowane naprzemiennie na 2 taśmy:

1. faza:

t1: 44 55 | 18

t2: 12 42 94 | 06 67

t3: 12 42 44 55 94 | 06 18 67 (2 serie)

 

2. faza:

t1: 12 42 44 55 94

t2: 06 18 67

t3: 06 12 18 42 44 55 67 94 (1 seria, plik posortowany)

 

https://github.com/mmichal10/natural-merge - moja implementacja w c - nie brakuje tu pewnie jakichś złych praktyk, wycieków pamięci itp. Miałem trochę inne rekordy to posortowania, ale może kod ci w czymś pomoże. Ciebie powinny zainteresować funkcje split() i merge() z pliku fileManager.c. W moim kodzie jest zapimplementowany mechanim stronnicowania, co może utrudnić jego zrozumienie, ale wydaje mi się, że jeżeli zignorujesz zmienne z 'offset' w nazwie, a putInBuffer i getRecord potraktujesz jako zwykłe pisanie i czytanie z pliku, to sporo ułatwi.

komentarz 8 lutego 2017 przez Mariusz M Obywatel (1,640 p.)
edycja 8 lutego 2017 przez Mariusz M

Mógłbyś jeszcze przeanalizować złożoność tego algorytmu

Opisałeś algorytm dzielenia i łączenia a co z procedurą sortującą ?
 

Z tym githubem są problemy

 

dopóki aktualnie sortowane serie w pliku nie są przeczytane:

Jak zapisać warunek dla tej pętli while 

pobierz z obu plików nowe linie

Jeśli będą to ostatnie linie w plikach nie wejdzie do pętli
i  nie zostaną one przekopiowane

komentarz 8 lutego 2017 przez .kassad Gaduła (3,420 p.)

Sortowanie odbywa się właśnie podczas złączania, to jest najważniejsze do zrozumienia w całym algorytmie. Ogólna koncepcja jest taka, żeby podczas scalania mieć w pamięci tylko dwa rekordy - jeden z pierwszego pliku pomocniczego, drugi z drugiego pliku pomocniczego. Ten który jest mniejszy przepisujesz do pliku docelowego, i pobierasz kolejny rekord, z tego samego pliku pomocniczego, z którego pochodził ten mniejszy rekord - chyba że w tym pliku nastąpił koniec serii - wtedy musisz poczekać, aż w drugim też skończy się seria i dopiero wtedy możesz zacząć kolejne serie w obu plikach.

Spróbuj przeanalizować ten przykład, co napisałem, mając na uwadze fakt, że możesz widzieć w danym momencie tylko po jednym rekordzie z każdego pliku pomocniczego. 

Myślę, że jak zwykłe sortowanie przez scalanie - O(n*logn)

 

dopóki aktualnie sortowane serie w pliku nie są przeczytane:

Jak zapisać warunek dla tej pętli while 

Jeżeli chcesz wiedzieć, czy rekord należy do nowej serii, czy jeszcze do aktualnej, potrzebujesz pamiętać wartość poprzedniego rekordu z tego pliku - jeżeli poprzednia wartość jest mniejsza, lub równa aktualnemu rekordowi, seria wciąż trwa, jeżeli poprzedni rekord jest większy od aktualnego, to zaczyna się nowa seria. 

string rekordZtmp1
string rekordZtmp2
string poprzedniRekordZtmp1 = cosOdCzegoKazdyStringBedzieWiekszy
string poprzedniRekordZtmp2 = cosOdCzegoKazdyStringBedzieWiekszy
int koniecSeriiWtmp1 = 0
int koniecSeriiWtmp2 = 0
rekordZtmp1 = pobierzLinie( tmp1 );
rekordZtmp2 = pobierzLinie( tmp2 );
while( tmp1 != EOF || tmp2 != EOF )
              while(!koniecSeriiWtmp1 && !koniecSeriiWtmp2)
                                if ( rekordZtmp1 > rekordZtmp2 )
                                                wpiszLinie( plikDocelowy, rekordZtmp1 );
                                                poprzedniRekordZtmp1 = rekordZtmp1;
                                                rekordZtmp1 = pobierzLinie( tmp1 );
                                                if ( poprzedniRekordZtmp1 > rekordZtmp1)
                                                                koniecSeriiWtmp1 = 1;
                                else
                                                wpiszLinie( plikDocelowy, rekordZtmp2 );
                                                poprzedniRekordZtmp2 = rekordZtmp2;
                                                rekordZtmp2 = pobierzLinie( tmp2 );
                                                if ( poprzedniRekordZtmp2 > rekordZtmp2 )
                                                                koniecSeriiWtmp2 = 2;

             while(!koniecSeriiWtmp1)
                          wpiszLinie( plikDocelowy, rekordZtmp1 );
                          oprzedniRekordZtmp1 = rekordZtmp1;
                          rekordZtmp1 = pobierzLinie( tmp1 );
                          if ( poprzedniRekordZtmp1 > rekordZtmp1)
                                           koniecSeriiWtmp1 = 1;
             while(!koniecSeriiWtmp2)
                          wpiszLinie( plikDocelowy, rekordZtmp2 );
                          poprzedniRekordZtmp2 = rekordZtmp2;
                          rekordZtmp2 = pobierzLinie( tmp2 );
                          if ( poprzedniRekordZtmp2 > rekordZtmp2 )
                                         koniecSeriiWtmp2 = 2;

             koniecSeriiWtmp1 = koniecSeriiWtmp2 = 0;
             string poprzedniRekordZtmp1 = cosOdCzegoKazdyStringBedzieWiekszy
             string poprzedniRekordZtmp2 = cosOdCzegoKazdyStringBedzieWiekszy

                

  

 

komentarz 15 października 2017 przez Mariusz M Obywatel (1,640 p.)
edycja 25 marca 2019 przez Mariusz M
Na poczatku myslalem o czyms co sie nazywa laczeniem prostym
Jak zastosowac ten pomysl do sortowania list ?

Odpowiedź była pomocna
Poprawiłem wykrywanie końca serii i działa także dla list
0 głosów
odpowiedź 23 marca 2019 przez Mariusz M Obywatel (1,640 p.)
edycja 30 marca 2019 przez Mariusz M

@.kassad testowałeś ten swój pseudokod ?

Próbowałem przystosować ten algorytm do sortowania listy i wyskoczył mi segmentation fault

podczas scalania

Funkcja rozdzielająca wydaje się być dobrze napisana

Wydaje mi się że w swoim pseudokodzie źle wykrywasz koniec serii
i dlatego w przypadku list następuje dereferencja NULLa

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


struct TNode
{
     int data;
     struct TNode *next;
     struct TNode *prev;  
};

struct TList
{
    struct TNode *head;
    struct TNode *tail;   
};

void ListInit(struct TList *L)
{
     (*L).head = NULL;
     (*L).tail = NULL;
}

int ListIsEmpty(struct TList L)
{
   return (L.head == NULL);  
}

void ListDisplayForward(struct TList L)
{
     int counter = 0;
     struct TNode *curr = L.head;
     printf("List (head-->tail): ");
     while(curr != NULL)
     {
         printf("%d -> ",curr->data);       
         curr = curr->next;
         counter++;       
     }
     printf("NULL \n");
     printf("Liczba wezlow listy : %d \n",counter);
}

void ListDisplayBackward(struct TList L)
{
     int counter = 0;
     struct TNode *curr = L.tail;
     printf("List (tail-->head): ");
     while(curr != NULL)
     {
         printf("%d -> ",curr->data);       
         curr = curr->prev;
         counter++;       
     }
     printf("NULL \n");
     printf("Liczba wezlow listy : %d \n",counter);
}


void ListInsert(struct TList *L,int k)
{
    struct TNode *x = (struct TNode *)malloc(sizeof(struct TNode )) ;
    x->data = k;
    x->next = (*L).head;
    if((*L).head != NULL)
       (*L).head->prev = x;
    (*L).head = x;
    x->prev = NULL; 
    if(x->next == NULL)
        (*L).tail = x;      
}

void ListDelete(struct TList *L)
{
     struct TNode *x = (*L).head;
     if((*L).head != NULL)
     {
        if((*L).head->next == NULL)     
             (*L).tail = (*L).head->prev;              
         (*L).head = x->next;
         if(x->next != NULL)
            x->next->prev = x->prev;       
         free(x);    
     }
}

int ListSplit(struct TList L,struct TList *A,struct TList *B)
{
    int isEmptyB,swapLists;
    struct TNode *currNode,*prevNode;
    swapLists = 1;
    isEmptyB = 1;
    ListInit(A);
    ListInit(B);
    if(L.head != NULL)
    {        
        // Usun wezel z glowy listy L
        //Wstaw wezel za ogon listy A
        currNode = L.head;
        if(L.head->next == NULL)
           L.tail = NULL;
        else
           L.head->next->prev = NULL;
        L.head = L.head->next;
        
        if((*A).head == NULL)
           (*A).head = currNode;
        else
        {
            (*A).tail->next = currNode;
            currNode->prev = (*A).tail;
        }       
         (*A).tail = currNode;
         currNode->next = NULL;
                      
        prevNode = currNode;
    }
    while(L.head != NULL)
    {
        // Usun wezel z glowy listy L
        currNode = L.head;
        if(L.head->next == NULL)
           L.tail = NULL;
        else
           L.head->next->prev = NULL;
        L.head = L.head->next;
        
        if(prevNode->data > currNode->data)
           swapLists = !swapLists;
        if(swapLists)
        {
           //Wstaw wezel za ogon listy A
           if((*A).head == NULL)
           (*A).head = currNode;
            else
            {
                (*A).tail->next = currNode;
                currNode->prev = (*A).tail;
            }       
             (*A).tail = currNode;
             currNode->next = NULL;
        }
        else
        {
            //Wstaw wezel za ogon listy B
            if((*B).head == NULL)
           (*B).head = currNode;
            else
            {
                (*B).tail->next = currNode;
                currNode->prev = (*B).tail;
            }       
             (*B).tail = currNode;
             currNode->next = NULL;
            isEmptyB = 0;
        }
        prevNode = currNode;                  
    }
    return isEmptyB;
}

void ListMerge(struct TList A,struct TList B,struct TList *L)
{
     struct TNode *tmpA, *tmpB;
     struct TNode *poprzedniZtmpA = NULL;
     struct TNode *poprzedniZtmpB = NULL;
     int koniecSeriiWtmpA = 0;
     int koniecSeriiWtmpB = 0;
     ListInit(L);
     if(A.head != NULL)
     {
         // Usun wezel z glowy listy A
         tmpA = A.head;
         if(A.head->next == NULL)
             A.tail = NULL;
         else
             A.head->next->prev = NULL;
         A.head = A.head->next;                      
     }
     if(B.head != NULL)
     {
         // Usun wezel z glowy listy B
         tmpB = B.head;
         if(B.head->next == NULL)
             B.tail = NULL;
         else
             B.head->next->prev = NULL;
         B.head = B.head->next;                    
     }
     while(A.head != NULL || B.head != NULL)
     {
           while(!koniecSeriiWtmpA && !koniecSeriiWtmpB)
               if(tmpA->data > tmpB->data)
               {
                  // Wstaw wezel z listy A za ogon listy L
                  if((*L).head == NULL)
                     (*L).head = tmpA;
                  else
                  {
                      (*L).tail->next = tmpA;
                      tmpA->prev = (*L).tail;
                  }
                  (*L).tail = tmpA;
                  (*L).tail->next = NULL;
                  poprzedniZtmpA = tmpA;
                 // Usun wezel z glowy listy A
                 tmpA = A.head;
                 if(A.head->next == NULL)
                     A.tail = NULL;
                 else
                     A.head->next->prev = NULL;
                 A.head = A.head->next;
                 if(poprzedniZtmpA->data > tmpA->data)
                      koniecSeriiWtmpA = 1;                                  
               }
               else
               {
                   // Wstaw wezel z listy B za ogon listy L
                   if((*L).head == NULL)
                     (*L).head = tmpB;
                   else
                   {
                       (*L).tail->next = tmpB;
                       tmpB->prev = (*L).tail;
                   }
                   (*L).tail = tmpB;
                   (*L).tail->next = NULL;
                   poprzedniZtmpB = tmpB;
                   // Usun wezel z glowy listy B
                   tmpB = B.head;
                   if(B.head->next == NULL)
                       B.tail = NULL;
                   else
                       B.head->next->prev = NULL;
                   B.head = B.head->next;
                   if(poprzedniZtmpB->data > tmpB->data)
                      koniecSeriiWtmpB = 1;
               }
            while(!koniecSeriiWtmpA)
            {
                // Wstaw wezel z listy A za ogon listy L
                if((*L).head == NULL)
                     (*L).head = tmpA;
                  else
                  {
                      (*L).tail->next = tmpA;
                      tmpA->prev = (*L).tail;
                  }
                  (*L).tail = tmpA;
                  (*L).tail->next = NULL;
                 poprzedniZtmpA = tmpA;
               // Usun wezel z glowy listy A
                 tmpA = A.head;
                 if(A.head->next == NULL)
                     A.tail = NULL;
                 else
                     A.head->next->prev = NULL;
                 A.head = A.head->next;
                 if(poprzedniZtmpA->data > tmpA->data)
                      koniecSeriiWtmpA = 1;
            }
            while(!koniecSeriiWtmpB)
            {
                // Wstaw wezel z listy B za ogon listy L
                if((*L).head == NULL)
                     (*L).head = tmpB;
                  else
                  {
                      (*L).tail->next = tmpB;
                      tmpB->prev = (*L).tail;
                  }
                  (*L).tail = tmpB;
                  (*L).tail->next = NULL;
                poprzedniZtmpB = tmpB;
               // Usun wezel z glowy listy B
               tmpB = B.head;
               if(B.head->next == NULL)
                   B.tail = NULL;
               else
                   B.head->next->prev = NULL;
               B.head = B.head->next;
               if(poprzedniZtmpB->data > tmpB->data)
                   koniecSeriiWtmpB = 1;
            }
           koniecSeriiWtmpA = 0;
           koniecSeriiWtmpB = 0;
           poprzedniZtmpA = NULL;
           poprzedniZtmpB = NULL;                               
     }
}

int main()
{
    int k,n,m;
    struct TList L,L1,L2;
    ListInit(&L);
    srand(time(NULL));
    scanf("%d %d",&n,&m);
    for(k = 1;k <= n;k++)
        ListInsert(&L,rand()%m);
    printf("List L \n");
    ListDisplayForward(L);
    ListDisplayBackward(L);
    ListSplit(L,&L1,&L2);
   printf("List L1 \n");
    ListDisplayForward(L1);
    ListDisplayBackward(L1);
    printf("List L2 \n");
    ListDisplayForward(L2);
    ListDisplayBackward(L2);
    while(!ListIsEmpty(L1))
        ListDelete(&L1);
    while(!ListIsEmpty(L2))
        ListDelete(&L2); 
 /*  
  ListMerge(L1,L2,&L);
    printf("List L \n");
    ListDisplayForward(L);
    ListDisplayBackward(L);
    while(!ListIsEmpty(L))
      ListDelete(&L); 
*/                  
    system("PAUSE");
    return 0;
}

 

Podobne pytania

0 głosów
1 odpowiedź 187 wizyt
pytanie zadane 21 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 592 wizyt
0 głosów
1 odpowiedź 364 wizyt
pytanie zadane 7 września 2019 w Algorytmy przez Jacuchna0 Użytkownik (640 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...