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

Để quản lý một danh sách liên kết chúng ta có thể sử dụng nhiều phương pháp khác nhau và tương ứng với các phương pháp này chúng ta sẽ có các cấu trúc dữ liệu khác nhau, cụ thể:
Nội dung trích xuất từ tài liệu:
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 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Ñ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 = 7B. 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. Trang: 93 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaäta. 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 NULLb. 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 Trang: 94 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Pnode 20 NULLc. Theâm moät phaàn töû vaøo trong danh saùch: Giaû söû chuùng ta caàn theâm moät phaàn töû coù giaù trò thaønh phaàn döõ lieäu laø NewData vaøo trong danh saùch. Vieäc theâm coù theå dieãn ra ôû ñaàu, cuoái hay ôû giöõa danh saùch lieân keát. Do vaäy, ôû ñaây chuùng ta trình baøy 3 thao taùc theâm rieâng bieät nhau: - Thuaät toaùn theâm phaàn töû vaøo ñaàu danh saùch lieân keát ñôn: B1: NewNode = SLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thöïc hieän Bkt B3: NewNode->NextNode = SLList // Noái SLList vaøo sau NewNode B4: SLList = NewNode // Chuyeån vai troø ñöùng ñaàu cuûa NewNode cho SLList Bkt: Keát thuùc - Minh hoïa thuaät toaùn: Giaû söû chuùng ta caàn theâm nuùt coù thaønh phaàn döõ lieäu laø 25: NewData = 25NewNode 25 NULL NULL SLList 10 20 18 40 35 30New ...