Bài giảng Lập trình - Chương 3: Cấu trúc dữ liệu

:
 – Các thành phần DL có trong CTDL đó,
 – Các liên kết (quan hệ) về cấu trúc giữa các thành phần 
 DL. 
 . Bước 2: xác định các thao tác cơ bản trên CTDL: 
 là các thao tác cơ bản, cần thiết nhất để có thể sử 
 dụng được CTDL này. 
 . Bước 3: xác định cấu trúc lưu trữ thích hợp để tổ 
 chức lưu trữ CTDL một cách có hiệu quả. Tính 
 hiệu quả thể hiện ở cả hai mặt: kích thước lưu 
 trữ nhỏ nhất và tốc độ thực hiện các thao tác là 
 nhanh nhất. 
Chương 3: Cấu trúc dữ liệu 59
 Các bước xây dựng một CTDL
 . Bước 4: Cài đặt các thao tác cơ bản. Việc cài đặt các 
 thao tác phải theo một số nguyên tắc sau:
 – Thao tác có khả năng sử dụng lại nhiều lần: sử dụng chương 
 trình con để cài đặt
 – Thao tác có tính độc lập về mặt sử dụng và độc lập với các 
 thao tác khác. Để đảm bảo tính chất này thì ta phải chọn các 
 tham số hợp lí cho các thao tác
 – Thao tác phải hiệu quả
Chương 3: Cấu trúc dữ liệu 60
 3. 4 Một số cấu trúc dữ liệu
 . Cấu trúc tuyến tính : 
 – Mảng
 – Danh sách: LIFO (Stack_ngăn xếp), FIFO (Queue_hàng đợi)
 – Danh sách móc nối (Danh sách liên kết)
 . Cấu trúc phi tuyến:
 – Cây
 – Đồ thị
Chương 3: Cấu trúc dữ liệu 61
 Danh sách liên kết đơn
 . Là tập hợp các phần tử dữ liệu không liên tục được 
 kết nối với nhau thông qua một liên kết (thường là 
 con trỏ)
 . Cho phép ta quản lý bộ nhớ linh động
 . Các phần tử được chèn vào DS và xóa khỏi DS một 
 cách dễ dàng
 . Tại mỗi nút có hai thành phần:
 . Dữ liệu trong nút
 . Con trỏ trỏ đến phần tử kế tiếp
 A B C D
Trong bộ nhớ
 712
 A 800 B C 992 D 0
 1000 800 712 992
 Chương 3: Cấu trúc dữ liệu 62
 Danh sách liên kết đơn()
 . Cú pháp khai báo một phần tử của danh sách liên kết trong C:
 struct Node
 {
 Kieu_PT data;
 Node *next;
 }
 Giải thuật thêm một phần tử vào danh sách liên kết
 . Cấp phát bộ nhớ cho node
 . Đưa số liệu vào node mới
 . Cho node liên kết với danh sách:
 • Thêm vào đầu DS
 • Thêm vào cuối DS
 • Chèn vào giữa DS
Chương 3: Cấu trúc dữ liệu 63
 Danh sách liên kết đơn()
 Thêm vào đầu DS
 Head Tail
 ...
 NewNode
 NULL
 Thêm vào giữa DS Head P
 sau con trỏ P
 ...
 (1) NULL
 (2)
 NewNode
Chương 3: Cấu trúc dữ liệu 64
 Danh sách liên kết đơn ()
 . Thuật toán để duyệt một DS liên kết:
 while(DS !=NULL)
 {
 ... Các thao tác với dữ liệu trên Node
 node=node->next; /* chuyển qua node tiếp theo 
 */
 }
Chương 3: Cấu trúc dữ liệu 65
 Ví dụ:
 . Một ví dụ đơn giản minh họa về cấu trúc list có liên 
 kết một chiều:
 – Mỗi node trong list chỉ chứa một dữ liệu thuộc kiểu int.
 – Hỗ trợ các hàm khởi tạo list, bổ sung phần tử, xóa phần tử 
 đầu list, xóa phần tử sau một phần tử nào đó, bổ sung phần 
 tử sau phần tử nào đó, xóa tất cả các phần tử.
 struct Node{ Liên kết sang 
 int data; Dữ liệu node node tiếp theo
 Node* next;
 };
 firstNode
 0
 struct List{
 Node* firstNode;
 }; list
