“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

7-Mavzu:“Ro‘yxat” turdagi ma'lumotlar tuzilmalari. Ro‘yxatlarni statik va dinamik tarzda amalga oshirish. Bir va ikki bog‘lamli ro‘yxatlar va ular ustida amal bajarish algoritmlari .

• Reja:
• Bog’langan ro’y’hatlar haqida tushuncha
• Bog’langan ro’y’hatlar klassifikasiyasi
• Bog’langan ro’y’hatlarni mantiqiy tasvirlash
• Bir va ikki bog’lamli ro’y’hatlar ustida amallar

Roʼyxatlar

• Roʼyxatning umumiy koʼrinishiga misol :
• E1, E2, ..., En, (n ≥0 boʼlib n fiksirlanmagan).
• Roʼyxat elementlari soni dastur bajarilishi davomida oʼzgarib turishi mumkin.

• Def.1.

• Roʼyxat deb bir turga tegishli boʼlgan elementlar ketma-ketligiga aytiladi.

• Eslatma

• Roʼyxatni tashkil etuvchi elementlar soni chegaralanmagan boʼlishi mumkin.

• Roʼyxatni mantiqiy tasvirlash

• Oshkormas(massiv)

• Oshkor(koʼrsatkichli)

• Def.1.1.

• Roʼyxatni tashkil etuvchi elementlar soni n ga roʼyxat uzunligi deyiladi.

Bog’langan ro’y’hatlar

• Def.1.

• Agar ro’yhat elementlari ko’rsatkichlar orqali bog’langan bo’lsa, u holda bunday tuzilmaga bog’langan ro’y’hatlar deyiladi.

• Eslatma

• Bog’langan ro’yhatlarning har bir elementi ikki xil maydonga ega tuzilma hisoblanadi.

• izoh

• Informatsion maydonda ro’y’hat elementi ma’lumotlari, ko’rsatkichlar maydonida esa mazkur element bilan bog’langan tuzilmaning boshqa elementlari manzillari joylashgan bo’ladi.

Misol.

• P1 va P2 – o’zaro bog’langan elementlarni adreslarini o’z ichiga oluvchi ko’rsatkichlardir.

• Ma’lumotlar

• Р1

• Р2

• Ma’lumotlar

• Р1

• Р2

• Ma’lumotlar

• Р1

• Р2

• izoh

• Bog’langan ro’yhat elementining ko’rsatkichlari maydoni soni bir nechta va turli xil bo’lishi mumkin.

• Def.2.

• Ro’yhat m bog’lamli deyiladi, agar ro’yhatning hech bo’lmaganda bitta elementi ko’pi bilan tuzilmaning m ta elementi bilan o’zaro bog’langan bo’lsa.

• Def.3.

• Agar bog’langan ro’yhat elementlari mavjud bo’lmasa, u holda bunday ro’yhat bo’sh ro’yhat deyiladi.

• - bo’sh ro’yhat

• 3 bog’lamli ro’yhatga misol

• Def.4.

• Agar element ko’rsatkichi 0 yoki bo’sh (NULL) bo’lsa, u holda bu element ro’yhatning eng so’nggi elementi hisoblanadi.

• Def.5.

• Bog’langan ro’yhatda yana shunday bir ko’rsatkich mavjud bo’lib, u ro’yhat boshini ko’rsatadi (Lst).

• Lst=NULL

• Def.3.

• Ro’yhatning afzalligi

• Elementlarni qo’shish, o’chirish qulay va oson;
• Ro’yhat uzunligi faqatgina kompyuter hotirasi xajmi va ko’rsatkich razryadiga bog’liq;
• Elementlarni dinamik tarzda qo’shish va o’chirish mumkin.

• Ro’yhatda element manzilini ro’yhatdagi raqami bo’yicha aniqlash murakkab;
• Ko’rsatkichlar maydoniga qo’shimcha xotira vzarur bo’ladi ( massivda kerak emas);
• Ro’yhatda ishlash massivga nisbatan sekinroq amalga oshadi (sababi, ro’yhat elementiga murojaat undan oldingi elementlar orqali bo’ladi);
• Ro’yhat elementlari xotirada tartibsiz joylashgan, bu esa protsessorni keshlashtirishga salbiy ta’sir ko’rsatadi;
• Bog’langan ro’yhatlarda vektor amallarni bajarish qiyinroq (masalan, yig’indini hisoblash);

• Ro’yhatning kamchiligi

• Bog’langan royhatlar

• chiziqli

• chiziqsiz

• Бир боғламли

• Ikki bog’lamli

• Bir bog’lamli

• Ko’p bog’lamli

• Ikki bog’lamli

• izoh

• Chiziqli ro’yhatlarda elementlar orasidagi bog’liqlik qat;iy tartiblangan bo’lib, element ko’rsatkichi o’zidan navbatdagi yoki oldingi element adresini o’z ichiga oladi.