Kỹ thuật lập trình C/C++-Chương: Cấu trúc dữ liệu

Chia sẻ: Nguyễn Kim Thành | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

119
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cấu trúc dữ liệu (CTDL) là một cách tổ chức dữ liệu của bài toán. CTDL có thể do ngôn ngữ lập trình định nghĩa trước hoặc có thể do người sử dụng định nghĩa. Cấu trúc dữ liệu tốt thì thuật toán xử lý bài toán mới tối ưu.Cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kỹ thuật lập trình C/C++-Chương: Cấu trúc dữ liệu

Cấu trúc dữ liệu EE3490: Kỹ thuật lập trình – HK1 2011/2012 1 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Mở đầu: mảng động Mảng trong C có số phần tử cố định từ khi khai báo  Mảng động là mảng có số phần tử thay đổi: bản chất là  một con trỏ và một biến cho biết số phần tử int n = 5;  int* arr = (int*)malloc(n*sizeof(int)); Bài toán chèn phần tử vào mảng động:  pos = 2; val = 25;  arr1 = (int*)malloc((n+1)*sizeof(int)); memcpy(arr1, arr, pos*sizeof(int)); memcpy(arr1+pos+1, arr+pos, (n-pos)*sizeof(int)); arr1[pos] = val; 10 20 30 40 50 free(arr); 25 arr = arr1; Tương tự khi xoá phần tử  EE3490: Kỹ25 thuật lập 30 – HK1 2011/2012 trình 10 20 40 50 2 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Khái niệm Ví dụ trên cho thấy mảng động khá kém hiệu quả trong  việc thêm/bớt phần tử vì cần di chuyển các vùng nhớ, nhất là khi mảng có nhiều phần tử  cần các cấu trúc dữ liệu linh hoạt hơn Các cấu trúc dữ liệu phổ biến, ứng dụng tuỳ bài toán:  Ngăn xếp (stack)  Hàng đợi (queue)  Danh sách liên kết (linked list)  Mảng động (vector, dynamic array)  Ánh xạ (map), từ điển (dictionary), bảng băm (hash table)  Tập hợp (set)  Cây (tree)  Đồ thị (graph)  EE3490: Kỹ thuật lập trình – HK1 2011/2012 3 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Danh sách liên kết (DSLK) Là tập hợp các phần tử được móc nối với nhau bằng con trỏ:  Một con trỏ trỏ đến phần tử đầu tiên (hoặc NULL nếu chưa có phần tử nào)  Mỗi phần tử bao gồm 2 thành phần: dữ liệu, con trỏ next tới phần tử tiếp theo  Con trỏ next của phần tử cuối cùng trỏ đến NULL  list data next data next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 4 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Khai báo DSLK Ví dụ với dữ liệu là kiểu int:  struct SELEM;  typedef struct SELEM ELEM, *PELEM, *LLIST; struct SELEM { int data; PELEM next; }; Thư viện DSLK:  llist.h  llist.c  EE3490: Kỹ thuật lập trình – HK1 2011/2012 5 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Thao tác với DSLK Các hàm cần viết:  LLIST llInit();  LLIST llInsertHead(LLIST l, int data);  LLIST llInsertTail(LLIST l, int data);  LLIST llInsertAfter(LLIST l, PELEM a, int data);  LLIST llDeleteHead(LLIST l);  LLIST llDeleteTail(LLIST l);  LLIST llDeleteAfter(LLIST l, PELEM a);  LLIST llDeleteAll(LLIST l);  PELEM llSeek(LLIST l, int i);  void llForEach(LLIST l, LLCALLBACK func);  int llLength(LLIST l);  EE3490: Kỹ thuật lập trình – HK1 2011/2012 6 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Khởi tạo DSLK LLIST llInit() { return NULL; } Khởi tạo DSLK với NULL  chưa có phần tử nào  EE3490: Kỹ thuật lập trình – HK1 2011/2012 7 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Thêm phần tử vào đầu DSLK LLIST llInsertHead(LLIST l, int data) { PELEM e = (PELEM)malloc(sizeof(ELEM)); e->data = data; e->next = l; return l = (LLIST)e; } list data next data data next next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 8 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Thêm phần tử vào cuối DSLK LLIST llInsertTail(LLIST l, int data) { PELEM p; PELEM e = (PELEM)malloc(sizeof(ELEM)); e->data = data; list e->next = NULL; data next data if (!l) return (LLIST)e; data next next data for (p=l; p->next; p = p->next) ; next p->next = e; return l; } EE3490: Kỹ thuật lập trình – HK1 2011/2012 9 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Thêm phần tử vào sau một phần tử của DSLK LLIST llInsertAfter(LLIST l, PELEM a, int data) { PELEM e; if (!a) return l; e = (PELEM)malloc(sizeof(ELEM)); e->data = data; e->next = a->next; a a->next = e; list data data return l; next next } data next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 10 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Xoá phần tử đầu trong DSLK LLIST llDeleteHead(LLIST l) { PELEM p; if (!l) return NULL; p = l->next; list free(l); data return (LLIST)p; next data } next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 11 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Xoá phần tử cuối DSLK LLIST llDeleteTail(LLIST l) { PELEM p; if (!l) return NULL; if (!l->next) { list data free(l); next return NULL; data } next data next for (p=l; p->next->next; p = p->next) ; free(p->next); p->next = NULL; return l; }12 EE3490: Kỹ thuật lập trình – HK1 2011/2012 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Xoá phần tử sau một phần tử trong DSLK LLIST llDeleteAfter(LLIST l, PELEM a) { PELEM p; if (!a || !a->next) return l; p = a->next; a->next = p->next; a list free(p); data return l; next data } next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 13 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Duyệt DSLK Tìm đến phần tử thứ i của DSLK  PELEM llSeek(LLIST l, int i) { for (; i>0 && l; i--) l = l->next; return (PELEM)l; } Gọi hàm với mỗi phần tử của DSLK  typedef void (*LLCALLBACK)(int, void*); void llForEach(LLIST l, LLCALLBACK func, void* user) { for (; l; l=l->next) func(l->data, user); } EE3490: Kỹ thuật lập trình – HK1 2011/2012 14 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Các hàm khác với DSLK Đếm số phần tử  int llLength(LLIST l) { int c; for (c=0; l; c++) l = l->next; return c; } Xoá tất cả các phần tử  LLIST llDeleteAll(LLIST l) { PELEM p; for (; l; l=p) { p = l->next; free(l); } return NULL; } EE3490: Kỹ thuật lập trình – HK1 2011/2012 15 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Ví dụ sử dụng DSLK for (i=0; inext) l = llDeleteAfter(l, p); printf("%d ", l->data); l = llDeleteHead(l); printf("\n"); l = llDeleteTail(l); } printList(l); void listSum(int data,void* user) { int* pS = (int*)user; s = 0; *pS += data; llForEach(l, listSum, (void*)&s); } printf("Tong gia tri: %d\n", s); int main() { LLIST l; l = llDeleteAll(l); PELEM p; printList(l); int i, s; return 0; l = llInit(); } EE3490: Kỹ thuật lập trình – HK1 2011/2012 16 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Đặc điểm của DSLK Ưu/nhược điểm so với mảng động:  Linh hoạt: thêm/bớt phần tử dễ dàng, sắp xếp và thay đổi + thứ tự phần tử mà không cần di chuyển trong bộ nhớ Không cần cấp phát một vùng nhớ lớn và liên tục + Cần thêm bộ nhớ phụ cho các biến con trỏ – Không truy cập tới phần tử bất kỳ thứ i được như mảng, – mà phải duyệt từ đầu tới Ngoài dạng cơ bản, có rất nhiều biến thể của DSLK:  DSLK kép, DSLK có thứ tự, hàng đợi, ngăn xếp, DSLK vòng,… và cũng có nhiều cách cài đặt khác nhau tuỳ thuộc vào bài toán cụ thể EE3490: Kỹ thuật lập trình – HK1 2011/2012 17 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Ngăn xếp (stack) Ngăn xếp là trường hợp riêng của  DSLK, chỉ có hai thao tác: push: thêm phần tử vào đầu danh sách  Pop Push  pop: lấy giá trị đồng thời xoá phần tử đầu danh sách  thuộc loại danh sách LIFO (last in, first out) Ứng dụng:  Tính toán biểu thức (ký pháp Ba Lan ngược)  Thực hiện việc gọi hàm trong ngôn ngữ lập  trình Giải đệ quy  Dữ liệu undo  EE3490: Kỹ thuật lập trình – HK1 2011/2012 18 Đào Trung Kiên – ĐH Bách khoa Hà Nội
Hàng đợi (queue) Hàng đợi là trường hợp riêng của DSLK,  chỉ có hai thao tác: Enqueue enqueue: thêm phần tử vào cuối danh sách   dequeue: lấy giá trị đồng thời xoá phần tử đầu danh sách  thuộc loại danh sách FIFO (first in, first out) Để lập trình hàng đợi, thường dùng hai con  Dequeue trỏ: một tới đầu danh sách để thêm, một tới cuối danh sách để lấy phần tử Ứng dụng:  Truyền thông tin, dữ liệu  Bộ nhớ đệm đọc/ghi dữ liệu  Cài đặt các dịch vụ (mô hình client/server)  EE3490: Kỹ thuật lập trình – HK1 2011/2012 19 Đào Trung Kiên – ĐH Bách khoa Hà Nội
DSLK kép (doubly linked list) Trong DSLK thông thường, mỗi phần tử chỉ có một con  trỏ next tới phần tử kế tiếp  gọi là DSLK đơn, chỉ duyệt DS được một chiều DSLK kép: mỗi phần tử có thêm con trỏ prev tới phần tử  ở trước  có thể duyệt được hai chiều prev list data prev next data prev next data next EE3490: Kỹ thuật lập trình – HK1 2011/2012 20 Đào Trung Kiên – ĐH Bách khoa Hà Nội