Xu Hướng 1/2023 # Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật # Top 5 View | Nhatngukohi.edu.vn

Xu Hướng 1/2023 # Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật # Top 5 View

Bạn đang xem bài viết Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật được cập nhật mới nhất trên website Nhatngukohi.edu.vn. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất.

Duyệt cây là gì?

Duyệt cây là một tiến trình để truy cập tất cả các nút của một cây và cũng có thể in các giá trị của các nút này. Bởi vì tất cả các nút được kết nối thông qua các cạnh (hoặc các link), nên chúng ta luôn luôn bắt đầu truy cập từ nút gốc. Do đó, chúng ta không thể truy cập ngẫu nhiên bất kỳ nút nào trong cây. Có ba phương thức mà chúng ta có thể sử dụng để duyệt một cây:

Duyệt tiền thứ tự (Pre-order Traversal)

Duyệt trung thứ tự (In-order Traversal)

Duyệt hậu thứ tự (Post-order Traversal)

Nói chung, chúng ta duyệt một cây để tìm kiếm hay là để xác định vị trí phần tử hoặc khóa đã cho trong cây hoặc là để in tất cả giá trị mà cây đó chứa.

Duyệt trung thứ tự trong cây nhị phân

Trong cách duyệt này, cây con bên trái được truy cập đầu tiên, sau đó là nút gốc và sau đó là cây con bên phải. Bạn nên luôn luôn ghi nhớ rằng mỗi nút đều có thể biểu diễn một cây con.

Nếu một cây nhị phân được duyệt trung thứ tự, kết quả tạo ra sẽ là các giá trị khóa được sắp xếp theo thứ tự tăng dần.

Ở hình ví dụ minh họa trên, A là nút gốc. Với phương thức duyệt trung thứ tự, chúng ta bắt đầu từ nút gốc A, di chuyển tới cây con bên trái B của nút gốc. Tại đây, B cũng được duyệt theo cách thức duyệt trung thứ tự. Và tiến trình tiếp tục cho đến khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt trung thứ tự cho cây trên sẽ là:

D → B → E → A → F → C → G Giải thuật cho cách duyệt trung thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Duyệt các cây con bên trái một cách đệ qui Bước 2: Truy cập nút gốc Bước 3: Duyệt các cây con bên phải một cách đệ qui

Duyệt tiền thứ tự trong cây nhị phân

Trong cách thức duyệt tiền thứ tự trong cây nhị phân, nút gốc được duyệt đầu tiên, sau đó sẽ duyệt cây con bên trái và cuối cùng sẽ duyệt cây con bên phải.

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách thức duyệt tiền thứ tự, đầu tiên chúng ta truy cập chính nút gốc A này và sau đó di chuyển tới nút con bên trái B của nó. B cũng được duyệt theo cách thức duyệt tiền thứ tự. Và tiến trình tiếp tục cho tới khi tất cả các nút đều đã được truy cập. Kết quả của cách thức duyệt tiền thứ tự cây này sẽ là:

A → B → D → E → C → F → G Giải thuật cho cách duyệt tiền thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Truy cập nút gốc Bước 2: Duyệt các cây con bên trái một cách đệ qui Bước 3: Duyệt các cây con bên phải một cách đệ qui

Duyệt hậu thứ tự trong cây nhị phân

Trong cách thức duyệt hậu thứ tự trong cây nhị phân, nút gốc của cây sẽ được truy cập cuối cùng, do đó bạn cần chú ý. Đầu tiên, chúng ta duyệt cây con bên trái, sau đó sẽ duyệt cây con bên phải và cuối cùng là duyệt nút gốc.

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta bắt đầu từ A, và theo cách duyệt hậu thứ tự, đầu tiên chúng ta truy cập cây con bên trái B. B cũng được duyệt theo cách thứ duyệt hậu thứ tự. Và tiến trình sẽ tiếp tục tới khi tất cả các nút đã được truy cập. Kết quả của cách thức duyệt hậu thứ tự của cây con trên sẽ là:

D → E → B → F → G → C → A Giải thuật cho cách duyệt hậu thứ tự

Duyệt cho tới khi tất cả các nút đều được duyệt:Bước 1: Duyệt các cây con bên trái một cách đệ qui Bước 2: Duyệt các cây con bên phải một cách đệ qui Bước 3: Truy cập nút gốc.

Theo Tutorialspoint

Bài trước: Giải thuật tìm kiếm theo chiều rộng

