Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 2, Phần 2: Các cấu trúc dữ liệu cơ bản - Nguyễn Duy Hiệp
Chapter 2
Các cấu trúc dữ liệu cơ bản
Các cấu trúc dữ liệu cơ bản
Container : là các cấu trúc dữ liệu cho phép lưu trữ và lấy
dữ liệu độc lập với nội dung của dữ liệu.
Các container phân biệt theo thứ tự lấy mà chúng hỗ trợ.
Hai loại container quan trọng, thứ tự lấy của chúng phụ
thuộc vào thứ tự chèn:
Stack: hỗ trợ lấy theo thứ tự vào sau ra trước – Last In First Out
Queue: hỗ trợ lấy theo thứ tự vào trước ra trước – First In First
Out
2.5 Ngăn xếp - stack
2.5 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
Định nghĩa 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)
Top: đỉnh stack
Bottom: đáy stack
Định nghĩa 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
Push
Pop
top
Pop
7
7
top
top
7
5
3
2
top
5
5
3
2
5
5
3
2
3
2
3
2
Bottom
Ví dụ
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
Push
Pop
Push
Pop
Push
5
5
3
7
Pop
5
3
7
3
3
3
7
7
n=3
7
7
7
Nhập vào: 7, 3, 5
In ra: 5, 3, 7
Ví dụ
Thực hiện lần lượt các thao tác sau :
1. Push(3);
2. Push(5);
3. Pop();
4. Push(6);
5. Pop();
6. Pop();
Kết quả thu được ? Vẽ hình stack minh họa
Cài đặt stack
Cài đặt stack
Các phương thức cơ bản của stack
push() : thêm một phần tử mới vào stack
pop() : lấy một phần tử khởi stack
empty() : kiểm tra xem stack có rỗng hay không
top() : trả về giá trị phần tử ở đỉnh stack
Lưu trữ stack
Lưu trữ kế tiếp dùng mảng
Lưu trữ sử dụng danh sách móc nối
Lưu trữ bằng mảng
#include <stdio.h>
#define MAX 10 /* số lượng phần tử tối đa*/
#include <stdlib.h>
Kiểm tra stack rỗng:
int empty(int stack[], int count)
Kiểm tra danh sách được lưu bởi mảng stack.
Trả về giá trị 1 nếu stack rỗng(không có phần tử nào)
Ngược lại thì trả về 0
Hàm empty()
int empty(int stack[], int count)
{
if(count <0) return 1;
else return 0;
}
Hàm push()
Thêm một phần tử mới vào stack
int push(int stack[], int &count, int value)
Thêm một phần tử mới vào stack lưu bởi mảng stack[]
Nếu stack chưa đầy thì thêm value vào stack và tăng số lượng
phần tử trong stack thêm một, trả về giá trị 0 (thêm thành công)
Ngược lại thì trả về giá trị -1(thêm không thành công)
Hàm push()
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;
}
}
Hàm pop()
Lấy một phần tử khỏi stack
int pop(int stack[], int &count, int &value)
Lấy một phần tử ra khỏi stack lưu bởi mảng stack[]
Nếu stack khác rỗng thì lấy một phần tử ra khỏi stack, giá trị phần
tử đó chứa trong value, và giảm số lượng phần tử trong stack đi
một, trả về giá trị 0 (lấy thành công)
Ngược lại thì trả về giá trị -1(không thành công)
Hàm pop()
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;
}
}
Hàm top()
Trả về giá trị phần tử đang ở đầu stack
int top(int stack[], int count, int &value)
Lấy giá trị phần tử ở đầu stack lưu bởi mảng stack[]
Nếu stack khác rỗng thì lấy giá trị phần tử ở đầu stack gán
cho value, trả về giá trị 0 (lấy thành công)
Ngược lại thì trả về giá trị -1(không thành công)
Hàm top()
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
NULL
top
top
NULL
5
top
top
3
7
5
3
NULL
NULL
5
Thêm lần lượt 5, 3 ,7 vào stack rỗng
Tải về để xem bản đầy đủ
80 trang
19360
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 2, Phần 2: Các cấu trúc dữ liệu cơ bản - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
