Számítógépes dokumentáció
Nem számít, hogy valaki rosszul jár,
talán jól néz ki.
Scott első törvénye (Alkalmazott Murfológia)
Felettünk elég figyelmet fordítottunk arra, hogy mátrixokkal és listákkal dolgozzunk, és ez nem véletlenül történik. A lista fogalmának még általánosabbá tétele érdekében egy többszörösen összekapcsolt lista definíciójához jutunk, amelyet a listán szereplő elemek tetszőleges számú mutató jelenléte jellemez. Meg lehet mondani, hogy minden egyes elemet tartalmaz annyi nem kapcsolódó listát, mivel rendelkezik mutatókkal. A többszörösen összekapcsolt listát "összefűzött" egyszerűen összekapcsolt listákkal nyerik, ezért az ilyen többszörösen összekapcsolt listákat varrják, vagy plexeket. Többszörösen összekapcsolt listák használatával szimulálhat egy adatstruktúrát, például egy hálózatot vagy grafikont. A hálózat egy speciális esete egy fa. Tekintse meg az adatszerkezeteknek a számítógép memóriájába történő bemutatásának lehetőségeit.
Network egy tuple G - (V, E), ahol V - egy véges csúcsok halmaza, E - ^ véges halmazát összekötő élek pár csúcsok sokasága V. két csúcsot u és v a több szomszédos V nevezett, ha van egy él a beállított E ( u, v) összekapcsolja ezeket a csúcsokat. A hálózat orientálható és irányítatlan. Ez attól függ, hogy a széleket (u, v) és (v, u) különböznek-e. Gyakorlati alkalmazásoknál gyakran a szélekhez vannak rendelve súlyok, vagyis néhány számérték. Ebben az esetben a hálózatot súlyozottnak nevezik. Minden v csúcs a hálózat több szomszédos csúcsok, azaz csúcsok, Uj (i = l..n), amelyekre jelenleg bordák (v, és :). Ez messze nem jelenti a hálózatra vonatkozó valamennyi definíciót, de a kiállításunk számára elegendő, hiszen célja az összeszerelő eszközeinek bemutatása különböző adatstruktúrákkal való együttműködésre. Ezért vegye fontolóra a hálózati memóriakártyák számítógépes memóriában történő ábrázolásának lehetőségét feldolgozásra alkalmas formában. Ezek közül a lehetőségek közül melyik a legjobban függ az adott feladattól. Nem fogjuk felbecsülni sem a megjelenítés hatékonyságát sem.
- A szomszédosság mátrixa. Az M csúcsú hálózatot MxM méretű mátrixként lehet megjeleníteni. Feltéve, hogy a csúcsokat v. v2. vm, az ay = 1 mátrix értéke azt jelzi, hogy létezik egy él a v és v csúcsok között. Más szavakkal ezek a csúcsok szomszédosak. Egy orientált hálózathoz a szomszédsági mátrix szimmetrikus lesz.
- Az incidencia mátrix. A mátrix ezen ábrázoláson alapul, de a sorok a csúcsok és a szélek oszlopainak felelnek meg (2.15. Ábra). Az ábrán látható, hogy minden oszlop sorban két egységet tartalmaz, és nincsenek azonos oszlopok a mátrixban.
Ábra. 2.15. A hálózat ábrázolása az incidencia mátrix segítségével
Ábra. 2.16. Hálózat képviselete összefüggő vektorokkal
Vonalkódok vektorai. Ez a változat a mátrix is (lásd a 2.16. Ábrát). Minden csúcs számozott. Minden csúcs a mátrix egy sorának felel meg, amelyben felsoroljuk az adott szomszédos csúcsok számát.
Példaként tekintse át a szkenner töredékét a valós számok felismerésére az assembler direktívákban dd, dq, dt. A számok szintaxis diagram formájában történő leírására vonatkozó szabályt a tankönyvben a "Coprocessor architektúrája és programozása" című lecke tartalmazza. Ez megfelel az alább látható szabályos kifejezésnek és a determinisztikus véges állapotú gépnek (2.17. Ábra):
Ábra. 2.17. A valós számok leírásának nyelve a direktívában dd és ennek megfelelő determinisztikus véges állapotú gép
A program két részből áll:
- listaépítés - itt egy többszörösen összekapcsolt listát készít egy adott szabályos kifejezéssel;
- feldolgozza a beviteli karakterláncot, hogy lássa, érvényes valódi bejegyzést tartalmaz-e a telepítési irányelvekben dd, dq, dt.
Amikor végrehajtja az első elemet, felmerül a probléma: hogyan lehet egy többszörösen összekapcsolt lista elemét megadni, ha általában a lista különböző elemei különböző számú linket tartalmaznak? Amint az ábrán látható, a különböző államoknak különböző száma van. Különböző megközelítéseket javasolhat e linkek szoftvervégrehajtásának megválasztására. A következőket választjuk. Az egyes elemek kimenő linkjeit egyszerűen összekapcsolt listán rendezzük. Ebben az esetben a szorzással összekapcsolt lista két elemet tartalmaz:
- Leírják az automaták állapotát - kétszeresen összekapcsolt listára vannak rendezve;
- A következő beviteli szimbólumtól függően az ilyen állapotból más államokra mutató linkeket vagy átmenetet írnak le - ezek a kapcsolatok az egyes államok számára egylépcsős listákként vannak rendezve.
Kétszeresen összekapcsolt lista nemlineáris elrendezése esetén számos probléma merül fel. Néhányuk eltávolításra kerül egy statikus módszerrel, amely egy listát készít, ami a legjobb a véges automata számára. Ha szükséges, az alábbi struktúrák felhasználásával az olvasó önállóan leírhat ilyen listát az adatszegmensében. Ezt követően a véges állapotú gépet megvalósító nemlineáris lista dinamikus, összetettebb verzióját fogjuk foglalkozni. Emlékezzünk arra, hogy feladata a lexéma felismerése - a hexadecimális szám leírása az assembler irányelvekben dd, dq, dt. Egy nem lineáris többszörösen összekapcsolt lista létrehozásához számos makrót fejlesztünk ki. Segítségükkel az építkezés két szakaszban zajlik:
- egy véges automata állapotainak kétszeresen összekapcsolt listáját létrehozva;
- egyszerűen összekapcsolt átmeneti listák létrehozása.
Az alábbi programban egy véges automata állapotainak kétszeresen összekapcsolt listája azonnal létrejön. Továbbá, minden olyan állapot esetében, ahol egy automatát találhatunk, az átmenetek egy-egy egyeztetési listáját állítjuk össze. A létrehozás során egyszerűen csatlakoztatott átmeneti listák kapcsolódnak a véges automatika kétszeresen csatlakoztatott állapotlistájának megfelelő elemeihez. A program végén a karakterlánc elismeri annak tagságát, hogy a halmazban szereplő karakterláncokat a fent megadott valós szám rendszeres kifejezése írja le.
Egy egyszerűen csatlakoztatott átmeneti lista létrehozása az állami gép állapotára vonatkozóan
Az átmeneti listaelem és a makró struktúráját is leírjuk az elem létrehozásához. A sajátosság az, hogy az államok listájával ellentétben a makró nem épít ki az egész listát, csak az egyik elemét. Egy másik jellemzője az, hogy a mutató a kapott láncolt lista egy hivatkozás az utolsó kiválasztott elemet a listából, és azt, hogy ez a része a meglévő állami egy elem kötődését a listát átmenetek, ami igazán nem számít sokat.
Tulajdonképpen prg02_ll.asm program épít és inicializálja egy olyan gép felismerni a zsetonok valós szám az irányelvekben dd, dq és dt, elég nagy.