Chương 3: Cấu trúc dữ liệu 66
 . Các khai báo hàm
 void List_Init(List* list);
 void List_Add(List* l, int data);
 void List_InsertAfter(Node* node, int data);
 void List_RemoveFirst(List* list);
 void List_RemoveAfter(Node* node);
 void List_DeleteAll(List* list);
 int List_Length(List* list);
 void List_Display(List* list)
 Node* List_Search(List* list, int data);
Chương 3: Cấu trúc dữ liệu 67
 . Khởi tạo List: gán con trỏ fistnode = 0
 void List_Init(List* list){
 list->firstNode = 0;
 }
 . Bổ sung phần tử vào đầu của List:
 3
 firstNode
Giải thuật: 0
 newnode
 1
 2
B2: newNode.next := list.firstNode
 list
B3: list.firstNode := newNode 
 void List_Add(List* list, int data){
 Node* newnode = new Node;
 newnode->data = data;
 newnode->next = list->firstNode;
 list->firstNode = newnode;
 }
 Chương 3: Cấu trúc dữ liệu 68
 . Bổ sung vào giữa list, sau một phần tử nào đó
 node
 Giải thuật: firstNode
 0
 . B2: newNode.next := node.next
 list
 3 2
 . B3: node.next := newNode
 newnode
 1
 void List_InsertAfter(Node* node, int data){
 Node* newnode = new Node;
 newnode->data = data;
 newnode->next = node->next;
 node->next = newnode;
 }
Chương 3: Cấu trúc dữ liệu 69
 . Xóa phần tử đầu list
 3
 1
 Giải thuật: firstNode
 0
B1: obsoleteNode := list.firstNode 
 2
B2: list.firstNode := list.firstNode.next 
 B3: destroy obsoleteNode 
 void List_RemoveFirst(List* list){
 Node* obsoleteNode = list->firstNode;
 list->firstNode = list->firstNode->next;
 delete obsoleteNode ;
 }
 Chương 3: Cấu trúc dữ liệu 70
 . Xóa phần tử sau một phần tử nào đó
 3
 1
 Giải thuật: firstNode
 0
- obsoleteNode := node.next node
- node.next := node.next.next 
 2
 - destroy obsoleteNode 
 void List_RemoveAfter(Node* node){
 Node* obsoleteNode = node->next;
 node->next = obsoleteNode ->next;
 delete obsoleteNode ;
 }
Chương 3: Cấu trúc dữ liệu 71
 . Xóa tất cả các phần tử của list
 node := list.firstNode 
 Giải thuật: while node not null { 
 (delete node)
 node := node.next 
 } 
 void List_DeleteAll(List* list){
 Node* node = list->firstNode;
 while (node != 0){
 Node* nextnode = node->next;
 delete node;
 node = nextnode;
 }
 list->firstNode = 0;
 }
Chương 3: Cấu trúc dữ liệu 72
 . Xác định độ dài của list (số phần tử của list)
 int List_Length(List* list){
 Node* node = list->firstNode;
 int i = 0;
 while(node != 0){
 i++;
 node = node->next;
 }
 return i;
 }
Chương 3: Cấu trúc dữ liệu 73
 . Để hỗ trợ kiểm tra kết quả, thực hiện một hàm hiển 
 thị như sau:
void List_Display(List* list){
 Node* node = list->firstNode;
 int i = List_Length(list);
 cout<<"\nDo dai cua list:\t"<<i;
 if (list->firstNode == 0)
 cout<<"\nList rong\r\n";
 else
 {
 while(node != 0){
 coutdata;
 coutdata:\t\t"data;
 coutnext:\t\t"next<<"\n";
 node = node->next;
 i--;
 }
 cout<<endl;
 }
} Chương 3: Cấu trúc dữ liệu 74
 . Hàm tìm kiếm một phần tử: 
 . Mục đích: trả về một phần tử có dữ liệu bằng dữ liệu 
 cho trước
 Node* List_Search(List* list, int data){
 Node* node = list->firstNode;
 while (node != 0){
 if(node->data == data)
 return node;
 else
 node = node->next;
 }
 return 0;
 }
Chương 3: Cấu trúc dữ liệu 75
 . Sử dụng:
