Bài giảng Kỹ thuật lập trình: Bài 7 - TS. Đào Trung Kiên

Bài 7: Cấu trúc dữ liệu<br /> (Data structures)<br /> <br /> 1<br /> <br /> EE3490: Kỹ thuật lập trình – HK1 2017/2018<br /> TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội<br /> <br /> Mở đầu: mảng động<br /> Mảng trong C có số phần tử cố định từ khi khai báo<br /> Mảng động là mảng có số phần tử thay đổi: bản chất là<br /> một con trỏ và một biến cho biết số phần tử<br /> <br /> <br /> <br /> <br /> <br /> <br /> int n = 5;<br /> int* arr = (int*)malloc(n*sizeof(int));<br /> <br /> Bài toán chèn phần tử vào mảng động:<br /> <br /> <br /> <br /> <br /> <br /> pos = 2; val = 25;<br /> arr1 = (int*)malloc((n+1)*sizeof(int));<br /> memcpy(arr1, arr, pos*sizeof(int));<br /> memcpy(arr1+pos+1, arr+pos, (n-pos)*sizeof(int));<br /> arr1[pos] = val;<br /> 10<br /> 20<br /> 30<br /> 40<br /> 50<br /> free(arr);<br /> 25<br /> arr = arr1;<br /> <br /> Tương tự khi xoá phần tử<br /> <br /> <br /> 2<br /> <br /> 10<br /> <br /> EE3490: Kỹ thuật lập trình – HK1 2017/2018<br /> 20<br /> 25<br /> 30<br /> 40<br /> 50<br /> TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội<br /> <br /> Khái niệm<br /> Ví dụ trên cho thấy mảng động khá kém hiệu quả trong<br /> việc thêm/bớt phần tử vì cần di chuyển các vùng nhớ,<br /> nhất là khi mảng có nhiều phần tử  cần các cấu trúc dữ<br /> liệu linh hoạt hơn<br /> Các cấu trúc dữ liệu phổ biến, ứng dụng tuỳ bài toán:<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> 3<br /> <br /> Ngăn xếp (stack)<br /> Hàng đợi (queue)<br /> Danh sách liên kết (linked list)<br /> Mảng động (vector, dynamic array)<br /> Ánh xạ (map), từ điển (dictionary), bảng băm (hash table)<br /> Tập hợp (set)<br /> Cây (tree)<br /> Đồ thị (graph)<br /> EE3490: Kỹ thuật lập trình – HK1 2017/2018<br /> TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội<br /> <br /> Danh sách liên kết (DSLK)<br /> Là tập hợp các phần tử được móc nối với nhau bằng con trỏ:<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> 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)<br /> 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<br /> Con trỏ next của phần tử cuối cùng trỏ đến NULL<br /> <br /> list<br /> data<br /> next<br /> data<br /> next<br /> data<br /> next<br /> 4<br /> <br /> EE3490: Kỹ thuật lập trình – HK1 2017/2018<br /> TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội<br /> <br /> Khai báo DSLK<br /> Ví dụ với dữ liệu là kiểu int:<br /> <br /> <br /> <br /> <br /> <br /> struct SELEM;<br /> typedef struct SELEM ELEM, *PELEM, *LLIST;<br /> struct SELEM {<br /> int data;<br /> PELEM next;<br /> };<br /> <br /> Thư viện DSLK:<br /> <br /> <br /> <br /> <br /> <br /> <br /> 5<br /> <br /> llist.h<br /> llist.c<br /> <br /> EE3490: Kỹ thuật lập trình – HK1 2017/2018<br /> TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội<br /> <br />