Thực đơn
trang chủExcel

Cấu trúc dữ liệu. Khái niệm về cơ sở dữ liệu và ngân hàng dữ liệu. Phân loại cơ sở dữ liệu. Các loại mô hình dữ liệu: phân cấp, mạng, quan hệ. Các loại và cấu trúc dữ liệu

Có những loại cấu trúc dữ liệu nào? (Bạn có thể cho biết tên cấu trúc bằng ngôn ngữ lập trình cụ thể) Tôi muốn biết mục đích, điểm mạnh và mặt yếu. Tôi cũng quan tâm đến việc phân loại, nó có được viết chính xác trên wiki không? Danh sách các cấu trúc dữ liệu Chưa cần có câu trả lời chi tiết cho từng cấu trúc, chỉ cần nói ngắn gọn, chẳng hạn, cho biết ưu điểm của cấu trúc này so với các cấu trúc khác là gì (ví dụ: thời gian nhanh chóng quyền truy cập vào một phần tử, khả năng tự động thay đổi dung lượng bộ nhớ, v.v.) Có thể bạn không nên trả lời mọi thứ cùng một lúc, đột nhiên khối lượng câu trả lời sẽ rất đáng kể, bạn có thể hủy đăng ký ít nhất một trong các cấu trúc mà bạn biết rõ, và tôi sẽ thêm thông tin vào bài viết chính. Sẽ rất thuận tiện khi có một danh sách như vậy trước mắt bạn, bạn có thể kiểm tra ngay và chọn những gì bạn cần.

1. Cấu trúc dữ liệu tuyến tính là các cấu trúc dữ liệu trong đó việc chuyển đổi từ phần tử dữ liệu này sang phần tử dữ liệu khác không phụ thuộc vào bất kỳ điều kiện logic, I E. trong cấu trúc tuyến tính chỉ sử dụng các kết nối vô điều kiện của các phần tử.

1.1 Danh sách Có thể giống như một mảng nhưng cho phép bạn thêm các phần tử vào bất kỳ vị trí nào, xóa các phần tử khỏi bất kỳ vị trí nào và lấy số phần tử hiện tại.

1.2 Mảng kết hợp

1.3 Bảng băm là một mảng thông thường có địa chỉ bất thường được chỉ định bởi hàm băm. Sự lựa chọn tốt nhất nếu bạn không cần sắp xếp thông tin mà chỉ truy cập nhanhĐến cô ấy. Bộ nhớ bổ sung bị lãng phí.

thuận lợi:

  • Một đặc tính quan trọng của bảng băm là, theo một số giả định hợp lý, cả ba thao tác (tra cứu, chèn, xóa phần tử) đều được hoàn thành trong thời gian trung bình là O(1), với thời gian trong trường hợp xấu nhất là O(n).

sai sót:

  • Lặp lại không theo thứ tự tăng dần của các phím
  • Sự cần thiết phải “làm lại” khi số lượng đối tượng được lưu trữ tăng lên (?)
  • không thể triển khai các hoạt động bổ sung chạy nhanh MIN, MAX và thuật toán duyệt qua tất cả các cặp được lưu trữ theo thứ tự tăng dần hoặc giảm dần của các khóa (?)
  • không duy trì thứ tự và không bảo toàn thứ tự của các phần tử (?)
  • khả năng va chạm

dạng mô tả chung của cấu trúc:

Mục đích chính, mô tả

Hoạt động được hỗ trợ

Thuận lợi

sai sót

Triển khai sẵn sàng bằng ngôn ngữ lập trình (tên hàm hoặc lớp)

biểu tượng

(?) - nghi ngờ, nếu viết sai vui lòng sửa lại hoặc ngược lại, xác nhận để loại bỏ sự mơ hồ.

chỉnh sửa tiếp tục...

Chủ đề của bài viết này một lần nữa liên quan đến lý thuyết lập trình, vì vậy bạn sẽ phải sử dụng nhiều cách phân loại khác nhau và vận hành theo thuật ngữ toán học. Cấu trúc dữ liệu thực tế là điều đầu tiên được dạy trong các khóa đào tạo. Đánh giá độ phức tạp của thuật toán là vấn đề thứ hai. Có vẻ như hai vấn đề này có rất ít mối liên hệ, nhưng thực tế không phải vậy, và khi câu chuyện tiến triển thì sẽ rõ lý do tại sao. Tôi sẽ không đi vào chi tiết, vì thực tế cho thấy rằng trong quá trình tích lũy kinh nghiệm, chỉ những điều quan trọng nhất vẫn còn trong đầu bạn. Theo tôi, điều này xảy ra ở bất kỳ lĩnh vực hoạt động nào. Tôi sẽ cố gắng phác thảo những gì còn đọng lại trong đầu tôi về những vấn đề này.

Phân loại cấu trúc dữ liệu

