Bài giảng Cấu trúc dữ liệu: Ngăn xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

21
lượt xem 3
download

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

Bài giảng Cấu trúc dữ liệu: Ngăn xếp cung cấp cho người học những kiến thức như: Sử dụng mảng; Sử dụng con trỏ; Ứng dụng của ngăn xếp. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Ngăn xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

TS. Lê Minh Trung ThS. Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin- Đại học Sư phạm TP. HCM
Ngăn Xếp (Stack)  Sử dụng mảng  Sử dụng con trỏ  Ứng dụng của ngăn xếp
Mô tả stack  Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack).  Là một cấu trúc vào sau ra trước – LIFO (Last In First Out)
Hoạt động của Stack  Stack rỗng:  Đẩy (push) Q vào: Q A Q  Đẩy A vào: A  Lấy (pop) ra một => được A: Q  Lấy ra một => được Q và stack rỗng: Q
Hoạt động của Stack
Thiết kế của Stack template //NodeType là kiểu dữ liệu tùy ý class Stack { public: Stack(void); //phương thức khởi tạo Stack(const Stack &source); //phương thức khởi tạo ~Stack(void); //phương thức hủy bool IsEmpty() const; void Push(const NodeType &item); //thêm phần tử vào đỉnh stack void Pop(); //gỡ phần tử ra khỏi đỉnh stack NodeType &Peek() const; //xem phần tử trên đỉnh stack void Clear(); //xóa dữ liệu của stack void operator=(const Stack &source); };
Cài đặt Stack sử dụng mảng http://www.cs.usfca.edu/~galles/visualization/StackArray.html
Thiết kế Stack dùng mảng const int MAX=20; //stack có tối đa MAX phần tử template class Stack { public: Stack(void); ~Stack(void); bool IsEmpty() const;//kiểm tra stack rỗng bool IsFull() const; //kiểm tra stack đầy void Push(const NodeType &item); NodeType &Peek() const; void Pop(); void Clear(); private: NodeType data[MAX]; //mảng chứa dữ liệu int top; //đỉnh của stack };
Các phương thức template template Stack::Stack(void) bool Stack::IsEmpty() const { { top =-1; return top==-1; //stack rỗng } } template template void Stack::Clear() bool Stack::IsFull() const { { top =-1; return top== MAX-1; //stack đầy } }
Các phương thức template void Stack::Push(const NodeType &item) { if(!IsFull()){ top++; data[top]= item; }else { throw exception("Stack is full"); } }
Các phương thức template void Stack::Push(const NodeType &item){ if(!IsFull()){ top++; data[top]= item; }else { throw exception("Stack is full"); } } template void Stack::Pop(){ if(!IsEmpty()){ top--; }else { throw exception("Stack is empty"); } }
Thử nghiệm #include "Stack.cpp" #include #include using namespace std; void main(){ Stack s; for(int i=1;i
Thử nghiệm #include "Stack.cpp" #include #include using namespace std; void main(){ Stack s; try{ for(int i=1;i
Cài đặt Stack sử dụng con trỏ http://www.cs.usfca.edu/~galles/visualization/StackLL.html
Thiết kế Node Node Cần: Dữ liệu Con trỏ để trỏ đến node sau Constructor
Thiết kế Node template struct Node { NodeType item; // dữ liệu của Node Node *next; // con trỏ tới Node kế tiếp Node(); //phương thức khởi tạo Node(NodeType item, Node *ptr=NULL); //phương thức khởi tạo };
Thiết kế Node #include "Node.h" template Node::Node(){} template Node::Node(NodeType item,Node *ptr=nullptr) { this->item= item; this->next = ptr; }
Ví dụ với Node liên kết Node first_node(‘a’); Node *p0 = &first_node; Node *p1 = new Node(‘b’); p0->next = p1; Node *p2 = new Node(‘c’, p0); p1->next = p2; p1 p2 first_node p0 a b c