Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý, dữ liệu có thể là dữ liệu vào, dữ liệu trung gian hoặc dữ liệu ra. Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc xây dựng cấu trúc dữ liệu (CTDL) quyết định rất lớn đến chất lượng cũng như công sức của người lập trình trong việc thiết kế và cài đặt chương trình.

1.2. Giải thuật

Khái niệm giải thuật hay thuật giải nhiều khi còn được gọi là thuật toán dùng để chỉ phương pháp hay cách thức để giải quyết vấn đề. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả dựa trên 1 hay 1 số ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà người lập trình chọn để cài đặt thuật toán) như Pascal, C,...

Khi đã xác định được CTDL thích hợp, người lập trình sẽ bắt đầu tiến hành xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở CTDL đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy sự lựa chọn phương pháp phù hợp là việc mà người lập trình cần phải cân nhắc và tính toán lựa chọn. Sự lựa chọn này cũng góp phần đáng kể trong việc giảm bớt công việc của người lập trình trong phần cài đặt trên một ngôn ngữ cụ thể.

1.3. Mối liên hệ giữa giải thuật và cấu trúc dữ liệu

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 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 cho bài toán.

Tuy nhiên khi giải quyết một bài toán trên máy tính, chúng ta thường có khuynh hướng chỉ chú trọng đến việc xây dựng giải thuật mà quên đi tầm quan trọng của việc tổ chức dữ liệu trong bài toán. Giải thuật phản ánh các phép xử lý , còn đối tượng xử lý của giải thuật lại là dữ liệu, chính dữ liệu chứa đựng các thông tin cần thiết để thực hiện giải thuật. Để xác định được giải thuật phù hợp cần phải biết nó tác động đến loại dữ liệu nào (ví dụ để làm nhuyễn các hạt đậu , người ta dùng cách xay chứ không băm bằng dao, vì đậu sẽ văng ra ngoài) và khi chọn lựa cấu trúc dữ liệu cũng cần phải hiểu rõ những thao tác nào sẽ tác động đến nó (ví dụ để biểu diễn các điểm số của sinh viên người ta dùng số thực thay vì chuỗi ký tự vì còn phải thực hiện thao tác tính trung bình từ những điểm số đó). Như vậy 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

Với một cấu trúc dữ liệu đã chọn, sẽ có những giải thuật tương ứng, phù hợp. Khi cấu trúc dữ liệu thay đổi thường giải thuật cũng phải thay đổi theo để tránh việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp. Hơn nữa, một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn, vừa đáp ứng nhanh vừa tiết kiệm vật tư, giải thuật cũng dễ hiễu và đơn giản hơn.

1.2. Kiểu dữ liệu, mô hình dữ liệu, kiểu dữ liệu trừu tượng

1.2.1. Kiểu dữ liệu

Khái niệm

Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần:

Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V,
Tập hợp các phép toán để thao tác dữ liệu: O.

T = <V, O>

Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu có kiểu T sẽ có giá trị trong miền V và có thể được thực hiện các phép toán thuộc tập hợp các phép toán trong O.

Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ nhớ, số byte(s) này gọi là kích thước của kiểu dữ liệu.

Các kiểu dữ liệu cơ bản

Hầu hết các ngôn ngữ lập trình đều có cung cấp các kiểu dữ liệu cơ bản. Tùy vào mỗi ngôn ngữ mà các kiểu dữ liệu cơ bản có thể có các tên gọi khác nhau song chung quy lại có những loại kiểu dữ liệu cơ bản như sau:

Kiểu số nguyên: Có thể có dấu hoặc không có dấu và thường có các kích thước sau:

Kiểu số nguyên 1 byte
Kiểu số nguyên 2 bytes
Kiểu số nguyên 4 bytes

Kiểu số nguyên thường được thực hiện với các phép toán: O = {+, -, *, /, DIV, MOD, <, >, <=, >=, =, …}

Kiểu số thực: Thường có các kích thước sau:

Kiểu số thực 4 bytes
Kiểu số thực 6 bytes
Kiểu số thực 8 bytes
Kiểu số thực 10 bytes

Kiểu số thực thường được thực hiện với các phép toán: O = {+, -, *, /, <, >, <=, >=, =, …}

Kiểu ký tự: Có thể có các kích thước sau:

Kiểu ký tự 1 byte
Kiểu ký tự 2 bytes

Kiểu ký tự thường được thực hiện với các phép toán: O = {+, -, <, >, <=, >=, =, ORD, CHR, …}

Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình

Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O = {+, &, <, >, <=, >=, =, Length, Trunc, …}

Kiểu luận lý: Thường có kích thước 1 byte

Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, XOR, <, >, <=, >=, =, …}

Các kiểu dữ liệu nâng cao

Các kiểu dữ liệu này ta sẽ tìm hiểu cụ thể ở chương 2.

1.2.2. Mô hình dữ liệu

Mô hình dữ liệu là mô hình toán học được biểu diễn trên máy tính.

Mô hình dữ liệu thường dùng: danh sách, cây, đồ thị, bảng băm...

Ví dụ:

Bài toán tìm đường đi ngắn nhất từ Trường CĐN Cơ điện Hà Nội đến Siêu thị Metro Thăng Long ta sử dụng đồ thị.

Bài toán về quản lí sinh viên ta sử dụng danh sách.

1.3. Thiết kế và phân tích giải thuật

1.3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu

Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán mà chúng ta cho là "tốt" nhất. Vậy ta cần lựa chọn thuật toán dựa trên cơ sở nào? Một cấu trúc dữ liệu tốt phải thỏa mãn các tiêu chuẩn sau:

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

Khi ta viết một chương trình chỉ để sử dụng một số ít lần, và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chưong trình thì tiêu chuẩn (1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương trình (hoặc thủ tục, hàm) để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp, tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người trong các bài toán khác nhau. Trong trường hợp này ta cần dựa trên tiêu chuẩn (2). Ta sẽ cài đặt thuật toán có thể rất phức tạp, miễn là chương trình nhận được chạy nhanh hơn các chương trình khác.

Tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán. Tính hiệu quả của thuật toán bao gồm hai nhân tố cơ bản.

1. Dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán.

2. Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy).

Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện thuật toán. Vì vậy, khi nói đến đánh giá độ phức tạp của thuật toán, có nghĩa là ta nói đến đánh gia thời gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có thời gian chạy ít hơn các thuật toán khác.

1.3.2. Đánh giá thời gian thực hiện thuật toán

Có hai cách tiếp cận để đánh giá thời gian thực hiện của một thuật toán.Trong phương pháp thử nghiệm, chúng ta viết chương trình và cho chạy chương trình với các dữ liệu vào khác nhau trên một máy tính nào đó. Thời gian chạy chương trình phụ thuộc vào các nhân tố chính sau đây :

1. Các dữ liệu vào

2. Chương trình dịch để chuyển chương trình nguồn thành mã máy.

3. Tốc độ thực hiện các phép toán của máy tính được sử dụng để chạy chương trình.

Vì thời gian chạy chương trình phụ thuộc vào nhiều nhân tố, nên ta không thể biểu diễn chính xác thời gian chạy là bao nhiêu đơn vị thời gian chuẩn, chẳng hạn nó là bao nhiêu giây.

Trong phương pháp lý thuyết (đó là phương pháp được sử dụng trong sách này), ta sẽ coi thời gian thực hiện thuật toán như là hàm số của cỡ dữ liệu vào. Cỡ của dữ liệu vào là một tham số đặc trưng cho dữ liệu vào, nó có ảnh hưởng quyết định đến thời gian thực hiện chương trình. Cái mà chúng ta chọn làm cỡ của dữ liệu vào phụ thuộc vào các thuật toán cụ thể. Đối với các thuật toán sắp xếp mảng, cỡ của dữ liệu là số thành phần của mảng. Đối với thuật toán giải hệ n phương trình tuyến tính với n ẩn, ta chọn n là cỡ. Thông thường cỡ của dữ liệu vào là một số nguyên dương n. Ta sẽ sử dụng hàm số T(n), trong đó n là cỡ dữ liệu vào, để biểu diễn thời gian thực hiện của một thuật toán.

Thời gian thực hiện thuật toán T(n) nói chung không chỉ phụ thuộc vào cỡ của dữ liệu vào, mà còn phụ thuộc vào dữ liệu vào cá biệt. Chẳng hạn, ta xét bài toán xác định một đối tượng a có mặt trong danh sách n phần tử (a₁, a₂, ... a_n) hay không. Thuật toán ở đây là, so sánh a với từng phần tử của danh sách đi từ đầu đến cuối danh sách, khi gặp phần tử a_i đầu tiên a_i = a thì dừng lại, hoặc đi đến hết danh sách mà không gặp a_i nào bằng a, trong trường hợp này a không có trong danh sách. Các dữ liệu vào là a và danh sách (a₁, a₂, ..., a_n) (có thể biểu diễn danh sách bằng mảng, chẳng hạn). Cỡ của dữ liệu vào là n. Nếu a₁ = a chỉ cần một phép so sánh. Nếu a₁a, a₂ = a, cần 2 phép so sánh. Còn nếu a_i  a, i = 1, ..., n-1 và a_n = a, hoặc a không có trong danh sách, ta cần n phép so sánh. Nếu xem thời gian thực hiện T(n) là số phép toán so sánh, ta có T(n) <= n, trong trường hợp xấu nhất T(n) = n. Trong các trường hợp như thế, ta nói đến thời gian thực hiện thuật toán trong trường hợp xấu nhất.

Ngoài ra, ta còn sử dụng khái niệm thời gian thực hiện trung bình. Đó là thời gian trung bình T_tb(n) trên tất cả các dữ liệu vào có cỡ n. Nói chung thời gian thực hiện trung bình khó xác định hơn thời gian thực hiện trong trường hợp xấu nhất.

Chúng ta có thể xác định thời gian thực hiện T(n) là số phép toán sơ cấp cần phải tiến hành khi thực hiện thuật toán. Các phép toán sơ cấp là các phép toán mà thời gian thực hiện bị chặn trên bởi một hằng số chỉ phụ thuộc vào cách cài đặt được sử dụng (ngôn ngữ lập trình, máy tính ...). Chẳng hạn các phép toán số học +, - , *, /, các phép toán so sánh = , < >, <, <= , > , > = là các phép toán sơ cấp. Phép toán so sánh hai xâu ký tự không thể xem là phép toán sơ cấp, vì thời gian thực hiện nó phụ thuộc vào độ dài của xâu.

1.4. Một số ví dụ về thiết kế và phân tích giải thuật

Ví dụ 1: Một chương trình quản lý điểm thi của sinh viên cần lưu trữ các điểm số của 3 sinh viên. Do mỗi sinh viên có 4 điểm số ứng với 4 môn học khác nhau nên dữ liệu có dạng bảng như sau:

Sinh viên	Môn 1	Môn 2	Môn3	Môn4
SV 1	7	9	5	2
SV 2	5	0	9	4
SV 3	6	3	7	4

Chỉ xét thao tác xử lý là xuất điểm số các môn của từng sinh viên.

Giả sử có các phương án tổ chức lưu trữ sau:

Phương án 1 : Sử dụng mảng một chiều

Có tất cả 3(SV)*4(Môn) = 12 điểm số cần lưu trữ, do đó khai báo mảng result như sau :

int result [ 12 ] = {7, 9, 5, 2,

5, 0, 9, 4,

6, 3, 7, 4};

khi đó trong mảng result các phần tử sẽ được lưu trữ như sau:

Và truy xuất điểm số môn j của sinh viên i - là phần tử tại (dòng i, cột j) trong bảng - phải sử dụng một công thức xác định chỉ số tương ứng trong mảng result:

bảngđiểm(dòng i, cột j)  result[((i-1)*số cột) + j]

Ngược lại, với một phần tử bất kỳ trong mảng, muốn biết đó là điểm số của sinh viên nào, môn gì, phải dùng công thức xác định sau

result[ i ]  bảngđiểm (dòng((i / số cột) +1), cột (i % số cột) )

Với phương án này, thao tác xử lý được cài đặt như sau :

void XuatDiem() //Xuất điểm số của tất cả sinh viên

