trang chủ-Tải chương trinh-4 kiểu dữ liệu trừu tượng là gì. Các kiểu dữ liệu trừu tượng do người dùng định nghĩa

4 kiểu dữ liệu trừu tượng là gì. Các kiểu dữ liệu trừu tượng do người dùng định nghĩa

Một kiểu dữ liệu mô tả một tập hợp các đối tượng có các thuộc tính tương tự nhau. Tất cả các ngôn ngữ lập trình truyền thống đều sử dụng tập hợp các kiểu dữ liệu cơ bản (thực, số nguyên, chuỗi, ký tự). Các kiểu dữ liệu cơ bản phải tuân theo một tập hợp các hoạt động được xác định trước. Ví dụ, kiểu dữ liệu cơ sở số nguyên cho phép bạn thực hiện các phép toán như cộng, trừ, nhân và chia.

Các ngôn ngữ lập trình truyền thống bao gồm các hàm tạo kiểu, trong đó phổ biến nhất là hàm tạo bản ghi. Ví dụ: đối với bản ghi kiểu KHÁCH HÀNG, bạn có thể xác định các trường dữ liệu. Mục nhập KHÁCH HÀNG sẽ là kiểu mới cấu trúc dữ liệu, sẽ lưu trữ thông tin về máy khách, bạn có thể truy cập trực tiếp vào cấu trúc dữ liệu này bằng cách tham khảo tên trường. Bạn có thể thực hiện các thao tác như VIẾT, ĐỌC, XÓA, CẬP NHẬT trên một bản ghi. Bạn không thể định nghĩa các thao tác mới cho các kiểu dữ liệu cơ bản.

Giống như các kiểu dữ liệu cơ bản, các kiểu dữ liệu trừu tượng (ATD) mô tả nhiều đối tượng tương tự. Có sự khác biệt giữa ATD và kiểu dữ liệu truyền thống:

· hoạt động theo ATD được xác định bởi người dùng;

· ATD không cho phép truy cập trực tiếp vào biểu diễn dữ liệu nội bộ và triển khai phương pháp.

Trong một số hệ thống OO (ví dụ: Smalltalk), các kiểu dữ liệu cơ bản được triển khai dưới dạng trừu tượng.

Để tạo một kiểu dữ liệu trừu tượng, bạn phải cung cấp:

tên loại;

Biểu diễn dữ liệu hoặc các biến thể hiện của một đối tượng thuộc sở hữu của ATD; mỗi biến thể hiện có một kiểu dữ liệu, có thể là kiểu cơ sở hoặc kiểu ATD khác;

· Các hoạt động và ràng buộc ATD được thực hiện bằng các phương thức.

Định nghĩa ATD xây dựng lại định nghĩa lớp. Một số hệ thống OO sử dụng từ khóa loại để phân biệt giữa các lớp và các loại khi đề cập đến các cấu trúc dữ liệu và các phương thức của một lớp và từ khóa lớp khi đề cập đến một tập hợp các thể hiện đối tượng. Loại (type) là một khái niệm tĩnh hơn, và lớp chủ yếu liên quan đến thời gian chạy. Sự khác biệt giữa lớp OO và loại OO có thể được minh họa bằng một ví dụ. Giả sử có một mẫu cho hàm tạo. Mẫu được kèm theo một mô tả về cấu trúc của nó, cũng như hướng dẫn sử dụng. Mẫu này là định nghĩa kiểu. Một tập hợp các sản phẩm thực được tạo bằng một mẫu, mỗi mẫu có số duy nhất(hoặc OID) tạo thành một lớp.

ATD, cùng với tính kế thừa, cho phép bạn tạo các đối tượng phức tạp. Một đối tượng phức tạp được hình thành bằng cách kết hợp các đối tượng khác có mối quan hệ phức tạp với nhau. Ví dụ đối tượng phức tạp có thể được tìm thấy trong các hệ thống an ninh sử dụng Nhiều loại khác nhau dữ liệu:

1. dữ liệu tiêu chuẩn (dạng bảng) về nhân viên (tên đầy đủ, số Tab, v.v.);

2. bitmap để lưu trữ ảnh nhân viên;

Khả năng làm việc với một môi trường dữ liệu phức tạp như vậy một cách tương đối dễ dàng làm tăng tầm quan trọng của các hệ thống OO trong thị trường cơ sở dữ liệu ngày nay.

Kiểu dữ liệu trừu tượng thường được gọi là kiểu dữ liệu không có sẵn rõ ràng trong ngôn ngữ lập trình; theo nghĩa này, khái niệm này là tương đối - một kiểu dữ liệu không có trong ngôn ngữ lập trình này có thể có trong ngôn ngữ lập trình khác.

Kiểu dữ liệu trừu tượng(ATD) được xác định bất kể nó được triển khai như thế nào:

§ tập hợp các giá trị có thể có của loại này,

§ và một tập hợp các hoạt động với các giá trị của loại này.

Việc sử dụng ADT có thể bị giới hạn trong giai đoạn phát triển phần mềm, nhưng để sử dụng rõ ràng trong chương trình, cần phải triển khai nó dựa trên các kiểu dữ liệu đã tồn tại (và đã được triển khai trước đó) trong ngôn ngữ lập trình:

§ cách biểu diễn các giá trị của loại này,

§ và việc thực hiện các thao tác với các giá trị kiểu này.

ADT không được xác định trước trong ngôn ngữ lập trình và thậm chí còn hơn thế nữa - các hoạt động xây dựng của các loại như vậy, được xác định trước bằng ngôn ngữ, chuyển câu hỏi về cách biểu thị các giá trị của loại này và thực hiện các hoạt động với các giá trị của loại này cho nhà phát triển-lập trình viên. Vì vậy, đối với những kiểu dữ liệu như vậy, vấn đề lựa chọn định nghĩa và phương pháp thực hiện các thao tác của biểu mẫu người xây dựng (giá trị và lưu trữ dữ liệu) thuộc loại này, bộ chọn Và bổ nghĩa các thành phần (giá trị và lưu trữ dữ liệu) thuộc loại này được gán cho nhà phát triển-lập trình viên.

Trong khái niệm về ATD, các khái niệm giao diện , mở cho người dùng, Và thực hiện ẩn từ anh ta. Vai trò đặc biệt của các khái niệm này trong khái niệm ADT có liên quan đến đề xuất cơ bản rằng khái niệm ADT độc lập với phương pháp thực hiện nó.

"Ngôn ngữ lập trình thực tế" hiện đại thường sử dụng thao tác xây dựng kiểu được xác định trước để xây dựng ADT. lớp học , cung cấp cho nhà phát triển-lập trình viên không chỉ phương tiện nhóm dữ liệu và hoạt động (với dữ liệu này) thành một tổng thể duy nhất, mà còn là phương tiện đóng gói, kế thừa và đa hình để kiểm soát cách dữ liệu đó được xây dựng và truy cập. Lưu ý rằng lớp mô tả một triển khai có thể có của ADT, ánh xạ của lớp tới ADT được biểu thị bằng hàm trừu tượng, nhưng mối quan hệ nghịch đảo thường không hoạt động, có thể có một số triển khai của cùng một ADT.



Trong nghiên cứu về kiểu dữ liệu trừu tượng, đã có trên giai đoạn đầu Nhận thức được vai trò quan trọng của khái niệm kiểu tham số hóa “. Thật vậy, ví dụ, ADT “Ngăn xếp” không phụ thuộc vào loại phần tử ngăn xếp, nhưng không thể triển khai ADT này bằng cách trỏ đến “phần tử cùng loại nào đó”. Các công cụ tương ứng để xây dựng các kiểu dữ liệu được tham số hóa đã được đưa vào ngôn ngữ lập trình Ada ngay từ đầu và trong "ngôn ngữ lập trình thực tế" hiện đại, công cụ nào chỉ xuất hiện kể từ khi phát triển thư viện STL. Ngày nay, khái niệm "lập trình tổng quát" chiếm một vị trí quan trọng trong lập trình thực tế do được đưa vào " ngôn ngữ thực tế lập trình" công cụ xây dựng cho các kiểu dữ liệu được tham số hóa (mẫu, bản mẫu , chung) .

Tất cả những điều trên có nghĩa là từ quan điểm phương pháp luận và lý thuyết, cần có một định nghĩa chính xác chi tiết hơn về khái niệm "kiểu dữ liệu trừu tượng". Về lý thuyết, khái niệm "kiểu dữ liệu trừu tượng" thường được định nghĩa là hệ đại số đa sắp xếp (đa cơ sở) , trong đó, ngoài tập hợp các giá trị có thể (sóng mang) và tập hợp các thao tác trên các giá trị đó, các khái niệm sau được làm nổi bật:

§ Sắp xếp và chữ ký - những khái niệm này cho phép phân loại cả phần tử sóng mang và hoạt động với chúng theo loại của chúng (đối với hoạt động - theo loại đối số và giá trị trả về của chúng).

§ Vị từ - quan hệ trên các phần tử của hỗ trợ. Điều này cho phép bạn xác định phạm vi giá trị có thể bằng cách áp đặt các hạn chế (yêu cầu) đối với giá trị được phép, cũng như trong giải thích tự nhiên để làm việc với tùy ý biểu thức logic, mà không buộc chúng phải được hiểu là các hàm liên thuộc cho các tập hợp hoặc dưới dạng các phép toán đa trị.

Trên cơ sở này, người ta có thể xem xét các kiểu dữ liệu trừu tượng từ một quan điểm logic-đại số tổng thể duy nhất, bao gồm các câu hỏi về hàm tạo (kiểu và giá trị), bộ chọn và bộ sửa đổi thuộc tính cho các đối tượng thuộc kiểu này.

Các khái niệm "cấu trúc dữ liệu" và "kiểu dữ liệu trừu tượng" có phần gần gũi. Tất nhiên, bạn có thể xem xét rằng những khái niệm này chỉ là hai quan điểm về cùng một thứ. Cách các giá trị ADT được biểu diễn luôn dựa trên một số cấu trúc dữ liệu, ít hoặc phức tạp hơn và việc triển khai các thao tác trên các giá trị đó đương nhiên phụ thuộc vào cấu trúc dữ liệu đã chọn này. Mặt khác, chúng tôi luôn có thể định dạng cấu trúc dữ liệu mà chúng tôi quan tâm dưới dạng ADT nếu chúng tôi thực sự muốn.

Tuy nhiên, chúng tôi sẽ phân biệt giữa hai khái niệm này, được đưa ra:

§ Kiểu dữ liệu trừu tượng - ngụ ý một mức độ trừu tượng nhất định để cố định kiểu dữ liệu (hướng miền) của ứng dụng, bất kể nó được triển khai như thế nào và ít nhất có thể đưa kiểu dữ liệu này vào thư viện ứng dụng cho sự phát triển cụ thể của một hệ thống phần mềm cụ thể. Một ADT có thể có một số triển khai thay thế dựa trên các cấu trúc dữ liệu khác nhau.

§ Cấu trúc dữ liệu - đúng hơn, một số sơ đồ tổ chức và quản lý dữ liệu, yêu cầu đặc điểm kỹ thuật phù hợp khi được sử dụng trong tình huống cụ thể khi giải các bài toán cụ thể.

Trước hết, các hệ đại số cơ bản toán học đương nhiên thuộc về các kiểu dữ liệu trừu tượng - dãy, tập hợp, quan hệ và ánh xạ (quan hệ hàm, hàm). Nhưng trong lập trình, điều quan trọng nhất không phải là nghiên cứu các tính chất chung của các khái niệm toán học này, mà là khả năng sử dụng chúng trong việc phát triển các mô hình để giải các bài toán trong lĩnh vực chủ đề, các thuật toán để giải các bài toán này và triển khai hiệu quả các giải pháp đã phát triển. thuật toán. Do đó, trong lập trình dưới dạng ATD, các biến thể hạn chế của các cơ bản này hệ thống đại số và mặt khác được mở rộng bởi các tập hợp hoạt động chuyên biệt có lợi ích thực tế từ quan điểm của phạm vi.

2.1. Sự liên tiếp.

Một dãy vô hạn (hữu hạn) được định nghĩa chính thức là một hàm có tập xác định là tập hợp các số nguyên dương: f(i)= , . Trong nhiều trường hợp, sẽ thuận tiện hơn khi lập chỉ mục một chuỗi từ đầu; thì tập xác định của / sẽ là tập hợp các số nguyên không âm. Tương tự, chúng ta định nghĩa một dãy hoặc danh sách hữu hạn là một hàm có tập xác định là tập hợp (1, 2, ..., ).

