zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Công nghệ thông tin

Bài tiểu luận: Ứng dụng ngăn xếp (Stack) và hàng đợi (Queue) để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố

Chia sẻ: Hoàng Năng Hưng | Ngày: | Loại File: DOCX | Số trang:32

Báo xấu

438
lượt xem 56
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài tiểu luận "Ứng dụng ngăn xếp (Stack) và hàng đợi (Queue) để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố" giới thiệu đến các bạn những nội dung về ngăn xếp, hàng đợi, ứng dụng của Stack và Queue trong ký pháp Ba Lan. Mời các bạn cùng tham khảo, với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích cho các bạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tiểu luận: Ứng dụng ngăn xếp (Stack) và hàng đợi (Queue) để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố

Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Mục lục Phần I: Mở đầu I. Giới thiệu đề tài Trong khoa học máy tính, cấu trúc dữ liệu là cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình. Trong đó nổi trội lên là hai cấu trúc dữ liệu đó là Stack (ngăn xếp) và Queue (hàng đợi). Stack và Queue có ứng dụng rất nhiều kể cả trong thuật toán lẫn trong thực tế. Hàng ngày chúng ta thường xuyên làm việc và tiếp xúc với các biểu thức, toán hạng, toán tử… và máy tính cũng vậy. Tuy nhiên máy tính không thể nào hiểu được ngôn ngữ và cách viết của con người, vì vậy để máy tính hiểu được các biểu thức thì chúng ta phải chuyển chúng về một dạng mà máy tính có thể thực hiện được. Vì vậy em xin chọn đề tài “Ứng dụng ngăn xếp GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 1
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật (Stack) và hàng đợi (Queue) để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố” để làm bài tiểu luận. II. Mục đích yêu cầu của đề bài 1. Mục đích Đề tài này giúp em củng cố, nâng cao kiến thức về môn học cấu trúc dữ liệu và giải thuật. Từ đó hiểu sâu hơn và vận dụng vào trong các bài toán số liệu thực tế đồng thời thông qua việc làm đề tài này giúp em biết được các phương pháp nghiên cứu một vấn đề nhỏ nào đó. 2. Yêu cầu Dùng ngôn ngữ lập trình C/C++ để cài đặt chương trình. Với dữ liệu được nhập vào từ bàn phím. III. Phương pháp nghiên cứu + Tham khảo tài liệu: cấu trúc dữ liệu và giải thuật, trên mạng… + Tìm hiểu thực tiễn, thực tế, quy cách, nhu cầu của bài toán. + Xin ý kiến, hướng dẫn của giáo viên hướng dẫn. Phần II: Nội dung I. Ngăn xếp (Stack) Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack. Với nguyên tắc vào sau ra trước, danh sách kiểu LIFO (last in first out). Có 2 cách lưu trữ Stack: GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 2
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật + Bằng mảng. + Bằng danh sách liên kết. Các thao tác cơ bản trên Stack: Push: Đưa một phần tử vào đỉnh của Stack. Pop: Lấy từ đỉnh của Stack một phần tử. Peek: Xem đỉnh của Stack chứa nội dung là gì? Một số ứng dụng của Stack: Ứng dụng trực tiếp: Ứng dụng nổi bật của Stack là Stack cho chương trình sử dụng Stack để gọi hàm. Trong trình duyệt WEB, các trang đã xem được lưu trong stack. Trong trình soạn thảo văn bản, thao tác Undo được lưu trong stack. Ứng dụng gián tiếp: Cấu trúc dữ liệu bổ trợ cho thuật toán khác. Một thành phần của cấu trúc dữ liệu khác. II. Hàng đợi (Queue) Hàng đợi là kiểu danh sách tuyến tính mà phép bổ sung được thực hiện ở 1 đầu, gọi là lối sau (rear) và phép loại bỏ thực hiện ở 1 đầu khác gọi là lối trước (front). Nguyên tắc vào trước ra trước, danh sách kiểu FIFO (first in first out). Có 2 cách lưu trữ tương tự như Stack: + Bằng mảng. GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 3
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật + Bằng danh sách liên kết. Ứng dụng của Queue Ứng dụng trực tiếp Danh sách hàng đợi. Quản lý truy cập tới các tài nguyên dùng chung (ví dụ máy in). Multiprogramming. Ứng dụng gián tiếp Cấu trúc dữ liệu phụ trợ cho các thuật toán. Một phần của CTDL khác. III. Ứng dụng của Stack và Queue trong ký pháp Ba Lan 1. Khái niệm: 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. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn này, thay vì viết x + y như dạng trung tố, ta sẽ viết + x y. Tùy theo độ ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía sau phần giới thiệu này. Postfix: Ngược lại với cách Prefix, biểu thức hậu tố tức là các toán tử sẽ được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo Ba Lan” hoặc được viết tắt là RPN(Reverse Polish notation), được phát minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles Hamblin người Úc. GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 4
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Ví dụ: 2. Chuyển đổi dạng Infix(trung tố) sang Postfix(hậu tố) Thuật toán: Bước 1: Đọc một thành phần của biểu thức E (dạng Infix biểu diễn bằng xâu, đọc từ trái qua phải). Giả sử thành phần đọc được là x Bước 1.1: Nếu x là toán hạng thì viết nó vào bên phải biểu thức E1 (xâu lưu kết quả của Postfix) Bước 1.2: Nếu x là dấu ‘(’ thì đẩy nó vào Stack. Bước 1.3: Nếu x là một trong các phép toán +, , *, / thì Bước 1.3.1: Xét phần tử y ở đỉnh Stack. Bước 1.3.2: Nếu Pri(y) >= Pri(x) là một phép toán thì loại y ra khỏi Stack và viết y vào bên phải của E1 và quay lại bước 1.3.1 Bước 1.3.3: Nếu Pri(y)
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Bước 2: Lập lại bước 1 cho đến khi toàn bộ biểu thức E được đọc qua Bước 3: Loại phần tử ở đỉnh Stack và viết nó vào bên phải E1. Lặp lại bước này cho đến khi Stack rỗng. Bước 4: Tính giá trị của biểu thức dưới dạng hậu tố Ví dụ: Cho biểu thức: E = a * (b + c) – d / e 3. Tính giá trị biểu thức dạng Postfix(hậu tố) Thuật toán: Bước 1: Đọc lần lượt các phần tử của biểu thức E1 (từ trái qua phải). Nếu gặp toán hạng thì đẩy nó vào Stack. Nếu gặp phép toán thì lấy hai phần tử liên tiếp trong Stack thực hiện phép toán, kết quả được đẩy vào trong Stack. Bước 2: Lập lại bước 1 cho đến khi hết tất cả các phần tử trong biểu thức E1. lúc đó đỉnh của Stack chứa giá trị của biểu thức cần tính Bước 3: Kết thúc. GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 6
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Ví dụ: tính giá trị của biểu thức sau: 4 5 + 2 3 + * 6 + 8 7 + / Giả thuật được trình bày như sau: 4. Chuyển đổi dạng Infix(trung tố) sang Prefix(tiền tố) Thuật toán: Ý tưởn: Sử dụng Stack và Queue và Stackkq. Bước 1: Đọc một thành phần của biểu thức E (dạng Infix biểu diễn bằng xâu, đọc từ phải qua trái). Giả sử thành phần đọc được là x: Bước 1.1: Nếu x là toán hạng thì đưa nó vào Queue. Bước 1.2: Nếu x là dấu ‘)’ thì đẩy nó vào Stack. Bước 1.3: Nếu x là một trong các phép toán +, , *, / thì: Bước 1.3.1: Kiểm tra xem stack có rỗng không? Nếu rỗng, đẩy vào Stack, nếu không rỗng, sang bước 1.3.2. Bước 1.3.2: Lấy phần tử y ở đỉnh Stack. Bước 1.3.3: Nếu Pre(y)>=Pre(x), đưa tất cả các phần tử trong Queue vào Stackkq, đưa y vào Stackkq, đưa x vào Stack. Bước 1.3.4: Nếu Pre(y)
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Bước 1.4: Nếu x là dấu ‘(’ thì: Bước 1.4.1: Đưa tất cả các phần tử trong Queue vào Stackkq, Bước 1.4.2: Xét phần tử y ở đầu của Stack. Bước 1.4.3: y là phép toán thì loại y ra khỏi Stack, đưa y vào Stackkq, quay về bước 1.4.2. Bước 1.4.3: Nếu y là dấu ‘)’ loại y ra khỏi Stack. Bước 2: Lập lại bước 1 cho đến khi toàn bộ biểu thức E được duyệt. Bước 3: Đưa tất cả các phần tử trong Queue vào Stackkq, tất cả phần tử trong Stack và Stackkq. Bước 4: Lấy từng phần tử trong Stackkq ra, đó là kết quả dạng Prefix. Bước 5: Tính giá trị của biểu thức dưới dạng tiền tố. Ví dụ: Cho biểu thức sau hãy chuyển về dạng Prefix: E = a * b + c / d Giải thuật được trình bày như sau: 5. Tình giá trị biểu thức dạng Prefix(tiền tố) Thuật toán: Bước 1: Đọc lần lượt các phần tử của biểu thức E1 (từ phải qua trái) GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 8
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật Bước 1.1: Nếu gặp toán hạng thì đẩy nó vào Stack. Bước 1.2: Nếu gặp phép toán thì lấy hai phần tử liên tiếp trong Stack thực hiện phép toán, kết quả được đẩy vào trong Stack. Bước 2: Lập lại bước 1 cho đến khi hết tất cả các phần tử trong biểu thức E1. Lúc đó đỉnh của Stack chứa giá trị của biểu thức cần tính. Bước 3: Kết thúc. Ví dụ: tính giá trị của biểu thức sau: /+7 8 + 6 * + 3 2 + 5 4 Giả thuật được trình bày như sau: IV. Chương trình đầy đủ #include #include #include #include GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 9
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật #define OPERAND 0 #define OPERATOR 1 #define PARENT_OPEN 2 #define PARENT_CLOSE 3 #define ERROR 1000000 typedef struct _Item{ float value; int type; } Item; // stack typedef struct _STACKNODE{ Item item; struct _STACKNODE *next; } STACKNODE; typedef struct _STACK{ STACKNODE *top; int size; } STACK; void InitStack(STACK *stack){ GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 10
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật stack >top = NULL; stack >size = 0; } int IsStackEmpty(STACK *stack){ return (stack >size == 0); } void PushStack(STACK *stack, Item item){ if(stack >top == NULL){ stack >top = (STACKNODE *)malloc(sizeof(STACKNODE)); stack >top >item = item; stack >top >next = NULL; } else{ STACKNODE *t = (STACKNODE *)malloc(sizeof(STACKNODE)); t >item = item; t >next = stack >top; stack >top = t; } GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 11
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật stack >size++; } Item PopStack(STACK *stack){ if(stack >size > 0){ STACKNODE *t = stack >top; stack >top = stack >top >next; Item item = t >item; free(t); stack >size; return item; } } Item PeekStack(STACK *stack){ if(stack >size > 0) return stack >top >item; } // queue typedef struct _QUEUENODE{ Item item; struct _QUEUENODE *next; GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 12
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật struct _QUEUENODE *prev; } QUEUENODE; typedef struct _QUEUE{ _QUEUENODE *front, *rear; int size; } QUEUE; void InitQueue(QUEUE *queue){ queue >front = NULL; queue >rear = NULL; queue >size = 0; } int IsQueueEmpty(QUEUE *queue){ return (queue >size == 0); } void PushQueue(QUEUE *queue, Item item){ if(queue >front == NULL && queue >rear == NULL){ queue >front = (QUEUENODE *)malloc(sizeof(QUEUENODE)); queue >front >item = item; queue >front >next = NULL; GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 13
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật queue >front >prev = NULL; queue >rear = queue >front; } else{ QUEUENODE *t = (QUEUENODE *)malloc(sizeof(QUEUENODE)); t >item = item; t >next = queue >front; t >prev = NULL; queue >front >prev = t; queue >front = t; } queue>size++; } Item PopQueue(QUEUE *queue){ if(queue >size != 0){ QUEUENODE *t = queue>rear; if(queue >rear == queue>front){ queue >rear = NULL; queue >front = NULL; GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 14
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật } else{ queue >rear = queue >rear >prev; queue >rear >next = NULL; } queue >size; Item i = t >item; free(t); return i; } } Item PeekQueue(QUEUE *queue) { if(queue>size > 0) return queue>front>item; } int DocSo(char str[], int &i){ int len = strlen(str); int j = 0; char t[20]; GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 15
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật while(i = '0' && str[i]
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật PushQueue(queue, item); } else if(str[i] == '('){ item.value = str[i]; item.type = PARENT_OPEN; PushQueue(queue, item); } else if(str[i] == ')'){ item.value = str[i]; item.type = PARENT_CLOSE; PushQueue(queue, item); } else if(str[i] >= '0' && str[i]
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật } // do uu tien int priority(int optr){ if(optr == '(' || optr == ')') return 1; if(optr == '+' || optr == '') return 2; if(optr == '*' || optr == '/') return 3; return 0; } // chuyen tu bieu thuc trung to sang hau to void Convert(QUEUE *queue, QUEUE *output){ int size = queue >size; QUEUENODE *i; Item item; STACK stack; InitStack(&stack); for(i = queue >rear; i != NULL; i = i >prev){ item = i >item; GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 18
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật switch(item.type){ case OPERAND:{ PushQueue(output, item); } break; case OPERATOR:{ while(priority(item.value) 0){ Item iTemp = PopStack(&stack); PushQueue(output, iTemp); } PushStack(&stack, item); } break; case PARENT_OPEN:{ PushStack(&stack, item); } break; case PARENT_CLOSE:{ item = PopStack(&stack); GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 19
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật while(item.type != PARENT_OPEN){ PushQueue(output, item); item = PopStack(&stack); } } break; } } while(stack.size > 0) { item = PopStack(&stack); PushQueue(output, item); } } void Print(QUEUE *queue){ QUEUENODE *i; Item item; for(i = queue >rear; i != NULL; i = i >prev){ item = i >item; switch(item.type){ case OPERAND: GVHD: Trịnh Thị Phú Sinh vên thực hiện: Hoàng Năng Hưng 20

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA

165 tài liệu

2049 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.