{

const int so_mon = 4;

int sv,mon;

for (int i=0; i<12; i+)

{

sv = i/so_mon;

mon = i % so_mon;

printf("Điểm môn %d của sv %d là: %d", mon, sv,result[i]);

}

Phương án 2 : Sử dụng mảng 2 chiều

Khai báo mảng 2 chiều result có kích thước 3 dòng* 4 cột như sau :

int result[3][4] ={{ 7, 9, 5, 2},

{ 5, 0, 9, 4},

{ 6, 3, 7, 4 }};

khi đó trong mảng result các phần tử sẽ được lưu trữ như sau:

	Cột 0	Cột 1	Cột 2	Cột 3
Dòng 0	result[0][0] =7	result[0][1] =9	result[0][2] =5	result[0][3] =2
Dòng 1	result[1][0] =5	result[1][1] =0	result[1][2] =9	result[1][3] =4
Dòng 2	result[2][0] =6	result[2][1] =3	result[2][2] =7	result[2][3] =4

Và truy xuất điểm số môn j của sinh viên i, là phần tử tại (dòng i, cột j) trong bảng, cũng chính là phần tử nằm ở vị trí (dòng i, cột j) trong mảng

bảngđiểm(dòng i,cột j)  result[ i] [j]

Với phương án này, thao tác xử lý được cài đặt như sau :

void XuatDiem() //Xuất điểm số của tất cả sinh viên

{

int so_mon = 4, so_sv =3;

for ( int i=0; i<so_sv; i+)

for ( int j=0; i<so_mon; j+)

printf("Điểm môn %d của sv %d là: %d", j, i,result[i][j]);

}

Nhận xét:

Có thể thấy rõ phương án 2 cung cấp một cấu trúc lưu trữ phù hợp với dữ liệu thực tế hơn phương án 1, và do vậy giải thuật xử lý trên cấu trúc dữ liệu của phương án 2 cũng đơn giản, tự nhiên hơn.

1.5. Bài tập

Câu hỏi 1: Trình bày tầm quan trọng của Cấu trúc dữ liệu và Giải thuật đối với người lập trình?

Câu hỏi 2: Liệt kê các kiểu dữ liệu cơ bản trong C++?

Bài tập 1: Phân tích thuật toán Euclid tính ước chung lớn nhất của 2 số tự nhiên.

Bài tập 2: Xây dựng sơ đồ giải thuật cho bài toán tính số Fibonaci thứ N, biết rằng dãy số Fibonaci được định nghĩa như sau:

F[0] = F[1] = 1, F[N] = F[N-1] + F[N-2] với N ≥ 2

Bài tập 3: Xây dựng sơ đồ giải thuật và phân tích bài toán tính biểu thức sau:

Với n số x thực, n và x nhập từ bàn phím

Bài tập 4: Trình bày thuật toán của bài toán sau bằng ngôn ngữ tự nhiên, lưu đồ và mã giả.

Nhập vào 2 số nguyên a và b. Giải phương trình: ax + b = 0.

Bài tập 5: Trình bày thuật toán của bài toán sau bằng ngôn ngữ tự nhiên, lưu đồ và mã giả

Nhập vào 3 số nguyên a, b và c. Giải phương trình: ax² + bx + c = 0.

Chương 2. Các kiểu dữ liệu nâng cao

2.1. Mảng

Mảng là một dãy liên tục các ô nhớ có cùng kiểu dữ liệu và cùng tên. Do đó để truy xuất các thành phần của mảng, ta dùng cơ chế chỉ mục.

Khai báo mảng 1 chiều

<kiểu dữ liệu> <Tên mảng> [Số phần tử tối đa];

Ví dụ: int A[10];

Truy xuất mảng 1 chiều:

<Tên mảng> [chỉ số];

Ví dụ: A[3];

Chỉ_số là số thứ tự của phần tử trong mảng, các phần tử của mảng được đánh chỉ số bắt đầu từ 0. Với mảng có n phần tử thì các phần tử của nó có chỉ số là 0, 1,..,n-1.

Khai báo mảng 2 chiều

<kiểu> <Tên mảng> [Số dòng][Số cột];

Ví dụ : int A[10][10];

Truy xuất mảng 2 chiều

Tên mảng[chỉ số dòng][chỉ số cột];

Ví dụ: A[1][2];

2.2. Con trỏ

Khái niệm

Con trỏ là một biến dùng để chứa địa chỉ. Vì có nhiều kiểu dữ liệu nên cũng có nhiều kiểu con trỏ tương ứng. Kiểu con trỏ int dùng để chứa địa chỉ biến kiểu int. Tương tự ta có con trỏ kiểu float, kiểu double,…

Cũng như với 1 biến bất kỳ nào khác, con trỏ cần được khai báo trước khi sử dụng.

Toán tử lấy địa chỉ (&)

Địa chỉ: Khi khai báo biến, máy sẽ cấp phát cho biến một khoảng nhớ. Địa chỉ của biến là số thứ tự của byte đầu tiên trong một dãy các byte liên tiếp mà máy dành cho biến (các byte được đánh số từ 0).

Máy phân biệt các loại địa chỉ như các biến. Ví dụ như: địa chỉ kiểu int, kiểu float,…

Vào thời điểm mà chúng ta khai báo một biến thì nó phải được lưu trữ trong một vị trí cụ thể trong bộ nhớ. Chúng ta không quyết định nơi nào biến đó được đặt, điều đó làm tự động bởi trình biên dịch và hệ điều hành. Nhưng khi hệ điều hành đã gán một địa chỉ cho biến thì chúng ta cần biết biến đó được lưu trữ ở đâu. Điều này được thực hiện bằng cách đặt trước tên biến một dấu và (&).

Ví dụ: x = &y;

Giải thích: Gán cho biến x địa chỉ của biến y vì khi đặt trước tên biến y dấu & ta không nói đến nội dung của biến nữa mà chỉ nói đến địa chỉ của nó trong bộ nhớ.

Giả sử biến y được đặt trọng ô nhớ có địa chỉ là 1202 và có các câu lệnh như sau:

y = 30;

z = y;

x = &y;

Kết quả: z = 30; x = 1202;

Chú ý: Có thể định nghĩa con trỏ như sau: Những biến lưu trữ địa chỉ của biến khác được gọi là con trỏ. Ở ví dụ trên, biến x là con trỏ.

Toán tử tham chiếu (*)

Bằng cách sử dụng con trỏ chúng ta có thể truy xuất trực tiếp đến giá trị được lưu trữ trong biến được trỏ bởi nó bằng cách đặt trước tên biến con trỏ một dấu (*).

Ví dụ: Giả sử biến y được đặt trong ô nhớ có địa chỉ là 1202 và có các câu lệnh như sau:

y = 30;

z = y;

x = &y;

t = *y;

Kết quả: biến t sẽ mang giá trị là 30.

Khai báo biến kiểu con trỏ.

Vì con trỏ có khả năng tham chiếu trực tiếp đến giá trị mà chúng trỏ tới nên cần thiết phải chỉ rõ kiểu dữ liệu nào mà một biến con trỏ trỏ tới khi khai báo.

Cấu trúc khai báo:

Kiểu_dữ_liệu *Tên_con_trỏ;

Chú ý: kiểu dữ liệu ở đây là kiểu dữ liệu được trở tới, không phải là kiểu của bản thân con trỏ.

Ví dụ:

int *x; //Khai báo con trỏ x kiểu int

float *t; //Khai báo con trỏ t kiểu float

Chú ý: dấu (*) khi khai báo biến kiểu con trỏ chỉ có nghĩa rằng đó là một con trỏ, không liên quan đến toán tử tham chiếu.

Ví dụ đơn giản về sử dụng con trỏ: khai báo, sử dụng toán tử tham chiếu, toán tử lấy địa chỉ:

#include<iostream.h>

main()

{

int x1 = 5, x2 = 15;

int *y;

y = &x1;

*y = 10;

y = &x2;

*y = 20;

cout<<“Gia tri 1 = “<<x1<<“\n Gia tri 2 = “<<x2;

return 0;

}

Kết quả: x1 = 10; x2 = 20;

2.3. Cấu trúc, hợp

2.3.1. Cấu trúc

Khái niệm cấu trúc

Cấu trúc (struct) thực chất là một kiểu dữ liệu do người dùng định nghĩa bằng cách gom nhóm các kiểu dữ liệu cơ bản có sẵn trong C++ thành một kiểu dữ liệu phức hợp nhiều thành phần.

Cấu trúc giúp cho việc tổ chức các dữ liệu phức tạp, đặc biệt trong những chương trình lớn vì trong nhiều tình huống chúng cho phép nhóm các biến có liên quan lại để xử lý như một đơn vị thay vì các thực thể tách biệt.

Một ví dụ là cấu trúc Sinh viên, trong đó mỗi sinh viên được mô tả bởi tập hợp các thuộc tính như: Họ tên, Ngày sinh, Địa chỉ, Tên lớp, Điểm,.. một số trong các thuộc tính này lại có thể là cấu trúc bởi trong nó có thể chứa nhiều thành phần như: Họ tên gồm: họ, tên đệm, tên; Địa chỉ: xã (phường, thị trấn), huyện (quận), tỉnh (thành phố)…

Khai báo cấu trúc

Khi xây dựng cấu trúc, ta cần mô tả kiểu của nó. Điều này cũng tương tự như việc phải thiết kế ra một kiểu nhà trước khi đi xây dựng căn nhà thực sự. Công việc định nghĩa một kiểu cấu trúc bao gồm việc nêu ra tên của kiểu cấu trúc và các thành phần của nó theo 2 cách sau:

struct <tên kiểu cấu trúc>

{

Khai báo các thành phần của cấu trúc

};

Trong đó:

struct: là từ khóa.

Tên_kiểu_cấu_trúc: là một tên bất kỳ do người lập trình tự đặt theo quy định đặt tên của C/C++.

Thành phần của cấu trúc có thể là: biến, mảng, cấu trúc khác đã được định nghĩa trước đó,…

Ví dụ

struct Sinhvien

{

char Hoten;

float Diem;

char Diachi;

};

Truy cập các thành phần kiểu cấu trúc

Để truy cập vào các thành phần kiểu cấu trúc ta sử dụng cú pháp:

Đối với biến thường: tên biến.tên thành phần

Đối với biến con trỏ: tên biến → tên thành phần

Đối với biến mảng: Truy cập thành phần mảng rồi đến thành phần cấu trúc

Đối với cấu trúc lồng nhau: Truy cập thành phần ngoài rồi đến thành phần của cấu trúc bên trong.

2.3.2. Hợp

Khai báo

Giống như cấu trúc, kiểu hợp cũng có nhiều thành phần nhưng các thành phần của chúng sử dụng chung nhau một vùng nhớ. Do vậy kích thước của một kiểu hợp là độ dài của trường lớn nhất và việc thay đổi một thành phần sẽ ảnh hưởng đến tất cả các thành phần còn lại.

union <tên kiểu>

{

Danh sách các thành phần;

};

Truy cập

Sử dụng toán tử lấy thành phần: dấu chấm . hoặc → cho biến con trỏ kiểu hợp

Ví dụ:

Void main()

{

union songuyen{

int n;

unsigned char c[2];

} x;

cout << “Nhập số nguyên:”; cin >> x.n;

cout << “Byte thấp nhất của x = ” << x.c[0] << endl;

cout << “Byte cao nhất của x = ” << x.c[1] << endl;

}

2.4. Tập tin

Khái niệm tập tin (File)

Tệp tin hay tệp dữ liệu là một tập hợp các dữ liệu có liên quan với nhau và có cùng một kiểu được nhóm lại thành một dãy. Chúng thường được chứa trong một thiết bị nhớ ngoài của máy tính (đĩa mềm, đĩa cứng,…) dưới một cái tên nào đó.

Tệp là một kiểu dữ liệu có cấu trúc. Định nghĩa của tệp có phần nào giống mảng ở chỗ chúng đều là tập hợp của các phần tử dữ liệu có cùng kiểu. Song mảng được định nghĩa và khai báo trong chương trình với số phần tử đã được xác định còn số phần tử của tệp không được xác định khi định nghĩa.

Tệp được chứa trong bộ nhớ ngoài, điều đó có nghĩa là tệp được lưu trữ để dùng nhiều lần và tồn tại ngay cả khi chương trình kết thúc hoặc mất điện.

Có 2 loại tập tin:

+ Tập tin văn bản: là tập tin dùng để ghi các ký tự lên đĩa theo các dòng.

Tệp tin văn bản là tệp chứa các phần tử ký tự là các chữ cái (viết hoa, viết thường); chữ số: ;0’, ‘1’, …, ‘9’; các dấu chấm câu, không kể các ký tự điều khiển. Các ký tự này được tổ chức thành từng dòng với dấu kết thúc dòng là CR ( Carriage Return - Về đầu dòng, mã Ascii là 13 )= ‘\r’ và LF (Line Feed - Xuống dòng, mã Ascii là 10) = ‘\n’, tệp văn bản dùng ký tự ^Z (xác định bởi tổ hợp phím Ctrl_Z) có mã ASCII là 26 để làm ký hiệu kết thúc tệp. Vì vậy, tệp văn bản có thể đọc được trên màn hình, có thể soạn thảo với các phần mềm soạn thảo văn bản.

+ Tập tin nhị phân: là tập tin dùng để ghi các cấu trúc dạng nhị phân (được mã hóa).

Tệp tin nhị phân chứa khá nhiều dữ liệu có mã điều khiển là các ký tự có mã ASCII từ 0 đến 31. Nếu một xâu ký tự được ghi ra tệp nhị phân thì kí hiệu hết dòng của nó chỉ còn có LF = ‘\n’, không có ký tự CR = ‘\r’.

Tạo file đọc file

Quá trình thao tác trên tập tin thông qua 4 bước:

Bước 1: Khai báo con trỏ trỏ đến tập tin.

Bước 2: Mở tập tin.

Bước 3: Các xử lý trên tập tin.

Bước 4: Đóng tập tin.

Khai báo con trỏ trỏ đến tập tin

Cú pháp: FILE *Tên_biến;

Ví dụ: FILE *f; //Khai báo biến con trỏ file f;

FILE *vb,*np; //Khai báo 2 biến con trỏ tệp.

Chú ý:

Trước khi khai báo con trỏ trỏ đến tập tin, cần khai báo thư viện: stdio.h.

Mỗi tệp đều được kết thúc bằng một dấu hiệu đặc biệt để báo hiệu hết tệp, hay gọi là EOF (End of File). Giá trị EOF trong UNIX được định nghĩa là -1, trong chương trình dịch C/C++ khác có thể có các giá trị khác.
C/C++ có một hàm chuẩn feof, theo kiểu Boolean, với tham số là một biến tệp để thử xem cửa sổ đã đặt vào vị trí kết thúc tệp đó chưa. Nếu cửa sổ còn chưa trỏ vào phần tử cuối tệp thì feof có giá trị là False, tức là bằng 0. Sử dụng hàm feof() sẽ an toàn và chính xác hơn.

2.5. Bài tập

Bài 1: Sử dụng các kiểu dữ liệu cơ bản trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ trong (RAM) của máy tính đa thức có bậc tự nhiên n (0 _ n _ 100) trên trường số thực (ai , x _ R):

Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để thực hiện các công việc sau:

- Nhập, xuất các đa thức.

- Tính giá trị của đa thức tại giá trị x0 nào đó.

- Tính tổng, tích của hai đa thức.

Bài 2: Tương tự như bài tập 1. nhưng đa thức trong trường số hữu tỷ Q (các hệ số ai và x là các phân số có tử số và mẫu số là các số nguyên).

Bài 3: Hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ trong (RAM) của máy tính trạng thái của các cột đèn giao thông (có 3 đèn: Xanh, Đỏ, Vàng). Với cấu trúc dữ liệu đã được xây dựng, hãy trình bày thuật toán để mô phỏng cho hoạt động của 2 cột đèn trên hai tuyến đường giao nhau tại một ngã tư.

Bài 4: Hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ trong (RAM) của máy tính trạng thái của một bàn cờ CARO có kích thước M×N (0 _ M, N _ 20). Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán để thực hiện các công việc sau:

- In ra màn hình bàn cờ CARO trong trạng thái hiện hành.

- Kiểm tra xem có ai thắng hay không? Nếu có thì thông báo “Kết thúc”, nếu không có thì thông báo “Tiếp tục”.

Chương 3. Danh sách

3.1. Danh sách đặc

3.1.1. Định nghĩa

Danh sách đặc là danh sách mà không gian bộ nhớ lưu trữ các phần tử được đặt liên tiếp nhau trong bộ nhớ.

3.1.2. Biểu diễn danh sách đặc

Để biểu diễn danh sách đặc chúng ta sử dụng một dãy (mảng) các phần tử có kiểu dữ liệu là kiểu dữ liệu của các phần tử trong danh sách. Do vậy, chúng ta cần biết trước số phần tử tối đa của mảng cũng chính là chiều dài tối đa của danh sách thông qua một hằng số nguyên. Ngoài ra, do chiều dài của danh sách luôn luôn biến động cho nên chúng ta cũng cần quản lý chiều dài thực của danh sách thông qua một biến nguyên.

Giả sử chúng ta quy ước chiều dài tối đa của danh sách đặc là 10000, khi đó cấu trúc dữ liệu để biểu diễn danh sách đặc như sau:

const int MaxLen = 10000; // hoặc: #define MaxLen 10000

int Length;

T CD_LIST[MaxLen]; // hoặc: T * CD_LIST = new T[MaxLen];

Nếu chúng ta sử dụng cơ chế cấp phát động để cấp phát bộ nhớ cho danh sách đặc thì cần kiểm tra sự thành công của việc cấp phát động.

3.1.3. Các thao tác trên danh sách đặc

Các thao tác cơ bản trên danh sách đặc như sau:

3.1.3.1. Khởi tạo danh sách (Initialize):

Trong thao tác này chỉ đơn giản là chúng ta cho chiều dài của danh sách về 0. Hàm khởi tạo danh sách đặc như sau:

void CD_Initialize(int &Len)

{

Len = 0;

return;

}

3.1.3.2. Tạo mới danh sách/ Nhập danh sách:

Hàm CD_Create_List có prototype:

int CD_Create_List(T M[], int &Len);

Hàm tạo danh sách đặc có chiều dài tối đa MaxLen. Hàm trả về chiều dài thực của danh sách sau khi tạo.

Nội dung của hàm như sau:

int CD_Create_List(T M[], int &Len)

{ if (Len > MaxLen)

Len = MaxLen;

for (int i = 0; i < Len; i++)

M[i] = Input_One_Element();

return (Len);

}

Lưu ý: Hàm Input_One_Element thực hiện nhập vào nội dung của một phần tử có kiểu dữ liệu T và trả về giá trị của phần tử mới nhập vào. Tùy vào từng trường hợpcụ thể mà chúng ta viết hàm Input_One_Element cho phù hợp.

3.1.3.3. Thêm một phần tử vào trong danh sách

Giả sử chúng ta cần thêm một phần tử có giá trị NewValue vào trong danh sách M có chiều dài Length tại vị trí InsPos.

- Thuật toán:

B1: IF (Length = MaxLen)

Thực hiện Bkt

//Dời các phần tử từ vị trí InsPos->Length ra sau một vị trí

B2: Pos = Length+1

B3: IF (Pos = InsPos)

Thực hiện B7

B4: M[Pos] = M[Pos-1]

B5: Pos--

B6: Lặp lại B3

B7: M[InsPos] = NewValue //Đưa phần tử có giá trị NewValue vào vị trí InsPos

B8: Length++ //Tăng chiều dài của danh sách lên 1

Bkt: Kết thúc

- Cài đặt thuật toán:

Hàm CD_Insert_Element có prototype:

int CD_Insert_Element(T M[], int &Len, T NewValue, int InsPos);

Hàm thực hiện việc chèn phần tử có giá trị NewValue vào trong danh sách M có chiều dài Len tại vị trí InsPos. Hàm trả về chiều dài thực của danh sách sau khi chèn nếu việc chèn thành công và ngược lại, hàm trả về giá trị -1. Nội dung của hàm như sau:

int CD_Insert_Element(T M[], int &Len, T NewValue, int InsPos)

{ if (Len == MaxLen)

return (-1);

for (int i = Len; i > InsPos; i--)

M[i] = M[i-1];

M[InsPos] = NewValue;

Len++;

return (Len);

}

3.1.3.4. Tìm kiếm một phần tử trong danh sách

Thao tác này chúng ta sử dụng các thuật toán tìm kiếm nội (Tìm tuyến tính hoặc tìmnhị phân) sẽ trình bày cụ thể trong chương sau.

1.3.5. Loại bỏ bớt một phần tử ra khỏi danh sách

Giả sử chúng ta cần loại bỏ phần tử tại vị trí DelPos trong danh sách M có chiều dài Length (Trong một số trường hợp có thể chúng ta phải thực hiện thao tác tìm kiếm để xác định vị trí của phần tử cần xóa).

- Thuật toán:

B1: IF (Length = 0 OR DelPos > Len)

Thực hiện Bkt

//Dời các phần tử từ vị trí DelPos+1->Length ra trước một vị trí

B2: Pos = DelPos

B3: IF (Pos = Length)

Thực hiện B7

B4: M[Pos] = M[Pos+1]

B5: Pos++

B6: Lặp lại B3

B7: Length-- //Giảm chiều dài của danh sách đi 1

Bkt: Kết thúc

- Cài đặt thuật toán:

Hàm CD_Delete_Element có prototype:

int CD_Delete_Element(T M[], int &Len, int DelPos);

Hàm thực hiện việc xóa phần tử tại vị trí DelPos trong danh sách M có chiều dài Len. Hàm trả về chiều dài thực của danh sách sau khi xóa nếu việc xóa thành công và ngược lại, hàm trả về giá trị -1. Nội dung của hàm như sau:

int CD_Delete_Element(T M[], int &Len, int DelPos)

{ if (Len == 0 || DelPos >= Len)

return (-1);

for (int i = DelPos; i < Len-1; i++)

M[i] = M[i+1];

Len--;

return (Len);

}

3.1.3.6. Cập nhật giá trị cho một phần tử trong danh sách

Giả sử chúng ta cần sửa đổi phần tử tại vị trí ChgPos trong danh sách M có chiều dài Length thành giá trị mới NewValue. Thao tác này chỉ đơn giả là việc gán lại giá trị mới cho phần tử cần thay đổi: M[ChgPos] = NewValue;

Trong một số trường hợp, trước tiên chúng ta phải thực hiện thao tác tìm kiếm phần tử cần thay đổi giá trị để xác định vị trí của nó sau đó mới thực hiện phép gán như trên.

3.1.3.7. Sắp xếp thứ tự các phần tử trong danh sách

Thao tác này chúng ta sử dụng các thuật toán sắp xếp nội (trên mảng) đã trình bày trong chương sau.

3.1.3.8. Tách một danh sách thành nhiều danh sách

Tùy thuộc vào từng yêu cầu cụ thể mà việc tách một danh sách thành nhiều danh sách có thể thực hiện theo những tiêu thức khác nhau:

+ Có thể phân phối luân phiên theo các đường chạy như đã trình bày trong các thuật toán sắp xếp theo phương pháp trộn ở chương sau;

+ Có thể phân phối luân phiên từng phần của danh sách cần tách cho các danh sách con. Ở dây chúng ta sẽ trình bày theo cách phân phối này;

+ Tách các phần tử trong danh sách thỏa mãn một điều kiện cho trước.

Giả sử chúng ta cần tách danh sách M có chiều dài Length thành các danh sách con SM1, SM2 có chiều dài tương ứng là SLen1, SLen2.

- Thuật toán:

// Kiểm tra tính hợp lệ của SLen1 và SLen2: SLen1 + SLen2 = Length

B1: IF (SLen1 Length)

B1.1: SLen1 = Length

B1.2: SLen2 = 0

B2: IF (SLen2 Length)

B2.1: SLen2 = Length

B2.2: SLen1 = 0

B3: IF (SLen1 + Slen2 Length)

SLen2 = Length – SLen1

B4: IF (SLen1 < 0)

SLen1 = 0

B5: IF (SLen2 < 0)

SLen2 = 0

// Chép SLen1 phần tử đầu trong M vào SM1

B6: i = 1, si = 1

B7: IF (i > SLen1)

Thực hiện B11

B8: SM1[si] = M[i]

B9: i++, si++

B10: Lặp lại B7

// Chép SLen2 phần tử cuối trong M vào SM2

B11: si = 1

B12: IF (i > Length)

Thực hiện Bkt

B13: SM2[si] = M[i]

B14: i++, si++

B15: Lặp lại B12

Bkt: Kết thúc

- Cài đặt thuật toán:

Hàm CD_Split có prototype:

void CD_Split(T M[], int Len, T SM1[], int &SLen1, T SM2[], int &SLen2);

Hàm thực hiện việc sao chép nội dung SLen1 phần tử đầu tiên trong danh sách M

vào trong danh con SM1 và sao chép SLen2 phần tử cuối cùng trong danh sách M

vào trong danh sách con SM2. Hàm hiệu chỉnh lại SLen1, SLen2 nếu cần thiết.

Nội dung của hàm như sau:

void CD_Split(T M[], int Len, T SM1[], int &SLen1, T SM2[], int &SLen2)

{ if (SLen1 >= Len)

{ SLen1 = Len;

SLen2 = 0;

}

if (SLen2 >= Len)

{ SLen2 = Len;

SLen1 = 0;

}

if (SLen1 < 0) SLen1 = 0;

if (SLen2 < 0) SLen2 = 0;

if (SLen1 + SLen2 != Len)

SLen2 = Len – SLen1;

for (int i = 0; i < SLen1; i++)

SM1[i] = M[i];

for (int j = 0; i < Len; i++, j++)

SM2[j] = M[i];

return;

}

3.1.3.9. Nhập nhiều danh sách thành một danh sách

Tùy thuộc vào từng yêu cầu cụ thể mà việc nhập nhiều danh sách thành một danh sách có thể thực hiện theo các phương pháp khác nhau, có thể là:

+ Ghép nối đuôi các danh sách lại với nhau;

+ Trộn xen lẫn các phần tử trong danh sách con vào danh sách lớn theo một trật tự nhất định như chúng ta đã trình bày trong các thuật toán trộn ở chương sau.

Ở đây chúng ta trình bày cách ghép các danh sách thành một danh sách.

Giả sử chúng ta cần ghép các danh sách SM1, SM2 có chiều dài SLen1, SLen2 vào thành một danh sách M có chiều dài Length = SLen1 + SLen2 theo thứ tự từ SM1 rồi đến SM2.

- Thuật toán:

// Kiểm tra khả năng chứa của M: SLen1 + SLen2 _ MaxLen

B1: IF (SLen1 + SLen2 > MaxLen)

Thực hiện Bkt

// Chép SLen1 phần tử đầu trong SM1 vào đầu M

B2: i = 1

B3: IF (i > SLen1)

Thực hiện B7

B4: M[i] = SM1[i]

B5: i++

B6: Lặp lại B3

// Chép SLen2 phần tử đầu trong SM2 vào sau M

B7: si = 1

B8: IF (si > SLen2)

Thực hiện Bkt

B9: M[i] = M2[si]

B10: i++, si++

B11: Lặp lại B8

Bkt: Kết thúc

- Cài đặt thuật toán:

Hàm CD_Concat có prototype:

int CD_Concat (T SM1[], int SLen1, T SM2[], int SLen2, T M[], int &Len);

Hàm thực hiện việc sao ghép nội dung hai danh sách SM1, SM2 có chiều dài

tương ứng SLen1, SLen2 về danh sách M có chiều dài Len = SLen1 + SLen2 theo thứ tự SM1 đến SM2. Hàm trả về chiều dài của danh sách M sau khi ghép nếu việc ghép thành công, trong trường hợp ngược lại hàm trả về giá trị -1.

Nội dung của hàm như sau:

int CD_Concat (T SM1[], int SLen1, T SM2[], int SLen2, T M[], int &Len)

{ if (SLen1 + SLen2 > MaxLen)

return (-1);

for (int i = 0; i < SLen1; i++)

M[i] = SM1[i];

for (int j = 0; j < SLen2; i++, j++)

M[i] = SM2[j];

Len = SLen1 + SLen2;

return (Len);

}

3.1.3.10. Sao chép một danh sách

Giả sử chúng ta cần sao chép nội dung dach sách M có chiều dài Length vào thành danh sách CM có cùng chiều dài.

- Thuật toán:

B1: i = 1

B2: IF (i > Length)

Thực hiện Bkt

B3: CM[i] = M[i]

B4: i++

B5: Lặp lại B2

Bkt: Kết thúc

- Cài đặt thuật toán:

Hàm CD_Copy có prototype:

int CD_Copy (T M[], int Len, T CM[]);

Hàm thực hiện việc sao chép nội dung danh sách M có chiều dài Len về danh

sách CM có cùng chiều dài. Hàm trả về chiều dài của danh sách CM sau khi sao chép.

Nội dung của hàm như sau:

int CD_Copy (T M[], int Len, T CM[])

{ for (int i = 0; i < Len; i++)

CM[i] = M[i];

return (Len);

}

3.1.3.11. Hủy danh sách

Trong thao tác này, nếu danh sách được cấp phát động thì chúng ta tiến hành hủy bỏ (xóa bỏ) toàn bộ các phần tử trong danh sách bằng toán tử hủy bỏ (trong C/C++ là free/delete). Nếu danh sách được cấp phát tĩnh thì việc hủy bỏ chỉ là tạm thời cho chiều dài của danh sách về 0 còn việc thu hồi bộ nhớ sẽ do ngôn ngữ tự thực hiện.

3.1.4. Ưu nhược điểm và ứng dụng

3.1.4.1. Ưu nhược điểm

Do các phần tử được lưu trữ liên tiếp nhau trong bộ nhớ, do vậy danh sách đặc có các ưu nhược điểm sau đây:

- Mật độ sử dụng bộ nhớ của danh sách đặc là tối ưu tuyệt đối (100%);

- Việc truy xuất và tìm kiếm các phần tử của danh sách đặc là dễ dàng vì các phần tử đứng liền nhau nên chúng ta chỉ cần sử dụng chỉ số để định vị vị trí các phần tử trong danh sách (định vị địa chỉ các phần tử);

- Việc thêm, bớt các phần tử trong danh sách đặc có nhiều khó khăn do chúng ta phải di dời các phần tử khác đi qua chỗ khác.

3.1.4.2. Ứng dụng của danh sách đặc:

Danh sách đặc được ứng dụng nhiều trong các cấu trúc dữ liệu mảng: mảng 1 chiều, mảng nhiều chiều; Mảng cấp phát tĩnh, mảng cấp phát động; … mà chúng ta đã nghiên cứu và thao tác khá nhiều trong quá trình lập trình trên nhiều ngôn ngữ lập trình khác nhau.

3.2. Danh sách liên kết

3.2.1. Định nghĩa

Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng.

Sự nối kết giữa các phần tử trong danh sách liên kết đó là sự quản lý, ràng buộc lẫn nhau về nội dung của phần tử này và địa chỉ định vị phần tử kia. Tùy thuộc vào mức độ và cách thức nối kết mà danh sách liên kết có thể chia ra nhiều loại khác nhau:

- Danh sách liên kết đơn;

- Danh sách liên kết đôi/kép;

- Danh sách đa liên kết;

- Danh sách liên kết vòng (vòng đơn, vòng đôi).

Mỗi loại danh sách sẽ có cách biểu diễn các phần tử (cấu trúc dữ liệu) riêng và các thao tác trên đó. Trong tài liệu này chúng ta chỉ trình bày 02 loại danh sách liên kết cơ bản là danh sách liên kết đơn và danh sách liên kết đôi.

3.2.2. Danh sách liên kết đơn (Singly Linked List)

3.2.2.1. Cấu trúc dữ liệu

Nội dung của mỗi phần tử trong danh sách liên kết (còn gọi là một nút) gồm hai vùng: Vùng dữ liệu và Vùng liên kết và có cấu trúc dữ liệu như sau:

typedef struct SLL_Node

{ T Key;

InfoType Info;

SLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp

} SLL_OneNode;

Tương tự như trong các chương trước, ở đây để đơn giản chúng ta cũng giả thiết rằng vùng dữ liệu của mỗi phần tử trong danh sách liên kết đơn chỉ bao gồm một thành phần khóa nhận diện (Key) cho phần tử đó. Khi đó, cấu trúc dữ liệu trên có thể viết lại đơn giản như sau:

typedef struct SLL_Node

{ T Key;

SLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp

} SLL_OneNode;

typedef SLL_OneNode * SLL_Type;

3.2.2.2. Các thao tác trên danh sách liên kết đơn

a. Khởi tạo danh sách (Initialize)

Trong thao tác này chỉ đơn giản là chúng ta cho giá trị con trỏ quản lý địa chỉ phần tử đầu danh sách về con trỏ NULL. Hàm khởi tạo danh sách liên kết đơn như sau:

void SLL_Initialize(SLL_Type &First)

{ First = NULL;

return;

}

b. Tạo mới một phần tử / nút:

Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData.

- Thuật toán:

B1: First = new SLL_OneNode

B2: IF (First = NULL)

Thực hiện Bkt

B3: First->NextNode = NULL

B4: First->Key = NewData

Bkt: Kết thúc

c. Thêm một phần tử vào trong danh sách:

Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách. Việc thêm có thể diễn ra ở đầu, cuối hay ở giữa danh sách liên kết.

Do vậy, ở đây chúng ta trình bày 3 thao tác thêm riêng biệt nhau:

- Thuật toán thêm phần tử vào đầu danh sách liên kết đơn:

B1: NewNode = SLL_Create_Node (NewData)

B2: IF (NewNode = NULL)

Thực hiện Bkt

B3: NewNode->NextNode = SLList // Nối SLList vào sau NewNode

B4: SLList = NewNode // Chuyển vai trò đứng đầu của NewNode cho SLList

Bkt: Kết thúc

d. Duyệt qua các nút trong danh sách:

Đây là một thao tác thường xuyên xảy ra trên danh sách liên kết đơn nói chung và các danh sách khác nói riêng để thực hiện thao tác xử lý các nút hoặc xử lý dữ liệu tại các nút. Có nhiều thao tác xử lý tùy từng trường hợp và yêu cầu song ở đây đơn giản chúng ta chỉ duyệt để xem nội dung thành phần dữ liệu trong danh sách.

- Thuật toán:

B1: CurNode = SLList

B2: IF (CurNode = NULL)

Thực hiện Bkt

B3: OutputData(CurNode->Key) // Xuất giá trị thành phần dữ liệu trong 1 nút

B4: CurNode = CurNode->NextNode

B5: Lặp lại B2

Bkt: Kết thúc

e. Tìm kiếm một phần tử trong danh sách:

Giả sử chúng ta cần tìm kiếm xem trong danh sách liên kết đơn có tồn tại nút có thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật toán tìm tuyến tính để tìm kiếm.

- Thuật toán:

B1: CurNode = SLList

B2: IF (CurNode = NULL OR CurNode->Key = SearchData)

Thực hiện Bkt

B3: CurNode = CurNode->NextNode

B4: Lặp lại B2

Bkt: Kết thúc

f. Loại bỏ bớt một phần tử ra khỏi danh sách:

Giả sử chúng ta cần loại bỏ phần tử có giá trị thành phần dữ liệu là DelData trong danh sách liên kết đơn. Để thực hiện điều này trước tiên chúng ta phải thực hiện thao tác tìm kiếm địa chỉ của nút có thành phần dữ liệu là DelData, sau đó mới thực hiện thao tác loại bỏ nếu tìm thấy. Tuy nhiên trong quá trình tìm kiếm, nếu tìm thấy chúng ta phải ghi nhận địa chỉ của nút đứng ngay trước nút tìm thấy là PreDelNode.

- Thuật toán:

// Tìm kiếm nút có Key là DelData trong danh sách

B1: DelNode = SLList

B2: PreDelNode = NULL

B3: IF (DelNode = NULL)

Thực hiện Bkt

B4: IF (DelNode->Key=DelData)

Thực hiện B8

B5: PreDelNode = DelNode

B6: DelNode = DelNode->NextNode

B7: Lặp lại B3

// Loại bỏ nút tại địa chỉ DelNode ra khỏi danh sách

B8: IF (PreDelNode = NULL) // Loại bỏ nút đầu tiên trong danh sách

B8.1: SLList = SLList->NextNode

B8.2: Thực hiện B10

// Liên kết các nốt sau DelNode về nút PreDelNode

B9: PreDelNode->NextNode = DelNode->NextNode

// Cắt mối liên kết giữa DelNode với các nút còn lại trong danh sách

// và hủy DelNode

B10: DelNode->NextNode = NULL

B11: delete DelNode

Bkt: Kết thúc

g. Hủy danh sách:

Thao tác này thực chất là thực hiện nhiều lần thao tác hủy một nút.

- Thuật toán:

B1: IF (SLList = NULL)

Thực hiện Bkt

B2: TempNode = SLList

B3: SLList = SLList->NextNode

B4: TempNode->NextNode = NULL

B5: delete TempNode

B6: Lặp lại B1

Bkt: Kết thúc

h. Tạo mới danh sách/ Nhập danh sách:

Việc tạo mới một danh sách liên kết đơn thực chất là chúng ta liên tục thực hiện thao tác thêm một phần tử vào danh sách mà ban đầu danh sách này là một danh sách rỗng. Có thể sử dụng một trong ba hàm thêm phần tử để thêm phần tử, ở đây chúng ta sử dụng hàm SLL_Add_First.

Giả sử chúng ta cần tạo danh sách liên kết đơn có N phần tử.

- Thuật toán:

B1: SLL_Initialize(SLList)

B2: i = 1

B3: IF (i > N)

Thực hiện Bkt

B4: NewData = InputNewData() // Nhập giá trị cho biến NewData

B5: SLL_Add_First(SLList, NewData)

B6: i++

B7: Lặp lại B3

Bkt: Kết thúc

i. Tách một danh sách thành nhiều danh sách:

Tương tự như danh sách đặc, việc tách một danh sách liên kết đơn thành nhiều danh sách liên kết đơn khác nhau cũng có nhiều tiêu thức khác nhau mà chúng ta sẽ thực hiện theo các cách khác nhau. Ngoài ra việc tách cũng sẽ khác nhau trong trường hợp có hay không giữ lại danh sách ban đầu. Ở đây chúng ta thực hiện việc tách các nút trong danh sách liên kết đơn SLList thành hai danh sách liên kết đơn con SLList và SLList1 luân phiên theo các đường chạy tự nhiên và không giữ lại danh sách liên kết ban đầu. Các trường hợp khác sinh viên tự vận dụng để thao tác.

- Thuật toán:

B1: CurNode = SLList

B2: SLList1 = SLList

B3: LastNode1 = NULL, LastNode2 = NULL

// Cắt các nút từ sau đường chạy tự nhiên thứ nhất về SLList1

B4: IF (CurNode = NULL OR CurNode->NextNode = NULL)

Thực hiện Bkt

B5: IF (CurNode->Key > CurNode->NextNode->Key)

B5.1: LastNode1 = CurNode

B5.2: SLList1 = SLList1->NextNode

B5.3: CurNode = CurNode->NextNode

B5.4: LastNode1->NextNode = NULL

B5.5: Thực hiện B8

B6: CurNode = CurNode->NextNode, SLList1 = SLList1->NextNode

B7: Lặp lại B4

// Cắt các nút từ sau đường chạy tự nhiên thứ hai về SLList

B8: IF (CurNode = NULL OR CurNode->NextNode = NULL)

Thực hiện Bkt

B9: IF (CurNode->Key > CurNode->NextNode->Key)

B9.1: LastNode2 = CurNode

B9.2: CurNode = CurNode->NextNode

B9.3: LastNode2->NextNode = NULL

B9.4: Thực hiện B12

B10: CurNode = CurNode->NextNode

B11: Lặp lại B8

// Phân phối (giữ lại) đường chạy kế tiếp trong SLList

B12: LastNode1->NextNode = CurNode

B13: IF (CurNode = NULL OR CurNode->NextNode = NULL)

Thực hiện Bkt

B14: IF (CurNode->Key > CurNode->NextNode->Key)

B14.1: LastNode1 = CurNode

B14.2: CurNode = CurNode->NextNode

B14.3: LastNode1->NextNode = NULL

B14.4: Thực hiện B17

B15: CurNode = CurNode->NextNode

B16: Lặp lại B13

// Phân phối (giữ lại) đường chạy kế tiếp trong SLList1

B17: LastNode2->NextNode = CurNode

B18: IF (CurNode = NULL OR CurNode->NextNode = NULL)

Thực hiện Bkt

B19: IF (CurNode->Key > CurNode->NextNode->Key)

B19.1: LastNode2 = CurNode

B19.2: CurNode = CurNode->NextNode

B19.3: LastNode2->NextNode = NULL

B19.4: Lặp lại B12

B20: CurNode = CurNode->NextNode

B21: Lặp lại B18

Bkt: Kết thúc

j. Nhập nhiều danh sách thành một danh sách:

Tương tự, việc nhập nhiều danh sách thành một danh sách chúng ta thực hiện theo hai trường hợp khác nhau:

+ Ghép nối đuôi các danh sách lại với nhau;

+ Trộn xen lẫn các phần tử trong danh sách con vào thành một danh sách lớn theo một trật tự nhất định.

Ngoài ra việc nhập có thể giữ lại các danh sách con ban đầu hoặc không giữ lại các danh sách con ban đầu. Ở đây chúng ta trình bày theo cách không giữ lại các danh sách con ban đầu và trình bày theo hai trường hợp:

+ Ghép nối đuôi hai danh sách lại với nhau;

+ Trộn hai danh sách lại với nhau theo các đường chạy tự nhiên thành một danh sách có chiều dài lớn hơn.

k. Sắp xếp thứ tự các phần tử trong danh sách:

Thao tác này chúng ta có thể vận dụng các thuật toán sắp xếp đã trình bày trong chương sau để sắp xếp dữ liệu trong danh sách liên kết đơn. Ở đây chúng ta chỉ trình bày sự vận dụng thuật toán trộn tự nhiên để sắp xếp.

Cũng cần lưu ý rằng đối với thao tác hoán vị hai phần tử thì chúng ta có thể hoán vị hoàn toàn hai nút hoặc chỉ hoán vị phần dữ liệu. Tuy nhiên việc hoán vị hoàn toàn hai nút sẽ phức tạp hơn.

- Thuật toán sắp xếp trộn tự nhiên:

B1: IF (SLL_Split(SLList, TempList) = NULL)

Thực hiện Bkt

B2: SLL_Merge(SLList, TempList, SLList)

B3: Lặp lại B1

Bkt: Kết thúc

h. Sao chép một danh sách:

Thực chất thao tác này là chúng ta tạo mới danh sách NewList bằng cách duyệt qua các nút của SLList để lấy thành phần dữ liệu rồi tạo thành một nút mới và bổ sung nút mới này vào cuối danh sách NewList.

- Thuật toán:

B1: NewList = NULL

B2: CurNode = SLList

B3: IF (CurNode = NULL)

Thực hiện Bkt

B4: SLL_Add_Last(NewList, CurNode->Key)

B5: CurNode = CurNode->NextNode

B6: Lặp lại B3

Bkt: Kết thúc

3.2.3. Danh sách liên kết kép (Doubly Linked List)

3.2.3.1. Cấu trúc dữ liệu:

Nếu như vùng liên kết của danh sách liên kết đơn có 01 mối liên kết với 01 phần tử khác trong danh sách thì vùng liên kết trong danh sách liên đôi có 02 mối liên kết với 02 phần tử khác trong danh sách, cấu trúc dữ liệu của mỗi nút trong danh sách liên kết đôi như sau:

typedef struct DLL_Node

{ T Key;

InfoType Info;

DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nó

DLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trước nó

} DLL_OneNode;

Ở đây chúng ta cũng giả thiết rằng vùng dữ liệu của mỗi phần tử trong danh sách liên kết đôi chỉ bao gồm một thành phần khóa nhận diện (Key) cho phần tử đó. Do vậy, cấu trúc dữ liệu trên có thể viết lại đơn giản như sau:

typedef struct DLL_Node

{ T Key;

DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nó

DLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trước nó

} DLL_OneNode;

3.2.2.3. Các thao tác trên danh sách liên kết kép

a. Khởi tạo danh sách (Initialize)

Trong thao tác này chỉ đơn giản là chúng ta cho giá trị các con trỏ quản lý địa chỉ hai nút đầu và cuối danh sách liên kết đôi về con trỏ NULL. Hàm khởi tạo danh sách liên kết đôi như sau:

DLLP_Type DLL_Initialize(DLLP_Type &DList)

{ DList.DLL_First = NULL;

DList.DLL_Last = NULL;

return (DList);

}

b. Tạo mới một phần tử / nút:

Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData.

- Thuật toán:

B1: DNode = new DLL_OneNode

B2: IF (DNode = NULL)

Thực hiện Bkt

B3: DNode->NextNode = NULL

B4: DNode->PreNode = NULL

B5: DNode->Key = NewData

Bkt: Kết thúc

c. Thêm một phần tử vào trong danh sách:

Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách. Việc thêm có thể diễn ra ở đầu, cuối hay ở giữa danh sách liên kết.

Do vậy, ở đây chúng ta trình bày 3 thao tác thêm riêng biệt nhau:

- Thuật toán thêm phần tử vào đầu danh sách liên kết đôi:

B1: NewNode = DLL_Create_Node (NewData)

B2: IF (NewNode = NULL)

Thực hiện Bkt

B3: IF (DLL_List.DLL_First = NULL) // Danh sách rỗng

B3.1: DLL_List.DLL_First = NewNode

B3.2: DLL_List.DLL_Last = NewNode

B3.3: Thực hiện Bkt

B4: NewNode->NextNode = DLL_List.DLL_First // Nối DLL_First vào

B5: DLL_List.DLL_First->PreNode = NewNode // sau NewNode

// Chuyển vai trò đứng đầu của NewNode cho DLL_First

B6: DLL_List.DLL_First = NewNode

Bkt: Kết thúc

d. Duyệt qua các nút trong danh sách:

Thao tác này nhằm nhiều mục đích, ở đây đơn giản chúng ta chỉ duyệt để xem nội dung thành phần dữ liệu trong danh sách. Thuật toán này hoàn toàn tương tự như trong danh sách liên kết đơn.

- Thuật toán:

B1: CurNode = DLL_List.First

B2: IF (CurNode = NULL)

Thực hiện Bkt

B3: OutputData(CurNode->Key) // Xuất giá trị thành phần dữ liệu trong 1 nút

B4: CurNode = CurNode->NextNode

B5: Lặp lại B2

Bkt: Kết thúc

e. Tìm kiếm một phần tử trong danh sách:

Giả sử chúng ta cần tìm kiếm xem trong danh sách liên kết đôi có tồn tại nút có thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật toán tìm tuyến tính để tìm kiếm.

- Thuật toán:

B1: CurNode = DLL_List.DLL_First

B2: IF (CurNode = NULL OR CurNode->Key = SearchData)

Thực hiện Bkt

B3: CurNode = CurNode->NextNode

B4: Lặp lại B2

Bkt: Kết thúc

f. Loại bỏ bớt một phần tử ra khỏi danh sách:

Giả sử chúng ta cần loại bỏ phần tử có giá trị thành phần dữ liệu là DelData trong danh sách liên kết đôi, Để thực hiện điều này trước tiên chúng ta phải thực hiện thao tác tìm kiếm địa chỉ của nút có thành phần dữ liệu là DelData, sau đó mới thực hiện thao tác loại bỏ nếu tìm thấy.

- Thuật toán:

// Tìm kiếm nút có Key là DelData trong danh sách

B1: DelNode = DLL_Searching(DLL_List, DelData)

B2: IF (DelNode = NULL)

Thực hiện Bkt

// Loại bỏ nút tại địa chỉ DelNode ra khỏi danh sách

B3: IF (DelNode->PreNode = NULL AND DelNode->NextNode = NULL)

B3.1: DLL_List.DLL_First = DLL_List.DLL_Last = NULL

B3.2: Thực hiện B8

B4: IF (DelNode->PreNode = NULL) // Loại bỏ nút đầu tiên trong danh sách

B4.1: DLL_List.DLL_First = DLL_List.DLL_First->NextNode

B4.2: DLL_List.DLL_First->PreNode = NULL

B4.3: Thực hiện B8

B5: IF (DelNode->NextNode = NULL) // Loại bỏ nút cuối cùng trong danh sách

B5.1: DLL_List.DLL_Last = DLL_List.DLL_Last->PreNode

B5.2: DLL_List.DLL_Last->NextNode = NULL

B5.3: Thực hiện B8

// Liên kết các nốt trước và sau DelNode với nhau

B6: DelNode->PreNode->NextNode = DelNode->NextNode

B7: DelNode->NextNode->PreNode = DelNode->PreNode

//Bỏ mối liên kết giữa DelNode với hai nút trước và sau nó, và hủy DelNode

B8: DelNode->NextNode = DelNode->PreNode = NULL

B9: delete DelNode

Bkt: Kết thúc

g. Hủy toàn bộ danh sách:

Ở đây, chúng ta thực hiện nhiều lần thao tác hủy một nút.

- Thuật toán:

B1: IF (DLL_List.DLL_First = NULL)

Thực hiện Bkt

B2: TempNode = DLL_List.DLL_First

B3: DLL_List.DLL_First = DLL_List.DLL_First->NextNode

B4: IF (DLL_List.DLL_First = NULL)

B4.1: DLL_List.DLL_Last = NULL

B4.2: Thực hiện B7

B5: DLL_List.DLL_First->PreNode = NULL

B6: TempNode->NextNode = NULL

B7: delete TempNode

B8: Lặp lại B1

Bkt: Kết thúc

h. Tạo mới danh sách/ Nhập danh sách:

Cũng tương tự như trong danh sách liên kết đơn trong thao tác này, chúng ta liên tục thực hiện thao tác thêm một phần tử vào danh sách mà ban đầu danh sách này là một danh sách rỗng (Gồm hai con trỏ NULL). Chúng ta cũng có thể sử dụng một trong ba hàm thêm phần tử để thêm phần tử, ở đây sử dụng hàm SLL_Add_Last.

Giả sử chúng ta cần tạo danh sách liên kết đôi có N phần tử.

- Thuật toán:

B1: DLL_Initialize(DLL_List)

B2: i = 1

B3: IF (i > N)

Thực hiện Bkt

B4: NewData = InputNewData() // Nhập giá trị cho biến NewData

B5: DLL_Add_Last(DLL_List, NewData)

B6: i++

B7: Lặp lại B3

Bkt: Kết thúc

i. Tách một danh sách thành nhiều danh sách:

Giả sử chúng ta cần thực hiện việc tách các nút trong danh sách liên kết đôi DLL_List thành hai danh sách liên kết đôi con DLL_List1 và DLL_List2 luân phiên theo các đường chạy tự nhiên và cần giữ lại danh sách liên kết ban đầu.

- Thuật toán:

B1: DLL_Initialize(DLL_List1)

B2: DLL_Initialize(DLL_List2)

B3: CurNode = DLL_List.DLL_First

// Cắt các nút từ 1 đường chạy tự nhiên về DLL_List1

B4: IF (CurNode = NULL)

Thực hiện Bkt

B5: DLL_Add_Last(DLL_List1, CurNode->Key)

B6: CurNode = CurNode->NextNode

B7: IF (CurNode = NULL)

Thực hiện Bkt

B8: IF (CurNode->PreNode->Key > CurNode->Key)

Thực hiện B10

B9: Lặp lại B4

// Cắt các nút từ 1 đường chạy tự nhiên về DLL_List2

B10: IF (CurNode = NULL)

Thực hiện Bkt

B11: DLL_Add_Last(DLL_List2, CurNode->Key)

B12: CurNode = CurNode->NextNode

B13: IF (CurNode = NULL)

Thực hiện Bkt

B14: IF (CurNode->PreNode->Key > CurNode->Key)

Thực hiện B4

B15: Lặp lại B10

Bkt: Kết thúc

j. Nhập nhiều danh sách thành một danh sách:

Chúng ta thực hiện thao tác này trong hai trường hợp:

+ Ghép nối đuôi các danh sách lại với nhau;

+ Trộn xen lẫn các phần tử trong các danh sách vào thành một danh sách theo một trật tự nhất định và sau khi nhập xong vẫn giữ lại các danh sách ban đầu.

Giả sử chúng ta cần nhập hai danh sách DLL_List1 và DLL_List2 lại với nhau thành một danh sách DLL_List.

- Thuật toán ghép nối hai danh sách thành một danh sách mới:

B1: DLL_Initialize (DLL_List)

// Đưa DLL_List1 vào đầu DLL_List

B2: CurNode = DLL_List1.DLL_First

B3: IF (CurNode = NULL)

Thực hiện B7

B4: IF (DLL_Add_Last(DLL_List, CurNode->Key) = NULL)

B4.1: DLL_Delete (DLL_List)

B4.2: Thực hiện Bkt

B5: CurNode = CurNode->NextNode

B6: Lặp lại B3

// Đưa DLL_List2 vào sau DLL_List

B7: CurNode = DLL_List2.DLL_First

B8: IF (CurNode = NULL)

Thực hiện Bkt

B9: IF (DLL_Add_Last(DLL_List, CurNode->Key) = NULL)

B4.1: DLL_Delete (DLL_List)

B4.2: Thực hiện Bkt

B10: CurNode = CurNode->NextNode

B11: Lặp lại B8

Bkt: Kết thúc

k. Sắp xếp thứ tự thành phần dữ liệu các nút trong danh sách:

Thao tác này rất thuận tiện trong việc áp dụng thuật toán sắp xếp trộn để sắp xếp, sinh viên có thể tự thực hiện. Ở đây, chúng ta vận dụng thuật toán sắp xếp nổi bọt để sắp xếp dữ liệu.

- Thuật toán sắp xếp vận dụng thuật toán nổi bọt:

B1: Inode = DLL_List.DLL_First

B2: IF (Inode = NULL)

Thực hiện Bkt

B3: IF (Inode = DLL_List.DLL_Last)

Thực hiện Bkt

B4: Jnode = DLL_List.DLL_Last

B5: IF (Jnode = Inode)

Thực hiện B7

B6: ELSE

B6.1: If (Jnode->Key < Jnode->PreNode->Key)

Swap (Jnode->Key, Jnode->PreNode->Key)

B6.2: Jnode = Jnode->PreNode

B6.3: Lặp lại B5

B7: Inode = Inode->NextNode

B8: Lặp lại B3

Bkt: Kết thúc

l. Sao chép một danh sách thành một danh sách mới:

Thao tác này hoàn toàn tương tự như trong danh sách liên kết đơn.

- Thuật toán:

B1: DLL_Initialize(NewList)

B2: CurNode = DLL_List.DLL_First

B3: IF (CurNode = NULL)

Thực hiện Bkt

B4: DLL_Add_Last(NewList, CurNode->Key)

B5: CurNode = CurNode->NextNode

B6: Lặp lại B3

Bkt: Kết thúc

3.2.4. Ưu nhược điểm của danh sách liên kết

Do các phần tử (nút) được lưu trữ không liên tiếp nhau trong bộ nhớ, do vậy danh sách liên kết có các ưu nhược điểm sau đây:

- Mật độ sử dụng bộ nhớ của danh sách liên kết không tối ưu tuyệt đối (<100%);

- Việc truy xuất và tìm kiếm các phần tử của danh sách liên kết mất nhiều thời gian bởi luôn luôn phải duyệt tuần tự qua các phần tử trong danh sách;

- Tận dụng được những không gian bộ nhớ nhỏ để lưu trữ từng nút, tuy nhiên bộ nhớ lưu trữ thông tin mỗi nút lại tốn nhiều hơn do còn phải lưu thêm thông tin về vùng liên kết. Như vậy nếu vùng dữ liệu của mỗi nút là lớn hơn thì tỷ lệ mức tiêu tốn bộ nhớ này là không đáng kể, ngược lại thì nó lại gây lãng phí bộ nhớ.

- Việc thêm, bớt các phần tử trong danh sách, tách nhập các danh sách khá dễ dàng do chúng ta chỉ cần thay đổi mối liên kết giữa các phần tử với nhau.

3.3. Ngăn xếp(Stack)

3.3.1. Khái niệm

Ngăn xếp là một danh sách mà trong đó thao tác thêm một phần tử vào trong danh và thao tác lấy ra một phần tử từ trong danh sách được thực hiện ở cùng một đầu.

Ngăn xếp (Stack)

3.3.2. Cấu trúc dữ liệu

Các phần tử được đưa vào trong ngăn xếp sau cùng sẽ được lấy ra trước tiên, phần tử đưa vào trong hàng đợi trước tiên sẽ được lấy ra sau cùng. Do đó mà ngăn xếp còn được gọi là danh sách vào sau ra trước (LIFO List) và cấu trúc dữ liệu này còn được gọi là cấu trúc LIFO (Last In – First Out).

Tương tự như hàng đợi, có nhiều cách để biểu diễn và tổ chức các ngăn xếp:

- Sử dụng danh sách đặc,

- Sử dụng danh sách liên kết,

Do ở đây cả hai thao tác thêm vào và lấy ra đều được thực hiện ở một đầu nên chúng ta chỉ cần quản lý vị trí đầu của danh sách dùng làm mặt cho ngăn xếp thông qua biến chỉ số bề mặt SP (Stack Pointer). Chỉ số này có thể là cùng chiều (đầu) hoặc ngược chiều (cuối) với thứ tự các phần tử trong mảng và trong danh sách liên kết. Điều này có nghĩa là bề mặt ngăn xếp có thể là đầu mảng, đầu danh sách liên kết mà cũng có thể là cuối mảng, cuối danh sách liên kết. Để thuận tiện, ở đây chúng ta giả sử bề mặt của ngăn xếp là đầu mảng, đầu danh sách liên kết. Trường hợp ngược lại, sinh viên tự áp dụng tương tự.

Ở đây chúng ta cũng sẽ biểu diễn và tổ chức hàng đợi bằng danh sách đặc và bằng danh sách liên kết đơn được quản lý bởi con trỏ đầu danh sách. Do vậy cấu trúc dữ liệu của ngăn xếp và các thao tác trên đó sẽ được trình bày thành hai trường hợp khác nhau.

3.3.2.1. Biểu diễn và tổ chức bằng danh sách đặc:

typedef struct S_C

{

int Size; // Kích thước ngăn xếp

int SP;

T * List; // Nội dung ngăn xếp

} C_STACK;

C_STACK CS_List;

3.3.2.2. Biểu diễn và tổ chức bằng danh sách liên kết đơn;

typedef struct S_Element

{

T Key;

S_Element * Next; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp

} S_OneElement;

typedef S_OneElement * S_STACK;

S_STACK S_SP;

3.3.3. Các thao tác trên ngăn xếp

3.3.3.1. Các thao tác trên ngăn xếp tổ chức bằng danh sách đặc

Do hạn chế của danh sách đặc cho nên mỗi ngăn xếp sẽ có một kích thước cố định. Do vậy, trong quá trình thao tác trên ngăn xếp có thể xảy ra hiện tượng ngăn xếp bị đầy. Ngăn xếp bị đầy khi số phần tử của ngăn xếp bằng kích thước cho phép của ngăn xếp (SP = 1). Lúc này chúng ta không thể thêm bất kỳ một phần tử nào vào trong ngăn xếp.

a. Khởi tạo ngăn xếp (Initialize)

Trong thao tác này chúng ta thực hiện việc xác định kích thước ngăn xếp, cấp phát bộ nhớ để lưu trữ phần dữ liệu cho ngăn xếp và cho giá trị thành phần SP về giá trị Size+1.

- Thuật toán:

B1: CS_List.Size = MaxSize

B2: CS_List.List = new T[MaxSize]

B3: IF (CS_List.List = NULL)

Thực hiện Bkt

B4: CS_List.SP = CS_List.Size + 1

Bkt: Kết thúc

b. Thêm (Đẩy) một phần tử vào ngăn xếp (Push)

Trong ngăn xếp chúng ta luôn luôn đưa phần tử mới vào trên cùng của ngăn xếp, ngay trước vị trí SP (nếu ngăn xếp chưa bị đầy). Giả sử chúng ta cần đưa phần tử có giá trị NewData vào trong ngăn xếp:

- Thuật toán:

B1: IF (CS_List.SP = 1) // Nếu ngăn xếp bị đầy

Thực hiện Bkt

B2: CS_List.SP--

B3: CS_List.List[CS_List.SP] = NewData

Bkt: Kết thúc

c. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop)

Ở đây chúng ta cũng luôn luôn lấy nội dung phần tử ở ngay bề mặt ngăn xếp, tại vị trí SP (nếu ngăn xếp không rỗng). Giả sử ta cần lấy dữ liệu ra biến Data:

- Thuật toán:

// Nếu ngăn xếp bị rỗng

B1: IF (CS_List.SP = CS_List.Size+1)

Thực hiện Bkt

B2: Data = CS_List.List[CS_List.SP]

B3: CS_List.SP++

Bkt: Kết thúc

d. Hủy ngăn xếp

Trong thao tác này chúng ta thực hiện việc hủy bộ nhớ đã cấp phát cho ngăn xếp.

Hàm CS_Delete có nội dung như sau:

void CS_Delete (C_STACK &SList)

{

delete SList.List;

return;

}

3.3.3.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách liên kết đơn

a. Khởi tạo ngăn xếp:

Hàm SS_Initialize có nội dung như sau:

S_STACK SS_Initialize (S_STACK &SList)

{

SList = NULL;

return (SList);

}

b. Thêm (Đẩy) một phần tử vào ngăn xếp (Push):

Ở đây chúng ta thêm một phần tử vào trước S_SP (Thêm vào đầu danh sách liên kết). Giả sử chúng ta cần đưa phần tử có giá trị dữ liệu là NewData vào trong ngăn xếp:

