IS11D107

Холбогдох өгөгдөлийн бүтэц

Компьютерийн шинжлэх ухаанд холбогдсон өгөгдөлийн бүтэц нь өгөгдөлийн бүтцэд өгөгдөлийн бичлэг суугдсан байдаг ба заалт холбогдсон эсвэл үзүүлэлтээр байгуулагддаг.Холбогдсон өгөдөлийн бүтэц онцгой өгөгдөлийн төрөл нь ихэнхдээ тэнцвэртэйбайдлыг харьцуулах эсвэл дахин зааварлалт зэргийг л чаддаг шиг боловсруулдаг.Холбогдсон өгөгдөлийн бүтэц нь маань болон өөр өгөгдөлийн бүтцэд шаардлагатай үзүүлэлт дээрх ариметик гүйцэтгэлтэй байх эдгээрээс эрс ялгаатай юм. Зангилаа яг үнэндээ нэг массивийн элемент шиг хэрэгжүүлэгдсэн мөн заавар нь яг массив индекс: өгөгдөлийн бүтэц нь яг 1 холбогдсон индекс дээр ямарч тооцоололгүй болвол дуусна.

Холболт нь 2 янзаар дуусдаг: динамик хувиарлал ашиглаж мөн массив индекс холболтыг ашиглана.Холбогдсон өгөгдөлийн бүтцэд холбогдсон жагсаалтууд, хайлтын мод, мөн олон ихээр хэрэглэгддэг өгөдөлийн бүтцүүд ордог.Тэдгээр нь түүнчлэн математикийн ухааны төрөл мөн нэгдэл хайлтыг суулгах нь түлхүүр хайлт болон олон ашигтай алгоритмууд байдаг.

Холбогдсон жагсаалтууд

Холбогдсон жагсаалтууд нь санах ойд изик байршуулалтаар биш дараалласан бүтцийн цуглуулга юм. Гэвч локигоор холбогдсон энэ нь дараалласан бүтэц нь өөрөө өгөдөлийн хэсэг шиг бүтэц юм. Энэ нь зэрэгцээ санах ойн байрлалд нөөц шаардлагатай биш юм. Өгөгдөл бүр өгөгдөлийн хэсэгтэй мөн хаягийн хсэгтэй байдаг. Хаягийн хэсэг нь залгамжлагчын хаягыг багтаасан байдаг. Хаягийн залгамжлагч нь 1,2 эсвэл олон холбогдсон мөн эдгээр нь бүгд шугаман эсвэл тойргоор байх боломжтой.

Гол шинж чанар

• обьект, дуудагдсан зангилаанууд, шугаман дараалалтай холбогдсон
• зааварын дагуу жагсааалтын эхний зангилаа нь хадгалагдсан байдаг. Дуудахдаа толгой эсвэл эсрэгийг нь дууддаг.

Жишээнүүд

A linked list with a single node.

Жишээ : Энэ жишээ нь холболтын жагсаал холболтын жагсаалтад Java-гийн бүхэл тооны хэрэгжилтийг харуулж байна.

public class IntNode{
	public int value;
	public IntNode link;
	public IntNode (int v) { value = v; }
}

Жишээ; холболтын жагсаалтын хэрэгжилтийг бүтцэд хэрэглэж байн

struct node
{
	int val;
	struct node *next;
};

Typedefs- ийг ашиглаж байна

typedef struct node_s node_t;
struct node_s
{
	int val;
	node_t *next;
};

хэмжээний жагсаалтын хэмжэгдэхүүний C++ дэх class бүтцийг хэрэглэдэг.

class Node
{
	int val;
	Node *next;
};

Массив харьцуулалтын давуу тал

