Cấu trúc dữ liệu chương 1b

1.2.3 Các kiểu dữ liệu có cấu trúc

Tuy nhiên trong nhiều trường hợp, chỉ với các kiểu dữ liệu cơ /sở không đủ để phản ánh tự nhiên và đầy đủ bản chất của sự vật thực tế, dẫn đến nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành phần dữ liệu có kiểu dữ liệu đã được định nghĩa. Những kiểu dữ liệu được xây dựng như thế gọi là kiểu dữ liệu có cấu trúc.
Một số kiểu dữ liệu có cấu trúc cơ bản :

a. Kiểu chuỗi ký tự
Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và thường các ngôn ngữ lập trình đều định nghĩa nó như một kiểu cơ bản. Do tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình luôn cung cấp sẵn một bộ các hàm thư viện các xử lý trên kiểu dữ liệu này. Các hàm này được đặt trong thư viện string.lib của C.
Chuỗi ký tự trong C được cấu trúc như một chuỗi liên tiếp các ký tự kết thúc bằng ký tự \0 có mã ASCII bằng 0 (NULL character). Như vậy, giới hạn chiều dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65535 ký tự), ký tự đầu tiên được đánh số là ký tự thứ 0.
Ta có thể khai báo một chuỗi ký tự theo một số cách sau đây:
char S[10]; //Khai báo một chuỗi ký tự S có chiều dài
// tối đa 10 (kể cả kí tự kết thúc)
char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều
// dài bằng chiều dài của chuỗi "ABC"
// và giá trị khởi đầu của S là "ABC"
char *S ="ABC";//Giống cách khai báo trên.
Trong ví dụ trên ta cũng thấy được một hằng chuỗi ký tự được thể hiện bằng một chuỗi ký tự đặt trong cặp ngoặc kép “”.
Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác thông dụng:
So sánh 2 chuỗi: strcmp
Sao chép chuỗi: strcpy
Độ dài chuỗi: strlen
Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr
Cắt 1 từ ra khỏi 1 chuỗi: strtok
Đổi 1 số ra chuỗi: itoa
Đổi 1 chuỗi ra số: atoi, atof, ...
Nhập một chuỗi: gets
Xuất một chuỗi: puts

b. Kiểu mảng
Kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tượng của mảng 1 chiều, ma trận là hình tượng của mảng 2 chiều.
Một điều đáng lưu ý là mảng 2 chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. Tương tự như vậy, một mảng n chiều có thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều.
Mảng 1 chiều được khai báo như sau:
<kiểu> <tên>[<số>];<kiểu><tên><số></số></tên></kiểu>
Ví dụ để khai báo một biến có tên a là một mảng nguyên 1 chiều có tối đa 100 phần tử ta phải khai báo như sau:
int a[100];
Ta cũng có thể vừa khai báo vừa gán giá trị khởi động cho một mảng như sau:
int a[5] = {1, 7, -3, 8, 19};
Trong trường hợp này C cho phép ta khai báo một cách tiện lợi hơn
int a[] = {1, 7, -3, 8, 19};
Như ta thấy, ta không cần chỉ ra số lượng phần tử cụ thể trong khai báo. Trình biên dịch của C sẽ tự động làm việc này cho chúng ta.
Tương tự ta có thể khai báo một mảng 2 chiều hay nhiều chiều theo cú pháp sau:
<kiểu> <tên>[<số>][<số>]...;
Ví dụ, ta có thể khai báo:
int a[100][150];
hay

int a[][]={{1, 7, -3, 8, 19},
{4, 5, 2, 8, 9},
{21, -7, 45, -3, 4}};

(mảng a sẽ có kích thước là 3x5).

c. Kiểu union
Kiểu union là một dạng cấu trúc dữ liệu đặc biệt của ngôn ngữ C. Nó rất giống với kiểu struct. Chỉ khác một điều, trong kiểu union, các trường được phép dùng chung một vùng nhớ. Hay nói cách khác, cùng một vùng nhớ ta có thể truy xuất dưới các dạng khác nhau.
Khai báo tổng quát của kiểu union như sau:

typedef union <tên kiểu union>
{
<KDL> <tên trường>;
<KDL> <tên trường>;
………
}[<Name>];

Ví dụ, ta có thể định nghĩa kiểu số sau:

typedef union tagNumber
{
int i;
long l;
}Number;

Việc truy xuất đến một trường trong union được thực hiện hoàn toàn giống như trong struct. Giả sử có biến n kiểu Number. Khi đó, n.i cho ta một số kiểu int còn n.l cho ta một số kiểu long, nhưng cả hai đều dùng chung một vùng nhớ. Vì vậy, khi ta gán
n.l = 0xfd03;
thì giá trị của n.i cũng bị thay đổi (n.i sẽ bằng 3);
Việc dùng kiểu union rất có lợi khi cần khai báo các CTDL mà nội dung của nó thay đổi tùy trạng thái. Ví dụ để mô tả các thông tin về một con người ta có thể khai báo một kiểu dữ liệu như sau:

struct tagNguoi
{
char HoTen[35];
int NamSinh;
char NoiSinh[40];
char GioiTinh; //0: Nữ, 1: Nam
char DiaChi[50];
char Ttgd; //0:Không có gia đình, 1: Có gia đình
union {
char tenVo[35];
char tenChong[35];
}
}Nguoi;