Bài tiếp: Cây tìm kiếm nhị phân (Binary Search Tree)

Cấu Trúc Dữ Liệu Và Giải Thuật (Data Structure And Algorithms): Cấu Trúc Dữ Liệu Là Gì?

Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms): Cấu trúc dữ liệu là gì?

Khái niệm cấu trúc dữ liệu (Data Structure)

Cấu trúc dữ liệu (Data Structure) là gì?

Với các sinh viên chuyên nghành tin học thì cụm từ Cấu trúc dữ liệu (Data Structure) không còn là xa lạ. Đây là một môn học bắt buộc và sẽ là thực sự khó cho bất kỳ sinh viên nào nếu không có sự chuẩn bị kỹ lưỡng và dành cách tiếp cận tích cực cho môn học này. Vậy Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms): Cài đặt môi trường trong cấu trúc dữ liệu

Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.

Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface biểu diễn một tập hợp các phép tính mà một cấu trúc dữ liệu hỗ trợ. Một Interface chỉ cung cấp danh sách các phép tính được hỗ trợ, các loại tham số mà chúng có thể chấp nhận và kiểu trả về của các phép tính này.

Implementation (có thể hiểu là sự triển khai): Cung cấp sự biểu diễn nội bộ của một cấu trúc dữ liệu. Implementation cũng cung cấp phần định nghĩa của giải thuật được sử dụng trong các phép tính của cấu trúc dữ liệu.

Đặc điểm của một Cấu trúc dữ liệu

Chính xác: Sự triển khai của Cấu trúc dữ liệu nên triển khai Interface của nó một cách chính xác.

Độ phức tạp về thời gian (Time Complexity): Thời gian chạy hoặc thời gian thực thi của các phép tính của cấu trúc dữ liệu phải là nhỏ nhất có thể.

Độ phức tạp về bộ nhớ (Space Complexity): Sự sử dụng bộ nhớ của mỗi phép tính của cấu trúc dữ liệu nên là nhỏ nhất có thể.

Tại sao Cấu trúc dữ liệu là cần thiết?

Ngày nay, các ứng dụng ngày càng phức tạp và lượng dữ liệu ngày càng lớn với nhiều kiểu đa dạng. Việc này làm xuất hiện 3 vấn đề lớn mà mỗi lập trình viên phải đối mặt:

Tìm kiếm dữ liệu: Giả sử có 1 triệu hàng hóa được lưu giữ vào trong kho hàng hóa. Và giả sử có một ứng dụng cần để tìm kiếm một hàng hóa. Thì mỗi khi thực hiện tìm kiếm, ứng dụng này sẽ phải tìm kiếm 1 hàng hóa trong 1 triệu hàng hóa. Khi dữ liệu tăng lên thì việc tìm kiếm sẽ càng trở lên chậm và tốn kém hơn.

* Tốc độ bộ vi xử lý: Mặc dù bộ vi xử lý có tốc độ rất cao, tuy nhiên nó cũng có giới hạn và khi lượng dữ liệu lên tới hàng tỉ bản ghi thì tốc độ xử lý cũng sẽ không còn được nhanh nữa.

Đa yêu cầu: Khi hàng nghìn người dùng cùng thực hiện một phép tính tìm kiếm trên một Web Server thì cho dù Web Server đó có nhanh đến mấy thì việc phải xử lý hàng nghìn phép tính cùng một lúc là thực sự rất khó.

Để xử lý các vấn đề trên, các cấu trúc dữ liệu là một giải pháp tuyệt vời. Dữ liệu có thể được tổ chức trong cấu trúc dữ liệu theo một cách để khi thực hiện tìm kiếm một phần tử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập tức.

Độ phức tạp thời gian thực thi trong cấu trúc dữ liệu và giải thuật

Có 3 trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau:

Trường hợp xấu nhất (Worst Case): là tình huống mà một phép tính của cấu trúc dữ liệu nào đó tốn thời gian tối đa (thời gian dài nhất). Ví dụ với ba số 1, 2, 3 thì nếu sắp xếp theo thứ tự giảm dần thì thời gian thực thi sẽ là dài nhất (và đây là trường hợp xấu nhất); còn nếu sắp xếp theo thứ tự tăng dần thì thời gian thực thi sẽ là ngắn nhất (và đây là trường hợp tốt nhất).

Trường hợp trung bình (Average Case): miêu tả thời gian thực thi trung bình một phép tính của một cấu trúc dữ liệu.

