Please enable JavaScript.
Coggle requires JavaScript to display documents.
Cấu trúc dữ liệu và giải thuật - Coggle Diagram
Cấu trúc dữ liệu và giải thuật
Thuật toán đệ quy
Đệ quy
Đệ quy quay lui
Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo. Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xóa bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại.
Đệ quy nhị phân
Mỗi lần thực thi có thể gọi đệ quy lần 2
Đệ quy lồng
Tham số trong lời gọi đệ quy là một lời gọi đệ quy. Đệ quy lồng chiếm bộ nhớ rất nhanh
Đệ quy tuyến tính
Mỗi lần thực thi chỉ gọi đệ quy một lần
Đệ quy hỗ tương
Các hàm gọi đệ quy lẫn nhau
Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa.
Hàm đệ quy gồm 2 phần:
Phần cơ sở: điều kiện thoát khỏi đệ quy
Phần đệ quy: thân hàm có chứa lời gọi đệ quy.
Đệ quy có ưu điểm là thuận lợi cho việc biểu diễn bài toán, đồng thời làm gọn chương trình. Tuy nhiên nó không tối ưu về mặt thời gian so với vòng lặp, gây tốn bộ nhớ.
Tham số hóa bài toán: Đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tới trường hợp suy biến.
Tìm trường hợp suy biến.
Cấu trúc dữ liệu cây
Cấu trúc cây là một tập hợp các phần tử gọi là nút, mỗi cây có một nút gốc, chứa nhiều nút con, mỗi nút con lại là một tập hợp các nút khác gọi là cây con.
Bậc của nút: Là số nút con của nút đó
Bậc của cây:là bậc lớn nhất của nút trong cây đó, cây bậc n sẽ được gọi là cây n - phân.
Độ dài đường đi lên nút x
Cây nhị phân
Cây nhị phân là một trường hợp đặc biệt của cấu trúc cây và nó cũng phổ biến nhất. ĐÚng như tên gọi của nó, cây nhị phân có bậc là 2 và mỗi nút trong cây nhị phân đều có bậc không quá 2.
Cây nhị phân đúng: là cây nhị phân mà mỗi nút của nó đều có bậc 2
Cây nhị phân đầy đủ là cây nhị phân có mức của các nút là đều bằng nhau.
Cấu trúc nút
Thành phần dữ liệu: có thể là bất kì kiểu dữ liệu nào
Thành phần liên kết trái: lưu trữ địa chỉ của nút gốc của cây con bên trái. Kiểu dữ liệu là cin trỏ trỏ vào node
Thành phần liên kết phải: lưu trữ địa chỉ của nút gốc cây con bên phải. Kiểu dữ liệu là con trỏ trỏ vào node
Cấu trúc cây
Để quản lý một cái cây, bản chỉ cần quản lý được nút gốc, bạn có thể đi được đến các nhánh và lá của nó từ đó.
Bản chất là nó sẽ tạo cho bạn một con trỏ có thể trỏ vào một node
Vì nó là con trỏ nên các bạn gắn nó bằng NULL để tránh lỗi
Duyệt cây nhị phân tìm kiếm
Cây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành các phần tư của cây con bên phải đều lớn hơn phần tử hiện hành.Do tính chất này,cây nhị phân tìm kiếm không được có phần tử cùng giá trị.
Nhờ vào tính chất đặc biệt này, cây nhị phân tìm kiếm được sử dụng để tìm kiếm phần tử nhanh hơn.
Duyệt cây nhị phân
Duyệt tiền tự: duyệt nút gốc, duyệt tiền tự cây con trái, duyệt tiền tự cây con phải
Duyệt trung tự:duyệt trung tự cây con trái, duyệt nút gốc, duyệt trung tự cây con phải.
Duyệt hậu tự: duyệt hậu tự cây con trái, duyệt hậu tự cây con phải, duyệt nút gốc.
Stack
Danh sách liên kết đơn
Việc bổ sung một phần tử vào Stack tương đương với việc thêm một phần tử vào cuối danh sách. Việc loại bỏ một phần tử trong Stack cũng tương đương với việc loại bỏ một phần tử ở cuối danh sách.
Stank bị tràn khi vùng không gian nhớ dùng cho các biến động không còn đủ đê thêm một phần tử mới. Tuy nhiên việc kiểm tra này rất khó bởi nó phụ thuộc vào máy tính và ngôn ngữ lập trình.
Khi cài đặt ta có thể bỏ qua việc kiểm tra Stack tràn
Mảng
Một ngăn xếp là một cấu rtusc dữ liệu dạng thùng chứa của các phần tử
Việc bổ dung một phần tử vào Stank tương đương với việc thêm một phần tử ở cuối mảng. Việc loại bỏ một phần tử khỏi Stank tương đương với việc loại bỏ một phần tử ở cuối mảng
Dễ dàng cài đặt, tiết kiệm bộ nhớ. Không dynamic, không thể tăng hoặc giảm stank tại thời điểm run time
Stank sẽ bị tràn nếu bổ sung vào mảng đã đầy. Stank là rỗng khi số phân tử thực sự đang chứa trong mảng = 0
Cấu trúc dữ liệu đồ thị
Thao tác xử lý
B1: Kiểm tra xem phần tử có trong đồ thị hay không
B2: Duyệt qua đồ thị
B3: Thêm các phần tử
B4: Tìm đường đi từ đỉnh này sang đỉnh khác
Một đồ thị là một dạng biểu diễn hình ảnh của một tập hợp các đối tượng, trong đó các cặp đối tượng được kết nối bởi các link
Các đối tượng được nối liền nhau được biểu diễn bởi các điểm được gọi là các cạnh.
Đỉnh: Mỗi nút của hình được biểu diễn như là một đỉnh. Trên các hình tròn biểu diễn các đỉnh. Do đó, các điểm từ A tớ G là các đỉnh.
Cạnh: Cạnh biểu diễn một đường nối 2 đỉnh
Kề nhau: Hai đỉnh là kề nhau nếu chúng được kết nối với nhau thông qua một cạnh.
Đường: Đường biểu diễn một dãy các cạnh giữa 2 đỉnh
Biểu diễn đồ thị
Ma trận kề
Ma trận kề là một mảng 2D gồm các đỉnh V x V.
Việc tra cứu cạnh là cực kì nhanh chóng trong biểu diễn ma trận kề nhưng chúng ta phải dành không gian cho mọi liên kết có thể có giữa tất cả các đỉnh, vì vậy nó đòi hỏi nhiều không gian hơn
Danh sách kề
Danh sách kề biểu thị một biểu đồ dưới dạng một mảng các danh sách đươc liên kết. Chỉ số của mảng đại diện cho một đỉnh và mỗi phần tử trong danh sách liên kết của nó đại diện cho các đỉnh khác tạo thành một cạnh với đỉnh.
Danh sách kề là hiệu quả về mặt lưu trữ vù chúng ta chỉ cần lưu trữ các giá trị cho các cạnh. Đối với một đồ thị có hàng triệu đỉnh, điều này có nghĩa là rất nhiều không gian được tiết kiệm.
GIải thuật tìm kiếm
Giải thuật tìm kiếm theo chiều sâu
Là giải thuật duyệt hoặc tìm kiếm thoe một cây hoặc một đồ thị và sử dụng strack để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kì vòng lặp nào.
Giải thuật tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.
Giải thuật tìm kiếm theo chiều rộng
Giải thuật tìm kiếm theo chiều rộng duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kì vòng lặp nào.
Set, map, Hash table
Set
Laf một dạng cấu trúc dữ liệu dùng để lưu trữ các phần tử không trùng lặp và được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
Về mặt tốc độ xử lý thì set có khả năng thêm, xóa, tìm kiếm dữ liệu với tốc độ cực cao là O, và nó còn cao hơn cả vector với tốc là O. Tuy nhiên thì do các phần tử được quản lý dạng cây nhị phân nên tốc dộ truy cập ngẫu nhiên tới một phần tử chỉ định trong set là cực thấp.
Mặc định trong set là tăng dần và chúng ta có thể viết lại hàm so sánh theo mục đích của chúng ta
Set trong C++ giống như môt mảng với cả phần tử không trùng lặp và được sắp xếp.
Map
Là một kiểu dữ liệu với mỗi phần tử là ánh xạ giữa yếu tố key với giá trị của nó.
Tương tự set, map không chứa hai phần tử nào giống nhau và các phần tử trong mao được sắp xếp theo một thứ tự nào đó. Mỗi p hần tử trong map có yếu tố key dùng để xác định value của nó.
Key và value có thể có kiểu khác nhau.
Tree map
Map được cài bằng cây đỏ đen. Mỗi một node trong cây có một key và một value, trỏ vào 2 node bên trái và bên phải. Giá trị key của node bên trái nhỏ hơn giá trị key ở node cha và nhỏ hơn giá trị key ở node bên phải.
Độ phức tạp thuật toán của các phép toàn thêm mổ node, lấy ra giá trị của mổ key là O.
Hash map
Map được cài đặt trên nguyên lý Hashing - băm. Để hiểu về Hasing, chúng ta cần nắm được 3 khái niệm. Hash function, hash value và bucket.
Hash function, hay còn gọi là hàm băm, là một hàm mà khi ta lấy đầu vào là một giá trị bất kì thì ở đầu ra, hash function sẽ cho ta một code - được gọi là hash value. mỗi đầu vào chỉ có duy nhất một hash value.
Bucket là nơi mà chúng ta lưu trữ các cặp value. Đô phức tạp thuật toán phép thêm và lấy dữ liệu là O
Hash table
Bảng băm hay Hash table là một cấu trúc mà khi người dùng thực hiện truy xuất một phần từ qua khóa thì nó sẽ được phản xạ vào thông qua hàm băm.
Quá trình ánh xạ khóa vào bảng băm được thực hiện thông qua hàm băm. Một bảng băm tốt cần phải có hàm băm tốt. Bảng băm là một mảng có M bị trí được đánh số từ 0 đến M-1
Hàm băm
Hàm băm hay là hash function là hàm thực hiện việc ánh xạ khóa k nào đó vào trong bảng băm.
Tốc độ tính toán nhanh. Các khóa được phân bố đều trong bảng ít xảy ra đụng độ
Đối với dữ liệu lớn, việc cấp phát một mảng quá lớn sẽ gây lãng phí bộ nhớ không đáng có, tuy nhiên, việc M lớn đảm bảo việc đụng độ ít xảy ra do các khóa phân bố đều. Ngược lại, nếu M nhỏ để tiết kieehm bộ nhớ, việc này sẽ làm giảm hiệu suất của bảng năm do việc đụng độ xảy ra với tần suất cao hơn
Cần phải cân nhắc giữa hiệu suất và dung lượng lưu trữ
Queue
Danh sách liên kết đơn
Gồm 2 con trỏ: 1 con trỏ chỉ đầu danh sách và 1 con trỏ chỉ đến cuối danh sách
Quản lý bằng 2 con trỏ với thao tác. Thêm cuối - lấy đầu
Có thể dễ dàng thay đổi kích thước của queue tại thời điểm run time.Nhưng lại tốn thêm bộ nhớ để lưu trữ con trỏ.
Nếu trong Queue không tồn tại phần tử nào thi phần tử được thêm vào chính là pHead và pTail. Ngược lại, nếu trong Queue đã tồn tại phần tử thì ta cho pNext của pTail trỏ tới node p.
Mảng
Cần có hai chỉ số front và rear để lưu chỉ số phần tử đầu và chỉ số phần tử cuối trong queue. Khởi tạo queue rỗng thì front = 0 và rear =-1
Để thêm một phần tử vào queue, ta tăng rear lên 1 và đưa giá trị vào đó vào phần tử thứ rear trong mảng. Để loại bỏ một phần tử khỏi queue, ta tăng front lên 1.
Khi front > rear thì queue đang rỗng. Khi rear tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, khôn gtheer thêm phần tử vào nữa
Khi sử dụng mảng để cài đặt queue, chỉ số rear và front chỉ tăng lên chứ không giảm đi, kể cả khi lấy các phần tử ra khỏ hàng đợi.Hơn nữa, nếu chỉ số rear tăng lên vượt quá số lượng phân tử cho phép trong mảng thì queue cũng bị tràn, không thể thêm phần tử vào queue nữa
Mảng
Mảng có thể lưu giữa một số phần tử cố định và các phần tử này nên có cùng kiểu. Hầu hết các cấu trúc dữ liệu đều sử dụng mảng để triển khai giải thuật
Mảng có kích thước cố định các phần tử được lưu trong các ô nhớ liên kết tiếp nhau hoặc lưu theo cách có thể tính được bị trí của các phần tử bằng một biểu thức toán học.
Nếu như chỉ cần sử dụng các ô nhớ này, việc thêm phần tử sẽ diễn ra rất nhanh và độ phức tạp chỉ là O
Mảng động
Thể hiện rõ sự khác biệt so với mảng chỉnh là kích thước của nó có thể thay đổi được. Khi làm việc với mảng, ta không thể thêm hay xóa phần tử trong mảng, còn với mảng động thì có thể.
Nếu phải cấp phát lại bộ nhớ thì độ phức tạp lúc này lại là O vì cần phải thao tsac sao chép n phần tử
Danh sách liên kết
Gồm 3 loại danh sách liên kết: danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng.
Là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong danh sách. Mỗi node sẽ lưu trữ dữ liệu của node đó và địa chỉ của node kế tiếp.
Chỉ có thể tìm kiếm tuyến tính
Kích thước thay đổi trong quá trình thêm/ xóa phần tử. Kích thước tối đa phụ thuộc vào bộ nhớ.
Bộ nhớ được cấp phát trong quá trình chạy
Được lưu trữ trên các ô nhớ ngẫu nhiên
Truy cập phần tử ngẫu nhiên cần phải duyệt từ đầu đến cuối phần tử đó O
Thuật toán tìm kiếm
Thuật toán tìm kiếm tuyến tính
Mỗi phần tử đều được kiểm tra và nếu tìm thấy bất kỳ kết nối nào thì phần tử cụ thể đó được trả về; nếu không tìm thấy thì quá trình tìm kiếm tiếp tục diễn ra cho tới khi tìm kiếm hết dữ liệu.
Thuật toán tìm kiếm nhị phân
So sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Nếu phần tử cần tìm là lơn hơn giá trị phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa, nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ tiếp tục như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này
Thuật toán tìm kiếm nội suy
Tìm kiếm nội suy là biến thế cải tiến của Tìm kiếm nhị phân. Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp và dò được vị trí nội suy
Thuật toán sắp xếp
Bubble Sort
So sánh 2 phần tử kế tiếp nhau lần lượt đến hết mảng. Phần tử nào lớn hơn sẽ đổi vị trí sau, cứ tiếp tục vậy cho đến khi mảng được sắp xếp
Insertion
Không yêu cầu thêm bất kỳ bộ nhớ phụ và việc sắp xếp được tiến hành trong chính phần bộ nhớ đã khai báo trước đó
Một danh sách con luôn luôn được duy trì dưới dạng đã sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp soa cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O với n là số phần tử
Selection Sort
Danh sách được chi hành hai phần, phần được sắp xếp ở bên trái và phần chưa được sắp xếp ở bên trái
Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắ xếp và được tráo đổi vơi phần bên trái nhất và phần tử đó trở thành phần tử của mảng được sắp xếp. Tiến trình này tiếp tục cho tới khi toàn bộ từng phần tử trong mảng chưa được sắp xeeso đều được di chuyển sang mảng đã được sắp xếp
Giải thuật này không phù hợp với tập dữ liệu lớn khi mà độ phức tạo trường hợp xấu nhất và trường hợp trung bình là O với n là số phần tử