Timtailieu.net 
Phân tích tư tưởng của nhân dân qua đoạn thơ: Những người vợ nhớ chồng… Những cuộc đời đã hóa sông núi ta trong Đất nước của Nguyễn Khoa Điềm
3407
1
0
9 trang
"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.
Nội dung trích xuất từ tài liệu:
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ị
...