Массив харьцуулалтыг харьцуулахад холбогдсон өгөгдөлийн бүтэц нь зайг хувиарлах мөн өгөгдөлийг зохион байгуулахад илүү уян хатан байдлыг хүлээн зөвшөөрдөг. Массивт эхэлхэд хэмжээ нь нарийн тодорхой байх ёстой. Энэ нь санах ойн илүүдэл байх боломжтой. Холбогдсон өгөгдөлийн бүтэц нь динамик бүтэцтэй мөн хэзээ ч програмаасаа том байх хэрэггүйг шаарддаг. Түүнчлэн холбогдсон өгөгдөлийн бүтэц хээглэх үед хувиарлахад хэр хэмжээний зай байгааг тааж тогтоох шаардлагатай байдаг. Энэ нь санах ойн хоосон зайг хамгаалах 1 арга юм. МАссивт массивын элемент нь санах ойн хэсэгт зэргэлдээ(дэс дараалалтай холбогдсон ) байх хэрэгтэй. Гэвч холбогдсон өгөгдөлийн бүтцэд дараагийн 1-ийг хаанаас олж болох мэдээллийг зангилаа бүр дээр заавар болгон өгдөг. Холбогдсон өгөгдөлийн бүтцийн зангилаа нь тусдаа хөдөлж логик өөрчлөлтгүйгээр өөр байрлалаас хоорондоо холбогддогоороо массиваац ялгаатай. Хамааралтай байх үед: өөр хэсгийн үйл явц нь ажиллаж байх зуур өгөгдөлийн бүтцийн 1 хэсэг зангилаа устах эсвэл үйл явцыг нэмж болно.Өөр нэг арга бол зааврын дагалдагч зангилаа нь холбогдсон өгөгдөлийн бүтцэд шаардлагатай байдаг. Үүнд ямар ч онцгойлсон зангилаа нь нэвтэрдэг. Ихэнхи өгөдлийн бүтцүүдэд зангилаа нь хамгийн багадаа л гэхэд (u-1)-ээс дээш алхамтай байхыг шаарддаг. Эсрэгээрээ ихэнхи хэмжээст өгөдлийн бүтцүүд нь оролтын хэмжээ нь бие даасан байдал бүхий тогтмол тооны үйлдлийн элемэнтүүдрүү хандахыг зөвшөөрнө. Ерөнхийдөө динамик өгөгдлийн бүтэц, холбогдсон өгөгдлийн бүтэц эдгээрийн гүйцэтгэл юм. Энэ нь бидэнд гол зайг дахин ашиглах боломж олгодог. Санах ой нь өгөгдлийн бүтцийн хэрэглээгээр илүү үр бүтээлтэйгээр ашиглах боломжтой юм. Санах ой нь шаардлагатай болсон үед хувиарлагдаж шаарлагагүй болсон үедээ чөлөөлөгддөг.

Ерөнхий сөрөг тал

Холбогдсон өгөгдлийн бүтэц нь мөн адил үндсэн санах ой нь хувиарлалтанд нэмэлтээр орох ба санах ой нь хуудаслалт болон процессор нууцлал хийх алгоритмын өгөгдлийг удаашруулдаг. Энэ тохиолдолд холбогдсон өгөгдлийн бүтэц нь илүү санах ой(холболтын талбар) үүнээс массивын бүтэц нь зөрөөтэй байдаг. Учир нь холболтын өгөгдлийн бүтэц нь зэрэгцээ биш байдаг. Жишээ нь өгөгдөл нь санах ойн доторхи бүгдийг олж чаддаг, массив нь үүнээс өөр юм.Массивд холбогдсон өгөгдлийн бүтэц нь олон зорилтыг дагаж тэгээд бүтцийн элемэнт нь цагийн төрлөөр нэвтэрч байхад элемэнт нь их хэмжээгээр нэвтрэх боломжтой болдог. Онолоор зарим тооцооллын загвар нь бүтцийн холболтын шахалтыг шаарддаг энэ нь заалтын машин, шиг мөн маш олон асуудлуудад хүсэлтээрээ санамсаргүй хэвтрэх машины завбар болон илүү алхамуудыг шаарддаг.