Bài giảng Ngôn ngữ lập trình C - Dữ liệu kiểu cấu trúc

ai 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;
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
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;
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->
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;
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();
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);
if (!n) {
printf("Khong co sinh vien nao\n");
return;
}
else {
k = 0;
// printf("DS Sv nhan hoc bong");
for (i=0; i<n; i++){
if (dssv[i].diemtb >=7)
k++;
}
if (!k)
printf("Khong co sinh vien dat hoc bong");
else
for (i=0; i<n; i++)
if (dssv[i].diemtb >=7)
printf("%d\t%s 
%5.2f\n",i+1,dssv[i].hoten,dssv[i].diemtb);
}
getch();
}
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
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();
}
Kết quả
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
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
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);
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();
}
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;
}
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)));
}
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;
}
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
Ví dụ
struct sinhvien {
char hoten[30];
float diem;
struct sinhvien *next;
};
struct tree {
float x;
struct tree *left, *right;
};
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.
/*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();
}
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<=100; i++){
p = ptmoi(i);
p->next = ds;
ds = p;
}
}
void inds(){
mn *p;
for (p=ds; p; p=p->next)
printf("%5d",p->so);
puts("");
}
Cách 2
 mn* ptmoi(int);
 mn* taods();
 void inds(mn*)
 void main()
 {
mn *ds;
ds=taods();
 inds(ds);
getch();
 }
mn *taods(){
int i;
mn *p, *ds;
ds = NULL;
for (i=1; i<=100; i++){
p = ptmoi(i);
p->next = ds;
ds = p;
}
return ds;
}
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
/*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<m; i++){
if (!(p=(mn*)malloc(sizeof(mn)))){
puts("Loi cap phat bo nho");
getch();
exit(0);
}
p->so = random(51);
p->next = ds;
ds = p;
}
}
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("");
}
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();
}
Kết quả
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ự)
/*dsmn5.c*/
#include 
#include 
#include 
typedef struct {
char ten[20];
float diem;
} hocsinh;
typedef struct mn{
hocsinh hs;
struct mn *next;
} ptr;
ptr *ds;
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);
}
}
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.diemnext)->hs.diem>=d){
x = p->hs;
p->hs = (p->next)->hs;
(p->next)->hs = x;
tiep = 1;
}
}
}
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();
}
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ố đó
/*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);
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;
}
void them(float x, node *p){
if (x==p->k) return;
if (xk){
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);
}
}
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);
}
}
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 (xk)
tim(x,p->left,t+1);
else tim(x,p->right,t+1);
}