›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Mảng danh sách - Đỗ Tuấn Anh

pdf 68 trang hapham 2900
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Mảng danh sách - Đỗ Tuấn Anh", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_3_mang_danh.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Mảng danh sách - Đỗ Tuấn Anh

  1. Cấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh Email: anhdt@it-hut.edu.vn
  2. Nội dung zChương 1 – Thiết kế và phân tích (5 tiết) zChương 2 – Giải thuật đệ quy (10 tiết) zChương 3 – Mảng và danh sách (5 tiết) zChương 4 – Ngăn xếp và hàng đợi (10 tiết) zChương 5 – Cấu trúc cây (10 tiết) zChương 8 – Tìm kiếm (5 tiết) zChương 7 – Sắp xếp (10 tiết) zChương 6 – Đồ thị (5 tiết)
  3. Chương 3 – Mảng và Danh sách 1. Mảng 2. Danh sách 3. Một số phép toán trên danh sách nối đơn 4. Các dạng khác của danh sách móc nối 5. Sử dụng danh sách móc nối – Ví dụ bài toán cộng đa thức
  4. 1. Mảng zMảng: {Số phần tử cố đinh {Kích thước một phần tử cố định {Các phần tử mảng phải cùng kiểu {Truy cập ngẫu nhiên (theo chỉ số)
  5. Mảng: Số phần tử cốđịnh zKích thướcmảng sau khi khai báo là cốđịnh zVí dụ: void notAllowed (); { int size; int arr[size]; /* không được phép, kích thướcmảng phảilàhằng số xác định*/ printf(“Enter the size of the array: “); scanf(“%d”, &size); }
  6. Cấu trúc lưu trữ của mảng double x[50]; x[0] x[1] x[2] x[3] x[49] addr addr + 49 * sizeof(double) Mảng được lưu trữ kế tiếp => truy cập ngẫu nhiên sử dụng chỉ số => tốc độ truy cập tất cả các phần tử là như nhau
  7. Mảng nhiều chiều double a[5][5]; z Ma trận (mảng 2 chiều) là a[0] a[0][0] a[0][1] a[0][2] a[0][4] một mảng mà mỗi phần tử là một mảng một chiều a[1] a[1][0] a[1][1] z C lưu trữ mảng nhiều chiều theo thứ tự ưu tiên hàng –mỗi phần tử là một hàng a[4][0] a[4][4] a[4] z Mảng nhiều chiều vẫn được lưu trữ kế tiếp như mảng một chiều a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[4][3] a[4][4] addr addr + (i*5+j)*sizeof(double)
  8. 2. Danh sách zDanh sách những người đến khám bệnh {Ban đầu chưa có ai {Có người mới đến {Có người khám xong đi về z(Tạo hình ảnh động tại đây)
  9. Danh sách tuyến tính zMột chuỗi các phần tử zTồn tại phần tử đầu và phần tử cuối zMỗi phần tử có phần tử trước và phần tử sau
  10. Danh sách tuyến tính zSố phần tử biến đổi zMột phần tử thường là một cấu trúc (struct) zThao tác thường xuyên nhất {Thêm phần tử {Xóa phần tử zCác thao tác khác: {Tìm kiếm {Ghép 2 danh sách {Tách 1 danh sách thành nhiều danh sách {Sao chép danh sách {Cập nhật
  11. Phân loại danh sách tuyến tính Nguồn: Data Structures : A Pseudocode Approach With C by Richard F. Gilberg, Behrouz A. Forouzan
  12. Thêm mộtphần tử mới
  13. Tìm một phần tử
  14. Xóa một phần tử khỏi danh sách
  15. Lưu trữ danh sách liên kết 1. Lưu trữ kế tiếp sử dụng mảng 2. Lưu trữ móc nối
  16. 2.1 Danh sách - Lưu trữ kế tiếp zSử dụng mảng 1 chiều zTìm kiếm dễ dàng (tuần tự hoặc tìm kiếm nhị phân) zDuyệt các phần tử dễ dàng sử dụng chỉ số: for(i = 0; i Không biết trước số phần tử
  17. Lưu trữ kế tiếp - Thêm mộtphầntử 123 125 Thêm mộtphầntử thứ i vào 135 mảng 155 - Chuyểncácphầntử i 161 165 i->n xuống các vị trí i+1 166 i+1 ->n+1 167 167 -Thêmphầntử cần 169 thêm vào vị trí thứ i n 177 n+1 178
  18. Lưu trữ kế tiếp - Xóa mộtphầntử 123 Xóa mộtphầntử thứ i khỏi 125 mảng 135 155 - Chuyểncácphầntử i+1->n vào các vị trí i 161 166 i ->n-1 i+1 167 167 n-1 169 177 n 178
  19. Không hiệuquả Việclưutrữ liên tiếp ⇒ thao tác thêm và xóa không hiệuquả (dịch chuyểnphầntử). 7 21 56 43 22 xóa 21 n/2 lầndịch chuyển (trung bình) 7 56 43 22 Thời gian tính: O(n) Thêm 67 sau 56 Các thao tác thêm và xóa có thời 7 56 67 43 22 gian chạylàO(n).
  20. Lưu trữ kế tiếp zƯu điểm: truy cập nhanh (ngẫu nhiên, thời gian truy cậpmọiphầntử là như nhau) zNhược điểm: {Việc thêm, bớtphầntử rấtkhókhăn(phảidịch chuyển nhiềuphầntử khác) {Tốn bộ nhớ, cấp phát nhiều hơn cần thiết để giữ chỗ
  21. 2.2 Danh sách móc nối Head A B C ∅ zMột danh sách móc nối là mộtchuỗicác phần tử, gọi là nút, đượcmócnốivới nhau zMỗi nút phải bao gồm node {Dữ liệu A {Móc nối(địa chỉ) tớinút data next tiếp theo trong danh sách zHead: con trỏ trỏđến nút đầu tiên zNút cuốicùngtrỏđến NULL
  22. Tổ chức danh sách móc nối zNút = dữ liệu + móc nối {Định nghĩa: typedef struct node { int data; struct node *next; }Node; head 15 99 {Tạo nút mới: data next data next Node* p = malloc(sizeof(Node)); {Giải phóng nút: free(p);
  23. Nút – Phầntử củadanhsách Nguồn: Data Structures : A Pseudocode Approach With C by Richard F. Gilberg, Behrouz A. Forouzan
  24. Khởi tạo và truy cập danh sách móc nối Head 20 45 75 85 zKhai 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.
  25. 3. 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
  26. Truyền danh sách móc nối vào hàm zKhi truyền danh sách móc nối vào hàm, chỉ cần truyền Head. zSử dụng Head để truy cập toàn bộ danh sách zNote: 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 zDo đó nên truyền Head theo tham biến (hoặc trả lại một con trỏ mới)
  27. Thêm một nút mới z 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 z 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
  28. Thêm vào danh sách rỗng Head = NULL; 20 Head newNode Node* newNode; newNode = malloc(sizeof(Node)); newNode->data = 20; newNode->next = NULL; Head = newNode;
  29. Thêm một nút vào đầu danh sách newNode = malloc(sizeof(Node)); newNode->data = 13; newNode->next = Head; Head = newNode; 20 Head 13 newNode
  30. 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; Head 50 40 20 currNode 13 newNode
  31. Thêm một nút mới z 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ụ,khiindex = 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.) z Giải thuật 1. Tìm nút thứ index – currNode 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; newNode
  32. Duyệt danh sách móc nối currNode = Head; Head 20 45 currNode currNode = currNode->next; Head 20 45 currNode
  33. Tìm currNode Thêm một nút mới vào sau nút thứ index. int currIndex = 1; Node* currNode = head; while (currNode && index > currIndex) { currNode = currNode->next; currIndex++; }
  34. Thêm một nút mới Node* InsertNode(Node* head, int index, int x) { Tìm nút thứ if (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; }
  35. Thêm một nút mới Node* InsertNode(Node* head, int index, int x) { if (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; Tạo nút mới head = newNode; } else { newNode->next = currNode->next; currNode->next = newNode; } return newNode; }
  36. Thêm một nút mới Node* InsertNode(Node* head, int index, int x) { if (index currIndex) { currNode = currNode->next; currIndex++; } if (index > 0 && currNode == NULL) return NULL; Node* newNode = (Node*)malloc(sizeof(Node));Thêm vào đầu danh sách newNode->data = x; if (index == 0) { head newNode->next = head; head = newNode; } else { newNode->next = currNode->next; newNode currNode->next = newNode; } return newNode; }
  37. Thêm một nút mới Node* InsertNode(Node* head, int index, int x) { if (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;Thêm vào sau currNode } currNode else { newNode->next = currNode->next; currNode->next = newNode; } return newNode; } newNode
  38. Tìm nút zint 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ại0. 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; return 0; }
  39. Xóa nút z 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ại0. zGiả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 zGiố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
  40. Xóa nút đầu danh sách head = currNode->next; free(currNode); Head (nút xóa) 20 45 75 85 currNode
  41. Xóa nút giữa/cuối danh sách prevNode->next = currNode- >next; free(currNode); Head (nút xóa) 20 45 75 85 prevNode currNode
  42. Xóa một nút Tìm nút có giá trị bằng x 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; }
  43. Xóa một nút 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++; prevNode currNode } if (currNode) { if (prevNode) { prevNode->next = currNode->next; free (currNode); } else { head = currNode->next; free (currNode); } return currIndex; } return 0; }
  44. Xóa một nút 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; } head currNode return 0; }
  45. Hủy danh sách zvoid DestroyList(Node* head) {Sử dụng hàm hủy để 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; // giải phóng nút vừa duyệt free (currNode); currNode = nextNode; } }
  46. In toàn bộ danh sách zvoid DisplayList(Node* head) {In dữ liệu của tất cả các phần tử void DisplayList(Node* head) { int num = 0; Node* currNode = head; while (currNode != NULL){ printf(“%d \n”, currNode->data); currNode = currNode->next; num++; } }
  47. 6 kết quả 7 Sử dụng danh sách 5 6 int main(void) 5 { Node* head = NULL; InsertNode(head, 0, 7); // thêm vào đầu danh sách InsertNode(head, 1, 5); // thêm vào sau phần tử đầu InsertNode(head, -1, 5); // không thêm được InsertNode(head, 0, 6); // thêm vào đầu danh sách InsertNode(head, 8, 4); // không thêm được DisplayList(head); // in danh sách DeleteNode(head, 7); // xóa nút có giá trị = 7 DisplayList(head); // in danh sách DestroyList(head); // hủy toàn bộ danh sách return 0; }
  48. So sánh mảng và danh sách liên kết zViệ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. zKhô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. zNgượ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 zĐể thêm và xóa một phần tử mảng, cần phải copy dịch chuyển phần tử. zVớ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
  49. Các dạng khác của DSLK zDanh sách nối vòng {Nút cuối cùng nối đến nút đầu tiên của danh sách A B C Head {Khi nào thì kết thúc duyệt? (kiểm tra currNode == head?)
  50. Các dạng khác của DSLK zDanh 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 ∅ A B C ∅ Head
  51. Danh sách nối kép zMỗ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 10 20 40 55 70 Head currNode->prev currNode currNode->next
  52. Định nghĩa danh sách nối kép typedef struct Node{ int data; struct Node* next; struct Node* prev; }Node;
  53. Thêm nút zThê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; 10 20 55 70 Head 40 Cur New
  54. Xóa nút zXó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); 10 20 40 55 70 Head Cur
  55. Danh sách nối kép với nút đầu giả {Danh sách không rỗng Nút đầu giả 10 20 40 55 70 Head {Danh sách rỗng Nút đầu giả Head
  56. Tạo danh sách nối kép rỗng Node* Head = malloc (sizeof(Node)); Head->next = Head; Head->prev = Head; Nút đầu giả Head
  57. Xóa nút zNút Cur cần xóa nằm tại đầu danh sách (Cur->prev)->next = Cur->next; (Cur->next)->prev = Cur->prev; free (Cur); Nút đầu giả 10 20 40 55 70 Head Cur
  58. zNút cần xóa nằm ởgiữa danh sách (Cur->prev)->next = Cur->next; (Cur->next)->prev = Cur->prev; free (Cur); // giống như xóa ở đầu DS! Nút đầu giả 10 20 40 55 70 Cur Head
  59. zNút cần xóa nằm tạicuối danh sách (Cur->prev)->next = Cur->next; (Cur->next)->prev = Cur->prev; free (Cur); // tương tự như xóa ở giữa DS! Nút đầu giả 10 20 40 55 70 Head Cur
  60. 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); } }
  61. Thêm nút zThêm nút New vào sau nút giả (đầu danh sách) và trước nút Cur New->next = Cur; New->prev = Cur->prev; Cur->prev = New; (New->prev)->next = New; Nút giả 20 10 Head New Cur
  62. Thêm vào giữa DS zThêm nút New vào trước nút Cur New->next = Cur; New->prev = Cur->prev; Cur->prev = New; (New->prev)->next = New; // giống như thêm vào đầu! Nút giả 10 20 55 40 New Cur Head
  63. Thêm vào cuối DS zThêm nút New vào cuối DS (lúc này Cur trỏ vào nút giả) New->next = Cur; New->prev = Cur->prev; Cur->prev = New; (New->prev)->next = New; // giống như thêm vào đầu Nút giả 10 20 40 55 70 Cur Head New
  64. Thêm vào DS rỗng zThêm New vào danh sách rỗng (Cur trỏ vào nút giả) New->next = Cur; New->prev = Cur->prev; Cur->prev = New; (New->prev)->next = New; Nút giả 20 Head Cur New
  65. 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; Cur->prev = New; (New->prev)->next = New; }
  66. 5. Sử dụng danh sách móc nối zBài toán cộng 2 đa thức: 5x4 + 6x3 + 7 +2x3 –7x2 + 3x = 5x4 + 8x3 –7x2 + 3x + 7 zMỗi nút của danh sách: nút 5 4 coef exponent next
  67. Figure 3-38 Biểu diễn đa thức
  68. ztypedef struct poly{ float hs; float sm; struct poly *nextNode; }