Trường hợp tốt nhất (Best Case): là tình huống mà thời gian thực thi một phép tính của một cấu trúc dữ liệu là ít nhất. Ví dụ như trên.

Thuật ngữ cơ bản trong Cấu trúc dữ liệu

Dữ liệu: Dữ liệu là các giá trị hoặc là tập hợp các giá trị.

Phần tử dữ liệu: Phần tử dữ liệu là một đơn vị đơn lẻ của giá trị.

Các phần tử nhóm: Phần tử dữ liệu mà được chia thành các phần tử con thì được gọi là các phần tử nhóm.

Các phần tử cơ bản: Phần tử dữ liệu mà không thể bị chia nhỏ thành các phần tử con thì gọi là các phần tử cơ bản.

Thuộc tính và Thực thể: Một thực thể là cái mà chứa một vài thuộc tính nào đó, và các thuộc tính này có thể được gán các giá trị.

Tập hợp thực thể: Các thực thể mà có các thuộc tính tương tự nhau thì cấu thành một tập hợp thực thể.

Trường: Trường là một đơn vị thông tin cơ bản biểu diễn một thuộc tính của một thực thể.

Bản ghi: Bản ghi là một tập hợp các giá trị trường của một thực thể đã cho.

File: Là một tập hợp các bản ghi của các thực thể trong một tập hợp thực thể đã cho.

Cấu Trúc Dữ Liệu Và Giải Thuật: Ngăn Xếp (Stack) Trong Swift

1. Ngăn xếp(stack) là gì

Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh.

Ngăn xếp có 2 thao tác cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.

Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO(last in first out – Vào sau ra trước)

2. Khởi tạo stack

2.1 . Định nghĩa kiểu dữ liệu stack

Vì stack là 1 dạng đặc biệt của danh sách liên kết nên ta có thể dùng kiểu dữ liệu Node đã trình bày ở bài danh sách liên kết để biểu diễn kiểu dữ liệu của stack

1

2

3

4

5

6

    

var

key

:

T

!

    

var

next

:

Node

?

}

Định nghĩa 1 class Stack với kiểu dữ liệu generic T và 1 node trên cùng gọi là top

1

2

3

4

5

}

2.2. Thêm 1 phần tử vào ngăn xếp (push)

Kiểm tra xem ngăn xếp có nil không, nếu nil thì gán đỉnh ngăn xếp vào phần tử muốn thêm vào.

Nếu đỉnh ngăn xếp không nil, tạo 1 nút mới, gán phần tử muốn thêm vào nút đó, gán đỉnh ngăn xếp vào nút vừa tạo.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

func

push

(

key

:

T

)

{

        

// neu ngan xep chua co dinh

        

if

top

==

nil

{

        

}

        

// neu dinh ngan xep rong

        

if

top

.

key

==

  

nil

{

            

top

.

key

=

key

            

return

        

}

else

{

// khong thi tao 1 nut moi roi gan nut do vao dinh

            

newNode

.

key

=

key

            

newNode

.

next

=

top

            

top

=

newNode

        

}

    

}

2.3. Lấy 1 phần tử ra khỏi danh sách(pop)

Kiểm tra danh sách đỉnh có rỗng không, nếu rỗng thì kết thúc.

Nếu đỉnh danh sách không rỗng, kiểm tra nút đỉnh trỏ đến có rỗng không nếu rỗng thì gán đỉnh danh sách bằng nil( trường hợp danh sách chỉ có 1 phần sau khi lấy 1 phần tử ra thì danh sách trở thành rỗng), còn không gán đỉnh của danh sách vào nút tiếp theo.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

        

// kiem tra xem dinh danh sach co rong khong

        

// neu rong thi ket thuc

        

guard

let

popItem

=

  

top

.

key

else

{

            

return

        

}

        

// kiem tra xem nut tiep theo cua dinh co rong khoong

        

if

let

nextNode

=

top

.

next

{

            

top

=

nextNode

        

}

else

{

            

top

=

nil

        

}

        

return

popItem

    

}

2.4. Xem phần tử đầu danh sách

Kiểm tra xem đỉnh của danh sách có rỗng không, nếu rỗng thì trả về nil còn không trả về giá trị của đỉnh danh sách.

1

2

3

4

5

6

7

8

9

10

11

12

        

// kiem tra xem dinh dach sach co rong khong

        

guard

