Cơ sở dữ liệu - Chương V: Stack - Queue

8/4/16 2
CHƯƠNG V: STACK - QUEUE CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 I. Stack – Ngăn xếp: CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 1. Giới thiệu: !  Ngăn xếp là một kiểu danh sách tuyến tính với hai phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối của danh sách !  Trong ngăn xếp một phần tử vào sau sẽ bị đẩy ra trước và phần tử vào trước sẽ bị đấy ra sau " gọi là danh sách LIFO (Last In First Out) A top empty stack top top top push an element push another A B pop A CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Các thao tác cơ bản với Stack ! initStack (Stack): Khởi tạo Stack rỗng ! isEmpty (Stack): Kiểm tra Stack có rỗng hay không? ! isFull (Stack): kiểm tra danh sách đầy ! Push (Stack, Item): Đẩy phần tử item vào Stack ! Pop (Stack): Hủy bỏ một phần tử khỏi Stack ! Top (Stack): Xem nội dung của phần tử đầu tiên của Stack CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 2. Cài đặt Stack !  bằng mảng #  Sử dụng mảng một chiều để chứa các phần tử #  Cần chỉ số top để chỉ đỉnh ! Thêm – xóa trên vị trí Top #  Chỉ số đầu (0) để chỉ đáy !  bằng danh sách liên kết #  Sử dụng một danh sách liên kết đơn #  khai báo và định nghĩa phần tử đầu (Top) để chỉ đỉnh !  Thêm-xóa thực hiện tại vị trí Top #  Phần tử cuối là đáy danh sách 8/4/16 Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 a. Cài đặt Stack bằng mảng ! Khai báo Cấu trúc DL Stack #define max struct Stack { int top; Data nut[max]; }; CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Khởi tạo Stack rỗng: void InitStack ( Stack &s ) { s.top = -1 } Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Kiểm tra ngăn xếp rỗng int isEmpty ( Stack s) { if ( s.top == -1 ) return 1; else return 0; } Top=-1 Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Kiểm tra danh sách đầy int isFull( Stack s) { if (s.top == Max – 1) return 1; else return 0; } Top=max-1 Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Bổ sung một phần tử vào ngăn xếp void Push( Stack &s, Data x) { if ( isFull(s) == 1) { printf(
Stack day); exit(1); } else { s.top = s.top + 1; s.nut[ s.top ] = x; } } Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 *Lấy một phần tử (xóa) ra khỏi danh sách Data Pop( Stack &s) { if ( isEmpty(s) == 1 ) { printf(
Ngan xep rong); exit(1); } else { Data tg; tg = s.nut[s.top]; s.top = s.top – 1; return tg; } } Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Lấy nội dung của phần tử đầu tiên Data Top( Stack *s) { Data tg; if ( isEmpty(s) = = 1 ) { printf(
Ngan xep rong); exit(1); } else { tg = s.nut[s.top]; } return tg; } Top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 b. Cài đặt Stack bằng Danh sách liên kết ! Ngăn xếp được cài đặt bằng danh sách liên kết có kích thước gần như
vô hạn CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Khai báo cấu trúc dữ liệu ! Stack là một danh sách liên kết đơn. Được định nghĩa với cấu trúc: struct StackNode { Data info; struct StackNode *next; }; struct Stack { Node top; }; 3 1 2 top CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Khởi tạo Stack void InitStack( Stack &s) { s.top = NULL; } CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 int isEmpty( Stack s ) { if (s.top == NULL) return 1; else return 0; } * Kiểm tra ngăn xếp rỗng CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Thêm phần tử vào danh sách: void Push ( Stack &s, Data x ) { StackNode *p; p = new StackNode; If (p==NULL) {cout<<“Khong cap phat duoc”; exit(1); } p->info = x; p->next = s.top; s.top = p; } CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Lấy phần tử khỏi danh sách: Data Pop ( Stack &s ) { StackNode *p; Data tg; if (isEmpty(s) == 1) { printf(
Stack rong); exit(1); } else { p = s.top; tg = p->info; s.top = s.top->next; delete p; } return tg; } CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Lấy nội dung phần tử đầu tiên Stack: Data Top (Stack *s) { Node *p; Data tg; if ( isEmpty(s) == 1 ) { printf(
Stack rong); exit(1); } else { tg = s->top.info; } return tg; } CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 3. Ứng dụng ngăn xếp ! Đảo ngược xâu ký tự ! Chuyển đổi cơ số ! Tính giá trị của một biểu thức ! Chuyển biểu thức dạng trung tố sang hậu tố ! Thuật toán sắp xếp QuickSort CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 a. Bài toán đảo ngược xâu ký tự ! Bài toán: cho một chuỗi ký tự, yêu cầu đảo ngược chuỗi ký tự đã có (ứng dụng Stack) ! Thuật toán # Bước 1: Tạo ngăn xếp ! Duyệt từ đầu xâu đến cuối xâu ! Lần lượt cho các ký tự vào ngăn xếp – cho hết các ký tự vào ngăn xếp # Bước 2: Lấy từ ngăn xếp ra ! Lần lượt lấy các phần tử từ ngăn xếp và in ra CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Cài đặt //định nghĩa các thao tác cơ bản của Stack chứa ký tự void main() { char *st; int i; stack *s; InitStack(s); printf(
Nhap chuoi ky tu:); gets(st); for (int i=0; i<strlen(st); i++) Push( s, st[i]); printf(
\n Xau dao nguoc:); while (!isEmpty(s)) printf(
%c, Pop(s)); getch(); } CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 b. Bài toán chuyển đổi cơ số ! Tính # 5310 = ?2 # 7210 = ?4 ! Chuyển một số từ hệ thập phân sang hệ cơ số bất kỳ 7210 = 1.43 + 0.42 + 2.41 + 0.40= 10204 5310 = 1.25 + 1.24 + 0.23 + 1.22 + 0.21 + 1.20= = 1101012 CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân *Thuật toán ! Cho số nguyên n trong hệ thập phân và cơ số cần chuyển sang là b ! Bước 1: Khởi tạo Stack rỗng ! Bước 2: Tạo Stack #  Tính kết quả = n % b. Đẩy vào Stack. #  Thay n = n / b (để tìm các số tiếp theo). #  Quá trình lặp cho đến khi n = 0. ! Bước 3: Đọc từ Stack #  Lấy lần lượt các chữ số lưu trong Stack, chuyển sang dạng ký tự tương ứng với hệ cơ số trước khi in ra kết quả 8/4/16 28
CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân Cài đặt chuyển đổi cơ số //Cài đặt các thao tác của Stack - Khai báo CTDL - Đ/n hàm khởi tạo - Đ/n hàm kiểm tra rỗng - Đ/n hàm kiểm tra đầy - Đ/n hàm bổ sung phần tử - Đ/n hàm lấy và xóa phần tử //Cài đặt hàm main thực hiện thuật toán int main() { } 8/4/16 30
CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 II. Queue – Hàng đợi CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 1. Giới thiệu: $  Hàng đợi là một kiểu danh sách trong đó có phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử ở đầu danh sách. $  Trong hàng đợi một phần tử vào trước sẽ bị đẩy ra trước và phần tử vào sau sẽ bị đẩy ra sau " gọi là danh sách FIFO (First In First Out) 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 * Các thao tác cơ bản với Queue ! InitQueue (Queue): Khởi tạo Queue rỗng ! isEmpty (Queue): Kiểm tra Queue có rỗng hay không? ! isFull (Queue): kiểm tra danh sách đầy ! Put (Queue, Item): Đẩy một phần tử vào Queue ! Get (Queue): Hủy bỏ một phần tử khỏi Queue CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 2. Biểu diễn Queue: !  Mảng # Dùng hai chỉ số Rear và Front để lưu giữ điểm đầu và điểm cuối hàng đợi !  Danh sách liên kết # Dùng DSLK đôi với điểm đầu Rear và điểm cuối Front ! Thêm vào Rear ! Lấy ra từ Front 8/4/16 R ea r Fr on t CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân *Cài đặt Queue bằng Danh sách liên kết $ Khai báo cấu trúc: struct NodeQueue { Data info; struct NodeQueue *next; struct NodeQueue *pre; }; struct Queue { NodeQueue *Rear, *Front; } Queue Q; 8/4/16 Rear Front CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân !  Khởi tạo void InitQueue(Queue &Q) { Q.Rear = NULL; Q.Front = NULL; } 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân Kiểm tra hàng đợi rỗng Int isEmpty( Queue q) { if (Q.Rear == NULL) return 1; else return 0; } 8/4/16 54
CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 Đưa thành phần x vào đầu Queue void Put( Queue &Q, Data x) { NodeQueue *p; p = new NodeQueue; if ( p == NULL ){ printf(
Ko bo sung duoc); exit(1); } p->info = x; p->next = NULL; p->pre = NULL; if ( Q.Rear = = NULL) { Q.Font = p; Q.Rear = p; } else //Chèn thêm phần tử mới vào cuối danh sách { p->next = Q.Rear; Q.Rear->pre = p; Q.Rear = p; } } * Thêm phần tử vào Queue: Rear Font p x CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 Hủy bỏ phần tử tại vị trí Front của DS * Hủy bỏ phần tử khỏi danh sách: Data Get ( Queue &Q ) { Data x; QueueNode *p; if ( Q.Front = = NULL ) { printf(
\n Ko huy bo duoc); exit(1); } p = Q.Front; x = p->info; Q.Front = p->pre; Q.Front->next = NULL; free(p); return x; } Rear Front x CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 3. Ứng dụng của hàng đợi CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân %  Chuỗi Palindrome là chuỗi mà đọc xuôi giống đọc ngược %  Ví dụ: Able was I ere I saw Alba % Thuật toán $  Đọc lần lượt chuỗi trên vào Stack và Queue $  So sánh từng phần tử của Stack và Queue, nếu giống nhau từng cặp thì đó là chuỗi Palindrome, ngược lại thì chuỗi trên không phải là chuỗi Palindrome Kiểm tra chuỗi Palindromes CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 Bài toán cộng 2 đa thức !  Mỗi nút của danh sách 5 4 HS SM Next CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân 8/4/16 Biểu diễn đa thức CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân Kiểm Tra giữa kỳ ! Thực hiện lần lượt các yêu cầu sau: # Khai báo CTDL dạng DSLK đơn để quản lý một đối tượng nào đó trong BTL của mình # Định nghĩa các CTC thực hiện: ! Nhập danh sách đối tượng ! In danh sách đối tượng ! Đếm số các đối tượng trong ds theo điều kiện nào đó ! Sắp xếp DS các đối tượng theo thứ tự tăng dần của một điều kiện nào đó ! Cho biết thông tin của đối tượng có giá trị lớn nhất của một yêu cầu nào đó # Chương trình chính: Áp dụng các yêu cầu trên ! Ghi rõ Họ tên – lớp – số nhóm ! Ghi rõ đề bài cụ thể trước khi làm 8/4/16 61