[计算机科学经典著作].Algorytmy-Niklaus.Wirth

[计算机科学经典著作].Algorytmy-Niklaus.WirthNiklaus wirthAlgorytmy+ strukturydanych=programWydanie szosteZ angielskiego przelozyliMichal IglewskiMarek missalJerzy CzyzowiczJerzy dabrowskiScaned by danteO AutorzeProfesor Niklaus Wirth urodzil sie(1934 r )w Winterthur,w Szwajcarii Jest absolwentem(1958 r)WydziahuElektrotechniki na Politechnice(ETH)w ZurychuMa tytul magistra, ktory otrzymat(1960 r ) na LavalUniversity w Kanadzie, i tytul doktora, ktoryotrzymal(1963 r )na University of California. Jestwspohzalozycielem Wydziahu Informatyki na StanfordUniversity. W latach 1963-1967 pelnif tam funkcjewicedyrektora. W latach 1968-1981 piastowaistanowisko profesora na ETH, gdzie zajmowal siepraca dydaktyczna. Obecnie kieruje dziatem informatykina tei uczelniZ komputerami i programowaniem profesor Wirthzetknal sie na wykladach analizy numerycznej w LavalUniversity. UZywano tam wowczas komputera Alvac IIIEPoniewaz byl on notorycznie niesprawny, wiekszosccwiczen z programowania robiono na papierze Wirthszybko zrozumial, ze komputery, do ktorych nalezyprzyszlosc, musza byc niezawodne i jak najefektywniejoprogramowane. Postanowil poswiecic sieprogramowaniu W 1960 roku opracowaf gramatykeprecedencyjna, po czym zajaf sie jezykami programowaniaPierwszym stworzonym przez Witha jezykiembyl Euler- przedstawiony nie tylko na paplerze, aletez wdrozony na komputerach IBM 704i Boroughs B500, stanowiacy punkt wyjscia doopracowania jezykow programowania strukturalnegoW1967 roku Wirth wrocil do Szwajcarii i od 1968 rokuzajal sie Pascalem Kompilator Pascala zostalprzedstawiony w 1970 roku, a jezyka Pascal zaczetouczyc na ETH juz w 1972 roku. Dzis jest on uwazanyza najwazniejszy wspolczesny jezyk programowaniaOdnioshszy wielkie sukcesy z Pascalem, Wirthzainteresowal sie przetwarzaniem wieloprogramowymWynikiem jego prac byl jezyk Modula-2. Pierwszykompilator tego jezyka postal w 1979 roku do pracyna PDP-11W 1980 roku Wirth opracowal Lilith- kombinacjePascala i Moduli-2, a pozniej Oberona, ktorego strukturabyla rozszerzeniem podstawowej struktury Moduli-2Dzis profesor Niklaus Wirth jest uwazany za jednegoz najwiekszych uczonych swiata w dziedzinieinformatyki, a jego dzielo- Pascal -za naywazniejszyjezyk programowania Jego marzeniem jest stworzeniebardziej strukturalnego, bardziej przyjaznegoi mocniejszego jezyka niz ten ostatni Miejmynadzieje, ze Mu sie to udaDane o orginalNIKLAUS WIRTHEidgenossische Technische HochschuleZurich. SwiTzerlandAlgorithms + Data Structures= ProgramsAuthorized translation from the English language edition published by Prentice Hall, IncCopyright C 1976All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,clectronic or mechanical, including photocopying, recording or by any information storage retrievalsystem, without permission from the PublisherPolish language edition published by Wydawnictwa Naukowo-TechniczneCopyright 2002Prow adzenie serii Elzbieta beuermannRedaktor pierwszego wydania Jowila Koncewicz-KrzemieniRedaktor szostego wydania Ewa Zdanowicz.Okladke i strony tytulowe projektowat Pawe! G. RubaszewskiRedaktor techniczny Grazyna MiazekKorekta ZSklad i lamanic aNgoe Copyright for the Polish edition by Wydawnictwa Naukowo-TechniczneWarszawa l980,.1999,2000,2001,2002All Rights ReservedPrinted in polandUtwor w calosci ani we fragmentach nic moze byc powielany ani rozpowszechnianyza pomoca urzadzen elektronicznych, mechanicznych, kopiujacych, nagrywajacychi innych, w tym rowniez nie moze by c umieszezany ani rozpowszechniany w postacicyfrowej zarowno w Internecie, jak i w sieciach lokalnych bez pisemnej zgodyposiadacza praw autorskichAdres poczty elektronicznej: wnt@pol, plStronawwwwww.wnt.com.pISBN83-204-2740-1Spis trescoPrzedmowaPodstawowe struktury danych171.1Wprowadzenie1, 2. Pojecie typu danych20Proste typy danych1. 4. Standardowe typy prost.5. Typy okrojone21. 6. Tablice281.7Rekordy1. 8. Rekordy z wariantami3719Zbior1.10. Reprezentacja tablic, rekordow i zbiorow1. 10.1. Reprezentacja tablic1. 10.2. Reprezentacja rekordow1.10.3. Reprezentacja zbiorow1. 11. Plik sekwencyiny5011.1 Elementarne operatory plikowe1. 11.2. Pliki z podstrukturami1.1 1.3. Teksty581. 11. 4. Program redagowania pliku2Sortowanie73Wprowadzenie22 Sortowanie tablic762.2. 1. Sortowanie przez proste wstawianle2.2.2. Sortowanie przez proste wybieranie802.2.3. Sortowanie przez prosta zamlane82224Sortowanie za pomona malejacych przyrostow225 Sortowanie drzewiasteSPIS TRESCI2.2.6. Sortowanie przez podzial2. 2. 7. Znajdowanie median1012.2.8. Porownanie metod sortowania tablic1032.3. Sortowanie plikow sek wencyjnych2.3. 1. taczenie prost1052.3.2. Eaczenie naturalne2.3.3. Wiclokierunkowe laczenie wywazone1182.3.4. Sortowanie polifazowe1242.3.5. Rozdzielanie serii poczatkowych1363Algorytmy rekurencyjne1453. 1. Wprowadzenie1453.2Kiedy nie stosowac rekursji1483.3Dwa przyklady programow rekurencyjnych151Algorytmy z powrotamI1583.5Problem osmiu hetmanow3.6Problem trwalego matzenstwa168Problem optymalnego wyboru175Dynamiczne struktury informacy]ne183Rekurencyine typy danych1834.2. Wskainiki lub odniesienia1864.3Listy lintowe1924.3.1.Opperacje podstawowe1924.3.2Listy uporzadkowane i listy rcorganizowane1954.3.3. Pewne zastosowanie: sortowanie topologiczne2034.4Struktury drzewiaste2114.4.1. Pojecia podstawowe i definicje2114.4.2. Podstawowe operacje na drzewach binarnych2204.4.3 Przeszukiwanie drzewa z wstawianiem4.4Usuwanie z drzewa2324.4.5. Analiza przeszukiwania drzewa z wstawianiem2344 46. Drzewa zrownowazone2374,4.7. Wstawianie w drzewach zrownowazonych2394.4.8.Usuwanie wezlow z drew zr'ownowazonych2444.4.9. Optymalne drzewa poszukiwan2484,. Drukowanic struktury drzewa2544.5 Drzewa wielokierunkowe2634.5.1 B-drzewa2654.5.2 Binarne B-drzewa2774.6Transformacje kluczy(kodowanie mieszajace2844.6.1. Wybor funkcji transformujace]4.6.2. Usuwanie kolizjl2864.6.3. Analiza transformacji kluczy292SPIS TRESCI5Struktury jezykowe i kompilatory3015.Definicja i struktura jezyka3013045Analiza zan5.3Konstrukcja diagram skladni3095.4Konstrukcja analizatora sktadniowego dla zadanej gramary3135.5Konstrukcja programu analizatora sterowanego skladnta3175.6Translator z notacii BNF na struktury danych sterujace analizatorem3205.7Jezyk programowania PL/05.8. Analizator sktadniowy dla jezyka PL/03325.9. Rcagowanie na bled sktadniowe3415. 10. Maszyna PL/0511. Generowanie kodu wynikowegoDodatckAZbior znakow ASCI372Dodatek bDiagramy skladni dla Pascala373Skorowidz przedmiotowy379Skorowidz programow383PrzedmowaNAMIw dzisiejszych czasach programowanie stalo sie dziedzina wiedzy, ktorejopanowanie ma zasadnicze znaczenie przy rozwiazywaniu wielu problemowInzynierskich, a ktora przy tym moina badac i prezentowac w sposob naukowyProgramowanie awansowato-przestalo byc rzemiostem, a stalo sie dyscyplinaakademicka. Pierwsze prace o niezwyktej doniostosci, ktore zapoczatkowaly tenrozwoj, byly udzialem E W. Dijkstry i C.A.R. Hoare'a. Praca Dijkstry Notes onstructured programming"* spowodowala rewolucje"w programowanlu, ukaz. ujac je w nowym Swietle-jako przedmiot nauki i wspotzawodnictwa intelektualnego. Hoare w artykule,, Axiomatic basis of computer programming"** pokazujew sposob klarowny, ie program mona analizowac, stosujac Sciste rozumowaniematematyczne. W obu tych pracach spotykamy przekonywajaca argumentacjestwierdzenia, Ze programisci mogliby uniknac wielu bledow, gdyby zdawali sobiesprawe z istoty metod i technik, ktore dotychczas stosowali intuicyjnie i nierzadkonieswiadomie. Prace te koncentrowaly sie wokot aspektow budowy i analizyprogramow lub, doktadniej, wokof problemu struktury algorytmow reprezentowanych przez teksty programow, Jest oczy wiste, Ze systematyczne i naukowepodejscie do konstrukcji programow ma szczegolne znaczenie w przypadkuduzych, zlozonych programow, w ktorych korzysta sie ze skomplikowanychzbiorow danych. A zatem metodyka programowania wiaie sie rowniez z koniecznoscia uwzglednienia wszystkich aspektow struktury danych. Programy stanowiaw koncu skonkretyzowane sformufowania abstrakcyjnych algorytmow na pod-stawie okreslonej reprezentacji i struktury danych. Niezwykle wazna praca,wprowadzajaca porzadek do klopotliwie roznorodnej terminologii i pojecdotyczacych struktur danych, byla publikacja Hoare'a Notes on data structuring"**>. Wynika z niej, ie jakiekolwiek decyzje dotyczace struktury danychW Structured pragrammingDahla, Dijkstry i Hoare'a, New York, Academic Press 1972,s.-82W Comm ACk1%69.12.No.10,8.576-583a* W Octreemn2.5.83-174