x9nd
05-23-2009, 05:01 PM
Bài 18 - Các kiểu dữ liệu Nâng cao và sắp xếp - Lý thuyết
Giới thiệu
- Các chương trình ứng dụng trong thực tế đòi hỏi lưu trữ dữ liệu khác nhau. Tuy nhiên, các kiểu dữ liệu của C mà chúng ta được học có thể không đủ trong trường hợp đó. Vì vậy, C cho phép tao ra các kiểu dữ liệu do người dùng định nghĩa. Một trong những kiểu như vậy gọi là cấu trúc (structure). Một cấu trúc là một tập các biến được nhóm lại với nhau có cùng tên. Một kiểu dữ liệu cũng có thể được đặt tên mới typedef.
- Các ứng dụng thường lưu trữ một số lượng dữ liêu rất lớn. Trong những trường hợp này, việc định vị một mục dữ liệu nào đó có thể tốn nhiều thời gian. Sắp xếp các giá trị theo một trật tự nào đó sẽ làm cho công việc tìm kiếm nhanh chóng và dễ dạng hơn. Trong chương này, chúng ta cũng sẽ xem một số giải thuật dùng để sắp xếp các mảng.
1. Cấu trúc
- Biến được sử dụng để lưu trữ một mẫu dữ liệu tại một thời điểm và mảng được sử dụng để lưu trữ một số mẫu dữ liệu có cùng kiểu. Tuy nhiên, một chương trình có thể yêu cầu xử lý các mục dữ liệu có kiểu khác nhau trong cùng một đơn vị chung. Ở trường hợp này, cả biến và mảng đều không thích hợp để sử dụng.
2. Định nghĩa một cấu trúc
- Việc định nghĩa cấu trúc sẽ tạo ra kiểu dữ liệu mới cho phép người dùng sử dụng chúng để khai báo các biển kiểu cấu trúc. Các biến trong cấu trúc được gọi là các phần tử hay các thành phần của cấu trúc.
- Một cách tổng quát, các phần từ của một cấu trúc quan hệ với nhau một cách logic vì chúng liên quan đến một thực thể duy nhất.
3. Khai báo biến kiểu cấu trúc
- Khi một cấu trúc đã được định nghĩa, chúng ta có thể khai báo một hoặc nhiều biến kiểu này.
Code:
struct cat books1;
- Câu lệnh này sẽ dành đủ vùng nhớ để lưu trữ tất cả các mục trong một cấu trúc. Khai báo trên thực hiện chức năng tương tự như các khai báo biến: int xyz và float ans. Nó bào với trình biên dịch dành ra một vùng lưu trữ cho một biến với kiểu nào đó và gán tên cho biến.
- Cũng như với int, float và các kiểu dữ liệu khác, ta có thể có một số bất kỳ các biến có kiểu cấu trúc đã cho. Trong một chương trình, có thể khai báo hai biến books1 và books2 có kiểu cấu trúc cat.
Code:
struc cat
{
char bk_name[25];
char author[20];
int edn;
float price;
} books1, books2
hoặc
struct cat books1, books2;
hoặc
struct cat books1
struct cat books2
- Các khai báo này sẽ dành vùng nhớ cho hai biến books1 và books2.
- Các phần tử của câu trúc được truy cập thông qua việc sử dụng toán tử chấm (.), toán tử này còn được gọi là toán tử thành viên membership. Cú pháp tổng quát dùng để truy cập một phần tử của cấu trúc là.
Code:
structure_name.element_name
4. Khởi tạo biến cấu trúc
- Giống như các biến và mảng, các biến kiểu cấu trúc có thể được khởi tạo tại thời điểm khai báo. Hình thức tương tự như cách khởi tạo mảng.
5. Thực hiện câu lệnh gán với các biến cấu trúc
- Có thể gán giá trị của một biến cấu trúc cho một biến khác cùng kiểu bằng cách sử dụng câu lệnh gán đơn giản. Chẳng hạn, nếu books1 và books2 là các biến cấu trúc có cùng kiểu, thì câu lệnh sau là hợp lệ.
Code:
books2 = books1;
- Cũng có những trường hợp không thể dùng câu lệnh gán trực tiếp, thì có thể sử dụng hàm tạo sẵn memcpy(). Nguyễn mâu hàm này là:
Code:
memcpy(char * destn, char &source, int nbytes);
- Hàm này thực hiện sao chép nbytes được lưu trữ bắt đầu từ địa chỉ source đến một vùng nhớ khác có địa chỉ bắt đầu từ destn. Hàm đòi hỏi người sử dụng phải chỉ ra kích cỡ của cấu trúc (nbytes), kích cỡ này có thể đạt được bằng cách sử dụng toán tử sizeof(). Sử dụng hàm memcpy(). có thể sao chép nội dung của books1 sang books2 như sau:
Code:
memcpy(&book2, &book1, sizeof(struct cat));
6. Cấu trúc ***g trong cấu trúc
- Một cấu trúc có thể ***g trong một cấu trúc khác. Tuy nhiên, một cấu trúc không thể ***g trong chính nó. Rất nhiều trường hợp thực tế đòi hỏi có một cấu trúc nầm trong cấu trúc khác. Mức độ ***g nhau của các cấu trúc chỉ bị giới hạn bới dung lượng hiện thời của bộ nhớ. Có thể có một cấu trúc ***g trong một cấu trúc rồi ***g trong một cấu trúc khác và v.v...Tên của các biến thường đặt theo cách gợi nhớ nội dung mà nó lưu trữ. Cũng cần nhớ rằng nếu một cấu trúc được ***g trong một cấu trúc khác, nó phải được khai báo trước cấu trúc sẽ sử dụng nó.
7. Truyền tham số kiểu câu trúc
- Kiểu tham số của một hàm có thể là cấu trúc. Đây là một phương tiện hữu dụng khi ta muốn truyền một nhóm các thành phần dữ liệu quan hệ logic với nhau thông qua một biến thay vì phải truyền từng thành phần một. Tuy nhiên, khi một cấu trúc được sử dụng như một tham số, cần phải lưu ý rằng kiểu của tham số thực phải trùng với kiểu của tham số hình thức.
- Có thể định nghĩa một cấu trúc mà không có nhãn. Điều này hữu dụng khi một biến được khia báo cùng lúc với định nghĩa cấu trúc của nó. Nhãn sẽ không cần thiết trong trường hợp này.
8. Mảng các cấu trúc
- Một trong những cách sử dụng thông thường của cấu trúc là mảng cấu trúc. Để khai báo một mảng các cấu trúc, một cấu trúc sẽ được định nghĩa trước, và sau đố một biến mảng có kiểu đó sẽ được khai báo. Giống như tất cả các biến, mảng các cấu trúc bắt đầu tại chỉ số 0. Tên mảng và chỉ số nằm trong cặp dấu ngoặc vuông theo sau tên mảng đại diện cho một phần tử của mảng. Sau lệnh khai báo ở trên, phần tử này là một cấu trúc theo định nghĩa của nó.
9. Khởi tạo mảnh cấu trúc
- Một mảng kiểu bất kỳ được khai tạo bằng cách liệt kê danh sách giá trị của các phần từ trong một cặp dấu móc. Luật này vẫn đúng khi các phần tử mảng là các cấu trúc. Vì mỗi phần tử của mảng là một cấu trúc, mà giá trị khỏi tạo của một cấu trúc được đặt trong cặp dấu móc, nên ta phải sử dụng các cặp dấu móc ***g nhau khi khởi tạo mảng các cấu trúc
Code:
struct unit
{
char ch;
int i;
}
struct unit series[3] =
{
{'a', 100},
{'b', 200},
{'c', 300},
}
- Đoạn lệnh này khai báo series là một mảng cấu trúc gồm 3 phần tử, mỗi phần tử có kiểu unit. Khi khởi tạo, vì mỗi phần tử là một cấu trúc nên giá trị của nó được đặt trong cặp dấu móc, và toàn bộ giá trị các phần tử được đóng trong dấu móc để cho biết đang khởi tạo một mảng.
10. Con trỏ cấu trúc
- C hỗ trợ con trỏ cấu trúc, nhưng có một số khía cạch đặc biệt đối với con trỏ cấu trúc. Giống như các kiểu con trỏ khác, con trỏ cấu trúc khai báo bằng cách đặt dấu * trước tên của biến cấu trúc. Ví dụ, câu lệnh sau đây khai báo con trỏ ptr_bk của kiểu cấu trúc cat.
Code:
struct cat *ptr_bk
- Bây giờ để gán địa chỉ của biến cấu trúc books kiểu cat cho ptr_bk, câu lệnh sẽ như sau:
Code:
ptr_bk = &books;
- Toán tử -> được dùng để truy cạp đến phần tử của một con trỏ cấu trúc. Toán tử này là một tổ hợp của dấu trừ (-) và dấu lớn hơn (>) và nó được biết đến như một toán tử tổ hợp. Ví dụ như, trường author có thể được truy cập theo một trong các cách sau đây:
Code:
ptr_bk -> author
hoặc
books.author
hoặc
(*ptr_bk).author
- Trong biểu thức cuối cùng, dấu ngoặc là bắt buộc vì toán tử chấm (.) có độ ưu tiên cao hơn toán tử vô hướng (*). Không có dấu ngoặc, trình biên dịch sẽ sinh ra một lỗi, vì toán tử chấm không được áp dụng trên biến con trỏ ptr_bk.
- Cũng như tất cả các khai báo con trỏ khác, việc khai báo một con trỏ chỉ cấp phát không gian cho con trỏ mà không cấp phát cho nơi nó trỏ đến. Vì vậy, khi một con trỏ cấu trúc được khai báo, không gian được cấp phát là dành cho địa chỉ của cấu trúc chứ không phải là bản thân cấu trúc.
11. Truyền con tro cấu trúc như là các tham số:
- Có thể sử dụng các con trỏ cấu trúc như là tham số của hàm. Tại thời điểm gọi hàm, một con trỏ cấu trúc hoặc địa chỉ của một biến cấu trúc được truyền vào hàm. Điều này cho phép một hàm có thể sửa đổi các phần tử của cấu trúc một cách trực tiếp.
12. Từ khóa typedef
- Một kiểu dữ liệu mới có thể được định nghĩa bằng cách sử dụng từ khóa typedef. Từ khóa này không tạo ra một kiểu dữ liệu mới, mà định nghĩa một tên mới cho một kiểu dữ liệu đã có. Cú pháp tổng quát của câu lệnh typedef là:
Code:
typedef type name;
- Trong đố type là một kiểu dữ liệu cho phép bất kỳ và name là một tên mới cho kiểu dữ liệu này. Đặc biệt tiện lợi khi định nghĩa các cấu trúc, vì ta không cần nhắc lại nhãn struct mỗi khi một sử dụng cấu trúc.
13. Sắp xếp mảng (Sorting Arrays)
- Sắp xếp có nghĩa là xếp mảng dữ theo một thứ tự xác định như tăng dần hay giảm dần. Khi mảng đã được sắp xếp, việc tìm kiếm trên mảng trở nên dễ dàng hơn.
- Có một số phương pháp để sắp xếp mảng. Chúng ta sẽ xem xét hai phương pháp sau đây:
+ Bubble Sort
+ Insertion Sort
- Các phương pháp được trình bày sau đây áp dụng với sắp xếp thứ tự tăng dần (trong diễn dàn có một khi vực dành riêng cho các thuật toán sắp xếp, các bạn có thể tham khảo, sách của aptech viết chỗ này hơn chuối và thiếu nhiều)
Hết bài 18
Bài tập tự làm
1. Viết một chương trình C để cài đặt một hệ thống quản lý kho. Hãy lưu trữ mã số, tên hàng, giá cả và số lượng đang có của mỗi món hàng trong một cấu trúc. Nhập chi tiết của 5 món hàng vào một mảng các cấu trúc và hiển thị tên từng món hàng và tổng giả trị của nó. Ở cuối chương trình, hãy hiển thị tổng giá trị của kho hàng.
2. Viết một chương trình C để lưu trữ các biến và điểm số của 5 sinh viên trong một mảng cấu trúc. Hãy sắp xếp mảng cấu trúc theo thứ tự điểm số giảm dần. Hiển thị 3 điểm số cao nhất.
Giới thiệu
- Các chương trình ứng dụng trong thực tế đòi hỏi lưu trữ dữ liệu khác nhau. Tuy nhiên, các kiểu dữ liệu của C mà chúng ta được học có thể không đủ trong trường hợp đó. Vì vậy, C cho phép tao ra các kiểu dữ liệu do người dùng định nghĩa. Một trong những kiểu như vậy gọi là cấu trúc (structure). Một cấu trúc là một tập các biến được nhóm lại với nhau có cùng tên. Một kiểu dữ liệu cũng có thể được đặt tên mới typedef.
- Các ứng dụng thường lưu trữ một số lượng dữ liêu rất lớn. Trong những trường hợp này, việc định vị một mục dữ liệu nào đó có thể tốn nhiều thời gian. Sắp xếp các giá trị theo một trật tự nào đó sẽ làm cho công việc tìm kiếm nhanh chóng và dễ dạng hơn. Trong chương này, chúng ta cũng sẽ xem một số giải thuật dùng để sắp xếp các mảng.
1. Cấu trúc
- Biến được sử dụng để lưu trữ một mẫu dữ liệu tại một thời điểm và mảng được sử dụng để lưu trữ một số mẫu dữ liệu có cùng kiểu. Tuy nhiên, một chương trình có thể yêu cầu xử lý các mục dữ liệu có kiểu khác nhau trong cùng một đơn vị chung. Ở trường hợp này, cả biến và mảng đều không thích hợp để sử dụng.
2. Định nghĩa một cấu trúc
- Việc định nghĩa cấu trúc sẽ tạo ra kiểu dữ liệu mới cho phép người dùng sử dụng chúng để khai báo các biển kiểu cấu trúc. Các biến trong cấu trúc được gọi là các phần tử hay các thành phần của cấu trúc.
- Một cách tổng quát, các phần từ của một cấu trúc quan hệ với nhau một cách logic vì chúng liên quan đến một thực thể duy nhất.
3. Khai báo biến kiểu cấu trúc
- Khi một cấu trúc đã được định nghĩa, chúng ta có thể khai báo một hoặc nhiều biến kiểu này.
Code:
struct cat books1;
- Câu lệnh này sẽ dành đủ vùng nhớ để lưu trữ tất cả các mục trong một cấu trúc. Khai báo trên thực hiện chức năng tương tự như các khai báo biến: int xyz và float ans. Nó bào với trình biên dịch dành ra một vùng lưu trữ cho một biến với kiểu nào đó và gán tên cho biến.
- Cũng như với int, float và các kiểu dữ liệu khác, ta có thể có một số bất kỳ các biến có kiểu cấu trúc đã cho. Trong một chương trình, có thể khai báo hai biến books1 và books2 có kiểu cấu trúc cat.
Code:
struc cat
{
char bk_name[25];
char author[20];
int edn;
float price;
} books1, books2
hoặc
struct cat books1, books2;
hoặc
struct cat books1
struct cat books2
- Các khai báo này sẽ dành vùng nhớ cho hai biến books1 và books2.
- Các phần tử của câu trúc được truy cập thông qua việc sử dụng toán tử chấm (.), toán tử này còn được gọi là toán tử thành viên membership. Cú pháp tổng quát dùng để truy cập một phần tử của cấu trúc là.
Code:
structure_name.element_name
4. Khởi tạo biến cấu trúc
- Giống như các biến và mảng, các biến kiểu cấu trúc có thể được khởi tạo tại thời điểm khai báo. Hình thức tương tự như cách khởi tạo mảng.
5. Thực hiện câu lệnh gán với các biến cấu trúc
- Có thể gán giá trị của một biến cấu trúc cho một biến khác cùng kiểu bằng cách sử dụng câu lệnh gán đơn giản. Chẳng hạn, nếu books1 và books2 là các biến cấu trúc có cùng kiểu, thì câu lệnh sau là hợp lệ.
Code:
books2 = books1;
- Cũng có những trường hợp không thể dùng câu lệnh gán trực tiếp, thì có thể sử dụng hàm tạo sẵn memcpy(). Nguyễn mâu hàm này là:
Code:
memcpy(char * destn, char &source, int nbytes);
- Hàm này thực hiện sao chép nbytes được lưu trữ bắt đầu từ địa chỉ source đến một vùng nhớ khác có địa chỉ bắt đầu từ destn. Hàm đòi hỏi người sử dụng phải chỉ ra kích cỡ của cấu trúc (nbytes), kích cỡ này có thể đạt được bằng cách sử dụng toán tử sizeof(). Sử dụng hàm memcpy(). có thể sao chép nội dung của books1 sang books2 như sau:
Code:
memcpy(&book2, &book1, sizeof(struct cat));
6. Cấu trúc ***g trong cấu trúc
- Một cấu trúc có thể ***g trong một cấu trúc khác. Tuy nhiên, một cấu trúc không thể ***g trong chính nó. Rất nhiều trường hợp thực tế đòi hỏi có một cấu trúc nầm trong cấu trúc khác. Mức độ ***g nhau của các cấu trúc chỉ bị giới hạn bới dung lượng hiện thời của bộ nhớ. Có thể có một cấu trúc ***g trong một cấu trúc rồi ***g trong một cấu trúc khác và v.v...Tên của các biến thường đặt theo cách gợi nhớ nội dung mà nó lưu trữ. Cũng cần nhớ rằng nếu một cấu trúc được ***g trong một cấu trúc khác, nó phải được khai báo trước cấu trúc sẽ sử dụng nó.
7. Truyền tham số kiểu câu trúc
- Kiểu tham số của một hàm có thể là cấu trúc. Đây là một phương tiện hữu dụng khi ta muốn truyền một nhóm các thành phần dữ liệu quan hệ logic với nhau thông qua một biến thay vì phải truyền từng thành phần một. Tuy nhiên, khi một cấu trúc được sử dụng như một tham số, cần phải lưu ý rằng kiểu của tham số thực phải trùng với kiểu của tham số hình thức.
- Có thể định nghĩa một cấu trúc mà không có nhãn. Điều này hữu dụng khi một biến được khia báo cùng lúc với định nghĩa cấu trúc của nó. Nhãn sẽ không cần thiết trong trường hợp này.
8. Mảng các cấu trúc
- Một trong những cách sử dụng thông thường của cấu trúc là mảng cấu trúc. Để khai báo một mảng các cấu trúc, một cấu trúc sẽ được định nghĩa trước, và sau đố một biến mảng có kiểu đó sẽ được khai báo. Giống như tất cả các biến, mảng các cấu trúc bắt đầu tại chỉ số 0. Tên mảng và chỉ số nằm trong cặp dấu ngoặc vuông theo sau tên mảng đại diện cho một phần tử của mảng. Sau lệnh khai báo ở trên, phần tử này là một cấu trúc theo định nghĩa của nó.
9. Khởi tạo mảnh cấu trúc
- Một mảng kiểu bất kỳ được khai tạo bằng cách liệt kê danh sách giá trị của các phần từ trong một cặp dấu móc. Luật này vẫn đúng khi các phần tử mảng là các cấu trúc. Vì mỗi phần tử của mảng là một cấu trúc, mà giá trị khỏi tạo của một cấu trúc được đặt trong cặp dấu móc, nên ta phải sử dụng các cặp dấu móc ***g nhau khi khởi tạo mảng các cấu trúc
Code:
struct unit
{
char ch;
int i;
}
struct unit series[3] =
{
{'a', 100},
{'b', 200},
{'c', 300},
}
- Đoạn lệnh này khai báo series là một mảng cấu trúc gồm 3 phần tử, mỗi phần tử có kiểu unit. Khi khởi tạo, vì mỗi phần tử là một cấu trúc nên giá trị của nó được đặt trong cặp dấu móc, và toàn bộ giá trị các phần tử được đóng trong dấu móc để cho biết đang khởi tạo một mảng.
10. Con trỏ cấu trúc
- C hỗ trợ con trỏ cấu trúc, nhưng có một số khía cạch đặc biệt đối với con trỏ cấu trúc. Giống như các kiểu con trỏ khác, con trỏ cấu trúc khai báo bằng cách đặt dấu * trước tên của biến cấu trúc. Ví dụ, câu lệnh sau đây khai báo con trỏ ptr_bk của kiểu cấu trúc cat.
Code:
struct cat *ptr_bk
- Bây giờ để gán địa chỉ của biến cấu trúc books kiểu cat cho ptr_bk, câu lệnh sẽ như sau:
Code:
ptr_bk = &books;
- Toán tử -> được dùng để truy cạp đến phần tử của một con trỏ cấu trúc. Toán tử này là một tổ hợp của dấu trừ (-) và dấu lớn hơn (>) và nó được biết đến như một toán tử tổ hợp. Ví dụ như, trường author có thể được truy cập theo một trong các cách sau đây:
Code:
ptr_bk -> author
hoặc
books.author
hoặc
(*ptr_bk).author
- Trong biểu thức cuối cùng, dấu ngoặc là bắt buộc vì toán tử chấm (.) có độ ưu tiên cao hơn toán tử vô hướng (*). Không có dấu ngoặc, trình biên dịch sẽ sinh ra một lỗi, vì toán tử chấm không được áp dụng trên biến con trỏ ptr_bk.
- Cũng như tất cả các khai báo con trỏ khác, việc khai báo một con trỏ chỉ cấp phát không gian cho con trỏ mà không cấp phát cho nơi nó trỏ đến. Vì vậy, khi một con trỏ cấu trúc được khai báo, không gian được cấp phát là dành cho địa chỉ của cấu trúc chứ không phải là bản thân cấu trúc.
11. Truyền con tro cấu trúc như là các tham số:
- Có thể sử dụng các con trỏ cấu trúc như là tham số của hàm. Tại thời điểm gọi hàm, một con trỏ cấu trúc hoặc địa chỉ của một biến cấu trúc được truyền vào hàm. Điều này cho phép một hàm có thể sửa đổi các phần tử của cấu trúc một cách trực tiếp.
12. Từ khóa typedef
- Một kiểu dữ liệu mới có thể được định nghĩa bằng cách sử dụng từ khóa typedef. Từ khóa này không tạo ra một kiểu dữ liệu mới, mà định nghĩa một tên mới cho một kiểu dữ liệu đã có. Cú pháp tổng quát của câu lệnh typedef là:
Code:
typedef type name;
- Trong đố type là một kiểu dữ liệu cho phép bất kỳ và name là một tên mới cho kiểu dữ liệu này. Đặc biệt tiện lợi khi định nghĩa các cấu trúc, vì ta không cần nhắc lại nhãn struct mỗi khi một sử dụng cấu trúc.
13. Sắp xếp mảng (Sorting Arrays)
- Sắp xếp có nghĩa là xếp mảng dữ theo một thứ tự xác định như tăng dần hay giảm dần. Khi mảng đã được sắp xếp, việc tìm kiếm trên mảng trở nên dễ dàng hơn.
- Có một số phương pháp để sắp xếp mảng. Chúng ta sẽ xem xét hai phương pháp sau đây:
+ Bubble Sort
+ Insertion Sort
- Các phương pháp được trình bày sau đây áp dụng với sắp xếp thứ tự tăng dần (trong diễn dàn có một khi vực dành riêng cho các thuật toán sắp xếp, các bạn có thể tham khảo, sách của aptech viết chỗ này hơn chuối và thiếu nhiều)
Hết bài 18
Bài tập tự làm
1. Viết một chương trình C để cài đặt một hệ thống quản lý kho. Hãy lưu trữ mã số, tên hàng, giá cả và số lượng đang có của mỗi món hàng trong một cấu trúc. Nhập chi tiết của 5 món hàng vào một mảng các cấu trúc và hiển thị tên từng món hàng và tổng giả trị của nó. Ở cuối chương trình, hãy hiển thị tổng giá trị của kho hàng.
2. Viết một chương trình C để lưu trữ các biến và điểm số của 5 sinh viên trong một mảng cấu trúc. Hãy sắp xếp mảng cấu trúc theo thứ tự điểm số giảm dần. Hiển thị 3 điểm số cao nhất.