Ҳама хонед
Дар ин ёддошт, ман тасмим гирифтам, ки сохторҳои асосии маълумотро, ки барои нигоҳ доштани графикҳо дар илми информатика истифода мешаванд, номбар кунам ва ман инчунин дар бораи якчанд чунин сохторҳое сӯҳбат хоҳам кард, ки барои ман "кристалл шудаанд".
Пас, биёед оғоз кунем. Аммо на аз аввал - ман фикр мекунам, ки ҳамаи мо аллакай медонем, ки график чист ва онҳо чӣ гунаанд (роҳнамоӣ, бесамар, вазннок, вазннашуда, бо кунҷҳо ва ҳалқаҳои сершумор ё бидуни он).
Пас, биёед. Кадом имконоти сохторҳои додаҳо барои "нигоҳдории графикӣ" мо дорем?
1. Сохторҳои маълумотҳои матритсавӣ
1.1 Матритсаи ҳамсоягӣ. Матритсаи ҳамсоя матритсаест, ки дар он сарлавҳаҳои сатр ва сутун ба рақамҳои қуллаҳои график мувофиқат мекунанд ва арзиши ҳар як унсури он a(i,j) бо мавҷудият ё набудани кунҷҳо дар байни қуллаҳо муайян карда мешавад. i ва j (равшан аст, ки барои графики беасос чунин матритса симметрӣ хоҳад буд, ё мо метавонем розӣ шавем, ки мо ҳама арзишҳоро танҳо дар болои диагонали асосӣ нигоҳ медорем). Барои графикҳои вазннашуда a(i,j)-ро аз рӯи шумораи кунҷҳо аз i то j (агар чунин канор мавҷуд набошад, a(i,j)= 0) ва барои графикҳои вазндор низ аз рӯи вазн муқаррар кардан мумкин аст. (вазни умумии) кунҷҳои зикршуда.
1.2 Матритсаи ҳодисаҳо. Дар ин ҳолат, графики мо низ дар ҷадвал нигоҳ дошта мешавад, ки дар он чун қоида, рақамҳои сатр ба рақамҳои қуллаҳои он ва рақамҳои сутун ба кунҷҳои қаблан рақамгузорӣшуда мувофиқат мекунанд. Агар қулла ва канор ба ҳамдигар дучор шаванд, он гоҳ дар ячейкаи мувофиқ арзиши ғайрисифр навишта мешавад (барои графикҳои беасос, 1, агар қулла ва канори канори он афтад, 1 навишта мешавад, барои графикҳои нигаронидашуда - “1” агар канор "баромад" аз қулла ва "-1" агар ба он "дар барояд" (дар хотир доштан ба қадри кофӣ осон аст, зеро аломати "минус" низ ба рақами "-1" "дохил шудааст")). Барои графикҳои вазндор, боз ба ҷои 1 ва -XNUMX, шумо метавонед вазни умумии канорро муайян кунед.
2. Сохторҳои маълумотҳои номбаркунӣ
2.1 Рӯйхати ҳамсоягӣ. Хуб, дар ин ҷо ҳама чиз оддӣ ба назар мерасад. Ҳар як қуллаи график метавонад дар маҷмӯъ бо ҳама гуна сохтори номбаркунӣ (рӯйхат, вектор, массив, ...) алоқаманд бошад, ки рақамҳои ҳама қуллаҳои шафати додашударо нигоҳ медорад. Барои графикҳои равонашуда, мо ба чунин рӯйхат танҳо он қуллаҳоеро илова мекунем, ки ба онҳо аз қуллаи хусусият канори “мувофиқ” мавҷуд аст. Барои графикҳои вазннок татбиқи онҳо мураккабтар хоҳад буд.
2.2 Рӯйхати қабурғаҳо. Сохтори хеле маъмули маълумот. Рӯйхати кунҷҳо, тавре ки капитан Обвиуснесс ба мо мегӯяд, воқеан як рӯйхати кунҷҳои график аст, ки ҳар кадоми онҳо бо қуллаи ибтидоӣ, қуллаи хотимавӣ муайян карда мешавад (барои графикҳои беасос тартиб дар ин ҷо муҳим нест, гарчанде ки барои муттаҳидшавӣ шумо метавонед қоидаҳои гуногунро истифода баред, масалан, муайян кардани қуллаҳо бо тартиби афзоиш) ва вазн (танҳо барои графикҳои вазншуда).
Шумо метавонед ба рӯйхатҳои матритсаи дар боло номбаршуда муфассалтар назар кунед (ва бо тасвирҳо), масалан, .
2.3 Массиви ҳамсоягӣ. На сохтори маъмултарин. Дар асл, он як шакли "бастабандӣ"-и рӯйхатҳои ҳамсоягӣ ба як сохтори рӯйхат (массив, вектор) мебошад. Элементҳои аввалини n (мувофиқи шумораи қуллаҳои график) чунин массив дорои индексҳои ибтидоии ҳамон массив мебошанд, ки аз онҳо ҳама қуллаҳои ҳамшафати додашуда дар як саф навишта мешаванд.
Дар ин ҷо ман шарҳи фаҳмотаринро (барои худам) пайдо кардам:
3. Вектори ҳамсоягӣ ва массиви ҳамсоягии ассотсиативӣ
Маълум шуд, ки муаллифи ин сатрҳо, ки барномасози касбӣ набуда, ба таври даврӣ бо графикҳо сару кор дошт, аксар вақт бо рӯйхатҳои канорҳо сару кор дошт. Дар ҳақиқат, он қулай аст, агар график ҳалқаҳо ва кунҷҳои сершумор дошта бошад. Ҳамин тариқ, ҳангоми таҳияи рӯйхатҳои классикии кунҷҳо ман пешниҳод мекунам, ки ба “инкишоф/шоҳида/модификатсия/мутатсия”-и онҳо, аз ҷумла: вектори ҳамсоягӣ ва массиви ҳамсоягии ассотсиативӣ диққат диҳам.
3.1 Вектори ҳамсоягӣ
Ҳолати (a1): графики вазннашуда
Мо вектори ҳамсояро барои графики вазннашуда маҷмӯи тартибёфтаи шумораи ҷуфти бутун (a[2i], a[2i+1],..., ки дар он i c 0 рақамгузорӣ шудааст) меномем, ки дар он ҳар як ҷуфт ададҳо a[2i] аст, a[2i+1 ] канори графикро байни қуллаҳои a[2i] ва a[2i+1] муайян мекунад.
Ин формати сабт маълумотро дар бораи равона кардани график дар бар намегирад (ҳарду интихоб имконпазир аст). Ҳангоми истифодаи формати диграф, канор аз a[2i] ба [2i+1] равона карда мешавад. Дар ин ҷо ва дар поён: барои графикҳои бесамар, агар лозим бошад, талаботро оид ба тартиби сабти қуллаҳо татбиқ кардан мумкин аст (масалан, қуллаи дорои арзиши камтари рақами ба он таъиншуда дар ҷои аввал меояд).
Дар C++ тавсия дода мешавад, ки вектори ҳамсоягӣ бо истифода аз std::vector муайян карда шавад, бинобар ин, ин сохтори додаҳо номида мешавад.
Ҳолати (a2): графики вазннашуда, вазнҳои канорӣ адад мебошанд
Дар муқоиса бо ҳолати (a1) мо вектори ҳамсояро барои графики вазндор бо вазнҳои канори бутун маҷмӯи тартибдодашуда (массиви динамикӣ) ададҳо (a[3i], a[3i+1], a[3i+2], ..., ки дар он i рақамгузорӣ шудааст c 0), ки ҳар як "сегона"-и ададҳои a[3i], a[3i+1], a[3i+2] канори графикро байни қуллаҳои рақами a[3i] муайян мекунад. ва a[3i+1], мутаносибан, ва арзиши a [3i+2] вазни ин канор аст. Чунин график инчунин метавонад равона карда шавад ё не.
Ҳолати (б): графики вазннашуда, вазнҳои канори ғайри бутун
Азбаски дар як массив (вектор) нигоҳ доштани элементҳои гетерогенӣ ғайриимкон аст, масалан, татбиқи зерин имконпазир аст. Графика дар як ҷуфт векторҳо нигоҳ дошта мешавад, ки дар он вектори аввал вектори ҳамсоягии график аст, бидуни муайян кардани вазнҳо ва вектори дуюм вазнҳои мувофиқро дар бар мегирад (иҷрои эҳтимолӣ барои C++: std::pair) ). Ҳамин тариқ, барои каноре, ки бо ҷуфти қуллаҳои зери индексҳои 2i, 2i+1 вектори якум муайян карда шудааст, вазн ба унсури зери индекси i вектори дуюм баробар хоҳад буд.
Хуб, ин барои чӣ лозим аст?
Хуб, муаллифи ин сатрҳо онро барои ҳалли як қатор масъалаҳо хеле муфид донист. Хуб, аз нуқтаи назари расмӣ, бартариҳои зерин хоҳанд буд:
- Вектори ҳамсоягӣ мисли ҳама гуна сохтори дигари "рӯйхатӣ" хеле зич буда, нисбат ба матритсаи ҳамсоягӣ (барои графикҳои камёфт) камтар хотираро ишғол мекунад ва татбиқи нисбатан осон аст.
- Қуллаҳои графикро аслан бо рақамҳои манфӣ низ метавон қайд кард. Чӣ мешавад, агар ин гуна «таҳриф» лозим бошад?
- Графикҳо метавонанд кунҷҳои сершумор ва ҳалқаҳои гуногун дошта бошанд, ки вазнҳои гуногун доранд (мусбат, манфӣ, ҳатто сифр). Дар ин ҷо ягон маҳдудият вуҷуд надорад.
- Шумо инчунин метавонед хосиятҳои гуногунро ба кунҷҳо таъин кунед - аммо барои маълумоти бештар дар бораи он, ба бахши 4 нигаред.
Бо вуҷуди ин, бояд эътироф кард, ки ин "рӯйхат" дастрасии зуд ба канорро надорад. Ва дар ин ҷо массиви ҳамсоягӣ ба наҷот меояд, ки дар поён муҳокима карда мешавад.
3.2 Массиви ҳамсоягии ассотсиативӣ
Пас, агар дастрасӣ ба як канори мушаххас, вазн ва дигар хосиятҳои он барои мо муҳим бошад ва талаботи хотира ба мо имкон надиҳад, ки матритсаи ҳамсояро истифода барем, пас биёед дар бораи он фикр кунем, ки чӣ гуна мо вектори ҳамсояро барои ҳалли ин масъала иваз карда метавонем. Ҳамин тавр, калид канори график аст, ки онро ҳамчун ҷуфти ададҳои фармоишӣ муайян кардан мумкин аст. Ин ба чӣ монанд аст? Оё он калид дар массиви ассотсиативӣ нест? Ва агар ин тавр бошад, чаро мо онро амалӣ намекунем? Биёед массиви ассотсиативӣ дошта бошем, ки дар он ҳар як калид - як ҷуфт ададҳои фармоишӣ - бо арзиш - адад ё рақами воқеӣ, ки вазни канори онро муайян мекунад, алоқаманд хоҳад буд. Дар C++ тавсия дода мешавад, ки ин сохтор дар асоси контейнери std::map (std::map) амалӣ карда шавад. , int> ё std::map , double>), ё std::multimap, агар кунҷҳои сершумор интизор шаванд. Хуб, мо сохтори нигоҳдории графикҳо дорем, ки нисбат ба сохторҳои “матритсавӣ” хотираи камтарро ишғол мекунанд, метавонанд графикҳоро бо ҳалқаҳо ва кунҷҳои сершумор муайян кунанд ва ҳатто барои манфии рақамҳои қуллаҳо талаботи қатъӣ надоранд (ман намедонам) ки ин ба кй лозим аст, вале ба хар хол).
4. Сохторҳои маълумот пуранд, аммо чизе намерасад
Ва ин дуруст аст: ҳангоми ҳалли як қатор мушкилот ба мо лозим меояд, ки баъзе хусусиятҳоро ба кунҷҳои график таъин кунем ва мувофиқан онҳоро захира кунем. Агар имкон бошад, ки ин хусусиятҳоро ба ададҳои бутун кам кунед, пас бо истифода аз версияҳои васеъи вектори ҳамсоягӣ ва массиви ҳамсоягии ассотсиативӣ чунин “графикҳоро бо хусусиятҳои иловагӣ” нигоҳ доштан мумкин аст.
Пас, биёед як графики бевазн дошта бошем, ки барои ҳар як канори он, масалан, 2 хусусияти иловагии бо ададҳои бутун нишондодашударо нигоҳ доштан лозим аст. Дар ин ҳолат метавон вектори ҳамсоягии онро ҳамчун маҷмӯи тартибдодашуда на аз “ҷуфтҳо”, балки аз “квартетҳо”-и ададҳои бутун (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , ки дар он a[2i+2] ва a[2i+3] хусусиятҳои канори мувофиқро муайян мекунанд. Барои график бо вазнҳои бутуни кунҷҳо, тартиб умуман шабеҳ аст (ягона фарқият дар он аст, ки атрибутҳо ба вазни канор пайравӣ мекунанд ва бо унсурҳои a[2i+3] ва a[2i+4] муайян карда мешаванд. , ва худи канори он на 4, балки 5 рақами фармоишӣ муайян карда мешавад). Ва барои график бо вазнҳои канори ғайри бутун, хусусиятҳоро ба ҷузъи бевазнии он навиштан мумкин аст.
Ҳангоми истифодаи массиви ҳамсоягии ассотсиативӣ барои графикҳо бо вазнҳои канори бутун, мумкин аст ҳамчун арзиш на як адад, балки массиви (вектори) ададҳо, ки ба ғайр аз вазни канор, тамоми дигар зарурии онро муайян мекунанд, муайян кардан мумкин аст. Вижагиҳо. Дар айни замон, як нороҳатӣ барои ҳолати вазнҳои ғайрибутунӣ зарурати нишон додани аломат бо рақами нуқтаи шинокунанда хоҳад буд (бале, ин нороҳатӣ аст, аммо агар ин гуна аломатҳо он қадар зиёд набошанд ва агар шумо 'Онҳоро аз ҳад зиёд дучандон "мушкил" нагузоред, пас он метавонад ҳеҷ чиз набошад) . Ин маънои онро дорад, ки дар C++ массивҳои ҳамсоягии васеъшударо ба таври зерин муайян кардан мумкин аст: std::map , std::вектор> ё std::харитаи , std::vektor, ки дар он арзиши аввал дар "калид-қимат-вектор" вазни канор хоҳад буд ва сипас нишондодҳои ададии характеристикаҳои он ҷойгир мешаванд.
Таърихи адабиёт
Дар бораи графикҳо ва алгоритмҳо дар маҷмӯъ:
1. Кормен, Томас Ҳ., Лейзерсон, Чарлз I., Ривест, Роналд Л., Стейн, Клиффорд. Алгоритмҳо: сохтмон ва таҳлил, нашри 2: Trans. аз англисӣ – М.: Нашриёти Вилямс, 2011.
2. Ҳарари Франк. Назарияи графикӣ. М.: Мир, 1973.
Гузориши муаллиф дар бораи ҳамин вектор ва массиви ассотсиативии ҳамсоягӣ:
3. Черноухов С.А. Вектори ҳамсоягӣ ва массиви ҳамсоягии ассотсиативӣ ҳамчун роҳҳои муаррифӣ ва нигоҳдории графикҳо / С.А. Черноухов. Вектори ҳамсоягӣ ва харитаи ҳамсоягӣ ҳамчун сохторҳои додаҳо барои муаррифии график // Маҷмӯаи мақолаҳои Конфронси байналмилалии илмӣ-амалии «Мушкилоти татбиқи натиҷаҳои таҳаввулоти инноватсионӣ ва роҳҳои ҳалли онҳо» (Саратов, 14.09.2019 сентябри 2019). – Стерлитамак: АМИ, 65, саҳ. 69-XNUMX
Сарчашмаҳои муфиди онлайн дар ин мавзӯъ:
4.
5.
Манбаъ: will.com