Tùy theo người mà ta đang xét là nam hay nữ ta sẽ truy xuất thông tin qua trường có tên tenVo hay tenChong.

d. Kiểu mẫu tin (cấu trúc)
Nếu kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ thì mẫu tin là kiểu dữ liệu mà trong đó mỗi phần tử của nó là tập hợp các giá trị có thể khác cấu trúc. Kiểu mẫu tin cho phép chúng ta mô tả các đối tượng có cấu trúc phức tạp.
Khai báo tổng quát của kiểu struct như sau:

typedef struct <tên kiểu struct>
{
<KDL> <tên trường>;
<KDL> <tên trường>;
…
}[<Name>];

Ví dụ để mô tả các thông tin về một con người ta có thể khai báo một kiểu dữ liệu như sau:

struct tagNguoi
{
char HoTen[35];
int NamSinh;
char NoiSinh[40];
char GioiTinh; //0: Nữ, 1: Nam
char DiaChi[50];
char Ttgd; //0:Không có gia đình, 1: Có gia đình
}Nguoi;

Kiểu mẫu tin bổ sung những thiếu sót của kiểu mảng, giúp ta có khả năng thể hiện các đối tượng đa dạng của thể giới thực vào trong máy tính một cách dễ dàng và chính xác hơn.
• Các thao tác trên biến cấu trúc:
o Truy xuất đến 1 thành phần của biến cấu trúc:
tênbiến.tênthànhphần
Trong C, địa chỉ của một thành phần trong biến cấu trúc được xác định bởi phép toán lấy địa chỉ: &tênbiến.tênthànhphần
o Gán 2 biến cấu trúc cho nhau
• Hàm và kiểu mẫu tin:
* Đối của hàm có thể là:
- Biến mẫu tin: khi đó tham số thực tương ứng là một giá trị mẫu tin
- Tham chiếu mẫu tin: khi đó tham số thực tương ứng là một giá trị mẫu tin
- Con trỏ mẫu tin: khi đó tham số thực là địa chỉ của biến cấu trúc.
* Hàm có thể trả về:
- Giá trị mẫu tin: nguoi tênhàm(...)
- Con trỏ mẫu tin: nguoi *tênhàm(....)
Ví dụ: Nhập và in danh sách thí sinh theo thứ tự tên và họ

#include
#include
#include
#include
typedef struct
{ int ngay, thang, nam;
} date;
typedef struct
{ int sbd;
char ho[25],ten[7];
date ngaysinh;
float toan,ly,hoa;
int phongthi;
}hoso;
hoso thisinh[100];
int n;
void NhapHoso(hoso ts[],int &n)
{ int i=0;
hoso hs;
printf("\nNhap Ho so thi sinh \"Ho bang rong de ket thuc\"");
do
{
hs.sbd = n+1;
printf("\nNhap ho so cho thi sinh: %3d",hs.sbd);
printf("\nHo : "); gets(hs.ho);
if (hs.ho[0]=='\0') break;
printf("Ten: "); gets(hs.ten);
printf("Ngay sinh: ");
scanf("%d/%d/%d%*c",&hs.ngaysinh.ngay,&hs.ngaysinh.thang,
&hs.ngaysinh.nam);
printf("Diem Toan: "); scanf("%f%*c",&hs.toan);
printf("Diem Ly: "); scanf("%f%*c",&hs.ly);
printf("Diem Hoa: "); scanf("%f%*c",&hs.hoa);
printf("Phong thi: "); scanf("%d%*c",&hs.phongthi);
ts[i] = hs;
n++; i++;
}while (i<100);
}
int sosanh(const void *p, const void *q)
{
int kq;
kq = strcmp(((hoso*)p)->ten,((hoso*)q)->ten);
if (kq == 0) return strcmp(((hoso*)p)->ho,((hoso*)q)->ho);
return kq;
}
void InKQ(hoso ts[], int n)
{
int i;
qsort(ts,n,sizeof(ts[0]),sosanh);
printf("\n%-4s %-25s %-10s %-4s %-4s %-4s %-5s","SBD", "Ho Ten","Ngay sinh","Toan","Ly","Hoa","Phong");
for (i=0;i<n;i++)
printf("\n%4d %-18s %-7s %2d/%2d/%2d %4.1f %4.1f %4.1f %3d", ts[i].sbd,ts[i].ho,ts[i].ten,ts[i].ngaysinh.ngay,
ts[i].ngaysinh.thang,ts[i].ngaysinh.nam,ts[i].toan,
ts[i].ly, ts[i].hoa, ts[i].phongthi);
getch();
}
hoso Timhs(int sbd, hoso ts[], int n)
{
int i; hoso hs;
hs.sbd = hs.ngaysinh.ngay= hs.ngaysinh.thang= hs.ngaysinh.nam=0;
hs.ho[0]= hs.ten[0] = 0;
for (i=0; i<n; i++)
if ( sbd == ts[i].sbd) return ts[i];
return hs;
}
hoso *pTimhs(int sbd, hoso ts[], int n)
{
int i;
for (i=0; i<n; i++)
if (sbd==ts[i].sbd) return(&ts[i]);
return (NULL);
}
void main()
{ clrscr();
NhapHoso(thisinh,n);
InKQ(thisinh,n);
}