[Playlisten] [Impressum und Datenschutzerklärung]

12.01.1 Datenstrukturen, Array, Queue, Stack


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

inden verbleibenden Termin ist jetzt ja nach dem Rundgang durch sie nicht mehr so viel in den verbleibenden Termin wollte ich ihn schon bisschen näher bringen was jetzt wirklich Informatik ist und als erstes hier die Algorithmen und Datenstruktureneines Mandantenstrukturendass es noch am einfachstenist ein dichtesten an dem dran was sie bisher gemacht haben??eine Datenstrukturschondie organisiere ich meine Datendann Struktur hatten wir schondas FAwenn Sie eine Liste an Messwerten haben das wäre so das erste was aneiner herunterkommtsie messen allezehn Sekundendie Temperatur in allen Räumen des Hauses und versuchen dann mehr oder minder geschickt zu regeln oder sie messen welche Konzentrationgeradeist also ?? hat die sieirgend einenBio Apparat rein schicken alle zehn Sekunden oder jede Minuteverkriechen sie eine Sammlung von MesswertenKomma vier mal dreizehn Komma neun und so weiter und so weiterso eineSammlung an Messwerten schreit nach einem eindimensionalenRaydas ist wohlanscheinend eine sinnvolle Datenstrukturdafürich gucke mir anwie ich meine Daten organisierenkann nicht einfach nurein Beutel mit den Zahlen sonderlich strukturierte sich organisierenund darum geht's bei den Datenstrukturendie machen es raffiniertwenn ich ein Bild habeoder vielleicht auch Geodatennach Längen Breitengrad Geodatenoder wenn ich ein Bild habedann werde ich die werde ich daswohlerst mal ohne weiteres Nachdenken in ein zweidimensionalesRay einsortierenoder Geodaten die nach Längengrad Breitengrad sortiert sind Tätigkeitenan zwei mit den auserwähltenes wäre zumindest nahe liegend wenn sie Volumendatenhaben denken Sie an die Klimasimulationenamüberlegen muss wo in diesem einen Kubikmeter meiner Atmosphäreein Kubikmeter meiner Atmosphäre habe ich ?? habe ich folgende Temperaturhabe ich folgende Luftfeuchtigkeitverlinken halt an Kohlendioxidfolgenden Inhaltund neunzig zweite und das fürMillionen Milliarden Kubikmeternwenn ich mir das speichern mussschreit das für mich nach einem dreidimensionalenRay gucken ob das wirklich praktikabelistaber auf eine für das für mich nach einem dreidimensionalenRay schreibenwenn ich topographischeAufnahmen habe von den Maschinenbauteilenund gemächlich angucken will oder Risse drin sind wenn ich die wahrscheinlich auch dreidimensionalspeichern3Ddas wenn ganz billigeDatenstrukturen gewährt hattenmal eine andere Datenstruktureine allererste andere Datenstrukturdie Warteschlangedenn siewenn sie irgendwie Tickets kaufen oder was auch immer man da ergänzt die Warteschlange dasbaut man eins zu eins nach in der Informatikeine Warteschlange kann zum Beispiel benutzt werden um Druckaufträgewerdenjaeine Warteschlangezu stellen Druck auf Englisch in eine Schlange zu stehen haben wir den DruckertextmalBeistrich was vor ??anden sie vor sie haben Info den Drucker der irgendwie gerade fleißig am arbeiten ist und sie schicken demeineX Dokumente nacheinander und jedes hat nochmals den Seitenirgendwie müssen diese ganzen Dokumente ja schlangestehenwie sie denn endlich aus dem Drucker rauskommen können ?? das würde ?? zu einer Datenstrukturmachenfür die diese die Seiten dieser Dokumente in eine Warteschlange stellenals Ende der Warteschlangewird es jeweils neue Dokument reingestelltam Anfang der Warteschlangeoder Druckertreiber das Dokument raus was als nächstes kann gedrucktals ein Beispiel für eine Warteschlange wie sie dann vorLebenabstraktin der Informatik ist natürlich erstan solchen abstrakten Strukturen interessiertAbstract sieht das so aus sie haben eineListe an Speicher stellenSie sich gar nicht genau dafür was hier drin steht nicht Beistrich denn anders als man Rayum sie auf jeder einzelnen der Speicherstellenauch direkt zugreifen können bei der Warteschlange möchte ich nicht wissen was dann der fünften oder an der achten Stelle stehtdas einzige?? des wichtigste soll ich sagen das wichtigste was ich mit der Warteschlange machen will ist das icheinen neues Elementhinten anhängen willdas würde heißen and youin die Schlange stellen die heißt ja auchQueuedie Warteschlangederübliche Witz istwenn der eineBrite an der Haltestelle steht und der zweite dritte dazu kommt und fragt ?? Hugh Ewingstehen sie in der Schlangealso juristisch langeEntziehungist etwas in die Schlange stellen das Ende der Schlange stellendas muss dann automatisch irgendwie durch Rücken und es gibtdie zudie Funktion die ?? muss es dann geben die so etwas aus der Schlange rausnehmenam Anfang der nächsten ?? bedient wird der wird mit Didueist das ein ekliges Wortdie Queue somit dem ?? aus der Schlangedaswird ja grausam Q U E ähes ist ?? ein Tippfehler ?? wirklich so ??diesesWasser hat also eigentlich zwei Funktionen im wesentlicheneine Funktion mit der sie sagen können Audi setzt dieses Ding bitte dieses Objekt bitte ans Ende schnellin die Schlange stellen und eine Funktion mittels des erst rausholen muss dieSinnunterstützung?? fähig und sie frei zugreifenauf irgend ein Element des Schreiben des Lesen bei der Warteschlange möchte das eigentlich nichthatten zwar typischerweisedoch die Möglichkeitdie Druckaufträgein Windows oder so ist an Druckaufträgensehnen kann sie doch sagen und den fünften möchte doch mal bitte killendie anderen doch die Möglichkeit aber eigentlich sie wahrscheinlich dafür gedacht ein diese Warteschlange nur dafürdas wäre so eineerstebillige Datenstrukturdas nennt sich first in first Auth auch das irgendwo sehen fifa Infobriefauf iPhoneeinen Fall vorwarf war ein first in first laut Bufferfirst in first aus der erste rein ist auch der erste der rauskommtwie bei der Warteschlangedie Tickets kaufen first in first auchdas soll das heißen erste rein geht es auf erste der rauskommtanjeder der in den Laden kommt's wird mit jubelnden Angestellte versickern zwanzig mal ein zu habenund aber nutzen zehnmal mehr derselben Seite die Queueweilalle ganz fürchterliche Bestellungen haben oder nach dem Kleingeld suchen und das super langsam vorangeht und es muss nicht paarig seineinsickernganz ?? zu haben und viel weniger die zu habenirgendwann sollte natürlich trotzdemgenauso viel die Queue aufgerufen worden sein ?? aufgerufen worden ist uns haben sie verschlang in der Schlange die sie nicht ?? sind haben sie ein paar Leute in der Schlange die sie nicht bedient haben?? zum Schluss sollte so häufig die ?? aufgerufen worden sein ?? aufgerufen worden ist anman sollte nicht häufiger die Queue aufrufen ?? Menschen aufgerufen worden ist das ein bisschen problematischwenn sie mehr Leute bedient als in den Laden gekommen sind das ein bisschen komisch an aber es kann sein das erst ganz häufig Entschuh aufgerufen wird ?? vorgestellt hundert Dokument in dieDruckerwarteschlangeund der Druckerbraucht drei Tage bis sie ihn endlich abgearbeitethatokay das ist die Warteschlange?? first in first Auth es gibt das umgekehrte Prinzip?? last in first AuthLive Punktdas ist der Stapeloder StackstarboderDeckHayes decken das MenschengeräuschHeustapelHashtagander funktioniert umgekehrt das ist last infirst Authder letzte der reingekommenistist der erste der wieder rauskommt stellt sich das im Laden vor es gibt Tumultähmdass wir die funktionieren dass der letzte Einkommen sofort bedient wirdder Stab ist genausoder letzte der ankommt wird sofort bedient ?? das isteineine Strukturdie sie wahrscheinlich erst relativ spät sehen wie ist aber deshalb gleich nochvon grundsätzlicher Bedeutung für die Mikroprozessorenamein Stapelstapelsachenübereinander in Stapelbücherstapelblätterzwei Operationen wieder eine Operation legt ein neues Element drauf die Halsbandstapeltypischerweise Pushauf den Stapeldrauflegen wäre zu Pushund du bist ??und die andere Operation dies gibt nimmt's runterdas wäre??meinesehr wohl aus als ober opfern müsstedas bezieht sich immer auf das oberste schädlichen Stapelbüchervoralle super schwer sie können nicht zwischendurch als raus ziehen das einzige was sie machen können ist oben eins drauflegen und noch eins noch als noch eins drauflegen auf das Wasser schon drauf liegt das oberste dürfen sie Unternehmenund die unteren sind vergrabenan die Komma nicht an das nach der Staffeldas sieht erst mal sehr schräg aus es konnte sich dann später beim Programmieren auch vorsieht aber erst mal schräg ausanwesentliche Anwendung für diesen Stapelist was der Mikroprozessorden ganzen Tag machtum Unterprogramme zu verwaltendieserStapel beim Mikroprozessorist typischerweise an die Decke geklebt stellt sich dasselbe voraber sie kleben es an die Deckefalsch rumsowohldie einzelnen Einträgeimmer bisschenKleber dazwischenTropfenkleberund so weiter unter die Decke geklebtund siekleben noch was drunter das wäre Pushodersie ziehen es wieder abvon diesem hängenden Stapelan das wäre Popso bitte typischerweiseimplementiertder Staffelundwas dieser Stapelim real existierendenMikroprozessormachtistzu speichernwussten wieder zurückgehtund was die lokalen Variablen sindanwenn ein Programm offen wenn eine Funktion aufgerufenwirdin Programmmuss sich der Mikroprozessormerken wusste wieder zurück geht nach Ende der Funktion wurden Sprinterin wieder zurückdas liegt auf einen Stapelund die Variablenwertedie übergeben werden Delikte auch auf den Stapelund dann geht er in die Funktion einiger aufgerufen worden ist das Unterprogramm was aufgerufen worden ist wenn dieses Unterprogrammselbst noch andere Funktion aufruftlegt es dieübergebenenArgumenteauf den Stapel legt esauf den Stapel wusste wie das weitergehtund ruft die Funktion auf und so weiter und so weiter da sie Struktur genau die Idealeder nachher wenn die Funktion wieder zurückgehen gucken sie einfach nach was ist denn das lässt was auf dem Stapel nicht wissenwo sie ihn zurückspringen müssen nimm das vom Stapel runterin die nächste Funktion ändert weiß sie wo sie zurückbringen muss und das im Start rund und so weiterdas ist die übliche Strukturum es möglich zu machen dass Funktioneneinander aufrufendas sei gerade normalim wahren Leben hierdass es gar nicht dumm wenn sie die backen dass sie das Malendes Destination sicherlich vorher eine FunktioninFinXundirgendwasplötzliches zurückklein X mal Xund eine Funktion gegen die aufrufteine Funktion die die Aufrufnämlich sagen wir Return F von Xmal Xzu viel des Gutenund Maine ruftMaineruft den Aufrufdieaufdie vonsowasso meine Mailfunktionruft die aufeine G Funktion groß F aufund es tut einfach irgendwas das muss irgendwie organisiert werdenwenn der Mikroprozessor mit dieser Fusion fertiges Muster wissen wo es in Mail weiter macht das da arbeitet auf ein Stapelspeicherdiese Funktion FLI aufgerufen worden ist muss die wissenwo sie denn aufgerufen worden ist und wie es dann weitergehtdass es auf einem Stapelspeicherdas wir dann tatsächlichdafür mäßig abgearbeitetdas es so verschachtelten Ausrufezeichen wie'sankommtdiese Variablen hier zu lokalen Variablenund wenn wir so weiter währenkann Ryandie würden auch auf den Stapel gespeichert und dann ebenfalls mit abgeräumtdas ist man die Bankensehr interessant weil sie diesen Stapel hier tatsächlich angucken können beim die Banken wenn ich hier mal rein gehein die Funktion G und jetzt in die Funktion FG ruft RF auf die Funktion F eingehenbin ich in F drin kann ich mir angucken wo ich gerade bin ?? youCall Stack als offizielles deckt derAufrufstapelkostet was ist denn jetzt aufgerufen wordenkein Platz mehr erscheint oder das okaywar Fenster dicht machenpro Seite landet Punkt das ist jetzt der Aufruf Stackdie Funktion F ist von der Funktion G aufgerufenworden die Funktion G ist von der Funktion Maine aufgerufen worden das Speicher denn ein Stapel in der in sehen sie als Programmiererin als Programmierer nicht das intern aber in ein Stapel abgelegte Singer das es schon so Stapel bildet die Funktion Männer die Fusion die aufgerufene Funktion gehen die Funktion F aufgerufenwenn die vom zuerstbeendet istda?? wieder rausguckennicht wieder raus der Funktionzu weitund die Kommawenn die Fonds wenn die eine Fusion beendet istspringt er eben wieder rausdareindareinwenn die Fusion es beendet ist die Dame noch die auf dem staatlichen Fonds umgeben ist immer noch mein auf dem Stab sie können auch ist das das interessant ist die Bank dicken tauchen und her springen und sagen ob und wo ist denn ?? aufgerufen worden ihrdoppelklickenvon der ASF aufgerufen war das muss irgendwo noch wissen wenn die Funktion F beendet ist muss er wissen ?? hier weiter macht das Wasser tatsächlichendliche Doppelklicken zeigte ihmwurde der Aufruf war und hierbei minderwertigen?? zeigte ihm wurden die aufrufen und dessen ganze Visite dieser Entwicklungsumgebungsie können auch zurückverfolgenvon wo der Aufruf kam in diesem Stapeldas ist das wohl wieder verbessern Stapel sehenund nicht etwas kompliziertdanach warMisses ja weiter