Bài giảng Cấu trúc dữ liệu 1 - Chương 3a. Cấu trúc dữ liệu động

CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@agu.edu.vnTRƯỜNG ĐẠI HỌC AN GIANGKHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNGChương 3. CẤU TRÚC DỮ LIỆU ĐỘNGĐặt vấn đềKiểu dữ liệu Con trỏDanh sách liên kết (link list)Danh sách đơn (xâu đơn)Tổ chức danh sách đơn theo cách cấp phát liên kếtMột số cấu trúc dữ liệu dạng danh sách liên kết khácDanh sách liên kết képHàng đợi hai đầu (double-ended queue)Danh sách liên kết có thứ tự (odered list)Danh sách liên kết vòngDanh sách có nhiều mối liên kếtDanh sách tổng quát Đặt vấn đềBiến không động (biến tĩnh, biến nửa tĩnh)Được khai báo tường minhTồn tại trong phạm vi khai báoĐược cấp phát vùng nhớ trong vùng dữ liệu (Data) hoặc là StackKích thước không thay đổi trong suốt quá trình sốngĐặt vấn đềBiến độngBiến không được khai báo tường minhCó thể cấp phát hay giải phóng bộ nhớ khi cầnVùng nhớ của biến được cấp phát trong HeapKích thước có thể không thay đổi trong quá trình sốngCon trỏ (Pointers)Khai báo: Dạng *Con trỏchar *c int *i; float *f;typedef int *intPointer;intPointer p; hoặc int *p;Ví dụ:Lập chương trình định nghĩa một số nguyên có giá trị bằng 1 và dùng một con trỏ p để chỉ số nguyên này. Sau đó in lên màn hình giá trị của số nguyên này bằng 2 cáchKhông dùng con trỏThông qua con trỏCon trỏ (tt)#include void main(){ int *p, n=1; printf("n=%d \n", n); p=&n; printf("n=%d \n", *p); //p}Kết quả: n=1; n=1; Con trỏ - Các phép tính về con trỏvoid main(){ char *a; char c[]="Pointers"; a=&c[0]; printf("c[1]=%c \n", *(a+1)); printf("Apter a+1, *a=%c \n", *a); a++; printf("Apter a+1, *a=%c \n", *a);}Kết quả:C[1]=oAfter a+1, *a=PAfter a++, *a=oCon trỏ - Các phép tính về con trỏvoid main(){ char *a; char c[]="Pointers"; int i; a=c; for(i=0; i;void main(){ char *p[3]=["Fortral", "Pascan", "List"]; *(p[0]+6)='n'; *(p[1]+5)='l'; *(p[2]+3)='p'; printf("%s \n %s \n %s\n", p[0], p[1], p[2]);}Con trỏ dùng như mảngVí dụ:Lập chương trình nhận từ bàn phím một số lượng từ 3 đến 10 dữ liệu số nguyên. Sau đó dùng lệnh printf để đưa chúng lên màn hình. Dùng 2 cáchCách dùng mảngCách dùng con trỏ kết hợp với mallocCon trỏ dùng như mảng#define MAX =10;void main(){ int a[MAX], i, n; printf("So luong du lieu"); scanf("%d", &n); for(i=0; iname); printf("Tuoi du lieu %d =",i); scanf("%s", (p+i)->age); } for(i=0; iname, (p+i)->age);}Con trỏ vạn năngLà con trỏ có thể chỉ bất kỳ loại dữ liệu nào (chữ, số nguyên, số thực, ) trong chương trìnhCon trỏ vạn năng được định nghĩa như sauvoid *p;Con trỏ vạn năngvoid main(){ void *p; char c='a'; int n='1'; float r =0.5; p=&c; printf("p= %c\n", *((char*)) p); p=&n; printf("p= %d\n", *((int*)) p); p=&r; printf("p= %1.1f\n", *((float*)) p);}Con trỏ képvoid main(){ char *p[3]=["Fortran", "Pascal", "Lisp"]; char **pp; pp=p; printf("%s\n %s\n %s\n", *pp, *(pp+1), *(pp+2));}Cảm ơn !