Bài giảng Cấu trúc dữ liệu: Chương 5 - Trịnh Xuân

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

46
lượt xem 3
download

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

Chương 4 cung cấp cho người học những kiến thức về ngăn xếp và hàng đợi. Nội dung chính trong chương 4 gồm: Trình bày khái niệm ngăn xếp (Stack) và hàng đợi (Queue), minh họa các ứng dụng, các phương pháp xây dựng Stack và Queue. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 5 - Trịnh Xuân

I. Stack – Ngăn xếp: CHƯƠNG V: STACK - QUEUE 8/4/16 2 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân 1. Giới thiệu: * Các thao tác cơ bản với Stack !  Ngăn xếp là một kiểu danh sách tuyến tính với hai !  initStack (Stack): Khởi tạo Stack rỗng phép toán bổ sung một phần tử vào cuối danh !  isEmpty (Stack): Kiểm tra Stack có rỗng sách và loại bỏ một phần tử cũng ở cuối của danh sách hay không? !  Trong ngăn xếp một phần tử vào sau sẽ bị đẩy ra !  isFull (Stack): kiểm tra danh sách đầy trước và phần tử vào trước sẽ bị đấy ra sau " !  Push (Stack, Item): Đẩy phần tử item vào gọi là danh sách LIFO (Last In First Out) 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 empty stack push an element push another pop tiên của Stack top B top top A A A top CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân 2. Cài đặt Stack a. Cài đặt Stack bằng mảng !  bằng mảng !  Khai báo Cấu trúc DL Stack #  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 #define max … #  Chỉ số đầu (0) để chỉ đáy Top struct Stack { !  bằng danh sách liên kết int top; #  Sử dụng một danh sách liên kết đơn Data nut[max]; #  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 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân
* Khởi tạo Stack rỗng: * Kiểm tra ngăn xếp rỗng int isEmpty ( Stack s) void InitStack ( Stack &s ) { { if ( s.top == -1 ) s.top = -1 return 1; } else return 0; } Top Top=-1 Top CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Kiểm tra danh sách đầy * Bổ sung một phần tử vào ngăn xếp int isFull( Stack s) void Push( Stack &s, Data x) { { if ( isFull(s) == 1) if (s.top == Max – 1) { printf( Stack day ); exit(1); } return 1; else else { s.top = s.top + 1; return 0; s.nut[ s.top ] = x; } } } Top Top=max-1 Top CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân *Lấy một phần tử (xóa) ra khỏi danh sách * Lấy nội dung của phần tử đầu tiên Data Pop( Stack &s) Data Top( Stack *s) { { if ( isEmpty(s) == 1 ) Data tg; { printf( Ngan xep rong ); exit(1); } if ( isEmpty(s) = = 1 ) else { printf( Ngan xep rong ); exit(1); } { else Data tg; tg = s.nut[s.top]; { s.top = s.top – 1; tg = s.nut[s.top]; return tg; } } return tg; } } Top Top CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân
b. Cài đặt Stack bằng Danh sách liên kết * Khai báo cấu trúc dữ liệu ! Ngăn xếp được cài đặt bằng danh sách !  Stacklà một danh sách liên kết đơn. Được liên kết có kích thước gần như vô hạn định nghĩa với cấu trúc: top 3 struct StackNode { Data info; 2 struct StackNode *next; }; struct Stack 1 { Node top; }; CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Khởi tạo Stack * Kiểm tra ngăn xếp rỗng int isEmpty( Stack s ) void InitStack( Stack &s) { { if (s.top == NULL) s.top = NULL; return 1; } else return 0; } CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Thêm phần tử vào danh sách: * Lấy phần tử khỏi danh sách: void Push ( Stack &s, Data x ) Data Pop ( Stack &s ) { { StackNode *p; StackNode *p; p = new StackNode; Data tg; If (p==NULL) {coutnext = s.top; else s.top = p; { } p = s.top; tg = p->info; s.top = s.top->next; delete p; } return tg; } CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân
* Lấy nội dung phần tử đầu tiên Stack: 3. Ứng dụng ngăn xếp Data Top (Stack *s) !  Đảo ngược xâu ký tự { !  Chuyển đổi cơ số Node *p; !  Tính giá trị của một biểu thức Data tg; if ( isEmpty(s) == 1 ) !  Chuyển biểu thức dạng trung tố sang hậu tố { printf( Stack rong ); exit(1); } !  Thuật toán sắp xếp QuickSort else { tg = s->top.info; } return tg; } CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân a. Bài toán đảo ngược xâu ký tự * Cài đặt … //định nghĩa các thao tác cơ bản của Stack chứa ký tự !  Bài toán: cho một chuỗi ký tự, yêu cầu đảo ngược chuỗi void main() ký tự đã có (ứng dụng Stack) { char *st; int i; !  Thuật toán stack *s; # Bước 1: Tạo ngăn xếp InitStack(s); ! Duyệt từ đầu xâu đến cuối xâu printf( Nhap chuoi ky tu: ); gets(st); ! Lần lượt cho các ký tự vào ngăn xếp – cho hết các for (int i=0; i
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() { … } 30 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân II. Queue – Hàng đợi 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) CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Các thao tác cơ bản với Queue 2. Biểu diễn Queue: !  InitQueue (Queue): Khởi tạo Queue rỗng !  Mảng #  Dùng hai chỉ số Rear và Front để lưu giữ điểm !  isEmpty (Queue): Kiểm tra Queue có rỗng đầu và điểm cuối hàng đợi hay không? !  Danh sách liên kết !  isFull (Queue): kiểm tra danh sách đầy #  Dùng DSLK đôi với điểm đầu Rear và điểm cuối Front !  Put (Queue, Item): Đẩy một phần tử vào ! Thêm vào Rear Queue ! Lấy ra từ Front !  Get (Queue): Hủy bỏ một phần tử khỏi Queue Front Rear CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 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: !  Khởi tạo struct NodeQueue { Rear Data info; void InitQueue(Queue &Q) struct NodeQueue *next; { struct NodeQueue *pre; }; Q.Rear = NULL; Q.Front = NULL; struct Queue } { NodeQueue *Rear, *Front; } Front Queue Q; CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân Kiểm tra hàng đợi rỗng * Thêm phần tử vào Queue: Int isEmpty( Queue q) Đưa thành phần x vào đầu Queue void Put( Queue &Q, Data x) { { p x NodeQueue *p; if (Q.Rear == NULL) p = new NodeQueue; return 1; if ( p == NULL ){ printf( Ko bo sung duoc ); exit(1); } p->info = x; p->next = NULL; p->pre = NULL; Rear else if ( Q.Rear = = NULL) { return 0; 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; } Font } 54 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Hủy bỏ phần tử khỏi danh sách: 3. Ứng dụng của hàng đợi Hủy bỏ phần tử tại vị trí Front của DS Data Get ( Queue &Q ) { Rear x 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; Front } CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân
Bài toán cộng 2 đa thức Kiểm tra chuỗi Palindromes %  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 !  Mỗi nút của danh sách $  Đọ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 5 4 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 HS SM Next CTDL – Khoa CNTH – Viện ĐH Mở HN Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân Biểu diễn đa thức 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 61 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân