Khác]Học trực tuyến những điều cơ bản về CTDL các bạn ơi
--------------------------------------------------------------------------------
Mình hiện đang học năm thứ 2, và đã học qua môn CTDL1 ở trong trường, với những gì mình biết, mình xin được post cho bà con cùng học thêm. Đây chỉ là những điều cơ bản về môn CTDL, xem ra cũng rất thích hợp đối với các bạn I tờ mờ (IT mờ). Đầu tiên,mình xin được post chương I trong cuốn giáo trình CTDL của thầy mình, nếu các bạn cảm thấy được thì mình sẽ post tiếp, các bạn đọc và cho mình biết ý kiến nhé. Thân ái!
Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật
1.1 Vai trò của cấu trúc dữ liệu (CTDL) trong một đề án tin học
1.1.1 Mối liên hệ giữa CTDL và giải thuật
Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên những đối tượng đó. Vì thế, để xây dựng một mô hình tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề :
Tổ chức biểu diễn các đối tượng thực tế :
Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựng những quan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ chức , xây dựng các cấu trúc thích hợp nhất sao cho vừa có thể phản ánh chính xác các dữ liệu thực tế này, vừa có thể dễ dàng dùng máy tính để xử lý. Công việc này được gọi là xây dựng cấu trúc dữ liệu (Data structure) cho bài toán.
Xây dựng các thao tác xử lý dữ liệu:
Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thi hành để cho ra kết quả mong muốn, đây là bước xây dựng giải thuật (Algorithm) cho bài toán.
Trong một đề án tin học, giải thuật và cấu trúc dữ liệu có mối quan hệ chặt chẽ với nhau, được thể hiện qua công thức :
Cấu trúc dữ liệu + Giải thuật = Chương trình
1.1.2 Các tiêu chuẩn đánh giá CTDL
Phản ánh đúng thực tế : Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ thể hiện chính xác đối tượng thực tế.
Ví dụ : Một số tình huống chọn cấu trúc lưu trữ sai :
- Chọn một biến số nguyên int để lưu trữ tiền thưởng bán hàng (được tính theo công thức tiền thưởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn mọi giá trị tiền thưởng gây thiệt hại cho nhân viên bán hàng. Trường hợp này phải sử dụng biến số thực để phản ánh đúng kết quả của công thức tính thực tế.
- Trong trường trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có 20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số nguyên unsigned char ( khả năng lưu trữ 0 - 255) để lưu trữ tổng học phí của lớp học trong tháng, nếu xảy ra trường hợp có thêm 6 học sinh được nhận vào lớp thì giá trị tổng học phí thu được là $260, vượt khỏi khả năng lưu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch.
Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý.
Ví dụ : Một tình huống chọn cấu trúc lưu trữ không phù hợp:
Cần xây dựng một chương trình soạn thảo văn bản, các thao tác xử lý thường xảy ra là chèn, xoá sửa các ký tự trên văn bản. Trong thời gian xử lý văn bản, nếu chọn cấu trúc lưu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý của chương trình vì phải làm việc trên bộ nhớ ngoài. Trường hợp này nên tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lưu trữ văn bản suốt thời gian soạn thảo.
LƯU Ý :
Đối với mỗi ứng dụng , cần chú ý đến thao tác nào được sử dụng nhiều nhất để lựa chọn cấu trúc dữ liệu cho thích hợp.
Tiết kiệm tài nguyên hệ thống: Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó. Thông thường có 2 loại tài nguyên cần lưu tâm nhất : CPU và bộ nhớ. Tiêu chuẩn này nên cân nhắc tùy vào tình huống cụ thể khi thực hiện đề án . Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì khi chọn cấu trúc dữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩn sử dụng tối ưu bộ nhớ, và ngược lại.
Ví dụ : Một số tình huống chọn cấu trúc lưu trữ lãng phí:
- Sử dụng biến int (2 bytes) để lưu trữ một giá trị cho biết tháng hiện hành . Biết rằng tháng chỉ có thể nhận các giá trị từ 1-12, nên chỉ cần sử dụng kiểu char (1 byte) là đủ.
- Để lưu trữ danh sách học viên trong một lớp, sử dụng mảng 50 phần tử (giới hạn số học viên trong lớp tối đa là 50). Nếu số lượng học viên thật sự ít hơn 50, thì gây lãng phí. Trường hợp này cần có một cấu trúc dữ liệu linh động hơn mảng- ví dụ xâu liên kết - sẽ được đề cập trong chương 3
1.2 Trừu tượng hoá dữ liệu
Máy tính thực sự chỉ có thể lưu trữ dữ liệu ở dạng nhị phân thô sơ. Nếu muốn phản ánh được dữ liệu thực tế đa dạng và phong phú, cần phải xây dựng những phép ánh xạ, những qui tắc tổ chức phức tạp che lên tầng dữ liệu thô, nhằm đưa ra những khái niệm logic về hình thức lưu trữ khác nhau được gọi là kiểu dữ liệu (Data Type)
1.2.1 Kiểu dữ liệu
Kiểu dữ liệu T được xác định bởi một bộ <V,O> , với :
V (Value): tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ
O (Operation): tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T.
Ví du: Giả sử có kiểu dữ liệu mẫu tự = <Vc ,Oc> với
Vc = { a-z,A-Z}
Oc = { lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa...}
Giả sử có kiểu dữ liệu số nguyên = <Vi ,Oi> với
Vi = { -32768..32767} Oi = { +, -, *, /, %}
Như vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu được phép lưu trữ và các xử lý tác động trên đó.
Các thuộc tính của 1 KDL bao gồm:
Tên KDL
Miền giá trị
Kích thước lưu trữ
Tập các toán tử tác động lên KDL
1.2.2 Các kiểu dữ liệu cơ bản
Các loại dữ liệu cơ bản thường là các loại dữ liệu đơn giản, không có cấu trúc như số nguyên, số thực, các ký tự, các giá trị logic ... Các loại dữ liệu này, do tính thông dụng và đơn giản của mình, thường được các ngôn ngữ lập trình (NNLT) cấp cao xây dựng sẵn như một thành phần của ngôn ngữ để giảm nhẹ công việc cho người lập trình. Chính vì vậy đôi khi người ta còn gọi chúng là các kiểu dữ liệu định sẵn.
Thông thường, các kiểu dữ liệu cơ bản bao gồm :
Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, liệt kê, miền con ...
Kiểu không rời rạc: số thực
Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn có thể khác nhau đôi chút. Với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số nguyên, số thực, ký tự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là kiểu số nguyên về mặt lưu trữ, chỉ khác về cách sử dụng. Ngoài ra, giá trị logic ĐÚNG (TRUE) và giá trị logic SAI (FALSE) được biểu diễn trong C như là các giá trị nguyên khác zero và zero.
Các kiểu dữ liệu định sẵn trong C gồm các kiểu sau:
Tên kiểu Kthước Miền giá trị Ghi chú
Char 01 byte -128 đến 127 Có thể dùng như số nguyên 1 byte có dấu hoặc kiểu ký tự
Unsign char 01 byte 0 đến 255 Số nguyên 1 byte không dấu
Int 02 byte -32738 đến 32767 Số nguyên 2 byte
Unsign int 02 byte 0 đến 65535 Có thể gọi tắt là unsign
Long 04 byte -232 đến 231 -1
Unsign long 04 byte 0 đến 232-1
Float 04 byte 3.4E-38 3.4E38 Giới hạn chỉ trị tuyệt đối.Các giá trị <3.4E-38 được coi = 0. Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa.
Double 08 byte 1.7E-308 1.7E308
Long double 10 byte 3.4E-4932 1.1E4932
Như vậy, trong C xét cho cùng chỉ có 2 loại dữ liệu cơ bản là số nguyên và số thực. Tức là chỉ có dữ liệu số. Hơn nữa các số nguyên trong C có thể được thể hiện trong 3 hệ cơ số là hệ thập phân, hệ thập lục phân và hệ bát phân.
Các kiểu cơ sở rất đơn giản và không thể hiện rõ sự tổ chức dữ liệu trong một cấu trúc, thường chỉ được sử dụng làm nền để xây dựng các kiểu dữ liệu phức tạp khác.
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 :
1.2.3.1. 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
1.2.3.2. 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 dữ liệu> <Tên biến>[<Số phần tử>];
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 dữ liệu> <Tên biến>[<Số phần tử1>][<Số phần tử2>]...;
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).
1.2.3.3. 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.
1.2.3.4. 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 <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
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("
Nhap Ho so thi sinh \"Ho bang rong de ket thuc\"");
do
{
hs.sbd = n+1;
printf("
Nhap ho so cho thi sinh: %3d",hs.sbd);
printf("
Ho : "); 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("
%-4s %-25s %-10s %-4s %-4s %-4s %-5s","SBD", "Ho Ten","Ngay sinh","Toan","Ly","Hoa","Phong");
for (i=0;i<n;i++)
printf("
%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);
}
1.2.3.5. Kiểu con trỏ
• Khái niệm:
Kiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ bộ nhớ đã cấp phát cho một đối tượng dữ liệu khác.
Biến con trỏ có kiểu cơ sở T là biến mà giá trị của nó là địa chỉ vùng nhớ đã cấp phát cho một biến kiểu T (có thể là biến con trỏ) hoặc là giá trị NULL để chỉ định biến con trỏ chưa chứa địa chỉ vùng nhớ nào.
• Khai báo kiểu con trỏ: typedef kiểucơsởT *tênkiểucontrỏ;
Kiểucơsở: là kiểu đã định nghiã trước, cũng có thể là kiểu con trỏ.
Kiểu con trỏ void: là kiểu con trỏ có thể chứa địa chỉ của bất kỳ kiểu nào. Nhưng khi sử dụng phải ép về 1 kiểu dữ liệu cụ thể.
• Khai báo biến con trỏ:
Mẫu 1: tênkiểucontrỏ tênbiếncontrỏ;
Mẫu 2: kiểucơsởT *tênbiếncontrỏ;
Ví dụ: typedef int *intpointer;
intpointer pt;
hay int *pt;
• Cấu trúc lưu trữ: Biến con trỏ được lưu trữ trong vùng nhớ cấp phát động (Heap) của chương trình. Kích thước của biến con trỏ tùy thuộc quy ước số byte địa chỉ trong từng mô hình bộ nhớ của từng ngôn ngữ lập trình
- Trong Pascal: 4 bytes(2 bytes địa chỉ Segment + 2 bytes địa chỉ offset)
- Trong C: 2 bytes cho con trỏ NEAR (chỉ lưu offset); 4 byte cho con trỏ FAR
• Các thao tác trên biến con trỏ:
o Gán 1 địa chỉ cho biến con trỏ:
Biến con trỏ có thể được khởi gán khi khai báo hay sử dụng câu lệnh gán tường minh.
tênbiếncontrỏ = &tênbiếncầnlấyđịachỉ;
tênbiếncontrỏ = NULL;
Ví dụ: Chứa địa chỉ của mảng 1 chiều: int *P , A[10]; --> P = A
Chứa địa chỉ của mảng 2 chiều: float *P, B[3][4]; --> P = (float*) B
Chứa địa chỉ của 1 biến cấu trúc: struct HocSinh *P, hs; --> P = &hs
o Truy xuất nội dung 1 biến do biến con trỏ trỏ đến: *tênbiếncontrỏ
Lưu ý: Toán tử * và & cùng độ ưu tiên
o Phép toán số học trên kiểu con trỏ:
Chỉ có ý nghĩa khi thực hiện trên mảng
pt + i ==> Cộng địa chỉ vùng nhớ lưu trong pt với i*sizeof(T)
pt1 - pt2 ==> số phần tử có kích thước sizeof(T) giữa 2 địa chỉ.
o Phép so sánh con trỏ: so sánh địa chỉ lưu trong 2 biến con trỏ: ==, !=
1.2.3.6. Kiểu tập tin
Các cấu trúc dữ liệu đã xét, lưu trữ và xử lý các mục dữ liệu ở bộ nhớ trong. Do đó có thể truy nhập đến chúng rất nhanh. Tuy nhiên dung lượng lưu trữ của bộ nhớ trong có thể quá nhỏ đối với những danh sách dữ liệu lớn, như danh sách nhân viên và không thể lưu trữ lâu dài. Những nhóm dữ liệu như vậy phải được lưu trữ ở bộ nhớ ngoài, gọi là tập tin (file).
Có 2 loại tập tin :
• File văn bản
• File có cấu trúc truy nhập ngẫu nhiên (File nhị phân)
Việc nhập xuất File văn bản chỉ khác file nhị phân khi xử lý ký tự chuyển dòng (mã 10, ký hiệu '
'):
• Khi ghi, 1 ký tự xuống dòng '
' được chuyển thành 2 ký tự CR (Carriage Return_13) và LF (Line Feed_10).
• Khi đọc 2 ký tự liên tiếp CR và LF trên file chỉ cho ta 1 ký tự LF.
Quy tắc làm việc với tập tin:
- Khai báo biến tập tin
- Mở tập tin
- Truy xuất tập tin
- Đóng tập tin
Trong C, việc truy xuất đến 1 file trên đĩa có thể thực hiện bằng các hàm trong STDIO.H thông qua biến con trỏ file.
a. Khai báo biến con trỏ file: FILE *TrỏFile;
Mỗi file đều được đánh dấu kết thúc bởi ký tự có mã 26. Khi sử dụng các hàm để đọc File, nếu gặp cuối File thì hàm sẽ trả về giá trị -1, có tên là EOF.
b. Mở file: TrỏFile = fopen (char *têntậptin, char *kiểu);
• Têntậptin: Bao gồm cả đường dẫn. Nếu có lỗi sẽ cho giá trị NULL.
• Kiểu: Kết hợp bởi các mã sau nhằm khai báo kiểu tập tin và cách thức truy xuất tập tin.
Kiểu Ý nghiã
"b" Mở tập tin kiểu nhị phân
"t" Mở tập tin kiểu văn bản
"r" Mở để đọc. Nếu không có File sẽ báo lỗi
"r+" Mở để sửa
"w" Mở file mới để ghi. Nếu file đã có sẽ bị xóa
"w+" Mở file mới đọc hoặc ghi.
"a" Mở file để ghi thêm vào cuối file
"a+" Mở file để đọc ghi. Nếu file cũ thì nối thêm,nếu không thì tạo mới
Ví dụ: FILE *fp;
fp = fopen("C:\\DSHS.DBF", "wb");
if ( fp == 0 )
{
perror("Loi Mo File:");
exit(1);
}
c. Đóng file:
- int fclose (FILE *fp); Nếu có lỗi hàm cho EOF ngược lại cho giá trị 0.
- int fcloseall ( ); Nếu có lỗi cho EOF nếu không cho số file được đóng.
File văn bản
a. Ghi dữ liệu từ biến ra file văn bản:
• int putc ( int ch, FILE *fp); Ghi lên file 1 ký tự có mã m = ch % 256.
Nếu không ghi được sẽ trả về EOF ngược lại trả về ký tự đã ghi.
• int fputc (int ch, FILE *fp); như trên
Ví dụ: Xây dựng chương trình tạo tập tin văn bản, trong đó tên tập tin được nhập trên dòng lệnh. Kết thúc khi ấn Ctrl-Z hay F6
int main(int n, char * a[]) //n là số đối số trên dòng lệnh kể cả tên chương trình a[0]
{ FILE *fp; char c; int sobyte=0;
if (n != 2) { puts("Loi cu phap: "); exit(1); }
fp = fopen(a[1], "wt");
while (( c = getchar()) != EOF) //hàm getchar() trả về EOF khi có lỗi hoặc ấn F6
{ putc( c, fp); sobyte++; }
printf("
\t 1 file copy \t\t %d bytes ", sobyte);
fclose(fp); }
Chú thích: Biên dịch thành file EXE, trở về dấu nhắc Dos: Taofile D:\LuuTru\Thoca.txt
• int fputs (const char *Str, FILE *fp); Ghi chuỗi Str vào file.
Khi thành công hàm trả về ký tự cuối cùng được ghi, ngược lại trả về EOF.
Ví dụ:
int main(int n, char * a[]) //n là số đối số trên dòng lệnh kể cả tên chương trình a[0]
{ FILE *fp; char st[80]; int sobyte=0;
if (n != 2) { puts("Loi cu phap: "); exit(1); }
fp = fopen(a[1], "wt");
while ( gets(st)) != NULL) //hàm gets(st) trả về NULL khi có lỗi hoặc ấn F6
{ fputs( st, fp); fputs("
", fp);
sobyte+=strlen(st);
}
printf("
\t 1 file copy \t\t %d bytes ", sobyte);
fclose(fp);
}
• int fprintf (FILE *fp, const char *dk, các biểu thức);
Ghi dữ liệu theo khuôn dạng. Nếu thành công hàm trả về số byte ghi lên điã, ngược lại trả về giá trị EOF (-1). Ký tự '
' được ghi thành 2 ký tự CR và LF.
Ví dụ: fprintf(fp,"so dinh %d
", n);
Ví dụ: Tạo file văn bản chứa một bản nhạc: Lời, tần số, thời gian nghỉ.
Ví dụ: Tạo file lưu bảng lượng giác của các góc từ 1 đến 89
b. Đọc dữ liệu vào biến bộ nhớ:
• int getc (FILE *fp) hoặc int fgetc (FILE *fp)
Đọc 1 ký tự. Nếu thành công hàm trả về mã đọc được (0 - 255). Nếu gặp ký tự cuối file (26) hay có lỗi đọc file thì trả về EOF.
Chú ý: Trong kiểu văn bản,
- Hàm đọc 1 lượt cả 2 mã 13, 10 và chỉ trả về mã 10
- Khi đọc ký tự kết thúc file (26) hàm trả về EOF
Ví dụ: Đếm số từ xuất hiện trong 1 file văn bản.
#include <stdio.h> #include <conio.h> #include <string.h>
#include <stdlib.h> #include <Ctype.h>
void main()
{ FILE *fp; char ch, Tu[8], fin[30];int i ;
clrscr(); textmode(C40); strcpy(fin,"d:\\thu.cpp");
fp = fopen(fin,"rt");
if (fp == NULL)
{ printf("Khong tim thay File: %s ", fin); getch(); exit(1);
}
while (!feof(fp))
{ memset(Tu,0,8);
while ((ch = getc(fp)) != EOF) //Tim ky tu dau tu
if (!isspace(ch))
{
Tu[0] = ch;
break;
}
if (Tu[0] != 0)
{ i = 1;
while ((ch = getc(fp)) != EOF)
if (isspace(ch)) { break; }
else Tu[i++] = ch;
printf("
%s",Tu);
}
}
fclose(fp);
}
• char *fgets (char * Str, int n, FILE *fp);
Đọc 1 chuỗi tối đa n-1 ký tự. Hàm trả về địa chỉ vùng chứa chuỗi. Nếu có lỗi hoặc gặp cuối file hàm cho giá trị NULL.
Việc đọc kết thúc khi:
- Đọc hết n-1 ký tự;
- Gặp dấu xuống dòng (cặp mã 13 10): khi đó mã 10 ('
') được ghi vào xâu kết quả
- Gặp dấu kết thúc file
Hàm sẽ thêm ký tự '\0' vao cuối chuỗi.
Ví dụ: Đọc file lượng giác bằng hàm fgets vào một mảng và cho phép sử dụng các phím mũi tên để duyệt trên danh sách trên màn hình.
• int fscanf (FILE *fp, const char *dk, địa chỉ các biến);
Đọc dữ liệu theo khuôn dạng. Nếu thành công hàm trả về số Fields đọc được, ngược lại trả về giá trị EOF (-1).
Ví dụ: Đọc file DAGIAC.DAT chứa toạ độ các đỉnh của đa giác. Dòng đầu ghi số đỉnh các dòng sau mỗi dòng ghi tọa độ của 1 đỉnh của đa giác.
typedef struct pointtype Polygol[10];
Polygol P;
void main(void)
{
FILE *fp;
char c; int n,i;
fp = fopen("c:\\dagiac.dat","rt");
fscanf(fp,"%d",&n);
printf("%d
",n);*/
for (i=0; i<n; i++)
fscanf(fp,"%d %d",&P[i].x,&P[i].y);
fclose(fp);
}
Trường hợp không biết trước số đỉnh của đa giác:
i = 0;
while (fscanf(fp,"%d %d",&P[i].x, &P[i].y) != EOF)
printf("%d %d
",P[i].x,P[i].y);
File truy nhập ngẫu nhiên
Tập tin truy nhập ngẫu nhiên thường dùng lưu trữ các mục dữ liệu cùng kiểu dưới dạng nhị phân như trong bộ nhớ. Cho phép truy nhập tuần tự các mục dữ theo thứ tự lưu trữ và có thể truy nhập trực tiếp đến một mục nào đó trong File bằng cách đặc tả vị trí của nó.
a. Ghi các mục dữ liệu vào File:
• int fwrite(void *ptr, int sizeofItem, int n, FILE *fp);
Ghi n phần tử ở địa chỉ ptr, mỗi phần tử có kích thước size bytes. Hàm trả về số phần tử thật sự được ghi. Sau khi ghi xong đầu đọc sẽ dời đi (n*sizeof(Item)) byte.
Ví dụ: Tạo File lưu trữ hồ sơ nhân viên.
b. Đọc các mục dữ liệu trên File:
• int fread (void *ptr, int sizeofItem, int n, FILE *fp);
Đọc n phần tử vào địa chỉ ptr , mỗi phần tử có kích thước size bytes. Hàm trả về số phần số phần tử thật sự đọc được.
Ví dụ: Liệt kê danh sách nhân viên.
Thuật toán: Duyệt tập tin
(1) Mở file để đọc
(2) Trong khi còn đọc được N nhân viên (đọc chừng 20 nhân viên)
while (N = fread(&nv, sizeof(NhanVien), 20, fp)) > 0)
(3) In N nhân viên
(4) Đóng file
void main()
{ FILE *f; item e; int N; const char *fname="e:\\DS.DBF";
f = fopen(fname, "rb");
while (N = fread(&e, sizeof(item), 1, f)) > 0 )
{ for (int i=1; i<=N; i++) printf("%6d", e.k);
getch();
}
fclose(f);
}
c. Kiểm tra cuối file:
• int feof (FILE *fp);
Hàm cho giá trị khác 0 nếu gặp cuối file sau khi đọc
Ví dụ: while (1)
{ fread(&e,sizeof(Item), 1, fp);
if ( feof( f )) break;
}
d. Vị trí con trỏ byte:
• long ftell (FILE *fp);
Cho biết con trỏ ở byte thứ mấy của file (tính từ 0). Khi có lỗi hàm trả về -1L.
e. Di chuyển đầu đọc File:
• void rewind (FILE *fp); Chuyển đầu đọc về đầu file.
• int fseek (FILE *fp, long sốbyte, int vịtríxuấtphát); chuyển đầu đọc từ vị trí xuất phát qua 1 số byte về hướng cuối file (sốbyte>0) hay hướng đầu file (sốbyte<0). Nếu thành công hàm trả về giá trị 0.
Vị trí xuất phát có thể nhận các giá trị:
+ SEEK_SET hay 0: xuất phát từ đầu file
+ SEEK_CUR hay 1: xuất phát từ vị trí hiện hành
+ SEEK_END hay 2: xuất phát từ cuối file.
Ví dụ : Hàm tính số byte trên file (đối với file văn bản ký tự xuống dòng được tính 2 còn file nhị phân tính 1)
long filesize(FILE *stream) { long curpos, length;
curpos = ftell(stream);
fseek(stream, 0L, SEEK_END);
length = ftell(stream);
fseek(stream, curpos, SEEK_SET);
return length;
}
f. Đánh dấu vị trí đầu đọc ghi:
• int fgetpos (FILE *fp, fpos_t *vịtrí);
g. Quay lại vị trí đã đánh dấu:
• int fsetpos(FILE * fp, fpos_t *vịtrí);
Trong đó: fpos_t tương đương với kiểu long int. Nếu thành công trả về giá trị 0
h. Thêm một số mục dữ liệu vào tập tin:
Thuật toán:
(1) Mở File để thêm
(2) Nhập dữ liệu vào biến bộ nhớ e
(3) Nếu (có nhập) thì ghi biến nhớ vào File
(4) Lặp lại (2) trong khi còn nhập.
(5) Đóng File
i. Sửa Dữ liệu:
Thuật toán:
(1) Mở file để đọc và ghi
(2) Nhập thông tin nhận dạng mục cần sửa
(3) Dời đầu đọc đến mục cần sửa
(4) Ghi nhận vị trí đầu đọc
(5) Đọc mục cần sửa vào biến nhớ
(6) Hiển thi thông tin và cho Nhập dữ liệu mới
(7) Dời đầu đọc về lại vị trí đã ghi nhận
(8) Ghi dữ liệu vào File
j. Hủy một mục dữ liệu:
Phương án 1:
Thuật toán:
(1) Đọc các phần tử không bị hủy trong tập tin chính vào một tập tin tạm.
Item e;
ftemp = fopen("??", "wb")
while (! feof( f ) )
{ fread( &e, sizeof(Item), 1, f );
if (e.khóa != Khóa_cần_tìm)
fwrite(&e, sizeof(Item), 1, ftemp);
}
(2) Đổi tên tập tin tạm thành tập tin chính
(2.1) Nếu có file ?.BAK thì xóa nó
remove(" ?.BAK");
(2.2) Đổi tên ? thành ?.BAK // rename( "? ", "?.BAK")
(2.3) Đổi tên ?? thành ? // rename( " ?? ", "?")
k. Đổi tên / di chuyển file :
int rename (const char *OldFile, const char *NewFile);
Nếu thành công: Trả về giá trị 0, ngược lại trả về -1.
l. Xóa tập tin:
int remove (const char * path);
Nếu thành công: Trả về giá trị 0, ngược lại trả về -1.
Phương án 2:
Tổ chức thêm vùng tin để đánh dấu sự loại bỏ tạm thời.
(1) Tìm và đánh dấu các phần tử cần loại bỏ.
• Tìm phần tử cần hủy
• Nếu tìm thấy thì e.dauloaibo = 1
• Ghi trở lại vào File
fseek( f , (long) -sizeof(Item), SEEK_CUR);
fwrite( &e, sizeof(Item), 1, f );
(2) Sau đó mới copy các phần tử không đánh dấu loại bỏ qua tập tin mới.
Ưu điểm:
- An toàn dữ liệu
- Tiết kiệm thời gian
- Có thể khôi phục lại các phần tử đã được đánh dấu loại bỏ tạm thời.
m. Trộn File:
Giả sử, có 2 file chứa các mẫu tin, mỗi mẫu tin chứa những thông tin khác nhau về một đối tượng cần quản lý (Nhân viên). Và hiện đang lưu trữ theo thứ tự của một trường khóa nào đó (MsNV).
Để Trộn 2 file đã sắp thứ tự theo khóa của mẫu tin sao cho file nhận được cũng sắp thứ tự có thể dùng thuật toán sau:
Thuật toán:
input: File1, File2 đã sắp thứ tự
output: File3 cũng sắp thứ tự
Bắt đầu:
(1) Mở File1 và File2 để đọc; File3 để ghi
(2) Đọc phần tử X trong File1 và phần tử Y trong File2
(3) Lặp lại các bước sau cho đến khi kết thúc File1 hay File2
Nếu ( Khóa(X) < Khóa(Y) ) thì
Ghi X vào File3
Đọc mẫu tin mới của X trong File1
Ngược lại
Ghi Y vào File3
Đọc mẫu tin mới của Y trong File2
(4) Nếu chưa kết thúc trong File1, sao tất cả các phần tử còn lại từ File1 sang File3. Nếu chưa kết thúc trong File2, sao tất cả các phần tử còn lại từ File2 sang File3.
(5) Đóng các file
Kết thúc.
1.3 Đánh giá độ phức tạp giải thuật
1.3.1 Tại sao phải phân tích giải thuật
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
1.- Giải thuật đúng đắn.
2.- Giải thuật đơn giản.
3.- Giải thuật thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết qủa , thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kỹ càng. Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật
1.3.2 Thời gian thực hiện của giải thuật
Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là lập trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào.
Thời gian thực hiện không chỉ phụ thuộc vào giải thuật mà còn phụ thuộc vào tập các chỉ thị của máy tính, chất lượng của máy tính và kỹ xảo của người lập trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào được chọn. Để vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi của giải thuật. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất.
1.3.2.1 Thời gian thực hiện chương trình.
Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Ví dụ 1-1: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số.
Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) 0 n0.
1.3.2.2 Đơn vị đo thời gian thực hiện.
Đơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây... mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng.
Ví dụ 1-2: Khi ta nói thời gian thực hiện của một chương trình là T(n) = cn thì có nghĩa là chương trình ấy cần cn chỉ thị thực thi.
1.3.2.3 Thời gian thực hiện trong trường hợp xấu nhất.
Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện chương trình có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm.
Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thưóc n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.
1.3.3 Tỷ suất tăng và độ phức tạp của giải thuật
1.3.3.1 Tỷ suất tăng
Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số c và n0 sao cho T(n) ≤ c.f(n) với mọi n ≥ n0.
Ta có thể chứng minh được rằng "Cho một hàm không âm T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó".
Ví dụ 1-3: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Đặt n0 = 1 và c = 4 thì với mọi n ≥ 1 chúng ta dễ dàng chứng minh rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2.
Ví dụ 1-4: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho n0 = 0 và c = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3
1.3.3.2 Khái niệm độ phức tạp của giải thuật
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Giải thuật nào sẽ thực hiện nhanh hơn? Câu trả lời phụ thuộc vào kích thước dữ liệu vào. Với n < 20 thì P2 sẽ nhanh hơn P1 (T2<T1), do hệ số của 5n3 nhỏ hơn hệ số của 100n2 (5<100). Nhưng khi n > 20 thì ngược lại do số mũ của 100n2 nhỏ hơn số mũ của 5n3 (2<3). Ở đây chúng ta chỉ nên quan tâm đến trường hợp n>20 vì khi n<20 thì thời gian thực hiện của cả P1 và P2 đều không lớn và sự khác biệt giữa T1 và T2 là không đáng kể..
Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện.
Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng c, N0 sao cho T(n) ≤ cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là "ô của f(n)")
Ví dụ 1-5: T(n)= (n+1)2 có tỷ suất tăng là n2 nên T(n)= (n+1)2 là O(n2)
Chú ý: O(c.f(n))=O(f(n)) với c là hằng số. Đặc biệt O(c)=O(1)
Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử c trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi là hàm đa thức. Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật.
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên của chương trình chính là xác định độ phức tạp của giải thuật
1.3.4 Cách tính độ phức tạp
Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau:
1.3.4.1 Qui tắc cộng:
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))
Ví dụ 1-6: Lệnh gán x=15 tốn một hằng thời gian hay O(1)
Lệnh đọc dữ liệu scanf("%d", x) tốn một hằng thời gian hay O(1)
Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)
1.3.4.2 Qui tắc nhân:
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và
T1(n) = O(f(n)), T2(n) = O(g(n) thì thời gian thực hiện của đoạn hai đoạn chương trình đó *****g nhau là T(n) = O(f(n).g(n))
1.3.4.3 Qui tắc tổng quát để phân tích một chương trình:
• Thời gian thực hiện của mỗi lệnh gán, Scanf, Printf là O(1)
• Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
• Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau IF hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).
• Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện than vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.
Ví dụ 1-7: Tính thời gian thực hiện của đoạn chương trình
void BubleSort(int a[], int N )
{ int i, j, tepm;
{1}for (i = 0 ; i<N-1 ; i++)
{2} for (j =N-1; j >i ; j --)
{3} if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ
{4} { temp = a[j];
{5} a[j] = a[j-1];
{6} a[j-1] = temp;
}
}
Cả ba lệnh đổi chỗ {4} {5} {6} tốn O(1) thời gian, do đó lệnh {3} tốn O(1).
Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1)=O(n-i).
Vòng lặp {1} lặp (n-1) lần vậy độ phức tạp của giải thuật là:
1.3.4.4 Độ phức tạp của chương trình có gọi chương trình con không đệ qui
Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các chương trình con mà nó gọi đã được đánh giá. Cuối cùng ta tính thời gian cho chương trình chính.
Giả sử ta có một hệ thống các chương trình gọi theo sơ đồ sau:
Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12.
Để tính thời gian thực hiện của A, ta tính theo các bước sau:
• Tính thời gian thực hiện của C, B2, B11 và B12.
• Tính thời gian thực hiện của B1.
• Tính thời gian thực hiện của B.
• Tính thời gian thực hiện của A.
Ví dụ 1-8: Ta có thể viết lại chương trình sắp xếp bubble như sau:
void Hoanvi (int *x, int *y)
{ int temp;
temp = *x;
*x = *y;
*y = temp;
)
void BubleSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =N-1; j >i ; j --)
if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ
Hoanvi(&a[j],&a[j-1]);
}
Trong cách viết trên, chương trình Bubble gọi chương trình con Hoanvi, do đó để tính thời gian thực hiện của Bubble, trước hết ta cần tính thời gian thực hiện của Hoanvi. Dễ thấy thời gian thực hiện của Hoanvi là O(1) vì nó chỉ bao gồm 3 lệnh gán.
Trong Bubble, lệnh {3} gọi Hoanvi nên chỉ tốn O(1), lệnh {2} thực hiện n-i lần, mỗi lần tốn O(1) nên tốn O(n-i). Lệnh {1} thực hiện n-1 lần
Chương 2 : Các phương pháp tìm kiếm và sắp xếp
2.1 Đặt vấn đề
Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin :
Ví du: tra cứu từ điển, tìm sách trong thư viện...
Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn:
Ví dụ: các từ trong từ điển được sắp xếp theo từng vần, trong mỗi vần lại được sắp xếp theo trình tự alphabet; sách trong thư viện được xếp theo chủ đề ...
Vì thế, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu.
Hiện nay đã có nhiều giải thuật tìm kiếm và sắp xếp dược xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ, do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau. Chương này sẽ trình bày các thuật toán sắp xếp và tìm kiếm dữ liệu được lưu trữ trên bộ nhớ chính - gọi là các giải thuật tìm kiếm và sắp xếp nội và một số giải thuật sắp xếp trên bộ nhớ phụ hay sắp xếp ngoại
2.2 Đệ qui và tìm kiếm bằng đệ qui
2.2.1 Khái niệm
Đệ qui là một khái niệm cơ bản trong toán học và khoa học máy tính
Một đối tượng X gọi là được định nghĩa đệ qui nếu trong phát biểu của X có dùng chính đối tượng X. Một chương trình đệ qui là chương trình gọi đến chính nó trong các câu lệnh, tuy nhiên yếu tố bắt buộc đối với một chương trình đệ qui là nó phải có một điều kiện dừng
Đệ quy mạnh ở chỗ có thể định nghĩa một tập rất lớn các tác động chỉ bởi một số rất ít mệnh đề. Một chương trình viết theo giải thuật có tính đệ quy sẽ mang tính "Người" hơn do đó sẽ:
Sáng sủa
Dễ hiểu
Nêu bật được vấn đề
Bản chất của đệ quy là ý tưởng quy nạp hay hạ bậc trong toán học, nghĩa là đưa một số vấn đề phức tạp về một vấn đề đơn giản hơn.
Đệ qui được ứng dụng trong rất nhiều bài toán thực tế nhưng không phải bất cứ bài toán nào được giải bằng phương pháp đệ qui đều tốt do việc sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến của chương trình đệ qui
Một định nghĩa đệ qui thường có 2 thành phần
- Thành phần cố định (điều kiện dừng) : không có lời gọi đệ qui
Ví duï: 0! = 1! = 1
- Thành phần đệ qui : ứng với tham số có lời gọi đệ qui đến tham số khác, dần tiến về thành phần cố định
ví duï: n! = n*(n-1)! neáu n > 1
2.2.2 Hàm đệ qui
Một hàm là một sự định nghiã về một công việc nào đó, nên cũng có thể là đệ qui:
Nếu trong hàm P có lời gọi tường minh đến chính nó thì gọi là đệ qui trực tiếp
Nếu trong P có gọi Q, và trong Q lại có lời gọi P thì P được gọi là đệ qui gián tiếp.
Khi hàm gọi đệ qui đến chính nó thì mỗi lần gọi, máy sẽ tạo ra một tập biến cục bộ mới hoàn toàn độc lập với tập biến cục bộ của hàm trước đó.
Cũng như các lệnh lặp, các thủ tục đệ qui cũng có thể thực hiện các tính toán không dừng, vì thế cần chú ý vấn đề kết thúc.
Ví dụ: Xây dựng hàm tính n! theo đệ qui.
long gt(int n)
{ if (n == 0 || n == 1) return 1;
else return (n * gt(n-1));
} Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide
int UCLN(int x, int y)
{ if (y == 0) return x;
else return (ucln(y, x % y));
}
Ví dụ: Dãy số Fibonacci được xác định như sau: F0=1; F1=1; Fn=Fn-1+Fn-2 với n>=2. Hãy xác định phần tử thứ n của của dãy số.
int Fibo(int n)
{ if (n == 0 || (n == 1) return 1;
else return (fibo(n - 1) + fibo(n - 2));
}
Nhận xét: Một hàm đệ quy về căn bản luôn gồm 2 phần.
• Phần dừng: Chứa các tác động của hàm ứng với 1 số giá trị ban đầu của tham số
• Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số có phạm vi nhỏ hơn.
2.2.3 Tìm kiếm đệ qui
Nội dung chính của thuật toán là việc xây dựng dần các thành phần của một lời giải hay một cấu hình bằng cách thử tất cả các khả năng.
Giả thiết cấu hình cần tìm được mô tả bằng một bộ n thành phần x1,x2,..,xn.
Giả sử, đã xác định được i - 1 thành phần x1,x2,..,xi-1. Ta cần tìm thành phần xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số các khả năng từ 1 đến ni). Với mỗi khả năng j, kiểm tra xem j có chấp nhận được không:
Nếu chấp nhận j thì xác định xi theo j, sau đó nếu i = n thì ta được một cấu hình ngược lại ta tiếp tục xác định xi+1 .
Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước để xác định lại xi-1 .
Mô hình quay lui được thiết kế đơn giản bằng đệ quy của hàm Try như sau:
/* Xác định thành phần xi bằng đệ quy */
void Try( int i )
{ int j;
If (i > N) < ghi nhận 1 cấu hình>;
else
{
for (j thuộc tập khả năng đề cử )
if < chấp nhận khả năng ( j )> then
{
< Xác định xi theo khả năng ( j ) >
<Ghi nhận khả năng ( j ) đã được chọn cho xi >;
Try( i+1);
< bỏ việc ghi nhận khả năng ( j ) đã chọn cho xi >;
}
}
}
Vấn đề:
Cần xác định được danh sách các khả năng đề cử
Cần ghi nhớ lại những khả năng nào đã được thử để tránh trùng lặp.
Xác định giá trị biểu thức logic <chấp nhận j >. Thông thường giá trị này ngoài việc phụ thuộc j, có phụ thuộc vào việc đã chọn các khả năng tại (i -1) bước trước. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trình tìm kiếm sau khi <xác định xi theo j > và trả lại trạng thái cũ sau khi đã <ghi nhận 1 cấu hình>.
Sau khi xây dựng giải thuật Try, đoạn chương trình chính của bài toán liệt kê có dạng:
main()
{ Init;
Try(i);
}
Ví dụ: Liệt kê các dãy nhị phân có độ dài n.
CTDL: Mảng byte: char X[20]; chứa dãy nhị phân.
Khả năng đề cử cho 1 thành phần X[i] là: 0 và 1
void Try(int i)
{ int j;
if ( i > n ) InKetqua;
else
for (j =0; j<2; j++)
{ X[i] = j;
Try( i + 1 );
}
}
Ví dụ: Liệt kê tất cả (n!) các hoán vị của {1,2,..,n}
Giải: Mỗi hoán vị được tổ chức như 1 mảng gồm n thành phần: x[1], x[2] ,.., x[n] trong đó mỗi x[i] nhận giá trị từ 1 đến n với điều kiện (x[i] != x[j] )với ( i != j ).
Giả sử đã xác định được i -1 thành phần: x1, x2 ,.., xi-1 Ta cần tìm thành phần xi :
Khả năng đề cử cho xi là từ giá trị j =1..n, trong đó j != xk với k=1 .. i-1.
Vì thế cần phải ghi nhớ đối với mỗi khả năng đã đề cử, xem nó đã được dùng hay chưa bằng mảng int chuadung[Max]; trong đó chuadung[ j ]=1 nếu j chưa được sử dụng trong i-1 thành phần trước đó.
/* Liet ke cac Hoan vi cua day so 1..n */
int x[Max], n ;
int gn[Max];/* ghi nhan trang thai da duoc chon hay chua*/
main()
{ memset(x, 0, Max* sizeof(x[0]));
memset(gn, 0, Max * sizeof(gn[0]));
printf("
Nhap n: "); scanf("%d", &n);
Try(1);
}
void Try(int i)
{ int j;
if (i > n) InMotHoanVi();
else
for (j=1; j <= n; j++)
if (!gn[j])
{ x[i] = j;
gn[j] = 1;
Try(i+1);
gn[j] = 1;
}
}
void InMotHoanVi(void)
{ int i; puts("");
for (i=0; i<n; i++)
printf("%-5d",x[i]);
}
Ví dụ: Bài toán ngựa đi tuần trên bàn cờ kích NxN
//số gia tọa độ
int a[8] ={2,1,-1,-2,-2,-1,1,2};
int b[8]={1,2,2,1,-1,-2,-2,-1};
void Try(int i)
{ int j,u,v;
if (i+1> n*n) {print ; Cóđườngđi = 1;}
else
for ( j =0; j < 8 ; j++) //
{ u=x+a[j]; v=y+b[j];
if (u>= 0 && u < n && v >=0 && v<N && h[u,v]==0)
{ h[u,v]=i; x=u; y=v;
Try(i+1);
x=u-a[j]; y=v-a[j]; h[u,v]=0
}
}
}
2.3 Các phương pháp tìm kiếm nội
Có 2 giải thuật thường được áp dụng để tìm kiếm dữ liệu là tìm tuyến tính và tìm nhị phân
2.3.1 Tìm kiếm tuyến tính
Giải thuật
Tìm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Các bước tiến hành như sau :
• Bước 1:
i = 1; // bắt đầu từ phần tử đầu tiên của dãy
• Bước 2: So sánh a[i] với x, có 2 khả năng :
o a[i] = x : Tìm thấy. Dừng
o a[i] != x : Sang Bước 3.
• Bước 3 :
i = i+1; // xét tiếp phần tử kế trong mảng
Nếu i >N: Hết mảng, không tìm thấy.Dừng
Ngược lại: Lặp lại Bước 2.
Ví dụ : cho dãy số a: 12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau :
Hình 2.2
i = 1
Hình 2.3
i = 2
i = 3 Dừng
Cài đặt
Từ mô tả trên đây của thuật toán tìm tuyến tính , có thể cài đặt hàm LinearSearch để xác định vị trí của phần tử có khoá x trong mảng a :
int LinearSearch(int a[], int N, int x)
{ int i=0;
while ((i<N) && (a[i]!=x )) i++;
if(i==N) return -1; // tìm hết mảng nhưng không có x
else return i; // a[i] là phần tử có khoá x
}
Trong cài đặt trên đây, nhận thấy mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện (i<N) - điều kiện biên của mảng - và (a[i]!=x )- điều kiện kiểm tra chính. Nhưng thật sự chỉ cần kiểm tra điều kiện chính(a[i] !=x), để cải tiến cài đặt, có thể dùng phương pháp "lính canh" - đặt thêm một phần tử có giá trị x vào cuối mảng, như vậy bảo đảm luôn tìm thấy x trong mảng, sau đó dựa vào vị trí tìm thấy để kết luận. Cài đặt cải tiến sau đây của hàm LinearSearch giúp giảm bớt một phép so sánh trong vòng lặp :
int LinearSearch(int a[],int N,int x)
{ int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x ) i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
else
return i; // tìm thấy x tại vị trí i
}
Ðánh giá giải thuật
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm tuyến tính, có:
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử đầu tiên có giá trị x
Xấu nhất n+1 Phần tử cuối cùng có giá trị x
Trung bình (n+1)/2 Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau.
Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán : T(n) = O(n)
NHẬN XÉT
Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.
2.3.2 Tìm kiếm nhị phân
Giải thuật
Ðối với những dãy số đã có thứ tự ( giả sử thứ tự tăng ), các phần tử trong dãy có quan hệ ai -1 £ ai £ ai+1, từ đó kết luận được nếu x > ai thì x chỉ có thể xuất hiện trong đoạn
[ai+1 ,aN] của dãy , ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1 ,ai-1] của dãy . Giải thuật tìm nhị phân áp dụng nhận xét trên đây để tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử aleft .. aright , các bước tiến hành như sau :
Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử
Bước 2:
• mid = (left+right)/2; // lấy mốc so sánh
• So sánh a[mid] với x, có 3 khả năng :
o a[mid] = x: Tìm thấy. Dừng
o a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 :
o right =midle - 1;
a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright :
left = mid + 1;
Bước 3:
• Nếu left right //còn phần tử chưa xét, tìm tiếp.
Lặp lại Bước 2.
• Ngược lại: Dừng; //Ðã xét hết tất cả các phần tử.
Ví dụ : Cho dãy số a gồm 8 phần tử:
1 2 4 5 6 8 12 15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau:
left = 1, right = 8, midle = 4
left = 5, right = 8, midle = 6 Dừng
Cài đặt
Thuật toán tìm nhị phân có thể được cài đặt thành hàm BinarySearch:
int BinarySearch(int a[],int N,int x )
{ int left =0; right = N-1;
int midle;
do {
mid = (left + right)/2;
if (x = a[midle]) return midle;//Thấy x tại mid else
if (x < a[midle]) right = midle -1;
else left = midle +1;
}while (left <= right);
return -1; // Tìm hết dãy mà không có x
}
Ðánh giá giải thuật
Trường hợp giải thuật tìm nhị phân, có bảng phân tích sau :
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử giữa của mảng có giá trị x
Xấu nhất log 2 n Không có x trong mảng
Trung bình log 2 (n/2) Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau
Vậy giải thuật tìm nhị phân có độ phức tạp tính toán : T(n) = O(log 2 n)
NHẬN XÉT
Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự.
Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuyến tính do Tnhị phân (n) = O(log2n) < Ttuyến tính (n) = O(n).
Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại . Tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm nhị phân. Ta cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất
2.4 Các phương pháp sắp xếp nội
Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử
Sắp xếp dãy số a1 , a2 ,... ,aN là thực hiện việc bố trí lại các phần tử sao cho hình thành được dãy mới ak1 , ak2 ,... ,akN có thứ tự ( giả sử xét thứ tự tăng) nghĩa là aki £ aki-1. Mà để quyết định được những tình huống cần thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh. Chính vì vậy, hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuật toán sắp xếp.
2.4.1 Các phương pháp sắp xếp có độ phức tạp N2
2.4.1.1 Phương pháp chọn trực tiếp (SelectionSort)
Giải thuật
Ta thấy rằng, nếu mảng có thứ tự, phần tử ai luôn là min(ai, ai+1, ., an-1). Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy. Các bước tiến hành như sau :
Bước 1: i = 1;
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]
Bước 3 : Hoán vị a[min] và a[i]
Bước 4 : Nếu i £ N-1 thì i = i+1; Lặp lại Bước 2
Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị trí.
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt
Cài đặt thuật toán sắp xếp chọn trực tiếp thành hàm SelectionSort
void SelectionSort(int a[],int N )
{ int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i<N-1 ; i++)
{
min = i;
for(int j = i+1; j <N ; j++)
if (a[j ] < a[min])
min = j; // ghi nhận vị trí phần tử hiện nhỏ nhất
Hoanvi(a[min], a[i]);
}
}
Ðánh giá giải thuật
Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận :
Số lần so sánh =
Số lần hoán vị (một hoán vị bằng 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy số, ta chỉ có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số phép gán
Tốt nhất n(n-1)/2 0
Xấu nhất n(n-1)/2 3n(n-1)/2
2.4.1.2 Phương pháp Chèn trực tiếp (InsertionSort)
Giải thuật
Giả sử có một dãy a1 , a2 ,... ,an trong đó i phần tử đầu tiên a1 , a2 ,... ,ai-1 đã có thứ tự. Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực tiếp là tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 £ ai < ak (1£k£i).
Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 a2 a3 được sắp; tiếp tục cho đến khi thêm xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2.... aN được sắp. Các bước tiến hành như sau :
Bước 1: i = 2; // giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i];
Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i]
Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i £ n : Lặp lại Bước 2.
Ngược lại : Dừng.
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Dừng
Cài đặt
Cài đặt thuật toán sắp xếp chèn trực tiếp thành hàm InsertionSort
void InsertionSort(int a[], int N )
{ int pos, i;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{// kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x]; // chèn x vào dãy
}
}
Nhận xét
Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn đã được sắp, nên có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos, khi đó có giải thuật sắp xếp chèn nhị phân :
void BInsertionSort(int a[], int N )
{ int l,r,m,i;
int x; //lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++)
{ x = a[i]; l = 1; r = i-1;
while(i<=r) // tìm vị trí chèn x
{ m = (l+r)/2; // tìm vị trí thích hợp m
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j]; // dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy
}
}
Đánh giá giải thuật
Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Giải thuật thực hiện tất cả N-1 vòng lặp while , do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau :
Trường hợp Số phép so sánh Số phép gán
Tốt nhất
Xấu nhất
2.4.1.3 Phương pháp đổi chỗ trực tiếp (InterchangeSort)
Giải thuật
Bước 1 : i = 1;// bắt đầu từ đầu dãy
Bước 2 : j = i+1;//tìm các phần tử a[j] < a[i], j>i
Bước 3 : Trong khi j £ N thực hiện
Nếu a[j]<a[i]: a[i]«a[j]; //xét cặp a[i], a[j]
j = j+1;
Bước 4 : i = i+1;
Nếu i < n: Lặp lại Bước 2.
Ngược lại: Dừng.
Ví dụ : Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu đổi chỗ trực tiếp thành hàm InterchangeSort:
void InterchangeSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ
Hoanvi(a[i],a[j]);
}
Ðánh giá giải thuật
Ðối với giải thuật đổi chỗ trực tiếp, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất
0
Xấu nhất
2.4.1.4 Phương pháp nổi bọt (Bubble sort)
Giải thuật
Ý tưởng chính của giải thuật là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. Các bước tiến hành như sau :
Bước 1 : i = 1; // lần xử lý đầu tiên
Bước 2 : j = N; //Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j < i) thực hiện:
Nếu a[j]<a[j-1]: a[j]«a[j-1]; //xét cặp phần tử kế cận
j = j-1;
Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu i >N-1: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2.
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu nổi bọt thành hàm BubbleSort:
void BubleSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =N-1; j >i ; j --)
if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ
Hoanvi(a[j],a[j-1]);
}
Ðánh giá giải thuật
Ðối với giải thuật nổi bọt, số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như sau :
Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất
0
Xấu nhất
Nhận xét
BubbleSort có các khuyết điểm sau: không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần. Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm.
2.4.1.5 Phương pháp nổi bọt cải tiến (Shake sort)
Giải thuật
Giải thuật sắp xếp ShakerSort cũng dựa trên nguyên tắc đổi chỗ trực tiếp, nhưng tìm cách khắc phục các nhược điểm của BubleSort với những ý tưởng cải tiến chính như sau :
Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phiá khác nhau :
+ Lượt đi: đẩy phần tử nhỏ về đầu mảng
+ Lượt về: đẩy phần tử lớn về cuối mảng
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Các bước tiến hành như sau :
Ý tưởng chính của giải thuật là xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. Các bước tiến hành như sau :
Bước 1 :
l = 1; r = n; //từ l đến r là đoạn cần được sắp xếp
k = n; // ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sở thu hẹp đoạn l đến r
Bước 2 :
Bước 2a :
j = r ; // đẩy phần tử nhỏ về đầu mảng
Trong khi (j > l) :
Nếu a[j]<a[j-1]: a[j] « a[j-1];
k = j; //lưu lại nơi xảy ra hoán vị
j = j - 1;
l = k; //loại các phần tử đã có thứ tự ở đầu dãy
Bước 2b :
j = l ; // đẩy phần tử lớn về cuối mảng
Trong khi (j < r) :
Nếu a[j]>a[j+1]:a[j] « a[j+1];
k = j; //lưu lại nơi xảy ra hoán vị
j = j+1;
r = k; //loại các phần tử đã có thứ tự ở cuối dãy
Bước 3 : Nếu l < r: Lặp lại Bước 2.
Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Cài đặt
Cài đặt thuật toán sắp xếp theo kiểu nổi bọt cải tiến thành hàm ShakeSort:
void ShakeSort(int a[], int N )
{ int i, j;
int left, right, k;
left = 0; right = n-1; k = n-1;
while (left < right)
{
for (j = right; j > left; j --)
{
if ( a[j]< a[j-1]) // sai vị trí thì đổi chỗ
{ Hoanvi(a[j],a[j-1]);
k = j;
}
}
left = k;
for (j = left; j < right; j ++)
{
if (a[j]> a[j+1]) // sai vị trí thì đổi chỗ
{ Hoanvi(a[j],a[j-1]);
k = j;
}
}
right = k;
}
}
Bạn đang đọc truyện trên: Truyen2U.Pro