Giáo trình Kỹ thuật lập trình - Bài 4: Cấu trúc dữ liệu - Trịnh Thành Trung

Trịnh Thành Trung (ThS) trungtt@soict.hust.edu.vn Bài 4 CẤU TRÚC DỮ LIỆU Các bài toán thực tế thường rất phức tạp Phải xác định được o Các dữ liệu liên quan đến bài toán o Các thao tác cần thiết để giải quyết bài toán 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 đó Cung cấp các thao tác trên dữ liệu đó Đặc trưng cho 1 kiểu dữ liệu là cách tổ chức và thao tác có hệ thống trên dữ liệu Dữ liệu, kiểu dữ liệu & cấu trúc dữ liệu Machine Level Data Storage Primitive Data Types Basic Data Structures High-Level Data Structures 0100110001101001010001 28 3.1415 'A' stack queue list array hash table tree Các kiểu dữ liệu Kiểu dữ liệu cơ bản (primitive data type) ▪Đại diện cho các dữ liệu giống nhau, không thể phân chia nhỏ hơn được nữa ▪Thường được các ngôn ngữ lập trình định nghĩa sẵn ▪Ví dụ ▫C/C++: int, long, char, bool... ▫Thao tác trên các số nguyên: + - * / ... Kiểu dữ liệu có cấu trúc (structured data type) ▪Được xây dựng từ các kiểu dữ liệu (cơ bản, có cấu trúc) khác ▪Có thể được các ngôn ngữ lập trình định nghĩa sẵn hoặc do lập trình viên tự định nghĩa Nội dung 1. Mảng 2. Danh sách 3. Ngăn xếp 4. Hàng đợi 5. Cây 1. Mảng Array Mảng Array ▪ Dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên ▪ Một hay nhiều chiều ▫ C không giới hạn số chiều của mảng Cú pháp DataType ArrayName[size]; mảng nhiều chiều DataType ArrayName[size 1][size 2]...[size n]; Khởi tạo giá trị mảng ▪ C1. Khi khai báo float y[5] = { 3.2, 1.2, 4.5, 6.0, 3.6 } int m[6][2] = { { 1, 1 }, { 1, 2 }, { 2, 1 }, { 2, 2 }, { 3, 1 }, { 3, 2 } }; char s1[6] = { 'H', 'a', 'n', 'o', 'i', '\0' }; //hoặc char s1[6] = "Hanoi"; char s1[] = "Dai hoc Bach Khoa Hanoi"; //L = 24 int m[][] = { { 1, 2, 3 }, { 4, 5, 6 } }; ▪ C2. Khai báo rồi gán giá trị cho từng phần tử của mảng. int m[4]; m[0] = 1; m[1] = 2; m[2] = 3; m[3] = 4; 2. Danh sách List 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, ví dụ sắp theo thứ tự tăng dần, giảm dần hay thứ tự trong bảng chữ cái ▸Các thao tác trên danh sách phải không làm ảnh hưởng đến trật tự này ▫ Danh sách phi tuyến tính: các phần tử trong danh sách không được sắp thứ tự Danh sách List ▪ Lưu trữ ▫ 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 Thao tác trên danh sách  Khởi tạo danh sách (create)  Kiểm tra danh sách rỗng (isEmpty)  Kiểm tra danh sách đầy (isFull)  Tính kích thước (sizeOf)  Xóa rỗng danh sách (clear)  Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert)  Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách (remove)  Lấy một phần tử tại một vị trí cụ thể (retrieve)  Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace) Duyệt danh sách và thực hiện một thao tác tại các vị trí trong danh sách (traverse) 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 ▫ 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 Danh sách kế tiếp ▪ Ưu điểm ▫ Tốc độ truy cập vào các phần tử của danh sách nhanh ▪ Nhược điểm ▫ Cần phải biết trước kích thước tối đa của danh sách ? ▫ Thực hiện các phép toán bổ sung các phần tử mới và loại bỏ các phần tử cũ khá tốn kém ? Thêm vào danh sách kế tiếp ▪ Đ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’) da b c 0 1 2 3 4 5 6 7 8 9 e f g h z count=89 Algorithm Insert Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào Output: tình trạng danh sách if list đầy return overflow if index nằm ngoài khoảng [0..count] return range_error //Dời tất cả các phần tử từ index về sau 1 vị trí for i = count-1 down to index entry[i+1] = entry[i] entry[index] = element // Gán element vào vị trí index count++ // Tăng số phần tử lên 1 return success; End Insert Thêm vào danh sách kế tiếp remove(3, ‘d’) da b c 0 1 2 3 4 5 6 7 8 9 e f g h count=7 Xóa khỏi danh sách kế tiếp Algorithm Remove Input: index là vị trí cần xóa bỏ, element là giá trị lấy ra được Output: danh sách đã xóa bỏ phần tử tại index if list rỗng return underflow if index nằm ngoài khoảng [0..count-1] return range_error element = entry[index] //Lấy element tại vị trí index ra count-- //Giảm số phần tử đi 1 //Dời tất cả các phần tử từ index về trước 1 vị trí for i = index to count-1 entry[i] = entry[i+1] return success; End Remove Xóa khỏi danh sách kế tiếp 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 Danh sách nối đơn ▪ Một phần tử trong danh sách bằng một nút ▪ Thành phần một nút: ▫ INFO: chứa thông tin (nội dung, giá trị) ứng với phần tử ▫ NEXT: chứa địa chỉ của nút tiếp theo ▪ Cần nắm được địa chỉ của nút đầu tiên trong danh sách ? L INFO NE X T Danh sách nối đơn ▪ Nút = dữ liệu + móc nối ▪ Định nghĩa: typedef struct hoso { }; typedef struct node { struct hoso data; struct node *next; } Node; ▪ Tạo nút mới: Node *p = malloc(sizeof(Node)) ▪ Giải phóng nút: free(p); Khởi tạo và truy cập ▪ Khai báo một con trỏ Node *Head; ▪ Head là con trỏ trỏ đến nút đầu của danh sách. Khi danh sách rỗng thì Head = NULL. ▪ Một số thao tác với danh sách nối đơn 1. Thêm một nút mới tại vị trí cụ thể 2. Tìm nút có giá trị cho trước 3. Xóa một nút có giá trị cho trước 4. Ghép 2 danh sách nối đơn 5. Hủy danh sách nối đơn 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) Tìm nút int FindNode(int x) ▪ Tìm nút có giá trị x trong danh sách. ▪ Nếu tìm được trả lại vị trí của nút.Nếu không, trả lại 0. int FindNode(Node *head, int x) { Node *currNode = head; int currIndex = 1; while (currNode && currNode->data != x) { currNode = currNode->next; currIndex++; } if (currNode) return currIndex; else return 0; } Thêm nút ▪ Các trường hợp của thêm nút 1. Thêm vào danh sách rỗng 2. Thêm vào đầu danh sách 3. Thêm vào cuối danh sách 4. Thêm vào giữa danh sách ▪ Thực tế chỉ cần xét 2 trường hợp ▫ Thêm vào đầu danh sách ▫ Thêm vào giữa hoặc cuối danh sách ? Node *InsertNode(Node **head, int index, int x) ▪ Thêm một nút mới với dữ liệu là x vào sau nút thứ index ▪ Nếu thao tác thêm thành công,trả lại nút được thêm. Ngược lại trả lại NULL. ▸ (Nếu index độ dài của danh sách, không thêm được.) ▪ Giải thuật 1. Tìm nút thứ index – currNode 2. Tạo nút mới 3. Móc nối nút mới vào danh sách newNode->next = currNode->next; currNode->next = newNode; Thêm nút Node *InsertNode(Node **head,int index,int x) { if (index < 0) return NULL; int currIndex = 1; Node *currNode = *head; while(currNode && index > currIndex) { currNode = currNode->next; currIndex++; } if (index > 0 && currNode== NULL) return NULL; Node *newNode = (Node*) malloc(sizeof(Node)); newNode->data = x; if (index == 0) { newNode->next = *head; *head = newNode; } else { newNode->next = currNode->next; currNode->next = newNode; } return newNode; } Tìm nút thứ index, nếu không tìm được trả về NULL Tạo nút mới Thêm vào đầu ds Thêm vào sau currNode Thêm nút Xóa nút int DeleteNode(Node **head, 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 int DeleteNode(Node **head, int x) { Node *prevNode = NULL; Node *currNode = *head; int currIndex = 1; while (currNode && currNode->data != x) { prevNode = currNode; currNode = currNode->next; currIndex++; } if (currNode) { if (prevNode) { prevNode->next = currNode->next; free (currNode); } else { *head = currNode->next; free (currNode); } return currIndex; } return 0; } Tìm nút có giá trị = x Xóa nút ở giữa Xóa nút head Xóa nút 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; } } Mảng và danh sách liên kết Việc lập trình và quản lý danh sách liên kết khó hơn mảng, nhưng nó có những ưu điểm ▪ Linh động: danh sách liên kết có kích thước tăng hoặc giảm rất linh động. ▫ Không cần biết trước có bao nhiêu nút trong danh sách. Tạo nút mới khi cần. ▫ Ngược lại,kích thước của mảng là cố định tại thời gian biên dịch chương trình. ▪ Thao tác thêm và xóa dễ dàng ▫ Để thêm và xóa một phần tử mảng, cần phải copy dịch chuyển phần tử. ▫ Với danh sách móc nối, không cần dịch chuyển mà chỉ cần thay đổi các móc nối 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 ▪ Mỗi nút có 2 mối nối ▫ prev nối đến phần tử trước ▫ next nối đến phần tử sau typedef struct Node { int data; struct Node *next; struct Node *prev; } Node; Danh sách nối kép ▪ 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; Danh sách nối kép ▪ 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; free (Cur); Danh sách nối kép Danh sách nối kép với nút đầu giả ▪ Danh sách không rỗng ▪ Danh sách rỗng ▪ 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, giữa hay cuối danh sách? Danh sách nối kép với nút đầu giả 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 < item) Cur = Cur->next; else break; } New->next = Cur; New->prev= Cur->prev; Cur->prev= New; (New->prev)->next = New; } Thêm nút void deleteNode(Node *Head, int x){ Node *Cur; Cur = FindNode(Head, x); if (Cur != NULL){ Cur->prev->next = Cur->next; Cur->next->prev= Cur->prev; free(Cur); } } Xóa nút 3. Ngăn xếp Stack Ngăn xếp Stack danh sách mà xóa và thêm phần tử bắt buộc phải cùng được thực hiện tại một đầu duy nhất (đỉnh) Thao tác trên ngăn xếp Push  Thêm một phần tử  P: Tràn (overflow) Pop  Xóa một phần tử  P: Underflow Top  Phần tử đỉnh  P: Stack rỗng Is Full / Is Empty Lưu trữ ngăn xếp ▪ 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) Cấu trúc dữ liệu dùng mảng động /* Stack của các số nguyên: intstack*/ typedef struct IntStack { int *stackArr; /* mảng lưu trữ các phần tử */ int count; /* số ptử hiện có của stack */ int stackMax; /* giới hạn Max của số phần tử */ int top; /* chỉ số của phần tử đỉnh */ } IntStack; Tạo ngăn xếp 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 ; } Thêm vào ngăn xếp 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->stackArr[stack->top] =dataIn; return 1; } Xóa khỏi ngăn xếp 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; } Kiểm tra rỗng đầy Top, isEmpty, isFull Top int TopStack(IntStack *stack, int *dataOut){ if(stack->count ==0) // Stack rỗng return 0; *dataOut = stack->stackArr[stack->top]; return 1; } Kiểm tra rỗng int IsEmptyStack(IntStack *stack){ return(stack->count == 0); } Kiểm tra đầy int IsFullStack(IntStack *stack) { return(stack->count==stack->stackMax); } Ứng dụng 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ỳ ▪ (cơ số 8) 2810 = 3 × 8 1+ 4 × 80=348 ▪ (cơ số 4) 7210 = 1 × 4 3+ 0 × 42+ 2 × 41+ 0 × 40= 10204 ▪ (cơ số 2) 5310 = 1 × 25+ 1 × 24+ 0 × 23+ 1 × 22+ 0 × 21+ 1 × 20= 1101012 Đầu vào số thập phân n, cơ số b Đầu ra số hệ cơ số b tương đương 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ước 1-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ả Ví dụ : Đổi 3553 sang cơ số 8 ▪ Đối với hệ cơ số 16 ▫ Đổi sang ký tự tương ứng char *digitChar= “0123456789ABCDEF”; char d = digitChar[13]; // 1310= D16 char f = digitChar[15]; // 1310= F16 Ứng dụng Bài toán đổ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]); } } ▪ 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 -2 + 3 * 5 (-2) + (3 * 5) ▪ Thứ tự ưu tiên của các toán tử () > ^ > * = % = / > + = – Ứng dụng Tính biểu thức dùng ký pháp hậu tố Ký pháp hậu tố ▪ Toán hạng đặt trước toán tử ▪ Không cần dùng các dấu (). Ví dụ a*b*c*d*e*f => ab*c*d*e*f* 1 + (-5) / (6 * (7+8)) => 1 5 -6 7 8 + * / + (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 –* Ứng dụng Tính biểu thức dùng ký pháp hậu tố (7 –11) * 2 + 3 Biểu thức hậu tố: 7 11 – 2 * 3 + 7 7 11 - 4 - 4 2 -8 3 -5 - * -8 + Ví dụ ▪ 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ả ▪ Quy ước - Toán hạng: Là các số nguyên không âm một chữ số (cho đơn giản) - Toán tử: + , - , * , / , % , ^ Ứng dụng Tính biểu thức dùng ký pháp hậu tố 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); } return value; } int TinhBtHauTo(string Bt) { int left, right, kq; char ch; IntStack *stack = CreateStack(MAX); for(int i=0; i < Bt.length(); i++) { ch = Bt[i]; if ( isdigit(ch) ) PushStack(stack, ch-'0'); // đẩy toán hạng vào stack 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); kq =compute(left, right, ch); // Tính "leftop right" PushStack(stack, kq); // Đẩy kq vào stack } 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 kq PopStack(stack, kq); Return kq; } 4. Hàng đợi Queue Hàng đợi Queue danh sách mà việc 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. Thao tác trên hàng đợi Enqueue  Thêm một phần tử  P: Tràn (overflow) Dequeue  Xóa một phần tử  P: Underflow Front  Phần tử đầu  P: Queue rỗng Rear  Phần tử cuối  P: Queue rỗng Hàng đợi Queue ▪ 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. ▪ Biểu diễn hàng đợi ▫ Mô hình vật lý ▫ Hiện thực tuyến tính ▫ Hiện thực dãy vòng Mô hình vật lý ▪ Dùng mảng. Phải nắm giữ cả front và rear. ▪ Giữ front luôn là vị trí đầu của dãy. ▫ Thêm phần tử vào hàng ⇒ thêm vào cuối dãy. ▫ Lấy ra 1 phần tử ra ⇒ dịch chuyển tất cả các phần tử của dãy lên 1 vị trí. ▪ Tương tự hình ảnh hàng đợi trong thực tế ▫ Không phù hợp với lưu trữ trong máy tính Mô hình hiện thực tuyến tính ▪ Dùng 2 chỉ số front và rear để lưu trữ đầu và cuối hàng mà không di chuyển các phần tử. ▫ Thêm phần tử vào hàng ⇒ Tăng rear lên 1 và thêm phần tử vào vị trí đó ▫ Lấy ra 1 phần tử ra ⇒ Lấy phần tử tại front và tăng front lên 1 ▪ Nhược điểm: front và rear chỉ tăng mà không giảm ⇒ lãng phí bộ nhớ ▫ Khắc phục: Khi hàng đợi rỗng thì ta gán lại front=rear=đầu dãy Mô hình hiện thực dãy vòng ▪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ố phần tử ▫ Để 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. ▸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; Mô hình hiện thực dãy vòng Cấu trúc dữ liệu dùng mảng động typedef struct intqueue{ int *queueArr; int maxSize; int count; int front; int rear; } IntQueue; Tạo hàng đợi 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*/ Thêm vào cuối hàng đợi int enqueue(struct intqueue *queue, int datain) { if (queue->count >= queue->maxSize) return 0; (queue->count)++; queue->rear = (queue->rear + 1) % queue- >maxSize; queue->queueAry[queue->rear] = datain; return 1; } Xóa ở đầu hàng đợi 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; } Lấy phần tử đầu int Front(struct intqueue *queue,int *dOutPtr) { if(!queue->count) return 0; else{ *dOutPtr= queue->queueAry[queue->front]; return 1; } } Lấy phần tử cuối int Rear(struct intqueue *queue,int*dOutPtr) { if(!queue->count) return 0; else{ *daOutPtr= queue->queueAry[queue->rear]; return 1; } } Kiểm tra rỗng và đầy ▪ Empty int isEmpty(struct intqueue *queue) { return(queue->count == 0); } ▪ Full int isFull(struct intqueue *queue) { return( queue->count == queue->maxSize); } Xóa hàng đợi struct intqueue *destroyQueue(struct intqueue *queue) { if(queue) { free(queue->queueAry); free(queue); } return NULL; } 5. Cây Tree Cây Tree ▪ Nhược điểm của danh sách: Tính tuần tự, chỉ thể hiện được các mối quan hệ tuyến tính. ▪ Cây được sử dụng để lưu trữ các thông tin phi tuyến như ▫ Các thư mục file ▫ Các bước di chuyển của các quân cờ ▫ Sơ đồ nhân sự của tổ chức ▫ Cây phả hệ Cây Tree Một cây (tree) gồm một tập hữu hạn các nút (node) và 1 tập hữu hạn các cành (branch) nối giữa các nút. Định nghĩa đệ quy Một cây là tập các nút o là tập rỗng, hoặc o có 1 nút gọi là nút gốc có 0 hoặc nhiều cây con, các cây con cũng là cây Biểu diễn cây Các khái niệm cơ bản ▪ Cạnh đi vào nút gọi là cành vào (indegree), cành đi ra khỏi nút gọi là cành ra (outdegree). ▪ Số cạnh ra tại một nút gọi là bậc (degree) của 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ác nút còn lại, mỗi nút phải có chính xác 1 cành vào. Tất cả các nút đều có thể có 0,1 hoặc nhiều cành ra Các khái niệm cơ bản Cây con Đường đi Độ sâu và chiều cao Cấp Cây nhị phân ▪ Mỗi nút có nhiều nhất 2 nút con: Nút trái và nút phải ▪ Một tập các nút T được gọi là cây nhị phân, nếu : a) Nó là cây rỗng, hoặc b) Gồm 3 tập con không trùng nhau: 1) Một nút gốc 2) Cây nhị phân con trái 3) Cây nhị phân con phải Cây nhị phân đầy đủ và cây nhị phân hoàn chỉnh ▪Cây nhị phân đầy đủ ▫Cây nút trừ nút lá có cấp bằng 2 ▪Cây nhị phân hoàn chỉnh ▫Tất cả các nút lá có cùng độ sâu và tất cả các nút giữa có cấp bằng 2 Cây cân bằng ▪ 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. ▪ 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 Lưu trữ cây nhị phân ▪ Lưu trữ kế tiếp: Sử dụng mảng ▪ Lưu trữ móc nối: Sử dụng con trỏ Cấu trúc dữ liệu dùng mảng typedef struct tree_node { int data ; struct tree_node *left ; struct tree_node *right ; }TREE_NODE; Tạo cây nhị phân TREE_NODE *root, *leftChild, *rightChild; // Tạo nút con trái leftChild= (TREE_NODE *)malloc(sizeof(TREE_NODE)); leftChild->data = 20; leftChild->left = leftChild->right = NULL; // Tạo nút con phải rightChild = (TREE_NODE *)malloc(sizeof(TREE_NODE)); rightChild->data = 30; rightChild->left = rightChild->right = NULL; // Tạo nút gốc root = (TREE_NODE *)malloc(sizeof(TREE_NODE)); root->data = 10; root->left = leftChild; root->right = rightChild; root->data= 50;// gán 50 cho root Duyệt cây nhị phân ▪ Duyệt theo thứ tự trước ▪ Duyệt theo thứ tự giữa ▪ Duyệt theo thứ tự sau Duyệt theo thứ tự trước 1. Thăm nút. 2. Duyệt cây con trái theo thứ tự trước. 3. Duyệt cây con phải theo thứ tự trước. Duyệt theo thứ tự giữa 1. Duyệt cây con trái theo thứ tự giữa 2. Thăm nút. 3. Duyệt cây con phải theo thứ tự giữa. 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 Duyệt theo thứ tự trước void Preorder(TREE_NODE *root) { if (root != NULL) { // tham node printf("%d", root->data); // duyet cay con trai Preorder(root->left); // duyet cay con phai Preorder(root->right); } } Ứng dụng của duyệt cây 1. Tính độ cao của cây 2. Đếm số nút lá trong cây 3. Tính kích thước của cây (số nút) 4. Sao chép cây 5. Xóa cây Tính độ cao của cây int Height(TREE_NODE *tree) { Int heightLeft, heightRight, heightval; if( tree== NULL ) heightval= -1; 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; } Đếm số nút lá int CountLeaf(TREE_NODE *tree) { if (tree == NULL) return 0; int count = 0; //Đếm theo thứ tự sau count += CountLeaf(tree->left);// Đếm trái count += CountLeaf(tree->right);//Đếm phải //nếu nút tree là nút lá, tăng count if(tree->left == NULL && tree->right == NULL) count++; return count; } Tính kích thước int TreeSize(TREE_NODE *tree) { if(tree== NULL) return 0; else return( TreeSize(tree->left) + TreeSize(tree->right) + 1 ); } Sao chép cây Sao chép cây TREE_NODE *CopyTree(TREE_NODE *tree) { // Dừng đệ quy khi cây rỗng if (tree== NULL) return NULL; TREE_NODE *leftsub, *rightsub, *newnode; leftsub=CopyTree(tree->left); rightsub= CopyTree(tree->right); // tạo cây mới newnode= malloc(sizeof(TREE_NODE)); newnode->data = tree->data; newnode->left = leftsub; newnode->right = rightsub; return newnode; } 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); } } Ứng dụng của cây nhị phân ▪ Cây biểu diễn biểu thức ▫ Tính giá trị biểu thức ▫ Tính đạo hàm ▪ Cây quyết định 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 Cây biểu diễn biểu thức ▪ 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. Cây biểu diễn biểu thức ▪ Dễ dàng để tạo ra các biểu thức tiền tố, trung tố, hậu tố ▪ Trung tố: ( ( 8 -5 ) * ( ( 4 + 2 ) / 3 ) ) ▪ Tiền tố: * -8 5 / + 4 2 3 ▪ Hậu tố: 8 5 -4 2 + 3 / * (thực chất là các phép duyệt theo thứ tự giữa, trước và sau) 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 }; ▪ InfoNode có 2 dạng enum OpType { OPERATOR, OPERAND } ; struct InfoNode { OpType whichType; union // ANONYMOUS union { char operator; int operand ; } }; Cài đặt cây biểu thức int Eval(TreeNode* ptr){ switch(ptr->info.whichType) { case OPERAND : return ptr->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) ) ; } } } Cài đặt cây biểu thức Cây tổng quát ▪ Biểu diễn giống như cây nhị phân? ▫ Mỗi nút sẽ chứa giá trị và các con trỏ trỏ đến các nút con của nó? ▫ Bao nhiêu con trỏ cho một nút? ▪ Mỗi nút sẽ chứa giá trị và một con trỏ trỏ đến một “tập” các nút con ▫ Xây dựng “tập”? Không hợp lý ▪ Mỗ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ỏ trỏ đến nút anh em kề với nó Cây tổng quát Ví dụ Cây tổng quát Duyệt cây tổng quát ▪ 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 ▪ 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 ▪ 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 Ứng dụng Cây quyết định ▪ Dùng để biểu diễn lời giải của bài toán cần quyết định lựa chọn ▪ Bài toán 8 đồng tiền vàng: ▫ Có 8 đồng tiền vàng a, b, c, d, e, f, g, h ▫ Có một đồng có trọng lượng không chuẩn ▫ Sử dụng một cân Roberval (2 đĩa) ▫ Output: ▸Đồng tiền k chuẩn là nặng hơn hay nhẹ hơn ▸ Số phép cân là ít nhất Cây quyết định void EightCoins(a, b, c, d, e, f, g, h) { if (a+b+c == d+e+f) { if (g > h) Compare(g, h, a); else Compare(h, g, a); } else if (a+b+c > d+e+f){ if (a+d == b+e) Compare(c, f, a); else if (a+d > b+e) Compare(a, e, b); else Compare(b, d, a); } else{ if (a+d == b+e) Compare(f,c,a); else if (a+d > b+e) Compare(d, b, a); else Compare(e, a, b); } } // so sánh x với đồng tiền chuẩn z void Compare(x,y,z){ if(x>y) printf(“x nặng”); else printf(“y nhẹ”); } Thanks! Any questions? Email me at trungtt@soict.hust.edu.vn Presentation template by SlidesCarnival