Cài đặt Stack trên cơ số danh sách móc nối
|
Tóm tắt nội dung tài liệu
Page 2
YOMEDIA
Hai danh sách tuyến tính đặc biệt: ngăn xếp-stack; hàng đợi-quêu. Stack: la danh sách mà xóa và thêm phần tử bắt nuộc phải cùng được thực hiện tại một đầu quy nhất định... 30-09-2012 284 61 Download  Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.
2.5 Ngăn xếp ‐ stack
Stack: là cấu trúc hiệu quả để lưu trữ và lấy dữ liệu theo thứ tự vào sau, ra trước (LIFO)
Hai thao tác cơ bản:
Ví dụ: đọc vào một danh sách gồm n số nguyên (n<100), và in ra các số đã đọc theo thứ tự ngược Cài đặt stack Các phương thức cơ bản của stack
Lưu trữ stack
Kiểm tra stack rỗng: int empty(int stack[], int count) { if(count <0) return 1; else return 0; }
Thêm một phần tử mới vào stack
int push(int stack[], int & count, int value) { if (count < MAX - 1) { count = count + 1; stack[count] = value; return 0; } else { printf("stack da day!\n"); return -1; } } Lấy một phần tử khỏi stack
int pop(int stack[], int & count, int & value) { if (count >= 0) { value = stack[count]; count = count - 1; return 0; } else { printf("Stack rong, khong the lay duoc!\n"); return -1; } } Lấy giá trị phần tử đang ở đầu stack
int top(int stack[], int count, int & value) { if (empty(stack, count) == 1) return -1; else { value = stack[count]; return 0; } } Ví dụ int main() { int stack[MAX]; int count = ‐1; //stack rong int n, value; push(stack, count, 10); push(stack, count, 5); push(stack, count, 7); while (empty(stack, count) == 0) { pop(stack, count, value); printf(ʺ % d ʺ, value); } return 0; } Lưu trữ bằng danh sách móc nối
Thêm lần lượt 5, 3 ,7 vào stack rỗng Nhận xét:
Cấu trúc nút typedef struct node { int data; struct node * pNext; } NODE; Hàm empty() int empty(NODE * pTop) { if (pTop == NULL) return 1; else return 0; } Hàm push() int push(NODE * & pTop, int value) { NODE * ptr = (NODE * ) malloc(sizeof(NODE)); if (ptr != NULL) { ptr -> data = value; ptr -> pNext = pTop; pTop = ptr; return 0; } else { printf("het bo nho !\n"); return -1; } } Ứng dụng của stack
Tính giá trị biểu thức hậu tố :
Cách tính: Duyệt biểu thức hậu tố (chỉ gồm toán hạng 2 ngôi)
|
