Algoritmni loyihalash va tahlil qilishga kirish

8. Matematik abstraktsiya usullari
Reja:
1. Ma'lumotlarning mavhum turi (ADT)
2. ADT namunalari
3. Shablonlar bilan katta o'xshashliklar
Abstraktsiya
Abstraktlik - bu ahamiyatsiz xususiyatlarni ko'rib chiqishdan tashqari, ob'ektning muhim xususiyatlari to'plamini ajratib ko'rsatish usuli. Shunga ko'ra, abstraktsiya bu kabi barcha xususiyatlarning to'plamidir.
Ma'lumotlar turi (ADT) - bu turdagi elementlar bilan ishlash uchun ma'lum funktsiyalar to'plamini, shuningdek maxsus funktsiyalar yordamida ushbu turdagi elementlarni yaratish qobiliyatini ta'minlaydigan ma'lumotlar turi. Ushbu turdagi barcha ichki tuzilish dasturiy ta'minot ishlab chiqaruvchisidan yashiringan - bu abstraktsiyaning mohiyati. Ma'lumotli ma'lumotlar turi, uning qiymatlari bo'yicha ishlash uchun tipning aniq bajarilishidan mustaqil funktsiyalar to'plamini belgilaydi. ADTlarning aniq tatbiq etilishi ma'lumotlar strukturasi deb ataladi.
Dasturlashda abstrakt ma'lumotlar turlari odatda tegishli turdagi amallarni yashiradigan interfeyslar sifatida ifodalanadi. Dasturchilar mavhum ma'lumotlar turlari bilan faqat o'z interfeyslari orqali ishlaydi, chunki kelajakda dastur o'zgarishi mumkin. Ushbu yondashuv ob'ektga yo'naltirilgan dasturlashda inkapsulyatsiya tamoyiliga mos keladi. Ushbu texnikaning kuchli tomoni - bu dasturni yashirish. Faqatgina interfeys tashqarida nashr etilgandan so'ng, ma'lumotlar tuzilishi ushbu interfeysni qo'llab-quvvatlagan ekan, mavhum ma'lumotlar turining berilgan tuzilishi bilan ishlaydigan barcha dasturlar ishlashni davom ettiradi. Ma'lumotlar tuzilmalarini ishlab chiquvchilar tashqi interfeys va funktsiyalar semantikasini o'zgartirmasdan, algoritmlarni tezligi, ishonchliligi va ishlatilgan xotirasi jihatidan takomillashtirib, tatbiq etishni bosqichma-bosqich takomillashtirishga harakat qilishadi. Ma'lumotlarning mavhum turlari va mavhum turlarini amalga oshiruvchi ma'lumotlar tuzilmalari o'rtasidagi farqni quyidagi misolda ko'rsatish mumkin. Ma'lumotlar turlarining mavhum ro'yxati massiv yoki chiziqli ro'yxat yordamida har xil dinamik xotirani taqsimlash usullari yordamida amalga oshirilishi mumkin. Biroq, har bir dastur barcha dasturlar uchun bir xil (tezlikda emas, balki) bajarishi kerak bo'lgan bir xil funktsiyalar to'plamini belgilaydi.
Ma'lumotlarning mavhum turlari dasturiy mahsulotlarning modulliligiga erishishga va alohida modulning bir-birining o'rnini bosadigan bir nechta muqobil dasturlariga ega bo'lishga imkon beradi. • Ro'yxat
• Stack
• Navbat
• Assotsiativ massiv
• navbatdagi navbat
Sinf shablonlari: dinamik massiv - Avvalgi misolda bo'lgani kabi, boshlang'ich uchun Paskal bilan o'xshashlik namunasi yordamida sinf shablonlari mexanizmini tahlil qilaylik. Paskalda massiv turini belgilashda dasturchi o'zboshimchalik bilan indekslar diapazonini tanlashi mumkin, bu ayniqsa har xil matematik masalalarni amalga oshirishda qulay bo'ladi. Xususan, aksariyat matematik ob'ektlarda elementlar birdan elementlar sonigacha indekslanadi. Masalan, N o'lchovning haqiqiy vektorini aniqlaylik:
vektor = massiv [1..N] haqiqiy;
C va C ++ da massivlar faqat noldan indekslanadi. Shuning uchun, bittadan indeksatsiya qilish uchun ishlab chiqilgan algoritmni amalga oshirishda dastur har doim massiv elementiga kirishda indeksni bittaga kamaytirishni unutmasligi kerak. Bunga massivga qo'shimcha element qo'shish orqali yo'l qo'ymaslik mumkin (massivda (N + 1) elementlar mavjud, 0 indeksli element ishlatilmaydi).
Biroq, ko'p hollarda bu usul qo'llanilmaydi (ko'p qatorli matritsa; masalan, 5 yoki -5 bilan indekslash; bitta element juda ko'p xotirani egallaydi).
Bu erda parametrlangan turlar (yoki sinf shablonlari) kiradi. Bizning holatda, parametrlar qator elementining bitta parametr turi va pastki va yuqori satrni belgilaydigan ikkita parametr-barqaror bo'ladi:
shablon
sinf Array {
xususiy:
// Element berilgan: T tipidagi (H - L + 1) elementlar to'plami
T elementlari [H - L + 1];
jamoat:
// Ushbu sinfni massiv sifatida ishlatish uchun indekslash operatsiyasini haddan tashqari yuklang.
// Amaliyot Elements massivi elementiga doimiy o'qimaganlikni qaytaradi va o'qishga ham imkon beradi
// ma'lumotlarni o'zgartirish. Bunday holda, asl indeks mos keladigan C ++ indeksini olish uchun o'rnatiladi.
T va operator [] (int indeks)
{
return Elements [indeks - L];
}
// Shuningdek, ushbu sinf uchun nusxa ko'chirish konstruktori va tayinlash jarayoni to'g'ri ishlaydi,
// sukut bo'yicha kompilyator tomonidan belgilanadi.
};
Funktsiya va sinf shablonlari o'rtasidagi asosiy o'xshashlik shablon uchun parametr turlarini tanlashdir. Farqi shundaki, aniq (ya'ni shablon parametrlarining qiymatlarini hisobga olgan holda) funktsiyalar kompilyator tomonidan avtomatik ravishda hosil qilinadi (ya'ni, kompilyator parametr qiymatlarini aniqlaydi) va siz kerakli parametr qiymatlarini belgilash orqali aniq sinflarni aniqlaysiz. Sinf shablonining parametrlari shablon nomidan keyin burchakli qavsda ko'rsatiladi.
Endi Array sinfining shabloniga ega bo'lsak, vektor turini yuqoridagi paskalda aniqlangan tarzda aniqlay olamiz:
typedef Array Vektor;
// Va uni paskal kabi ishlating:
A, b, c vektor;
uchun (int i = 1; i <= N; i ++) {
a [i] = i * 0,5; // indekslar bo'yicha kirish
b [i] = a [i] + i; // 1dan Ngacha
}
c = b; // topshiriq
Sinf shablonlaridan foydalanishda shablonga turli xil parametrlarni qo'llash yangi turni yaratishini unutmaslik kerak. Shuning uchun murakkab sinf shablonlaridan haddan tashqari foydalanish etarli bo'lmagan katta bajariladigan faylga olib kelishi mumkin. Masalan:
// Quyidagi o'zgaruvchilarni aniqlang:
Array a;
Array b;
Array c;
Array d;
// Quyidagi aniq sinflar aniqlanadi:
Array sinfi {
xususiy:
int elementlari [N - 1 + 1];
public:
int& operator [](int index) { return Elements[index - 1]; }
};
class Array {
private:
int Elements[N - 0 + 1];
public:
int& operator [](int index) { return Elements[index - 0]; }
};
class Array {
private:
char Elements[5 - -5 + 1];
public:
char& operator [](int index) { return Elements[index - -5]; }
};
class Array {
private:
float Elements[5 - -5 + 1];
public:
float& operator [](int index) { return Elements[index - -5]; }
};
Shuni ham ta'kidlash joizki, Paskal sizga massiv elementlariga kirishda indekslarning to'g'riligini tekshirishga imkon beradi. C va C ++ yo'q. Ammo, agar kerak bo'lsa, buni oldindan protsessor vositalari yordamida osonlikcha amalga oshirish mumkin.Standart kutubxonada dastur ishlab chiqish bosqichida xatolarni aniqlash uchun ishlatiladigan assert makrosini belgilaydigan "assert.h" nomli fayl mavjud. Ibratli hujjatning yagona argumenti bu shart (ifoda) bo'lib, uni keyinchalik xatosiz dastur ishlashi uchun bajarish kerak. Dastlabki protsessor tomonidan dastlabki matnni qayta ishlagandan so'ng, ushbu holatni tekshiradigan so'l o'rniga kod qo'yiladi. Agar shart bajarilmasa (ya'ni uni belgilaydigan ifoda qiymati nolga teng bo'lsa), unda xato xabari bosiladi va abort () funktsiyasini chaqirish orqali dastur g'ayritabiiy ravishda tugaydi.
Tasdiq makrosi yordamida Array klassi shablonini o'zgartiramiz, ya'ni. indekslarni tekshirish uchun:
#include
...
template
class Array {
...
T& operator [](int index)
{
assert(L <= index && index <= H);
return Elements[index - L];
}
};

