Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 7 ppsx

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 139

if (QList.Front == -1)

QList.Front = 0;

if (QList.Rear == QList.Len)

QList.Rear = 0;

else

QList.Rear += 1;

QList.List[QList.Rear] = NewData;

return (QList.Rear);

}

c. Laáy noäi dung moät phaàn töû trong haøng ñôïi ra ñeå xöû lyù (Get):

Trong haøng ñôïi chuùng ta luoân luoân laáy noäi dung phaàn töû ôû ngay ñaàu haøng ñôïi, taïi vò

trí Front (neáu haøng ñôïi khoâng roãng). Giaû söû ta caàn laáy döõ lieäu ra bieán Data:

- Thuaät toaùn:

// Neáu haøng ñôïi bò roãng

B1: IF (CQ_List.Front = 0)

Thöïc hieän Bkt

B2: Data = CQ_List.List[CQ_List.Front]

B3: IF (CQ_List.Rear = CQ_List.Front) // Haøng ñôïi chæ coù 1 phaàn töû

B3.1: CQ_List.Rear = CQ_List.Front = 0

B3.2: Thöïc hieän Bkt

B4: IF (CQ_List.Front = CQ_List.Len)

CQ_List.Front = 1

B5: ELSE

CQ_List.Front++

Bkt: Keát thuùc

- Caøi ñaët thuaät toaùn:

Haøm CQ_Get coù prototype:

int CQ_Get (C_QUEUE &QList, T &Data);

Haøm thöïc hieän vieäc laáy noäi dung phaàn töû ñaàu haøng ñôïi quaûn lyù bôûi QList vaø ghi

nhaän vaøo Data neáu laáy ñöôïc. Haøm traû veà giaù trò 1 neáu vieäc laáy thaønh coâng, ngöôïc

laïi khi haøng ñôïi bò roãng haøm traû veà giaù trò -1.

Noäi dung cuûa haøm nhö sau:

int CQ_Get (C_QUEUE &QList, T &Data)

{ if (QList.Front == -1)

return (-1);

Data = QList.List[QList.Front];

if (QList.Front == QList.Rear)

{ QList.Front = QList.Rear = -1;

return (1);

}

if (QList.Front == QList.Len-1)

QList.Front = 0;

else

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 140

QList.Front += 1;

return (1);

}

d. Huûy haøng ñôïi:

Trong thao taùc naøy chuùng ta thöïc hieän vieäc huûy boä nhôù ñaõ caáp phaùt cho haøng ñôïi.

Haøm CQ_Delete coù noäi dung nhö sau:

void CQ_Delete (C_QUEUE &QList)

{ delete QList.List;

return;

}

C. Caùc thao taùc treân haøng ñôïi toå chöùc baèng danh lieân keát ñôn:

Khaùc vôùi haøng ñôïi bieåu dieãn baèng danh saùch ñaëc, ôû ñaây haøng ñôïi chæ bò ñaày khi heát

boä nhôù vaø khoâng bao giôø bò traøn.

a. Khôûi taïo haøng ñôïi (Initialize):

Töông töï nhö trong danh saùch lieân keát ñôn, trong thao taùc naøy chuùng ta chæ ñôn

giaûn thöïc hieän vieäc gaùn caùc con troû Front vaø Rear veà con troû NULL. Haøm

SQ_Initialize coù noäi dung nhö sau:

S_QUEUE SQ_Initialize (S_QUEUE &QList)

{ QList.Front = QList.Rear = NULL;

return (QList);

}

b. Theâm (Ñöa) moät phaàn töû vaøo haøng ñôïi (Add):

ÔÛ ñaây chuùng ta theâm moät phaàn töû vaøo sau Rear (Theâm vaøo cuoái danh saùch lieân keát).

Giaû söû chuùng ta caàn ñöa phaàn töû coù giaù trò döõ lieäu laø NewData vaøo trong haøng ñôïi:

- Thuaät toaùn:

B1: NewElement = SLL_Create_Node(NewData)

B2: IF (NewElement = NULL)

Thöïc hieän Bkt

B3: IF (SQ_List.Front = NULL) // Neáu haøng ñôïi bò roãng

B3.1: SQ_List.Front = SQ_List.Rear = NewElement

B3.2: Thöïc hieän Bkt

B4: SQ_List.Rear->Next = NewElement

B5: SQ_List.Rear = NewElement

Bkt: Keát thuùc

- Caøi ñaët thuaät toaùn:

Haøm SQ_Add coù prototype:

Q_Type SQ_Add (S_QUEUE &QList, T NewData);

Haøm thöïc hieän vieäc theâm phaàn töû coù noäi dung NewData vaøo trong haøng ñôïi quaûn

lyù bôûi QList. Haøm traû veà ñòa chæ cuûa phaàn töû vöøa môùi theâm neáu vieäc theâm thaønh

coâng, ngöôïc laïi haøm traû veà con troû NULL.