- Thuật toán:

B1: NewElement = SLL_Create_Node(NewData)

B2: IF (NewElement = NULL)

Thực hiện Bkt

B3: IF (S_SP = NULL) // Nếu ngăn xếp bị rỗng

B3.1: S_SP = NewElement

B3.2: Thực hiện Bkt

B4: NewElement->Next = S_SP

B5: S_SP = NewElement

Bkt: Kết thúc

c. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop):

Ở đây chúng ta lấy nội dung thành phần dữ liệu của phần tử ở địa chỉ S_SP ra biến Data và tiến hành hủy luôn phần tử này.

- Thuật toán:

// Nếu ngăn xếp bị rỗng

B1: IF (S_SP = NULL)

Thực hiện Bkt

B2: TempElement = S_SP

B3: S_SP = S_SP->Next

B4: TempElement->Next = NULL

B5: Data = TempElement->Key

B6: delete TempElement

Bkt: Kết thúc

d. Hủy ngăn xếp

Trong thao tác này chúng ta thực hiện việc hủy toàn bộ các phần tử trong ngăn xếp.

Hàm SS_Delete có nội dung như sau:

void SS_Delete (S_STACK &SList)

{

while (SList != NULL)

{ S_STACK TempElement = SList;

SList = SList->Next;

TempElement->Next = NULL;

delete TempElement;

}

return;

}

