YOMEDIA
Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack
Chia sẻ: Nguyen Duc Anh
| Ngày:
| Loại File: PDF
| Số trang:10
228
lượt xem
43
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
Stack (ngăn xếp)
- Là một cấu trúc dữ liệu mà các
thao tác xử lý chỉ được thực hiện
ở phía đáy (cuối) của nó
AMBIENT/
Chủ đề:
Nội dung Text: Ngôn ngữ lập trình C - Chương 7 - Bài 2. Stack
- 4/28/2010
Chương 7.
Bài 2. Stack
ĐỖ BÁ LÂM
ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI
Nội dung
1. Khái niệm stack
2. Xây dựng stack
2.1. Sử dụng mảng
2.2. Sử dụng danh sách liên kết
2
1. Khái niệm stack
Stack (ngăn xếp)
Là một cấu trúc dữ liệu mà các
thao tác xử lý chỉ được thực hiện
ở phía đáy (cuối) của nó
Cấu trúc dạng LIFO (Last In First
Out) – “Vào sau ra trước”
Thao tác xử lý
• Đẩy vào PUSH
• Lấy ra POP
3
1
- 4/28/2010
1. Khái niệm stack
Đỉnh
Đáy
1. Khái niệm stack
Push(B) Pop() Pop()
Push(A)
A B
A
B
B
A
A A
Stack rỗng Stack có 1 phần tử: Stack có 2 phần tử: Stack còn 1 phần tử: Stack lại rỗng
A AB A
Ứng dụng của Stack
Lưu trữ các trang web đã từng được duyệt
trên Web browser
Cài đặt thao tác Undo trong các phần mềm
soạn thảo
Lưu danh sách các lời gọi hàm trong Java
Virtual Machine
2
- 4/28/2010
Ghi nhớ
Stack được hình dung như một ngăn xếp
chứa các quyển sách với 2 thao tác đưa
vào và lấy ra theo nguyên tắc:
Quyển sách nào được đưa vào sau sẽ lấy ra
trước – LIFO (Last In First Out)
Ví dụ - Bài toán chuyển cơ số
Nguyên tắc đổi một số nguyên từ thập
phân sang nhị phân:
Các số dư lấy ra sau được
hiển thị trước
Cơ chế sắp xếp của Stack
Giải pháp
Dùng stack để lưu trữ số dư qua từng
phép chia:
Khi thực hiện phép chia: Đưa số dư vào
Stack
Khi hiển thị kết quả: Lấy chúng lần lượt từ
Stack
3
- 4/28/2010
Giải pháp
1
1 1
PUSH
0 0 0
PUSH
0 0 0 0
1
1
0
0
1
1 1
POP
0 0 0
0 0 0 0
Giải thuật
1. Nhap N
2. while N != 0
R = N% 2; //Tính số dư trong phép chia N cho 2
PUSH (S, R); //Đẩy R vào đỉnh Stack S
N=N/2; //Thay N bằng N/2
3. while S chưa rỗng
POP(S,R); //Lấy phần tử từ stack đưa vào R
Hien_thi R;
2. Xây dựng Stack
Lưu trữ được các đối tượng dữ liệu (quyển
sách)
Xây dựng 2 thao tác Push và Pop theo
nguyên tắc LIFO
Có hai cách cài đặt stack
Sử dụng mảng
Sử dụng danh sách liên kết
4
- 4/28/2010
2.1. Sử dụng mảng
Đáy Stack
Mỗi phần tử của stack được lưu như một phần tử của
mảng
Đáy: phần tử có chỉ số 0
Đỉnh: phần tử được đưa vào cuối cùng, có chỉ số T
Khởi tạo T=-1
Stack rỗng (empty) T = -1, stack đầy T = MAX-1
13
2.1. Sử dụng mảng
#define MAX 100 //So phan tu lon nhat
cua Stack
//Khai bao Stack va T la 2 bien toan cuc
ElemType Stack[MAX];
int T=-1;
14
2.1. Sử dụng mảng
Stack được biểu diễn thông qua mảng S[MAX]
int push(ElemType N){
if (T==MAX-1) return 0;
else{ //mảng chưa đầy
T++;
S[T]=N;
}
return 1;
}
5
- 4/28/2010
2.1. Sử dụng mảng
int pop(ElemType *N){
if (T== -1)
return 0;
else{
*N = S[T--];
return 1;
}
}
2.2. Sử dụng danh sách liên kết
Head
Stack là cấu trúc LIFO (Last In First Out)
Thao tác Push, Pop?
17
2.2. Sử dụng danh sách liên kết
Push
Thêm một nút vào đầu danh sách
Pop
Lấy giá trị nút đầu tiên trong danh sách
Loại bỏ nút này khỏi danh sách
18
6
- 4/28/2010
2.2. Sử dụng danh sách liên kết
struct node {
ElemType data;
struct node *next;
};
//Khai báo con trỏ đầu là
biến toàn cục
struct node *top;
Push
Temp void push(ElemType N) {
top
struct node *temp;
45
temp=(struct node *)
7
malloc(sizeof(struct node));
temp->data = N;
1
temp->next = top;
top = temp;
8
\ }
Push
Temp void push(ElemType N) {
top
struct node *temp;
45
temp=(struct node *)
7
malloc(sizeof(struct node));
temp->data = N;
1
temp->next = top;
top = temp;
8
\ }
7
- 4/28/2010
Push
Temp void push(ElemType N) {
top
struct node *temp;
45
temp=(struct node *)
7
malloc(sizeof(struct node));
temp->data = N;
1
temp->next = top;
top = temp;
8
\ }
Pop
int pop(ElemType *N){
Temp
top
struct node *temp;
45
if(top==NULL)
return 0;
else{
7
*N = top->data;
temp = top;
top = top->next;
1
free(temp);
return 1;
}
8
}
\
Giá trị của thành phần top cần
lưu lại trước khi giải phóng vùng nhớ
Pop
int pop(ElemType *N){
Temp
top
struct node *temp;
45
if(top==NULL)
return 0;
else{
7
*N = top->data;
temp = top;
top = top->next;
1
free(temp);
return 1;
}
8
}
\
8
- 4/28/2010
Pop
int pop(ElemType *N){
Temp
top
struct node *temp;
if(top==NULL)
return 0;
else{
7
*N = top->data;
temp = top;
top = top->next;
1
free(temp);
return 1;
}
8
}
\
Bài toán
Demo dS_Array.c, dS_List.c
Bài tập 1.
Viết chương trình chuyển một số nguyên
dương từ hệ cơ số 10 sang hệ cơ số 2 sử
dụng stack (bằng mảng và danh sách liên kết)
Bài toán
Bài tập 2. Cộng hai số nguyên lớn
Kiểu dữ liệu số nguyên chỉ biểu diễn số trong
phạm vi nhất định
Mục đích: thực hiện thao tác cộng, trừ, nhân,
chia trên các số nằm ngoài phạm vi biểu diễn
27
9
- 4/28/2010
Bài toán
Thực hiện phép cộng trên hai số nguyên
“lớn”
Hai số được lưu dưới dạng xâu kí tự
28
Bài toán
Cải tiến
Trong cách xây dựng stack bằng mảng, thay
vì tách rời mảng và biến T chúng ta định
nghĩa một cấu trúc gồm 2 trường là mảng và
biến T này
Áp dụng làm lại các bài tập ở trên.
29
Thảo luận
30
10
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.98:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