Cấu trúc dữ liệu là một hình thức lưu trữ và trình bày thông tin. Định nghĩa rất mơ hồ nên các chuyên gia sử dụng nhiều hình thức phân loại và làm rõ khác nhau. Cấu trúc dữ liệu có thể đơn giản hoặc phức tạp: chúng đại diện cho một đơn vị thông tin nguyên tử hoặc một tập hợp dữ liệu cùng loại. Cấu trúc dữ liệu đơn giản được đặc trưng bởi, ví dụ, số nguyên, số thực, logic, dạng văn bản vân vân. Cấu trúc dữ liệu phức tạp được chia thành các tập động và tĩnh. Năng động trong quá trình vòng đời cho phép bạn thay đổi kích thước của chúng (thêm và xóa các phần tử), nhưng các phần tử tĩnh thì không. Và cuối cùng, theo cách tổ chức mối quan hệ giữa các phần tử của cấu trúc dữ liệu phức tạp, có sự phân loại như sau:

  • tuyến tính
    • Mảng
    • Danh sách
    • Danh sách liên quan
    • Xếp hàng
    • Bảng băm
  • Thứ bậc
    • Cây nhị phân
    • Cây N-ary
    • Danh sách phân cấp
  • Mạng
    • Đồ thị đơn giản
    • đồ thị có hướng
  • dạng bảng
    • Bảng cơ sở dữ liệu quan hệ
    • Mảng hai chiều
  • Khác

    • Sự phân loại ở trên vẫn chưa hoàn chỉnh. Các phần tử của cấu trúc dữ liệu phức tạp có thể vừa là thể hiện của cấu trúc dữ liệu đơn giản vừa là thể hiện của cấu trúc dữ liệu phức tạp, ví dụ như cấu trúc dữ liệu rừng là danh sách các cây rời rạc. Bây giờ tôi sẽ cố gắng đưa ra Mô tả ngắn các lớp được liệt kê của cấu trúc dữ liệu phức tạp. Cấp độ phân loại đầu tiên dựa trên sự khác biệt trong cách xác định và tìm kiếm các phần tử riêng lẻ trong một tập hợp các cấu trúc dữ liệu phức tạp.

    Cấu trúc dữ liệu tuyến tính

    Một phần tử của cấu trúc dữ liệu tuyến tính được đặc trưng bởi số sê-ri hoặc chỉ mục trong chuỗi các phần tử tuyến tính.

    Mảng– cái này ở trong tĩnh cấu trúc tuyến tính cùng loại dữ liệu, được tối ưu hóa cho các hoạt động tìm kiếm một phần tử theo chỉ mục của nó. Vị trí rõ ràng của một phần tử trong bộ nhớ được đảm bảo chính xác bởi cùng loại phần tử trong mảng và được xác định bằng tích của chỉ mục của nó với kích thước bộ nhớ mà một phần tử chiếm giữ.

    Mảng dòng.
    Địa chỉ (phần tử (chỉ mục)) = cell_size * index.

    Danh sách– là cấu trúc dữ liệu tuyến tính động trong đó mỗi phần tử chỉ tham chiếu đến phần tử trước đó – danh sách tuyến tính một chiều, hoặc đến cái trước và cái tiếp theo sau nó - danh sách tuyến tính kép. Ưu điểm của cấu trúc dữ liệu này ngoài khả năng thay đổi kích thước là dễ thực hiện. Ngoài ra, do có các tham chiếu, mỗi phần tử trong danh sách, không giống như mảng, có thể chiếm một lượng bộ nhớ khác nhau. Địa chỉ của phần tử đầu tiên trong danh sách tuyến tính được xác định duy nhất bởi địa chỉ của chính danh sách đó.

    Danh sách liên quan là một biến thể của danh sách tuyến tính thông thường, được tối ưu hóa cho các hoạt động thêm và xóa phần tử. Sự tối ưu hóa là các phần tử danh sách liên kết không nhất thiết phải được định vị lần lượt trong bộ nhớ. Thứ tự của các phần tử được xác định bằng tham chiếu đến phần tử đầu tiên (không nhất thiết phải ở đầu bộ nhớ được phân bổ cho danh sách) và chuỗi tham chiếu đến các phần tử còn lại của danh sách.


    Danh sách liên quan.

    Cây rơm là một cấu trúc dữ liệu tuyến tính động trong đó chỉ có hai thao tác để thay đổi một tập hợp các phần tử được xác định: thêm một phần tử vào cuối và xóa phần tử cuối cùng. Họ cũng nói rằng ngăn xếp thực hiện nguyên tắc LIFO (Vào sau, ra trước) - đến sau cùng và rời đi trước. Ví dụ, trong quá trình thực hiện Mã chương trình, máy tính, khi cần gọi một thủ tục hoặc hàm, trước tiên sẽ đặt một con trỏ đến vị trí mà nó được gọi trên ngăn xếp, để khi quá trình thực thi mã của nó hoàn tất, nó sẽ quay trở lại lệnh tiếp theo một cách chính xác sau điểm đó. của cuộc gọi. Cấu trúc dữ liệu này được gọi là ngăn xếp cuộc gọi chương trình con.

    Cây rơm.

    Xếp hàng- một cấu trúc dữ liệu động, không xếp chồng rất giống nhau, với điểm khác biệt duy nhất là nó thực hiện nguyên tắc FIFO (Nhập trước, xuất trước) - nhập trước và xuất trước. Đúng như tên gọi, bạn không cần phải tìm đâu xa để tìm những ví dụ trong đời thực. Trong lập trình, hàng đợi được sử dụng, ví dụ, để xử lý các sự kiện giao diện người dùng, yêu cầu của khách hàng và các yêu cầu thông tin khác.

    Xếp hàng.

    Bảng băm– loại cấu trúc dữ liệu tuyến tính động phức tạp nhất. Bảng băm được tối ưu hóa để tìm nhanh các phần tử bằng cách tính địa chỉ của phần tử dưới dạng giá trị băm. Đối số của hàm băm là một khóa nhất định được liên kết với phần tử, ví dụ: số thứ tự của nó. Để đảm bảo các giá trị băm duy nhất cho các giá trị khóa duy nhất (để tránh xung đột), bảng băm ngoài các thuật toán thông minh còn tận dụng RAM một cách hào phóng. Việc sử dụng bảng băm phải được chứng minh và cân nhắc cẩn thận.

    Cấu trúc dữ liệu phân cấp

    Một phần tử trong cấu trúc dữ liệu phân cấp được đặc trưng bởi một liên kết đến phần tử cao hơn trong cấu trúc phân cấp (hoặc liên kết đến các phần tử cấp dưới) và (tùy chọn) một số sê-ri trong chuỗi tuyến tính ở cấp độ của nó (danh sách phân cấp).

    Cây– cấu trúc dữ liệu phân cấp động được biểu thị bằng một nút gốc duy nhất và các nút con của nó. Số lượng con tối đa của mỗi nút xác định kích thước cây. Phân bổ riêng nhị phân hoặc cây nhị phân, vì chúng được sử dụng trong các thuật toán sắp xếp và tìm kiếm: mỗi nút của nhị phân cây tìm kiếm tương ứng với một phần tử từ một tập hợp được sắp xếp nào đó, tất cả các phần tử con bên trái của nó tương ứng với các phần tử nhỏ hơn và tất cả các phần tử con bên phải của nó tương ứng với phần tử lớn. Mỗi nút trong cây được xác định duy nhất bởi một chuỗi các nút không lặp lại từ gốc đến nó - một đường dẫn. Độ dài của đường dẫn là cấp độ của nút trong hệ thống phân cấp cây. Đối với cây nhị phân hoặc cây nhị phân, những điều sau đây được phân biệt: các kiểu duyệt đệ quy tất cả các phần tử của nó (thứ tự truy cập các phần tử của mỗi nút được biểu thị bằng dấu ngoặc nhọn, bắt đầu từ gốc):

    • trực tiếp hoặc tiền tố
      (nút, cây con trái, cây con phải);

    • đảo ngược hoặc hậu tố
      (cây con trái, cây con phải, nút);

    • đối xứng hoặc trung tố
      (cây con trái, nút, cây con phải);

    Để hiển thị các phần tử theo thứ tự tăng dần, cây tìm kiếm phải được duyệt theo thứ tự đối xứng. Vì vậy các phần tử nằm trong thứ tự ngược lại, trong quá trình duyệt cần thay đổi thứ tự thăm các cây con.


    Cây nhị phân.

    Danh sách phân cấp– sự cộng sinh của danh sách tuyến tính và cây. Mỗi phần tử danh sách cũng có thể là phần đầu của danh sách ở cấp phân cấp tiếp theo. Một ví dụ về danh sách phân cấp là cấu trúc của các diễn đàn Internet: một chuỗi các tin nhắn tạo thành một danh sách tuyến tính, trong khi các tin nhắn trả lời các tin nhắn khác sẽ tạo ra các chủ đề thảo luận mới.


    Danh sách phân cấp.

    Cấu trúc dữ liệu mạng

    Một phần tử trong cấu trúc dữ liệu mạng được đặc trưng bởi một tập hợp các kết nối với các phần tử lân cận khác. Trong các cấu trúc dữ liệu như vậy, cả phần tử ban đầu và phần tử gốc đều không được phân bổ rõ ràng.

    đồ thị– cấu trúc dữ liệu mạng động, được biểu thị bằng tập hợp các đỉnh và cạnh – kết nối giữa các đỉnh. Mỗi đỉnh có thể được kết nối với bất kỳ số đỉnh nào khác hoặc với chính nó. Không còn bất kỳ hệ thống phân cấp rõ ràng nào ở đây nữa. Nếu chúng ta coi các nút cây là các đỉnh của biểu đồ và các kết nối giữa các nút cây ở các cấp độ phân cấp khác nhau là các cạnh của biểu đồ, thì bản thân cây có thể được coi là một biểu đồ không chứa chu trình hoặc biểu đồ tuần hoàn. Nếu mỗi cạnh của đồ thị có hướng xác định thì đó là đồ thị có hướng. Ngoài hướng, mỗi cạnh của đồ thị có thể có trọng số riêng. Ví dụ, bằng cách sử dụng biểu đồ, họ lập mô hình mạng lưới giao thông và các vấn đề tối ưu hóa luồng giao thông được giải quyết. Khối lượng công việc hoặc ngược lại, thông lượng các tuyến vận chuyển được cho bởi trọng số của các cạnh tương ứng.


    Đồ thị.
    Đồ thị có hướng.

    Một phần tử trong cấu trúc dữ liệu dạng bảng được đặc trưng bởi chỉ mục hai chiều: chỉ mục hàng và chỉ mục cột tại giao điểm của nó. Bảng là ví dụ về cấu trúc dữ liệu dạng bảng.


    Đánh giá độ phức tạp của thuật toán

    Khi đánh giá độ phức tạp của các thuật toán, chúng tôi không muốn nói đến nỗ lực trí tuệ mà các tác giả đã bỏ ra để phát triển mà là sự phụ thuộc của số lượng thao tác cơ bản được thực hiện bởi máy tính vào khối lượng thông tin được xử lý. Ví dụ, số lần so sánh của hai số sẽ phụ thuộc như thế nào vào độ dài của dãy gốc trong quá trình thực hiện thuật toán sắp xếp? Tôi cố tình thu hẹp định nghĩa một chút, vì trong phần tiếp theo chúng ta sẽ chỉ nói về số lượng các phép toán cơ bản. Trên thực tế, độ phức tạp của thuật toán được xác định không chỉ bởi số lượng thao tác mà còn bởi lượng tài nguyên máy tính liên quan đến việc giải quyết vấn đề và trước hết, bộ nhớ truy cập tạm thời. Thuật toán càng đơn giản thì khả năng hoạt động càng lâu. Các thuật toán phức tạp và nhanh chóng thường sử dụng các cấu trúc dữ liệu phụ trợ và do đó tiêu tốn thêm bộ nhớ. Định luật bảo toàn năng lượng hay “bạn phải trả tiền cho mọi thứ”. Một ví dụ về “tối ưu hóa cận biên” đã được thảo luận trước đó - bảng băm. Cá nhân tôi không biết bảng băm được cấu trúc như thế nào và hàm băm trông như thế nào (tôi đoán là nó không dễ dàng), nhưng thời gian cần thiết để tìm kiếm các phần tử theo khóa thực tế không phụ thuộc vào kích thước của bảng. Tiếp theo, một chút lý thuyết.

    Độ phức tạp của thuật toán được đánh giá bằng các công cụ toán học phân tích tiệm cận và rút ra một ước tính độ phức tạp tiệm cận.

    Ước tính độ phức tạp tiệm cậnđược ký hiệu bằng chữ cái Hy Lạp Θ (theta).

    f(n) = Θ(g(n)), nếu tồn tại c1, c2>0 và n0 sao cho c1*g(n)n0.

    Hàm g(n) là ước tính chính xác tiệm cận về độ phức tạp của thuật toán - hàm f(n), bất đẳng thức trên được gọi là đẳng thức tiệm cận và chính ký hiệu Θ tượng trưng cho tập hợp các hàm phát triển “nhanh chóng” như hàm g(n) - tức là e. đến phép nhân với một hằng số. Như sau từ bất đẳng thức trên, ước tính Θ vừa là ước tính trên và vừa là ước tính dưới của độ phức tạp. Không phải lúc nào cũng có thể có được ước tính theo hình thức này, vì vậy ước tính trên và ước tính dưới đôi khi được xác định riêng biệt.

    Điểm độ khó cao hơnđược ký hiệu bằng chữ cái Hy Lạp Ο (omicron) và là một tập hợp các hàm tăng không nhanh hơn g(n).

    f(n)= Ο(g(n)), nếu có c>0 và n0 sao cho 0n0.

    Điểm khó thấp hơnđược ký hiệu bằng chữ cái Hy Lạp Ω (omega) và là tập hợp các hàm tăng không chậm hơn g(n).

    f(n)= Ω(g(n)), nếu có c>0 và n0 sao cho 0n0.

    Kết quả là: ước lượng tiệm cận chỉ tồn tại nếu giới hạn dưới và giới hạn trên của độ phức tạp của thuật toán trùng nhau. Trong thực hành phân tích thuật toán, ước tính độ phức tạp thường được hiểu là ước tính trên của độ phức tạp. Điều này khá logic, vì điều quan trọng nhất là ước tính thời gian mà thuật toán được đảm bảo hoàn thành công việc của nó chứ không phải thời gian mà thuật toán chắc chắn sẽ không hoàn thành.

    Làm việc với cấu trúc dữ liệu tuyến tính

    Chà, để kết luận, tôi sẽ đưa ra ước tính về độ phức tạp của các thao tác cơ bản với cấu trúc dữ liệu tuyến tính, cụ thể là thêm, xóa và tìm kiếm một phần tử theo chỉ mục hoặc khóa. Trong trường hợp này, các phép toán cơ bản là các phép toán so sánh, liệt kê, tính địa chỉ hoặc sắp xếp lại các phần tử của tập cấu trúc dữ liệu. TRONG bảng tổng hợp, ngoài ước tính độ phức tạp trên, các thành phần thư viện tương ứng với cấu trúc dữ liệu được liệt kê cũng được đưa ra. Do đó, cấu trúc dữ liệu tuyến tính cơ bản đã sẵn sàng và có sẵn cho tất cả các nhà phát triển phần mềm trên nền tảng .

    Một điều kiện cần thiết việc xây dựng thuật toán là chính thức hóa dữ liệu, I E. giảm thông tin cho một số mô hình thông tin (cm. " Mô hình thông tin"), đã được mô tả và nghiên cứu. Khi một mô hình như vậy được tìm thấy, nó được cho là đã được xác định cấu trúc dữ liệu trừu tượng.

    Cấu trúc dữ liệu trừu tượng mô tả các đặc điểm và tính chất của một đối tượng, mối quan hệ giữa các phần tử đối tượng, tốt nhất có thể hoạt động trên một đối tượng hoặc lớp đối tượng nhất định.

    Một trong những nhiệm vụ của khoa học máy tính là tìm ra các dạng biểu diễn thông tin thuận tiện cho xử lý máy tính. Khoa học máy tính với tư cách là một ngành khoa học chính xác hoạt động với các đối tượng hình thức (được mô tả chặt chẽ về mặt toán học). Những đối tượng như vậy - cơ bản cấu trúc dữ liệu trừu tượngđược sử dụng trong khoa học máy tính là:

    · số nguyên;

    · số thực;

    · biểu tượng;

    · giá trị logic.

    Để máy tính xử lý các đối tượng này bằng ngôn ngữ lập trình, có các phương pháp thích hợp Loại dữ liệu(cm. " Loại dữ liệu"). Các đối tượng cơ bản có thể được kết hợp thành các cấu trúc phức tạp hơn bằng cách thêm các thao tác trên toàn bộ cấu trúc và truy cập các quy tắc vào các thành phần riêng lẻ của cấu trúc dữ liệu trừu tượng này.

    Các cấu trúc dữ liệu trừu tượng này bao gồm:

    · vectơ (mảng hữu hạn);

    · bảng (ma trận) và trong trường hợp chung- mảng đa chiều;

    · Cấu trúc động:

    Chuỗi ký hiệu, số;

    Hàng đợi;

    Cây;

    Việc lựa chọn thành công cấu trúc dữ liệu thường là chìa khóa để tạo ra một thuật toán hiệu quả và một chương trình triển khai nó: bằng cách sử dụng sự tương tự của cấu trúc dữ liệu và các đối tượng thực, bạn có thể tìm thấy giải pháp hiệu quả nhiệm vụ.

    Lưu ý rằng các cấu trúc được liệt kê tồn tại bất kể việc triển khai chúng trong quá trình lập trình như thế nào. Họ đã làm việc với những cấu trúc dữ liệu này cả trong thế kỷ 18 và 19. thế kỷ 19, khi máy tính vẫn chưa được phát minh. Chúng ta có thể phát triển một thuật toán theo cấu trúc dữ liệu trừu tượng, nhưng để triển khai thuật toán bằng một ngôn ngữ lập trình cụ thể, chúng ta cần tìm cách biểu diễn nó theo các thuật ngữ Loại dữ liệu Và toán tửđược hỗ trợ bởi ngôn ngữ lập trình này (xem “ Toán tử ngôn ngữ lập trình"). Vì biểu diễn máy tính cấu trúc trừu tượng được sử dụng cấu trúc dữ liệu, đại diện cho một tập hợp các biến, có lẽ nhiều loại khác nhau dữ liệu kết hợp theo một cách nhất định. Để xây dựng các cấu trúc như vector, bảng, chuỗi, dãy, hầu hết các ngôn ngữ lập trình đều có chuẩn Loại dữ liệu: mảng một chiều, mảng hai chiều, chuỗi, tệp (ít thường xuyên hơn là danh sách). Tổ chức các cấu trúc dữ liệu khác, trước hết cấu trúc động, kích thước của nó thay đổi trong quá trình thực hiện chương trình, người lập trình phải thực hiện độc lập, sử dụng các kiểu dữ liệu cơ bản. Chúng ta hãy xem xét các cấu trúc như vậy chi tiết hơn.

    Danh sách

    Danh sách tuyến tính- một chuỗi các phần tử có liên quan tuyến tính trong đó cho phép thực hiện các thao tác thêm phần tử vào một vị trí tùy ý trong danh sách và xóa bất kỳ phần tử nào. Danh sách tuyến tính được xác định duy nhất bằng con trỏ tới đầu danh sách. Các thao tác điển hình trên danh sách là: duyệt qua danh sách, tìm kiếm một phần tử cho trước, chèn một phần tử ngay sau hoặc trước yếu tố nhất định, xóa một phần tử nhất định, hợp nhất hai danh sách thành một, chia một danh sách thành hai hoặc nhiều danh sách, v.v.

    Trong danh sách tuyến tính cho mọi phần tử ngoại trừ Đầu tiên, Có trước yếu tố; cho mọi phần tử ngoại trừ cuối cùng, Có Kế tiếp yếu tố. Vì vậy, tất cả các phần tử của danh sách đều được sắp xếp. Tuy nhiên, việc xử lý danh sách liên kết đơn tuyến tính không phải lúc nào cũng thuận tiện, bởi vì không có khả năng di chuyển theo hướng ngược lại - từ cuối danh sách đến đầu. Trong danh sách tuyến tính, bạn chỉ có thể duyệt qua tất cả các phần tử bằng cách di chuyển tuần tự từ phần tử hiện tại sang phần tử tiếp theo, bắt đầu từ phần tử đầu tiên, truy cập trực tiếp vào Tôi phần tử thứ là không thể.

    Ví dụ 1. Thứ tự ghi tên người đọc trong máy tính của thủ thư xác định mối quan hệ “trước-tiếp”. Theo quy định, bản thân hồ sơ có tài sản bổ sung- chúng được sắp xếp theo thứ tự abc. Các thao tác thêm đầu đọc mới và nếu cần, xóa đầu đọc cũ được thực hiện trong danh sách này. Ngoài ra, nếu hồ sơ về các cuốn sách được phát hành cho mỗi người đọc được lưu giữ thì sẽ thuận tiện hơn khi trình bày từng hồ sơ đó bằng cách sử dụng danh sách các cuốn sách được phát hành.

    Danh sách đổ chuông- cấu trúc tương tự như một danh sách tuyến tính, nhưng với giao tiếp bổ sung giữa phần tử cuối cùng và phần tử đầu tiên, tức là phần tử tiếp theo sau phần tử cuối cùng là phần tử đầu tiên.

    Trong danh sách vòng tròn trái ngược với danh sách tuyến tính tất cả các phần tử đều bằng nhau(vì đối với mỗi phần tử cả phần tử trước và phần tử mục tiếp theo). Việc lựa chọn các phần tử “đầu tiên” và “cuối cùng” trong danh sách vòng là rất tùy tiện, vì trên thực tế cấu trúc danh sách không có phần tử được phân bổ rõ ràng!

    Ví dụ 2. Trong nhiều trò chơi, trẻ sử dụng quầy để chọn người lãnh đạo, chia thành các đội, v.v. Theo quy định, các quầy đếm dài và trẻ em (không tự biết) sắp xếp một danh sách vòng tròn. Mối quan hệ “trước-sau” được xác định theo hướng mà người lãnh đạo đang tính đến. Một thao tác điển hình trong cấu trúc như vậy là loại bỏ một phần tử khỏi danh sách trong khi vẫn duy trì cấu trúc vòng tròn của nó.

    Danh sách tuyến tính, trong đó các thao tác chèn, xóa và truy cập vào các giá trị phần tử chỉ được thực hiện trên các phần tử ngoài cùng (đầu tiên hoặc cuối cùng), đã nhận được các tên đặc biệt.

    Cây rơm - trương hợp đặc biệt một danh sách liên kết đơn tuyến tính trong đó hai thao tác được xác định: thêm một phần tử vào đầu ngăn xếp (trước phần tử đầu tiên) và xóa một phần tử khỏi đầu ngăn xếp (loại bỏ phần tử đầu tiên).

    Ví dụ 3. Xét bài toán xác định sự cân bằng của dấu ngoặc nhiều loại khác nhau trong biểu thức số học. Ví dụ: bạn muốn phân tích xem dấu ngoặc đơn trong biểu thức chứa dấu ngoặc đơn và dấu ngoặc vuông có cân bằng hay không: ? Để giải quyết vấn đề này chúng ta sẽ sử dụng cấu trúc động dữ liệu cây rơm. Hãy để chúng tôi trình bày một thuật toán để giải quyết vấn đề này từng bước một. Chúng ta sẽ sử dụng ký hiệu sau:

    Tôi- số ký hiệu được phân tích;

    N- số ký tự trong biểu thức.

    1. Tôi = 0.

    2. Tôi = Tôi + 1.

    3. Nếu TôiN, sau đó chuyển sang bước (4), ngược lại nếu ngăn xếp trống thì hiển thị thông báo “ngoặc được cân bằng”, ngược lại hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

    4. Nếu Tôi Ký hiệu thứ khác với ký hiệu ngoặc, sau đó chuyển sang bước (2).

    5. Nếu Tôi Ký hiệu thứ bằng “(” hoặc “[”, sau đó ta bỏ vào ngăn xếp, chuyển sang bước (2).

    6. Nếu Tôi Ký hiệu thứ là “)”, thì ta kiểm tra phần trên cùng của ngăn xếp: nếu có dấu “(” ở đầu ngăn xếp thì ta loại bỏ khỏi ngăn xếp; chuyển sang bước (2), nếu không thì hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

    7. Nếu Tôi Ký tự thứ là “]”, thì ta kiểm tra phần trên cùng của ngăn xếp: nếu có “[” ở đầu ngăn xếp thì ta xóa nó ra khỏi ngăn xếp; chuyển sang bước (2), nếu không hiển thị thông báo “ dấu ngoặc không cân bằng" Kết thúc thuật toán.

    Xếp hàng- trường hợp đặc biệt của danh sách liên kết đơn tuyến tính, trong đó chỉ được phép thực hiện hai thao tác: thêm một phần tử vào cuối (đuôi) của hàng đợi và xóa một phần tử khỏi đầu (đầu) của hàng đợi.

    Khái niệm hàng đợi thực sự rất gần với thuật ngữ hàng ngày"xếp hàng". Hàng đợi khách hàng trong cửa hàng được mô tả rõ ràng dưới dạng cấu trúc dữ liệu này.

    Cây

    Cây là tập hợp các phần tử được gọi là điểm giao, trong đó một phần tử được chọn ( nguồn gốc), và các phần tử còn lại được chia thành các tập rời nhau (cây con), mỗi tập là một cây và gốc của mỗi cây con là hậu duệ gốc của cây, tức là tất cả các phần tử được kết nối với nhau bằng một mối quan hệ (tổ tiên-hậu duệ). Kết quả là một cấu trúc phân cấp của các nút được hình thành. Các nút không có con nào được gọi là lá. Phía trên cây được xác định hoạt động sau đây: thêm một phần tử vào cây, xóa một phần tử khỏi cây, duyệt cây, tìm kiếm một phần tử trong cây.

    Ví dụ 4. Cây là cấu trúc dữ liệu thuận tiện nhất để biểu diễn cây gia phả, có thể được sử dụng để giải quyết các vấn đề xác định mức độ quan hệ giữa hai người.

    Cây còn được dùng để xác định chiến lược giành chiến thắng trong trò chơi (xem bài “ Trò chơi. Chiến lược chiến thắng") và để xây dựng các mô hình thông tin khác nhau (xem " Mô hình thông tin”).

    Một vai trò đặc biệt quan trọng trong khoa học máy tính được thực hiện bởi cái gọi là cây nhị phân.

    Cây nhị phân- một trường hợp đặc biệt của cây trong đó mỗi nút không thể có nhiều hơn hai con cháu, đó là các gốc của cây con trái và cây con phải.

    Ngoài ra, nếu thỏa mãn điều kiện đối với các nút cây là tất cả giá trị của các phần tử của cây con bên trái đều nhỏ hơn giá trị của gốc cây và tất cả các giá trị của các phần tử của cây con bên phải giá trị lớn hơn gốc thì cây như vậy được gọi là cây tìm kiếm nhị phân và được thiết kế để nhanh chóng tìm kiếm các phần tử. Thuật toán tìm kiếm trong cây như vậy hoạt động như sau: giá trị tìm kiếm được so sánh với giá trị gốc của cây và tùy thuộc vào kết quả so sánh, việc tìm kiếm sẽ kết thúc hoặc chỉ tiếp tục ở bên trái hoặc chỉ ở bên phải. cây con tương ứng. Tổng số thao tác so sánh sẽ không vượt quá cái gọi là chiều cao cây- số phần tử tối đa trên đường đi từ gốc đến một trong các lá. Vậy chiều cao của cây trong hình là 4.

    Đồ thị

    đồ thị là một tập hợp các phần tử được gọi là đỉnh caođồ thị cùng với một tập hợp các mối quan hệ giữa các đỉnh này, được gọi là xương sườnđồ thị. Giải thích đồ họa của cấu trúc dữ liệu này là một tập hợp các điểm tương ứng với các đỉnh, một số cặp được kết nối bằng các đường hoặc mũi tên tương ứng với các cạnh. Trong trường hợp sau, đồ thị được gọi là định hướng(xem thêm bài viết “ Mô hình đồ họa " Và " Mô hình dạng bảng ”).

    Do các đối tượng có cấu trúc tùy ý có thể được mô tả bằng đồ thị nên đồ thị là phương tiện chính để mô tả cấu trúc vật thể phức tạp và hoạt động của các hệ thống. Ví dụ, để mô tả mạng máy tính, hệ thống giao thông, cấu trúc phân cấp (cây là một trong các loại đồ thị). Lưu đồ thuật toán (xem “ Cách viết thuật toán”) cũng là đồ thị.

    Nếu mỗi cạnh cũng được gán một số nhất định ( cân nặng), thì đồ thị như vậy được gọi là có trọng lượng. Ví dụ: khi mô tả hệ thống đường bộ của Nga bằng biểu đồ, điều quan trọng là chiều dài của con đường (trọng lượng của cạnh biểu đồ) kết nối một số điểm nhất định. khu định cư(các đỉnh của đồ thị). Hơn nữa, trong hình, độ dài của các cạnh tương ứng không nhất thiết phải tương ứng với trọng số được gán cho chúng, không giống như bản đồ đường đi.

    Ví dụ 5. Thật thuận tiện khi giải quyết vấn đề sau đây bằng đồ thị có trọng số. Chính phủ Nga đang lên kế hoạch xây dựng những tuyến đường cao tốc hiện đại nối các thành phố có dân số hơn một triệu người. Nên xây dựng loại đường nào để từ bất kỳ thành phố nào như vậy người ta có thể đến bất kỳ thành phố nào khác bằng đường cao tốc mới và tổng chiều dài của các con đường sẽ là tối thiểu?

    Bài toán này trong lý thuyết đồ thị có lời giải đơn giản và chính xác. Chúng ta có thể bắt đầu quy hoạch mạng lưới đường bộ, bắt đầu từ bất kỳ thành phố nào, chẳng hạn như St. Petersburg. Hãy kết nối nó với thành phố hơn một triệu người gần nhất. Sau đó, ở mỗi bước, con đường ngắn nhất sẽ được thêm vào mạng hiện có, con đường này có thể kết nối một thành phố chưa được kết nối với mạng với một trong những thành phố đã có trong mạng. Do đó, số đường sẽ ít hơn số thành phố một đường.

    Cấu trúc dữ liệu trừu tượng - biểu đồ - có thể được biểu diễn trong chương trình theo nhiều cách, tức là. sử dụng các kiểu dữ liệu khác nhau. Ví dụ: một đồ thị có thể được mô tả bằng cách sử dụng danh sách các cạnh, xác định mỗi cạnh bằng một cặp đỉnh và, tùy chọn, một trọng số. Việc lưu trữ biểu đồ dạng bảng đã trở nên phổ biến nhất (xem “ Mô hình dạng bảng"), còn được gọi là ma trận kề, I E. một mảng hai chiều, nói MỘT, trong đó đối với đồ thị không có trọng số (hoặc 1), nếu cạnh giữa các đỉnh Tôi Và j tồn tại và (hoặc 0) nếu ngược lại. Đối với đồ thị có trọng số MỘT[Tôi][j] bằng trọng số của cạnh tương ứng, và sự vắng mặt của cạnh trong một số bài toán được biểu thị thuận tiện bằng vô cực. Đối với đồ thị vô hướng, ma trận kề luôn đối xứng qua đường chéo chính ( Tôi = j). Sử dụng ma trận kề, dễ dàng kiểm tra xem có cạnh nào trong đồ thị nối một đỉnh hay không Tôi với đầu j. Nhược điểm chính của nó là ma trận kề đòi hỏi lượng bộ nhớ đủ để lưu trữ N 2 giá trị cho đồ thị chứa N các đỉnh, ngay cả khi có ít cạnh hơn đáng kể trong đồ thị so với N 2 .

    Khi giải thích khái niệm cấu trúc dữ liệu Bạn có thể sử dụng hình minh họa sau.

    Khi giải quyết bất kỳ vấn đề nào cũng cần có sự hợp tác dữ liệu và thực hiện các thao tác trên chúng. Nói chung, tập hợp các thao tác này cho mỗi nhiệm vụ là khác nhau. Tuy nhiên, nếu một tập hợp các phép toán nào đó thường được sử dụng để giải Các nhiệm vụ khác nhau, thì sẽ rất hữu ích nếu bạn tìm ra cách sắp xếp dữ liệu cho phép bạn thực hiện chính xác các thao tác này một cách hiệu quả nhất có thể. Sau khi phương pháp này được phát minh, khi giải nhiệm vụ cụ thể chúng ta có thể giả định rằng chúng ta có một “hộp đen” (chúng ta sẽ gọi nó là cấu trúc dữ liệu), trong đó người ta biết rằng một loại dữ liệu nào đó được lưu trữ trong đó và có thể thực hiện một số thao tác nhất định trên dữ liệu này. Điều này cho phép bạn thoát khỏi các chi tiết và tập trung vào tính năng đặc trưng nhiệm vụ. Bên trong (tức là trong máy tính) “hộp đen” này có thể được triển khai theo nhiều cách khác nhau, nhưng người ta nên cố gắng triển khai hiệu quả nhất (nhanh và tiết kiệm bộ nhớ) nhất có thể.

    Tiêu chuẩn giáo dục của tiểu bang quy định việc nghiên cứu các cấu trúc dữ liệu khác nhau cả trong khóa học cơ bản của trường tiểu học và trung học. Trong quá trình xây dựng chương trình tiểu học ở Chương trình mẫu chuỗi ký tự (chuỗi), số, danh sách, cây, đồ thị được đề cập dưới dạng đối tượng được xử lý. Tuy nhiên, trong công việc thực tế của dữ liệu có cấu trúc phức tạp chỉ đề cập đến mảng (xem bài “ Hoạt động mảng"). Ở trường cơ bản, rõ ràng việc nghiên cứu các cấu trúc còn lại trước hết là hợp lý khi xây dựng các mô hình đồ họa và các mô hình khác (xem phần IV của bộ bách khoa toàn thư).

    Một chương trình gần đúng dành cho một trường chuyên biệt bao gồm việc làm việc với các con số, ma trận, chuỗi, danh sách và cây. Như một minh họa đơn giản khi làm việc với danh sách, bạn có thể chọn sắp xếp ngăn xếp bằng cách sử dụng mảng một chiều và một biến số nguyên trỏ đến đỉnh ngăn xếp (“phần dưới cùng” của ngăn xếp luôn nằm ở phần tử đầu tiên của mảng ). Ngoài bài toán kiểm tra dấu ngoặc đơn để cân bằng được đưa ra trong bài, các bạn có thể nghiên cứu hoạt động của máy tính ngăn xếp bằng ví dụ về thuật toán chuyển biểu thức số học sang ký hiệu Ba Lan ngược ( hậu tố ghi âm) từ cái mà chúng ta đã quen thêm vào ghi và tính toán thêm giá trị của một biểu thức số học.

    Cây nhị phân cũng có thể được biểu diễn dễ dàng trong bộ nhớ máy tính bằng mảng một chiều, với phần tử đầu tiên của mảng lưu trữ gốc của cây và con cháu của nút cây được lưu trữ trong Tôi-phần tử thứ của mảng sẽ nằm ở vị trí thứ 2 Tôi-m và (2 Tôi+1) phần tử thứ tương ứng. Nếu một nút không có phần tử con thì phần tử tương ứng sẽ bằng, ví dụ: 0. Thủ tục đệ quy duyệt cây t và in các phần tử của nó trong trường hợp này sẽ trông như thế này:

    thứ tự thủ tục(i:số nguyên);

    nếu như t[i]<> 0 sau đó

    Bạn có thể đọc về cách triển khai danh sách và mảng bằng cách sử dụng các biến động, chẳng hạn như trong cuốn sách cổ điển của N. Wirth “Thuật toán và cấu trúc dữ liệu”.

    Chương trình dành cho trường chuyên cũng bao gồm các thuật toán đồ thị. Đặc biệt, việc tìm kiếm đường đi ngắn nhất trong đồ thị được đề cập. Đối với đồ thị không có trọng số, vấn đề này có thể được giải quyết, ví dụ: bằng cách sử dụng thuật toán "tìm kiếm theo chiều rộng", khi đầu tiên các đỉnh của đồ thị được kết nối bởi một cạnh với đỉnh ban đầu được đánh dấu, sau đó tất cả các đỉnh được kết nối với các đỉnh được đánh dấu, v.v. . Đối với biểu đồ có trọng số, thuật toán Dijkstra thường được sử dụng nhiều nhất (ví dụ: xem bài viết của E.V. Andreeva “Olympiads in Informatics. Paths to the Top”, “Informatics” số 8/2002). Kiến thức về các thuật toán như vậy là cần thiết để giải quyết thành công vấn đề về Olympic trong khoa học máy tính. Vì vậy, ở giai đoạn IV của quận liên bang Olympic toàn Nga Trong khoa học máy tính vào năm 2007, bài toán “Rãnh và rãnh” đã được đề xuất, giải pháp của bài toán này là tìm đường đi ngắn nhất trong biểu đồ có trọng số.

    Cấu trúc dữ liệu là một đơn vị chương trình cho phép bạn lưu và xử lý nhiều dữ liệu cùng loại hoặc logic thông tin liên quan V. Thiết bị tính toán. Nếu bạn muốn thêm, tìm, thay đổi hoặc xóa thông tin, khung này sẽ cung cấp một gói tùy chọn cụ thể tạo nên giao diện của nó.

    Khái niệm cấu trúc dữ liệu bao gồm những gì?

    Thuật ngữ này có thể có một số ý nghĩa tương tự nhưng vẫn có ý nghĩa đặc biệt. Cái này:

    • kiểu trừu tượng;
    • thực hiện một loại thông tin trừu tượng;
    • một thể hiện của một kiểu dữ liệu, chẳng hạn như một danh sách cụ thể.

    Nếu chúng ta nói về cấu trúc dữ liệu trong bối cảnh lập trình hàm, thì đây là một đơn vị đặc biệt được bảo toàn trong quá trình thay đổi. Nó có thể được gọi một cách không chính thức như một cấu trúc duy nhất, mặc dù thực tế là có thể có phiên bản khác nhau.

    Những gì hình thành cấu trúc?

    Nó được hình thành bằng cách sử dụng các liên kết và thao tác trên chúng bằng một ngôn ngữ lập trình cụ thể. Thật đáng để nói rằng các loại khác nhau cấu trúc phù hợp để thực hiện ứng dụng khác nhau, chẳng hạn, một số có chuyên môn hoàn toàn hẹp và chỉ phù hợp để thực hiện các nhiệm vụ đã được thiết lập.

    Nếu chúng ta lấy cây B thì chúng thường thích hợp để hình thành cơ sở dữ liệu và chỉ dành cho chúng. Đồng thời, bảng băm vẫn được sử dụng ở mọi nơi trong thực tế để tạo ra các từ điển khác nhau, chẳng hạn như để thể hiện tên miền trong địa chỉ Internet của PC chứ không chỉ để tạo thành cơ sở dữ liệu.

    Trong quá trình phát triển phần mềm này hay phần mềm kia, độ phức tạp của việc triển khai và chất lượng chức năng của các chương trình phụ thuộc trực tiếp vào ứng dụng đúng cấu trúc dữ liệu. Sự hiểu biết này về mọi thứ đã thúc đẩy sự phát triển của các phương pháp phát triển chính thức và ngôn ngữ lập trình, trong đó các cấu trúc, chứ không phải thuật toán, được đặt ở các vị trí dẫn đầu trong kiến ​​trúc chương trình.

    Điều đáng chú ý là nhiều ngôn ngữ lập trình có loại đã cài đặt tính mô đun, cho phép cấu trúc dữ liệu được sử dụng an toàn trong các ứng dụng khác nhau. Những ví dụ đáng chú ý là ngôn ngữ Java, C# và C++. Giờ đây, cấu trúc cổ điển của dữ liệu được sử dụng được trình bày trong thư viện tiêu chuẩn của ngôn ngữ lập trình hoặc được tích hợp trực tiếp vào chính ngôn ngữ đó. Ví dụ: bảng băm được tích hợp vào Lua, Python, Perl, Ruby, Tcl và các bảng khác. Áp dụng rộng rãi thư viện chuẩn mẫu trong C++.

    So sánh cấu trúc trong lập trình chức năng và mệnh lệnh

    Điều đáng nói ngay là việc thiết kế kết cấu cho ngôn ngữ chức năng khó khăn hơn so với những câu mệnh lệnh, vì ít nhất hai lý do:

    1. Trên thực tế, tất cả các cấu trúc thường sử dụng phép gán trong thực tế, vốn không được sử dụng theo phong cách chức năng thuần túy.
    2. Cấu trúc chức năng- đây là những hệ thống linh hoạt. Trong lập trình mệnh lệnh, các phiên bản cũ chỉ được thay thế bằng phiên bản mới, nhưng trong lập trình chức năng, mọi thứ vẫn hoạt động như trước. Nói cách khác, trong lập trình mệnh lệnh, cấu trúc là nhất thời, nhưng trong lập trình chức năng, chúng là vĩnh viễn.

    Cấu trúc bao gồm những gì?

    Thông thường, dữ liệu mà các chương trình làm việc được lưu trữ dưới dạng mảng, hằng hoặc có độ dài thay đổi được tích hợp trong ngôn ngữ lập trình được sử dụng. Mảng là cấu trúc đơn giản nhất tuy nhiên, với thông tin, để giải quyết một số vấn đề, cần có hiệu quả cao hơn của một số thao tác, do đó các cấu trúc khác (phức tạp hơn) được sử dụng.

    Mảng đơn giản nhất phù hợp cho việc truy cập thường xuyên thành phần được cài đặt theo chỉ số và những thay đổi của chúng, đồng thời loại bỏ các phần tử ở giữa hoạt động theo nguyên tắc O(N)O(N). Nếu bạn cần loại bỏ các phần tử để giải quyết một số vấn đề nhất định, bạn sẽ phải sử dụng một cấu trúc khác. Ví dụ: cây nhị phân (std::set) cho phép bạn thực hiện việc này trong O(logN)O(log⁡N), nhưng nó không hỗ trợ làm việc với các chỉ mục, nó chỉ thực hiện duyệt từng phần tử và tìm kiếm chúng theo giá trị. Vì vậy, chúng ta có thể nói rằng cấu trúc khác nhau ở các hoạt động mà nó có khả năng thực hiện cũng như tốc độ thực hiện chúng. Ví dụ, cần xem xét các cấu trúc đơn giản nhất không mang lại lợi ích về mặt hiệu quả nhưng chắc chắn có đặt bộ các hoạt động được hỗ trợ.

    Cây rơm

    Đây là một trong những kiểu cấu trúc dữ liệu, được trình bày dưới dạng một mảng đơn giản có giới hạn. Ngăn xếp cổ điển chỉ hỗ trợ ba tùy chọn:

    • Đẩy một phần tử vào ngăn xếp (Độ khó: O(1)O(1)).
    • Lấy một phần tử ra khỏi ngăn xếp (Độ phức tạp: O(1)O(1)).
    • Kiểm tra xem ngăn xếp có trống hay không (Độ khó: O(1)O(1)).

    Để giải thích cách hoạt động của ngăn xếp, chúng ta có thể sử dụng phép tương tự lọ cookie trong thực tế. Hãy tưởng tượng rằng có một vài chiếc bánh quy ở dưới đáy bát. Bạn có thể đặt thêm một vài miếng lên trên hoặc ngược lại, lấy một chiếc bánh quy lên trên. Những cookie còn lại sẽ được bao phủ bởi những cookie trên cùng và bạn sẽ không biết gì về chúng. Đây là cách mọi thứ diễn ra với ngăn xếp. Để mô tả khái niệm này, người ta sử dụng chữ viết tắt LIFO (Last In, First Out), trong đó nhấn mạnh rằng thành phần được đưa vào ngăn xếp cuối cùng sẽ là thành phần đầu tiên bị xóa khỏi ngăn xếp đó.

    Xếp hàng

    Đây là một loại cấu trúc dữ liệu khác hỗ trợ cùng một bộ tùy chọn như một ngăn xếp, nhưng nó có ngữ nghĩa ngược lại. Chữ viết tắt FIFO (First In First Out) được sử dụng để mô tả hàng đợi vì phần tử được thêm vào trước sẽ bị xóa trước. Tên của cấu trúc đã nói lên điều đó - nguyên lý hoạt động hoàn toàn giống với hàng đợi có thể thấy trong cửa hàng hoặc siêu thị.

    Tháng mười hai

    Đây là một loại cấu trúc dữ liệu khác, còn được gọi là hàng đợi hai đầu. Tùy chọn này hỗ trợ tập hợp các thao tác sau:

    • Chèn phần tử vào đầu (Độ khó: O(1)O(1)).
    • Trích xuất thành phần từ đầu (Độ khó: O(1)O(1)).
    • Thêm một phần tử vào cuối (Độ khó: O(1)O(1)).
    • Trích xuất một phần tử từ cuối (Độ phức tạp: O(1)O(1)).
    • Kiểm tra xem bộ bài có trống không (Độ khó: O(1)O(1)).

    Danh sách

    Cấu trúc này data xác định một chuỗi các thành phần có liên quan tuyến tính mà các hoạt động thêm thành phần vào bất kỳ vị trí nào trong danh sách và xóa nó đều được phép. Một danh sách tuyến tính được chỉ định bởi một con trỏ tới đầu danh sách. Các thao tác điển hình trên danh sách: duyệt qua, tìm kiếm một thành phần cụ thể, chèn một phần tử, loại bỏ một thành phần, hợp nhất hai danh sách thành một tổng thể, chia danh sách thành một cặp, v.v. Điều đáng chú ý là trong một danh sách tuyến tính, ngoài phần tử đầu tiên, còn có một thành phần trước đó cho mỗi phần tử, không bao gồm phần tử cuối cùng. Điều này có nghĩa là các thành phần danh sách ở trạng thái có thứ tự. Có, việc xử lý danh sách như vậy không phải lúc nào cũng thuận tiện, vì không có khả năng di chuyển theo hướng ngược lại - từ cuối danh sách đến đầu danh sách. Tuy nhiên, trong danh sách tuyến tính, bạn có thể đi qua tất cả các thành phần theo từng bước.

    Ngoài ra còn có danh sách đổ chuông. Đây là cấu trúc giống như một danh sách tuyến tính, nhưng nó có một kết nối bổ sung giữa thành phần đầu tiên và thành phần cuối cùng. Nói cách khác, thành phần tiếp theo sau phần tử cuối cùng là thành phần đầu tiên.

    Các phần tử trong danh sách này đều bằng nhau. Chọn cái đầu tiên và cái cuối cùng là một quy ước.

    Cây

    Đây là tập hợp các thành phần được gọi là nút, trong đó có một (một) thành phần chính ở dạng gốc và tất cả các thành phần còn lại được chia thành nhiều phần tử rời rạc. Mỗi tập hợp là một cái cây, và gốc của mỗi cây là con của gốc cây đó. Nói cách khác, tất cả các thành phần được kết nối với nhau bằng mối quan hệ tổ tiên-con cái. Kết quả là có thể quan sát được cấu trúc phân cấp của các nút. Nếu các nút không có nút con thì chúng được gọi là các nút lá. Các thao tác sau được xác định trên cây: thêm một thành phần và xóa nó, duyệt qua, tìm kiếm một thành phần. Cây nhị phân đóng một vai trò đặc biệt trong khoa học máy tính. Nó là gì? Đây là trường hợp đặc biệt của cây, trong đó mỗi nút không thể có nhiều hơn một cặp con, là gốc của cây con trái và cây con phải. Nếu, ngoài các nút của cây, điều kiện được đáp ứng là tất cả các giá trị của các thành phần của cây con bên trái đều nhỏ hơn các giá trị của gốc và các giá trị của các thành phần của cây con bên phải cây con lớn hơn gốc thì cây như vậy được gọi là cây tìm kiếm nhị phân và nó được dùng để nhanh chóng tìm thấy các phần tử. Thuật toán tìm kiếm hoạt động như thế nào trong trường hợp này? Giá trị tìm kiếm được so sánh với giá trị gốc và tùy thuộc vào kết quả, việc tìm kiếm sẽ kết thúc hoặc tiếp tục, nhưng chỉ ở cây con bên trái hoặc bên phải. Tổng số phép toán so sánh sẽ không vượt quá chiều cao của cây (điều này số lớn nhất các thành phần trên đường đi từ gốc đến một trong các lá).

    Đồ thị

    Đồ thị là một tập hợp các thành phần, được gọi là các đỉnh, cùng với một tập hợp các mối quan hệ giữa các đỉnh này, được gọi là các cạnh. Giải thích đồ họa Cấu trúc này được trình bày dưới dạng một tập hợp các điểm tương ứng với các đỉnh và một số cặp được kết nối bằng đường thẳng hoặc mũi tên tương ứng với các cạnh. Trường hợp cuối cùng gợi ý rằng đồ thị nên được gọi là đồ thị có hướng.

    Đồ thị có thể được sử dụng để mô tả các đối tượng của bất kỳ cấu trúc nào; chúng là phương tiện chính để mô tả các cấu trúc phức tạp và hoạt động của tất cả các hệ thống.

    Thêm chi tiết về cấu trúc trừu tượng

    Để xây dựng một thuật toán cần phải hình thức hóa dữ liệu hay nói cách khác là đưa dữ liệu về một mô hình thông tin nào đó đã được nghiên cứu và viết sẵn. Một khi mô hình đã được tìm thấy, có thể nói rằng cấu trúc trừu tượng đã được thiết lập.

    Đây là cấu trúc dữ liệu chính thể hiện các đặc điểm, tính chất của một đối tượng, mối quan hệ giữa các thành phần của đối tượng và các thao tác có thể thực hiện trên nó. Nhiệm vụ chính là tìm kiếm và hiển thị các dạng trình bày thông tin thuận tiện cho việc chỉnh sửa trên máy tính. Điều đáng nói ngay là khoa học máy tính, với tư cách là một ngành khoa học chính xác, hoạt động với các đối tượng hình thức.

    Cấu trúc dữ liệu được phân tích bởi các đối tượng sau:

    • Số nguyên và số thực.
    • Các giá trị Boolean.
    • Biểu tượng.

    Để xử lý tất cả các phần tử trên máy tính cần có các thuật toán và cấu trúc dữ liệu phù hợp. Đối tượng điển hình có thể được kết hợp thành các cấu trúc phức tạp. Bạn có thể thêm các thao tác, quy tắc trên chúng vào các thành phần nhất định của cấu trúc này.

    Cấu trúc tổ chức dữ liệu bao gồm:

    Nếu tất cả các yếu tố được chọn thành công thì đây sẽ là chìa khóa hình thành thuật toán hiệu quả và cấu trúc dữ liệu. Nếu bạn áp dụng sự tương tự giữa các cấu trúc và vật thể thực trong thực tế, bạn có thể giải quyết các vấn đề hiện có một cách hiệu quả.

    Điều đáng chú ý là tất cả các cấu trúc tổ chức dữ liệu tồn tại riêng biệt trong lập trình. Họ đã làm việc rất nhiều với chúng vào thế kỷ 18 và 19, khi vẫn chưa có dấu vết của máy tính.

    Có thể phát triển một thuật toán theo cấu trúc trừu tượng, nhưng để triển khai thuật toán bằng một ngôn ngữ lập trình cụ thể, bạn sẽ cần tìm một kỹ thuật để biểu diễn nó trong các kiểu dữ liệu, toán tử được hỗ trợ. ngôn ngữ cụ thể lập trình. Để tạo các cấu trúc như vector, bảng, chuỗi, dãy, nhiều ngôn ngữ lập trình có các loại cổ điển dữ liệu: mảng một chiều hoặc hai chiều, chuỗi, tệp.

    Chúng ta đã đề cập đến các đặc điểm của cấu trúc dữ liệu, bây giờ cần chú ý hơn đến việc hiểu khái niệm cấu trúc. Khi giải quyết hoàn toàn bất kỳ vấn đề nào, bạn cần phải làm việc với một số dữ liệu để thực hiện các thao tác trên thông tin. Mỗi nhiệm vụ có một tập hợp thao tác riêng, nhưng một tập hợp nhất định được sử dụng trong thực tế thường xuyên hơn để giải quyết các nhiệm vụ khác nhau. Trong trường hợp này, sẽ rất hữu ích nếu bạn đưa ra một cách tổ chức thông tin nhất định cho phép bạn thực hiện các thao tác này một cách hiệu quả nhất có thể. Ngay sau khi phương pháp này xuất hiện, bạn có thể coi như mình có một “hộp đen” trong đó dữ liệu thuộc một loại nhất định sẽ được lưu trữ và sẽ thực hiện một số thao tác nhất định với dữ liệu. Điều này sẽ cho phép bạn thoát khỏi các chi tiết và tập trung hoàn toàn vào các tính năng đặc trưng của nhiệm vụ. “Hộp đen” này có thể được triển khai theo bất kỳ cách nào, nhưng cần phải cố gắng thực hiện hiệu quả nhất có thể.

    Ai cần biết điều này?

    Những lập trình viên mới bắt đầu muốn tìm chỗ đứng trong lĩnh vực này nhưng chưa biết đi đâu thì nên làm quen với thông tin. Đây là những điều cơ bản trong mọi ngôn ngữ lập trình, vì vậy sẽ là một ý tưởng hay nếu bạn tìm hiểu ngay về cấu trúc dữ liệu và sau đó làm việc với chúng trong ví dụ cụ thể và bằng một ngôn ngữ nhất định. Chúng ta không nên quên rằng mỗi cấu trúc có thể được đặc trưng bởi các biểu diễn logic và vật lý, cũng như một tập hợp các thao tác trên các biểu diễn này.

    Đừng quên: nếu bạn nói về cấu trúc này hay cấu trúc kia thì hãy ghi nhớ cách biểu diễn logic của nó, bởi vì biểu diễn vật lý hoàn toàn ẩn giấu khỏi “người quan sát bên ngoài”.

    Ngoài ra, hãy nhớ rằng cách biểu diễn logic hoàn toàn độc lập với ngôn ngữ lập trình và máy tính, trong khi cách biểu diễn vật lý thì ngược lại, phụ thuộc vào người dịch và công nghệ máy tính. Ví dụ: mảng hai chiều trong Fortran và Pascal có thể được biểu diễn theo cách giống hệt nhau và cách biểu diễn vật lý theo cùng một cách. máy tính sẽ khác nhau trong các ngôn ngữ này.

    Đừng vội bắt đầu học các cấu trúc cụ thể; tốt nhất bạn nên hiểu cách phân loại của chúng, làm quen với chúng về mặt lý thuyết và tốt nhất là trong thực tế. Điều đáng ghi nhớ là tính biến đổi là một đặc điểm quan trọng của cấu trúc và nó biểu thị vị trí tĩnh, động hoặc bán tĩnh. Tìm hiểu những điều cơ bản trước khi chuyển sang những thứ mang tính toàn cầu hơn, điều này sẽ giúp bạn phát triển hơn nữa.

    • Dịch

    Ekaterina Malakhova, một biên tập viên tự do, đã phỏng theo một bài viết của Beau Carnes về các loại cấu trúc dữ liệu chính, đặc biệt là cho blog Netology.

    “Lập trình viên tồi chỉ nghĩ về mã. Lập trình viên giỏi hãy nghĩ về cấu trúc dữ liệu và mối quan hệ của chúng,” Linus Torvalds, người tạo ra Linux.

    Cấu trúc dữ liệu đóng vai trò quan trọng trong quá trình phát triển phần mềm và cũng là câu hỏi thường gặp trong các cuộc phỏng vấn của nhà phát triển. Tin tốt là về cơ bản chúng chỉ định dạng đặc biệtđể tổ chức và lưu trữ dữ liệu.

    Trong bài viết này, tôi sẽ chỉ cho bạn 10 cấu trúc dữ liệu phổ biến nhất. Đối với mỗi người trong số họ, các video và ví dụ về cách triển khai chúng trong JavaScript đều được cung cấp. Để giúp bạn thực hành, tôi cũng đưa vào một số bài tập từ phiên bản beta của chương trình giảng dạy freeCodeCamp mới.

    Trong bài viết, tôi cung cấp các ví dụ về cách triển khai các cấu trúc dữ liệu này trong JavaScript; chúng cũng sẽ hữu ích nếu bạn đang sử dụng ngôn ngữ cấp thấp như C. Nhiều ngôn ngữ cấp cao, bao gồm cả JavaScript, đã có hầu hết các triển khai tích hợp sẵn. cấu trúc dữ liệu chúng ta sẽ thảo luận. Tuy nhiên, kiến ​​thức như vậy sẽ là một lợi thế lớn trong quá trình tìm kiếm việc làm của bạn và sẽ hữu ích khi viết mã hiệu suất cao.

    Danh sách liên kết

    Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản. Nó thường được so sánh với một mảng, vì nhiều cấu trúc khác có thể được triển khai bằng cách sử dụng mảng hoặc danh sách liên kết. Hai loại này đều có ưu điểm và nhược điểm.

    Đây là cách hoạt động của danh sách liên kết

    Danh sách liên kết bao gồm một nhóm các nút cùng nhau tạo thành một chuỗi. Mỗi nút chứa hai thứ: dữ liệu thực tế mà nó lưu trữ (đây có thể là bất kỳ loại dữ liệu nào) và một con trỏ (hoặc liên kết) tới nút tiếp theo trong chuỗi. Ngoài ra còn có các danh sách liên kết đôi: trong đó, mỗi nút có một con trỏ tới cả phần tử tiếp theo và phần tử trước đó trong danh sách.

    Các thao tác cơ bản trong danh sách liên kết bao gồm thêm, xóa và tìm kiếm một phần tử trong danh sách.

    Độ phức tạp về thời gian của danh sách liên kết ═════════ ╗ ║ Thuật toán ║Trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬══════ ═══════ ════ ╬═════════ ══════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O (1) O (1) ║ ║ Xóa ║ O (1) ║ O (1) ║ ╚═══════════╩══════════════ ╚═══════════╩══════════════ ═══╩════ ══════ ═════╝

    Các bài tập từ freeCodeCamp

    ngăn xếp

    Ngăn xếp là cấu trúc cơ bản data, cho phép bạn thêm hoặc xóa các phần tử ở đầu dữ liệu. Nó giống như một chồng sách: nếu bạn muốn xem cuốn sách ở giữa chồng thì trước tiên bạn phải bỏ những cuốn ở trên xuống.

    Ngăn xếp được tổ chức theo nguyên tắc LIFO (Last In First Out). Điều này có nghĩa là phần tử cuối cùng bạn thêm vào ngăn xếp sẽ là phần tử đầu tiên được đưa ra khỏi ngăn xếp.


    Đây là cách ngăn xếp hoạt động

    Ngăn xếp có thể thực hiện ba thao tác: thêm phần tử (đẩy), xóa phần tử (pop) và hiển thị nội dung của ngăn xếp (pip).

    Độ phức tạp về thời gian ngăn xếp ════════╗ ║ Thuật toán ║Giá trị trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬════════ ════════ ═ ╬══════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1 ) ║ O(1) ║ ║ Xóa ║ O( 1) ║ O(1) ║ ╚═══════════╩══════════════ ═══ ╩════ ═══════ ════╝

    Các bài tập từ freeCodeCamp

    Hàng đợi

    Cấu trúc này có thể được biểu diễn dưới dạng hàng đợi trong cửa hàng tạp hóa. Ai đến ngay từ đầu sẽ được phục vụ trước - giống như trong cuộc sống.


    Đây là cách hàng đợi hoạt động

    Hàng đợi được sắp xếp theo nguyên tắc FIFO (First In First Out). Điều này có nghĩa là bạn chỉ có thể xóa một phần tử sau khi tất cả các phần tử được thêm trước đó đã bị xóa.

    Hàng đợi cho phép bạn thực hiện hai thao tác cơ bản: thêm các phần tử vào cuối hàng đợi ( xếp hàng) và xóa phần tử đầu tiên ( xếp hàng).

    Độ phức tạp của thời gian xếp hàng ════════╗ ║ Thuật toán ║Giá trị trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═══════ ═════════ ═ ╬══════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1 ) ║ O(1) ║ ║ Xóa ║ O( 1) ║ O(1) ║ ╚═══════════╩══════════════ ═══ ╩════ ═══════ ════╝

    Các bài tập từ freeCodeCamp

    bộ



    Đây là những gì rất nhiều trông giống như

    Một tập hợp lưu trữ các giá trị dữ liệu mà không theo một trật tự nhất định mà không lặp lại chúng. Nó cho phép bạn không chỉ thêm và xóa các phần tử: còn có một số phần tử khác chức năng quan trọng, có thể được áp dụng cho hai bộ cùng một lúc.

    • Một hợp kết hợp tất cả các phần tử từ hai bộ khác nhau thành một (không trùng lặp).
    • Phép giao phân tích hai tập hợp và tạo một tập hợp khác từ những phần tử có trong cả hai tập hợp ban đầu.
    • Sự khác biệt hiển thị danh sách các phần tử nằm trong một bộ nhưng không nằm trong bộ khác.
    • Tập hợp con tạo ra một giá trị Boolean cho biết liệu một tập hợp có bao gồm tất cả các phần tử của tập hợp khác hay không.
    Ví dụ triển khai bằng JavaScript

    Các bài tập từ freeCodeCamp

    Bản đồ

    Bản đồ là một cấu trúc lưu trữ dữ liệu theo cặp khóa/giá trị, trong đó mỗi khóa là duy nhất. Đôi khi nó còn được gọi là mảng kết hợp hoặc một cuốn từ điển. Bản đồ thường được sử dụng để tìm kiếm dữ liệu nhanh chóng. Nó cho phép bạn làm những việc sau:
    • thêm cặp vào bộ sưu tập;
    • xóa các cặp khỏi bộ sưu tập;
    • thay đổi một cặp hiện có;
    • tìm kiếm một giá trị được liên kết với một khóa cụ thể.

    Đây là cách cấu trúc bản đồ hoạt động

    Các bài tập từ freeCodeCamp

    Bảng băm

    Đây là cách bảng băm và hàm băm hoạt động

    Bảng băm là một cấu trúc giống như Bản đồ chứa các cặp khóa/giá trị. Nó sử dụng hàm băm để tính chỉ mục thành một mảng các khối dữ liệu nhằm tìm giá trị mong muốn.

    Thông thường, hàm băm lấy chuỗi ký tự làm đầu vào và xuất ra một giá trị số. Đối với cùng một đầu vào, hàm băm sẽ trả về số tương tự. Nếu hai đầu vào khác nhau được băm cho cùng một kết quả thì sẽ xảy ra xung đột. Mục tiêu là có càng ít trường hợp như vậy càng tốt.

    Vì vậy, khi bạn nhập cặp khóa/giá trị vào bảng băm, khóa sẽ được chuyển qua hàm băm và chuyển thành một số. Con số này sau đó được sử dụng làm khóa thực tế, tương ứng với một giá trị nhất định. Khi bạn nhập lại cùng một khóa, hàm băm sẽ xử lý nó và trả về kết quả số tương tự. Kết quả này sau đó sẽ được sử dụng để tìm giá trị liên quan. Cách tiếp cận này làm giảm đáng kể thời gian tìm kiếm trung bình.

    Độ phức tạp về thời gian của bảng băm ═════════ ═╗ ║ Thuật toán ║Trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬═════ ═══════ ════ ═╬════════ ═══════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(1) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(n) ║ ║ Xóa ║ O(1) ║ O(n) ║ ╚═══════════╩════════════ ═ ════╩════ ═════ ══════╝

    Các bài tập từ freeCodeCamp

    Cây tìm kiếm nhị phân


    Cây tìm kiếm nhị phân

    Cây là một cấu trúc dữ liệu bao gồm các nút. Nó có các tính chất sau:

    • Mỗi cây đều có một nút gốc (trên cùng).
    • Một nút gốc có 0 hoặc nhiều nút con.
    • Mỗi nút con có 0 hoặc nhiều nút con, v.v.
    Cây tìm kiếm nhị phân có hai thuộc tính bổ sung:
    • Mỗi nút có tối đa hai nút con (con cháu).
    • Mỗi nút nhỏ hơn các nút con của nó ở bên phải và các nút con của nó ở bên trái nhỏ hơn chính nó.
    Cây tìm kiếm nhị phân cho phép bạn nhanh chóng tìm, thêm và xóa các phần tử. Chúng được thiết kế sao cho thời gian của mỗi thao tác tỷ lệ thuận với logarit Tổng số các phần tử trong cây.

    Độ phức tạp về thời gian của cây tìm kiếm nhị phân ════════ ╗ ║ Thuật toán ║Giá trị trung bình ║Trường hợp xấu nhất ║ ╠═══════════╬══════ ══════ ═════ ╬═════════ ═════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Xóa ║ O(log n) ║ O(n) ║ ╚═══════════╩═══════════ ══════╩════ ════ ══════╝


    Các bài tập từ freeCodeCamp

    Cây tiền tố

    Cây tiền tố (được tải) là một loại cây tìm kiếm. Nó lưu trữ dữ liệu dưới dạng nhãn, mỗi nhãn đại diện cho một nút trong cây. Những cấu trúc như vậy thường được sử dụng để lưu trữ các từ và thực hiện tìm kiếm nhanh trên chúng - ví dụ: đối với chức năng tự động hoàn thành.

    Đây là cách cây tiền tố hoạt động

    Mỗi nút trong cây tiền tố ngôn ngữ chứa một chữ cái của từ. Để tạo thành một từ, bạn cần đi theo các cành cây, chuyển từng chữ cái một. Cây bắt đầu phân nhánh khi thứ tự các chữ cái khác với các từ khác trong đó hoặc khi từ kết thúc. Mỗi nút chứa một chữ cái (dữ liệu) và một giá trị Boolean cho biết liệu đó có phải là chữ cái cuối cùng trong từ hay không.

    Nhìn vào hình minh họa và cố gắng tạo thành các từ. Luôn bắt đầu với nút gốc ở trên cùng và thực hiện theo cách của bạn. Cây này chứa các từ sau: bóng, dơi, búp bê, do, dork, ký túc xá, gửi, giác quan.

    Các bài tập từ freeCodeCamp

    Đống nhị phân

    Đống nhị phân là một cấu trúc dữ liệu dựa trên cây khác. Mỗi nút trong đó có không quá hai nút con. Nó cũng là một cây hoàn hảo: điều này có nghĩa là tất cả các cấp độ trong đó đều chứa đầy dữ liệu và cấp độ cuối cùng được điền từ trái sang phải.


    Đây là cách hoạt động của đống tối thiểu và tối đa

    Một đống nhị phân có thể là tối thiểu hoặc tối đa. Trong vùng heap tối đa, khóa của bất kỳ nút nào luôn là nhiều chìa khóa hơn con cháu của ông hoặc ngang hàng với họ. Trong một đống tối thiểu, mọi thứ hoạt động theo cách khác: khóa của bất kỳ nút nào nhỏ hơn hoặc bằng khóa của nút con cháu của nó.

    Thứ tự các cấp trong đống nhị phân rất quan trọng, trái ngược với thứ tự của các nút trong cùng một cấp. Hình minh họa cho thấy trong heap tối thiểu ở cấp độ thứ ba, các giá trị không theo thứ tự: 10, 6 và 12.


    Độ phức tạp về thời gian của heap nhị phân ═════════ ═╗ ║ Thuật toán ║ Trung bình ║ Trường hợp xấu nhất ║ ╠═══════════╬══════ ═══════ ═══ ══╬═══════ ════════╣ ║ Dấu cách ║ O(n) ║ O(n) ║ ║ Tìm kiếm ║ O(n) ║ O(n) ║ ║ Chèn ║ O(1) ║ O(log n) ║ ║ Xóa ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═════════ ══╩══════════ ════════╩═══════════════╝

    Các bài tập từ freeCodeCamp

    đồ thị

    Đồ thị là tập hợp các nút (đỉnh) và các kết nối giữa chúng (các cạnh). Chúng còn được gọi là mạng.

    Đồ thị được chia thành hai loại chính: có hướng và vô hướng. Trong đồ thị vô hướng, các cạnh giữa các nút không có hướng, trong khi các cạnh trong đồ thị có hướng thì có.

    Thông thường, đồ thị được mô tả theo một trong hai dạng: nó có thể là danh sách kề hoặc ma trận kề.


    Đồ thị dưới dạng ma trận kề

    Danh sách kề có thể được coi là danh sách các phần tử, với một nút ở bên trái và tất cả các nút khác mà nó kết nối ở bên phải.

    Ma trận kề là một lưới các số trong đó mỗi hàng hoặc cột tương ứng với một nút khác nhau trong biểu đồ. Tại giao điểm của hàng và cột có một số cho biết sự hiện diện của kết nối. Số không có nghĩa là nó bị thiếu; đơn vị - rằng có một kết nối. Để biểu thị trọng số của mỗi kết nối, các số lớn hơn một được sử dụng.

    Có các thuật toán đặc biệt để xem các cạnh và đỉnh trong đồ thị - được gọi là thuật toán truyền tải. Các loại chính của chúng bao gồm tìm kiếm theo chiều rộng ( tìm kiếm theo chiều rộng) và chuyên sâu ( tìm kiếm theo chiều sâu). Ngoài ra, chúng có thể được sử dụng để xác định mức độ gần của các đỉnh nhất định của đồ thị với nút gốc. Video bên dưới cho biết cách thực hiện tìm kiếm theo chiều rộng trong JavaScript.