›
›

Bài giảng Kỹ thuật lập trình - Chương 4: Một số cấu trúc dữ liệu và giải thuật căn bản (Phần 1) - Lương Mạnh Bá

•Cấu trúc dữ liệu là cách tổ chức và thao tác có hệ thống trên dữ liệu

•Một cấu trúc dữ liệu :

–Mô tả

•Các dữ liệu cấu thành

•Mối liên kết về mặt cấu trúc giữa các dữ liệu đó

–Xác định các thao tác trên dữ liệu đó

 

•

ppt 123 trang xuanthi 27/12/2022 2960
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 4: Một số cấu trúc dữ liệu và giải thuật căn bản (Phần 1) - Lương Mạnh Bá", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pptbai_giang_ky_thuat_lap_trinh_chuong_4_mot_so_cau_truc_du_lie.ppt

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 4: Một số cấu trúc dữ liệu và giải thuật căn bản (Phần 1) - Lương Mạnh Bá

  1. 1. Các khái niệm cơ bản Cấu trúc dữ liệu • Cấu trúc dữ liệu là cách tổ chức và thao tác có hệ thống trên dữ liệu • Một cấu trúc dữ liệu : – Mô tả • Các dữ liệu cấu thành • Mối liên kết về mặt cấu trúc giữa các dữ liệu đó – Xác định các thao tác trên dữ liệu đó 30/12/2022 SE-SoICT KTLT4-2.2 Last Update 8-2010
  2. 1. Các khái niệm cơ bản Dữ liệu, kiểu dữ liệu, cấu trúc dữ liệu Machine Level Data Storage 0100110001101001010001 Primitive Data Types 28 3.1415 'A' Basic Data Structures array High-Level Data Structures stack queue list hash table tree 30/12/2022 SE-SoICT KTLT4-2.4 Last Update 8-2010
  3. 1. Danh sách (list) • Danh sách : – Tập hợp các phần tử cùng kiểu – Số lượng các phần tử của danh sách không cố định • Phân loại: – Danh sách tuyến tính: • Có phần tử đầu tiên, phần tử cuối cùng • Thứ tự trước / sau của các phần tử được xác định rõ ràng – Danh sách không tuyến tính: các phần tử trong danh sách không được sắp thứ tự • Có nhiều hình thức lưu trữ danh sách – Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ → danh sách kế tiếp – Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ → danh sách móc nối • Danh sách nối đơn • Danh sách nối kép 30/12/2022 SE-SoICT KTLT4-2.6 Last Update 8-2010
  4. 1.1. Danh sách kế tiếp • Sử dụng một vector lưu trữ gồm một số các ô nhớ liên tiếp để lưu trữ một danh sách tuyến tính – Các phần tử liền kề nhau được lưu trữ trong những ô nhớ liền kề nhau – Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ tự được lưu trữ trong vector – Tham chiếu đến các phần tử sử dụng địa chỉ được tính giống như lưu trữ mảng. 0 1 2 i last n-1 30/12/2022 SE-SoICT KTLT4-2.8 Last Update 8-2010
  5. 1.1.a. Thêm một phần tử vào một danh sách kế tiếp • 2 trường hợp – insert(index, element): thêm một phần tử element vào một vị trí cụ thể index – insert(list, element): thêm một phần tử element vào vị trí bất kỳ trong danh sách list • Điều kiện tiên quyết: – Danh sách phải được khởi tạo rồi – Danh sách chưa đầy – Phần tử thêm vào chưa có trong danh sách • Điều kiện hậu nghiệm: – Phần tử cần thêm vào có trong danh sách insert(3, ‘z’) 0 1 2 3 4 5 6 7 8 9 z a b c d e f g h 30/12/2022 SE-SoICT count=count=8KTLT4-2.910 Last Update 8-2010
  6. 1.1.b.Xóa 1 phần tử khỏi danh sách kế tiếp remove(3, ‘d’) 0 1 2 3 4 5 6 7 8 9 a b c d e f g hh count=8count=7 30/12/2022 SE-SoICT KTLT4-2.12 Last Update 8-2010
  7. 1.1.c.Duyệt danh sách kế tiếp Algorithm Traverse Input: hàm visit dùng để tác động vào từng phần tử Output: danh sách được cập nhật bằng hàm visit //Quét qua tất cả các phần tử trong list for index = 0 to count-1 Thi hành hàm visit để duyệt phần tử entry[index] End Traverse 30/12/2022 SE-SoICT KTLT4-2.14 Last Update 8-2010
  8. Tổ chức danh sách móc nối • Nút = dữ liệu + móc nối{ • Định nghĩa: typedef struct node { typed data; struct node *next; } Node; • Tạo nút mới: Node *p = malloc(sizeof(Node));{ • Giải phóng nút: free(p); 30/12/2022 SE-SoICT KTLT4-2.16 Last Update 8-2010
  9. Truyền danh sách móc nối vào hàm • { Khi truyền danh sách móc nối vào hàm, chỉ cần truyền Head. • { Sử dụng Head để truy cập toàn bộ danh sách – { Note: nếu hàm thay đổi vị trí nút đầu của danh sách (thêm hoặc xóa nút đầu) thì Head sẽ không còn trỏ đến đầu danh sách – { Do đó nên truyền Head theo tham biến (hoặc trả lại một con trỏ mới) 30/12/2022 SE-SoICT KTLT4-2.18 Last Update 8-2010
  10. Thêm vào danh sách rỗng • Head = NULL Node *newNode; newNode= malloc(sizeof(Node)); newNode->data = 20; newNode->next = NULL; Head = newNode; 30/12/2022 SE-SoICT KTLT4-2.20 Last Update 8-2010
  11. Thêm một nút vào giữa/cuối danh sách newNode= malloc(sizeof(Node)); newNode->data = 13; newNode->next = currNode->next; currNode->next= newNode; 30/12/2022 SE-SoICT KTLT4-2.22 Last Update 8-2010
  12. Thêm một nút mới Node * InsertNode(Node *head,int index,int x) { if (index currIndex) { NULL currNode = currNode->next; currIndex++; } if (index data = x; if (index == 0) { newNode->next = head; Thêm vào đầu ds head = newNode;} else { newNode->next = currNode->next; Thêm vào sau currNode currNode->next = newNode;} return newNode; }30/12/2022 SE-SoICT KTLT4-2.24 Last Update 8-2010
  13. Xóa nút { int DeleteNode(int x) • { Xóa nút có giá trị bằng x trong danh sách. • { Nếu tìm thấy nút, trả lại vị trícủa nó. Nếu không, trả lại 0. • { Giải thuật – Tìm nút có giá trị x (tương tự như FindNode) – Thiết lập nút trước của nút cần xóa nối đến nút sau của nút cần xóa – Giải phóng bộ nhớ cấp phát cho nút cần xóa – Giống như InsertNode, có 2 trường hợp • Nút cần xóa là nút đầu tiên của danh sách • Nút cần xóa nằm ở giữa hoặc cuối danh sách 30/12/2022 SE-SoICT KTLT4-2.26 Last Update 8-2010
  14. Hủy danh sách { void DestroyList(Node *head) • { Dùng để giải phóng bộ nhớ được cấp phát cho danh sách. • { Duyệt toàn bộ danh sách và xóa lần lượt từng nút. Void DestroyList(Node* head){ Node *currNode = head, *nextNode= NULL; while(currNode != NULL){ nextNode = currNode->next; free(currNode); // giải phóng nút vừa duyệt currNode = nextNode; } } 30/12/2022 SE-SoICT KTLT4-2.28 Last Update 8-2010
  15. Danh sách nối kép { Mỗi nút không chỉ nối đến nút tiếp theo mà còn nối đến nút trước nó • { Có 2 mối nối NULL: tại nút đầu và nút cuối của danh sách • { Ưu điểm:tại một nút có thể thăm nút trước nó một cách dễ dàng. Cho phép duyệt danh sách theo chiều ngược lại 30/12/2022 SE-SoICT KTLT4-2.30 Last Update 8-2010
  16. • Thêm nút New nằm ngay trước Cur (không phải nút đầu hoặc cuối danh sách) New->next = Cur; New->prev= Cur->prev; Cur->prev= New; (New->prev)->next = New; • Xóa nút Cur(không phải nút đầu hoặc cuối danh sách) (Cur->prev)->next = Cur->next; (Cur->next)->prev = Cur->prev; 30/12/2022free (Cur); SE-SoICT KTLT4-2.32 Last Update 8-2010
  17. • Tạo danh sách nối kép rỗng Node *Head = malloc (sizeof(Node)); Head->next = Head; Head->prev = Head; • Khi thêm hoặc xóa các nút tại đầu ds, giữa hay cuối ds ??? 30/12/2022 SE-SoICT KTLT4-2.34 Last Update 8-2010
  18. Thêm nút void insertNode(Node *Head, int item) { Node *New, *Cur; New = malloc(sizeof(Node)); New->data = item; Cur = Head->next; while (Cur != Head){ if (Cur->data next; else break; } New->next = Cur; New->prev= Cur->prev; Cur->prev= New; (New->prev)->next = New; } 30/12/2022 SE-SoICT KTLT4-2.36 Last Update 8-2010
  19. 1.3 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 • 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) 30/12/2022 SE-SoICT KTLT4-2.38 Last Update 8-2010
  20. Ví dụ về Stack trong thực tế 30/12/2022Stack là một cấu trúcSE LIFO:-SoICT Last In First OutKTLT4-2.40 Last Update 8-2010
  21. 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 (sau) 30/12/2022 SE-SoICT KTLT4-2.42 Last Update 8-2010
  22. Tạo Stack 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->stackArr=malloc(max * sizeof(int)); return stack ; } 30/12/2022 SE-SoICT KTLT4-2.44 Last Update 8-2010
  23. 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->stackArr[stack->top]; (stack->count) ; (stack->top) ; /* Giảm đỉnh */ Return 1; } 30/12/2022 SE-SoICT KTLT4-2.46 Last Update 8-2010
  24. Ứng dụng của Stack zBà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 =348 3 2 1 0 • (base 4) 7210 = 1•4 + 0•4 + 2•4 + 0•4 = 10204 5 4 3 2 • (base 2) 5310 = 1 •2 + 1 •2 + 0 •2 + 1 •2 + 1 0 0 •2 + 1 •2 = 1101012 30/12/2022 SE-SoICT KTLT4-2.48 Last Update 8-2010
  25. Chuyển sang dạng ký tự tương ứng: Char *digitChar= “0123456789ABCDEF”; char d = digitChar[13]; // 1310= D16 char f = digitChar[15]; // 1510= F16 30/12/2022 SE-SoICT KTLT4-2.50 Last Update 8-2010
  26. Ứng dụng của Stack (tiếp) Các biểu thức số học được biểu diễn bằng 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: vd -2 + 3 * 5 (-2) + (3 * 5) • Thứ tự ưu tiên của các phép tử: () > ^ > * = % = / > + = – • Việc đánh giá biểu thức trung tố khá phức tạp 30/12/2022 SE-SoICT KTLT4-2.52 Last Update 8-2010
  27. 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 + -5 3 + -8 -8 2 * - 4 - 4 11 - 30/127/2022 7 SE-SoICT KTLT4-2.54 Last Update 8-2010
  28. Bool isOperator(char op) { return op == '+‘ || op == '-' || op == '*‘ || op == '%‘ || op == '/‘ || op == '^‘ ; } Int compute(int left, int right, char op){ int value; 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); } 30/12/2022return value; SE-SoICT KTLT4-2.56 }Last Update 8-2010
  29. Bài tập • Sửa Chương trình trên để tính toán kết quả của 1 biểu thức hậu tố với các toán hạng tổng quát ( có thể là số thực, có thể âm ) • Xây dựng chương trình chuyển đổi 1 biểu thức từ trung tố sang hậu tố, biểu thức trung tố là 1 xâu ký tự với các toán hạng tổng quát và các phép toán cùng độ ưu tiên như sau : () > ^ > * = % = / > + = – 30/12/2022 SE-SoICT KTLT4-2.58 Last Update 8-2010
  30. • Phần tử đầu hàng sẽ được phục trước, phần tử này được gọi làfront , hay head của hàng. Tương tự, phần tử cuối hàng , cũng là phần tử vừa được thêm vào hàng, được gọi là rear hay tail của hàng. 30/12/2022 SE-SoICT KTLT4-2.60 Last Update 8-2010
  31. • Hiện thực của dãy vòng – Ta dùng 1 dãy tuyến tính để mô phỏng 1 dãy vòng. – Các vị trí trong vòng tròn được đánh số từ 0 đến max-1, trong đó max là tông số PTử. – Để thực hiện dãy vòng, chúng ta cũng sử dụng các phân tử được đánh số tương tư dãy tuyến tính. – Sự thay đổi các chỉ số chỉ đơn giản là phép lấy phần dư số học: khi một chỉ số vợt quá max-1, nó đc bắt đầu trở lại vợi trị 0. Điều này tương tự với việc cộng thêm giờ trên đồng hồ mặt tròn i = ((i+1) == max) ? 0: (i+1); Hoặc if ((i+1) == max) i = 0; else i = i+1; Hoặc i = (i+1) % max; 30/12/2022 SE-SoICT KTLT4-2.62 Last Update 8-2010
  32. 30/12/2022 SE-SoICT KTLT4-2.64 Last Update 8-2010
  33. Queue thực hiện trên mảng 30/12/2022 SE-SoICT KTLT4-2.66 Last Update 8-2010
  34. 30/12/2022 SE-SoICT KTLT4-2.68 Last Update 8-2010
  35. • 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*/ 30/12/2022 SE-SoICT KTLT4-2.70 Last Update 8-2010
  36. Dequeue : Xóa PT ở đầu queue int dequeue(struct intqueue *queue, int *dOutPtr) {if(!queue->count) return 0; *dOutPtr= queue->queueAry[queue->front]; (queue->count) ; queue->front = (queue->front +1) % queue->maxSize; return 1; } 30/12/2022 SE-SoICT KTLT4-2.72 Last Update 8-2010
  37. • Rear : lấy PT cuối Queue int Rear(struct intqueue *queue,int*dOutPtr) { if(!queue->count) return 0; else{ *daOutPtr= queue->queueAry[queue->rear]; return 1; } } 30/12/2022 SE-SoICT KTLT4-2.74 Last Update 8-2010
  38. • destroyQueue struct intqueue *destroyQueue(struct intqueue *queue) { if(queue) { free(queue->queueAry); free(queue); } return NULL; }/* destroyQueue*/ 30/12/2022 SE-SoICT KTLT4-2.76 Last Update 8-2010
  39. 4.II.2 Tree 1.Định nghĩa và khái niệm 2.Cây nhị phân – { Định nghĩa vàTính chất – { Lưu trữ – { Duyệt cây 3.Cây tổng quát – { Biểu diễn cây tổng quát – { Duyệt cây tổng quát (nói qua) 4.Ứng dụng của cấu trúc cây – Cây biểu diễn biểu thức (tính giá trị, tính đạo hàm) – Cây quyết định 30/12/2022 SE-SoICT KTLT4-2.78 Last Update 8-2010
  40. Các khái niệm cơ bản về cây • Một cây (tree) gồm một tập hữu hạn cácnút (node) và 1 tập hữu hạn các cành (branch) nối giữa các nút= > quan hệ phân cấp “cha-con”. • Số cạnh ra (con) tại một nút gọi làbậc /cấp (degree) cuả nút đó. Nếu cây không rỗng thì phải có 1 nút gọi là nút gốc (root), nút này không có cạnh vào • Cấp của 1 cây là cấp cao nhất của các nút trên cây. • Định nghĩa (ĐQ): Một cây là tập các nút mà : - là tập rỗng, hoặc - có 1 nút gọi là nút gốc và có 0 hoặc nhiều cây 30/12/2022 SE-SoICT KTLT4-2.80 Last Updatecon, 8-2010 các cây con cũng là cây.
  41. 30/12/2022 SE-SoICT KTLT4-2.82 Last Update 8-2010
  42. Đường đi 30/12/2022 SE-SoICT KTLT4-2.84 Last Update 8-2010
  43. Cấp 30/12/2022 SE-SoICT KTLT4-2.86 Last Update 8-2010
  44. Cây nhị phân hoàn chỉnh và Cây nhị phân đầy đủ Cây nhị phân hoàn chỉnh Cây nhị phân đầy đủ Các nút có tối đa 2 con Tất cả nút lá đều có cùng Các nút lấp đầy từ trái độ sâu và tất cả nút sang phải. Thiếu về phải giữa có cấp = 2 30/12/2022 SE-SoICT KTLT4-2.88 Last Update 8-2010
  45. Cây cân bằng (tự đọc) • Khoảng cách từ 1 nút đến nút gốc xác định chi phí cần để định vị nó : 1 nút có độ sâu là 5 => phải đi từ nút gốc và qua 5 cành • Nếu cây càng thấp thì việc tìm đến các nút sẽ càng nhanh. Điều này dẫn đến tính chất cân bằng của cây nhị phân. Hệ số cân bằng của cây (balance factor) là sự chênh lệch giữa chiều cao của 2 cây con trái và phải của nó: B = HL-HR • Một cây cân bằng khi B = 0 và các cây con của nó cũng cân bằng 30/12/2022 SE-SoICT KTLT4-2.90 Last Update 8-2010
  46. • Cấu trúc cây nhị phân typedef structtree_node { int data ; structtree_node *left ; structtree_node *right ; }TREE_NODE; 30/12/2022 SE-SoICT KTLT4-2.92 Last Update 8-2010
  47. 2.3. Duyệt cây nhị phân • { Duyệt cây: lần lượt duyệt toàn bộ nút trên cây • { Có 3 cách duyệt cây: – { Duyệt theo thứ tự trước – { Duyệt theo thứ tự giữa – { Duyệt theo thứ tự sau • { Định nghĩa duyệt cây nhị phân là những định nghĩa đệ quy. 30/12/2022 SE-SoICT KTLT4-2.94 Last Update 8-2010
  48. Duyệt theo thứ tự sau 1. Duyệt cây con trái theo thứ tự sau. 2. Duyệt cây con phải theo thứ tự sau. 3. Thăm nút. 30/12/2022 SE-SoICT KTLT4-2.96 Last Update 8-2010
  49. Thứ tự trước: 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 Thứ tự giữa :2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 30Thứ/12/2022 tự sau :2, 4, 3, 9,SE -13,SoICT 7, 6, 17, 20, 18, 15KTLT4-2.98 Last Update 8-2010
  50. Duyệt theo thứ tự trước–Vòng lặp void Preorder_iter(TREE_NODE *treeRoot) {// không tối ưu!!! Xem trongCTDL> TREE_NODE *curr= treeRoot; STACK *stack= createStack(MAX);// khởi tạostack while (curr != NULL || !IsEmpty(stack)) { printf("%d", curr->data); // thămcurr // nếu có cây con phải, đẩy cây con phải vào stack if (curr->right != NULL) pushStack(stack, curr->right); if(curr->left!=NULL) curr= curr->left; // duyệt cây con trái else popStack(stack, &curr);// duyệt cây con phải } destroyStack(&stack);// giải phóng stack 30/12/2022 SE-SoICT KTLT4-2.100 }Last Update 8-2010
  51. Duyệt theo thứ tự cuối voidPostorder_iter(TREE_NODE *treeRoot) { TREE_NODE *curr= treeRoot; STACK *stack= createStack(MAX);//ktạo một stack while( curr != NULL || !IsEmpty(stack)) { if (curr == NULL) { while(!IsEmpty(stack) && curr==Top(stack)->right){ PopStack(stack, &curr); printf(“%d”, curr->data); } curr= isEmpty(stack)? NULL: Top(stack)->right; } else{ PushStack(stack, curr); curr= curr->left; } } destroyStack(&stack);// giải phóng stack 30/12/2022 SE-SoICT KTLT4-2.102 Last} Update 8-2010
  52. Tính độ cao của cây int Height(TREE_NODE *tree) { Int heightLeft, heightRight, heightval; if( tree== NULL ) heightval= 0; else { // Sửdụng phương pháp duyệt theo thứ tự sau heightLeft= Height (tree->left); heightRight= Height (tree->right); heightval= 1 + max(heightLeft,heightRight); } return heightval; 30/12/2022 SE-SoICT KTLT4-2.104 } Last Update 8-2010
  53. Sao chép cây 30/12/2022 SE-SoICT KTLT4-2.106 Last Update 8-2010
  54. Xóa cây void DeleteTree(TREE_NODE *tree) { //xóa theo thứ tự sau if(tree != NULL) { DeleteTree(tree-> left); DeleteTree(tree-> right); free(tree); } } 30/12/2022 SE-SoICT KTLT4-2.108 Last Update 8-2010
  55. Biểu diễn cây tổng quát • Sử dụng con trỏ nhưng mở rộng hơn: – zMỗi nút sẽ có 2 con trỏ: một con trỏ trỏ đến nút con đầu tiên của nó, con trỏ kia trỏ đến nút anh em kề với nó – {Cách này cho phép quản lý số lượng tùy ý của các nút con 30/12/2022 SE-SoICT KTLT4-2.110 Last Update 8-2010
  56. 3.2. Duyệt cây tổng quát 1.Thứ tự trước: 1.Thăm gốc 2.Duyệt cây con thứ nhất theo thứ tự trước 3.Duyệt các cây con còn lại theo thứ tự trước 2.Thứ tự giữa 1.Duyệt cây con thứ nhất theo thứ tự giữa 2.Thăm gốc 3.Duyệt các cây con còn lại theo thứ tự giữa 3.Thứ tự sau: 1.Duyệt cây con thứ nhất theo thứ tự sau 2.Duyệt các cây con còn lại theo thứ tự sau 3.Thăm gốc 30/12/2022 SE-SoICT KTLT4-2.112 Last Update 8-2010
  57. Cây biểu diễn biểu thức là. Một loại cây nhị phân đặc biệt, trong đó: 1. Mỗi nút lá chứa một toán hạng 2. Mỗi nút giữa chứa một toán tử 3. Cây con trái và phải của một nút toán tử thể hiện các biểu thức con cần được đánh giá trước khi thực hiện toán tử tại nút gốc 30/12/2022 SE-SoICT KTLT4-2.114 Last Update 8-2010
  58. Các mức chỉ ra thứ tự ưu tiên • Các mức (độ sâu) của các nút chỉ ra thứ tự ưu tiên tương đối của chúng trong biểu thức (không cần dùng ngoặc để thể hiện thứ tự ưu tiên). • Các phép toán tại mức cao hơn sẽ được tính sau các các phép toán có mức thấp. • Phép toán tại gốc luôn được thực hiện cuối cùng. 30/12/2022 SE-SoICT KTLT4-2.116 Last Update 8-2010
  59. Cài đặt cây biểu thức • Mỗi nút có 2 con trỏ struct TreeNode { InfoNode info ;// Dữ liệu TreeNode *left ;// Trỏ tới nút con trái TreeNode *right ; // Trỏ tới nút con phải }; 30/12/2022 SE-SoICT KTLT4-2.118 Last Update 8-2010
  60. int Eval(TreeNode* ptr){ switch(ptr->info.whichType) { case OPERAND : returnptr->info.operand ; case OPERATOR : switch ( tree->info.operation ){ case ‘+’: return ( Eval( ptr->left ) + Eval( ptr->right ) ) ; case ‘-’: return ( Eval( ptr->left ) -Eval( ptr->right ) ) ; case ‘*’: return ( Eval( ptr->left ) * Eval( ptr->right ) ) ; case ‘/’: return ( Eval( ptr->left ) / Eval( ptr->right ) ) ; } } } 30/12/2022 SE-SoICT KTLT4-2.120 Last Update 8-2010
  61. 30/12/2022 SE-SoICT KTLT4-2.122 Last Update 8-2010