let

topItem

=

top

.

key

else

{

            

// neu rong thi tra ve nil

            

return

nil

        

}

        

// con khong tra ve gia tri dinh danh sach

        

return

topItem

    

}

2.5. Test thử danh sách

2.5.1. Test build stack

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

func

buildStack

(

)

{

        

let

numberList

=

[

1

,

4

,

7

,

9

,

10

,

12

,

20

]

        

for

number

in

numberList

{

            

stack

.

push

(

number

)

        

}

        

printStack

(

)

    

}

    

func

printStack

(

)

{

        

var

top

=

stack

.

top

        

print

(

top

.

key

)

        

while

top

.

next

!=

nil

{

            

top

=

top

.

next

            

print

(

top

.

key

)

        

}

    

}

2.5.2. Test push stack

1

2

3

4

5

6

7

func

pushStack

(

)

{

        

stack

.

push

(

40

)

        

printStack

(

)

    

}

2.5.3 Test pop stack

1

2

3

4

5

6

func

popStack

(

)

{

        

let

item

=

stack

.

pop

(

)

        

print

(

item

)

    

}

3. Một số ứng dụng của ngăn xếp

3.1. Đảo ngược xâu ký tự

Bài toán đảo ngược xâu ký tự yêu cầu hiển thị các ký tự của 1 xâu ký tự theo chiều ngược lại.

Ký tự cuối cùng của xâu sẽ được hiển thị trước, tiếp theo là ký tự sát ký tự cuối … và ký tự đầu tiên sẽ được hiển thị đầu tiên.

Để giải quyết bài toán, ta chỉ cần duyệt từ đầu đến cuối xâu, lần lượt cho các ký tự vào ngăn xếp.

Khi đó, các ký tự đầu tiên sẽ vào trước, tiếp theo đến ký tự thứ 2 … ký tự cuối cùng vào sau cùng. Sau khi đã cho toàn bộ ký tự của xâu vào ngăn xếp, lần lượt lấy các phần tử ra khỏi ngăn xếp và hiển thị lên màn hình.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

        

for

s

in

stringInput

.

characters

{

            

stringStack

.

push

(

String

(

s

)

)

        

}

        

var

newString

=

“”

        

var

item

=

stringStack

.

top

        

newString

+=

item

.

key

        

while

item

.

next

!=

nil

{

            

item

=

item

.

next

            

newString

+=

item

.

key

        

}

        

return

newString

    

}

3.2. Tính giá trị biểu thức dạng hậu tố

3.2.1. Bài toán

Một biểu thức toán học thông thường bao gồm các toán tử: + – * / , các toàn hạng và dấu ngoặc cho biết thứ tụ tính toán.

Chẳng hạn 1 biểu thức toán học: (3 * (((5 – 2) * (7 + 1)) – 6)) Như chúng ta đã thấy trong biểu thức trên , các toán tử bao h cũng nằm giữa 2 toàn hạng. Do vậy, cách viết trên được gọi là cách viết trung tố (infix). Để tính toán giá trị biểu thức trên, ta phải tính toán giá trị các phép toán trong ngoặc trước. Đôi khi ta cần lưu các kết quả tính toán này như 1 kết quả trung gian, sau đó sử dụng chúng như toán hạng tiếp theo. Ví dụ ở biểu thức trên, đầu tiên ta tính 5 – 2 = 3, lưu kết quả này lại. Trong các biểu thức dạng này, vị trí dấu ngoặc rất quan trọng. Nếu vị trí các dấu ngoặc thay đổi thì giá trị biểu thức cũng thay đổi theo. Đối với con người, cách trình bày biểu thức toán học theo dạng này có vẻ như là hợp lý nhất, nhưng đối với máy tính, việc tính toán nhũng biểu thức như vậy là tương đối phức tạp. Để dễ dạng cho máy tính trong việc tính toán các biểu thức, người ta đưa ra 1 cách trình bày khác cho biểu thức toán học, đó là dạng hậu tố (postfix).

Theo cách trình bày nay, toán tử không nằm giữa 2 toán hạng mà nằm ở ngay phía sau 2 toán hạng. Chẳng hạn ở biểu thức trên ta có thể viết dưới dạng hậu tố như sau: 3 5 2 – 7 1 + * 6 – * Toán tử – nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 – 2 = 3, lưu kết quả 3. Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8. Toán tử * nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24. Toán tử – nằm ngay sau kết quả vừa lưu và 6 nên lấy 24 – 6 = 18 Toán tử * nằm ngay sau kết quả vừa lưu và 3 nên lấy 3 * 18 = 54 là kết quả cuối cùng của biểu thức.