3.4. Hàng đợi(Queue)

3.4.1. Khái niệm

Hàng đợi là một danh sách mà trong đó thao tác thêm một phần tử vào trong danh sách được thực hiện ở một đầu này và thao tác lấy ra một phần tử từ trong danh sách lại được thực hiện ở đầu kia.

Hàng đợi

3.4.2. Cấu trúc dữ liệu

Như vậy, các phần tử được đưa vào trong hàng đợi trước sẽ được lấy ra trước, phần tử đưa vào trong hàng đợi sau sẽ được lấy ra sau. Do đó mà hàng đợi còn được gọi là danh sách vào trước ra trước (FIFO List) và cấu trúc dữ liệu này còn được gọi là cấu trúc FIFO (First In – First Out).

Có nhiều cách để biểu diễn và tổ chức các hàng đợi:

- Sử dụng danh sách đặc,

- Sử dụng danh sách liên kết,

Tuy nhiên, điều quan trọng và cần thiết là chúng ta phải quản lý vị trí hai đầu của hàng đợi thông qua hai biến: Biến trước (Front) và Biến sau (Rear). Hai biến này có thể cùng chiều hoặc ngược chiều với thứ tự các phần tử trong mảng và trong danh sách liên kết. Điều này có nghĩa là đầu hàng đợi có thể là đầu mảng, đầu danh sách liên kết mà cũng có thể là cuối mảng, cuối danh sách liên kết. Để thuận tiện, ở đây chúng ta giả sử đầu hàng đợi cũng là đầu mảng, đầu danh sách liên kết. Trường hợp ngược lại, sinh viên tự áp dụng tương tự.

