Xây dựng stack bằng danh sách liên kết đơn

Chia sẻ: Khoa CNTT DTU D15TMT | Ngày: | Loại File: DOC | Số trang:5

Thêm vào BST

Báo xấu

668
lượt xem 79
download

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

Dùng kỷ thuật template để xây dựng một stack có thể lưu trữ bất kỳ. ở đây T là kiểu bất kỳ template class Stack{ private: struct Node{ T info; Node *next; }; Node *top; void makeEmpty( ); //Làm rỗng từ 1 stack đã có

Chủ đề:

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

Lưu

Nội dung Text: Xây dựng stack bằng danh sách liên kết đơn

Phần 1: Xây dựng stack bằng danh sách liên kết đơn Dùng kỷ thuật template để xây dựng một stack có thể lưu trữ bất kỳ. ở đây T là kiểu bất kỳ template class Stack{ private: struct Node{ T info; Node *next; }; Node *top; //Làm rỗng từ 1 stack đã có void makeEmpty( ); public: Stack( ); // C O N S T R U C T O R Stack( const Stack & ); // C O P Y C O N S T R U C T O R ~Stack( ); // DES T R U C T O R //Kiểm tra Stack rỗng? bool isEmpty( ) ; //Trả về phần tử ở đỉnh stack T & topOfStack( ); //Lấy ra khỏi stack phần tử ở đỉnh stack void pop( ); //Thêm 1 phần tử kiểu T vào stack void push( T ); Stack & operator=( Stack & ); // O V E R L O A D E D "=" O P E R A T O R }; 1. C O N S T R U C T O R Mục đích: tạo một ngăn xếp rỗng không có phần tử nào Sử dung: Stack S; Đầu vào: Không có Đầu ra: một ngăn xếp S rỗng dùng để chứa kiểu T Code:
template Stack::Stack(){ top = NULL; } 2. C O P Y C O N S T R U C T O R Mục đích: tạo một ngăn xếp giống như một ngăn xếp S1 đã có sẵn Sử dung: Stack S ( S1); Đầu vào: Ngăn xếp S1 đã tồn tại Đầu ra: một ngăn xếp S giống như ngăn xếp S1 nhưng dữ liệu ở 2 vị trí bộ nhớ khác nhau Code: template Stack::Stack(const Stack &s){ top = NULL; while(!s.isEmpty()){ this->push(s.topOfStack()); s.pop(); } } 3. DES T R U C T O R Mục đích: Hũy một ngăn xếp khi phạm vi sử dụng của nó hết Sử dung: chương trình tự gọi template Stack::~Stack(){ makeEmpty(); } 4. Kiểm tra Stack rỗng? Mục đích: Kiểm tra một stack S có rỗng không Sử dụng: S.isEmpty(); Đầu vào: một stack S bất kỳ
Đầu ra: trả về true nếu S không có phần tử nào, ngược lại là false Code: template bool Stack::isEmpty() { return top == NULL; } 5. Trả về giá trị phần tử ở đỉnh stack Mục đích: Trả về giá trị trên cùng của satck S Sử dụng: S.topOfStack(); Đầu vào: một stack S bất kỳ Đầu ra: trả về về giá trị ở đỉnh stack S nếu S không rỗng Code: template const T & Stack::topOfStack() { if(isEmpty()) {cout
pop(); } 7. Lấy ra khỏi stack phần tử ở đỉnh stack Mục đích: Loại 1 phần tử của stack S Sử dụng: S.pop(); Đầu vào: một stack S bất kỳ Đầu ra: stack S bớt đi phần tử ở đỉnh nếu stack không rỗng Code: template void Stack::pop(){ if(isEmpty()) {cout
Node *t = new Node; t->info = x; t->next = top; top = t; } 9. Operator= Mục đích: được dùng để gán stack S cho stack T Sử dụng: T = S; Đầu vào: một stack S bất kỳ Đầu ra: stack T giống như stak S nhưng ở vị trí khác trong bộ nhớ Code: template const Stack & Stack::operator =(const Stack &r){ if(*this != &r) { makeEmpty(); top = NULL; *this = r; } return *this; } Chú ý: Để sử dụng stack ST lưu trữ kiểu bất kỳ T thì khai báo theo cú pháp Stack ST; đối với những lớp có thuộc tính con trỏ muốn sử dụng template trên thì cần định nghĩa chồng tóan tử gán “operator=”