Shubhasiz, ushbu tekshiruv dastur hajmini ham, ishlash vaqtini ham oshiradi. Ya'ni, bu faqat rivojlanish bosqichida amal qiladi. Paskalda u kompilyator sozlamalarida o'chirilgan. C va C ++ da yana qayta ishlash vositalarini ishlatishingiz kerak bo'ladi. Agar "assert.h" ni yoqishdan oldin NDEBUG makrosini aniqlasangiz, assert makrosi bo'sh deb belgilanadi (uning ta'rifida shartli kompilyatsiya ishlatiladi). T. haqida. dasturdagi o'z o'rnida oldindan protsessor hech qanday kod kiritmaydi va tekshirishlar "o'chiriladi". Endi sinf shablonlari va assert makrosidan foydalanishning asosiy nuqtalari ko'rib chiqilganligi sababli siz sinf shablonini yozishga o'tishingiz mumkin. Masalan, bir o'lchovli dinamik massivning Array sinfining shablonini olamiz. Shablonda bitta turdagi parametr mavjud - massiv elementlari turi. U "Array.h" sarlavha faylida aniqlangan. 1-misoldan olingan funktsiya shablonlari ishlatiladi. T turiga cheklovlar qo'yilmaydi ("Algo.h" dagi funktsiya shablonlari bo'yicha). Buning sababi shundaki, ularning to'liq tavsifi juda katta hajmga ega bo'ladi, chunki bu sinfning qaysi funktsiyalari-elementlaridan foydalanmoqchi ekanligingizga bog'liq.Masalan, agar siz massivlarni tayinlasangiz, unda T operatsiyasi uchun belgilash jarayoni to'g'ri aniqlangan bo'lishi kerak. ...

Tenglik va tengsizlik operatorlarini massivlarga tatbiq etish uchun T da tengsizlik operatori aniqlanishi kerak.
Misol, shuningdek, oqimlarni ishlatishda << va >> operatsiyalarini qanday qilib haddan tashqari yuklashni va foydalanuvchi turidagi qiymatlarni kiritish-chiqarishni oqimlar yordamida sozlash uchun maxsus sinfni ko'rsatadi. (O'rnatilgan turlar uchun ushbu operatsiyalar oqim kutubxonasida ortiqcha yuklangan.)
Array shablonidan foydalanish "Ex_Array.cpp" dasturida ko'rsatilgan. Ushbu moduldan asosiy sifatida foydalanib, Win32 konsol dasturini yarating.
Array.h
#ifndef ArrayH
#define ArrayH
//---------------------------------------------------------------------------
#include
#include "Algo.h"
//---------------------------------------------------------------------------
/*
Sinf shablonlari: T tipidagi elementlarning bir o'lchovli dinamik massivi.
* /
template
class Array {
private:
unsigned FCount; // elementlar soni
T * FData; // massivning birinchi elementiga ko'rsatgich (agar FCount> 0 bo'lsa)
public:
// Sanoq elementlari qatorini yarating, sukut bo'yicha 0.
Array (imzosiz son = 0)
: FCount (0) // FCount elementini nusxa ko'chirish konstruktori bilan boshlang
{// (standart konstruktor o'rniga)
O'lchamini o'zgartirish (hisoblash, noto'g'ri);
}
// Initsializatsiya qilingan hisoblash elementlari massivini yarating
// ma'lumotlar bilan ko'rsatilgan elementlarni hisoblash.
Array (imzosiz hisoblash, const T * ma'lumotlar)
: FCount (0)
{
Tayinlash (hisoblash, ma'lumotlar);
}
// Konstruktorni nusxalash.
Array (const Array & array)
: FCount (0)
{
Assign (array.FCount, array.FData);
}
// Destructor (xotirani bo'shatadi).
~ Array ()
{
Aniq ();
}
// Massiv hajmini qaytaradi.
unsigned Count () const {return FCount; }
// Massiv o'lchamini belgilaydi.
bekor son (imzosiz hisoblash) {O'lchamini o'zgartirish (hisoblash); }
// Massivni hisoblash uchun o'lchamini belgilaydi va unga elementlarni nusxa ko'chiradi
// ma'lumotlar [0], ma'lumotlar [1], ..., ma'lumotlar [hisoblash - 1].
void Assign (imzosiz hisoblash, const T * ma'lumotlar);
// Massiv o'lchamini belgilaydi. Eski elementlar (yangi o'lchamga qanchalik mos keladi)
// sukut bo'yicha qoladi (parametr do'kon = rost) yoki yo'qoladi (do'kon = yolg'on).
void Resize (unsigned count, bool store = true);
// Barcha elementlarni olib tashlang.
void Clear ()
{
Graf (0);
}
// Topshiriq operatsiyasi. Xuddi shu o'lcham o'rnatiladi va massivdagi ma'lumotlar ko'chiriladi.
Array & operator = (const Array & array)
{
// Agar o'z-o'zini tayinlash amalga oshirilmasa (Array a; a = a;), keyin
agar (bu! = va qator)
// topshiriqni bajaring.
Assign (array.FCount, array.FData);
// Belgilash operatsiyasining chap argumentiga havolani qaytaring, masalan,
// keyingi topshiriq (Array a, b, c; a = b = c;).
return * this;
}
// Indekslash jarayoni (doimiy massiv uchun).
const T & operatori [] (imzosiz indeks) const
{
tasdiqlash (indeks return FData [index]; // va elementga doimiy murojaatni qaytaring
}
// Indekslash jarayoni (doimiy bo'lmagan massiv uchun).
T va operator [] (imzosiz indeks)
{
tasdiqlash (indeks return FData [index]; // va elementga havolani qaytaring
}
// Oqim uchun chiqishning ishlashi.
do'st ostream va operator << (ostream & stream, const Array & array)
{
// Oqim uchun chiqish va
Yozing (array.FData, array.FCount, oqim);
// keyingi chiqishga ruxsat berish uchun oqim ma'lumotnomasini qaytaring (masalan: cout << a << b).
qaytib oqim;
}
// Oqimdan kirish jarayoni.
do'st istream & operator >> (istream & stream, Array va massiv)
{
// Oqimdan kirish va
O'qing (array.FData, array.FCount, oqim);
// qo'shimcha ma'lumot olish uchun oqim ma'lumotnomasini qaytaring (masalan: cin >> a >> b).
qaytib oqim;
}
// Tenglik operatsiyasi.
friend bool operatori == (const Array & x, const Array & y)
{
// Agar massivlar turli xil ob'ektlar bo'lsa, taqqoslashni bajaring.
agar (& x! = & y)
// Agar elementlar soni bir xil bo'lsa,
agar (x.FCount == y.FCount)
// keyin element bo'yicha taqqoslashni amalga oshiring.
return Compare (x.FData, y.FData, FCount);
// Aks holda, massivlar teng emas.
boshqa
return false;
// Aks holda, true qiymatini qaytaring (chunki har qanday massiv o'ziga teng).
haqiqiy qaytish;
}
// Tengsizlik operatsiyasi.
friend bool operatori! = (const Array & x, const Array & y)
{
qaytish! (x == y);
}
};
// ------------------------------------------------ ---------------------------
// Inline bo'lmagan a'zo funktsiyalarining ta'rifi
// ------------------------------------------------ ---------------------------
shablon
void Array :: Assign (imzosiz hisoblash, const T * ma'lumotlar)
{
O'lchamini o'zgartirish (hisoblash, noto'g'ri); // elementlarni saqlamasdan, o'lchamini o'rnating
Nusxalash (FData, ma'lumotlar, FCount); // va ma'lumotlarni nusxalash
}
// ------------------------------------------------ ---------------------------
shablon
void Array :: O'lchamini o'zgartirish (unsigned count, bool store)
{
// Agar elementlar soni o'zgarsa.
if (FCount! = count) {
// Agar elementlarning yangi soni nolga teng bo'lmasa, u holda xotirani ajrating;
agar (hisoblash) {
// Sanoq elementlarining dinamik qatorini yarating,
T * p = yangi T [hisoblash];
// va agar kerak bo'lsa, eski elementlarni u erga nusxalash (iloji boricha).
agar (do'kon)
Nusxalash (p, FData, Min (FCount, count));
// Bo'sh bo'lmasa eski qatorni yo'q qiling.
agar (FCount) o'chirish [] FData;
// Yangi massivning birinchi elementi manzilini sinfda saqlang.
FData = p;
}
// aks holda xotirani bo'shating.
boshqa
o'chirish [] FData;
// Elementlarning yangi sonini sinfda saqlang.
FCount = hisoblash;
}
}
// ------------------------------------------------ ---------------------------
#endif
Ex_Array.cpp
# fludream.h> ni o'z ichiga oladi
# "Array.h" ni o'z ichiga oladi
// Massivni oqimga chiqarish uchun yordamchi sinf.
shablon
Wr sinf {
const char * Ism; // qator nomi
const Array & Arr; // qatorga havola
jamoat:
Wr (const char * n, const Array & a): Ism (n), Arr (a) {}
do'st ostream va operator << (ostream & s, const Wr & w)
{
// qator nomini, teng belgini, elementlarni va satr oxirini chop eting.
s << w.Name << "=" << w.Arr << endl; qaytish s;
}
};
// Element turi.
typedef int turi;
// Shablon parametrlarini doim ko'rsatib turmaslik uchun odatda tipdagi sinonim ishlatiladi.
typedef Array TypeArray;
typedef Wr W;
const imzosiz SZ = 5;
const Init turi [5] = {1, 2, 3, 4, 5};
void main ()
{
// Mavjud barcha konstruktorlardan foydalangan holda massivlar yarating,
TypeArray a, // bo'sh qator
b (3), // sukut bo'yicha yaratilgan 3 ta elektron kirish qatori
// (int uchun sukut bo'yicha kompilyator tomonidan belgilanadi, bu
// hech narsa qilmaydi, ya'ni qiymat aniqlanmagan)
c (SZ, Init), // boshlang'ich bilan SZ e-in dan massiv
d (c); // raqamni nusxalash
// yordamchi chiqish sinflarini yaratish va
W wa ("a", a), wb ("b", b), wc ("c", c), wd ("d", d);
// natijani ko'ring.
cout << wa << wb << wc << wd << endl;
// Elektron pochtani saqlamasdan c massividagi elementlar sonini ikki baravar oshiring.
c.Resize (c.Count () * 2, noto'g'ri); cout << wc;
// d qatoridan elementlar yordamida c qatorini to'ldiring,
imzosiz i;
uchun (i = 0; i c [i * 2] = d [i];
c [i * 2 + 1] = 2 * d [i];
}
// va a-ga nusxa oling.
a = c;
cout << wc << wa << endl;
// d qatoridagi elementlar sonini ikki baravar oshirish,
d.Count (d.Count () * 2); cout << wd;
// va yangi elementlarni c dan nusxa oling.
uchun (i = d.Count () / 2; i d [i] = c [i];
cout << wd << endl;
// Tenglik amalini sinab ko'ring.
cout << "a == b:" << (a == b) << endl;
cout << "a == c:" << (a == c) << endl;
cout << "a == d:" << (a == d) << endl;
cout << "a! = b:" << (a! = b) << endl;
cout << "a! = c:" << (a! = c) << endl;
cout << "a! = d:" << (a! = d) << endl;
// Endi chiquvchi yordamchi sinflar qatorini yarataylik va
// yozish funktsiyasi yordamida barcha massivlarni "_out.txt" fayliga chiqaring.
{
W x [] = {wa, wb, wc, wd};
Ofstream f ("_ out.txt");
Yozing (x, 4, f, "------------------------- \ n");
}
cin.ignore (100, 'q');
}