void main(){
 List l;
 List_Init(&l);
 List_Display(&l);
 List_Add(&l, 1);//list: 1
 List_Add(&l, 2);//list: 2 1
 cout<<"Noi dung List sau hai lenh List_Add:";
 List_Display(&l);
 cout<<"Noi dung List sau khi them 2 lenh List_Add nua:";
 List_Add(&l, 3);//list: 3 2 1
 List_Add(&l, 4);//list: 4 3 2 1
 List_Display(&l);
 Chương 3: Cấu trúc dữ liệu 76
 cout<<"Noi dung sau khi removefirst:";
 List_RemoveFirst(&l);
 List_Display(&l);
 cout<<"Noi dung sau khi remove node dung sau node co data = 3:";
 List_RemoveAfter(List_Search(&l,3));
 List_Display(&l);
 cout<<"Noi dung sau khi chen node dung sau node co data = 3:";
 List_InsertAfter(List_Search(&l,3),100);
 List_Display(&l);
 cout<<"Noi dung sau khi xoa tat ca:";
 List_DeleteAll(&l);
 List_Display(&l);
 }
Chương 3: Cấu trúc dữ liệu 77
 . Kết quả trên mà hình
Chương 3: Cấu trúc dữ liệu 78
Chương 3: Cấu trúc dữ liệu
 Danh sách liên kết đôi
 L R
 A1 A2 A3
 LPTR INFO RPTR
 . Sử dụng 2 con trỏ, giúp ta luôn xem xét được cả 2 
 chiều của danh sách
 . Tốn bộ nhớ nhiều hơn
 . Con trỏ trái (LPTR): trỏ tới thành phần bên trái (phía 
 trước)
 . Con trỏ phải (RPTR): trỏ tới thành phần bên phải 
 (phía sau)
Chương 3: Cấu trúc dữ liệu 80
Bài tập về nhà
 Thực hiện một cấu trúc list quản lý sinh viên. Thông 
 tin về sinh viên được biểu diễn bởi một struct gồm mã 
 sinh viên (int), họ tên sinh viên (string), lớp (string). 
 Chương trình có chức năng:
 -Nhập thông tin sinh viên từ bàn phím
 -Thêm sinh viên vào cuối danh sách
 -Hiển thị danh sách sinh viên
 -Tìm sinh viên theo tên
 -Xóa sinh viên theo tên
 Viết hàm main minh họa cách sử dụng
Chương 3: Cấu trúc dữ liệu 81
 Ngăn xếp (Stack-LIFO)
. Là tập hợp các phần tử có trình 
 tự, các phần tử vào/ra ngăn xếp 
 gọi là “đỉnh ngăn xếp” (stack-top)
. Các phần tử vào ra theo nguyên push pop, top
 tắc LIFO (Last In First Out)
. Các thao tác cơ bản: push, pop, con trỏ 
 top, hàm khởi tạo stack initialize(), hàm 
 kiểm tra stack có rỗng hay không Stack
 isEmpty() 
. Để xây dựng ngăn xếp có thể 
 dùng:
 – Mảng kết hợp với một biến nguyên 
 “top” lưu vị trí tên cùng của ngăn xếp
 – Danh sách liên kết với thuật toán 
 chèn/xóa ở đầu của danh sách.
 Chương 3: Cấu trúc dữ liệu 82
 Ứng dụng của stack
 . Đổi cơ số: VD từ 10 sang 2
 . Cách làm: ta chia liên tiếp cho 2 và lấy các số dư theo 
 chiều ngược lại
 Số 26 cơ số 10 chuyển sang cơ số 2 1
 1 1
 PUSH 0 0 0
 1 1 1 1
 0 0 0 0 0
 1
 POP 0 0
 1 1 1
 0 0 0 0
 1 1 0 1 0
Chương 3: Cấu trúc dữ liệu 83
 Ứng dụng của stack (...)
 . Định giá trị biểu thức theo phương pháp nghịch đảo Balan
 Ví dụ: tính biểu thức 13 – 2 * (5 * 2 – 4)
 •Khái niệm infix, postfix, prefix
 –infix:3 + 4 postfix: 3 4 + prefix: + 3 4
 –infix:2 + 3 * 4 postfix: 2 3 4 * + prefix: + 2 * 3 4
 –infix:2 * 3 + 4 postfix: 2 3 * 4 + prefix: + * 2 3 4
 •Ứng dụng hậu tố (postfix) vào ví dụ
 •13 2 5 2 * 4 -* -
 •Đọc từ trái qua phải
 •Nếu là số: PUSH vào Stack
 •Nếu là phép tính (operator) thì lấy số (POP) trong Stack ra, 
 tính toán rồi lại PUSH vào
Chương 3: Cấu trúc dữ liệu 84
 Ứng dụng của stack (...)
 . Ví dụ: tính biểu thức 13 – 2 * (5 * 2 – 4)
 . Biểu diễn dưới dạng hậu tố: 13 2 5 2 * 4 - * -
 2 5 2 * 4 -* - PUSH 13
 5 2 * 4 -* - PUSH 2
 13 .
 .
 .
 * 4 -* - 2
 5 POP 5 * 2 = 10
 2
 13
 10
 4 -* -
 2 PUSH
 13
Chương 3: Cấu trúc dữ liệu 85
 Ứng dụng của stack (...)
 . Ví dụ: tính biểu thức 13 – 2 * (5 * 2 – 4) (tiếp...)
 -* - PUSH 4
 10 POP 10 - 4 = 6
 2
 13
 PUSH
 6
 * -
 2
 2 * 6 = 12
 13 POP
 PUSH
 - 12
 13 - 12 = 1
 13 POP
 PUSH
 1 POP 1
Chương 3: Cấu trúc dữ liệu 86
 Ví dụ: Đổi cơ số dùng stack
 #include 
 using namespace std;
 struct Node
 {
 int data;
 Node *next;
 };
 struct Stack
 {
 Node *top;
 };
 void Khoi_Tao(Stack &s)
 {
 s.top =NULL;
 }
Chương 3: Cấu trúc dữ liệu 87
 void Push(Stack &s,int pt)
 {
 Node *tmp= new Node;
 tmp->data =pt;
 if(s.top ==NULL) /* Phan tu dau tien */
 { 
 s.top =tmp;
 s.top->next =NULL; 
 }
 else /* Phan tu tiep theo */
 {
 tmp->next =s.top;
 s.top =tmp;
 }
 }
Chương 3: Cấu trúc dữ liệu 88
 bool isEmpty(Stack s)
 {
 return (s.top==NULL); 
 }
 void Pop(Stack &s,int &pt)
 {
 if (!isEmpty(s))
 {
 pt=s.top->data ;
 s.top=s.top->next ;
 }
 }
Chương 3: Cấu trúc dữ liệu 89
 void main() /* Quy doi co so 10 ra nhi phan */
 {
 Stack S;
 Khoi_Tao(S);
 int a,pt;
 cout<<"Nhap vao so he 10:\n”;
 cin>>a;
 while((a/2)>0)
 {
 Push(S,a%2);
 a=a/2;
 }
 Push(S,a);
 cout<<"Bieu dien duoi dang nhi phan:\n";
 while(!isEmpty(S))
 {
 Pop(S,pt);
 cout<<pt;
 }
 cout<<"\n";
 }
Chương 3: Cấu trúc dữ liệu 90
 Cây nhị phân (Binary Tree)
 . Mô tả cây nhị phân và các khái niệm cơ bản
 – Cây có thứ tự và là cây cấp hai, tức là mỗi nút có tối đa 2 
 con. 
 – Hai con của một nút được phân biệt thứ tự và quy ước nút 
 trước gọi là nút con trái và nút sau được gọi là nút con phải
 . Khi biểu diễn cây nhị phân, ta cũng cần có sự phân biệt rõ 
 ràng giữa con trái và con phải, nhất là khi nút chỉ có một 
 con. 1
 . Cây nhị phân có tính chất đệ 
 quy: nếu ta chặt một nhánh 
 2 3
 bất kì của cây nhị phân thì ta 
 sẽ thu được hai cây con cũng 
 đều là cây nhị phân. 4 5 6 7
 8
Chương 3: Cấu trúc dữ liệu 91
 Cây nhị phân (...)
 . Mô tả cây nhị phân và các khái niệm cơ bản
 – Loại nút:
  Nút có đủ hai con được gọi là nút kép: 2, 3
  Nút chỉ có một con gọi là nút đơn: 7
  Nút không có con vẫn được gọi là nút lá: 
 4, 5, 6, 8 1
 Phải
 – Cây con có gốc là nút con trái/phải được (Right)
 gọi là cây con trái/phải. Trái
 (Left)
 2 3
 4 5 6 7
 8