3.2.2. Cách thực hiện

Chuyển đổi biểu thức tiền tố sang hậu tố:

Duyệt từ trái qua phải.

Nếu gặp dấu mở ngoặc thì bỏ qua.

Nếu gặp số thì đưa vào biểu thức mới.

Nếu gặp toán tử thì đưa vào ngăn xếp.

Nếu gặp dấu đóng ngoặc thì lấy toán tử ra đưa vào biểu thức mới.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

        

var

postfixExpression

=

“”

        

for

s

in

infixExpression

.

characters

{

            

let

x

=

String

(

s

)

            

if

numbers

.

rangeOfString

(

x

)

!=

nil

{

                

postfixExpression

+=

x

            

}

else

if

operators

.

rangeOfString

(

x

)

!=

nil

{

                

stackOperator

.

push

(

x

)

            

}

else

if

x

==

“)”

{

// gap dau dong ngoac lay toan tu ra dua vao bieu thuc moi

                

let

_operator

=

stackOperator

.

pop

(

)

                

postfixExpression

+=

_operator

!

            

}

else

{

// dau mo ngoac bo qua

            

}

        

}

        

return

postfixExpression

    

}

Tính toán biểu thức hậu tố:

Tính toán biểu thức hậu tố:

Duyệt biểu thức từ trái qua phải.

Nếu gặp toán hạng thì đưa vào ngăn xếp.

Nếu gặp toán tử, lấy ra 2 toán hạng từ ngăn xếp, sử dụng toán tử để tính, sau đó đưa kết quả vào ngăn xếp.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

func

calculateInfixExpression

(

)

{

        

let

infixExpression

=

“(3*(((5-2)*(7+1))-6))”

        

let

postfixExpression

=

convertInfixToPostfixExpression

(

infixExpression

)

        

for

s

in

postfixExpression

.

characters

{

            

let

x

=

String

(

s

)

            

if

numbers

.

rangeOfString

(

x

)

!=

nil

{

                

resultStack

.

push

(

Int

(

x

)

!

)

            

}

else

if

operators

.

rangeOfString

(

x

)

!=

nil

{

                

let

number1

=

resultStack

.

pop

(

)

!

                

let

number2

=

resultStack

.

pop

(

)

!

                

let

result

=

calculate

(

number1

,

number2

:

number2

,

_operator

:

x

)

                

resultStack

.

push

(

result

)

            

}

else

{

            

}

        

}

        

print

(

resultStack

.

top

.

key

)

    

}

4. Demo

https://github.com/pqhuy87it/MonthlyReport

5. Tài liệu tham khảo

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html

Via Viblo

DVMS chuyên:

– Tư vấn, xây dựng, chuyển giao công nghệ Blockchain, mạng xã hội,… – Tư vấn ứng dụng cho smartphone và máy tính bảng, tư vấn ứng dụng vận tải thông minh, thực tế ảo, game mobile,… – Tư vấn các hệ thống theo mô hình kinh tế chia sẻ như Uber, Grab, ứng dụng giúp việc,… – Xây dựng các giải pháp quản lý vận tải, quản lý xe công vụ, quản lý xe doanh nghiệp, phần mềm và ứng dụng logistics, kho vận, vé xe điện tử,… – Tư vấn và xây dựng mạng xã hội, tư vấn giải pháp CNTT cho doanh nghiệp, startup,…

Cấu Trúc Dữ Liệu Và Giải Thuật (Data Structure And Algorithms) Cơ Bản

Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms) là một trong những khối lượng kiến thức quan trọng nhất trong bất cứ chương trình học nào của sinh viên các ngành công nghệ thông tin. Bạn đã được nghe các bậc tiền bối ở đâu đó nói rằng, học lập trình bắt buộc phải học cấu trúc dữ liệu và giải thuật, điều này không hẳn nhưng lại là yếu tố tiên quyết để bạn đi được xa hơn trên con đường này. Đây là một khía cạnh kiến thức khó cho bất kỳ ai mới học nhưng lại là yếu tố cốt lõi trong mọi chương trình. Bạn có thể học một ngôn ngữ lập trình mới thành thạo trong chưa đầy một tháng nhưng để vận dụng nó tốt thì rất cần nắm vững các yếu tố đặc trưng của nó thể hiện ở các cấu trúc dữ liệu mà nó hỗ trợ, cách thức quản lý cấu trúc dữ liệu đó và các lớp giải thuật hỗ trợ sẵn có trong nó cũng như quan trọng hơn là cách thức để triển khai các thuật toán để giải quyết các vấn đề bằng ngôn ngữ lập trình đó.

