Mở đầu • Các bài toán thực tế thường phức tạp • Hiểu bài toán đặt ra == để giải quyết bài toá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 toán Các thao tác cần thiết để giải quyết bài toán Ví dụ: Bài toán quản lý nhân viên của một cơ quan • Cần quản lý những • Cần thực hiện những thao tác quản lý nào ? thông tin nào ? – Tạo ra hồ sơ cho nhân – Thông tin về nhân viên mới vào làm viên: tên, ngày – Cập nhật một số thông sinh, số bảo hiểm tin trong hồ sơ xã hội, phòng ban – Tìm kiếm thông tin về làm việc, … 1 nhân viên nhân viên ảo –… –… • Ai được phép thực hiện thao tác nào? 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 • 1 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 1. Các khái niệm cơ bản Kiểu dữ liệu • Kiểu dữ liệu cơ bản • Kiểu dữ liệu có cấu (primitive data type) trúc (structured data – Đại diện cho các dữ type) liệu giống nhau, – Được xây dựng từ các không thể phân chia kiểu dữ liệu (cơ bản, nhỏ hơn được nữa có cấu trúc) khác – Thường được các – Có thể được các ngôn ngôn ngữ lập trình ngữ lập trình định định nghĩa sẵn nghĩa sẵn hoặc do lập – Ví dụ: trình viên tự định • C/C++: int, long, nghĩa char, boolean, v.
• Thao tác trên các số nguyên: + - * /. 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 28 3.1415 'A' Primitive Data Types array Basic Data Structures High-Level Data Structures stack queue list hash table tree II. Cấu trúc dữ liệu • Mang ( bo qua ) • Danh sách • Cây • Bảng băm 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, 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ế 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 1.
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) – 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) 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. 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 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 • Tại sao? 1. 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 count=9 count=8 1.
Thêm một phần tử vào một 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 1.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 h count=7 count=8 1.Xóa 1 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 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 1. Danh sách nối đơn • Một phần tử trong INFO N danh sách = một L E X 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 đầ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 node { int 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 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 – 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) 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) – Thêm vào giữa hoặc cuối danh sách(TH3 và TH4 ) 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; Thêm một nút vào đầu danh sách newNode= malloc(sizeof(Node)); newNode->data = 13; newNode->next = Head; Head = newNode; 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; 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ạiNULL. • (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 một nút mới Node * InsertNode(Node *head,int index,int x) { if (index < 0) return NULL; int currIndex = 1; Tìm nút thứ index, nếu Node *currNode = head; Không tìm được trả về while(currNode && 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) { 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; } 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; else return 0; } 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.