Kỹ thuật lập trình - Bài 5: Cấu trúc dữ liệu

126 trang vanle 2100

Download

Bạn đang xem 20 trang mẫu của tài liệu "Kỹ thuật lập trình - Bài 5: Cấu trúc dữ liệu", để 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:

ky_thuat_lap_trinh_bai_5_cau_truc_du_lieu.pdf

Nội dung text: Kỹ thuật lập trình - Bài 5: Cấu trúc dữ liệu

MỞ ĐẦU • Các bài tốn thực tế thường phức tạp • Hiểu bài tốn đặt ra = để giải quyết bài tốn, cần làm gì, khơng cần làm gì. Do đĩ, phải xác định được: Các dữ liệu liên quan đến bài tốn Các thao tác cần thiết để giải quyết bài tốn © Copyright Showeet.com -
Ví dụ: Bài tốn quản lý nhân viên của một cơ quan • Cần quản lý những thơng tin • Cần thực hiện những thao nào ? tác quản lý nào ? – Thơng tin về nhân viên: – Tạo ra hồ sơ cho nhân tên, ngày sinh, số bảo viên mới vào làm hiểm xã hội, phịng ban – Cập nhật một số thơng làm việc, nhân viên tin trong hồ sơ ảo – Tìm kiếm thơng tin về 1 – nhân viên – • Ai được phép thực hiện © Copyright Showeet.com thao tác nào?
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 • 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 © Copyright Showeet.com
Kiểu dữ liệu • Kiểu dữ liệu cơ bản (primitive • Kiểu dữ liệu cĩ cấu trúc data type) (structured data type) – Đại diện cho các dữ liệu – Được xây dựng từ các giống nhau, khơng thể phân kiểu dữ liệu (cơ bản, cĩ chia nhỏ hơn được nữa cấu trúc) khác – Thường được các ngơn ngữ – Cĩ thể được các ngơn lập trình định nghĩa sẵn ngữ lập trình định nghĩa – Ví dụ: sẵn hoặc do lập trình • C/C++: int, long, char, boolean, viên tự định nghĩa © Copyright Showeet.com v.v. • Thao tác trên các số nguyê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 © Copyright Showeet.com High-Level Data Structures stack queue list hash table tree
Danh sách • 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 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ế © Copyright Showeet.com 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
Danh sách • Thao tác trên danh sách tuyến tính – 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) © Copyright Showeet.com – 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 để 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ỉ © Copyright Showeet.com đượ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 của cách lưu trữ kế tiếp – Tốc độ truy cập vào các phần tử của danh sách nhanh • Nhược điểm của cách lưu trữ kế tiếp – Cần phải biết trước kích thước tối đa của danh sách • Tại sao? – Thực hiện các phép tốn bổ sung các phần tử © Copyright Showeet.com mới và loại bỏ các phần tử cũ khá tốn kém • Tại sao?
Thêm một phần tử vào 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’) © Copyright Showeet.com 0 1 2 3 4 5 6 7 8 9 z a b c d e f g h count=9count=8
Thêm một phần tử vào danh sách kế tiếp 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 ngồ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 © Copyright Showeet.com return success; End Insert
Xĩa một 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=7 © Copyright Showeet.com
Xĩa một phần tử 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 ngồ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] © Copyright Showeet.com return success; End Remove
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 © Copyright Showeet.com
Danh sách nối đơn INFO N L E • Một phần tử trong danh X sách bằng một nút T • Quy cách của 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 • Để thao tác được trên danh sách, cần nắm được địa chỉ của nút © Copyright Showeet.com đầu tiên trong danh sách, tức là biết được con trỏ L trỏ tới đầu danh sách
Tổ chức danh sách mĩc nối • 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));{ © Copyright Showeet.com • Giải phĩng nút: free(p);
Khởi tạo và truy cập danh sách mĩc nối • 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. • Tham chiếu đến các thành phần của một nút trỏ bởi p – INFO(p) – NEXT(p) • 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 © Copyright Showeet.com 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 tồ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) © Copyright Showeet.com
Tìm nút int FindNode(intx) • {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; © Copyright Showeet.com else return 0; }
Thêm một nút mới • 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 (TH1 và TH2) © Copyright Showeet.com – Thêm vào giữa hoặc cuối danh sách (TH3 và TH4 )
Thêm một nút mới {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 (Ví dụ,khi index = 0, nút được thêm là phần tử đầu danh sách; khi index = 1, chèn nút mới vào sau nút đầu tiên,v.v) • 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 © Copyright Showeet.com newNode->next = currNode->next; currNode->next = newNode;
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 > 0 && currNode== NULL) return NULL; Tạo nút mới Node *newNode = (Node *) malloc(sizeof(Node)); newNode->data = x; if (index == 0) { Thêm vào đầu ds newNode->next = head; head = newNode; } © Copyright Showeet.com else { newNode->next = currNode->next; Thêm vào sau currNode currNode->next = newNode; } return newNode; }
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 © Copyright Showeet.com • 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; Tìm nút cĩ giá trị = x currIndex++; } if (currNode) { Xĩa nút ở giữa if (prevNode) { prevNode->next = currNode->next; free (currNode); } else { head = currNode->next; Xĩa nút head free (currNode); © Copyright Showeet.com } return currIndex; } return 0; }
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 tồ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; } © Copyright Showeet.com }
So sánh 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 © Copyright Showeet.com 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 © Copyright Showeet.com
• 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; © Copyright Showeet.com struct Node *next; struct Node *prev; } Node;
• 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; © Copyright Showeet.com • 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);
• 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? © Copyright Showeet.com
Xĩa 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); } } © Copyright Showeet.com
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; © Copyright Showeet.com Cur->prev= New; (New->prev)->next = New; }
Bài tập Sử dụng danh sách mĩc nối kép với nút đầu giả, xây dựng bài tốn quản lý điểm SV đơn giản, với các chức năng sau : 1. Nhập dữ liệu vào danh sách 2. Hiển thị dữ liệu 1 lớp theo thứ tự tên 3. Sắp xếp dữ liệu 4. Tìm kiếm kết quả Với thơng tin về mỗi sinh viên được định nghĩa trong cấu trúc sau typedef struct { int masv; // mã hiệu sv char malop[12]; char ho[30]; char ten[30]; © Copyright Showeet.com float diemk1; float diemk2; } sinhvien
Ngăn xếp • {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ắt buộc phải cùng được thực hiện tại một đầu duy nhất (đỉnh) © Copyright Showeet.com
• {Push – Thêm một phần tử – Tràn (overflow) • {Pop – Xĩa một phần tử – Underflow • {Top – Phần tử đỉnh – stack rỗng • {Kiểm tra rỗng/đầy © Copyright Showeet.com Các thao tác cơ bản trên Stack
Lưu trữ Stack 2 cách lưu trữ: – {Lưu trữ kế tiếp: sử dụng mảng © Copyright Showeet.com – {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 /* 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; © Copyright Showeet.com
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 ; © Copyright Showeet.com }
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; } © Copyright Showeet.com
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; } © Copyright Showeet.com
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); © Copyright Showeet.com }
Ứng dụng của Stack {Bài tố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 + 0 1 0 •2 + 1 •2 = 1101012 © Copyright Showeet.com
Đầ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 © Copyright Showeet.com
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 © Copyright Showeet.com
Đổ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ả © Copyright Showeet.com printf(“%c”, digitChar[n]); } }
Ứ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 tốn 2 ngơi: Mỗi tốn tử được đặt giữa hai tốn hạng. Với phép tốn một ngơi: Tốn tử được đặt trước tố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 © Copyright Showeet.com
Ký pháp hậu tố Là giải pháp thay thế ký pháp trung tố, trong đĩ : Tốn hạng đặt trước tố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) => © Copyright Showeet.com xy*z*x2^y2*z3^ –/ –1z/+xy –*
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 * © Copyright Showeet.com - 4 - 4 11 - 7 7
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ả • Với : - Tốn hạng: Là các số nguyên khơng âm một chữ số (cho đơn giản ) - Tốn tử: + , - , * , / , % , ^ © Copyright Showeet.com
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; } © Copyright Showeet.com
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 tốn hạng vào stack else if (isOperator(ch)) { // rút stack 2 lần để lấy 2 tố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 tốn hạng hoặc tốn tử printf(“Bieu thuc loi”); } // Kết thúc tính tốn, giá trị biểu thức nằm trên đỉnh stack, đưa vào kq © Copyright Showeet.com PopStack(stack, kq); Return kq; }
Bài tập • Sửa chương trình trên để tính tốn kết quả của 1 biểu thức hậu tố với các tố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 tốn hạng tổng quát và các phép tốn cùng độ ưu tiên như sau : () > ^ > * = % = / > + = – © Copyright Showeet.com
Hàng đợi • Hàng đợi – 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. • Queue là một kiểu cấu trúc FIFO: First In First Out © Copyright Showeet.com
• 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. © Copyright Showeet.com
Các phương án thực hiện hàng • Mơ hình vật lý – Cĩ thể dùng 1 mảng. Tuy nhiên, cần phải nắm giữ cả front và rear. – Một cách đơn giản là ta luơn giữ front luơn là vị trí đầu của dãy. Lúc đĩ nếu thêm phần tử vào hàng ta chỉ việc thêm vào cuối dãy. Nhưng nếu lấy ra 1 phần tử ta phải dịch chuyển tất cả các phần tử của dãy lên 1 vị trí. – Mặc dù cách làm này rất giống với hình ảnh hàng đợi trong thực tế, nhưng lại là 1 lựa chọn rất dở với máy tính • Hiện thực tuyến tính – Ta 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ử. – Khi thêm ta chỉ việc tăng rear lên 1 và thêm phần tử vào vị trí đĩ – Khi rút phần tử ra, ta 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ớ – Cĩ thể cải tiến bằng cách khi hàng đợi rỗng thì ta gán lại front=rear= đầu dãy © Copyright Showeet.com
• 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ố 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. Đ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; © Copyright Showeet.com Hoặc i = (i+1) % max;
Các thao tác cơ bản với Queue • {Enqueue–Thêm một phần tử vào cuối queue – {Tràn Overflow? • {Dequeue–Xĩa một phần tử tại đầu queue – {Queue rỗng? • {Front –Trả lại phần tử tại đầu queue – {Queue rỗng? • {Rear –Trả lại phần tử tại cuối queue © Copyright Showeet.com – {Queue rỗng
Định nghĩa cấu trúc Queue typedef struct intqueue{ int *queueArr; int maxSize; int count; int front; int rear; } IntQueue; © Copyright Showeet.com
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; © Copyright Showeet.com return queue; } /* createQueue*/
Thêm vào cuối Queue • Enqueue 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; © Copyright Showeet.com return 1; }
Xĩa ở đầu queue • Dequeue 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; © Copyright Showeet.com return 1; }
Lấy phần tử đầu queue • Front int Front(struct intqueue *queue,int *dOutPtr) { if(!queue->count) return 0; else{ *dOutPtr= queue->queueAry[queue->front]; return 1; © Copyright Showeet.com } }
Lấy phần tử cuối queue • Rear int Rear(struct intqueue *queue,int*dOutPtr) { if(!queue->count) return 0; else{ *daOutPtr= queue->queueAry[queue->rear]; return 1; © Copyright Showeet.com } }
Kiểm tra empty và full • Empty int emptyQueue(struct intqueue *queue) { return(queue->count == 0); }/* emptyQueue*/ • Full int fullQueue(struct intqueue *queue) { © Copyright Showeet.com return( queue->count == queue->maxSize); }/* fullQueue*/
Xĩa queue • Destroy struct intqueue *destroyQueue(struct intqueue *queue) { if(queue) { free(queue->queueAry); free(queue); } © Copyright Showeet.com return NULL; }/* destroyQueue*/
Cây 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 © Copyright Showeet.com – Cây biểu diễn biểu thức (tính giá trị, tính đạo hàm) – Cây quyết định
Định nghĩa cây • So với cấu trúc liên tục như mảng, danh sách cĩ ưu điểm vượt trội về tính mềm dẻo • Nhưng nhược điểm lớn của danh sách là tính tuần tự và chỉ thể hiện được các mối quan hệ tuyến tính. • Thơng tin cịn cĩ thể cĩ quan hệ dạng phi tuyến, vídụ: – {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ệ • {Sử dụng cây cho phép tìm kiếm thơng tin nhanh © Copyright Showeet.com
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á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. 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 • Định nghĩa: Một cây là tập các nút mà : - là tập rỗng, hoặc © Copyright Showeet.com - 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
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 © Copyright Showeet.com
Cây nhị phân đầy đủ và cây nhị phân hồn chỉnh • Cây nhị phân đầy đủ • Cây nhị phân hồn chỉnh – Cây nút hoặc nút lá cĩ – Tất cả các nút lá cĩ cấp bằng 2 cùng độ sâu và tất cả các nút giữa cĩ cấp bằng 2 © Copyright Showeet.com
Một số tính chất • Số nút tối đa cĩ độ sâu i : 2i • Gọi N là số nút của cây nhị phân, H là chiều cao của cây thì, – Hmax = N, Hmin = [log2N] +1 – Nmin = H, Nmax = 2H-1 © Copyright Showeet.com
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. Đ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 © Copyright Showeet.com cân bằng
Cấu trúc cây nhị phân typedef structtree_node { int data ; structtree_node *left ; structtree_node *right ; }TREE_NODE; © Copyright Showeet.com
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; © Copyright Showeet.com root->left = leftChild; root->right = rightChild; root -> data= 50;// gán 50 cho root
Duyệt cây nhị phân • {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. © Copyright Showeet.com
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. © Copyright Showeet.com
• 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 © Copyright Showeet.com
• 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. © Copyright Showeet.com
• 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 © Copyright Showeet.com • Thứ tự sau: 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15
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); } } • Bài tập: Viết giải thuật đệ quy của © Copyright Showeet.com – {Duyệt theo thứ tự giữa – {Duyệt theo thứ tự sau
Duyệt theo thứ tự trước • Dùng vịng lặp void Preorder_iter(TREE_NODE *treeRoot) { 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 © Copyright Showeet.com popStack(stack, &curr);// duyệt cây con phải } destroyStack(&stack);// giải phĩng stack }
Duyệt theo thứ tự giữa void Inorder_iter(TREE_NODE *root) { TREE_NODE *curr= root; STACK *stack= createStack(MAX);//ktạo stack while(curr != NULL || !IsEmpty(stack)) { if (curr==NULL) { popStack(stack, &curr); printf(“%d”, curr->data); curr= curr->right; } else { pushStack(stack, curr); curr= curr->left; // duyệt cây con trái } } © Copyright Showeet.com destroyStack(stack); //giải phĩng stack }
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; © Copyright Showeet.com } } destroyStack(&stack);// giải phĩng stack }
Một vài ứ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 © Copyright Showeet.com
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); } © Copyright Showeet.com 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++; © Copyright Showeet.com return count; }
Kích thước của cây int TreeSize(TREE_NODE *tree) { if(tree== NULL) return 0; else return( TreeSize(tree->left) + TreeSize(tree->right) + 1 ); } © Copyright Showeet.com
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; © Copyright Showeet.com 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); © Copyright Showeet.com } }
Ứ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 © Copyright Showeet.com
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 tốn hạng 2. Mỗi nút giữa chứa một tốn tử 3. Cây con trái và phải của một nút tốn tử thể hiện các biểu thức con cần được đánh giá trước khi thực hiện tốn tử tại nút gốc © Copyright Showeet.com
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 tốn tại mức cao hơn sẽ được tính sau các các phép tốn cĩ mức thấp. – Phép tốn tại gốc luơn được thực hiện cuối © Copyright Showeet.com 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 © Copyright Showeet.com • Hậu tố: 8 5 -4 2 + 3 / * (thực chất là các phép duyệt theo tt 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 }; © Copyright Showeet.com
• InfoNode cĩ 2 dạng enum OpType { OPERATOR, OPERAND } ; struct InfoNode { OpType whichType; union // ANONYMOUS union { char operator; int operand ; } }; © Copyright Showeet.com
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 ) ) ; } } } © Copyright Showeet.com
Cây tổng quát Biểu diễn 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? -> Khơng hợp lý • 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 © Copyright Showeet.com – Xây dựng “tập” như thế nào?
• Sử dụng con trỏ nhưng mở rộng hơn: – {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ỏ 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 © Copyright Showeet.com Biểu diễn 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 © Copyright Showeet.com 2. Duyệt các cây con cịn lại theo thứ tự sau 3. Thăm gốc
Cây quyết định • Dùng để biểu diễn lời giải của bài tốn cần quyết định lựa chọn • Bài tố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 © Copyright Showeet.com • Số phép cân là ít nhất
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); } } © Copyright Showeet.com // 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ẹ”); }