Бүгдээрээ сайн байцгаана уу.
Энэ тэмдэглэлд би компьютерийн шинжлэх ухаанд график хадгалахад ашигладаг үндсэн өгөгдлийн бүтцийг жагсаахаар шийдсэн бөгөөд миний хувьд ямар нэгэн байдлаар "талсжсан" өөр хэд хэдэн бүтцийн талаар ярих болно.
За ингээд эхэлцгээе. Гэхдээ анхнаасаа биш - График гэж юу болох, тэдгээр нь юу болохыг бид бүгд аль хэдийн мэддэг болсон гэж би бодож байна (чиглүүлсэн, чиглүүлээгүй, жинтэй, жингүй, олон ирмэг ба гогцоотой эсвэл байхгүй).
За, явцгаая. "График хадгалах" өгөгдлийн бүтцийн ямар сонголтууд бидэнд байна вэ?
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-ийн оронд дахин ирмэгийн нийт жинг зааж өгч болно.
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] -ээс a[2i+1] хүртэл чиглүүлсэн гэж үзнэ. Энд ба доор: чиглүүлээгүй графикийн хувьд шаардлагатай бол оройг бүртгэх дарааллын шаардлагыг тавьж болно (жишээлбэл, түүнд оноогдсон тооноос бага утгатай орой нь нэгдүгээрт ордог).
C++ хэл дээр std::vektor ашиглан зэргэлдээх векторыг зааж өгөхийг зөвлөж байна, иймээс энэ өгөгдлийн бүтцийн нэр.
Тохиолдол (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], [2i+3]…) , энд a[2i+2] болон a[2i+3] нь харгалзах ирмэгийн шинж чанарыг тодорхойлно. Ирмэгүүдийн бүхэл жинтэй графикийн хувьд дараалал нь ерөнхийдөө төстэй байна (Ганц ялгаа нь шинж чанарууд нь ирмэгийн жинг дагаж, a[2i+3] ба a[2i+4] элементүүдээр тодорхойлогддог. , мөн ирмэг нь өөрөө 4 биш, харин 5 дараалсан тоогоор тодорхойлогдоно). Бүхэл бус ирмэгийн жинтэй графикийн хувьд шинж чанаруудыг жинлээгүй бүрэлдэхүүн хэсэг болгон бичиж болно.
Бүхэл тооны ирмэгийн жинтэй графикт ассоциатив зэргэлдээх массивыг ашиглахдаа утгын хувьд нэг тоо биш, харин ирмэгийн жингээс гадна шаардлагатай бусад бүх зүйлийг зааж өгсөн тоон массив (вектор) зааж өгөх боломжтой. онцлог. Үүний зэрэгцээ бүхэл бус туухайны хувьд таагүй байдал нь хөвөгч цэгийн дугаар бүхий тэмдгийг зааж өгөх шаардлагатай болно (тиймээ, энэ нь эвгүй, гэхдээ ийм олон тэмдэг байхгүй бол "Тэднийг хэтэрхий "зальтай" давхар болгож болохгүй, тэгвэл юу ч биш байж магадгүй). Энэ нь C++ дээр өргөтгөсөн ассоциатив зэргэлдээ массивуудыг дараах байдлаар тодорхойлж болно гэсэн үг юм: std::map , std::вектор> эсвэл std::map , std::вектор, үүнд "түлхүүр-утга-вектор"-ын эхний утга нь ирмэгийн жин байх ба дараа нь түүний шинж чанарын тоон тэмдэглэгээг байрлуулна.
Уран зохиол:
График ба алгоритмын тухай ерөнхийд нь:
1. Кормен, Томас Х., Лейзерсон, Чарльз I., Ривест, Рональд Л., Стейн, Клиффорд. Алгоритм: бүтээн байгуулалт, дүн шинжилгээ, 2-р хэвлэл: Транс. англи хэлнээс – М.: Уильямс хэвлэлийн газар, 2011 он.
2. Харари Фрэнк. Графикийн онол. М.: Мир, 1973 он.
Эдгээр ижил вектор ба ассоциатив массивын талаархи зохиогчийн тайлан:
3. Черноухов С.А. Зэргэлдээх вектор ба ассоциатив зэргэлдээх массив нь графикийг дүрслэх, хадгалах арга замууд / С.А.Черноухов. Зэргэлдээх вектор ба зэргэлдээ газрын зураг нь график дүрслэх өгөгдлийн бүтэц // “Шинэлэг бүтээн байгуулалтын үр дүнг хэрэгжүүлэх асуудал, түүнийг шийдвэрлэх арга зам” олон улсын шинжлэх ухаан, практикийн бага хурлын өгүүллийн түүвэр (Саратов, 14.09.2019 оны 2019-р сарын 65). – Стерлитамак: AMI, 69, х. XNUMX-XNUMX
Энэ сэдвээр хэрэгтэй онлайн эх сурвалжууд:
4.
5.
Эх сурвалж: www.habr.com