›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Ngắn xếp và hàng đợi - Đỗ Tuấn Anh

pdf 77 trang hapham 3560
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Ngắn xếp và hàng đợi - Đỗ Tuấn Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_4_ngan_xep_v.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Ngắn xếp và hàng đợi - Đỗ Tuấn Anh

  1. Cấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh anhdt@it-hut.edu.vn
  2. Nội dung Chương 1 – Thiết kế và phân tích (5 tiết) Chương 2 – Giải thuật đệ quy (10 tiết) Chương 3 – Mảng và danh sách (5 tiết) Chương 4 – Ngăn xếp và hàng đợi (10 tiết) Chương 5 – Cấu trúc cây (10 tiết) Chương 8 – Tìm kiếm (5 tiết) Chương 7 – Sắp xếp (10 tiết) Chương 6 – Đồ thị (5 tiết)
  3. Chương 4 – Ngăn xếp và hàng đợi 1. Định nghĩa Stack 2. Lưu trữ kế tiếp với Stack (sử dụng mảng) 3. Ứng dụng của Stack 4. Định nghĩa Queue 5. Lưu trữ kế tiếp với Queue (sử dụng mảng) 6. Ứng dụng của Queue (not yet) 7. Lưu trữ móc nối với Stack 8. Lưu trữ móc nối với Queue (bài tập) 9. Stack và cài đặt đệ quy (not neccesary)
  4. 1. Định nghĩa Stack Hai danh sách tuyến tính đặcbiệt: Ngăn xếp – Stack Hàng đợi – Queue Stack: là danh sách mà xóa và thêm phần tử bắtbuộcphảicùngđượcthựchiệntại một đầu duy nhất(đỉnh) Push Pop top Pop 7 top 7 top 7 5 5 5 top 5 3 3 3 3 2 2 2 2
  5. Ví dụ của Stack trong thựctế
  6. Ví dụ của Stack trong thựctế • Stack là mộtcấu trúc LIFO: Last In First Out
  7. Các thao tác cơ bảntrênStack Push Thêm mộtphầntử Tràn (overflow) Pop Xóa mộtphầntử Underflow Top Phầntửđỉnh stack rỗng Kiểmtrarỗng/đầy
  8. Push Thêm phầntử mớivàođỉnh stack
  9. Pop Rút mộtphầntử ra khỏi đỉnh stack
  10. Top Kiểmtraphầntửđỉnh. Stack không thay đổi
  11. Push/Pop Stack Stack rỗng thêm mộtphầntử Thêm mộtphầntử khác top B top top A A Lấymộtphầntử ra khỏi Stack top A
  12. Lưu trữ Stack 2 cách lưu trữ: Lưu trữ kế tiếp: sử dụng mảng Lưu trữ móc nối: sử dụng danh sách móc nối
  13. Lưu trữ Stack bằng Mảng Stack đượclưutrữ như mộtmảng Số các phầntử giớihạn Figure 4-20
  14. Cấutrúcdữ liệu /* Stack củacácsố nguyên: intstack */ typedef struct intstack { int *stackAry;/* mảng lưu trữ các phầntử */ int count; /* số ptử hiện có của stack */ int stackMax; /* giớihạn Max của số ptử */ int top; /* chỉ số củaphầntử đỉnh */ }IntStack;
  15. Tràn và Cạn Cạn (underflow) xảy ra khi cố gắng rút phần tử từ stack rỗng Pop Tràn (overflow) xảy ra khi đẩy thêm phần tử vào stack đang đầy 18 6 11 3
  16. Push int PushStack(IntStack *stack, int dataIn) { /* Kiểm tra tràn */ if (stack->count == stack->stackMax) return 0; /* Thêm phần tử vào stack */ (stack->count)++; (stack->top)++; /* Tăng đỉnh */ stack->stackAry[stack->top] =dataIn; return 1; } /* pushStack */
  17. Pop int PopStack (IntStack *stack, int *dataOut) { /* Kiểm tra stack rỗng */ if (stack->count == 0) return 0; /* Lấy giá trị phần tử bị loại*/ *dataOut=stack->stackAry[stack->top]; (stack->count) ; (stack->top) ; /* Giảm đỉnh */ return 1; } /* popStack */
  18. Top /* Lấy phần tử đỉnh của stack Trả lại1 nếu thành công; 0nếu stack rỗng dataOut chứakếtquả */ int TopStack (IntStack *stack, int* dataOut) { if (stack->count == 0) // Stack rỗng return 0; *dataOut = stack->stackAry[stack->top]; return 1; } /* stackTop */
  19. Kiểmtrarỗng? /* Kiểm tra stack rỗng Trả lại1 nếulàrỗng 0 nếu không rỗng */ int IsEmptyStack (IntStack *stack) { return (stack->count == 0); } /* emptyStack */
  20. Kiểmtrađầy? /* Kiểm tra stack đầy Trả lại 1 nếu là đầy 0 nếu không đầy */ int IsFullStack (IntStack *stack) { return(stack->count==stack->stackMax); } /* fullStack */
  21. TạoStack IntStack *CreateStack (int max) { IntStack *stack; stack=(IntStack*)malloc(sizeof(IntStack)); if (stack == NULL) return NULL ; /* Khởi tạo stack rỗng */ stack->top = -1; stack->count = 0; stack->stackMax = max; stack->stackAry =malloc(max*sizeof(int)); return stack ; } /* createStack */
  22. 3. Ứng dụng của Stack Bài toán đổi cơ số: Chuyển một số từ hệ thập phân sang hệ cơ số bất kỳ 1 0 (base 8) 2810 = 3 • 8 + 4 • 8 = 34 8 3 2 1 0 (base 4) 7210 = 1 • 4 + 0 • 4 + 2 • 4 + 0 • 4 = 10204 5 4 3 2 1 0 (base 2) 5310 = 1 • 2 + 1 • 2 + 0 • 2 + 1 • 2 + 0 • 2 + 1 • 2 = 1101012
  23. 3. Ứng dụng Stack Đầu vào số thập phân n Đầu ra số hệ cơ số b tương đương 6 Ex. 7 7 4 4 4 67418 1 1 1 1 Stack rỗng n%8 = 1 n%8 = 4 n%8 = 7 n%8 = 6 n = 3553 n/8 = 444 n/8 = 55 n/8 = 6 n/8 = 0 n = 444 n = 55 n = 6 n = 0 1. Chữ số bên phải nhất của kết quả = n % b. Đẩy vào Stack. 2. Thay n = n / b (để tìm các số tiếp theo). 3. Lặp lại bước1-2 cho đến khi n = 0. 4. Rút 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ả
  24. Chuyển sang dạng ký tự tương ứng: char* digitChar = “0123456789ABCDEF”; char d = digitChar[13]; // 1310 = D16 char f = digitChar[15]; // 1310 = F16
  25. Đổi cơ số void DoiCoSo(int n, int b) { char* digitChar = "0123456789ABCDEF“; // Tạo một stack lưu trữ kết quả IntStack *stack = CreateStack(MAX); do { // Tính chữ số bên phải nhất,đẩy vào stack PushStack (stack, n % b); n /= b; // Thay n = n/b để tính tiếp } while (n != 0); // Lặp đến khi n = 0 while ( !IsEmptyStack(stack) ){ // Rút lần lượt từng phần tử của stack PopStack(stack, &n); // chuyển sang dạng ký tự và in kết quả printf(“%c”, digitChar[n]); } }
  26. 3. Ứng dụng của Stack (tiếp) Ký pháp trung tố: Với phép toán 2 ngôi: Mỗi toán tử được đặt giữa hai toán hạng Với phép toán một ngôi: Toán tử được đặt trước toán hạng -2 + 3 * 5 (-2) + (3 * 5) Việc đánh giá biểu thức trung tố khá phức tạp Sắp xếp giảm dần của thứ tự ưu tiên của toán tử: () > ^ > * = % = / > + = –
  27. Ký pháp hậu tố Toán hạng đặt trước toán tử. a b * c + Không cần dấu ngoặc a * b + c (Biểu thức trung tố tương đương) Ví dụ. Trung tố Hậu tố a*b*c*d*e*f ab*c*d*e*f* 1 + (-5) / (6 * (7+8)) 1 5 - 6 7 8 + * / + y (x/y – a*b) * ((b+x) – y ) x y / a b * – b x + y y ^ – * (x*y*z – x^2 / (y*2 – z^3) + 1/z) * (x – y) xy*z*x2^y2*z3^ – / – 1z/+xy – *
  28. Tính giá trị biểu thức hậu tố Biểu thức trung tố: (7 – 11) * 2 + 3 Biểu thức hậu tố: 7 11 – 2 * 3 + Sử dụng một stack lưu trữ toán hạng 2 bước1 7 11 – 2 * 3 + bước 4 * 3 + -4 11 –2 * 3 + bước 2 bước 5 -8 3 + 7 3 + 2 * 3 + bước 6 bước 3 -4 -8 bước 7 -5 Kết quả
  29. postfixEval Tính giá trị của biểu thức hậu tố Tính giá trị của một một biểu thức hậu tố được lưu trong một xâu ký tự và trả về giá trị kết quả. Toán hạng: Các số nguyên không âm một chữ số (cho đơn giản ☺) Toán tử: +, -, *, /, %, ^ (lũy thừa)
  30. Định nghĩa một số hàm int compute(int left, int right, char op); /* Thực hiện tính: “left op right”*/ bool isOperator(char op); /* Kiểm tra op có phải là toán tử không? op phải là một trong số '+','-','*','/','%','^‘ */
  31. Hàm isOperator() Hàm isOperator() kiểm tra ký tự có phải là toán tử? bool isOperator(char op) { return op == '+' || op == '-' || op == '*' || op == '%' || op == '/' || op == '^'; }
  32. int compute(int left, int right, char op) { int value; // Tính "left op right" switch(op){ case '+': value = left + right; break; case '-': value = left - right; break; case '*': value = left * right; break; case '%': value = left % right; break; case '/': value = left / right; break; case '^': value = pow(left, right); break; } return value; }
  33. Hàm postfixEval() int postfixEval(string expression) { // expValue lưu kết quả của biểu thức int left, right, expValue; char ch; // Tạo một stack lưu trữ toán hạng IntStack* stack = CreateStack(MAX); // Duyệt từng ký tự cho đến khi hết xâu for (int i=0; i < expression.length(); i++) { // đọc một ký tự ch = expression[i]; // nếu ch là toán hạng if (isdigit(ch)) // đẩy toán hạng vào stack PushStack(stack, ch - '0');
  34. // nếu ch là toán tử else if (isOperator(ch)){ // rút stack 2 lần để lấy 2 // toán hạng left và right PopStack(stack, &right); PopStack(stack, &left); // Tính "left op right" result = compute(left, right, ch); // Đẩy result vào stack PushStack(stack, temp); }else //không phải toán hạng hoặc toán t printf(“Bieu thuc loi”); } // Kết thúc tính toán, giá trị biểu thức // nằm trên đỉnh stack, đưa vào expValue PopStack(stack, expValue); return expValue; }
  35. Chuyển đổi trung tố→hậu tố Trong khi quét biểu thức số học: Toán hạng sẽ được ghi ngay vào xâu kết quả Không cần sử dụng stack cho toán hạng. stack toán tử Khi gặp toán tử hoặc dấu ngoặc, đẩy vào stack. Quản lý thứ tự ưu tiên giữa các toán tử Xử lý các biểu thức con.
  36. Hạng Chỉ xét các toán tử hai ngôi. Hạng. 1nếu là toán hạng -1 nếu là +, -, *, /, %, ^ 0 nếu là (, )
  37. Ví dụ 1 stack dùng để lưu trữ một cách tạm thời các toán tử trong khi chờ toán hạng 2 (phải) tương ứng. a + b * c * có mức ưu tiên cao hơn+ ⇒ Thêm vào stack Stack toán tử: * + Xâu hậu tố: a b c * +
  38. Ví dụ 2 Sử dụng stack để xử lý các toán tử có cùng thứ tự ưu tiên hoặc thấp hơn. a * b / c + d * có cùng mức ưu tiên với/ ⇒ rút * và ghi nó vào xâu hậu tố trước khi thêm / vào stack. / có mức ưu tiên cao hơn+ Stack toán tử: +*/ Xâu hậu tố: a b * c / d +
  39. Ví dụ 3 Sử dụng giá trị mức ưu tiên để xử lý ^ (tính lũy thừa). Mức ưu tiên đầu vào: 4 khi ^ là đầu vào. Mức ưu tiên tại stack: 3 khi ^ nằm trong stack. a ^ b ^ c ^ thứ 2 có mức ưu tiên là 4 nhưng ^ thứ 1 có mức ưu tiên là 3 Stack toán tử: ⇒ ^ thứ 2 được đẩy tiếp vào stack ^ (do đónósẽ được rút ra trước ^ thứ 1) ^ Xâu hậu tố: a b c ^ ^
  40. Ví dụ 4 Hai mức ưu tiên cho dấu ngoặc trái ( Mức ưu tiên đầu vào: 5 cao hơn bất kỳ toán tử nào. (tất cả các toán tử trong stac phải giữ nguyên vì có một biểu thức con mới.) Mức ưu tiên tại stack: -1 thấp hơn của bất kỳ toán tử nào. (không toán tử nào trong biểu thức con được xóa cho đến khi gặp dấu ngoặc mở) a * ( b + c ) ( có mức ưu tiên là 5 ⇒ đưa vào stack. Stack toán tử: + ( hiện có mức ưu tiên là -1 ⇒ ( tiếp tục ở trong stack. * Xâu hậu tố: a b c + *
  41. Mức ưu tiên đầu vào và tại Stack Mức ưu tiên Mức ưu tiên Toán tử đầu vào tại stack Hạng + - 1 1 -1 * / % 2 2 -1 ^ 4 3 -1 ( 5 -1 0 ) 0 0 0
  42. Các quy luật đánh giá Ghi ký tự vào xâu hậu tố nếu nó là toán hạng. Nếu ký tự là một toán tử hoặc (, so sánh mức ưu tiên của nó với mức ưu tiên của toán tử tại đỉnh stack. Rút phần tử đỉnh stack nếu mức ưu tiên của phần tử tại stack là cao hơn hoặc bằng và ghi tiếp nó vào xâu hậu tố. Lặp cho đến khi toán tử tại đỉnh stack có hạng thấp hơn, đẩy ký tự vào stack. Nếu ký tự là ), rút tất cả các toán tử ra khỏi stack cho đến khi gặp ( và ghi các toán tử vào xâu hậu tố.Rút( ra khỏi stack. Khi kết thúc biểu thức trung tố,rút tất cả các toán tử ra khỏi stack và ghi vào xâu hậu tố.
  43. Ví dụ 3 * (4 – 2 ^ 5) + 6 Stack toán tử ( [-1] ( [-1] * [2] * [2] * [2] Hậu tố 3 3 3 3 4 ^ [3] ^ [3] - [1] - [1] - [1] - [1] ( [-1] ( [-1] ( [-1] ( [-1] ( [-1] * [2] * [2] * [2] * [2] * [2] 3 4 3 4 2 3 4 2 3 4 2 5 3 4 2 5 ^ -
  44. cont’d Pop ( 3 * (4 – 2 ^ 5) + 6 * [2] + [1] + [1] 3 4 2 5 ^ - 3 4 2 5 ^ - * 3 4 2 5 ^ - * 6 3 4 2 5 ^ - * 6 +
  45. Stack Xây dựng một stack cho phép lưu trữ các toán tử và mức ưu tiên của nó. typedef struct Operator { char symbol; // toán tử // mức ưu tiên đầu vào của toán tử op int inputPrecedence; // mức ưu tiên trong stack của toán tử op int stackPrecedence; }Operator; typedef struct OpStack { Operator * stackAry; . } OpStack ;
  46. Output Stack Symbols Rút các toán tử trong stack có stack precedence ≥ input precendence của ký tự đang đọc. void PopHigherOrEqualOp(OpStack* stack, Operator& op string& postfix) { Operator op2; while(!IsEmpty(stack) && (op2 = Top(stack)).stackPrecedence >= op.inputPrecedence) { Pop(stack); postfix += op2.symbol; } }
  47. Hàm chuyển đổi trung tố -hậu tố Infix2Postfix() thực hiện những công việc sau: Ghi toán hạng ra xâu hậu tố. Gọi outputHigherOrEqual() nếu gặp toán tử. Gọi outputHigherOrEqual() nếu gặp ). Kết thúc khi đọc hết biểu thức
  48. string Infix2Postfix ( string infix) { string postfix; // lưu xâu biểu thức hậu tố OpStack* stack = CreateStack( MAX); // tạo stack // Duyệt từng ký tự của biểu thức for (i=0; i < infix.length(); i++) { ch = infix [i]; // Trường hợp toán hạng if (isdigit(ch)) // ghi toán hạng vào biểu thức hậu tố postfix += ch; // Trường hợp toán tử hoặc '(' else if (isOperator(ch) || ch == '(') { // rút các toán tử có mức ưu tiên cao hơn // ra khỏi stack Operator op = createOperator(ch); PopHigherOrEqualOp(stack, op, postfix); // đẩy toán tử hiện tại vào stack Push(stack, op); }
  49. // Trường hợp ‘)' else if (ch == ‘)’) { // tạo một biến Operator cho ')‘ Operator op = CreateOperator(ch); // Rút tất cả toán tử của biểu thức con // cho đến khi gặp '(' PopHigherOrEqualOp(stack, op, postfix); // Rút '(' ra khỏi stack Pop(stack); } } // end for // Rút các toán tử còn lại trg stack, ghi vào xâu while (!IsEmpty(stack)) { op = Pop(stack); postfix += op.symbol; } return postfix; }
  50. 4. Định nghĩa Queue Queue: là danh sách mà thêm phải được thực hiện tại một đầu còn xóa phải thực hiện tại đầu kia. Xóa Thêm Đầu Cuối (Enqueue) (Dequeue)
  51. Figure 5-1 Ví dụ của Queue trong thựctế • Queue là mộtkiểucấu trúc FIFO: First In First Out
  52. Các thao tác cơ bảnvới Queue Enqueue – Thêm mộtphầntử vào cuối queue Tràn Overflow Dequeue – Xóa mộtphầntử tại đầu queue Queue rỗng? Front – Trả lạiphầntử tại đầu queue Queue rỗng? End – Trả lạiphầntử tạicuối queue Queue rỗng
  53. Figure 5-2 Enqueue
  54. Figure 5-3 Dequeue
  55. Figure 5-4 Queue Front
  56. Figure 5-5 Queue Rear
  57. Lưu trữ Queue Tương tự như Stack, có 2 cách lưu trữ: Lưu trữ kế tiếp: sử dụng mảng Lưu trữ móc nối: sử dụng danh sách móc nối
  58. Figure 5-15 5. Lưu trữ kế tiếp với Queue
  59. Figure 5-16 Queue tăng hếtmảng •Do đócầnsử dụng mộtmảng rấtlớn?
  60. Queue dạng vòng front front front A rear A A D B C B C B rear rear rear D E rear D C C B front B front
  61. Queue thựchiệntrênmảng queueAry maxsize count front rear 7415 front rear 11 37 22 15 3 -7 1
  62. Định nghĩa cấu trúc Queue typedef struct intqueue { int *queueAry; int maxSize; int count; int front; int rear; }IntQueue;
  63. Tạo Queue IntQueue* CreateQueue (int max) { IntQueue *queue; queue = (IntQueue *)malloc(sizeof(IntQueue)); /* Cấp phát cho mảng */ queue->queueAry = malloc(max * sizeof(int)); /* Khởi tạo queue rỗng */ queue->front = -1; queue->rear = -1; queue->count = 0; queue->maxSize = maxSize; return queue; } /* createQueue */
  64. Enqueue int enqueue (struct intqueue *queue, int datain) { if (queue->count == queue->maxSize) return 0; /* queue is full */ (queue->rear)++; if (queue->rear == queue->maxSize) /* Queue wraps to element 0 */ queue->rear = 0; queue->queueAry[queue->rear] = datain; if (queue->count == 0) { /* Inserting into null queue */ queue->front = 0; queue->count = 1; } /* if */ else (queue->count)++; return 1;
  65. Dequeue int dequeue (struct intqueue *queue, int *dataOutPtr) { if (!queue->count) return 0; *dataOutPtr = queue->queueAry[queue->front]; (queue->front)++; if (queue->front == queue->maxSize) /* queue front has wrapped to element 0 */ queue->front = 0; if (queue->count == 1) /* Deleted only item in queue */ queue->rear = queue->front = -1; (queue->count) ; return 1;
  66. queueFront int queueFront (struct intqueue *queue, int *dataOutPtr) { if (!queue->count) return 0; else { *dataOutPtr = queue->queueAry[queue->front]; return 1; } /* else */ } /* queueFront */
  67. queueRear int queueRear (struct intqueue *queue, int *dataOutPtr) { if (!queue->count) return 0; else { *dataOutPtr = queue->queueAry[queue->rear]; return 1; } /* else */ } /* queueRear */
  68. emptyQueue and fullQueue int emptyQueue (struct intqueue *queue) { return (queue->count == 0); } /* emptyQueue */ int fullQueue (struct intqueue *queue ) { return ( queue->count == queue->maxSize); } /* fullQueue */
  69. destroyQueue struct intqueue *destroyQueue (struct intqueue *queue) { if (queue) { free (queue->queueAry); free (queue); } /* if */ return NULL; } /* destroyQueue */
  70. 6. Lưu trữ móc nối với Stack
  71. Các cấutrúccủa head và node link link
  72. Khai báo stack typedef struct node { int data ; struct node *link ; } STACK_NODE; typedef struct stack { int count ; STACK_NODE *top ; } STACK;
  73. createStack static STACK *createStack () { STACK *stack ; stack = (STACK *) malloc( sizeof (STACK) ) ; if (stack) { stack->top = NULL ; stack->count = 0; } /* if */ return stack ; } /* createStack */
  74. Push Giống như Thêm mộtphầntử mớivào danh sách trướcphầntửđầu
  75. pushStack static int pushStack(STACK *stack, int dataIn) { STACK_NODE *newPtr; newPtr = (STACK_NODE *) malloc(sizeof( STACK_NODE)); if (newPtr == NULL) return 0; /* no more space */ newPtr->data = dataIn; newPtr->link = stack->top; stack->top = newPtr; ( stack->count )++; return 1; } /* pushStack */
  76. 7. Lưutrữ móc nốivới Queue Bài tậpvề nhà: Xây dựng Queue móc nối