Bài giảng Ngôn ngữ lập trình C - Chương 5: Dữ liệu kiểu cấu trúc - Ninh Thị Thanh Tâm

Nội dung text: Bài giảng Ngôn ngữ lập trình C - Chương 5: Dữ liệu kiểu cấu trúc - Ninh Thị Thanh Tâm

1. NGÔN NGỮ LẬP TRÌNH C Dữ liệu kiểu cấu trúc Ninh Thị Thanh Tâm Khoa CNTT – HV Quản lý Giáo dục
2. Mục đích  Biết cách khai báo các kiểu dữ liệu phức tạp: cấu trúc  Cách biểu diễn các kiểu danh sách liên kết nhờ cấu trúc tự trỏ  Các thao tác trên danh sách liên kết
3. Nội dung  Cấu trúc Khái niệm, định nghĩa Khai báo cấu trúc Đặt tên kiểu dữ liệu Thao tác trên biến cấu trúc Truyền biến cấu trúc cho hàm  Các cấu trúc tự trỏ Ngăn xếp - LIFO Hàng đợi - FIFO Cây nhị phân – BINARY TREE
4. Cấu trúc  Khái niệm, định nghĩa  Khai báo cấu trúc  Đặt tên kiểu dữ liệu  Thao tác trên biến cấu trúc  Truyền biến cấu trúc cho hàm
5. Khái niệm, định nghĩa  Cấu trúc: Một kiểu dữ liệu bao gồm nhiều thành phần có thể thuộc nhiều kiểu dữ liệu khác nhau
6. Khai báo cấu trúc  Khai báo kiểu dữ liệu cấu trúc: struct { }; struct là từ khóa đứng trước một khai báo cấu trúc  là tên hợp lệ, dùng làm tên cấu trúc  tương tự khai báo biến
7. Ví dụ struct sinhvien { char ho_ten[30]; float diemtb; }; struct diem { float x,y; };
8. Khai báo cấu trúc (2)  Khai báo biến cấu trúc: struct ; Ví dụ: struct sinhvien sv, dssv[100]; struct diem p, q, dsdiem[50];
9. Khai báo cấu trúc (3)  Khai báo đồng thời cấu trúc và biến cấu trúc: struct [ ] { } ;
10. Ví dụ struct dagiac { int n; struct diem dsdinh[20]; } dg1, dg2;  Có thể khai báo trực tiếp kiểu của các thành phần là biến cấu trúc bên trong một cấu trúc lớn hơn struct dagiac { int n; struct { float x, y; } dsdinh[20]; } dg1, dg2;
11. Đặt tên kiểu dữ liệu  Từ khóa typedef Cho phép thêm tên mới cho một kiểu dữ liệu Cú pháp typedef ;  là kiểu dữ liệu muốn thêm tên  là tên mới muốn đặt Dùng để định nghĩa các kiểu dữ liệu phức hợp thành một tên duy nhất để dễ dàng khi viết
12. Ví dụ  typedef unsigned char byte; byte được xem như kiểu dữ liệu tương đương với unsigned char Có thể sử dụng trong khai báo các biến như kiểu dữ liệu khác
13. Ví dụ /*struct1.c*/ #include #include typedef unsigned char byte; void main() { byte ch = 12, ch1; int i; clrscr(); ch1 = ch; for (i=0; i<5; i++) { ch <<=1; printf("%x\n",ch); } printf("byte %X sau khi dich trai 5 lan la: %X", ch1, ch); getch(); }
14. Sử dụng typedef với cấu trúc  Cho phép đơn giản hóa cách viết khai báo  Ví dụ: struct sinhvien { char hoten[30]; float diemtb; }; typedef struct sinhvien sv; typedef struct sinhvien *ptr_sv;  Cấu trúc struct sinhvien sẽ là sv  Định nghĩa một kiểu con trỏ cấu trúc có tên là ptr_sv  Khi đó:  sv sv1, sv2, dssv[100]; ~ struct sinhvien sv1, sv2, dssv[100];  ptr_sv ptrsv; ~ struct sinhvien *ptrsv;
15. Thao tác trên biến cấu trúc  Truy cập thành phần trong cấu trúc  Truy cập tới thành phần cấu trúc từ con trỏ cấu trúc  Nhập dữ liệu cho biến cấu trúc
16. Truy cập thành phần trong cấu trúc  Cần đến tên thành phần và biến tương ứng  Cú pháp: .  Dấu chấm (.) là toán tử truy cập thành phần cấu trúc  Nếu có nhiều cấu trúc lồng nhau thì sử dụng nhiều dấu (.) tương ứng  Ví dụ:  p.x = 0; p.y = 5;  dg1.dsdinh[10].x = 0; dg1.n = 10;
17. Truy cập thành phần cấu trúc từ con trỏ cấu trúc  Nếu ptr là con trỏ cấu trúc, có 2 cách để truy cập tới thành phần của nó Cách 1: (*ptr). Cách 2: ptr->
18. Nhập dữ liệu cho biến cấu trúc  Nên sử dụng biến trung gian  Nhập dữ liệu qua biến trung gian  Gán các giá trị nhập được cho các thành phần cần nhập  Ví dụ float temp; printf("Toa do x="); scanf("%f", &temp); p.x = temp; printf("Toa do y="); scanf("%f", &temp); p.y = temp;
19. Ví dụ /*struct2.c*/ #include #include struct sinhvien { char hoten[30]; float diemtb; }; void main() { int n; int k; int i; struct sinhvien dssv[100]; char name[30]; float temp; clrscr();
20. n = 0; do { printf("Nhap thong tin sinh vien thu %d\n",n+1); printf("Ho ten:"); fflush(stdin); gets(name); if (strcmp(name,"")!=0) { strcpy(dssv[n].hoten,name); printf("Diem:"); scanf("%f",&temp); dssv[n++].diemtb = temp; } } while (strcmp(name,"")!=0);
21. if (!n) { printf("Khong co sinh vien nao\n"); return; } else { k = 0; // printf("DS Sv nhan hoc bong"); for (i=0; i =7) k++; } if (!k) printf("Khong co sinh vien dat hoc bong"); else for (i=0; i =7) printf("%d\t%s %5.2f\n",i+1,dssv[i].hoten,dssv[i].diemtb); } getch(); }
22. Phép gán giữa các biến cấu trúc  Gán nội dung của một biến cấu trúc cho một biến cấu trúc khác cùng kiểu
23. Ví dụ /*struct3.c*/ #include #include struct sinhvien { char hoten[30]; float diemtb; } sv1, sv2; void main() { clrscr(); sv1.diemtb = 8.7; strcpy(sv1.hoten,"Nguyen Van A"); sv2 = sv1; printf("sv1: (%s\t%5.2f)\n",sv1.hoten,sv1.diemtb); printf("sv2: (%s\t%5.2f)\n",sv2.hoten,sv2.diemtb); getch(); }
24. Kết quả
25. Truyền biến cấu trúc cho hàm  Truyền biến cấu trúc bằng tham trị Nội dung của biến cấu trúc dùng làm tham số thực được sao chép sang vùng nhớ dành cho tham số hình thức Giảm tốc độ thực hiện chương trình  Truyền biến cấu trúc bằng tham biến Truyền cho hàm địa chỉ của cấu trúc
26. Ví dụ  Khai báo hai cấu trúc Cấu trúc điểm gồm 2 thành phần hoành độ, tung độ Cấu trúc tam giác gồm 3 thành phần là 3 biến có kiểu điểm Nhập, tính diện tích tam giác Cho biến tam giác vừa nhập là loại tam giác nào
27. Ví dụ /*struct4.c*/ #include #include #include typedef struct { float x, y; } diem; typedef struct { diem A, B, C; } tamgiac; void nhap(tamgiac *); float canh(diem, diem); float canhbp(diem, diem); int loaitg(tamgiac); float dientich(tamgiac);
28. void main() { tamgiac tg; clrscr(); printf("Nhap toa do cac dinh tam giac\n"); nhap(&tg); printf("Canh BC:%f\n", canh(tg.B,tg.C)); printf("Canh CA:%f\n", canh(tg.C,tg.A)); printf("Canh AB:%f\n", canh(tg.A,tg.B)); switch (loaitg(tg)) { case 1: printf("Tam giac deu\n"); break; case 2: printf("Tam giac vuong can\n"); break; case 3: printf("Tam giac can\n"); break; case 4: printf("Tam giac vuong\n"); break; case 5: printf("Tam giac thuong\n"); break; } printf("Dien tich %f\n",dientich(tg)); getch(); }
29. void nhap(tamgiac *temp){ float t; printf("Nhap dinh A\n"); printf("x="); scanf("%f",&t); temp->A.x = t; printf("y="); scanf("%f",&t); temp->A.y = t; printf("Nhap dinh B\n"); printf("x="); scanf("%f",&t); temp->B.x = t; printf("y="); scanf("%f",&t); temp->B.y = t; printf("Nhap dinh C\n"); printf("x="); scanf("%f",&t); temp->C.x = t; printf("y="); scanf("%f",&t); temp->C.y = t; }
30. float canh(diem p, diem q){ return (sqrt(pow(p.x-q.x,2.0)+pow(p.y-q.y,2.0))); } float canhbp(diem p, diem q){ return (pow(p.x-q.x,2.0)+pow(p.y-q.y,2.0)); } float dientich(tamgiac tg){ float a, b, c, p; a = canhbp(tg.B,tg.C); b = canhbp(tg.A,tg.C); c = canhbp(tg.A,tg.B); p = (a+b+c)/2; return (sqrt(p*(p-a)*(p-b)*(p-c))); }
31. int loaitg(tamgiac tg){ float a, b, c; a = canh(tg.B,tg.C); b = canh(tg.A,tg.C); c = canh(tg.A,tg.B); if (a==b||b==c||c==a) if (a==b&&b==c) return 1; else if (a==b+c||b==c+a||c==b+a) return 2; else return 3; else if (a==b+c||b==c+a||c==a+b) return 4; else return 5; }
32. Cấu trúc tự trỏ  Khái niệm cấu trúc tự trỏ: Cấu trúc có ít nhất một thành phần là con trỏ chỉ đến bản thân cấu trúc  Đặc điểm Kéo dài danh sách ra vô hạn Hạn chế bộ nhớ nếu số lượng phần tử nhỏ Các thao tác phức tạp hơn
33. Ví dụ struct sinhvien { char hoten[30]; float diem; struct sinhvien *next; }; struct tree { float x; struct tree *left, *right; };
34. Ví dụ - LIFO  Tạo danh sách móc nối gồm 100 số tự nhiên đầu tiên; in lại danh sách.
35. /*dsmn3.c*/ #include #include typedef struct mn { int so; struct nn *next; } mn; mn *ds; mn *ptmoi(int); void taods(); void inds(); void main(){ taods(); inds(); getch(); }
36. mn *ptmoi(int k){ mn *p; p = (mn *)malloc(sizeof(mn)); p->so = k; return p; } void taods(){ //Kieu LIFO int i; mn *p; ds = NULL; for (i=1; i next = ds; ds = p; } }
37. void inds(){ mn *p; for (p=ds; p; p=p->next) printf("%5d",p->so); puts(""); }
38. Cách 2  mn* ptmoi(int);  mn* taods();  void inds(mn*)  void main()  { mn *ds; ds=taods(); inds(ds); getch();  }
39. mn *taods(){ int i; mn *p, *ds; ds = NULL; for (i=1; i next = ds; ds = p; } return ds; }
40. Ví dụ - LIFO  Tạo ngẫu nhiên một dãy gồm 10 số nguyên, các số nằm trong khoảng từ 0 đến 100, đưa vào một danh sách móc nối  Sắp lại danh sách theo thứ tự giảm dần  Xóa tất cả các số chẵn
41. /*dsmn4.c*/ #include #include #include typedef struct mn { int so; struct mn *next; } mn; mn *ds; int m = 10; void taoday(){ int i; mn *p; randomize(); ds = NULL; for (i=0; i so = random(51); p->next = ds; ds = p; } }
42. void sapxep(){ mn *p, *t; int x; p = ds; for (p = ds; p->next; p = p->next) for (t = p->next; t; t=t->next) if (p->so so) { x = p->so; p->so = t->so; t->so = x; } } void inday(){ mn *p; for (p=ds; p; p=p->next) printf("%5d",p->so); puts(""); }
43. void xoasau(mn *p){ if (p->next) p->next = (p->next)->next; else printf("Khong hop le"); } void main(){ mn *p; clrscr(); taoday(); inday(); sapxep(); inday(); for (p = ds; p->next;) if ((p->next)->so %2==0) xoasau(p); else if (p->next) p = p->next; if (ds->so%2==0) ds = ds->next; inday(); getch(); }
44. Kết quả
45. Ví dụ - FIFO  Đưa vào một danh sách móc nối thông tin tên và điểm của từng học sinh; nhập điểm chuẩn: Đưa những học sinh đạt điểm chuẩn vào đầu danh sách Những học sinh không đạt xuống cuối danh sách (không làm thay đổi thứ tự)
46. /*dsmn5.c*/ #include #include #include typedef struct { char ten[20]; float diem; } hocsinh; typedef struct mn{ hocsinh hs; struct mn *next; } ptr; ptr *ds;
47. void taods(){ ptr *p, *q; hocsinh x; float d; char w[20]; ds = NULL; puts("Nhap danh sach ten, diem. Het go /"); fflush(stdin); gets(w); while (strcmp(w,"/")){ strcpy(x.ten,w); scanf("%f",&d); x.diem = d; p = (ptr*)malloc(sizeof(ptr)); p->hs = x; p->next = NULL; if (ds) q->next = p; else ds = p; q = p; fflush(stdin); gets(w); } }
48. void sapxep(){ float d; hocsinh x; ptr *p; int tiep = 1; printf("Nhap diem chuan"); scanf("%f",&d); while (tiep){ tiep = 0; for (p=ds; p->next; p=p->next) if (p->hs.diem next)->hs.diem>=d){ x = p->hs; p->hs = (p->next)->hs; (p->next)->hs = x; tiep = 1; } } }
49. void inds(){ ptr *p; for (p=ds; p; p=p->next) printf("%s %6.1f\n",p->hs.ten,p->hs.diem); getch(); } void main(){ taods(); inds(); sapxep(); inds(); }
50. Cây tìm kiếm nhị phân  Ví dụ: Nhập một dãy số thực Xây dựng cây tìm kiếm nhị phân từ dãy số đó
51. /*tree.c*/ #include #include #include typedef struct node { float k; struct node *left, *right; } node; node *goc; node *nutmoi(float x); void them(float x, node *p); void taocay(); void incay(node *p); void tim(float x, node *p, int t);
52. void main(){ float y; taocay(); incay(goc); printf("Nhap y="); scanf("%f",&y); tim(y,goc,1); incay(goc); getch(); } node *nutmoi(float x){ node *p; if(!(p=(node*)malloc(sizeof(node)))){ printf("Loi cap phat bo nho"); getch(); exit(0); } p->k = x; p->left = p->right = NULL; return p; }
53. void them(float x, node *p){ if (x==p->k) return; if (x k){ if (p->left) them(x,p->left); else p->left = nutmoi(x); } else{ if(p->right) them(x,p->right); else p->right = nutmoi(x); } }
54. void taocay(){ float x; int i, n; printf("x="); scanf("%f",&x); printf("n="); scanf("%d",&n); for (i=1; i<n; i++){ printf("x="); scanf("%f",&x); them(x,goc); } }
55. void incay(node *p){ if (!p) return; incay(p->left); printf("%6.1f",p->k); incay(p->right); } void tim(float x, node *p, int t){ if(!p){ printf("Khong tim thay"); getch(); exit(0); } if (p->k==x){ puts("Da tim thay"); getch(); exit(0); } if (x k) tim(x,p->left,t+1); else tim(x,p->right,t+1); }