Documentația calculatorului

Nu contează că cineva merge prost,
poate arata bine.
Prima lege a lui Scott (Murfologie aplicată)

Deasupra am acordat suficientă atenție lucrului cu matrice și liste, iar acest lucru nu se întâmplă din întâmplare. Chiar mai generalizând noțiunea de listă, ajungem la definiția unei liste multiple, care se caracterizează prin prezența unui număr arbitrar de indicatori către alte elemente ale listei. Se poate spune că fiecare element particular este inclus în cât mai multe liste neconectate cu indicii. O listă multiplă conectată este obținută prin listele "cusute" pur și simplu conectate, prin urmare, astfel de liste multiplicate conectate sunt numite cusute sau plexe. Utilizând liste multiple, puteți simula o structură de date, cum ar fi o rețea sau un grafic. Un caz special al rețelei este un copac. Luați în considerare opțiunile de prezentare a acestor structuri de date în memoria computerului.






Rețeaua este un G tuple - (V, E), unde V - un set finit de noduri, E - ^ set finit de margini care leagă perechile de noduri ale unui V. pluralitate Două vârfuri u și v dintr-o pluralitate de V adiacente numite, dacă există un avantaj în setul E ( u, v) conectarea acestor vârfuri. Rețeaua poate fi orientată și nedirecționată. Depinde dacă aripioarele sunt luate în considerare (u, v) și (v, u) diferit. În aplicațiile practice, de multe ori atribuite greutatea marginilor, care este, unele valori numerice. În acest caz, rețeaua este numită ponderată. Pentru fiecare vârf v în rețea are o multitudine de vârfuri adiacente, adică vârfuri astfel Uj (i = l..n), pentru care există nervuri (v și :). Acest lucru este nu toate definițiile referitoare la rețea, dar pentru discuția noastră de suficient, deoarece scopul său - ilustrare a ansamblului de instrumente pentru lucrul cu diferite structuri de date. Prin urmare, luați în considerare opțiunile de reprezentare a rețelelor în memoria calculatorului într-o formă potrivită pentru procesare. Care dintre aceste opțiuni este cea mai bună depinde de sarcina specifică. De asemenea, nu vom evalua eficiența oricărui tip de prezentare.

  • Matricea de contiguitate. O rețea care are vârfuri M poate fi reprezentată ca o matrice cu dimensiunea MxM. Cu condiția ca nodurile să fie etichetate v. v2. vm, valoarea matricei ay = 1 indică existența unei margini între vârfurile v și v. Cu alte cuvinte, aceste noduri sunt adiacente. Pentru o rețea orientată, matricea adjacency va fi simetrică.
  • Matricea incidenței. Matricea se bazează, de asemenea, pe această reprezentare, dar rândurile din ea corespund vârfurilor și coloanelor marginilor (Figura 2.15). Se vede din figură că fiecare coloană conține două unități în rânduri și nu există coloane identice în matrice.

Fig. 2.15. Reprezentarea rețelei prin matricea incidenței

Fig. 2.16. Reprezentarea unei rețele de vectori de contiguitate







Vectors of contiguity. Această variantă a reprezentării este, de asemenea, matrice (vezi Figura 2.16). Toate nodurile sunt numerotate. Fiecare vârf corespunde unui rând al matricei, în care sunt enumerate numerele vârfurilor adiacente datei.
De exemplu, ia în considerare fragmentul scanerului pentru recunoașterea numerelor reale în directivele asamblare dd, dq, dt. Regula de descriere a acestor numere sub forma unei diagrame de sintaxă este dată în lecția 19 "Arhitectură și programare a coprocesorului" din manual. Aceasta corespunde expresiei regulate prezentate mai jos și mașinii deterministe finite (Figura 2.17):

Fig. 2.17. Gramatica limbii descrierii numerelor reale din directiva dd și a mașinii deterministe determinate finite

Programul va cuprinde două părți:

  • construirea unei liste - aici construiți o listă multiplă conectată printr-o expresie regulată dată;
  • procesarea șirului de intrare pentru a vedea dacă este o intrare numerică reală validă în directivele de asamblare dd, dq, dt.

Atunci când primul element este executat, apare problema - cum să specificați elementul unei liste multiple, dacă, în general, diferitele elemente ale listei pot avea un număr diferit de linkuri? După cum se arată în figură, diferite state au un număr diferit de conexiuni. Puteți sugera diferite abordări în alegerea implementării software a acestor linkuri. Alegem următoarele. Organizăm toate legăturile de ieșire ale fiecărui element într-o listă pur și simplu conectată. În acest caz, lista multiplă va conține elemente de două tipuri:

  • Ele descriu stările automatului - ele sunt organizate într-o listă dublu conectată;
  • Acestea descriu legături sau tranziții de la această stare la alte state în funcție de simbolul de intrare următor - aceste linkuri sunt organizate ca liste unice pentru fiecare stat.

În cazul unei organizări neliniare a unei liste dublu legate, construcția ei prezintă o serie de probleme. Unele dintre ele sunt eliminate prin metoda statică de construire a unei liste, care este cea mai bună pentru automatele finite. Dacă este necesar, utilizând structurile de mai jos, cititorul poate descrie independent o astfel de listă în segmentul său de date. Apoi, vom aborda o versiune dinamică și mai complexă a organizării unei liste neliniare care implementează mașina finită de stat. Amintiți-vă că sarcina sa este de a recunoaște lexeme - o descriere a numărului hexazecimal în directivele de asamblare dd, dq, dt. Pentru a construi o listă neliniară multiplă conectată, vom dezvolta un număr de macrocomenzi. Cu ajutorul lor, construcția se desfășoară în două etape:

  • crearea unei liste dublate de stări a unui automat finit;
  • crearea de liste de tranziții pur și simplu conectate.

În programul de mai jos, este construită imediat o listă a stărilor automatelor finite conectate dublu. Mai mult, pentru fiecare stare în care poate fi localizat un automat, sunt construite listele de corespondență unu-la-unu cu tranziții. Pe măsură ce sunt create, listele de tranziție pur și simplu conectate sunt conectate la elementele corespondente ale listei de stare dublu conectate a automatului finit. La sfârșitul programului, șirul este recunoscut pentru apartenența sa în setul de șiruri descrise de expresia regulată pentru numărul real dat mai sus.

Crearea unei liste simple de tranziții pentru starea mașinii de stat

De asemenea, descriem structura elementului listei de tranziție și macro pentru a crea acest element. Particularitatea este că, în contrast cu statul construiește o listă a macro nu întreaga listă, dar numai unul din elementele sale. O altă caracteristică este aceea că un pointer la lista legată care rezultă este o referire la ultimul element selectat în listă și este la această parte a statului existent a unui element de legare la lista sa de tranziții care face într-adevăr nu contează prea mult.

De fapt, programul prg02_ll.asm construiește și inițializează o mașină de stat pentru a recunoaște semnele unui număr real în directivele dd, DQ și dt, este destul de mare.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: