"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 10: Ứng dụng của ngăn xếp" với những kiến thức đảo mảng, đảo chuỗi, chuyển đổi hệ số, bracket matching, balancing ACT.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 10: Ứng dụng của ngăn xếp
- Cấu trúc dữ liệu và giải thuật
Bài 10: Ứng dụng của ngăn xếp
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- Bài 10. Một vài ứng dụng của Stack
Nội dung:
10.1. Đảo mảng (3)
10.2. Đảo chuỗi (4)
10.3. Chuyển đổi hệ số (9)
10.4. Bracket Matching (5)
10.5. Balancing Act (4)
Tham khảo:
1. Data structures and Algorithms Stacks.htm
2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues
3. Elliz Horowitz – Fundamentals of Data Structures, Chapter 3 Stacks and
Queues
4. Deshpande Kakle – C and Data Structures, Chapter 19. Stacks and
Queues
5. Bài giảng TS Nguyễn Nam Hồng
2 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.1. Đảo mảng (1/3)
Cho một mảng gồm một dãy các giá trị.
Để đảo thứ tự các phần tử trong mảng, sử dụng
nguyên lý Last-In-First-Out của Stack.
Ví dụ về hoạt động của đảo mảng:
17 18 134 216
23 25 47 55
25 23 55 47
18 17 216 134
3 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.1. Đảo mảng (2/3)
Ý tưởng thực hiện giải thuật:
1. Khởi tạo một Stack rỗng, có kiểu số.
2. Với n phần tử của mảng, lần lượt đưa vào Stack
thông qua hàm Push:
Push a[i] in to Stack.
3. Lần lượt lấy ra từ Stack n phần tử và đưa vào trở
lại mảng ban đầu:
Pop a item from nStack in to a[i].
4. Kết thúc giải thuật.
4 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.1. Đảo mảng (3/3)
Ví dụ về đảo mảng:
void revArray(int a[],int n,int stack[])
{
makeEmpty(stack);
for(int i=0;i
- 10.2. Đảo chuỗi (1/4)
Cho một chuỗi gồm nhiều từ.
Đảo chuỗi thực hiện việc đảo các từ trong chuỗi, sử
dụng ý tưởng Last-In-First-Out của Stack.
Ví dụ về đảo chuỗi:
Tôi Tập Chăm Giỏi
Làm Bài Học Thì
Bài Làm Thì Học
Tập Tôi Giỏi Chăm
6 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.2. Đảo chuỗi (2/4)
Ý tưởng xây dựng chương trình:
1. Tạo một wStack rỗng.
2. Với mỗi từ mWord đọc được từ string, đưa từ đó
vào Stack:
Push mWord into wStack.
3. Đọc từ wStack cho đến hết, thực hiện:
Pop a word from wStack into mWord.
Concate mWord to the end of outp string.
4. Dừng giải thuật.
Chú ý: cần xây dựng hàm tách word từ string.
7 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.2. Đảo chuỗi (3/4)
#include for(int i=1; i=0)
char* pop(char* stack[], int* top);
void main() { {
char* stack[MAXSIZE]; p=strcat(p," ");
int top=-1; p=strcat(p,pop(stack,&top));
char mString[MAX]; }
char* mWord; printf("Chuoi ket qua \n");
printf("Nhap vao mot chuoi: "); puts(p);
gets(mString);
getch();
mWord = strtok(mString," ");
}
push(stack,mWord,&top);
8 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.2. Đảo chuỗi (4/4)
void push(char* stack[], char* value, int* top) char* pop(char* stack[], int* top) {
{ char* value;
if(*top < MAXSIZE) if(*top>=0) {
{
*top=*top+1; value=(char*)malloc(strlen(stack[*top]));
stack[*top]=(char*)malloc(strlen(value)); strcpy(value,stack[*top]);
strcpy(stack[*top],value); *top=*top-1;
}
}
else
else
{
{ printf("STACK rong\n");
printf("Khong the them vao STACK\n");
value = NULL; }
getch();
} return value;
} }
void makeEmpty(int* top) {
*top=-1;
}
9 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (1/9)
Các hệ số hay sử dụng: hệ thập phân (Decimal), hệ
nhị phân (Binary), hệ 16 (Hexadecimal).
Con người thường sử dụng hệ thập phân.
Đối với máy tính, thường sử dụng hệ nhị phân.
Hệ 16 là hệ trung gian giữa hệ thập phân và hệ nhị
phân.
Ví dụ: 111 = (01101111)B = (6F)H
10 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (2/9)
Việc chuyển đổi giữa các hệ số thường xét:
1. Chuyển đổi từ hệ thập phân sang hệ nhị phân.
2. Chuyển đổi từ hệ nhị phân sang hệ thập phân.
3. Chuyển đổi từ hệ thập phân sang hệ 16.
4. Chuyển đổi từ hệ 16 sang hệ thập phân.
11 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (3/9)
Ý tưởng chuyển đổi từ hệ thập phân sang hệ nhị
phân sử dụng Stack:
Khởi tạo một Stack rỗng.
Chuyển đổi số từ dạng thập phân sang nhị phân bằng
phép div và mod cho 2.
Kết quả của phép mod được đưa vào Stack.
Đọc từ Stack cho đến hết, kết quả được nối với nhau để
tạo thành chuỗi.
Kết thúc giải thuật.
12 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (4/9)
Các hàm chính Dec to Binary: void push(char stack[], char value)
char* DecToBin(int a, char stack[]) { { if(stack[0] < MAXSIZE) {
makeEmpty(stack); stack[0]++;
int n=0;
stack[stack[0]]= value; }
while(a>0) {
else {
push(stack,a%2+'0');
printf("Khong the them vao STACK\n");
a=a/2;
getch(); } }
n++;
} char pop(char stack[])
char* mString; { char value;
mString = (char*) malloc(n); if(stack[0]>0) {
int i=0; value=stack[stack[0]];
while(stack[0]>0) stack[0]--; }
{ mString[i]=pop(stack); else {
i++; }
printf("STACK rong\n");
mString[i]='\0';
value = -1; }
return mString; }
return value;
}
13 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (3/9)
Ý tưởng chuyển đổi từ hệ thập phân sang hệ 16 sử
dụng Stack:
Khởi tạo một Stack rỗng.
Chuyển đổi số từ dạng thập phân sang nhị phân bằng
phép div và mod cho 16.
Kết quả của phép mod được đưa vào Stack.
Đọc từ Stack cho đến hết, kết quả được nối với nhau để
tạo thành chuỗi.
Kết thúc giải thuật.
14 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.3. Chuyển đổi hệ số (4/9)
Các hàm chính Dec to Hex: char* mString;
char* DecToHex(int a, char stack[]) mString = (char*) malloc(n);
{ int i=0;
makeEmpty(stack);
while(stack[0]>0)
int n=0;
{
while(a>0)
mString[i]=pop(stack);
{
i++;
int t = a%16;
if(t>=0 && t
- 10.4. Bracket Matching (1/6)
Một biểu thức sử dụng dấu ngoặc (Bracket) đúng
nếu:
• với mỗi dấu ngoặc trái sẽ có 1 dấu ngoặc phải gần nhất
khớp với nó.
• với mỗi dấu ngoặc phải sẽ có 1 dấu ngoặc trái gần nhất
(bên trái) khớp với nó.
• một đoạn biểu thức nằm giữa một cặp dấu ngoặc trái,
phải được gọi là sử dụng đúng dấu ngoặc.
16 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.4. Bracket Matching (2/6)
Ví dụ về sử dụng dấu ngoặc trong biểu thức toán
học:
s * (s – a) * (s – b) * (s – c) → Well
(– b + (b2 – 4*a*c)^0.5) / 2*a → Well
s * (s – a) * (s – b * (s – c) → ???
s * (s – a) * s – b) * (s – c) → ???
(– b + (b^2 – 4*a*c)^(0.5/ 2*a)) → ???
17 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.4. Bracket Matching (3/6)
Giải thuật kiểm tra sử dụng dấu ngoặc:
1. Tạo một bStack rỗng (Stack chứa dấu ngoặc).
2. Với mỗi ký hiệu sym trong đoạn (từ trái sang phải) :
2.1. Nếu sym là dấu ngoặc trái:
2.1.1. Đưa sym vào bStack.
2.2. Nếu sym là dấu ngoặc phải:
2.2.1. Nếu bStack rỗng, return false.
2.2.2. Lấy dấu ngoặc ở bStack, đưa vào biến left.
2.2.3. Nếu left và sym không khớp được với nhau,
return false.
3. Dừng giải thuật, trả về True nếu bStack rỗng, hoặc
False với các trường hợp khác.
18 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.4. Bracket Matching (4/6)
#include gets(a);
#include if(bracketMatching(a,bStack,&top))
#include printf("Bieu thuc su dung DUNG dau
#include "string.h" ngoac\n");
#define MAXSIZE 100 else
#define MAX 100 printf("Bieu thuc su dung KHONG
void push(char bStack[], char value, int *top); DUNG dau ngoac\n");
char pop(char bStack[], int *top); getch();
int isEmpty(char bStack[],int top); }
int isFull(char bStack[], int top);
void makeEmpty(int bStack[],int* top);
int bracketMatching(char* a,char bStack[], int *top);
void main()
{
char bStack[MAXSIZE];
char a[MAX];
int top=-1;
printf("Doc vao mot bieu thuc: ");
19 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 10.4. Bracket Matching (5/6)
int bracketMatching(char* a,char bStack[],int *top) void push(char bStack[], char value, int *top)
{ int kt=1; {
for(int i=0;i
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
