Kiểu dữ liệu trừu tượng – (ADT)

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

264
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'kiểu dữ liệu trừu tượng – (adt)', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kiểu dữ liệu trừu tượng – (ADT)

Kiểu dữ liệu trừu tượng – (ADT) Trình bày khái niệm tổng quát về kiểu dữ liệu Cài đặt các kiểu dữ liệu theo hướng cấu trúc Cài đặt các kiểu dữ liệu theo hướng đối tượng bằng C++ Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1 Nội dung trình bày Kiểu dữ liệu trừu tượng (ADT) So sánh một số cài đặt kiểu dữ liệu theo hướng cấu trúc và cài đặt kiểu dữ liệu theo hướng đối tượng bằng C++ Áp dụng Template và việc xây dựng các kiểu dữ liệu tổng quát Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 1
Kiểu dữ liệu trừu tượng (ADT) ADT - Abstract Data Type Kiểu dữ liệu trừu tượng: T = V (Values - miền giá trị): tập hợp các giá trị mà kiểu T có thể nhận O (Operators – các thao tác): tập hợp các thao tác cơ bản được định nghĩa trên V Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3 Kiểu dữ liệu trừu tượng (ADT) Ví dụ: T = int: V = {-32768 .. +32767} O = {+, -, *, div, mod, >, >=,
Kiểu dữ liệu trừu tượng (ADT) Cài đặt kiểu dữ liệu theo hướng cấu trúc (struct): Áp dụng khi chưa có công cụ lập trình hướng đối tượng Xây dựng các thao tác dưới dạng những thủ tục/hàm Các thao tác và dữ liệu (V, O) tách rời nhau Dữ liệu không được “bảo vệ”, vì ta có thể truy xuất đến ở bất cứ đâu trong phạm vi mà dữ liệu đã được định nghĩa … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5 Kiểu dữ liệu trừu tượng (ADT) Cài đặt kiểu dữ liệu theo hướng đối tượng: Dữ liệu và thao tác được tích hợp lại Dữ liệu được “ẩn” (hiding) và bảo vệ, tránh những truy xuất trực tiếp Chương trình chỉ truy xuất đến dữ liệu thông qua các thao tác đã được định nghĩa … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6 3
Kiểu dữ liệu trừu tượng (ADT) Bảo vệ Yêu cầu truy xuất dữ liệu Dữ liệu và Chương các thao tác trình Kết quả thực hiện Ưu điểm của cài đặt kiểu dữ liệu bằng hướng đối tượng Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7 Kiểu dữ liệu trừu tượng (ADT) Add Add Yêu cầu Remove Remove Program Program Data Data Kết quả Find Find Display Display Truy xuất “tự do” đến dữ liệu Dữ liệu được “bảo vệ” Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8 4
Kiểu dữ liệu trừu tượng (ADT) Cài đặt kiểu dữ liệu theo hướng đối tượng…: (tt) Có thể “che dấu” những thao tác xử lý cục bộ, giúp đơn giản hoá việc sử dụng bằng cách chỉ cung cấp cho người dùng những thao tác thực sự cần thiết Nâng cao tính “module hoá” của chương trình Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9 Kiểu dữ liệu trừu tượng (ADT) Che dấu các thao tác xử lý cục bộ Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10 5
So sánh một số cài đặt kiểu dữ liệu… Danh sách liên kết (Linked-list) Ngăn xếp (Stack) Cây nhị phân tìm kiếm (BST) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 11 So sánh một số cài đặt kiểu dữ liệu… Danh sách liên kết (Linked-list) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 12 6
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc typedef struct tagNODE { INFO data; tagNODE *pNext; } NODE; // Quản lý danh sách bằng con trỏ đầu và cuối typedef struct LINKED_LIST { NODE *pHead; NODE *pTail; unsigned int Count; // số nút trong danh sách } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 13 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc … (tt) // Xây dựng các thao tác cơ bản void CreateEmptyList(LINKED_LIST &list); int IsEmptyList(const LINKED_LIST &list); int CountNode(const LINKED_LIST &list); int InsertNode(LINKED_LIST &list, int index, INFO newdata); int DeleteNode(LINKED_LIST &list, NODE *pPrev, NODE *pCurr); void TraverseList(const LINKED_LIST &list); NODE *FindNode(const LINKED_LIST &list, key); Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 14 7
So sánh một số cài đặt kiểu dữ liệu… Create Traverse Gọi thao tác Insert Chương trình Dữ liệu của List sử dụng List Delete Kết quả Find Client Interface Server Cài đặt danh sách liên kết theo hướng đối tượng Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 15 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng class LINKED_LIST { private: struct NODE // 1 nút trong danh sách { INFO data; NODE *pNext; // trỏ đến nút kế tiếp }; unsigned int Count; // Số nút trong danh sách NODE *pHead; NODE *pTail; … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 16 8
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng…(tt) public: // constructors và destructor: LINKED_LIST(); LINKED_LIST(const LINKED_LIST &aList); ~List(); // các thao tác int IsEmpty() const; int Count() const; int Insert(int index, INFO newdata); int Delete(NODE *pPrev, NODE *pCurr); void Traverse(); NODE *Find( key); } // end class Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 17 So sánh một số cài đặt kiểu dữ liệu… Ngăn xếp (Stack) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 18 9
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc (dùng mảng) typedef struct STACK { int *StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack }; Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 19 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc (dùng danh sách liên kết) // Khai báo cấu trúc 1 phần tử trong Stack typedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext; } STACK_NODE; // Khai báo cấu trúc Stack typedef struct STACK { int StkCount; STACK_NODE *StkTop; } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 20 10
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc // - Định nghĩa các thao tác int InitStack(STACK &s, int MaxItems); int IsEmpty(const STACK &s); int IsFull(const STACK &s); int Push(STACK &s, int newitem); int Pop(STACK &s, int &outitem); int StackTop(const STACK &s, int &outitem); Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 21 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng (dùng mảng) class STACK { private: int *StkArray; int StkMax; int StkTop; int IsEmpty(); int IsFull(); … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 22 11
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng (dùng mảng)…(tt) public: // constructors và destructor STACK(int MaxItems = N); STACK(const STACK &aStack); ~STACK(); // các thao tác int Push(int newitem); int Pop(int &outitem); int Top(int &outitem); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 23 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng (dùng linked-list) class STACK { private: struct NODE // 1 nút trong stack { int data; NODE *pNext; // trỏ đến nút kế tiếp }; unsigned int Count; // Số nút trong stack NODE *pHead; public: // các thao tác tương tự như cách dùng mảng } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 24 12
So sánh một số cài đặt kiểu dữ liệu… Cây nhị phân tìm kiếm (BST) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 25 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc typedef struct tagBT_NODE { int Data; tagBT_NODE *pLeft; // con trỏ đến nút con trái tagBT_NODE *pRight; // con trỏ đến nút con phải } BT_NODE; // cấu trúc 1 nút typedef struct BIN_TREE { int Count; // Số nút trong cây BT_NODE *pRoot; // con trỏ đến nút gốc }; // cấu trúc cây nhị phân tìm kiếm Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26 13
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng cấu trúc…(tt) void BSTCreate(BIN_TREE &t); int BSTIsEmpty(const BIN_TREE &t); BT_NODE *BSTSearch(const BT_NODE *pCurr, int Key); int BSTInsert(BT_NODE *&pCurr, int Key); void _Delete(BT_NODE *&pCurr); BT_NODE *_SearchStandFor(BT_NODE *&p, BT_NODE *pCurr); int BSTDelete(BT_NODE *&pCurr, int Key); void BSTNLR(const BT_NODE *pCurr); Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27 So sánh một số cài đặt kiểu dữ liệu… Cài đặt BST bằng hướng đối tượng Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 28 14
So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng class BST { private: struct NODE // 1 nút trong cây { int Data; NODE *pLeft; // trỏ đến nút con trái NODE *pRight; // trỏ đến nút con phải }; unsigned int Count; // Số nút trong cây NODE *pRoot; void _Delete(NODE *&pCurr); NODE *_SearchStandFor(NODE *&p, NODE *pCurr); … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 29 So sánh một số cài đặt kiểu dữ liệu… // Cài đặt theo hướng đối tượng…(tt) public: BST(); ~BST(); int IsEmpty(); NODE *Search(const NODE *pCurr, int Key); int Insert(NODE *&pCurr, int Key); int Delete(NODE *&pCurr, int Key); void NLR(const NODE *pCurr); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 30 15
So sánh một số cài đặt kiểu dữ liệu… Nhận xét ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 31 Áp dụng Template và việc xây dựng các kiểu dữ liệu tổng quát Vấn đề: Ta muốn sử dụng cấu trúc Stack với các kiểu dữ liệu khác nhau: int, char, float,… Tất cả các thao tác căn bản không thay đổi Nếu xây dựng theo hướng cấu trúc… …Ta phải xây dựng nhiều kiểu Stack Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32 16
Áp dụng Template và việc xây dựng các kiểu dữ liệu tổng quát Áp dụng Template và class cho phép xây dựng các kiểu dữ liệu “tổng quát” VD. Linked-List/Stack/Queue/Tree với các phần tử có thể là kiểu int, char, string, struct XYZ,… Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 33 Áp dụng Template và việc xây dựng các kiểu dữ liệu tổng quát // Xây dựng template class STACK template class STACK { private: T *StkArray; int StkMax, StkTop; int IsEmpty(); int IsFull(); public: STACK(int MaxItems = N); ~STACK(); int Push(T newitem); int Pop(T &outitem); int Top(T &outitem); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 34 17
Áp dụng Template và việc xây dựng các kiểu dữ liệu tổng quát // Sử dụng STACK // với các kiểu dữ liệu khác nhau STACK intStack; STACK chrStack(1000); STACK fltStack(50); Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 35 Thanks for your attention 18