Ở đây chúng ta sẽ biểu diễn và tổ chức hàng đợi bằng danh sách đặc và bằng danh sách liên kết đơn được quản lý bởi hai con trỏ đầu và cuối danh sách. Do vậy cấu trúc dữ liệu của hàng đợi cũng như các thao tác trên hàng đợi sẽ được trình bày thành hai trường hợp khác nhau.

3.4.2.1. Biểu diễn và tổ chức bằng danh sách đặc

typedef struct Q_C

{ int Len; // Chiều dài hàng đợi

int Front, Rear;

T * List; // Nội dung hàng đợi

} C_QUEUE;

C_QUEUE CQ_List;

3.4.2.2. Biểu diễn và tổ chức bằng danh sách liên kết đơn

typedef struct Q_Element

{ T Key;

Q_Element * Next; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp

} Q_OneElement;

typedef Q_OneElement * Q_Type;

typedef struct QP_Element

{ Q_Type Front;

Q_Type Rear;

} S_QUEUE;

S_QUEUE SQ_List;

3.4.3. Các thao tác trên hàng đợi

3.4.3.1. Các thao tác trên hàng đợi tổ chức bằng danh sách đặc

Do hạn chế của danh sách đặc cho nên mỗi hàng đợi đều có một chiều dài cố định.

Do vậy, trong quá trình thao tác trên hàng đợi có thể xảy ra hiện tượng hàng đợi bị đầy hoặc hàng đợi bị tràn.

- Khi hàng đợi bị đầy: số phần tử của hàng đợi bằng chiều dài cho phép của hàng đợi. Lúc này chúng ta không thể thêm bất kỳ một phần tử nào vào hàng đợi.

- Khi hàng đợi bị tràn: số phần tử của hàng đợi nhỏ hơn chiều dài cho phép của hàng đợi nhưng Rear = Len. Lúc này chúng ta phải khắc phục tình trạng tràn hàng đợi bằng cách dịch tất cả các phần tử của hàng đợi ra phía trước Front-1 vị trí hoặc xoay vòng để Rear chuyển lên vị trí đầu danh sách đặc. Trong phần này chúng ta sử dụng phương pháp xoay vòng. Như vậy theo phương pháp này, hàng đợi bị đầy trong các trường hợp sau:

+ Front = 1 và Rear = Len, khi: Front < Rear

+ Rear + 1 = Front, khi: Rear < Front

Ghi chú:

Nếu chúng ta khắc phục hàng đợi bị tràn bằng phương pháp dịch tất cả các phần tử của hàng đợi ra phía trước Front-1 vị trí thì hàng đợi bị đầy khi thỏa mãn điều kiện:

Front = 1 và Rear = Len (Ở đây ta luôn luôn có: Front _ Rear).

a. Khởi tạo hàng đợi (Initialize)

Trong thao tác này chúng ta thực hiện việc xác định kích thước hàng đợi, cấp phát bộ nhớ để lưu trữ phần dữ liệu cho hàng đợi, đồng thời cho giá trị các thành phần Front, Rear về giá trị 0 (trong C chúng ta khởi tạo về giá trị –1).

- Thuật toán:

B1: CQ_List.Len = Length

B2: CQ_List.List = new T[Length]

B3: IF (CQ_List.List = NULL)

Thực hiện Bkt

B4: CQ_List.Front = CQ_List.Rear = 0

Bkt: Kết thúc

b. Thêm (Đưa) một phần tử vào hàng đợi (Add)

Trong hàng đợi chúng ta luôn luôn đưa phần tử mới vào cuối hàng đợi, ngay sau vị trí Rear (nếu hàng đợi chưa bị đầy). Giả sử chúng ta cần đưa phần tử có giá trị NewData vào trong hàng đợi:

- Thuật toán:

// B1+B2: Nếu hàng đợi bị đầy

B1: IF (CQ_List.Front = 1 AND CQ_List.Rear = CQ_List.Len)

Thực hiện Bkt

B2: IF (CQ_List.Rear+1 = CQ_List.Front)

Thực hiện Bkt

B3: IF (CQ_List.Front = 0) // Nếu hàng đợi rỗng

CQ_List.Front = 1

B4: IF (CQ_List.Rear = CQ_List.Len) //Nếu hàng bị tràn

CQ_List.Rear = 1

B5: ELSE

CQ_List.Rear++

B6: CQ_List.List[CQ_List.Rear] = NewData

Bkt: Kết thúc

c. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get)

Trong hàng đợi chúng ta luôn luôn lấy nội dung phần tử ở ngay đầu hàng đợi, tại vị trí Front (nếu hàng đợi không rỗng). Giả sử ta cần lấy dữ liệu ra biến Data:

- Thuật toán:

// Nếu hàng đợi bị rỗng

B1: IF (CQ_List.Front = 0)

Thực hiện Bkt

B2: Data = CQ_List.List[CQ_List.Front]

