Chương 3: Ngăn xếp + Ứng dụng ngăn xếp - Cô Võ Thị Hường

NGĂN XẾP STACK 4 CẤU TRÚC NGĂN XẾP  Khái niệm, đặc điểm  Lưu trữ kế tiếp của ngăn xếp  Ngăn xếp móc nối  Ứng dụng của ngăn xếp 2/35 4.1 Khái niệm, đặc điểm ngăn xếp Khái niệm  Là một danh sách tuyến tính  Phép toán bổ sung một phần tử vào ngăn xếp hoặc lấy một D C phần tử ra khỏi ngăn xếp chỉ B thực hiện ở một đầu gọi là đỉnh A ngăn xếp Đỉnh Đáy Hình ảnh ngăn xếp 3/35 4.1 Khái niệm, đặc điểm ngăn xếp  Phần tử đưa vào ngăn xếp sau sẽ được lấy ra xử lí trước, phần tử đưa vào ngăn xếp trước sẽ được lấy ra xử lí sau.  Được gọi là danh sách LIFO (Last - In - First - Out) 4/35 4.2 Lưu trữ kế tiếp của ngăn xếp  Định nghĩa và khai báo cấu trúc dữ liệu  Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản 5/35 Định nghĩa và khai báo cấu trúc dữ liệu  Ngăn xếp mảng là một bản ghi gồm có hai trường  Trường 1 : là một số nguyên biểu diễn số phần tử có trong ngăn xếp  Trường 2 : Là mảng một chiều có kích thước đủ lớn để lưu các phần tử của ngăn xếp 6/35 Định nghĩa và khai báo cấu trúc dữ liệu  Khai báo cấu trúc : const max= <1 số thích hợp>; struct stack { int top ; ptu[max] ; }s; 7/35 Định nghĩa và khai báo cấu trúc dữ liệu max -1 Chưa có phần tử … 3 1 D C B 0 A 2 Ngăn xếp Mảng lưu trữ ngăn xếp s 8/35 Các phép toán cơ bản  Khởi tạo danh sách rỗng : creat(s)  Kiểm tra danh sách rỗng : empty(s)  Kiểm tra danh sách đầy : full(s)  Chèn phần tử x vào đỉnh của ngăn xếp : push(x,s)  Loại phần tử đỉnh của ngăn xếp gán cho x : pop(s,x) 9/35 Các phép toán cơ bản  Khởi tạo ngăn xếp rỗng max -1 void creat(stack &s) … { s.top = 0; 4 }  3 Kiểm tra ngăn xếp rỗng int empty(stack s) { 1 0 top = 0 return s.top == 0 ; } 2 Ngăn xếp rỗng 10/35 Các phép toán cơ bản max -1  Kiểm tra ngăn xếp đầy 3 int full(stack s) { 1 return s.top == max ; } 2 0 G F … D C B A top = max s Ngăn xếp đầy 11/35 Các phép toán cơ bản  Bổ sung phần tử x vào đỉnh ngăn xếp s max=7 6 6 5 5 4 top = 4 X 4 2 D C 1 B 0 A 3 6 s top =4 5 4 3 D 3 2 C B A 2 1 0 s top = 5 1 0 X D C B A s 12/35 Các phép toán cơ bản  Bổ sung phần tử x vào đỉnh ngăn xếp s void push( x, stack &s) { if (!full(s)) s.ptu[s.top++]=x; } 13/35 Các phép toán cơ bản  Loại phần tử ở đỉnh ngăn xếp s gán cho x max=7 6 6 5 5 x 4 2 D C 1 B 3 top = 4 0 A s D 4 x 3 2 top = 3 1 0 C B A s 14/35 Các phép toán cơ bản  Loại phần tử ở đỉnh ngăn xếp s gán cho x void pop(stack &s, &x) { if (s.top>0) x=s.ptu[--s.top]; } 15/35 4.3 Lưu trữ móc nối của ngăn xếp  Định nghĩa và khai báo cấu trúc dữ liệu  Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản 16/35 Định nghĩa và khai báo CTDL  Mỗi phần tử của ngăn xếp móc nối là một bản ghi gồm có 2 trường data   next data chứa thông tin của phần tử next là một con trỏ,trỏ vào nút đứng sau trong ngăn xếp 17/35 Định nghĩa và khai báo CTDL  Ngăn xếp được định nghĩa là một con trỏ trỏ vào phần tử đỉnh của ngăn xếp an … a2 a1 NULL s  Con trỏ next của phần tử đáy ngăn xếp nhận giá trị NULL báo hiệu kết thúc ngăn xếp 18/35 Định nghĩa và khai báo CTDL  Khai báo cấu trúc ngăn xếp móc nối : struct node { ptu; node *next; } *s ; 19/35 Các phép toán cơ bản  Khởi tạo ngăn xếp rỗng : creat(s)  Kiểm tra ngăn xếp rỗng : empty(s)  Chèn phần tử x vào đỉnh ngăn xếp : push(x,s)  Loại bỏ một phần tử khỏi danh sách : pop(s,x) 20/35 Các phép toán cơ bản Khởi tạo ngăn xếp rỗng void { creat(node *&s) s =NULL; } 21/35 Các phép toán cơ bản Kiểm tra ngăn xếp rỗng int empty(node *l) { return s==NULL ; } 22/35 Các phép toán cơ bản Bổ sung phần tử x vào đỉnh của ngăn xếp s … an x a2 a1 NULL s p 23/35 Các phép toán cơ bản Bổ sung phần tử x vào đỉnh của ngăn xếp s void push( x, node *&s) { node *p=new node; p->ptu = x; p->next = s; s = p; } 24/35 Các phép toán cơ bản Loại phần tử đỉnh của ngăn xếp gán cho x s … an a2 an NULL x = an 25/35 Các phép toán cơ bản Loại phần tử đỉnh của ngăn xếp gán cho x void pop(node *&s, x) { x=s->ptu ; node *p=s ; s = s->next ; delete p ; } 26/35 4.4 Ứng dụng của ngăn xếp  Định giá biểu thức số học  Chuyển đổi cơ số đếm  Giải các bài toán đệ quy  Soạn thảo văn bản 27/35 Định giá biểu thức số học  Sử dụng ngăn xếp chuyển biểu thức dạng trung tố có dấu ngoặc sang dạng hậu tố  Sử dụng ngăn xếp định giá biểu thức dạng hậu tố 28/35  Infix: Biểu thức trung tố là biểu thức đại số được sử dụng hằng ngày  Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các toán hạng.  Postfix: Ngược lại với cách Prefix, tức là các toán tử sẽ được đặt sau các toán hạng. 29/35 Định giá biểu thức số học Thuật toán 1 : Chuyển biểu thức dạng trung tố có dấu ngoặc sang dạng hậu tố  Sử dụng ngăn xếp rỗng có đáy là $  Sử dụng hàm pri với pri($)=pri(x) thì loại y ra khỏi stack và cho ra output  Nếu pri(y)