Khái niệm về một chuỗi trong đó các phần tử nối tiếp nhau là cơ bản trong lập trình. Trình tự xảy ra trong đầu ra từng dòng của mã chương trình máy tính, trong đó thứ tự của các lệnh xác định các hành động được thực hiện bởi chương trình. Một chuỗi các gói mạng tạo thành một thông điệp E-mail, bởi vì thông báo sẽ chỉ có ý nghĩa nếu các gói được nhận theo cùng thứ tự chúng được gửi. Trình tự đại diện cho các mối quan hệ quan trọng như vậy giữa các đối tượng là "tiếp theo" và "trước đó". Ngoài ra, các chuỗi thường được sử dụng để triển khai các cấu trúc dữ liệu khác, nghĩa là chúng là các khối xây dựng dựa trên thiết kế của các cấu trúc đó.

¨ Tập hợp các giá trị có thể có là một dãy hữu hạn các phần tử cùng loại.

¨ Tập hợp các thao tác:

§ Chèn phần tử theo thứ tự.

§ Xóa bỏ phần tử từ dãy.

§ Nhìn là hàm trả về giá trị của một phần tử của dãy.

Các loại của loại ADT này khác nhau ở cách mà các phần tử của chuỗi được truy cập và các hạn chế về nơi các phần tử được chèn vào và loại bỏ.

Đối với loại ATD này cây rơm , xếp hàng Và tháng mười hai (deque từ hàng đợi kết thúc kép ) một cách đặc trưng đọc phá hoại, bởi vì quyền truy cập vào các phần tử (đối với cả ba thao tác) bị giới hạn ở một trong các đầu của chuỗi và thao tác "xem phần tử khác" chỉ có thể được thực hiện bằng cách loại bỏ các phần tử cản trở điều này. Đối với ATD vectơ (mảng, vector), tệp (file) Và danh sách tuyến tính hạn chế truy cập cung cấp đọc không phá hủy, vì vậy nó có tầm quan trọng đặc biệt ( phái sinh) thao tác tra cứu trình tự.

Các hạn chế về quyền truy cập vào các phần tử trình tự được phản ánh một cách tự nhiên trong ngữ nghĩa của các hoạt động chính. truy cập nối tiếp dựa trên khái niệm vị trí hiện tại và cho phép truy cập (di chuyển, điều hướng) đến một (hoặc cả hai) đầu của chuỗi và đến vị trí liền kề (trái, phải hoặc cả hai) so với vị trí hiện tại. Nơi áp dụng các hoạt động chính trong trường hợp này thường được gắn với vị trí hiện tại. Truy cập trực tiếp (theo vị trí, ngẫu nhiên) dựa trên khái niệm toàn cầu chức vụ phần tử trong chuỗi và cung cấp quyền truy cập trực tiếp vào phần tử nếu biết vị trí của nó. Ví dụ, trong ATD vector động (mảng động, vector) , vị trí là chỉ số của phần tử. Nhưng trong các triển khai khác của các loại trình tự khác, mã định danh vị trí có thể được triển khai khác.

Các khái niệm về “số” và “vị trí” của một phần tử gần giống nhau, nhưng có thể không trùng nhau:

§ Con số là số thứ tự thực của phần tử trong dãy. Nhưng số thứ tự của phần tử thay đổi do việc thêm và xóa các phần tử trước đó, điều này gây ra một số bất tiện trong việc xác định các phần tử của dãy.

§ Chức vụ- tương tự số seri theo nghĩa, đối với một phần tử ở một vị trí nhất định, người ta có thể nói về các phần tử trước và sau của dãy (và vị trí của chúng). Tuy nhiên, giá trị của vị trí của một phần tử không thay đổi do chèn và xóa các phần tử trước đó, vì vậy giá trị của vị trí của phần tử có thể được lưu trữ và sử dụng để truy cập phần tử này trong tương lai. Ví dụ: trong một triển khai danh sách được liên kết của một chuỗi, khái niệm "vị trí" có thể được biểu thị bằng một con trỏ tới một phần tử và trong các triển khai khác, nó có thể được biểu thị bằng một loại định danh khác, được triển khai hỗ trợ đặc biệt.

Đối với ADT trình tự, các hoạt động bổ sung của biểu mẫu được quan tâm: nối hai trình tự, hủy liên kết thành hai trình tự. Ví dụ, trong ATD sợi dây loại hoạt động này thực sự là một trong những chính.

Đối với các loại "Trình tự" ATD khác nhau, có thể đạt được hiệu quả triển khai khác nhau hoạt động khác nhau. Ví dụ: nếu một triển khai cung cấp quyền truy cập trực tiếp hiệu quả vào các phần tử của trình tự, thì có khả năng thời gian thực hiện thao tác chèn ở giữa trình tự còn nhiều điều mong muốn. Các loại khác nhau(và triển khai) ATD "Trình tự" đưa ra cho lập trình viên nhiều đề xuất khác nhau cả về thành phần hoạt động và hiệu quả của việc triển khai chúng. Do đó, trong thực tế lập trình, thông thường, không có nhiều biến thể phổ biến của ADT này (cũng như khác) được quan tâm nhiều hơn, mà là những biến thể chuyên biệt và lập trình viên phải đưa ra lựa chọn phù hợp, có tính đến việc sử dụng chúng trong giải quyết các vấn đề thuộc phạm vi đề tài.

2.2. Bộ.

¨ Tập hợp các giá trị khả dĩ là tập hợp hữu hạn các phần tử cùng loại.

¨ Tập hợp các thao tác:

§ Chèn phần tử vào tập hợp.

§ Xóa bỏ phần tử từ tập hợp.

§ Thuộc về là một hàm trả về ĐÚNG VẬY nếu phần tử thuộc tập hợp.

Đối với một khái niệm cơ bản như vậy của toán học cổ điển, việc mở rộng tập hợp các phép toán thành một tập hợp cổ điển điển hình là điều tự nhiên. Nhưng vì một số lý do có tính chất thực dụng trong lập trình, loại ADT chung (phổ quát) như vậy chỉ được quan tâm hạn chế. Ví dụ, việc đưa vào hoạt động kết hợp các tập hợp giao nhau, khi được thực hiện, yêu cầu loại bỏ các phần tử giao nhau. Điều này rất có thể làm phức tạp việc thực hiện hoạt động này. Mặt khác, sự hiện diện của các bản sao có thể không quan trọng từ quan điểm của vấn đề đang được giải quyết, trong trường hợp đó, ATD là nhiều bộ. Tất nhiên, ý nghĩa cơ bản của khái niệm tập hợp được thể hiện bằng sự hiện diện của một tập hợp phong phú các phần mở rộng chuyên biệt của "Bộ" ADT cơ bản này, được sử dụng rộng rãi trong thực hành lập trình, cả hai đều do sức mạnh biểu cảm mạnh mẽ của điều này bộ công cụ trong việc phát triển một mô hình vấn đề và các thuật toán để giải quyết chúng, và do có sẵn các phương pháp triển khai hiệu quả các ATD này.

Các phần mở rộng chuyên dụng của "Bộ" ATD được xem xét theo nhiều hướng khác nhau:

§ Gần với khái niệm “bộ” là khái niệm “bộ”. Set (Túi, MultiSet) - cũng giống như tập hợp là họ các phần tử, không phụ thuộc vào quan hệ thứ tự được quy định trên các phần tử mà các phần tử trong tập hợp có thể lặp lại về giá trị. Nói chung, một tập hợp có thể được biểu diễn bằng một tập hợp, chẳng hạn, có các phần tử là các cặp [giá trị phần tử, số lần xuất hiện trong tập hợp].

§ Trong các ứng dụng thực tế, các phần tử của tập hợp thường được xác định, tức là một phần tử là một cặp [khóa phần tử, chính giá trị phần tử], Dictionary ADT là một ví dụ về phần mở rộng chuyên biệt như vậy của Set ADT. Trường hợp ưu tiên là khi khóa phần tử - duy nhất, I E. Một tập hợp không thể chứa hai phần tử có cùng khóa. Nhưng có thể khóa được sử dụng không phải là duy nhất, tức là xác định một cách mơ hồ giá trị thực của phần tử. Nói chung, một tập hợp (và tập hợp) có khóa không phải là duy nhất có thể được biểu diễn dưới dạng một tập hợp có khóa duy nhất bằng cách làm cho loại giá trị của phần tử trở nên phức tạp hơn, chẳng hạn, bằng cách coi giá trị của phần tử là một tập hợp các giá trị của loại trước (có cùng khóa).

§ Có vẻ như việc gán một quan hệ thứ tự, một phần hoặc tuyến tính, trên tập hợp là điều tự nhiên, “Hàng đợi ưu tiên” của ADT là một ví dụ về phần mở rộng chuyên biệt như vậy của “Tập hợp” ADT. Tương tự như vậy, trong lĩnh vực chủ đề của vấn đề đang được giải quyết, các quan hệ khác trên tập hợp có thể được quan tâm.

§ Một vị trí cơ bản trong toán học bị chiếm giữ bởi khái niệm quan hệ tương đương và theo đó, khái niệm phân hoạch một tập hợp thành các lớp tương đương. Đương nhiên, khái niệm này được sử dụng rộng rãi trong việc phát triển thực tế các mô hình để giải quyết vấn đề. Các môn học. ADT "Họ các tập hợp rời rạc" (Disjoint Sets, Partitions, Partitions) là một ví dụ về phần mở rộng chuyên biệt tương ứng của ATD "Set".

Đối với các phần mở rộng chuyên biệt của “Bộ” ATD, các hoạt động nêu trên được chỉ định một cách tự nhiên theo cách thích hợp và các hoạt động quan tâm mới xuất hiện.

2.3. Từ điển (Bản đồ), tên khác là một mảng kết hợp.

¨ Tập hợp các giá trị có thể - tập hợp hữu hạn các phần tử cùng loại, có dạng , trong đó Khóa - chìa khóa duy nhất phần tử, Giá trị - giá trị thực tế.

¨ Tập hợp các thao tác:

§ Chèn một phần tử (có khóa) thành một tập hợp.

§ Xóa bỏ một phần tử (được cung cấp bởi một khóa) từ một tập hợp.

§ Tìm phần tử– một hàm trả về giá trị của một phần tử theo khóa hoặc giá trị “trống” nếu phần tử có khóa như vậy không có trong tập hợp.

ADT "Từ điển" là một phiên bản chuyên biệt của khái niệm ánh xạ (được lưu trữ) (các khóa tới giá trị), được sử dụng rộng rãi trong lập trình thực tế. Nhưng đối với một số lĩnh vực chủ đề, có thể thuận tiện hơn khi thiết kế ATD lập bản đồ , gần với định nghĩa toán học cổ điển hơn .

2.4. Hàng đợi ưu tiên.

¨ Tập hợp các giá trị khả dĩ là tập hợp hữu hạn các phần tử cùng loại. Trên các tập hợp (giá trị có thể), một quan hệ thứ tự tuyến tính được chỉ định, được coi là so sánh các phần tử theo mức độ ưu tiên. Mức độ ưu tiên có thể được tách biệt như một thành phần của giá trị phần tử hoặc được tính hàm đã cho từ giá trị của phần tử.

Lưu ý rằng một tập hợp các giá trị có thể như vậy cũng có thể được coi là một tập hợp các chuỗi (với việc liệt kê các phần tử của nó theo một thứ tự tuyến tính nhất định).

¨ Tập hợp các thao tác:

§ Chèn phần tử trong một tập hợp (được sắp xếp tuyến tính).

§ Xóa tối thiểu phần tử từ tập hợp.

§ Tìm giá trị nhỏ nhất là hàm trả về giá trị của phần tử nhỏ nhất trong tập hợp.

Chúng tôi cũng xem xét các biến thể (thiết yếu) của ADT này với các hoạt động bổ sung:

§ Chia hàng đợi thành hai đặt giá trị(độ ưu tiên) của phần tử - đến hàng đợi của các phần tử có mức độ ưu tiên thấp hơn và hàng đợi của phần còn lại.

§ Xâu chuỗi hai hàng đợi, trong đó một trong số đó có tất cả các phần tử có mức ưu tiên cao hơn tất cả các phần tử của hàng đợi kia, thành một hàng đợi ưu tiên mà không bảo toàn các hàng đợi nối ban đầu.

§ Hợp nhất hai tập hợp có thứ tự khác nhau (hợp nhất hai hàng đợi như vậy) thành một tập hợp có thứ tự (một hàng đợi ưu tiên), cũng như không giữ nguyên những thứ đã hợp nhất ban đầu.

§ Giảm giá trị (độ ưu tiên) của phần tử được chỉ định.

§ Xoá (tùy tiện) một phần tử đã cho ra khỏi tập hợp.

2.5. Tập rời rạc, phân vùng, phân vùng.