B3: IF (CQ_List.Rear = CQ_List.Front) // Hàng đợi chỉ có 1 phần tử

B3.1: CQ_List.Rear = CQ_List.Front = 0

B3.2: Thực hiện Bkt

B4: IF (CQ_List.Front = CQ_List.Len)

CQ_List.Front = 1

B5: ELSE

CQ_List.Front++

Bkt: Kết thúc

d. Hủy hàng đợi

Trong thao tác này chúng ta thực hiện việc hủy bộ nhớ đã cấp phát cho hàng đợi.

Hàm CQ_Delete có nội dung như sau:

void CQ_Delete (C_QUEUE &QList)

{

delete QList.List;

return;

}

3.4.3.2. Các thao tác trên hàng đợi tổ chức bằng danh liên kết đơn:

Khác với hàng đợi biểu diễn bằng danh sách đặc, ở đây hàng đợi chỉ bị đầy khi hết bộ nhớ và không bao giờ bị tràn.

a. Khởi tạo hàng đợi (Initialize)

Tương tự như trong danh sách liên kết đơn, trong thao tác này chúng ta chỉ đơn giản thực hiện việc gán các con trỏ Front và Rear về con trỏ NULL. Hàm

SQ_Initialize có nội dung như sau:

S_QUEUE SQ_Initialize (S_QUEUE &QList)

{

QList.Front = QList.Rear = NULL;

return (QList);

}

b. Thêm (Đưa) một phần tử vào hàng đợi (Add)

Ở đây chúng ta thêm một phần tử vào sau Rear (Thêm vào cuối danh sách liên kết).

Giả sử chúng ta cần đưa phần tử có giá trị dữ liệu là NewData vào trong hàng đợi:

- Thuật toán:

B1: NewElement = SLL_Create_Node(NewData)

B2: IF (NewElement = NULL)

Thực hiện Bkt

B3: IF (SQ_List.Front = NULL) // Nếu hàng đợi bị rỗng

B3.1: SQ_List.Front = SQ_List.Rear = NewElement

B3.2: Thực hiện Bkt

B4: SQ_List.Rear->Next = NewElement

B5: SQ_List.Rear = NewElement

Bkt: Kết thúc

c. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get):

Ở đây chúng ta lấy nội dung thành phần dữ liệu của phần tử ở địa chỉ Front ra biến Data và tiến hành hủy luôn phần tử này.

- Thuật toán:

// Nếu hàng đợi bị rỗng

B1: IF (SQ_List.Front = NULL)

Thực hiện Bkt

B2: TempElement = SQ_List.Front

B3: SQ_List.Front = SQ_List.Front->Next

B4: TempElement->Next = NULL

B5: Data = TempElement->Key

B6: IF (SQ_List.Front = NULL) // Hàng đợi chỉ có 1 phần tử

SQ_List.Rear = NULL

B7: delete TempElement

Bkt: Kết thúc

d. Hủy hàng đợi

Trong thao tác này chúng ta thực hiện việc hủy toàn bộ các phần tử trong hàng đợi.

Hàm SQ_Delete có nội dung như sau

void SQ_Delete (S_QUEUE &QList)

{

QList.Rear = NULL;

while (QList.Front != NULL)

{ Q_Type TempElement = QList.Front;

QList.Front = QList.Front->Next;

TempElement->Next = NULL;

delete TempElement;

}

return;

}

3.5. Một số ứng dụng của danh sách

3.5.1. Một số ứng dụng của Stack

3.5.1.1. Dùng Stack để đổi 1 số nguyên dương từ hệ 10 sang hệ 2.

* Phân tích giải thuật:

- Dùng Stack S để lưu trữ phần dư của phép chia n cho 2

- While n <> 0: đẩy phần dư của phép chia n cho 2 vào stack S đỉnh k sau đó lấy phần nguyên của phép chia chia tiếp cho 2. Quá trình này cứ lặp đi lặp lại.

- k <> 0 thì lấy i từ stack S đỉnh k để đưa i ra.

* Giải thuật:

Procedure Doi n (n)

Begin

R := 0;

While n <> 0 do

Begin

Push (S, R, n Mod 2);

n = n div 2;

End;

Write (‘ Kết quả’);

While k <> 0 do

Begin

Pop (S, k, i);

Write (i);

End;

3.5.1.2. Dùng Stack để tính giá trị biểu thức dạng hậu tố .

* Biểu thức dạng hậu tố: Các thành phần tham gia vào biểu thức có thể bao gồm các toán hạng (TH) và dấu phép toán (). Khi tính toán phép toán ta cần quan tâm đến thứ tự thực hiện phép toán.

Chú ý: Khi tính giá trị của biểu thức ta luôn xác định phép toán thực hiện cuối cùng, căn cứ vào các quy ước về thứ tự thực hiện phép toán. Trong cách viết thông thường ta phải dùng các dấu ngoặc để thực hiện thứ tự phép toán nếu nó ngược với thứ tự quy ước.

Ví dụ: x + y * (z – t) – u/v

Biểu thức viết dạng như trên gọi là biểu thức dạng trung tố. Với cách sử dụng dấu ngoặc như vậy thì khi viết chương trình tính toán giá trị của biểu thức cần thêm dung lượng bộ nhớ để lưu dấu ngoặc, để giảm sự cồng kềnh này, 1 nhà toán học người Balan đã đưa ra phương pháp biểu diễn biểu thức theo ký pháp hậu tố (Poitfix Notation) hoặc tiền tố (Postfix Notation) mà gọi chung là ký pháp Balan (Polish Notation)

Ví dụ:

Biểu thức dạng trung tố	Biểu thức dạng hậu tố	Biểu thức dạng tiền tố
(A +B) * C	A B + C *	+ A B * C
A + B * C	A B C * +	+ A * B C

Trong đa số các ngôn ngữ lập trình, các biểu thức vẫn được viết dưới dạng trung tố thông thường, nhưng khi việc tính toán trong máy thì lại được chương trình dịch tự động chuyển sang dạng hậu tố hoặc tiền tố để tính giá trị của biểu thức.

* Quy ước về biểu diễn biểu thức dưới dạng hậu tố:

- Dấu phép toán đặt sau các toán hạng tham gia phép toán này:

 TH  TH 

TH1  TH2  TH1 TH 2 

- Dấu phép toán thực hiện cuối cùng khi tính giá trị của biểu thức luôn nằm bên phải nhất.

* Các bước biến đổi biểu thức dạng trung tố thành biểu thức dạng hậu tố:

- Phân tích biểu thức để xác định dấu phép toán thực hiện cuối cùng khi tính giá trị, Nếu các toán hạng tham gia vào phép toán này là biểu thức con của biểu thức ban đầu thì tiếp tục phân tích các biểu thức con đó để xác địng dấu phép toán được thực hiện cuối cùng để tính giá trị biểu thức con đó. Phép toán cứ thế được thực hiện cho đến khi tất cả mọi toán hạng đều là nguyên tố (là hằng hoặc là biến)

- Thực hiện quy ước 1 để chuyển dấu phép toán ra sau các toán hạng tương ứng của nó. Biểu thức thu được ta gọi là biểu thức dạng hậu tố.

Ví dụ: Chuyển biểu thức x + y * (z – t) – u/v sang biểu thức dạng hậu tố:

x

+

y

*

(

z

-

t

)

-

u

/

v



x

+

y

*

(

z

-

t

)

u

/

v

-



x

y

*

(

z

-

t

)

+

u

v

/

-



x

y

(

z

-

t

)

*

+

u

v

/

-



x

y

z

t

-

*

+

u

v

/

-

* Giải thuật chuyển biểu thức từ dạng trung tố sang biểu thức dạng hậu tố:

Procedure Polish (Q, P);

{Q là biểu thức viết dưới dạng trung tố, giải thuật này biến đổi Q sang dạng hậu tố P, thoạt đầu P rỗng}

1. Thêm dấu “)” vào cuối Q; {để làm dấu kết thúc}

