intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo trình hướng dẫn dùng hàm Input new data để tạo mới danh sách và tách một list thành nhiều danh sách p4

Chia sẻ: Dgdsfg Hkuyou | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST
Báo xấu
85
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData. - Thuật toán: B1: DNode = new DLL_OneNode B2: IF (DNode = NULL) Thực hiện Bkt B3: DNode-NextNode = NULL B4:Vận dụng các thuật toán sắp xếp đã học, hãy cài đặt các hàm sắp xếp trên danh sách liên kết đơn,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình hướng dẫn dùng hàm Input new data để tạo mới danh sách và tách một list thành nhiều danh sách p4

  1. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o DLL_List c u -tr a c k c u -tr a c k DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode NULL 25 NULL NewNode->NextNode = InsNode->NextNode: DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 NULL InsNode->NextNode->PreNode = NewNode: DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 NULL InsNode->NextNode = NewNode: DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 NULL NewNode->PreNode = InsNode Trang: 118
  2. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o DLL_List c u -tr a c k c u -tr a c k DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 Keát quaû sau khi cheøn: DLL_List DLL_First DLL_Last NULL 16 20 18 25 40 30 NULL - Caøi ñaët thuaät toaùn: Caùc haøm theâm phaàn töû töông öùng vôùi caùc tröôøng hôïp coù prototype nhö sau: DLL_Type DLL_Add_First(DLLP_Type &DList, T NewData); DLL_Type DLL_Add_Last(DLLP_Type &DList, T NewData); DLL_Type DLL_Add_Mid(DLLP_Type &DList, T NewData, DLL_Type &InsNode); Haøm thöïc hieän vieäc cheøn phaàn töû coù giaù trò thaønh phaàn döõ lieäu NewData vaøo trong danh saùch lieân keát ñoâi quaûn lyù bôûi hai con troû ñaàu vaø cuoái danh saùch trong DList töông öùng vôùi 3 tröôøng hôïp: Theâm ñaàu, theâm cuoái, theâm giöõa. Caùc haøm traû veà giaù trò laø moät ñòa chæ cuûa nuùt vöøa môùi theâm neáu vieäc theâm thaønh coâng. Trong tröôøng hôïp ngöôïc laïi, caùc haøm traû veà con troû NULL. Rieâng ñoái vôùi tröôøng hôïp theâm giöõa, haøm DLL_Add_Mid thöïc hieän vieäc theâm vaøo ngay sau nuùt coù ñòa chæ InsNode. Noäi dung cuûa caùc haøm nhö sau: DLL_Type DLL_Add_First(DLLP_Type &DList, T NewData) { DLL_Type NewNode = DLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (DList.DLL_First == NULL) DList.DLL_First = DList.DLL_Last = NewNode; else { NewNode->NextNode = DList.DLL_First; DList.DLL_First->PreNode = NewNode; DList.DLL_First = NewNode; } return (NewNode); } //================================================================= DLL_Type DLL_Add_Last(DLLP_Type &DList, T NewData) Trang: 119
  3. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o { DLL_Type NewNode = DLL_Create_Node(NewData); c u -tr a c k c u -tr a c k if (NewNode == NULL) return (NULL); if (DList.DLL_Last == NULL) DList.DLL_First = DList.DLL_Last = NewNode; else { DList.DLL_Last->NextNode = NewNode; NewNode->PreNode = DList.DLL_Last; DList.DLL_Last = NewNode; } return (NewNode); } //================================================================= DLL_Type DLL_Add_Mid(DLLP_Type &DList, T NewData, DLL_Type &InsNode) { DLL_Type NewNode = DLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (InsNode->NextNode == NULL) { InsNode->NextNode = NewNode; NewNode->PreNode = InsNode; DList.DLL_Last = NewNode; } else { NewNode->NextNode = InsNode->NextNode; InsNode->NextNode->PreNode = NewNode; InsNode->NextNode = NewNode; NewNode->PreNode = InsNode; } return (NewNode); } d. Duyeät qua caùc nuùt trong danh saùch: Thao taùc naøy nhaèm nhieàu muïc ñích, ôû ñaây ñôn giaûn chuùng ta chæ duyeät ñeå xem noäi dung thaønh phaàn döõ lieäu trong danh saùch. Thuaät toaùn naøy hoaøn toaøn töông töï nhö trong danh saùch lieân keát ñôn. - Thuaät toaùn: B1: CurNode = DLL_List.First B2: IF (CurNode = NULL) Thöïc hieän Bkt B3: OutputData(CurNode->Key) // Xuaát giaù trò thaønh phaàn döõ lieäu trong 1 nuùt B4: CurNode = CurNode->NextNode B5: Laëp laïi B2 Bkt: Keát thuùc - Caøi ñaët thuaät toaùn: Haøm DLL_Travelling coù prototype: Trang: 120
  4. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o void DLL_Travelling(DLLP_Type DList); c u -tr a c k c u -tr a c k Haøm duyeät qua caùc nuùt trong danh saùch lieân keát ñoâi quaûn lyù bôûi hai ñòa chæ nuùt ñaàu tieân vaø nuùt cuoái cuøng thoâng qua DList ñeå xem noäi dung thaønh phaàn döõ lieäu cuûa moãi nuùt. Noäi dung cuûa haøm nhö sau: void DLL_Travelling (DLLP_Type DList) { DLL_Type CurNode = DList.DLL_First; while (CurNode != NULL) { OutputData(CurNode->Key); CurNode = CurNode->NextNode; } return; } Löu yù: Haøm OutputData thöïc hieän vieäc xuaát noäi dung cuûa moät bieán coù kieåu döõ lieäu T. Tuøy vaøo töøng tröôøng hôïp cuï theå maø chuùng ta vieát haøm OutputData cho phuø hôïp. e. Tìm kieám moät phaàn töû trong danh saùch: Giaû söû chuùng ta caàn tìm kieám xem trong danh saùch lieân keát ñoâi coù toàn taïi nuùt coù thaønh phaàn döõ lieäu laø SearchData hay khoâng. Thao taùc naøy chuùng ta vaän duïng thuaät toaùn tìm tuyeán tính ñeå tìm kieám. - Thuaät toaùn: B1: CurNode = DLL_List.DLL_First B2: IF (CurNode = NULL OR CurNode->Key = SearchData) Thöïc hieän Bkt B3: CurNode = CurNode->NextNode B4: Laëp laïi B2 Bkt: Keát thuùc - Caøi ñaët thuaät toaùn: Haøm DLL_Searching coù prototype: DLL_Type DLL_Searching(DLLP_Type DList, T SearchData); Haøm thöïc hieän vieäc tìm kieám nuùt coù thaønh phaàn döõ lieäu laø SearchData treân danh saùch lieân keát ñoâi quaûn lyù bôûi hai ñòa chæ nuùt ñaàu tieân vaø nuùt cuoái cuøng thoâng qua DList. Haøm traû veà ñòa chæ cuûa nuùt ñaàu tieân trong danh saùch ñöôïc tìm thaáy, ngöôïc laïi haøm traû veà con troû NULL. Noäi dung cuûa haøm nhö sau: DLL_Type DLL_Searching(DLLP_Type DList, T SearchData) { DLL_Type CurNode = DList.DLL_First; while (CurNode != NULL) { if (CurNode->Key == SearchData) break; CurNode = CurNode->NextNode; } Trang: 121
  5. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o return (CurNode); c u -tr a c k c u -tr a c k } f. Loaïi boû bôùt moät phaàn töû ra khoûi danh saùch: Giaû söû chuùng ta caàn loaïi boû phaàn töû coù giaù trò thaønh phaàn döõ lieäu laø DelData trong danh saùch lieân keát ñoâi, Ñeå thöïc hieän ñieàu naøy tröôùc tieân chuùng ta phaûi thöïc hieän thao taùc tìm kieám ñòa chæ cuûa nuùt coù thaønh phaàn döõ lieäu laø DelData, sau ñoù môùi thöïc hieän thao taùc loaïi boû neáu tìm thaáy. - Thuaät toaùn: // Tìm kieám nuùt coù Key laø DelData trong danh saùch B1: DelNode = DLL_Searching(DLL_List, DelData) B2: IF (DelNode = NULL) Thöïc hieän Bkt // Loaïi boû nuùt taïi ñòa chæ DelNode ra khoûi danh saùch B3: IF (DelNode->PreNode = NULL AND DelNode->NextNode = NULL) B3.1: DLL_List.DLL_First = DLL_List.DLL_Last = NULL B3.2: Thöïc hieän B8 B4: IF (DelNode->PreNode = NULL) // Loaïi boû nuùt ñaàu tieân trong danh saùch B4.1: DLL_List.DLL_First = DLL_List.DLL_First->NextNode B4.2: DLL_List.DLL_First->PreNode = NULL B4.3: Thöïc hieän B8 B5: IF (DelNode->NextNode = NULL) // Loaïi boû nuùt cuoái cuøng trong danh saùch B5.1: DLL_List.DLL_Last = DLL_List.DLL_Last->PreNode B5.2: DLL_List.DLL_Last->NextNode = NULL B5.3: Thöïc hieän B8 // Lieân keát caùc noát tröôùc vaø sau DelNode vôùi nhau B6: DelNode->PreNode->NextNode = DelNode->NextNode B7: DelNode->NextNode->PreNode = DelNode->PreNode //Boû moái lieân keát giöõa DelNode vôùi hai nuùt tröôùc vaø sau noù, vaø huûy DelNode B8: DelNode->NextNode = DelNode->PreNode = NULL B9: delete DelNode Bkt: Keát thuùc - Caøi ñaët thuaät toaùn: Haøm DLL_Delete_Node coù prototype: int DLL_Delete_Node (DLLP_Type &DList, T DelData); Haøm thöïc hieän vieäc xoùa phaàn töû coù thaønh phaàn döõ lieäu laø DelData trong danh saùch lieân keát ñoâi quaûn lyù bôûi hai con troû ñaàu vaø cuoái ghi nhaän trong DList. Haøm traû veà giaù trò 1 neáu vieäc xoùa thaønh coâng vaø ngöôïc laïi, haøm traû veà giaù trò -1. Noäi dung cuûa haøm nhö sau: int DLL_Delete_Node (DLLP_Type &DList, T DelData) { DLL_Type DelNode = DLL_Searching(DList, DelData); if (DelNode == NULL) return (-1); Trang: 122
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2