Trịnh Thành Trung (ThS) trungtt@soict.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 Mô tả Cấu trúc Các dữ liệu cấu thành dữ liệu Mối liên kết về mặt cấu trúc giữa các dữ liệu đó là cách tổ chức và thao tác Cung cấp các thao tác có hệ thống trên dữ liệu trên dữ liệu đó Đặc trưng cho 1 kiểu dữ liệu 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' array Basic Data Structures High-Level Data Structures stack queue list hash table tree Các kiểu dữ liệu Kiểu dữ liệu cơ bản Kiểu dữ liệu có cấu trúc (primitive 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ể kiểu dữ liệu (cơ bản, có phân chia nhỏ hơn được cấu trúc) khác nữa ▪Có thể được các ngôn ▪Thường được các ngôn ngữ lập trình định nghĩa ngữ lập trình định nghĩa sẵn hoặc do lập trình viên sẵn tự định nghĩa ▪Ví dụ ▫C/C++: int, long, char, bool. ▫Thao tác trên các số nguyên: + - * /. 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.
Khai báo rồi gán giá trị cho từng phần tử của mảng. 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’) 0 1 2 3 4 5 6 7 8 9 z a b c d e f g h count=9 count=8 Thêm 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 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 Xóa 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 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 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 INFO N L E X T ▪ 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 ? 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 ? Thêm nút 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 < 0 hoặc > độ dài của danh sách, không thêm được. Tìm nút thứ index – currNode 2.
Móc nối nút mới vào danh sách newNode->next = currNode->next; currNode->next = newNode; Thêm Node *InsertNode(Node **head,int index,int x) nút { if (index < 0) return NULL; Tìm nút thứ index, nếu không tìm int currIndex = 1; được trả về NULL 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; Tạo nút mới if (index == 0) { newNode->next = *head; Thêm vào đầu ds *head = newNode; } else { Thêm vào sau currNode newNode->next = currNode->next; currNode->next = newNode; } return newNode; } 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 Xóa int DeleteNode(Node **head, int x) { Node *prevNode = NULL; nút Node *currNode = *head; Tìm nút có giá trị = x int currIndex = 1; while (currNode && currNode->data != x) { prevNode = currNode; currNode = currNode->next; currIndex++; } if (currNode) { Xóa nút ở giữa if (prevNode) { prevNode->next = currNode->next; free (currNode); } else { *head = currNode->next; free (currNode); } Xóa nút head 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 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ử.
