Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
Bài 10 - CẤU TRÚC DỮ LIỆU DO NGƯỜI DÙNG TỰ ĐỊNH NGHĨA
tải về 1.56 Mb.
|
- Điều hướng trang này:
- I. Cấu trúc dữ liệu do người dùng tự định nghĩa
- 2. Khai báo biến cấu trúc
- 3. Các thao tác trên biến kiểu cấu trúc
- 4. Con trỏ cấu trúc
- 5. Cấu trúc với thành phần kiểu bit
- 6. Câu lệnh typedef
- 7. Hàm sizeof()
Bài 10 - CẤU TRÚC DỮ LIỆU DO NGƯỜI DÙNG TỰ ĐỊNH NGHĨANội dung bài học I. Cấu trúc dữ liệu do người dùng tự định nghĩa 1 Khái niệm 2. Khai báo biến cấu trúc 3. Các thao tác trên biến kiểu cấu trúc 4. Con trỏ cấu trúc II. Kiểu ngăn xếp 1. Khái niệm 2. Các thao tác cơ bản 3. Cài đặt 4. Ứng dụng III. Kiểu hàng đợi 1. Khái niệm 2. Các thao tác cơ bản 3. Cài đặt 4. Ứng dụng IV. Kiểu hợp V. Kiểu liệt kê VI. Tóm tắt nội dung bài học VII. Bài tập I. Cấu trúc dữ liệu do người dùng tự định nghĩa1 Khái niệmVấn đề: Làm thế nào để mô tả một SINH VIÊN với các thông tin:
Hoặc làm thế nào để mô tả NGÀY THÁNG bao gồm các thông tin:
=> Hầu hết các ngôn ngữ lập trình trong đó có C/C++ cho phép người lập trình tự định nghĩa ra cấu trúc mới theo nhu cầu sử dụng từ những kiểu dữ liệu đã có hoặc đã định nghĩa trước đó. Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu khác nhau, mỗi thành phần được gọi là một trường (field). Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng kiểu còn các phần tử của kiểu cấu trúc có thể có kiểu khác nhau. Hình ảnh sau là của kiểu cấu trúc với 7 trường
còn kiểu mảng có dạng:
Cú pháp 1: struct { …….. }; Cú pháp 2: typedef struct {
……..
} Trong đó:
Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm. struct KieuNgayThang { unsigned char Ngay; unsigned char Thang; unsigned int Nam; }; typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } KieuNgayThang;
struct KieuSinhVien { char MSSV[10]; char HoTen[40]; struct KieuNgayThang NgaySinh; int Phai; char DiaChi[40]; }; typedef struct { char MSSV[10]; char HoTen[40]; KieuNgayThang NgaySinh; int Phai; char DiaChi[40]; } KieuSinhVien;
2. Khai báo biến cấu trúcViệc khai báo biến cấu trúc cũng tương tự như khai báo biến thuộc kiểu dữ liệu chuẩn. Cú pháp:
struct
Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc KieuNgayThang; biến SV có kiểu cấu trúc KieuSinhVien. struct KieuNgayThang NgaySinh; struct KieuSinhVien SV; KieuNgayThang NgaySinh; KieuSinhVien SV;
Khi sử dụng cách truy xuất theo kiểu này, các thao tác trên Ví dụ1: Viết chương trình cho phép đọc dữ liệu từ bàn phím cho biến mẩu tin SinhVien và in biến mẩu tin đó lên màn hình: #include #include #include typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } KieuNgayThang; typedef struct { char MSSV[10]; char HoTen[40]; KieuNgayThang NgaySinh; int Phai; char DiaChi[40]; } KieuSinhVien; /* Hàm in lên màn hình 1 m?u tin SinhVien*/ void InSV(KieuSinhVien s) { printf(“MSSV: | Ho va ten | Ngay Sinh | Dia chi\n”); printf(“%s | %s | %d-%d-%d | %s\n”,s.MSSV,s.HoTen, s.NgaySinh.Ngay,s.NgaySinh.Thang,s.NgaySinh.Nam,s.DiaChi); } int main() { KieuSinhVien SV, s; printf(“Nhap MSSV: “);gets(SV.MSSV); printf(“Nhap Ho va ten: “);gets(SV.HoTen); printf(“Sinh ngay: “);scanf(“%d”,&SV.NgaySinh.Ngay); printf(“Thang: “);scanf(“%d”,&SV.NgaySinh.Thang); printf(“Nam: “);scanf(“%d”,&SV.NgaySinh.Nam); printf(“Gioi tinh (0: Nu), (1: Nam): “);scanf(“%d”,&SV.Phai); fflush(stdin); printf(“Dia chi: “);gets(SV.DiaChi); InSV(SV); s=SV;
InSV(s); getch(); return 0; }
Ví dụ 2: Nhập vào hai số phức và tính tổng của chúng. Ta biết rằng số phức là một cặp (a,b) trong đó a, b là các số thực, a gọi là phần thực, b là phần ảo. (Đôi khi người ta cũng viết số phức dưới dạng a + ib trong đó i là một đơn vị ảo có tính chất i2=-1). Gọi số phức c1=(a1, b1) và c2=(a2,b2) khi đó tổng của hai số phức c1 và c2 là một số phức c3 mà c3=(a1+a2, b1+b2). Với hiểu biết như vậy ta có thể xem mỗi số phức là một cấu trúc có hai trường, một trường biểu diễn cho phần thực, một trường biểu diễn cho phần ảo. Việc tính tổng của hai số phức được tính bằng cách lấy phần thực cộng với phần thực và phần ảo cộng với phần ảo. #include #include #include typedef struct { float Thuc; float Ao; } SoPhuc; /* Ham in so phuc len man hinh*/ void InSoPhuc(SoPhuc p) { printf(“%.2f + i%.2f\n”,p.Thuc,p.Ao); } int main() { SoPhuc p1,p2,p; printf(“Nhap so phuc thu nhat:\n”); printf(“Phan thuc: “);scanf(“%f”,&p1.Thuc); printf(“Phan ao: “);scanf(“%f”,&p1.Ao); printf(“Nhap so phuc thu hai:\n”); printf(“Phan thuc: “);scanf(“%f”,&p2.Thuc); printf(“Phan ao: “);scanf(“%f”,&p2.Ao); printf(“So phuc thu nhat: “); InSoPhuc(p1); printf(“So phuc thu hai: “); InSoPhuc(p2); p.Thuc = p1.Thuc+p2.Thuc; p.Ao = p1.Ao + p2.Ao; printf(“Tong 2 so phuc: “); InSoPhuc(p); getch(); return 0; }
Việc khởi tạo cấu trúc có thể được thực hiện trong lúc khai báo biến cấu trúc. Các trường của cấu trúc được khởi tạo được đạt giữa 2 dấu { và }, chúng được phân cách nhau bởi dấu phẩy (,). Ví dụ: Khởi tạo biến cấu trúc NgaySinh: struct KieuNgayThang NgaySinh ={29, 8, 1986}; 4. Con trỏ cấu trúcKhai báo Việc khai báo một biến con trỏ kiểu cấu trúc cũng tương tự như khi khai báo một biến con trỏ khác, nghĩa là đặt thêm dấu * vào phía trước tên biến. Cú pháp: struct Ví dụ: Ta có thể khai báo một con trỏ cấu trúc kiểu NgayThang như sau: struct NgayThang *p; /* NgayThang *p; // Nếu có định nghĩa kiểu */
Khi khai báo biến con trỏ cấu trúc, biến con trỏ chưa có địa chỉ cụ thể. Lúc này nó chỉ mới được cấp phát 2 byte để lưu giữ địa chỉ và được ghi nhận là con trỏ chỉ đến 1 cấu trúc, nhưng chưa chỉ đến 1 đối tượng cụ thể. Muốn thao tác trên con trỏ cấu trúc hợp lệ, cũng tương tự như các con trỏ khác, ta phải:
Ví dụ: Sau khi khởi tạo giá trị của cấu trúc: struct NgayThang Ngay = {29,8,1986}; p = &Ngay; lúc này biến con trỏ p đã chứa địa chỉ của Ngay. Truy cập các thành phần của cấu trúc đang được quản lý bởi con trỏ Để truy cập đến từng trường của 1 cấu trúc thông qua con trỏ của nó, ta sử dụng toán tử dấu mũi tên (->: dấu - và dấu >). Ngoài ra, ta vẫn có thể sử dụng đến phép toán * để truy cập vùng dữ liệu đang được quản lý bởi con trỏ cấu trúc để lấy thông tin cần thiết. Ví dụ: Sử dụng con trỏ cấu trúc. #include #include typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } NgayThang; int main() { NgayThang Ng={29,8,1986}; NgayThang *p; p=&Ng;
printf(“Truy cap binh thuong %d-%d-%d\n”, Ng.Ngay,Ng.Thang,Ng.Nam); printf(“Truy cap qua con tro %d-%d-%d\n”, p->Ngay,p->Thang,p->Nam); printf(“Truy cap qua vung nho con tro %d-%d-%d\n”, (*p).Ngay,(*p).Thang,(*p).Nam); getch(); return 0; } - Cho phép sử dụng cấu trúc, con trỏ cấu trúc là đối số của hàm như các loại biến khác - Cho phép hàm xây dựng trả về là kiểu cấu trúc Ví dụ : Xử lý danh sách sinh viên, sử dụng hàm với đối số là cấu trúc #include #include //Ngay thang struct Ngaythang { int ng ; int th ;
int nam ; }; //Sinh vien struct Sinhvien { char hoten[25] ; Ngaythang ns; int gt;
float diem ; } ;
//cac ham xu ly int sua(Sinhvien &r) ; int in(Sinhvien x) ; int nhap(Sinhvien *p) ; int nhapds(Sinhvien *a, int n) ; int suads(Sinhvien *a, int n) ; int inds(const Sinhvien *a, int n) ; // struct Sinhvien a[10]; int main() { nhap(a); // in(a[1]); // sua(a[1]); nhapds(a,9); suads(a,9); inds(a,9); getch();
return 0; } ///trien khai cac ham int sua(Sinhvien &r) { int chon; do { printf("1: Sua ho ten\n2: Sua ngay sinh\n3:Sua gioi tinh\n4:Sua diem\n5:In\n0: Ket thuc\n"); scanf("%d",&chon); switch (chon) { case 1:
printf("Nhap ho ten:"); scanf("%s",r.hoten); break; case 2:
printf("Nhap ngay thang nam sinh:"); scanf("%d%d%d",&r.ns.ng,&r.ns.th,&r.ns.nam); break; case 3:
printf("Nhap gioi tinh 0:Nu 1:Nam:"); scanf("%d",&r.gt) ; break; case 4:
printf("Nhap diem:"); scanf("%f",&r.diem); break; case 5:
printf("Sinh vien:"); in(r);
break; case 0:
break; default:
printf("Nhap gia tri khong dung\n"); break;
} } while (chon) ; return 0; } //////// int in(Sinhvien x) { printf("Ho ten :%s\nNgay sinh %d/%d/%d\n",x.hoten,x.ns.ng, x.ns.th, x.ns.nam) ; printf("Gioi tinh :%s\nDiem :%f\n",(x.gt==1) ?"Nam" :"Nu",x.diem) ; return 0; }
int nhap(Sinhvien *p) { printf("Nhap ho va ten: "); scanf("%s",p->hoten); printf("Nhap ngay sinh (ngay thang nam): "); scanf("%d%d%d", &p->ns.ng ,&p->ns.th,&p->ns.nam); printf("Gioi tinh 0: nu, 1: nam: "); scanf("%d",& p->gt); printf("Diem: "); scanf("%f",& p->diem); return 0; } //////
int nhapds(Sinhvien *a, int n) { for (int i=1; i<=n; i++) nhap(&a[i]) ; return 0; } ///// int suads(Sinhvien *a, int n) { int chon; do { printf("\nNhap phan tu duoc su tu 1 den %d, gia tri khac thoat:",n); scanf("%d",&chon); if(chon>0 &&chon<=n) { sua(a[chon]) ; } }while(chon>0 && chon<=n); return 0; } ////////// int inds(const Sinhvien *a, int n) { for (int i=1; i<=n; i++) in(a[i]) ; return 0; }
Để tiết kiệm trong lưu trữ, trong ngôn ngữ lập trình C cho phép khai báo các trường của cấu trúc với số lượng bit xác định không phụ thuộc vào số lượng bit các kiểu dữ liệu chuẩn. Một trường bit là một khai báo trường int và thêm dấu: cùng số bit n theo sau, trong đó 0 ≤ n < 15. Ví dụ do độ lớn của ngày không vượt quá 31, tháng không vuợt quá 12 nên 2 trường này trong cấu trúc ngày tháng có thể khai báo tiết kiệm hơn bằng 5 và 4 bit như sau: struct Date { int ng: 5; int th: 4; int nam:14; } ;
b. Đặc điểm Cần chú ý các đặc điểm sau của một cấu trúc có chứa trường bit: − Các bit được bố trí liên tục trên dãy các byte. − Kiểu trường bit phải là int (signed hoặc unsigned). − Độ dài mỗi trường bit không quá 16 bit. − Có thể bỏ qua một số bit nếu bỏ trống tên trường, ví dụ: struct tu { int: 8;
int x:8; } mỗi một biến cấu trúc theo khai báo trên gồm 2 byte, bỏ qua không sử dụng byte thấp và trường x chiếm byte (8 bit) cao. − Không cho phép lấy địa chỉ của thành phần kiểu bit. − Không thể xây dựng được mảng kiểu bit. − Không được trả về từ hàm một thành phần kiểu bit. Ví dụ nếu b là một thành phần của biến cấu trúc x có kiểu bit thì câu lệnh sau là sai: return x.b ; // sai tuy nhiên có thể thông qua biến phụ như sau: int tam = x.b ; return tam ; − Tiết kiệm bộ nhớ − Dùng trong kiểu union để lấy các bit của một từ (xem ví dụ trong phần kiểu hợp). 6. Câu lệnh typedefĐể thuận tiện trong sử dụng, thông thường các kiểu được NSD tạo mới sẽ được gán cho một tên kiểu bằng câu lệnh typedef như sau: typedef Ví dụ: Để tạo kiểu mới có tên Bool và chỉ chứa giá trị nguyên (thực chất chỉ cần 2 giá trị 0, 1), ta có thể khai báo: typedef int Bool; khai báo này cho phép xem Bool như kiểu số nguyên. hoặc có thể đặt tên cho kiểu ngày tháng là Date với khai báo sau: typedef struct Date { int ng; int th;
int nam; };
khi đó ta có thể sử dụng các tên kiểu này trong các khai báo (ví dụ tên kiểu của đối, của giá trị hàm trả lại …). 7. Hàm sizeof()Hàm trả lại kích thước của một biến hoặc kiểu. Ví dụ: Bool a, b; Date x, y, z[50]; printf("%d,%d,%d",sizeof(a),sizeof(b),sizeof(Bool)) ; // in 2,2,2 printf("Số phần tử của z =%d ",sizeof(z) / sizeof(Date)); // in 50
Каталог: files -> FileMonHoc FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam tải về 1.56 Mb. Chia sẻ với bạn bè của bạn:
|