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 5 pps

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

Trang: 93

Ñeå quaûn lyù moät danh saùch lieân keát chuùng ta coù theå söû duïng nhieàu phöông phaùp khaùc

nhau vaø töông öùng vôùi caùc phöông phaùp naøy chuùng ta seõ coù caùc caáu truùc döõ lieäu

khaùc nhau, cuï theå:

- Quaûn lyù ñòa chæ phaàn töû ñaàu danh saùch:

SLL_Type SLList1;

Hình aûnh minh hoïa:

SLList1 NULL

15 10 20 18 40 35 30

- Quaûn lyù ñòa chæ phaàn töû ñaàu vaø cuoái danh saùch:

typedef struct SLL_PairNode

{ SLL_Type SLLFirst;

SLL_Type SLLLast;

} SLLP_Type;

SLLP_Type SLList2;

Hình aûnh minh hoïa:

SLLFirst SLLLast NULL

15 10 20 18 40 35 30

- Quaûn lyù ñòa chæ phaàn töû ñaàu, ñòa chæ phaàn töû cuoái vaø soá phaàn töû trong danh saùch:

typedef struct SLL_PairNNode

{ SLL_Type SLLFirst;

SLL_Type SLLLast;

unsigned NumNode;

} SLLPN_Type;

SLLPN_Type SLList3;

Hình aûnh minh hoïa:

SLLFirst SLLLast NULL

15 10 20 18 40 35 30

NumNode = 7

B. Caùc thao taùc treân danh saùch lieân keát ñôn:

Vôùi moãi caùch quaûn lyù khaùc nhau cuûa danh saùch lieân keát ñôn , caùc thao taùc cuõng seõ

coù söï khaùc nhau veà maët chi tieát song noäi dung cô baûn ít coù söï khaùc nhau. Do vaäy, ôû

ñaây chuùng ta chæ trình baøy caùc thao taùc theo caùch quaûn lyù thöù nhaát (quaûn lyù ñòa chæ

cuûa phaàn töû ñaàu danh saùch lieân keát ñôn), caùc caùch quaûn lyù khaùc sinh vieân töï vaän

duïng ñeå ñieàu chænh cho thích hôïp.

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

Trang: 94

a. Khôûi taïo danh saùch (Initialize):

Trong thao taùc naøy chæ ñôn giaûn laø chuùng ta cho giaù trò con troû quaûn lyù ñòa chæ phaàn

töû ñaàu danh saùch veà con troû NULL. Haøm khôûi taïo danh saùch lieân keát ñôn nhö sau:

void SLL_Initialize(SLL_Type &First)

{ First = NULL;

return;

}

Hình aûnh minh hoïa:

SLList1 NULL

b. Taïo môùi moät phaàn töû / nuùt:

Giaû söû chuùng ta caàn taïo môùi moät phaàn töû coù thaønh phaàn döõ lieäu laø NewData.

- Thuaät toaùn:

B1: First = new SLL_OneNode

B2: IF (First = NULL)

Thöïc hieän Bkt

B3: First->NextNode = NULL

B4: First->Key = NewData

Bkt: Keát thuùc

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

Haøm SLL_Create_Node coù prototype:

SLL_Type SLL_Create_Node(T NewData);

Haøm taïo môùi moät nuùt coù thaønh phaàn döõ lieäu laø NewData, haøm traû veà con troû troû

tôùi ñòa chæ cuûa nuùt môùi taïo. Neáu khoâng ñuû boä nhôù ñeå taïo, haøm traû veà con troû

NULL.

SLL_Type SLL_Create_Node(T NewData)

{ SLL_Type Pnode = new SLL_OneNode;

if (Pnode != NULL)

{ Pnode->NextNode = NULL;

Pnode->Key = NewData;

}

return (Pnode);

}

- Minh hoïa thuaät toaùn:

Giaû söû chuùng ta caàn taïo nuùt coù thaønh phaàn döõ lieäu laø 20: NewData = 20

Pnode = new SLL_OneNode

Pnode

Pnode->NextNode = NULL

Pnode->Key = NewData