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

Giáo trình phân tích quy trình ứng dụng thuật toán có thành phần dữ liệu newdata p4

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

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

Tham khảo tài liệu 'giáo trình phân tích quy trình ứng dụng thuật toán có thành phần dữ liệu newdata p4', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

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 phân tích quy trình ứng dụng thuật toán có thành phần dữ liệu newdata 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 c u -tr a c k c u -tr a c k CurNode->Key < SearchData // Tìm kieám treân caây con phaûi ⇒ CurNode = CurNode->BST_Right BSTree 60 25 CurNode 65 19 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL 50 15 NULL NULL NULL NULL CurNode->Key > SearchData // Tìm kieám treân caây con traùi ⇒ CurNode = CurNode->BST_Left BSTree 60 25 65 19 CurNode 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL 50 15 NULL NULL NULL NULL CurNode->Key < SearchData // Tìm kieám treân caây con phaûi ⇒ CurNode = CurNode->BST_Right Trang: 168
  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 BSTree c u -tr a c k c u -tr a c k 60 25 65 19 40 NULL NULL 10 NULL 30 CurNode 44 NULL NULL NULL NULL 50 15 NULL NULL NULL NULL CurNode = NULL ⇒ Thuaät toaùn keát thuùc (Khoâng tìm thaáy) - Caøi ñaët thuaät toaùn: Haøm BST_Searching coù prototype: BST_Type BST_Searching(BST_Type BS_Tree, T SearchData); Haøm thöïc hieän thao taùc tìm kieám treân caây nhò phaân tìm kieám BS_Tree nuùt coù thaønh phaàn Key laø SearchData. Haøm traû veà con troû troû tôùi ñòa chæ cuûa nuùt coù Key laø SearchData neáu tìm thaáy, trong tröôøng hôïp ngöôïc laïi haøm traû veà con troû NULL. BST_Type BST_Searching(BST_Type BS_Tree, T SearchData) { BST_Type CurNode = BS_Tree; while (CurNode != NULL && CurNode->Key != SearchData) { if (CurNode->Key > SearchData) CurNode = CurNode->BST_Left; else CurNode = CurNode->BST_Right; } return (CurNode); } b. Theâm moät nuùt vaøo trong caây: Giaû söû chuùng ta caàn theâm moät nuùt coù thaønh phaàn döõ lieäu (Key) laø NewData vaøo trong caây nhò phaân tìm kieám sao cho sau khi theâm caây vaãn laø moät caây nhò phaân tìm kieám. Trong thao taùc naøy tröôùc heát chuùng ta phaûi tìm kieám vò trí theâm, sau ñoù môùi tieán haønh theâm nuùt môùi vaøo caây (Do vaäy thuaät toaùn coøn ñöôïc goïi laø thuaät toaùn tìm kieám vaø theâm vaøo caây). Quaù trình tìm kieám tuaân thuû caùc böôùc trong thuaät toaùn tìm kieám ñaõ trình baøy ôû treân. Trong thuaät toaùn naøy chuùng ta seõ trình baøy thao taùc theâm vaøo caây nhò phaân tìm kieám trong tröôøng hôïp khoâng coù hieän töôïng truøng laép khoùa. Do vaäy, neáu NewData bò truøng Trang: 169
  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 vôùi Key cuûa moät trong caùc nuùt ôû trong caây nhò phaân tìm kieám thì chuùng ta seõ khoâng c u -tr a c k c u -tr a c k thöïc hieän thao taùc theâm naøy. Tuy nhieân, neáu chuùng ta söû duïng caáu truùc döõ lieäu môû roäng thì vieäc truøng khoùa seõ giaûi quyeát ñôn giaûn vì khoâng laøm taêng soá nuùt cuûa caây nhò phaân tìm kieám maø chæ laøm taêng thaønh phaàn Count cuûa nuùt bò truøng khoùa theâm 1. - Thuaät toaùn theâm 1 nuùt vaøo caây nhò phaân tìm kieám: B1: NewNode = BinT_Create_Node(NewData) B2: IF (NewNode = NULL) Thöïc hieän Bkt B3: IF (BSTree = NULL) // Caây roãng B3.1: BSTree = NewNode B3.2: Thöïc hieän Bkt B4: CurNode = BSTree B5: IF (CurNode->Key = NewData) // Truøng khoùa Thöïc hieän Bkt B6: IF (CurNode->Key > NewData) B6.1: AddLeft = True // Theâm vaøo caây con traùi cuûa CurNode B6.2: If (CurNode->BST_Left != NULL) CurNode = CurNode->BST_Left B7: IF (CurNode->Key < NewData) B7.1: AddLeft = False // Theâm vaøo caây con phaûi cuûa CurNode B7.2: If (CurNode->BST_Right != NULL) CurNode = CurNode->BST_Right B8: Laëp laïi B5 B9: IF (AddLeft = True) CurNode->BST_Left = NewNode B10: ELSE CurNode->BST_Right = NewNode Bkt: Keát thuùc - Minh hoïa thuaät toaùn: Giaû söû chuùng ta caàn theâm vaøo trong caây nhò phaân tìm kieám 1 nuùt coù thaønh phaàn döõ lieäu laø 55: NewData = 55 NewNode CurNode BSTree 55 60 NULL NULL 25 65 19 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL NULL NULL Trang: 170
  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 CurNode->Key > NewData // Theâm vaøo caây con traùi c u -tr a c k c u -tr a c k ⇒ AddLeft = True CurNode->BST_Left != NULL // Chuyeån sang caây con traùi ⇒ CurNode = CurNode->BST_Left BSTree NewNode CurNode 60 55 25 65 NULL NULL 19 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL NULL NULL CurNode->Key < NewData // Theâm vaøo caây con phaûi ⇒ AddLeft = False CurNode->BST_Right != NULL // Chuyeån sang caây con phaûi ⇒ CurNode = CurNode->BST_Right BSTree 60 NewNode 25 CurNode 65 55 19 40 NULL NULL NULL NULL 10 NULL 30 44 NULL NULL NULL NULL NULL NULL CurNode->Key < NewData // Theâm vaøo caây con beân phaûi ⇒ AddLeft = False CurNode->BST_Right != NULL // Chuyeån sang caây con beân phaûi ⇒ CurNode = CurNode->BST_Right Trang: 171
  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 c u -tr a c k c u -tr a c k BSTree 60 25 65 19 40 NULL NULL NewNode CurNode 10 NULL 30 44 55 NULL NULL NULL NULL NULL NULL NULL NULL CurNode->Key < NewData // Theâm vaøo caây con phaûi ⇒ AddLeft = False CurNode->BST_Right == NULL // Theâm NewNode vaøo thaønh nuùt goác caây con phaûi cuûa CurNode // (AddLeft = False), thuaät toaùn keát thuùc. ⇒ CurNode->BST_Right = NewNode Keát quaû sau khi theâm: BSTree 60 25 65 19 40 NULL NULL CurNode 10 NULL 30 44 NewNode NULL NULL NULL NULL NULL 55 NULL NULL - Caøi ñaët thuaät toaùn: Haøm BST_Add_Node coù prototype: BST_Type BST_Add_Node(BST_Type &BS_Tree, T NewData); Trang: 172
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
3=>0