¨ Tập các giá trị có thể là các tập hữu hạn (họ) các tập hữu hạn không trùng nhau. Các yếu tố của gia đình được xác định, tức là mỗi bộ trong họ có một tên (duy nhất).

¨ Tập hợp các thao tác:

§ Hợp Nhất(A,B)– một phép toán có dạng A:= A È B mà không bảo toàn các tập hợp ban đầu (có nghĩa là giá trị mới của họ sẽ vẫn là họ của các tập hợp rời rạc và số lượng của chúng sẽ giảm đi).

§ tìm bộ là một hàm trả về, với một x đã cho, tên của một tập X như vậy trong họ x Î X.

2.6. Cây, đồ thị và quan hệ tổng quát.

Trong toán học rời rạc, người ta đặc biệt chú ý đến các mối quan hệ (hữu hạn) của dạng - cây, đồ thị và mạng (đa đồ thị, siêu đồ thị), có cách giải thích hình học xác định:

¨ đồ thị là một quan hệ nhị phân (hữu hạn) (đối xứng trong trường hợp đồ thị vô hướng), E Í V 2 , trong đó V là tập đỉnh và E là tập các cạnh của đồ thị.

Trong toán học rời rạc, E thường không được định nghĩa là một tập hợp mà là một tập hợp các cạnh của đồ thị, điều này cho phép chúng ta xem xét các đồ thị trong đó một cặp đỉnh có thể được nối với nhau bằng một số cạnh (ví dụ: được dán nhãn khác nhau).

¨ Cây là một mối quan hệ nhị phân của thứ tự bộ phận (nghiêm ngặt), đáp ứng thêm các yêu cầu (phân cấp, cấu trúc cây):

§ từ thực tế là x<у,z следует, что у и z сравнимы, т.е. либо у£z либо z£у (х<у трактуется как: х встречается раньше у в пути к корню дерева, х – потомок, у - предок);

§ trong tập V (các đỉnh của cây) có phần tử lớn nhất (gốc của cây).

Các cây có thể được phân biệt nếu thứ tự các con trai (cho ít nhất một) đỉnh của cây là khác nhau. cây đặt hàng là một cây trong đó đối với mỗi đỉnh, thứ tự trên tập hợp các đỉnh con được chỉ định, tức là trẻ em có thể được định nghĩa là thứ nhất, thứ hai, v.v.

¨ Mạng lưới là một quan hệ có dạng tổng quát, có thể hiểu là một quan hệ tổng quát - E Í VÈV 2 È...V k , hoặc là một quan hệ (E Í V k) với tập các phần tử V có một "rỗng" (hư cấu) yếu tố.

Tất nhiên, những khái niệm này được sử dụng rộng rãi trong việc phát triển các mô hình miền vấn đề. Nhưng cũng giống như trường hợp của các tập hợp, vì một số lý do có tính chất thực dụng trong lập trình, một ADT thuộc loại chung (phổ quát) như vậy chỉ được quan tâm hạn chế. Chính xác hơn, tất nhiên, các loại biểu diễn cây, đồ thị và mạng được sử dụng rộng rãi trong thực hành lập trình. Nhưng việc kết hợp chúng với một tập hợp các hoạt động phổ quát và thiết kế một ADT phổ quát như vậy dường như chỉ hữu ích trong các tình huống đơn giản.

Vai trò cơ bản của cây và biểu đồ thể hiện đúng hơn trong bối cảnh của một vấn đề được áp dụng khi chọn cấu trúc dữ liệu để triển khai hiệu quả ADT đã chọn và thuật toán để giải quyết vấn đề nói chung. Nhưng trong bối cảnh như vậy, cả cách biểu diễn và tập hợp các hoạt động trên các cây, biểu đồ và mạng này đều được chuyên biệt hóa một cách tự nhiên phù hợp với một bối cảnh cụ thể.

Phụ lục chương trình làm việc cho môn học "Cấu trúc và thuật toán xử lý dữ liệu trong máy tính"

Kiểu dữ liệu trừu tượng "Danh sách".

Danh sách- một chuỗi các phần tử của một loại nhất định Một1 , Một2 , ..., Một N, Ở đâu N https://pandia.ru/text/78/308/images/image001_307.gif" width="13" height="16">1, sau đó Một1

Nó được gọi là phần tử đầu tiên, và MỘT là phần tử cuối cùng của danh sách. Các phần tử của danh sách được sắp xếp tuyến tính theo vị trí của chúng trong danh sách. yếu tố ai đi trước yếu tố ai+1 Vì Tôi = 1,2, N-1 Và ai nên phía sau ai-1 Vì Tôi = 2,3, N. Mỗi phần tử của danh sách ai Nó có chức vụ Tôi, Tôi=1,2, N. Có một mục trong danh sách , biểu thị sự kết thúc của danh sách - không. Nó theo sau phần tử cuối cùng của danh sách.

Các nhà khai thác của "Danh sách" ATD:

1. CHÈN( x, R,l). Toán tử này chèn một đối tượng X vào vị trí r trong danh sách l di chuyển các phần tử từ vị trí p trở lên đến vị trí cao hơn tiếp theo. Như vậy, nếu danh sách l bao gồm các yếu tố Một1 , Một2 , ..., MỘTN a1, a2, ..., ar-1, x, ar, ..., MộtN.. Nếu p lấy giá trị không, thì chúng ta sẽ có Một1 , Một2 , ..., MộtN , , X. Nếu trong danh sách l không có vị trí R, thì kết quả của câu lệnh này là không xác định.

2. ĐỊNH VỊ(x , l ). Hàm này trả về vị trí của một đối tượng X trong danh sách l. Nếu đối tượng nằm trong danh sách x xảy ra nhiều lần, vị trí của đối tượng đầu tiên từ đầu danh sách được trả về x. Nếu đối tượng X không có trong danh sách l, sau đó trả về không.

3. LẤY LẠI(P , l ). Hàm này trả về phần tử tại vị trí r trong danh sách l. Kết quả là không xác định nếu p = không hoặc trong danh sách l không có vị trí r.

4. XÓA BỎ(P , l ). Toán tử này loại bỏ phần tử tại vị trí r danh sách l. Vì vậy, nếu danh sách l bao gồm các yếu tố Một1 , Một2 , ..., MỘTN, thì sau khi thực hiện toán tử này, nó sẽ giống như a1, a2, ...,, áp dụng- Tôi , áp dụng+ Tôi, ..., MỘT N. Kết quả là không xác định nếu trong danh sách l không có vị trí r hoặc r = không.

5. KẾ TIẾP( P, l ) Và TRƯỚC (p, l ). Các hàm này lần lượt trả về các vị trí tiếp theo và trước đó từ vị trí r trong danh sách l. Nếu như R - vị trí cuối cùng trong danh sách l Tiếp tục (P, l) = không. Chức năng NEXT không được xác định khi p=không. Hàm PREVIOUS không được xác định nếu p=1. Cả hai hàm đều không xác định nếu trong danh sách l không có vị trí r.

6. KIẾM TIỀN( l ) . Chức năng này tạo một danh sách l rỗng và trả về vị trí không.

7. ĐẦU TIÊN(l ). Hàm này trả về vị trí đầu tiên trong danh sách L. Nếu danh sách trống thì trả về vị trí không.

8. DANH SÁCH IN(l ). In các phần tử của một danh sách l theo thứ tự mà chúng xuất hiện trong danh sách.

Biểu diễn một danh sách bằng cách sử dụng một mảng:

Xem danh sách với danh sách liên kết đơn:

chỉ định:

- con trỏ đến đầu danh sách,

· cuối cùng - con trỏ đến phần tử cuối cùng trong danh sách ,

· chiều dài tối đa – độ dài tối đa (số phần tử) trong danh sách.

Biểu diễn danh sách bằng danh sách liên kết kép:

bài tập:

1. Viết chương trình chèn, bớt, tìm phần tử của danh sách đã sắp xếp, sử dụng hàm thực thi danh sách

§ mảng,

§ con trỏ.

2. Viết chương trình gộp

§ hai danh sách liên kết được sắp xếp,

§ n danh sách liên kết được sắp xếp,

3. Cho một đa thức có dạng

p(x) = c1 xe1 + c2 xe2 + + VớiNXN, Ở đâu e1 > e2 > ... > eN> 0.

Một đa thức như vậy có thể được biểu diễn dưới dạng một danh sách được liên kết, trong đó mỗi phần tử có ba trường: một cho hệ số VớiTôi thứ hai là cho số mũ eTôi thứ ba là dành cho một con trỏ tới phần tử tiếp theo. Để biểu diễn các đa thức đã mô tả, hãy viết chương trình cộng và nhân các đa thức bằng cách sử dụng biểu diễn này.

4. Triển khai DANH SÁCH ATD cho bất kỳ loại dữ liệu nào và các câu lệnh INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST của nó:

§ danh sách được đưa ra dưới dạng một mảng,

§ danh sách được cho dưới dạng danh sách liên kết đơn,

§ Danh sách được cho dưới dạng danh sách liên kết kép.

chương chương trình làm việc 2.1.2

Kiểu dữ liệu trừu tượng "Ngăn xếp".

Cây rơm - là một loại danh sách đặc biệt trong đó tất cả các thao tác thêm và xóa chỉ được thực hiện ở một đầu, được gọi là hội nghị thượng đỉnh , (đứng đầu). Phương pháp truy cập ngăn xếp được sử dụng LIFO(nhập sau xuất trước - nhập sau - xuất trước).

Toán tử "Ngăn xếp" ATD:

1. KIẾM TIỀN(S). Làm trống ngăn xếp S.

2. ĐỨNG ĐẦU(S). Trả về phần tử từ đỉnh ngăn xếp S. Thông thường, đỉnh ngăn xếp được xác định bởi vị trí 1, khi đó TOP(S) có thể được viết dưới dạng các toán tử danh sách chung là RETRIEVE(FIRST(S), S).

3. NHẠC POP(S). Xóa một phần tử khỏi đỉnh ngăn xếp (bật nó ra khỏi ngăn xếp), về mặt toán tử danh sách, toán tử này có thể được viết là DELETE(FIRST(S), S).

4. XÔ(x, S ). Chèn một phần tử X lên đỉnh ngăn xếp S (đẩy phần tử vào ngăn xếp). Phần tử trước đó ở trên cùng của ngăn xếp trở thành phần tử tiếp theo ở trên cùng, v.v... Về mặt toán tử danh sách tổng quát, câu lệnh này có thể được viết là INSERT(;c, FIRST(S), S).

5. TRỐNG(S) . Hàm này trả về true nếu ngăn xếp S trống, và sai khác.

mảng:

Biểu diễn ngăn xếp với danh sách liên kết đơn:

bài tập:

Triển khai STACK ATD cho bất kỳ loại dữ liệu nào và các toán tử MAKENULL, TOP, POP, PUSH, EMPTY của nó.

§ ngăn xếp được đưa ra dưới dạng một mảng,

§ Ngăn xếp được cho dưới dạng danh sách liên kết đơn.

Chương trình làm việc mục 2.1.2

Kiểu dữ liệu trừu tượng "Hàng đợi".

Xếp hàng (hàng đợi) là một loại danh sách đặc biệt trong đó các phần tử được chèn vào từ một đầu, được gọi là ở phía sau (phía sau), nhưng được loại bỏ từ khác, đằng trước (đằng trước). Hàng đợi còn được gọi là "danh sách FIFO" (FIFO là viết tắt của nhập trước xuất trước). Toán tử hàng đợi tương tự như toán tử ngăn xếp. Sự khác biệt cơ bản giữa chúng là việc chèn các phần tử mới được thực hiện trong cuối danh sách và không đến phần đầu, như trong ngăn xếp.

Toán tử "Hàng đợi" ATD:

1. KIẾM TIỀN(Hỏi) xóa hàng đợi Q , làm cho nó trống rỗng.

2. ĐẰNG TRƯỚC(Hỏi) - một hàm trả về phần tử đầu tiên của hàng đợi q. Bạn có thể triển khai tính năng này bằng cách sử dụng toán tử danh sách như RETRIEVE(FIRST(Q), Q ).

3. TUYỆT VỜI(Một, Hỏi) chèn một phần tử Xđến cuối hàng đợi Q.

Sử dụng các toán tử danh sách, câu lệnh này có thể được thực hiện như sau: INSERT(x, END(Q), Q ).

4. DEQUEUE(Hỏi) loại bỏ phần tử đầu tiên của hàng đợi Q . Đồng thời triển khai bằng cách sử dụng các toán tử danh sách như DELETE(FIRST(Q), Q).

5. TRỐNG(Hỏi) trả về true khi và chỉ khi Q là một hàng đợi trống.

theo chu kỳ mảng:

chỉ định:

Hỏi- xếp hàng,

