YOMEDIA
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
670
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ó
AMBIENT/
Chủ đề:
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=”
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
