Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Jak zamienić ścieżki na strukturę drzewiastą?



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
AndyBo



Dołączył: 12 Cze 2016
Posty: 5

PostWysłany: Pią Lut 24, 2017 9:59 pm  OP    Temat postu: Jak zamienić ścieżki na strukturę drzewiastą? Odpowiedz z cytatem Pisownia

Mam plik archiwum, w nim ścieżki:
Cytat:
guava-master\.gitattributes
guava-master\.gitignore
guava-master\.travis.yml
guava-master\guava\src\com\google\common\base\Absent.java
guava-master\guava-gwt\src\com\google\common\base\Absent_CustomFieldSerializer.java
guava-master\guava-tests\test\com\google\common\util\concurrent\AbstractAbstractFutureTest.java

Domyślnie posortowane po ostatnim członie ścieżki czyli nazwie
Zaczynam od posortowania po ścieżce.
Ale to nie takie łatwe, bo separator ścieżki nie jest ani pierwszym ani ostatnim znakiem ASCII, więc może być tak:
ab1a
ab\a
abra

Jak to zrobić prawidłowo?
Może najpierw zamienić separator na \0 , posortować i co dalej?
Tylko aby C# czy C++ nie uznały że \0 oznacza koniec stringa
Czy jest sens zmiany na \001 zamiast na 0? Lepiej niż na \255 a raczej na \65535 bo Unicode w C# a poza tym 255 koliduje z UTF8
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Pią Lut 24, 2017 10:49 pm      Temat postu: Odpowiedz z cytatem Pisownia

Zacznijmy od ustalenia, o co w ogóle pytasz. W tytule napisałeś o zamianie tej listy na drzewo. W treści piszesz o sortowaniu. Co więc chcesz zrobić? Wstępne sortowanie może być przydatne przy wstawianiu serii danych do niektórych rodzajów drzew jako optymalizacja, ale jest to jedynie drobny, dodatkowy krok. Zatem o co pytasz?

Dalej rozwodzisz się nad kodowaniami... ale co one mają w ogóle wspólnego z tym tematem? Co ma już praktycznie nigdzie nie używane kodowanie ASCII do rzeczy? Co mają do tego znaki U+0000 i U+0001, albo nieistniejący* "znak U+FFFF"? O jakich kolizjach mówisz? Ani w C# ani w C++ znak o wartości 0 nie kończy ciągu znaków**.

Halo, pobudka!

Do sortowania: zwykłe sortowanie leksykograficzne z "/" jako separatorem. Koniec, kropka. Rozdzielenie możesz zrobić albo wstępnie rozbijając każdą ścieżkę na listy fragmentów i to sortując, albo rozdzielać na listy fragmentów w komparatorze. Rozwiązanie #2 jest lepsze pod względem wymagań pamięciowych, mniej morduje cache i ma większy potencjał do późniejszej optymalizacji, bo można w razie potrzeby przepisać komparator tak, żeby działał bez tworzenia dodatkowych obiektów. Rozwiązanie #1 ma za to niższy koszt stały, bo rozbicie na fragmenty wykonywane jest tylko raz.
____
* Taki znak nie istnieje w Unicode.
** Nie mylisz z C?
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
samolot



Dołączył: 26 Sty 2006
Posty: 8196
Skąd: Toruń

PostWysłany: Pią Lut 24, 2017 11:19 pm      Temat postu: Odpowiedz z cytatem Pisownia

1. Każdą ze ścieżek podziel splitem względem znaku ukośnika"\".
2. Otrzymasz tablicę stringów, z pominięciem tego użytego ukośnika jako separatora.
3. Przepisz elementy tej tablicy do tablicy struktur, które zawierają po dwa pola:
a) treść elementu tablicy
b) jego długość w znakach
4. Takie ciągi stworzone kolejno z wszystkich ścieżek posortuj alfabetycznie rosnąco i zapisz do tablicy stringów
5. Teraz w pętli, przebiegając po tych ciągach, wstaw ponownie do tych ciągów znaki ukośnika"\", wykorzystując do tego celu informacje z tablicy struktur o długościach poszczególnych elementów

W tym momencie masz już stworzoną listę ścieżek, zachowującą strukturę drzewa katalogów, mając katalogi posortowane alfabetyczne na poszczególnych poziomach, a wewnątrz katalogów posortowane rosnąco listy plików.
Tak to widzę teoretycznie. Oczywiście w trakcie pisania algorytmu trafisz na trudności, które będzie trzeba dopiero wtedy rozwiązać, bo teraz jeszcze nie jesteśmy w stanie przewidzieć wszystkich niuansów.

_________________
Nie zadawaj bezcelowych pytań / Windows 8.1 / Windows 10 / VB2008 / VB 2010 / VB 2012 / Pisz poprawnie
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.20173 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |