GIẢI THUẬT VÀ ỨNG DỤNG CẤU TRÚC ĐỐNG.doc

Báo cáo nghiên cứu khoa học Cấu trúc đống và ứng dụng

Mục Lục

Phần 1:MỞ ĐẦU .................................................................... 3

Lí do chọn đề tài. ........................................................................................................... 3

Phần 2:Nội Dung ..................................................................... 3

Chương 1 : Cơ sở lý thuyết về cây nhị phân. ............................................................... 3

I. Định nghĩa và các ví dụ .................................................................................... 3

1. Định nghĩa. ..................................................................................................................... 4

2.Ví dụ . .............................................................................................................................. 4

II. Cây nhị phân. ................................................................................................... 5

1. Định nghĩa và các tính chất. .......................................................................................... 5

2. Biểu diễn cây nhị phân ................................................................................................... 5

Chương 2. Cấu trúc đống. ............................................................................................. 8

I. Định nghĩa . ....................................................................................................... 8

1.Định nghĩa. ...................................................................................................................... 8

2. Heap có các tính chất sau : ........................................................................................... 9

3. Ví dụ : ............................................................................................................................. 9

4) Thuật giải. .................................................................................................................... 10

II. Các phép toán của Heap. ............................................................................... 10

1. Thêm một phần tử vào Heap. ...................................................................................... 10

2. Xoá một phần tử nhỏ nhất khỏi Heap. ........................................................................ 12

Chương 3: Các ứng dụng của Đống ............................................................................ 13

I. Ứng dụng của Heap trong giải thuật Heap_sort. ........................................... 13

1.Giải thuật. ...................................................................................................................... 13

II.Ứng dụng đống tổ chức hàng đợi có ưu tiên ................................................ 19

1.Ứng dụng của đống trong giải thuật Hufman. ................................................ 19

2.Ứng dụng của đống trong giải thuật xây dựng cây bao trùm nhỏ nhất của đồ thị liên

thông : ........................................................................................................................................... 23

Nguyễn Thị Ngọc Anh_lớp K54A-CNTT

1

Báo cáo nghiên cứu khoa học Cấu trúc đống và ứng dụng

Chương 4: Mô phỏng và cài đặt cấu trúc đống và ứng dụng. .................................... 25

I.Mô phỏng thuật toán. ....................................................................................... 25

1.Khái niệm chung về mô phỏng thuật toán. ................................................................... 26

2.Mục đích của mô phỏng thuật toán. ............................................................................. 26

3.Cấu trúc tổng quan của mô phỏng thuật toán: ............................................................. 27

4. Quy trình thiết kế nhiệm vụ của mô phỏng thuật toán. ............................................... 27

Nguyễn Thị Ngọc Anh_lớp K54A-CNTT

2

Báo cáo nghiên cứu khoa học Cấu trúc đống và ứng dụng

Phần 1:MỞ ĐẦU

Lí do chọn đề tài.

Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà khoa học

khẳng định rằng chưa có một ngành khoa học - công nghệ nào lại có nhiều ứng dụng

như công nghệ thông tin. Việc ứng dụng công nghệ thông tin vào trong giáo dục đã

trở thành mối ưu tiên hàng đầu của nhiều quốc gia trong đó có Việt Nam.

Trong quá trình học các giải thuật nói chung và môn cấu trúc dữ liệu nói riêng,

chúng ta rút ra một nhận định chung là: nhiều giải thuật phức tạp trừu tượng, khó hiểu,

khó hình dung vấn đề. Do đó chúng ta luôn mong muốn trong quá trình học giải thuật

nên có những mô phỏng trực quan để chúng ta có thể tiếp thu giải thuật một cách dễ

dàng hơn. Tuy nhiên, việc học tốt giải thuật có rất nhiều thận lợi dó là giúp cho quá

trình tư duy giải thật tốt hơn, phát hiện vấn đề nhanh hơn, đặc biệt giúp cho việc học

các môn học khác có tính logic cao được thuận lợi hơn. Nhưng để học tốt giải thuật thì

không dễ dàng với nhiều người. Vậy để giúp người học tiếp thu một cách dễ dàng các

giải thuật thì phải xây dựng các phần mền mô phỏng thuật toán.

Cấu trúc đống có rất nhiều ứng vào các giải thuật nhưgiả thuật sắp xếp đống,

vào hàng đợi ưu tiên. Nghiên cứu cấu trúc đống để hiểu thêm về nó phục vụ trong việc

giải quyết các bài toán

Phần 2:Nội Dung

Chương 1 : Cơ sở lý thuyết về cây nhị phân.

I. Định nghĩa và các ví dụ

Nguyễn Thị Ngọc Anh_lớp K54A-CNTT

3