Chương 3: Cấu trúc dữ liệu 92
 Cây nhị phân (...)
 . Các thao tác cơ bản - Giải thuật duyệt cây
 – Phép duyệt cây
  Phép thăm một nút (visit): là thao tác truy nhập vào một 
 nút của cây để xử lý nút đó.
  Phép duyệt (traversal): là phép thăm một cách hệ thống 
 tất cả các nút của cây, mỗi nút đúng một lần. 
 . Có 3 phép duyệt cây thông dụng:
 – Duyệt theo thứ tự trước (preorder traversal) 
 – Duyệt theo thứ tự giữa (inorder traversal) 
 – Duyệt theo thứ tự sau (postorder traversal)
Chương 3: Cấu trúc dữ liệu 93
 Cây nhị phân (...)
 . Các thao tác cơ bản - Giải thuật duyệt cây
 – Giải thuật duyệt theo thứ tự trước (preorder traversal, còn 
 gọi là duyệt cây theo chiều sâu): đây là giải thuật đệ quy
  Trường hợp đệ quy: để duyệt cây nhị phân T, ta theo các 
 bước sau:
 – Thăm gốc
 1
 – Duyệt cây con trái theo thứ tự trước
 – Duyệt cây con phải theo thứ tự trước
  Trường hợp điểm dừng: 
 2
 – Khi cây T rỗng. 3
 7
 VD: 1, 2, 4, 8, 9, 5, 10, 3, 6, 7 4 5 6
 8 9 10
Chương 3: Cấu trúc dữ liệu 94
 Giải thuật duyệt cây (...)
. Giải thuật duyệt theo thứ tự giữa (inorder 
 travelsal): đây là giải thuật đệ quy.
 – Trường hợp đệ quy: để duyệt cây nhị phân T, ta theo các bước 
 sau:
  Duyệt cây con trái theo thứ tự giữa
  Thăm gốc 1
  Duyệt cây con phải theo thứ tự giữa
 – Trường hợp điểm dừng: 
 2
  Khi cây T rỗng. 3
 4 5 6 7
 VD: 8, 4, 9, 2, 10, 5, 1, 6, 3, 7
 8 9 10
Chương 3: Cấu trúc dữ liệu 95
 Giải thuật duyệt cây (...)
. Giải thuật duyệt theo thứ tự sau (postorder 
 travelsal): đây là giải thuật đệ quy.
 – Trường hợp đệ quy: để duyệt cây nhị phân T, ta theo các bước sau:
  Duyệt cây con trái theo thứ tự sau
  Duyệt cây con phải theo thứ tự sau
 1
  Thăm gốc
 – Trường hợp điểm dừng: 
  Khi cây T rỗng. 2 3
 4 5 6 7
 VD: 8, 9, 4, 10, 5, 2, 6, 7, 3, 1
 8 9 10
 Chương 3: Cấu trúc dữ liệu 96
 Cài đặt cây nhị phân
 . Nguyên tắc cài đặt: Sử dụng cấu trúc lưu trữ móc nối
 – Đối với cây nhị phân, ta cần lưu trữ hai thành phần: 
 – Các phần tử (nút) của cấu trúc cây:
  Dùng các nút của CTLT để lưu trữ các phần tử.
 – Các nhánh (quan hệ cha-con) giữa các cặp nút: 
  Sử dụng con trỏ để biểu diễn các nhánh. 
  Do mỗi nút có nhiều nhất hai con nên trong mỗi 
 nút của CTLT ta sẽ có hai con trỏ để trỏ đến tối 
 đa hai con này. 
Chương 3: Cấu trúc dữ liệu 97
 Cài đặt cây nhị phân (...)
. Dùng cấu trúc móc nối
 LP Info RP
 – Cấu tạo mỗi nút (xem hình):
  Trường Info: chứa thông tin về một phần Nút
 tử. 
  Trường LP và RP tương ứng là hai con T
 trỏ sẽ trỏ vào hai nút con trái và con 
 phải. 1
  Nếu không có con thì giá trị con trỏ 
 tương ứng sẽ rỗng (NIL/NULL) 2 3
  Khai báo cấu trúc một nút:
 – Tổ chức cấu trúc cây như sau (xem hình): 4 5 6
  Ít nhất một con trỏ T trỏ vào nút gốc, 
 vừa đại diện cho cây, vừa là điểm truy Cây
 nhập vào các nút khác trong cây. 
  Các thao tác muốn truy nhập vào các nút
 trong cây phải thông qua con trỏ này. 
 Chương 3: Cấu trúc dữ liệu 98