Call Push(S,T, “(“); {Dấu ngoặc mở này tương ứng với dấu ngoặc đóng mới thêm vào cuối Q}

2. Repeat {Đọc ký tự X trong Q khi duyệt từ trái qua phải}

3. Case

X là toán hạng: Bổ sung thêm X vào P;

X là dấu ngoặc mở: Call Push (S, T, “(“);

X là toán tử: While thứ tự ưu tiên của S[T]  thứ tự ưu tiên của X do Begin

Call POP (S, T, W); {Bổ sugn thêm W vào P}

End;

Call Push(S, T, X);

X là dấu ngoặc đóng: reapeat

Call POP(S, T, W); {Bổ sung thêm W vào P};

Until gặp dấu “(“ thì loại dấu “(“ ra khỏi Stack S

End Case

Until Stack rỗng

4. Return;

* Giải thuật tính giá trị của biểu thức dạng hậu tố:

Procedure Eval (P, Val);

1. Ghi thêm dấu “)” vào cuối biểu thức P để làm kết thúc;

2. Repeat {Đọc ký tự X trong P khi duyệt từ trái sang phải}

3. If X là toán hạng then

Call Push (S, T, X)

4. Else Begin

Call POP (S, T, Y);

Call POP (S, T, Z);

W := Z (X) Y; {(X) chỉ toán tử X}

Call PUSH (S, T, W)

End;

Until gặp dấu kết thúc “)”;

5. Call POP (S, T, Val);

6. Return;

3.5.2. Một số ứng dụng của Queue

3.5.2.1. Dùng Queue để đổi 1 số 0 < x <1 từ hệ 10 sang hệ 2.

* Phân tích giải thuật: Mang giá trị x nhân liên tiếp với 2, giữ lại phần nguyên rồi lại lấy phần lẻ nhân với 2 cho đến khi x = 0 hoặc nhân đến lúc số lần nhân bằng số lượng số lẻ mà máy tính có thể biểu diễn được, số lượng số lẻ đó quyết định Nmax trong Queue, nếu Nmax càng lớn thì sai số càng hạn chế.

Kết quả chuyển đổi là phần nguyên của các tích mà ta nhận được viết theo đúng thứ tự.

Procedure Doi_co_so (x);

Begin

F := 0; R := 0;

While (x <> 0) and (R < Nmax) do

Begin

R := Trunc (x * 2);

CQInsert (Q, F, R, k);

x := x*2 – trunc(x*2)

End;

Write (‘0’);

While F <> 0 do

Begin

CQDelete (Q, F, R, i);

Write (i);

End;

3.5.2.2. Bài toán quản lý kho hàng

Đây là dạng bài toán sản xuất và tiêu dùng, mặt hàng được sản xuất ra sẽ được lưu vào kho, hàng hóa từ kho này sẽ được xuất ra ngoài cho nhà phân phối. Khi đó mặt hàng nào đưa vào kho trước tiên sẽ được xuất kho trước. Đây là dạng FIFO nên chúng ta có thể sử dụng cấu trúc dữ liệu queue.

3.6. Bài tập

Bài 1: Sử dụng Stack, viết chương trình nhập vào một số nguyên, không âm bất kỳ, sau đó xuất ra màn hình số đảo ngược thứ tự các chữ số của số nhập vào.

Ví dụ:

- Nhập vào một số nguyên: 10245

- Số nguyên ở dạng đảo ngược: 54201

Bài 2: Sử dụng Stack, viết chương trình chuyển đổi một số nguyên N trong hệ thập phân (hệ 10) sang biểu diễn ở:

a. Hệ nhị phân (hệ 2)

b. Hệ thập lục phân (hệ 16)

Bài 3: Viết chương trình mô phỏng cho bài toán “Tháp Hà nội” và “Tháp Saigon” với các

cấu trúc dữ liệu như sau:

a. Sử dụng danh sách liên kết để lưu trữ các cột tháp;

b. Sử dụng Stack để lưu trữ các cột của tháp

c. Có nhận xét gì cho từng trường hợp?

Bài 4: Cho biểu thức dạng trung tố P_tt : (a + b)  c / (d + e * (f - g))

a. Viết biểu thức dạng hậu tố Pht tương ứng.

b. Minh họa tình trạng của Stack qua các bước thực hiện giải thuật EVAL khi tính giá trị của biểu thức Pht với:

a = 7; b = 3; c = 2; d = 5; e = 2; f = 16; g = 6

Chương 4. Sắp xếp và tìm kiếm

4.1. Giới thiệu về sắp xếp và tìm kiếm

Sắp xếp và tìm kiếm là các vấn đề rất cơ bản trong tin học cũng như thực tiễn. Chương này giới thiệu các phương pháp sắp xếp và tìm kiếm thông dụng nhất, bao gồm các giải thuật từ đơn giản đến phức tạp.

4.1.1. Giới thiệu về sắp xếp

Sắp xếp (sorting) là quá trình bố trí lại các phần tử của 1 tập đối tượng nào đó, theo một thứ tự nhất định nhằm thực hiện tìm kiếm thuận lợi, xử lý các kết quả nhanh chóng,...

Dữ liệu trong máy tính có thể xuất hiện dưới nhiều dạng khác nhau, nhưng ở đây ta quy ước tập đối tượng được sắp xếp là tập các bản ghi (record), mỗi bản ghi bao gồm các trường dữ liệu, tương ứng là các thuộc tính dữ liệu khác nhau.

Giả sử rằng mỗi phần tử dữ liệu được xem xét có 1 thành phần khóa (key) để nhận diện, việc sắp xếp dữ liệu coi như sắp xếp đối với khóa, để minh họa cho các phương pháp sắp xếp ta coi khóa K₁, K₂,..., K_n là các số và thứ tự sắp xếp là tăng dần, giả sử dãy số được coi là các khóa dùng minh họa cho các giải thuật là:

24

42

23

74

11

65

58

94

36

99

87

4.1.2. Giới thiệu về tìm kiếm

Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Ví dụ tra cứu từ điển, tìm kiế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 1 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ừ điểm được sắp xếp theo vần, trong mỗi vần lại được sắp xếp theo trình tự alphabet sẽ giúp chúng ta tìm kiếm nhanh hơn.

Vì thế, khi xây dựng một hệ quản lí thông tin, bên cạnh thuật toán tìm kiếm, các thuật toán sắp xếp dự liệu cũng là chủ đề được quan tâm hàng đầu.

Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Kết quả tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn phải xác định xem vị trí của phần tử dữ liệu tìm thấy ở đâu.

4.2. Các phương pháp sắp xếp

4.2.1. Các phương pháp sắp xếp đơn giản

a. Thuật toán sắp xếp lựa chọn (Selection Sort)

Ý tưởng thuật toán

Dựa vào thuật toán tìm MAX, MIN
Ở lần duyệt thứ i, với 1<=i<n, tìm ra phần tử nhỏ nhất đổi chỗ cho phần tử thứ i.
Sau n-1 lượt dãy được sắp xếp

Ví dụ: Cho mảng A có 5 số nguyên (n=5)

A[1]	A[2]	A[3]	A[4]	A[5]
3	-1	5	7	-4

Yêu cầu sắp xếp dãy số theo chiều tăng dần.

Quá trình sắp xếp theo thuật toán sắp xếp lựa chọn được mô tả như sau:

Thuật toán sắp xếp lựa chọn

Input: Dãy X₁, X₂, …, X_n
Output: Dãy X₁, X₂, …, X_n không giảm
Thuật toán:

For i = 1 to n-1

k = i;

For j = i+1 to n

If(X_j < X_k)

k = j;

If (i != k)

ĐổiChỗ(X_i, X_k);

Lời giải ví dụ 1:

Khóa Bước	A[1]	A[2]	A[3]	A[4]	A[5]
Ban đầu	3	-1	5	7	-4
Bước 1	-4	-1	5	7	3
Bước 2		-1	5	7	3
Bước 3			3	7	5
Bước 4				5	7
Kết quả	-4	-1	3	5	7

b. Thuật toán sắp xếp chèn (Insertion Sort)

Ý tưởng thuật toán :

Ở lần duyệt thứ i, với 1<=i<n, đặt phần tử phần tử ở vị trí i vào đúng thứ tự của nó so với i-1 phần tử trước đã được sắp xếp.
Sau n-1 lượt dãy được sắp xếp

Ví dụ: Cho mảng A có 5 số nguyên (n=5)

A[1]	A[2]	A[3]	A[4]	A[5]
3	-1	7	-4	5

Yêu cầu sắp xếp dãy số theo chiều tăng dần.

Quá trình sắp xếp theo thuật toán sắp xếp chèn được mô tả như sau:

Xem dãy cần sắp gồm 2 dãy nối tiếp
Dãy trái (dãy đích) gồm các phần tử đã được sắp, dãy phải (dãy nguồn) là các phần tử chưa được sắp.

Lấy phần tử đầu dãy nguồn chèn vào vị trí thích hợp trong dãy đích

Thuật toán sắp xếp chèn

Input: Dãy X1, X2, …, Xn
Output: Dãy X1, X2, …, Xn không giảm
Thuật toán:

For i = 2 to n

tg = Xi;

j = i-1;

While (tg < Xj) & (j > 0)

Xj+1 = Xj;

j = j – 1;

Xj+1 = tg;

Ví dụ:

c. Thuật toán sắp xếp nổi bọt (Bubble Sort)

Ý tưởng thuật toán :

Ở lần duyệt thứ i, với 1<=i<n, xuất phát từ cuối dãy, so sánh hai phần tử kế tiếp nhau, phần tử nào nhỏ hơn cho đổi lên. Phần tử nhỏ nhất sẽ được đổi lên vị trí thứ i.
Sau n -1 lượt dãy được sắp xếp

Ví dụ: Cho mảng A có 5 số nguyên (n=5)

A[1]	A[2]	A[3]	A[4]	A[5]
3	-1	7	-4	5

Yêu cầu sắp xếp dãy số theo chiều tăng dần.

Quá trình sắp xếp theo thuật toán sắp xếp lựa chọn được mô tả như sau:

Kết quả của các lần duyệt như sau:

Thuật toán sắp xếp nổi bọt

Input: Dãy X1, X2, …, Xn
Output: Dãy X1, X2, …, Xn không giảm
Thuật toán:

For i = 1 to i=n-1

For j = n to i+1

If (X_j < X_j-1) then ĐổiChỗ(X_j, X_j-1)

Ví dụ:

4.2.2. Các phương pháp sắp xếp nhanh

a. Thuật toán sắp xếp phân đoạn (Quick Sort)

Ý tưởng thuật toán :

Gán i = chỉ số đầu, so sánh a[i] với chốt, a[i]<chốt tăng i, a[i]>=chốt dừng i
Gán j=chỉ số cuối, so sánh a[j] với chốt, a[j]>chốt giảm j, a[j]<=chốt dừng j
Nếu i<=j thì đổi chỗ a[i] với a[j], tăng i, giảm j tiếp tục so sánh tới khi i>j
Gọi đệ quy cho đoạn từ chỉ số đầu tới j, từ i tới chỉ số cuối
Gán i = chỉ số đầu, so sánh a[i] với chốt, a[i]<chốt tăng i, a[i]>=chốt dừng i
Gán j=chỉ số cuối, so sánh a[j] với chốt, a[j]>chốt giảm j, a[j]<=chốt dừng j
Nếu i<=j thì đổi chỗ a[i] với a[j], tăng i, giảm j tiếp tục so sánh tới khi i>j
Gọi đệ quy cho đoạn từ chỉ số đầu tới j, từ i tới chỉ số cuối

Ví dụ: Sắp xếp dãy số nguyên sau theo thứ tự tăng dần

A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
53	21	68	12	40	33	67	31	25

Quá trình sắp xếp theo thuật toán sắp xếp lựa chọn được mô tả như sau:

Thuật toán sắp xếp phân đoạn

void quick(int l,int r,int a[])

{ int i,j,x,tg;

if (l>=r) return;

x=a[(l+r)/2];

i=l; j=r;

while (i<=j)

{ while (a[i]<x) i++;

while (a[j]>x) j-- ;

if (i<=j)

{tg=a[i];

a[i]=a[j];

a[j]=tg;

i++; j--;

}

quick(l,j,a);

quick(i,r,a);

}

Ví dụ:

b. Thuật toán sắp xếp vun đống (heapsort)

Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó.

Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách.

Ý tưởng thuật toán :

(1) Xem mảng ban đầu là một cây nhị phân. Mỗi nút trên cây lưu trữ 1 phần tử mảng, trong nó a[0] là nút gốc và mỗi nút không là nút lá a[i] có con trái là a[2i+1] và con phải là a[2i+2]. Với cách tổ chức này thì cây nhị phân thu được sẽ có các nút trong là các nút a[0], …, a[(n-2)/2]. Tất cả các nút trong đều có 2 con, ngoại trừ nút a[(n-2)/2] có thể chỉ có một con trái (trong trường hợp n là một số chẵn).
(2) Sắp xếp cây ban đầu thành một heap căn cứ vào giá trị khoá của các nút.
(3) Hoán đổi nút gốc a[0] cho cho nút lá cuối cùng.
(4) Sắp lại cây sau khi đã bỏ đi nút lá cuối cùng để nó trở thành một heap mới.
Lặp lại quá trình (3) và (4) cho tới khi cây chỉ còn một nút. Nút này cùng với các nút lá đã bỏ đi tạo thành một mảng sắp theo thứ tự giảm.

Ví dụ:

Dãy khóa K:

45 21 32 15 72 62 54 90 82

Sắp xếp dãy khóa K theo thứ tự tăng dần bằng phương pháp sắp xếp vun đống

Từ dãy đã cho ta có cây nhị phân:

Cây nhị phân: các cây trong đó mỗi nút có không quá hai con.
Về chỉ số: Nếu i chỉ ra nút bất kì (i ≤ n/2) thì :

Con trái có chỉ số là: 2i
Con phải có chỉ số là: 2i+1

Vun đống

Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.

Vun đống tại đỉnh thứ i

Nếu hai cây con gốc 2i và 2i +1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị K[2i] và K[2i + 1], nếu K[i] nhỏ hơn thì đổi chỗ chúng cho nhau.

Nếu đổi chỗ cho K[2i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đến khi hoặc gặp đỉnh lá.

Vun một mảng thành đống

Để vun mảng a[0..n-1] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n-2/2) ngược lên tới a[0].

Bước vun đống:

Bước 1: Bắt đầu vun đống từ đỉnh i = 4:

Bước 2: Vun đống tại đỉnh i = 3:

Bước 3: Bắt đầu vun đống từ đỉnh i = 2:

Bước 4: Vun đống tại đỉnh i = 1:

Sắp xếp bằng vun đống

Đổi chỗ (Swap): Sau khi mảng a[0..n-1] đã là đống, lấy phần tử a[0] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n-1] lên đỉnh đống thì phần tử a[n-1] đã được đứng đúng vị trí.
Vun lại: Phần còn lại của mảng a[0..n-2] chỉ khác cấu trúc đống ở phần tử a[0]. Vun lại mảng này thành đống với n-1 phần tử.
Lặp: Tiếp tục với mảng a[0..n-2]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.

Bước sắp xếp vun đống

Bước 1: Hoán đổi vị trí của K[1] cho K[9] rồi vun các khóa từ K[1] đến K[8] thành đống

Bước 2: Hoán đổi vị trí của K[1] cho K[8] rồi vun các khóa từ K[1] đến K[7] thành đống

Bước 3: Hoán đổi vị trí của K[1] cho K[7] rồi vun các khóa từ K[1] đến K[6] thành đống

Bước 4: Hoán đổi vị trí của K[1] cho K[6] rồi vun các khóa từ K[1] đến K[5] thành đống

Bước 5: Hoán đổi vị trí của K[1] cho K[5] rồi vun các khóa từ K[1] đến K[4] thành đống

Bước 6: Hoán đổi vị trí của K[1] cho K[4] rồi vun các khóa từ K[1] đến K[3] thành đống

Bước 7: Hoán đổi vị trí của K[1] cho K[3] rồi vun các khóa từ K[1] đến K[2] thành đống

Bước 8: Hoán đổi vị trí của K[1] cho K[2] rồi vun các khóa từ K[1] đến K[1] thành đống

Thứ tự của dãy khóa K sau khi sắp xếp là:

15 21 32 45 54 62 72 82 90

4.3. Các phương pháp tìm kiếm

4.3.1.Tìm kiếm tuyến tính

a.Giới thiệu phương pháp

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 dãy khó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.

b.Giải thuật

Các bước thực hiện ý tưởng giải thuật:

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 :

+ a[i] = x : Tìm thấy. Dừng

+ 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.

Cài đặt thuật toán:

Function TKTT(A,n,X):Integer;

Begin

i:=1; A[n+1]:=X;

While A[i] <> X do i:=i+1;

{Tìm thấy hay không}

if i=n+1 then TKTT:=0

else TKTT:=i;

End;

c. Ví dụ minh họa

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 :

i = 1

i = 2

i = 3

Dừng.

4.3.2.Tìm kiếm nhị phân

a. Giới thiệu phương pháp

Nếu các phần tử của A đã được sắp xếp, thì tìm kiếm nhị phân là phương pháp tìm kiếm khá thông dụng. Nó tương tự như cách thức ta hay làm như tra một từ trong từ điển. Đối với phép tìm kiếm nhị phân thì ta luôn chọn khoá ở giữa, giả sử dẫy đang xét là A₁, …,A₂ thì khoá ở giữa dãy sẽ là A_i với i= (l+r) div 2. Nếu X<A_i thì tìm kiếm được thực hiện tiếp với A₁,…,A_i-1; còn nếu ngược lại tìm kiếm lại được làm với A_i+1,…,A_n

b. Giải thuật

Các bước thực hiện ý tưởng giải thuật:

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 :

+ a[mid] = x: Tìm thấy. Dừng

+ a[mid] > x: //tìm tiếp x trong dãy con a_left.. a_{mid -1} :

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ử.

Cài đặt thuật toán:

Function B_search(A,n,X)

Var l,r,m:Integer;

Begin

l:=1; r:=n;

While l<=r do

Begin

m:=(l+r)div 2;

if X < A[m] then r:=m-1;

else if X > A[m] then l:=m+1;

else

Begin

B_Search:=m; Exit;

End;

end;

B_Search:=0;

End;

c.Ví dụ minh họa

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.

4.4. Bài tập

Bài 1: Cho dãy số: 3 7 4 5 17 2 6 9

Minh hoạ việc sắp xếp dãy số trên theo chiều tăng dần bằng 5 phương pháp đã học.

Bài 2: Cho dãy số ở câu 4.1

Minh hoạ việc sắp xếp dãy số trên theo chiều giảm dần bằng 5 phương pháp đã học.

Bài 3. Cho dãy số : -10 8 9 6 12 7.

Minh họa việc tìm kiếm số k=15 trong dãy trên theo phương pháp tìm kiếm tuần tự.

Bài 4: Cho danh sách các tên sinh viên được xếp theo thứ tự sau:

1	2	3	4	5	6	7	8	9	10
An	Binh	Cúc	Giao	Hùng	Kiên	Lộc	Ninh	Sơn	Vy

Áp dụng thuật toán tìm kiếm nhị phân(Binary Search) để tìm tên Cúc, Sơn trong danh sách. Nêu rõ giá trị của biến L, R, Mid ứng với từng lược

Hỏi đáp

MÔN HỌC

Cấu trúc dữ liệu & giải thuật

Nội dung tài liệu

Các tài liệu liên quan

Có thể bạn quan tâm

Thông tin tài liệu