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

1. Cấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh
2. Nội dung Chương 1 – Thiết kế và phân tích [5 tiết] Chương 2 – Giải thuật đệ quy [10 tiết] Chương 3 – Mảng và danh sách [5 tiết] Chương 4 – Ngăn xếp và hàng đợi [10 tiết] Chương 5 – Cấu trúc cây [10 tiết] Chương 8 – Tìm kiếm [5 tiết] Chương 7 – Sắp xếp [10 tiết] Chương 6 – Đồ thị [5 tiết]
3. Chương 4 – Ngăn xếp và hàng đợi 1. Định nghĩa Stack 2. Lưu trữ kế tiếp với Stack [sử dụng mảng] 3. Ứng dụng của Stack 4. Định nghĩa Queue 5. Lưu trữ kế tiếp với Queue [sử dụng mảng] 6. Ứng dụng của Queue [not yet] 7. Lưu trữ móc nối với Stack 8. Lưu trữ móc nối với Queue [bài tập] 9. Stack và cài đặt đệ quy [not neccesary]
4. 1. Định nghĩa Stack Hai danh sách tuyến tính đặc biệt: Ngăn xếp – Stack Hàng đợi – Queue Stack: là danh sách mà xóa và thêm phần tử bắt buộc phải cùng được thực hiện tại một đầu duy nhất [đỉnh] Pop Push top Pop 7 7 7 top top 5 top 5 5 5 3 3 3 3 2 2 2 2
5. Ví dụ của Stack trong thực tế
6. Ví dụ của Stack trong thực tế • Stack là một cấu trúc LIFO: Last In First Out
7. Các thao tác cơ bản trên Stack Push Thêm một phần tử Tràn [overflow] Pop Xóa một phần tử Underflow Top Phần tử đỉnh stack rỗng Kiểm tra rỗng/đầy
8. Push Thêm phần tử mới vào đỉnh stack
9. Pop Rút một phần tử ra khỏi đỉnh stack
10. Top Kiểm tra phần tử đỉnh. Stack không thay đổi
11. Push/Pop Stack Stack rỗng thêm một phần tử Thêm một phần tử khác top B top A top A Lấy một phần tử ra khỏi Stack top A
12. Lưu trữ Stack 2 cách lưu trữ: Lưu trữ kế tiếp: sử dụng mảng Lưu trữ móc nối: sử dụng danh sách móc nối
13. Lưu trữ Stack bằng Mảng Stack được lưu trữ như một mảng Số các phần tử giới hạn Figure 4-20
14. Cấu trúc dữ liệu /* Stack của các số nguyên: intstack */ typedef struct intstack { int *stackAry;/* mảng lưu trữ các phần tử */ /* số ptử hiện có của stack */ int count; int stackMax; /* giới hạn Max của số ptử */ /* chỉ số của phần tử đỉnh */ int top; }IntStack;
15. Tràn và Cạn Cạn [underflow] xảy ra khi cố gắng rút phần tử từ stack rỗng Pop Tràn [overflow] xảy ra khi đẩy thêm phần tử vào stack đang đầy 18 6 … 11 3
16. Push int PushStack[IntStack *stack, int dataIn] { /* Kiểm tra tràn */ if [stack->count == stack->stackMax] return 0; /* Thêm phần tử vào stack */ [stack->count]++; [stack->top]++; /* Tăng đỉnh */ stack->stackAry[stack->top] =dataIn; return 1; } /* pushStack */
17. Pop int PopStack [IntStack *stack, int *dataOut] { /* Kiểm tra stack rỗng */ if [stack->count == 0] return 0; /* Lấy giá trị phần tử bị loại*/ *dataOut=stack->stackAry[stack->top]; [stack->count]--; [stack->top]--; /* Giảm đỉnh */ return 1; } /* popStack */
18. Top /* Lấy phần tử đỉnh của stack Trả lại 1 nếu thành công; 0 nếu stack rỗng dataOut chứa kết quả */ int TopStack [IntStack *stack, int* dataOut] { if [stack->count == 0] // Stack rỗng return 0; *dataOut = stack->stackAry[stack->top]; return 1; } /* stackTop */
19. Kiểm tra rỗng? /* Kiểm tra stack rỗng Trả lại 1 nếu là rỗng 0 nếu không rỗng */ int IsEmptyStack [IntStack *stack] { return [stack->count == 0]; } /* emptyStack */
20. Kiểm tra đầy? /* Kiểm tra stack đầy Trả lại 1 nếu là đầy 0 nếu không đầy */ int IsFullStack [IntStack *stack] { return[stack->count==stack->stackMax]; } /* fullStack */

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

• Định nghĩa
• Ứng dụng
• Cài đặt bằng mảng
• Cài đặt bằng danh sách móc nối
• Định giá biểu thức

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]

• Top: đỉnh stack
• Bottom: đáy stack

Hai thao tác cơ bản:

• Push: thao tác thêm một phần tử vào stack
• Pop: thao tác lấy một phần tử ra khỏi stack

Ví dụ: đọc vào một danh sách gồm n số nguyên [n data = value; ptr -> pNext = pTop; pTop = ptr; return 0; } else { printf["het bo nho !\n"]; return -1; } }

Ứng dụng của stack

• Định giá biểu thức: A = b + c * d / e –f
• Biểu thức trung tố : toán tử hai ngôi đứng giữa hai toán hạng, toán tử một ngôi đứng trước toán hạng.
• Biểu thức hậu tố : Toán tử đứng sau toán hạng
• Ví dụ:

• Xử lý gọi hàm trong C/C++
• Stack trong máy tính
  
  • Sử dụng để tính giá trị biểu thức
  • Xử lý ngắt
• Trong các chương trình biên dịch [compiler]
• Trong trình duyệt web, trình soạn thảo văn bản

Tính giá trị biểu thức hậu tố :

• Trung tố : [4.5 * 1.2] + 5.0 + [6.0 * 1.5]
• Hậu tố : 4.5 1.2 * 5.0 + 6.0 1.5 * +

Cách tính: Duyệt biểu thức hậu tố [chỉ gồm toán hạng 2 ngôi]

• Gặp toán hạng: đẩy vào stack
• Gặp toán tử 1 ngôi: lấy ra 1 toán hạng trong stack, áp dụng toán tử lên toán hạng và đẩy kết quả trở lại stack
• Gặp toán tử 2 ngôi: lấy 2 toán hạng ở đỉnh stack theo thứ tự, áp dụng toán tử lên 2 toán hạng đó, kết quả lại đẩy vào stack.
• Kết thúc, đưa ra kết quả là giá trị ở đỉnh stack.