Hỏi. đằng trước- con trỏ đến đầu hàng đợi,

Hỏi. ở phía sau- một con trỏ đến cuối hàng đợi.

Đại diện cho một hàng đợi với danh sách liên kết đơn:

bài tập:

Triển khai QUEUE ATD cho bất kỳ loại dữ liệu nào và các toán tử MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY của nó.

§ hàng đợi được chỉ định là một mảng tuần hoàn,

§ Hàng đợi được cho dưới dạng danh sách liên kết đôi.

Kiểu dữ liệu trừu tượng "Cây".

Cây là một tập hợp các phần tử được gọi là nút thắt (một trong số đó được định nghĩa là nguồn gốc ), và quan hệ ("cha mẹ"), tạo thành một cấu trúc phân cấp của các nút. Các nút, giống như các mục trong danh sách, có thể là bất kỳ loại mục nào. Chính thức, một cây có thể được định nghĩa đệ quy như sau.

1. Một nút là một cây. Nút này cũng là gốc của cây này.

2. Hãy để P -đây là một nút, một t1 , T2, ...,TK- cây có rễ N1 . N2 , ..., nk tương ứng. Bạn có thể xây dựng một cây mới bằng cách làm P nút cha N1 . N2 , ..., nk. trong cây này P sẽ là gốc, một t1 , T2, ...,TK - cây con gốc này. Nút thắt N1 . N2 , ..., nk gọi điện con trai nút P.

Định nghĩa này thường bao gồm khái niệm cây rỗng , tức là "cây" không có nút, cây như vậy được biểu thị bằng từ không .

Ví dụ: Về phần đầu của cuốn sách có thể được biểu diễn dưới dạng sơ đồ bằng một cái cây. Mối quan hệ cha-con được hiển thị dưới dạng một dòng. Cây thường được vẽ từ trên xuống dưới để bố mẹ ở trên "con".

DIV_ADBLOCK135">

Chiều cao nút cây là độ dài của con đường dài nhất từ ​​nút này đến bất kỳ lá nào. Trong ví dụ chiều cao nút Ch.1 bằng 1, nút Chương 2 - 2 và nút Ch. z-0. chiều cao cây phù hợp với chiều cao của gốc. Độ sâu nút được định nghĩa là độ dài của đường dẫn (nó là duy nhất) từ gốc đến nút này.

Các nút con của nút thường được sắp xếp từ trái sang phải. Do đó, hai cây trong hình là khác nhau, do thứ tự của các con của nút MỘT khác biệt. Nếu thứ tự của các con trai bị bỏ qua, thì một cái cây như vậy được gọi là rối loạn , nếu không thì cây được gọi là ngăn nắp .

Người điều hành ATD "Cây":

1. CHA MẸ(N, T). Hàm này trả về cha của nút P trong một cái cây t. Nếu như P là một root không có cha mẹ, thì trong trường hợp này trả về không. Đây không chỉ ra rằng một thoát cây đã xảy ra.

2. NGOÀI TRÁI__ ĐỨA TRẺ(N , T). Hàm này trả về con ngoài cùng bên trái của một nút N trong một cái cây t. Nếu như N là một chiếc lá (và do đó không có con trai), sau đó trả về không.

3. PHẢI_ ANH EM RUỘT(N , T). Hàm này trả về anh chị em bên phải của nút P trong một cái cây t hoặc giá trị không, .nếu nó không tồn tại. Đó là những gì cha mẹ dành cho. r nút P và tất cả các con trai của nút R, thì trong số những con này là nút ngay bên phải của. nút P.

4. NHÃN(N , t ). Trả về nhãn của nút N. cây t. Chức năng này yêu cầu các nhãn được xác định trên các nút của cây.

5. TẠO NÊN(v , t 1 , t 2 , ..., ti ,) là một họ các hàm mà với mỗi i = 0, 1, 2,... tạo một gốc mới r dán nhãn v và sau đó gốc này tạo ra i con trai trở thành gốc của các cây con t1 , T2, ….ti;. Các hàm này trả về một gốc cây r. Lưu ý rằng nếu i = 0, thì một nút được trả về r, vừa là gốc vừa là lá.

6. NGUỒN GỐC(t ) trả về nút là gốc của cây t, Nếu như t- cây rỗng sau đó trả về không.

7. KIẾM TIỀN(t ). Toán tử này tạo một cây t cây rỗng.

Biểu diễn một cây bằng cách sử dụng một mảng cha mẹ:

Biểu diễn cây bằng danh sách liên kết:

Đại diện của một cái cây bởi, con trai bên trái và anh em bên phải.

Các ký hiệu trong hình:

không gian nút – mảng nút cây,

    nhãn – nhãn nút, tiêu đề – chỉ số của con trai bên trái trong danh sách con trai,

không gian tế bào – một mảng các danh sách con trai của các nút,

    nút – con trỏ tới nút trong mảngkhông gian nút , Kế tiếp – chỉ số của con trai bên phải trong danh sách con trai.

bài tập:

1. Cho một cái cây:

DIV_ADBLOCK137">

§ cây được đưa ra dưới dạng một mảng các bản ghi nút chứa chỉ số của con trai ngoài cùng bên trái, chỉ số của anh em bên phải và nhãn,

§ một cây nhị phân liên thông được xác định bằng cách sử dụng các con trỏ tới các con trái và phải.

4. Viết các hàm duyệt cây nhị phân theo thứ tự tiến, lùi và đối xứng.

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng "Set".

một bó thường được mô tả dưới dạng một dãy các phần tử của nó được đặt trong dấu ngoặc nhọn, ví dụ (1, 4) biểu thị một tập hợp gồm hai phần tử, các số 1 và 4. Thứ tự viết các phần tử của tập hợp là không đáng kể, vì vậy bạn có thể viết (4, 1) giống như (1, 4), khi viết cùng một tập hợp. Một tập hợp không phải là một danh sách (ít nhất là trên cơ sở thứ tự tùy ý trong đó các phần tử được viết). Tập hợp không có phần tử lặp lại ((1, 4, 1) không phải là một tập hợp).

Khái niệm cơ bản của lý thuyết tập hợp là khái niệm về quan hệ thuộc bộ , được biểu thị bằng ký hiệu . Như vậy mục nhập X X không thuộc tập hợp MỘT", I E. X không phải là phần tử của tập hợp MỘT. tồn tại bộ đặc biệt, được biểu thị bằng ký hiệu , được gọi là rỗng, nhiều , và không có phần tử nào. Đặt DIV_ADBLOCK138">

Họ nói rằng nhiều MỘT chứa trong vô số TRONG(hoặc bật lên vào vô số TRONG),đánh vần MỘT TRONG hoặc TRONG MỘT nếu bất kỳ phần tử nào của tập hợp MỘT cũng là một phần tử của tập hợp TRONG. Khi MỘT TRONG cũng nói rằng nhiều MỘT là tập hợp con của tập hợp TRONG.

