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 (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...
Nội dung trích xuất từ tài liệu:
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/20121 Đào Trung Kiên – ĐH Bách khoa Hà NộiMở đầ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ộiKhá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ộiDanh 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ộiKhai 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ộiThao 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ộiKhởi tạo DSLKLLIST 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ộiThêm phần tử vào đầu DSLKLLIST llInsertHead(LLIST l, int data) { PELEM e = (PELEM)malloc(sizeof(ELEM)); e->data = data; e->next = l; return l = (LLIST)e;} list ...