Cấu trúc dữ liệu cơ bản

Cấu trúc dữ liệu là gì? Tổng quan về cấu trúc dữ liệu

Cấu trúc dữ liệu mảng và những vấn đề cần biết

Danh sách liên kết và các thao tác trên danh sách liên kết

Danh sách liên kết đơn, sự khác biệt giữa danh sách liên kết và mảng

Danh sách liên kết đôi và các đặc điểm

Danh sách liên kết vòng và ứng dụng

Ngăn xếp và các thao tác trên ngăn xếp

Cấu trúc dữ liệu hàng đợi và các thao tác cơ bản

Một số kiểu hàng đợi

Circular Queue và ứng dụng

Priority Queue (Hàng đợi ưu tiên)

Deque và các phép toán trên Deque

Bảng băm và ứng dụng của bảng băm

Các cấu trúc dữ liệu dạng cây

Cấu trúc dữ liệu cây và ứng dụng

Duyệt cây và thứ tự duyệt cây

Cây nhị phân và các kiểu cây nhị phân

Cây nhị phân tìm kiếm và các ứng dụng

Cây AVL và các thao tác cơ bản trên cây AVL

Splay Tree và ứng dụng

B-Tree và ứng dụng của B-tree

B+ tree và ứng dụng

Cây đỏ đen (Red-Black Tree) và ứng dụng

Cấu trúc dữ liệu Heap và các phép toán

Cấu trúc dữ liệu đồ thị

Cấu trúc dữ liệu đồ thị (Graph) và ứng dụng

Cây khung và cây khung nhỏ nhất trong đồ thị

Thuật toán Tarjan trong tìm thành phần liên thông mạnh

Thuật toán BFS – Tìm kiếm theo chiều rộng trên đồ thị

Thuật toán DFS – Tìm kiếm theo chiều sâu trên đồ thị

Biểu diễn đồ thị bằng ma trận kề và danh sách kề

Thuật toán tổng quan

Thuật toán là gì? Mối liên hệ giữa cấu trúc dữ liệu và thuật toán

Độ phức tạp tính toán

Phân tích thiết kế thuật toán

Thuật toán tham lam (Greedy Algorithms)

Thuật toán chia để trị (Divide and Conquer)

Quy hoạch động (Dynamic Programming)

Thuật toán quay lui (Back Tracking)

Đệ quy và ước lượng độ phức tạp đệ quy bằng định lý thợ (Master Theorem)

Các giải thuật tìm kiếm

Thuật toán tìm kiếm tuyến tính

Thuật toán tìm kiếm nhị phân

Tìm kiếm nội suy

Các giải thuật sắp xếp

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chọn (Selection Sort)

Thuật toán Insertion Sort (sắp xếp chèn)

Merge Sort (sắp xếp trộn)

Quick sort (sắp xếp nhanh)

Counting Sort (sắp xếp đếm)

Radix Sort (sắp xếp theo cơ số)

Bucket Sort (sắp xếp theo khối)

Heap Sort (sắp xếp vun đống)

Shell Sort (ứng dụng của sắp xếp chèn)

Các thuật toán đối sánh mẫu, tìm xâu con

Thuật toán Knuth-Morris-Pratt trong tìm kiếm xâu con

Thuật toán Boyer-Moore trong tìm kiếm xâu con

Thuật toán Rabin-Karp ứng dụng trong đối sánh mẫu

Thuật toán Wu-Manber trong đối sánh đa mẫu

Thuật toán Aho-Corasick trong đối sánh đa mẫu

Các thuật toán trên đồ thị

Thuật toán Dijkstra và các cách thực thi

Thuật toán Bellman-Ford cho đồ thị có trọng số âm

Thuật toán Floyd-Warshall cho đồ thị dầy

Thuật toán Johnson cho đồ thị thưa

Cập nhật thông tin chi tiết về Duyệt Cây Trong Cấu Trúc Dữ Liệu Và Giải Thuật trên website Nhatngukohi.edu.vn. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Chúc bạn một ngày tốt lành!