Ví dụ: (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif" width="15" height="15 src="> TRONG và A B thì tập hợp A được gọi là riêng, đúng hoặc tập hợp con nghiêm ngặt bộ TRONG.

Các phép toán chính được thực hiện trên các tập hợp là hợp, giao và hiệu. Sự kết hợp bộ MỘT Và TRONG(ký hiệu là MỘT TRONG) là tập hợp gồm các phần tử thuộc ít nhất một trong các tập hợp MỘT Và TRONG.

băng qua bộ MỘT Và TRONG(ký hiệu là MỘT TRONG) Tập hợp gọi là tập hợp chỉ gồm các phần tử thuộc tập hợp đó. MỘT, và nhiều TRONG. sự khác biệt bộ MỘT Và TRONG(ký hiệu là MỘT\ b) là tập hợp chỉ gồm các phần tử của tập hợp đó MỘT, không thuộc tập hợp TRONG.

Ví dụ: nếu A \u003d (a, b, c) và B \u003d (b, a), thì A B \u003d (a, b, c, d), A B \u003d (b) và A \ B \u003d (một, c ).

Toán tử "Đặt" ADT:

1. LIÊN HIỆP(MỘT, B,C) MỘT Và TRONG VỚI, bình đẳng MỘT TRONG.

2. NGÃ TƯ(MỘT, B,C) đã đặt đối số "đầu vào" MỘT Và TRONG, và kết quả là - tập hợp "đầu ra" VỚI, bình đẳng MỘT TRONG..

3. SỰ KHÁC BIỆT(MỘT, B,C) đã đặt đối số "đầu vào" MỘT Và TRONG, và kết quả là - tập hợp "đầu ra" VỚI, bình đẳng A/B.

4. HỢP NHẤT( MỘT , B, C) nhà điều hành thực hiện sáp nhập (hợp nhất), hoặc hợp của các tập hợp rời rạc . Toán tử này không khác gì toán tử. LIÊN HIỆP, nhưng ở đây giả định rằng toán hạng đặt không cắt nhau (tức là không có yếu tố phổ biến). Toán tử gán cho tập hợp VỚI nghĩa MỘT TRONG, nhưng kết quả sẽ không xác định nếu A B , tức là, trong trường hợp khi các bộ MỘT Và TRONG có những phần tử chung.

5. thành viên(x, A ) có nhiều lý lẽ MỘT và đối tượng X cùng kiểu với các phần tử của tập hợp MỘT, và trả về một giá trị boolean ĐÚNG VẬY(đúng) nếu X a", "b", "c"))= "MỘT". Toán tử được định nghĩa theo cách tương tự TỐI ĐA.

11.BÌNH ĐẲNG(MỘT , TRONG ) trả về một giá trị ĐÚNG VẬY khi và chỉ nếu các tập hợp MỘT Và TRONGđược tạo thành từ các phần tử giống nhau.

12. TÌM THẤY(x ) hoạt động trong môi trường có tập hợp các tập hợp rời nhau. Nó trả về tên của tập hợp (đơn) có chứa phần tử x.

Đặt đại diện:

Một tập hợp có thể được chỉ định bằng cách sử dụng một mảng hoặc một danh sách được liên kết.

bài tập:

1. Cho hai tập hợp A = (1, 2, 3) và B = (3, 4, 5). Điều gì sẽ là kết quả của việc thực hiện các tuyên bố sau đây?

CÔNG ĐOÀN(A. B. C),

GIAO ĐOẠN(A, B, C),

SỰ KHÁC BIỆT (A. B. C),

THÀNH VIÊN(l. A),

CHÈN(1,A),

XÓA(1, A),

2. Triển khai "Bộ" ADT cho bất kỳ loại dữ liệu nào và các toán tử của nó MAKENULL, UNION, INTERSECTION, MEMBER, MIN.

tập hợp được chỉ định bằng cách sử dụng một mảng có độ dài cố định và một con trỏ tới vị trí chiếm giữ cuối cùng trong mảng,

tập hợp được xác định bằng danh sách liên kết chưa sắp xếp,

tập hợp được xác định bằng danh sách liên kết được sắp xếp,

Chương trình làm việc mục 2.1.3

Các loại tập hợp đặc biệt

Kiểu dữ liệu trừu tượng “Cây tìm kiếm nhị phân”

Cây tìm kiếm nhị phân - một cấu trúc dữ liệu để biểu diễn các tập hợp có các phần tử được sắp xếp theo một số quan hệ thứ tự tuyến tính. Toán tử tập hợp có thể được thực hiện trên cây tìm kiếm nhị phân CHÈN, XÓA BỎ, THÀNH VIÊN Và TỐI THIỂU, và thời gian thực hiện của chúng trung bình là bậc O(log n) đối với các tập hợp bao gồm P phần tử.

Một đặc điểm của cây tìm kiếm nhị phân là các nút của nó được gắn nhãn bằng các phần tử tập hợp (các nút của cây chứa các phần tử tập hợp). Hơn nữa, tất cả các phần tử được lưu trữ trong các nút của cây con bên trái của bất kỳ nút nào X, nhỏ hơn phần tử chứa trong nút X, và tất cả các phần tử được lưu trữ trong các nút của cây con bên phải của nút X, yếu tố hơn chứa trong nút x.

Ví dụ về cây nhị phân:

https://pandia.ru/text/78/308/images/image023_7.jpg" width="277" height="122 src=">

Biểu diễn của cây AVL không khác với biểu diễn của cây tìm kiếm nhị phân.

Một loại cây tìm kiếm cân bằng khác là 2-3 cây. Cấu trúc của cây 2-3 khác với cấu trúc của cây tìm kiếm nhị phân, đối với cây 2-3, thông thường tất cả các nút đều có 2 hoặc 3 nút con, tất cả các đường đi từ gốc đến lá đều có cùng độ dài , và tất cả các phần tử của tập hợp được chứa trong các lá. Các nút 2-3 của cây được chia thành bên trong và đầu cuối (lá). Các nút bên trong chỉ được sử dụng để định tuyến tìm kiếm cây. Mỗi nút bên trong chứa các khóa phần tử nhỏ nhất của nút con thứ hai và thứ ba (nếu có nút con thứ ba) và con trỏ tới các nút con.

Biểu diễn cây tìm kiếm nhị phân được liên kết:

Biểu diễn cây 2-3 liên thông cân đối:

bài tập:

1. Vẽ tất cả các cây tìm kiếm nhị phân có thể có cho bốn phần tử 1, 2, 3 và 4.

2. Chèn các số nguyên 7, 2, 9, 0, 5, 6, 8, 1 vào cây tìm kiếm nhị phân trống.

3. Cho biết kết quả của việc bỏ đi số 7 rồi đến số 2 từ cây thu được ở bài tập trước.

4. Vẽ cây 2-3 là kết quả của việc chèn các phần tử 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 vào tập hợp trống (được biểu diễn dưới dạng cây 2-3).

5. Cho biết kết quả của việc loại bỏ phần tử 3 khỏi cây 2-3 thu được trong bài tập trước.

3. Triển khai ADT Cây tìm kiếm cho bất kỳ loại dữ liệu nào và các câu lệnh INSERT, DELETE, MEMBER và MIN của nó.

cây được đưa ra dưới dạng cây nhị phân được kết nối

cây được tặng dưới dạng 2-3 cây

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng "Từ điển".

Từ điển – một bộ dành cho việc lưu trữ các đối tượng "hiện tại" với việc chèn hoặc xóa định kỳ một số trong số chúng. Đôi khi, việc biết liệu một phần tử cụ thể có tồn tại trong một tập hợp nhất định hay không cũng trở nên cần thiết. Từ điển được triển khai bằng cách sử dụng “Từ điển” ADT với các toán tử CHÈN,XÓA BỎ Và THÀNH VIÊN. Tập hợp các toán tử từ điển cũng bao gồm toán tử KIẾM TIỀNđể khởi tạo cấu trúc dữ liệu ADT.

Một từ điển có thể được biểu diễn bằng bảng băm. Bảng được xây dựng trên cơ sở ý tưởng sau: tập hợp tiềm năng của các phần tử (có thể là vô hạn) được chia thành một số hữu hạn các lớp. Vì TRONG lớp được đánh số từ 0 đến TRONG 1, đang xây dựng hàm băm h sao cho đối với bất kỳ phần tử nào X chức năng thiết lập ban đầu h(x) nhận một giá trị nguyên từ khoảng 0, ..., TRONG - 1, tương ứng với lớp mà phần tử thuộc về x. Yếu tố X thường gọi chìa khóa, h( x) - băm-giá trị x và "lớp học" phân đoạn . Cách giải quyết va chạm băm (hai phần tử của tập hợp có cùng giá trị h(x)) băm công khai và riêng tư được áp dụng.

mở bảng băm

Một mảng được gọi bảng phân khúc và lập chỉ mục số phân khúc 0, 1,...,B - 1 , chứa các tiêu đề cho TRONG các danh sách liên kết. Yếu tố Tôi danh sách thứ là một phần tử của tập hợp ban đầu mà h(.x:) =Tôi.

Đại diện cho một từ điển với bảng băm đóng

Bảng phân đoạn lưu trữ trực tiếp các phần tử từ điển. Do đó, chỉ có một phần tử từ điển có thể được lưu trữ trong mỗi phân đoạn. Với băm riêng, kỹ thuật này được sử dụng làm lại . Khi cố gắng đặt một phần tử x đến số phân khúc h ( x ) , đã bị chiếm bởi phần tử khác, chuỗi số phân đoạn được chọn h 1 ( x ) ,h 2 ( x ) , … , nơi phần tử có thể được đặt. Việc sử dụng từng phân đoạn này được kiểm tra tuần tự cho đến khi tìm thấy phân đoạn trống. Nó chứa một phần tử x . Để đặt số phân đoạn để băm lại, hãy áp dụng Các phương pháp khác nhau giải quyết va chạm. Ví dụ: phương pháp băm tuyến tính, phương pháp trung bình phương, phương pháp băm ngẫu nhiên

bài tập:

1. Giả sử rằng hàm băm h(i) = i % 7 được sử dụng để băm các số nguyên vào bảng băm 7 đoạn.

· Đưa ra bảng băm kết quả nếu các khối chính xác 1, 8, 27,64,125, 216,343 được chèn vào nó;

· Lặp lại điểm trước đó cho bảng băm kín với kỹ thuật giải quyết va chạm tuyến tính.

2. Giả sử chúng ta có một bảng băm kín với 5 phân đoạn, hàm băm h(i) = i % 5 và kỹ thuật giải quyết xung đột tuyến tính. Hiển thị kết quả của việc chèn vào bảng băm trống ban đầu của dãy số 23, 48, 35, 4, 10.

3. Triển khai Dictionary ADT cho chuỗi văn bản và các câu lệnh INSERT của nó , XÓA, THÀNH VIÊN và MAKENULL

từ điển được đặt bằng bảng băm mở,

từ điển được xác định bằng cách sử dụng bảng băm kín với kỹ thuật giải quyết va chạm tuyến tính,

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng Ánh xạ.

Trưng bày - là một tập hợp, trên các phần tử được xác định chức năng hiển thị các phần tử cùng loại ( tên miền ) thành các phần tử thuộc loại khác ( các dãy ) thuộc loại khác. Trưng bày m khớp với một phần tử đ domaintype từ phạm vi phần tử r loại phạm vi từ phạm vi: m(đ) = r.màn hình trống không chứa bất kỳ yếu tố nào

Các nhà khai thác của ATD "Display":

1. KIẾM TIỀN(m ). Làm cho màn hình hiển thị m trống.

2. GIAO PHÓ(m đ,r). Làm m(đ) bình đẳng r dù cho như thế nào m(đ) đã được xác định trước đó.

3. TÍNH TOÁN( M, d, r). Trả về true và đặt biến r thành giá trị m(đ), nếu cái sau được xác định và trả về false nếu không.

Chế độ xem hiển thị:ánh xạ có thể được thực hiện hiệu quả bằng cách sử dụng bảng băm. Đây x đặt giá trị từ vùng định nghĩa hiển thị và phần tử bảng có số h ( x ) – một phần tử từ phạm vi giá trị.

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng “Hàng đợi ưu tiên”

hàng đợi ưu tiên - đây là một tập hợp cho các phần tử mà chức năng ưu tiên (mức độ ưu tiên) được đặt, tức là cho từng phần tử x set, bạn có thể tính hàm r( x )- ưu tiên phần tử x , thường lấy giá trị từ tập hợp các số thực, hay tổng quát hơn, từ một số tập hợp có thứ tự tuyến tính.

ATD “Hàng đợi ưu tiên” dựa trên ADT “Set” với các toán tử CHÈN Và XÓA, cũng như với toán tử KIẾM TIỀNđể khởi tạo cấu trúc dữ liệu. Nhà điều hành CHÈN cho một hàng đợi ưu tiên được hiểu trong theo nghĩa thông thường, trong khi XÓA là một hàm trả về phần tử có mức ưu tiên thấp nhất và, như một tác dụng phụ, loại bỏ phần tử đó khỏi tập hợp.

Đại diện cho một hàng đợi với danh sách liên kết kép có thứ tự.


Đại diện cho một hàng đợi với cây liên kết được sắp xếp một phần:

Ý tưởng chính của việc triển khai này là tổ chức các phần tử của hàng đợi dưới dạng cây nhị phân. Ở cấp độ thấp hơn, nơi một số lá có thể bị thiếu, tất cả các lá bị thiếu chỉ có thể được đặt ở bên phải của các lá cấp thấp hơn. Quan trọng hơn, cây đặt hàng một phần . Điều này có nghĩa là độ ưu tiên của nút v không lớn hơn mức độ ưu tiên của bất kỳ nút con nào v, trong đó mức độ ưu tiên của nút là giá trị ưu tiên của phần tử được lưu trữ trong nút đã cho. Từ hình có thể thấy rằng các giá trị ưu tiên nhỏ không thể xuất hiện ở mức cao hơn, nơi có các giá trị ưu tiên lớn.

Hàm DELETEMIN trả về phần tử có mức ưu tiên thấp nhất, phần tử này phải là gốc của cây. Để không phá hủy cây và giữ nguyên thứ tự một phần của các giá trị ưu tiên trên cây sau khi loại bỏ gốc, các hành động sau được thực hiện: nút ngoài cùng bên phải được đặt ở mức thấp nhất và tạm thời được đặt ở gốc của cây. Sau đó, phần tử này đi xuống các nhánh của cây (tới các tầng thấp hơn), đổi chỗ cho các phần tử con có mức độ ưu tiên thấp hơn trên đường đi, cho đến khi phần tử này là một chiếc lá hoặc ở vị trí mà các phần tử con của nó ít nhất có mức độ ưu tiên không kém hơn.

Biểu diễn một hàng đợi bằng cách sử dụng một mảng chứa các nút của cây được sắp xếp một phần:

trong mảng MỘTĐầu tiên N vị trí tương ứng N các nút cây. Yếu tố MỘT chứa gốc của cây. Con trái của nút cây MỘT[ Tôi], nếu nó tồn tại, là trong ô MỘT, và con trai bên phải, nếu nó tồn tại, đang ở trong phòng giam MỘT. Ngược lại, nếu con trai ở trong ô MỘT[ Tôi], sau đó cha mẹ của nó trong tế bào MỘT[ Tôi%2] . Các nút cây lấp đầy các ô MỘT, MỘT, … MỘT[ N] tuần tự theo cấp độ, bắt đầu từ gốc và bên trong cấp độ - từ trái sang phải. Cây hiển thị ở trên sẽ được biểu diễn trong một mảng theo trình tự các nút sau: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

bài tập:

1. Vẽ cây có thứ tự một phần là kết quả của việc chèn các số nguyên 5, 6, 4, 9, 3, 1 và 7. Kết quả của việc áp dụng ba câu lệnh DELETEMIN cho cây này theo trình tự là gì?

2. Triển khai ADT hàng đợi ưu tiên cho bất kỳ loại dữ liệu nào và các câu lệnh INSERT, DELETEMIN và MAKENULL của nó

§ Cây có thứ tự một phần được thực hiện bằng cách sử dụng con trỏ,

§ Một cây có thứ tự một phần được thực hiện bằng cách sử dụng một mảng.

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng "Union of sets".

ADT là một tập hợp các đối tượng, mỗi đối tượng là một tập hợp. Các hoạt động chính được thực hiện trên một bộ sưu tập như vậy là kết hợp các bộ thành Thứ tự nhất định, cũng như trong việc kiểm tra xem một đối tượng nào đó có thuộc một tập xác định hay không. Những nhiệm vụ này được giải quyết với sự trợ giúp của các toán tử HỢP NHẤT(Hợp nhất) và TÌM THẤY(Tìm thấy). HỢP NHẤT( MỘT,V,C) tạo thành một tập hợp VỚI bằng hợp của các tập hợp MỘT Và TRONG, nếu các tập hợp này không giao nhau (nghĩa là không có các phần tử chung); toán tử này không được xác định nếu các bộ MỘT Và TRONG giao nhau. TÌM THẤY( x) trả về tập hợp mà phần tử thuộc về X; trong trường hợp khi X thuộc một số bộ hoặc không thuộc bộ nào, giá trị của hàm này không được xác định.

Toán tử của “Bộ kết hợp” ADT:

1. HỢP NHẤT(MỘT , TRONG) kết hợp các thành phần MỘT Và . TRONG, kết quả được gán cho A hoặc TRONG.

2. TÌM THẤY(x ) - một hàm trả về tên của thành phần mà nó thuộc về x.

3. BAN ĐẦU(MỘT , X ) tạo một thành phần có tên A chỉ chứa phần tử x.

Biểu diễn sự kết hợp của các tập hợp bằng cách sử dụng mảng:

Tên bộ giống với giá trị chỉ số mảng đặt tiêu đề ( tên 0 )

chỉ định:

đặt tiêu đề – mảng các tiêu đề đã đặt:

§ Với hết là số phần tử của tập hợp,

§ yếu tố đầu tiên - chỉ số mảngtênvới phần tử đầu tiên của tập hợp,

tên – mảng danh sách các phần tử tập hợp:

    đặt tên - tên của tập hợp mà phần tử thuộc về, phần tử tiếp theo - chỉ mục của phần tử tiếp theo trong danh sách tập hợp nhất định(giá trị chỉ số 0 được dùng làm cuối danh sách).

Chương trình làm việc mục 2.1.3

Kiểu dữ liệu trừu tượng “ Đồ thị có hướng”

Định nghĩa cơ bản:

đồ thị có hướng (chữ ghép lại ) g = (ĐÃ) gồm nhiều đỉnh V và nhiều cung e. Các đỉnh còn được gọi là nút thắt , và các cung các cạnh định hướng . Cung có thể được biểu diễn dưới dạng một cặp đỉnh có thứ tự ( bạn, w), đỉnh ở đâu Và gọi điện bắt đầu , Một w - kết thúc vòng cung.

Họ cũng nói rằng vòng cung Và -> w dẫn từ trên xuống dưới w, và hàng đầu w liền kề đứng đầu v.

Ví dụ 1 sơ đồ:

Các đỉnh của một sơ đồ ghép đôi có thể được sử dụng để biểu diễn các đối tượng và các cung có thể được sử dụng để biểu thị các mối quan hệ giữa các đối tượng.

đường trong một sơ đồ được gọi là một dãy các đỉnh v1 , v2 , … , vn , , mà có các cung v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Con đường này bắt đầu từ trên cùng v1 và đi qua các đỉnh v2 , v3 , ..., vn-1 kết thúc ở trên cùng vn. Chiều dài đường - số lượng cung tạo nên đường dẫn, trong trường hợp nàyđộ dài đường đi là P - 1 . Là một trường hợp đặc biệt của một đường dẫn, hãy xem xét một đỉnh v như một con đường có độ dài 0 từ đầu vĐẾN cùng một đỉnh v. Trong hình, dãy các đỉnh 1, 2, 4 tạo thành một đường đi có độ dài 2 từ đỉnh 1 đến đỉnh 4.

Con đường được gọi là đơn giản , nếu tất cả các đỉnh trên nó, có lẽ ngoại trừ đỉnh đầu tiên và đỉnh cuối cùng, là khác biệt. Xe đạp - là đường đi đơn có độ dài ít nhất bằng 1 bắt đầu và kết thúc tại cùng một đỉnh. Trong hình, các đỉnh 3, 2, 4, 3 tạo thành một chu trình có độ dài 3.

Trong nhiều ứng dụng, việc đính kèm một số thông tin vào các đỉnh và cung của một sơ đồ sẽ rất thuận tiện. Đối với những mục đích này, nó được sử dụng chữ ghép có nhãn , tức là, một sơ đồ mà mỗi cung và/hoặc mỗi đỉnh có một nhãn tương ứng. Nhãn có thể là tên, trọng lượng hoặc chi phí (của cung) hoặc giá trị dữ liệu của bất kỳ loại đã cho nào.

Ví dụ 2 có nhãn chữ ghép:

DIV_ADBLOCK149">

3. Thuật toán đóng chuyển tiếp (thuật toán Warshall):

cho số lượng g = (V, e) thuật toán tính toán ma trận chuyển tiếp t, mỗi phần tử trong đó t[Tôi, j] = 1 chỉ khi có một con đường từ đầu Tôi về đầu trang j Và t[ Tôi, j] = 0 nếu không thì.

4. Thuật toán tìm tâm của sơ đồ:

Cho phép Và -đỉnh tùy ý của sơ đồ g = (VÑe). Độ lệch tâm (loại bỏ tối đa) đỉnh Vàđịnh nghĩa là

max(độ dài đường đi nhỏ nhất từ ​​đỉnh w về đầu trang v }

w V

trung tâm chữ ghép gđược gọi là đỉnh có độ lệch tâm nhỏ nhất. Nói cách khác, tâm của sơ đồ là đỉnh mà khoảng cách lớn nhất (độ dài đường đi) đến các đỉnh khác là nhỏ nhất.

Ví dụ: Tâm của đồ thị là đỉnh đ

lập dị-t

5. Thuật toán bỏ qua một bản tóm tắt theo chiều sâu (tìm kiếm theo chiều sâu):

Khi giải nhiều bài toán liên quan đến đồ thị có hướng, cần phải phương pháp hiệu quả duyệt có hệ thống các đỉnh và các cung của đồ thị. Phương pháp này được gọi là tìm kiếm theo chiều sâu - một tổng quát của phương pháp duyệt cây trực tiếp. Tìm kiếm theo chiều sâu bắt đầu với việc chọn đỉnh ban đầu vđếm g,đỉnh này được dán nhãn đã đến thăm (đã viếng thăm). Sau đó, đối với mỗi đỉnh liền kề với đỉnh v và chưa được truy cập trước đó, tìm kiếm theo chiều sâu được áp dụng theo cách đệ quy. Khi tất cả các đỉnh có thể đạt được từ đỉnh v, sẽ được "thưởng" bằng một lượt truy cập, cuộc tìm kiếm kết thúc. Nếu một số đỉnh vẫn chưa được thăm, thì một trong số chúng sẽ được chọn và quá trình tìm kiếm được lặp lại. Quá trình này tiếp tục cho đến khi tất cả các đỉnh của sơ đồ được bao phủ bởi đường ngang. g.

6. Thuật toán xây dựng cây khung sâu của đồ thị:

Khi duyệt đồ thị bằng phương pháp tìm kiếm theo chiều sâu, chỉ một số cung nhất định dẫn đến các đỉnh chưa được thăm. Các cung như vậy dẫn đến các đỉnh mới được gọi là các cung cây và tạo thành biểu đồ tìm kiếm theo chiều sâu bao trùm khu rừng – rừng sâu . Khi dựng rừng người ta vẫn phân biệt 3 loại cung: cung ngược, cung thẳng và cung ngang. Vòng cung ngược - những vòng cung như vậy trong khu rừng bao trùm đi từ con cháu đến tổ tiên. cung thẳng được gọi là các cung đi từ tổ tiên đến con cháu thực sự, nhưng không phải là các cung cây.

Các cung nối các đỉnh không phải là tổ tiên cũng không phải là con cháu của nhau được gọi là cung ngang . Nếu khi xây dựng cây bao trùm, các con của một đỉnh được sắp xếp từ trái sang phải theo thứ tự được thăm và nếu các cây mới được thêm vào rừng cũng từ trái sang phải, thì tất cả các cung ngang đi từ phải sang trái .

Ví dụ, các cung D->C và G->D- ngang, vòng cung C-> MỘT- đảo ngược, không có vòng cung thẳng.

Khi duyệt sâu một cây, thường thuận tiện để đánh số các đỉnh theo thứ tự chúng được truy cập. Những con số như vậy được gọi là sâu.

Biểu diễn chữ ghép:

§ Biểu diễn sơ đồ bằng ma trận kề:

Ma trận kề cho chữ ghép G-đây là một ma trận MỘT kích cỡ N N với các giá trị boolean, trong đó MỘT[ Tôi, j] = ĐÚNG VẬY khi và chỉ khi có một cung từ đỉnh Tôi lên đầu j. Thông thường trong ma trận kề giá trị ĐÚNG VẬYđược thay thế bằng 1, và giá trị SAI- đến 0.

Việc tổng quát hóa biểu diễn của một sơ đồ ghép bằng ma trận kề có thể được coi là biểu diễn của một sơ đồ ghép có nhãn cũng sử dụng ma trận kề, nhưng phần tử MỘT[ Tôi, j] bằng nhãn cung tôi ->j. Nếu các cung từ trên xuống Tôi về đầu trang j không tồn tại thì giá trị của A[ Tôi, j] không thể là giá trị của bất kỳ nhãn hợp lệ nào nhưng có thể được coi là ô "trống".

Ma trận kề cho chữ ghép có nhãn (ví dụ 2):

§ Biểu diễn sơ đồ bằng danh sách kề:

Danh sách kề của một đỉnh Tôiđược gọi là danh sách tất cả các đỉnh kề với đỉnh Tôi, và được sắp xếp theo một cách nhất định. chữ ghép lại g có thể được biểu diễn bằng một mảng CÁI ĐẦU(Tiêu đề) có phần tử CÁI ĐẦU[Tôi] là một con trỏ tới danh sách kề của đỉnh Tôi.


Các nhà điều hành của ATD “Orgraf”:

Các toán tử phổ biến nhất được thực hiện trên đồ thị có hướng bao gồm đọc nhãn đỉnh và cung, chèn và xóa đỉnh và cung, và điều hướng qua các chuỗi cung.

Ba toán tử sau đây được yêu cầu để xem tập hợp các đỉnh liền kề.

1. ĐẦU TIÊN ( v) trả về chỉ số của đỉnh đầu tiên liền kề với đỉnh v. Nếu hàng đầu v không có đỉnh liền kề, thì đỉnh "null" được trả về không.

2. TIẾP THEO( v, Tôi) trả về chỉ số của đỉnh liền kề với đỉnh v, chỉ mục sau Tôi. Nếu như Tôi- là chỉ số của đỉnh cuối cùng liền kề với đỉnh v, sau đó trở về không.

3.VERTEX( v,Tôi) trả về đỉnh tại chỉ mục Tôi từ tập các đỉnh kề với v.

bài tập:

Cho một đồ thị có hướng (digraph):

https://pandia.ru/text/78/308/images/image043_12.gif" width="125" height="100 src=">


Một ví dụ về đồ thị bị ngắt kết nối:

xe đạp Đường đi (đơn giản) là đường đi (đơn giản) có độ dài ít nhất là 3 từ một số đỉnh đến chính nó. Số đếm được gọi là theo chu kỳ , nếu nó có ít nhất một chu kỳ. Đồ thị tuần hoàn liên thông, là một "cây không có gốc", được gọi là cây miễn phí . Hình thứ hai ở trên cho thấy một đồ thị bao gồm hai thành phần được kết nối, mỗi thành phần là một cây tự do. Một cây tự do có thể được tạo thành cây "thông thường" nếu một số đỉnh được chỉ định làm gốc và tất cả các cạnh được định hướng theo hướng ra khỏi gốc này.

Cây tự do có hai thuộc tính quan trọng:

1. Mọi cây tự do với số đỉnh N, N > 1 , có chính xác N - 1 xương sườn.

2. Nếu một cạnh mới được thêm vào một cây tự do thì sẽ thu được một chu trình.

Cho phép g = (V, E) -đồ thị liên thông trong đó mỗi cạnh ( r, w) được đánh dấu bằng một số Với(v, w),được gọi là chi phí cạnh . cây bao trùm đếm gđược gọi là cây tự do chứa tất cả các đỉnh VĐếm G Giá cây khung được tính bằng tổng chi phí của tất cả các cạnh có trong cây này

Các thuật toán cơ bản để xử lý đồ thị vô hướng:

1. Xây dựng cây bao trùm giá trị nhỏ nhất(Thuật toán của Prim):

Nhiều đỉnh cao đang được xây dựng bạn, từ đó cây bao trùm "mọc lên". Cho phép V= (1, 2, ...,N}. lúc đầu U = (1).Ở mỗi bước của thuật toán, cạnh của chi phí thấp nhất được tìm thấy ( bạn, v) như vậy mà bạn bạn Và v V/U, sau đó lên trên v chuyển từ tập hợp V \ U vào vô số bạn. Quá trình này tiếp tục cho đến khi tập hợp bạn sẽ không bằng tập hợp V.

Trình tự xây dựng một cây bao trùm được đưa ra dưới đây.

https://pandia.ru/text/78/308/images/image048_12.gif" width="501" height="384 src=">

3. Duyệt đồ thị vô hướng bằng cách tìm kiếm theo chiều sâu:

Tìm kiếm theo chiều sâu được sử dụng để duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống. Thuật toán tìm kiếm theo chiều sâu tương tự như thuật toán duyệt qua các đỉnh của một đồ thị ghép. Cái sau cũng được sử dụng cho các đồ thị vô hướng, vì một cạnh vô hướng (v, w) có thể được biểu diễn dưới dạng một cặp cung định hướng v -> w Và w -> v.

Di chuyển theo chiều sâu có thể được sử dụng để xây dựng một cây bao trùm.

Biểu đồ và cây bao trùm thu được bằng cách duyệt qua các đỉnh của nó bằng phương pháp tìm kiếm theo chiều sâu được hiển thị bên dưới:

4. Tra cứu đồ thị vô hướng bằng tìm kiếm theo chiều rộng

Một phương pháp khác để duyệt qua các đỉnh của đồ thị một cách có hệ thống được gọi là tìm kiếm theo chiều rộng . Nó có tên như vậy do thực tế là khi tiếp cận trong quá trình bỏ qua bất kỳ đỉnh nào v thì tất cả các đỉnh kề với đỉnh đó đều được coi là v, tức là các đỉnh được quét "theo chiều rộng". Phương pháp này cũng có thể áp dụng cho đồ thị có hướng.

Cũng giống như tìm kiếm theo chiều sâu, phương pháp tìm kiếm theo chiều rộng tạo ra một rừng bao trùm khi duyệt qua biểu đồ. Nếu sau khi lên đến đỉnh X khi xem xét một xương sườn (x, y)đỉnh Tại chưa được thăm trước đó, thì cạnh này được coi là một cạnh của cây. Nếu hàng đầu Tạiđã được truy cập trước đó, sau đó cạnh (x, y) sẽ là một cạnh ngang, vì nó kết nối các đỉnh không có quan hệ thừa kế với nhau.

Cây bao trùm thu được bằng cách tìm kiếm theo chiều rộng được hiển thị bên dưới.

Biểu diễn đồ thị vô hướng bằng ma trận kề:

Để biểu diễn đồ thị vô hướng, bạn có thể sử dụng các phương pháp tương tự như để biểu diễn đồ thị có hướng, nếu cạnh vô hướng giữa các đỉnh v Và wđược coi là hai cung định hướng từ đỉnh v đểđứng đầu w và từ đầu w về đầu trang v.

https://pandia.ru/text/78/308/images/image051_12.gif" width="159" height="106">

Biểu diễn đồ thị vô hướng bằng danh sách kề:

https://pandia.ru/text/78/308/images/image053_12.gif" width="339" height="115 src=">

1. Xây dựng:

cây bao trùm có chi phí nhỏ nhất theo thuật toán Prim;

cây bao trùm chi phí tối thiểu sử dụng thuật toán của Kruskal;

cây bao trùm bằng cách tìm kiếm theo chiều sâu, bắt đầu từ các nút a và d;

cây bao trùm bằng cách tìm kiếm theo chiều rộng, bắt đầu từ các đỉnh a và d.

2. Thực hiện thuật toán Prim và Kruskal.

3. Triển khai xây dựng cây bao trùm sử dụng tìm kiếm theo chiều sâu

§ đối với đồ thị vô hướng được biểu diễn bằng ma trận kề,

§ đối với đồ thị vô hướng được biểu diễn bằng danh sách kề.

4. Triển khai cây mở rộng tìm kiếm đầu tiên theo chiều rộng

§ đối với đồ thị vô hướng được biểu diễn bằng ma trận kề,

§ đối với đồ thị vô hướng được biểu diễn bằng danh sách kề.

Cập nhật lần cuối: 04.08.2018

Ngoài các lớp thông thường trong C#, còn có lớp trừu tượng. Một lớp trừu tượng tương tự như một lớp thông thường. Nó cũng có thể có các biến, phương thức, hàm tạo, thuộc tính. Điều duy nhất là khi định nghĩa các lớp trừu tượng, từ khóa trừu tượng được sử dụng:

Lớp trừu tượng Con người ( public int Độ dài ( get; set; ) public double Trọng lượng ( get; set; ) )

Nhưng sự khác biệt chính là chúng ta không thể sử dụng hàm tạo của một lớp trừu tượng để tạo đối tượng của nó. Ví dụ, như sau:

Con người h = con người mới();

Tại sao các lớp trừu tượng cần thiết? Giả sử rằng trong chương trình của chúng tôi dành cho lĩnh vực ngân hàng, chúng tôi có thể xác định hai thực thể chính: khách hàng ngân hàng và nhân viên ngân hàng. Mỗi thực thể này sẽ khác nhau, ví dụ, đối với nhân viên, bạn cần xác định vị trí của anh ta và đối với khách hàng - số tiền trên tài khoản. Theo đó, client và employee sẽ được tách biệt thành các class Client và Employee. Đồng thời, cả hai thực thể này có thể có điểm chung, chẳng hạn như họ và tên hoặc một số chức năng chung khác. Và tốt hơn là đặt chức năng chung này vào một số lớp riêng biệt, chẳng hạn như Người, mô tả một người. Tức là các lớp Employee (nhân viên) và Client (khách hàng ngân hàng) sẽ được dẫn xuất từ ​​lớp Person. Và vì tất cả các đối tượng trong hệ thống của chúng tôi sẽ đại diện cho nhân viên ngân hàng hoặc khách hàng, nên chúng tôi sẽ không tạo các đối tượng trực tiếp từ lớp Person. Vì vậy, nó có ý nghĩa để làm cho nó trừu tượng:

Lớp trừu tượng Person ( public string Name ( get; set; ) public Person(string name) ( Name = name; ) public void Display() ( Console.WriteLine(Name); ) class Client: Person ( public int Sum ( get ; set; ) // số tiền tài khoản public Client(string name, int sum): base(name) ( Sum = sum; ) ) class Nhân viên: Person ( public string Vị trí ( get; set; ) // vị trí public Employee( string tên, vị trí chuỗi): base(tên) ( Vị trí = vị trí; ) )

Sau đó chúng ta có thể sử dụng các lớp này:

Máy khách máy khách = Máy khách mới("Tom", 500); Nhân viên nhân viên = nhân viên mới("Bob", "Apple"); client.Display(); nhân viên.Display();

Hoặc thậm chí như thế này:

Khách hàng cá nhân = Khách hàng mới("Tom", 500); Person employee = new Employee("Bob", "Operator");

Nhưng chúng ta KHÔNG thể tạo một đối tượng Person bằng hàm tạo của lớp Person:

Người người = Người mới("Hóa đơn");

Tuy nhiên, mặc dù thực tế là chúng ta không thể gọi trực tiếp hàm tạo của lớp Person để tạo một đối tượng, tuy nhiên, hàm tạo trong các lớp trừu tượng có thể đóng vai trò tương tự vai trò quan trọng, đặc biệt, để khởi tạo một số biến và thuộc tính phổ biến cho các lớp dẫn xuất, như trong trường hợp của thuộc tính Tên. Mặc dù hàm tạo của lớp Person không được gọi trong ví dụ trên, nhưng các lớp dẫn xuất Client và Employee vẫn có thể truy cập nó.

Thành viên lớp trừu tượng

Ngoài các thuộc tính và phương thức thông thường lớp trừu tượng có thể có thành viên trừu tượng các lớp được định nghĩa với từ khóa trừu tượng và không có chức năng. Cụ thể, trừu tượng có thể là:

  • Của cải

    Người lập chỉ mục

Các thành viên lớp trừu tượng không được có công cụ sửa đổi riêng. Trong trường hợp này, lớp dẫn xuất phải ghi đè và triển khai tất cả các phương thức và thuộc tính trừu tượng có trong lớp trừu tượng cơ sở. Khi được ghi đè trong một lớp dẫn xuất, một phương thức hoặc thuộc tính như vậy cũng được khai báo bằng công cụ sửa đổi ghi đè (như với ghi đè thông thường của các phương thức và thuộc tính ảo). Cũng cần lưu ý rằng nếu một lớp có ít nhất một phương thức trừu tượng (hoặc thuộc tính trừu tượng, bộ chỉ mục, sự kiện), thì lớp này phải được định nghĩa là trừu tượng.

Các thành viên trừu tượng, giống như các thành viên ảo, là một phần của giao diện đa hình. Nhưng nếu trong trường hợp của các phương thức ảo, chúng ta nói rằng lớp kế thừa sẽ kế thừa việc triển khai, thì trong trường hợp của các phương thức trừu tượng, giao diện được đại diện bởi các phương thức trừu tượng này sẽ được kế thừa.

phương pháp trừu tượng

Ví dụ: hãy tạo phương thức Hiển thị trừu tượng trong ví dụ trên:

Lớp trừu tượng Person ( public string Name ( get; set; ) public Person(string name) ( Name = name; ) public abstract void Display(); ) class Client: Person ( public int Sum ( get; set; ) // sum trên tài khoản public Client(string name, int sum): base(name) ( Sum = sum; ) public override void Display() ( Console.WriteLine($"(Name) has a account on sum (Sum)"); ) ) lớp Nhân viên: Người ( chuỗi công khai Vị trí ( get; set; ) // vị trí công khai Nhân viên(tên chuỗi, vị trí chuỗi): cơ sở(tên) ( Vị trí = vị trí; ) ghi đè công khai void Display() ( Console.WriteLine($ " (Chức vụ) (Tên)"); ) )

Thuộc tính trừu tượng

Lưu ý việc sử dụng các thuộc tính trừu tượng. Định nghĩa của họ tương tự như định nghĩa của autoproperties. Ví dụ:

Lớp trừu tượng Người ( chuỗi trừu tượng công khai Tên ( get; set; ) ) lớp Khách hàng: Người ( tên chuỗi riêng; tên chuỗi ghi đè công khai ( get ( return "Mr/Ms." + name; ) set ( name = value; ) ) ) lớp Nhân viên: Người ( chuỗi ghi đè công khai Tên ( get; set; ) )

Lớp Person định nghĩa tên thuộc tính trừu tượng. Nó tương tự như một tài sản tự động, nhưng nó không phải là một tài sản tự động. Vì thuộc tính này không cần triển khai nên nó chỉ có các khối get và set trống. Trong các lớp dẫn xuất, chúng ta có thể ghi đè thuộc tính này bằng cách biến nó thành thuộc tính chính thức (như trong lớp Client) hoặc bằng cách đặt nó tự động (như trong lớp Employee).

Tránh triển khai các thành viên trừu tượng

Một lớp dẫn xuất phải cài đặt tất cả các thành viên trừu tượng của lớp cơ sở. Tuy nhiên, chúng ta có thể chọn không triển khai, trong trường hợp đó, lớp dẫn xuất cũng phải được định nghĩa là trừu tượng:

Lớp trừu tượng Người ( chuỗi trừu tượng công khai Tên ( get; set; ) ) Trình quản lý lớp trừu tượng: Người ( )

Ví dụ lớp trừu tượng

Một ví dụ trong sách giáo khoa là hệ thống các hình hình học. Trong thực tế, không có hình hình học như vậy. Có hình tròn, hình chữ nhật, hình vuông, nhưng đơn giản là không có hình. Tuy nhiên, cả hình tròn và hình chữ nhật đều có điểm chung là các hình:

// lớp hình trừu tượng lớp trừu tượng Hình ( // phương thức trừu tượng để lấy chu vi public trừu tượng float Perimeter(); // phương thức trừu tượng để lấy diện tích public trừu tượng float Area(); ) // lớp hình chữ nhật dẫn xuất class Hình chữ nhật: Hình ( public float Chiều rộng ( get; set; ) public float Chiều cao ( get; set; ) public Rectangle(float width, float height) ( this.Width = width; this.Height = height; ) // lấy chu vi ghi đè public ghi đè chu vi float () ( trả về Chiều rộng * 2 + Chiều cao * 2; ) // ghi đè vùng nhận công khai ghi đè Diện tích float () ( trả về Chiều rộng * Chiều cao; ) )

Sự phát triển của các mô hình trừu tượng cho dữ liệu và cách xử lý dữ liệu này là thành phần thiết yếu trong quá trình giải bài toán bằng máy tính. Chúng tôi thấy các ví dụ về điều này cả ở cấp độ thấp trong lập trình hàng ngày (ví dụ: khi sử dụng mảng và danh sách được liên kết, được thảo luận trong) và ở cấp độ cao khi giải quyết nhiệm vụ được áp dụng(như khi giải quyết vấn đề kết nối bằng cách sử dụng rừng tìm kiếm tham gia trong phần "Giới thiệu"). Bài giảng này thảo luận về các kiểu dữ liệu trừu tượng ( kiểu dữ liệu trừu tượng, sau đây gọi là ADT), cho phép bạn tạo các chương trình bằng cách sử dụng các trừu tượng cấp cao. Các kiểu dữ liệu trừu tượng cho phép bạn tách các phép biến đổi trừu tượng (khái niệm) mà các chương trình thực hiện trên dữ liệu khỏi bất kỳ biểu diễn cụ thể nào của cấu trúc dữ liệu và bất kỳ triển khai thuật toán cụ thể nào.

Tất cả các hệ thống máy tính đều dựa trên các mức độ trừu tượng: một số tính chất vật lý nhất định của silicon và các vật liệu khác cho phép áp dụng mô hình trừu tượng của bit, có thể nhận các giá trị nhị phân 0-1; sau đó, một mô hình trừu tượng của máy được xây dựng dựa trên các thuộc tính động của các giá trị của một tập hợp các bit nhất định; hơn nữa, dựa trên nguyên lý hoạt động của máy dưới sự điều khiển của chương trình trên ngôn ngữ máy một mô hình trừu tượng của ngôn ngữ lập trình được xây dựng; và cuối cùng là xây dựng khái niệm trừu tượng thuật toán được triển khai dưới dạng chương trình C++. Các kiểu dữ liệu trừu tượng làm cho quá trình này có thể tiến xa hơn và phát triển các cơ chế trừu tượng cho các tác vụ tính toán nhất định ở mức cao hơn so với hệ thống C++ cung cấp, phát triển các cơ chế trừu tượng dành riêng cho ứng dụng phù hợp để giải quyết các vấn đề trong nhiều lĩnh vực ứng dụng và tạo ra nhiều trừu tượng hơn cấp độ cao sử dụng các cấu trúc cơ bản này. Các kiểu dữ liệu trừu tượng cung cấp cho chúng ta một tập hợp có thể mở rộng vô hạn công cụđể giải quyết ngày càng nhiều vấn đề mới.

Một mặt, việc sử dụng các cấu trúc trừu tượng giải phóng người ta khỏi những lo lắng về việc thực hiện chi tiết của chúng; mặt khác, khi hiệu suất chương trình là quan trọng, bạn cần biết chi phí thực hiện các hoạt động cơ bản. Chúng tôi sử dụng rất nhiều trừu tượng cơ bản được tích hợp vào phần cứng máy tính và làm cơ sở cho các lệnh của máy; thực hiện trừu tượng hóa khác trong phần mềm; và sử dụng các bản tóm tắt bổ sung được cung cấp bởi phần mềm hệ thống đã viết trước đó. Các cấu trúc trừu tượng cấp cao thường dựa trên nhiều kiểu dáng đơn giản. Ở tất cả các cấp độ, nguyên tắc cơ bản giống nhau được áp dụng: bạn cần tìm các hoạt động quan trọng nhất trong các chương trình và đặc điểm quan trọng dữ liệu, và sau đó xác định chính xác cả ở cấp độ trừu tượng và phát triển các cơ chế cụ thể hiệu quả để thực hiện chúng. Trong bài giảng này, chúng ta sẽ xem xét nhiều ví dụ về việc áp dụng nguyên tắc này.

Việc phát triển một cấp độ trừu tượng mới sẽ yêu cầu (1) xác định các đối tượng trừu tượng sẽ được thao tác và các thao tác được thực hiện trên chúng; (2) đại diện cho dữ liệu trong một số cấu trúc dữ liệu và thực hiện các hoạt động; (3) và (quan trọng nhất) để đảm bảo rằng các đối tượng này được sử dụng thuận tiện để giải các bài toán ứng dụng. Những điểm này cũng áp dụng cho loại đơn giản dữ liệu, để các cơ chế cơ bản hỗ trợ các loại dữ liệu, đã được thảo luận trong "Cấu trúc dữ liệu cơ bản", có thể được điều chỉnh cho các mục đích của chúng tôi. Tuy nhiên, ngôn ngữ C++ cung cấp một phần mở rộng quan trọng của cơ chế cấu trúc được gọi là lớp. Các lớp cực kỳ hữu ích trong việc tạo ra các lớp trừu tượng và do đó được coi là công cụ chính được sử dụng cho mục đích này trong phần còn lại của cuốn sách.

Định nghĩa 4.1. Một kiểu dữ liệu trừu tượng (ATD) là một kiểu dữ liệu (một tập hợp các giá trị và một tập hợp các thao tác trên các giá trị đó) chỉ được truy cập thông qua một giao diện. Chương trình sử dụng ADT sẽ được gọi là máy khách và chương trình chứa thông số kỹ thuật của loại dữ liệu này sẽ được gọi là triển khai.

Đó là từ chỉ làm cho kiểu dữ liệu trở nên trừu tượng: trong trường hợp của một ADT, các chương trình máy khách không có quyền truy cập vào các giá trị dữ liệu theo bất kỳ cách nào khác ngoài các thao tác được mô tả trong giao diện. Việc biểu diễn dữ liệu này và các chức năng thực hiện các hoạt động này nằm trong quá trình triển khai và được phân tách hoàn toàn bởi một giao diện với máy khách. Chúng tôi nói rằng giao diện không rõ ràng: khách hàng không thể nhìn thấy việc triển khai thông qua giao diện.

Trong các chương trình C++, sự khác biệt này thường rõ ràng hơn một chút, vì dễ dàng nhất để tạo một giao diện bằng cách bao gồm Sự miêu tả dữ liệu, nhưng chỉ định rằng các chương trình máy khách không được phép truy cập trực tiếp vào dữ liệu. Nói cách khác, các nhà phát triển khách hàng có thể biết Sự miêu tả dữ liệu, nhưng không thể sử dụng nó theo bất kỳ cách nào.

Ví dụ, xem xét giao diện kiểu dữ liệu cho các điểm (Chương trình 3.3) từ Phần 3.1 "Cấu trúc dữ liệu cơ bản". Giao diện này tuyên bố rõ ràng rằng các điểm được biểu diễn dưới dạng cấu trúc bao gồm một cặp số dấu phẩy động, được biểu thị bằng x và y. Việc sử dụng các kiểu dữ liệu này là phổ biến trong hệ thống lớn phần mềm: chúng tôi phát triển một tập hợp các quy ước biểu diễn dữ liệu (cũng như xác định một tập hợp các thao tác liên quan) và cung cấp các quy tắc này thông qua một giao diện để các chương trình máy khách là một phần của phần mềm có thể sử dụng chúng. hệ thống lớn. Kiểu dữ liệu đảm bảo rằng tất cả các phần của hệ thống nhất quán với biểu diễn của các cấu trúc dữ liệu toàn hệ thống cơ bản. Dù chiến lược này tốt đến đâu, nó cũng có một nhược điểm: nếu cần thay đổi Sự miêu tả dữ liệu, bạn sẽ cần thay đổi tất cả các chương trình máy khách. Chương trình 3.3 một lần nữa cho chúng ta một ví dụ đơn giản: một trong những lý do để phát triển loại dữ liệu này là sự thuận tiện của các chương trình máy khách làm việc với các điểm và chúng tôi hy vọng rằng các máy khách sẽ có quyền truy cập vào các tọa độ riêng lẻ của một điểm nếu cần. Nhưng chúng tôi không thể thay đổi sang một biểu diễn dữ liệu khác (ví dụ: tọa độ cực hoặc tọa độ 3D hoặc thậm chí các loại dữ liệu khác cho các tọa độ riêng lẻ) mà không thay đổi tất cả các chương trình máy khách.

Ngược lại, Chương trình 4.1 chứa cách triển khai kiểu dữ liệu trừu tượng tương ứng với kiểu dữ liệu trong Chương trình 3.3, nhưng sử dụng lớp ngôn ngữ C++ để xác định cả dữ liệu và các hoạt động liên quan của nó cùng một lúc. Chương trình 4.2 là chương trình máy khách hoạt động với kiểu dữ liệu này. Hai chương trình này thực hiện các tính toán tương tự như chương trình 3.3 và 3.8. Chúng minh họa một số thuộc tính chính của các lớp mà bây giờ chúng ta sẽ xem xét.

Khi chúng ta viết một định nghĩa như int i trong một chương trình, chúng ta yêu cầu hệ thống dành một vùng bộ nhớ cho dữ liệu kiểu int (tích hợp sẵn), có thể được gọi là i. Ngôn ngữ C++ có thuật ngữ đối tượng cho các thực thể như vậy. Khi một định nghĩa chẳng hạn như POINT p được viết trong một chương trình, người ta nói rằng một đối tượng của lớp POINT được tạo ra, có thể được gọi bằng tên p. Trong ví dụ của chúng tôi, mỗi đối tượng chứa hai phần tử dữ liệu, được đặt tên là x và y. Cũng như các cấu trúc, chúng có thể được gọi bằng các tên như p.y.

Các thành viên dữ liệu x và y được gọi là các thành viên dữ liệu của lớp. Lớp cũng có thể định nghĩa các hàm thành viên thực hiện các hoạt động liên quan đến kiểu dữ liệu này. Ví dụ, lớp được định nghĩa trong Chương trình 4.1 có hai hàm thành viên có tên là POINT và distance .

Các chương trình máy khách, chẳng hạn như chương trình 4.2, có thể gọi các hàm thành viên được liên kết với một đối tượng bằng cách chỉ định tên của chúng giống như tên của dữ liệu chứa trong cấu trúc cấu trúc nào đó. Ví dụ: biểu thức p. distance(q) tính toán khoảng cách giữa các điểm p và q (khoảng cách tương tự sẽ được trả về bằng cách gọi q. distance(p) ). Hàm POINT(), hàm đầu tiên trong Chương trình 4.1, là một hàm thành viên đặc biệt được gọi là hàm tạo: nó có cùng tên với một lớp và được gọi khi một đối tượng của lớp đó cần được tạo.

Chương trình 4.1. Thực hiện lớp POINT (điểm)

Lớp này định nghĩa một kiểu dữ liệu bao gồm một tập hợp các giá trị là "các cặp số dấu phẩy động" (giả sử chúng được hiểu là các điểm trong mặt phẳng Descartes), cũng như hai hàm thành viên được xác định cho tất cả các phiên bản của POINT class: function POINT() , là hàm tạo khởi tạo tọa độ với các giá trị ngẫu nhiên từ 0 đến 1 và hàm distance(POINT) tính toán khoảng cách đến một điểm khác. Sự miêu tả dữ liệu là riêng tư và chỉ các chức năng thành viên mới có thể truy cập hoặc sửa đổi nó. Bản thân các chức năng thành viên là công khai ( public ) và có sẵn cho bất kỳ khách hàng nào. Mã có thể được lưu, ví dụ, trong một tệp có tên POINT .cxx.

#bao gồm lớp POINT ( private: float x, y; public: POINT() ( x = 1.0*rand()/RAND_MAX; y = 1.0*rand()/RAND_MAX; ) khoảng cách float(POINT a) ( float dx = x-a.x , dy = y-a.y; return sqrt(dx*dx + dy*dy); ) );

Chương trình 4.2. Chương trình client cho lớp POINT (tìm điểm gần nhất)

Phiên bản này của chương trình 3.8 là một máy khách sử dụng POINT ADT được xác định trong chương trình 4.3. Hoạt động mới tạo ra một mảng các đối tượng POINT (bằng cách gọi hàm tạo POINT() để khởi tạo từng đối tượng với các giá trị tọa độ ngẫu nhiên). Biểu thức a[i]. distance(a[j]) gọi hàm thành viên distance trên đối tượng a[i] với đối số a[j] .

#bao gồm #bao gồm #include "POINT.cxx" int main(int argc, char *argv) ( float d = atof(argv); int i, cnt = 0, N = atoi(argv); POINT *a = new POINT[N]; cho (i = 0; i< N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

Việc xác định POINT p trong chương trình máy khách dẫn đến việc phân bổ một vùng bộ nhớ cho một đối tượng mới và sau đó (sử dụng hàm POINT()) gán cho mỗi thành phần dữ liệu trong số hai thành phần dữ liệu của nó một giá trị ngẫu nhiên trong phạm vi từ 0 đến 1.

Phong cách lập trình này, đôi khi được gọi là lập trình hướng đối tượng, được hỗ trợ đầy đủ bởi cấu trúc lớp C++. Một lớp có thể được coi là một phần mở rộng của khái niệm cấu trúc, trong đó không chỉ dữ liệu được kết hợp mà các thao tác trên dữ liệu đó cũng được xác định. Có thể có nhiều đối tượng khác nhau thuộc cùng một lớp, nhưng chúng đều giống nhau ở chỗ các thành viên dữ liệu của chúng có thể nhận cùng một tập giá trị và cùng một tập hoạt động có thể được thực hiện trên các thành viên dữ liệu đó - nói chung, chúng là trường hợp của cùng một kiểu dữ liệu. Trong lập trình hướng đối tượng, các đối tượng được thiết kế để xử lý các thành viên dữ liệu của chúng (trái ngược với việc sử dụng các hàm độc lập để xử lý dữ liệu được lưu trữ trong các đối tượng).

Chúng ta đang xem ví dụ về một lớp nhỏ được mô tả ở trên chỉ để làm quen với các tính năng cơ bản của lớp; vì vậy nó còn lâu mới hoàn thành. Trong mã thực cho lớp điểm, chúng ta sẽ có nhiều thao tác hơn. Ví dụ, trong chương trình 4.1, thậm chí không có thao tác nào cho phép bạn tìm ra giá trị của tọa độ x và y. Như chúng ta sẽ thấy, việc thêm các hoạt động này và các hoạt động khác là một nhiệm vụ khá đơn giản. Trong Phần 5, chúng ta sẽ xem xét kỹ hơn các lớp cho điểm và các trừu tượng hình học khác như đường thẳng và đa giác.

Trong C++ (nhưng không phải trong C), các cấu trúc cũng có thể có các chức năng liên kết với chúng. Sự khác biệt chính giữa các lớp và cấu trúc liên quan đến quyền truy cập thông tin, được đặc trưng bởi các từ khóa.

Bài viết liên quan: