Giáo án Tin học Lớp 11 - Bài 19: Các Kiểu dữ liệu Nâng cao và Sắp xếp

 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 đã có. Cú pháp tổng quát của câu lệnh typedef là:
	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.
Tên mới được định nghĩa, là một tên thêm vào, chứ không phải là tên thay thế, cho kiểu dữ liệu đã có. Ví dụ như, một tên mới cho float có thể được định nghĩa theo cách sau:
	typedef float deci;
Câu lệnh này sẽ báo cho trình biên dịch biết để nhận dạng deci là một tên khác của float. Một biến float có thể được định nghĩa sử dụng deci như sau:
	deci amt;
Ở đây, amt là một biến số thực kiểu deci, chính là một tên khác của float. Sau khi được định nghĩa, deci có thể được sử dụng như một kiểu dữ liệu trong câu lệnh typedef để gán một tên khác cho kiểu float. Chẳng hạn,
	typedef deci point;
Câu lệnh trên báo cho trình biên dịch biết để nhận dạng point như là một tên khác của deci, cũng chính là một tên khác của float. Đặc tính typedef đặ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. Vì vậy, cấu trúc có thể được liên hệ một cách chính xác hơnKhi đó việc sử dụng cấu trúc sẽ thuận tiện hơn. Thêm vào đó, tên cho một kiểu cấu trúc do người dùng định nghĩa thường gợi nhớ đến mục đích của cấu trúc trong chương trình. Một cách tổng quát, một cấu trúc do người dùng định nghĩa có thể được viết như sau:
	typedef struct new_type
	{
	type var1;
	type var2;
	}
Ở đây, new_type là kiểu cấu trúc do người dùng định nghĩa và nó không phải là một biến cấu trúc. Bây giờ, các biến kiểu cấu trúc có thể được định nghĩa theo kiểu dữ liệu mới. Một ví dụ như sau:Ví dụ:
	typedef struct
	{
	int day;
	int month;
	int year;
	} date;
	date due_date;	
Ở đây, date là một kiểu dữ liệu mới và due_date là một biến kiểu date.
Cần nhớ rằng typedef không thể sử dụng với storage classes.
19.3	Sắp xếp mảng (Sorting Arrays)
Sắp xếp có nghĩa là xếp mảng dữ liệu theo một thứ tự đãxác định như tăng dần hay giảm dần. Dữ liệu trong một mảng sẽ dễ dàng tìm được nếu mảng được sắp xếpKhi 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 đối với mảng sắp xếp theo thứ tự tăng dần
19.3.1	Bubble Sort 
Tên Bản thân tên của quá trình sắp xếp này đã mô tả cách thức nó làm việc. Ở đây, việc so sánh bắt đầu từ phần tử dưới cùng và phần tử có giá trị nhỏ hơn sẽ nổi bọt dần lên trên đỉnh. Quá trình sắp xếp một mảng 5-phần tử theo thứ tự tăng dần được cho như sau:
So sánh giá trị trong phần tử thứ 5 với giá trị trong phần tử thứ 4.
Nếu giá trị trong phần tử thứ 5 nhỏ hơn giá trị trong phần tử thứ 4, thì giá trị trong hai phần tử sẽ được hoántrao đổi.
Kế tiếp, so sánh giá trị trong phần tử thứ 4 với giá trị trong phần tử thứ 3, và theo cách tương tự, các giá trị sẽ được traohoán đổi nếu giá trị trong phần tử dướisau là nhỏ hơn giá trị của phần tử trướcên.
So sánh giá trị trong phần tử thứ 3 với giá trị trong phần tử thứ 2, và quá trình so sánh và traohoán đổi này cứ thế tiếp tục.
Sau một lượt, giá trị nhỏ nhất sẽ được dờiđặt vào đến phần tử đầu tiên. Một cách nôm na, có thể phát biểu rằng giá trị nhỏ nhất đã ‘nổi lên’.
Trong lượt kế tiếp, việc so sánh lại bắt đầu với phần tử thấp nhấtcuối cùng, và so sánh dần lên đến phần tử thứ 2. Vì phần tử thứ nhất đã chứa phần tửgiá trị nhỏ nhất, không cần thiết phải so sánh nó nữa.
Với cách như vậy, ở cuối quá trình sắp xếp, các phần tử nhỏ hơn sẽ ‘nổi bọt’ dần lên đỉnhtrên, trong khi các giá trị lớn hơn sẽ ‘chìm xuống’. Hình 19.2 minh họa cho phương pháp buble sort.
23
23
23
23
9
90
90
90
9
23
9
9
9
90
90
25
16
16
16
16
16
25
25
25
25
9
9
9
9
23
23
23
16
90
90
16
23
16
16
90
90
25
25
25
25
9
9
9
16
16
16
23
23
23
90
25
25
25
90
90
9
9
16
16
23
23
25
25
90
90
9
16
23
25
90
Figure 19.2: Bubble Sort
Chương trình thực hiện sắp xếp mảng theo phương pháp bubble sort được cho như sau:
Ví dụ 2:
#include 
void main()
{
	int i, j, temp, arr_num[5] = { 23, 90, 9, 25, 16};
	clrscr();
	for(i = 3; i >= 0; i--) /* Tracks every pass */
	for(j = 4; j >= 4 - i; j--) /* Compares elements */
	{
	if(arr_num[j] < arr_num[j - 1])
	{
	temp = arr_num[j];
	arr_num[j] = arr_num[j - 1];
	arr_num[j - 1] = temp;
	}
	}
	printf("\nThe sorted array");
	for(i = 0; i < 5; i++)
	printf("\n%d", arr_num[i]);
	getch();
}
19.3.2	Insertion Sort
Trong phương pháp Insertion sort, mỗi phần tử trong mảng được xem xét,ta xét mỗi phần tử của mảng và đặt vào vị trí đúng của nó giữa các phần tử đã được sắp xếp. Khi phần tử cuối cùng được đặt vào vị trí đúng của nó, thì mảng đã được sắp xếp. Ví dụ, xét một mảng có 5 phần tử,
Giá trị trong phần tử thứ nhất được xem như là đã ở đúng thứ tự.
So sánh giá trị trong phần tử thứ hai với phần mảng đã sắp xếp, mà hiện tại chỉ có phần tử thứ nhất.
Nếu giá trị trong phần tử thứ hai nhỏ hơn, nó được xen trước phần tử thứ nhất. Bây giờ, hai phần tử đầu tiên đã tạo thành phần danh sách sắp xếp và phần còn lại tạo thànhlà danh sách chưa sắp xếp.
Phần tử kế tiếp trong danh sách chưa sắp xếp, phần tử thứ 3, được so sánh với danh sách đã sắp xếp.
Nếu giá trị trong phần tử thứ 3 nhỏ hơn phần tử thứ 1, giá trị trong phần tử thứ 3 được xen trước phần tử thứ 1. 
Ngược lại, nếu giá trị trong phần tử thứ 3 nhỏ hơn phần tử thứ 2, giá trị trong phần tử thứ 3 được xen trước phần tử thứ 2. Bây giờ, phần sắp xếp của mảng chứagồm 3 phần tử, trong khi phần chưa sắp xếp chứagồm 2 phần tử còn lại.
Quá trình so sánh các phần tử trong danh sách chưa sắp xếp với các phần tử trong danh sách đã sắp xếp tiếp tục cho đến khi phần tử cuối cùng trong mảng đã được so sánh và đặt vào vị trí đúng của nó. 
Ở cuối quá trình sắp xếp, mỗi phần tử được xen vào đúng vị trí của nó. Hình 19.3 minh họa cách làm việc của insertion sort.
23
23
90
90
9
9
25
25
16
16
23
9
90
23
9
90
25
25
16
16
9
9
9
9
23
23
23
23
90
90
90
25
25
25
25
90
16
16
16
16
9
9
9
23
23
16
25
25
23
90
90
25
16
16
90
Figure 19.3: Insertion Sort
Chương trình thực hiện sắp xếp mảng theo phương pháp insertion sort được cho như sau:
Ví dụ 3:
#include
void main()
{
	int i, j, arr[5] = { 23, 90, 9, 25, 16 };
	char flag;
	clrscr();
	/*Loop to compare each element of the unsorted part of the array*/
	for(i = 1; i < 5; i++)
	/*Loop for each element in the sorted part of the array*/
	for(j = 0, flag = 'n'; j < i && flag == 'n'; j++)
	{
	if(arr[j] > arr[i])
	{
/*Invoke the function to insert the number*/
	insertnum(arr, i, j);
	flag = 'y';
	}
	}
	printf("\n\nThe sorted array\n");
	for(i = 0; i < 5; i++)
	printf("%d\t", arr[i]);
	getch();
}
insertnum(int arrnum[], int x, int y)
{
	int temp;
	/*Store the number to be inserted*/
	temp = arrnum[x];
	/*Loop to push the sorted part of the array down from the position where the number has to inserted*/
	for(; x > y; x--)
	arrnum[x] = arrnum[x - 1];
	/*Insert the number*/
	arrnum[x] = temp;
}
Tóm tắt
Một cấu trúc là một nhóm các biến có kiểu dữ liệu khác nhau được gom lại dưới cùng một tên.Một cấu trúc là tập các biến có thể có kiểu dữ liệu khác nhau được nhóm lại với nhau dưới cùng một tên.
Một định nghĩa cấu trúc tạo thành một khuôn mẫu, khuôn mẫu này có thể được sử dụng để tạo ra các biến 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 phần tử độc lập của cấu trúc được tham chiếu đếntruy cập bằng cách sử dụng toán tử chấm (.), hay còn được gọi là toán tử thành viên.
Các giá trị của một biến cấu trúc có thể được gán cho một biến khác có cùng kiểu bằng cách sử dụng câu lệnh gán đơn giản.
Có thể có một cấu trúc nằm trong một cấu trúc khác. Tuy nhiên một cấu trúc không thể lồng trong chính nó.
Một biến cấu trúc có thể được truyền vào một hàm như là một đốitham số.
Cách cài đặtsử dụng thông dụng nhất của cấu trúc là dưới hình thức các mảng cấu trúc.
Toán tử -> được sử dụng để truy cập vào các phần tử của một cấu trúc thông qua một con trỏ trỏ đến cấu trúc đó.
Một kiểu dữ liệu mới có thể được định nghĩa bằng từ khóa typedef.
Hai kỹ thuậtphương pháp dùng để sắp xếp một mảng là bubble sort và insertion sort.
Trong bubble sort, giá trị của các phần tử được so sánh với giá trị của phần tử kế tiếp. Trong phương pháp này, các phần tử nhỏ hơn nổi lên dần, và cuối cùng mảng sẽ được sắp xếp.
Trong insertion sort, ta xét mỗi phần tử trong mảng sẽ được xem xét, và chèn vào vị trí đúng của nó giữa các phần tử đã được sắp xếp.
Kiểm tra tiến độ học tập
Một __________ nhóm một số mụcẫu dữ liệu lại với nhau, các mụcẫu dữ liệu này không cầnnhất thiết phải có cùng kiểu.
Các phần tử của cấu trúc được tham chiếutruy cập đến thông qua việc sử dụng _________.
Các giá trị của một biến cấu trúc có thể được gán cho một biến khác có cùng kiểu bằng cách sử dụng câu lệnh gán đơn giản. 	(Đúng / Sai)
Không thể có một cấu trúc nằm trong một cấu trúc khác. 	(Đúng / Sai)
Một kiểu dữ liệu mới có thể được định nghĩa sử dụng từ khóa _________.
Trong bubble sort, các phần tử ______________ được so sánh.
Trong insertion sort, nếu một phần tử chưa được sắp xếp phải được đặt vào một vị trí đã được sắp xếp nào đó, thì các giá trị này sẽ được trao đổi với nhau.	(Đúng / Sai)
Bài tập tự làm
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.
Viết một chương trình C để lưu trữ các tê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.