Xem mẫu
- TRƯỜNG CAO ĐẲNG NGHỀ ĐẮK LẮK
KHOA ĐIỆN TỬ - TIN HỌC
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGHỀ: CÔNG NGHỆ THÔNG TIN
TRÌNH ĐỘ: CAO ĐẲNG NGHỀ - TRUNG CẤP NGHỀ
Người biên soạn: Nguyễn Thị Thu Hà
Lưu hành nội bộ - 2014
- 1
Lời nói đầu
Hiện nay, tại Trường chưa có giáo trình Cấu trúc dữ liệu & giải thuật. Đặc
biệt trên thị trường không có tài liệu học tập, tham khảo phù hợp với chương
trình khung Cao đẳng nghề, trung cấp nghề thuộc nghề Công nghệ thông tin
(CNTT) trong quá trình đào tạo nghề hiện nay.
Nhóm tác giả biên soạn giáo trình lập trình cơ bản nhằm mục đích giúp học
sinh, sinh viên (HSSV) sử dụng giáo trình làm tài liệu nghiên cứu và học
tập một cách thuận tiện. Chương trình môn học được sử dụng để giảng dạy
cho sinh viên cao đẳng nghề Công nghệ thông tin (ứng dụng phần mềm) và
làm tài liệu tham khảo cho các nghề thuộc các ngành nghề kỹ thuật.
Vậy, rất mong được sự góp ý của bạn đọc để tài liệu này ngày càng được
hoàn thiện hơn, chúng tôi xin chân thành cảm ơn.
Đắk Lắk, ngày 02 tháng 09 năm 2014
Tham gia biên soạn
Chủ biên: Nguyễn Thị Thu Hà
ThS. Lê Văn Tùng
- 2
CHƯƠNG TRÌNH MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Mã số của môn học: MH 12;
Thời gian của môn học: 75 giờ; (Lý thuyết: 24 giờ; Thực hành: 51 giờ)
I. VỊ TRÍ, TÍNH CHẤT CỦA MÔN HỌC:
Cấu trúc dữ liệu và giải thuật là môn cơ sở nghề bắt buộc, được học sau các môn học
Tin học, Lập trình căn bản.
II. MỤC TIÊU CỦA MÔN HỌC:
- Hiểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng
chương trình;
- Hiểu được ý nghĩa, cấu trúc, cách khai báo, các thao tác của các loại cấu trúc dữ liệu:
mảng, danh sách liên kết, cây và các giải thuật cơ bản xử lý các cấu trúc dữ liệu đó;
- Xây dựng được cấu trúc dữ liệu và mô tả tường minh các giải thuật cho một số bài
toán ứng dụng cụ thể;
- Cài đặt được một số giải thuật trên ngôn ngữ lập trình C;
Coi việc học môn này là một nền tảng cho các môn học chuyên môn tiếp theo,
nghiêm túc và tích cực trong việc học lý thuyết và làm bài tập, chủ động tìm kiếm các
nguồn tài liệu liên quan đến môn học.
III. NỘI DUNG MÔN HỌC:
1. Nội dung tổng quát và phân bổ thời gian:
Thời gian
Tên chương, mục
Số
Thực Kiểm tra*
TT Tổng Lý
hành, (LT hoặc
số thuyết
Bài tập TH)
I Thiết kế và phân tích giải thuật 15 4 11 0
II Các kiểu dữ liệu cơ sở 8 2 6 0
Mảng, danh sách và các kiểu dữ liệu
III 20 5 13 2
trừu tượng
IV Cây 7 3 4 0
V Sắp xếp 15 5 10 0
VI Tìm kiếm 10 3 5 2
Tổng cộng 75 22 49 4
- 3
Chương 1: Thiết kế và phân tích giải thuật
1. Mở đầu:
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 đưa vào (input data), dữ liệu trung gian hoặc dữ liệu
đưa ra (output data). 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 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ế, cài đặt chương trình.
2. Thiết kế giải thuật:
Khái niệm giải thuật hay thuật giải mà 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 (method) để 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ả tựa trên một hay một 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), chẳng hạn như C, Pascal, ?
Khi đã xác định được cấu trúc dữ liệu 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ở của cấu
trúc dữ liệu đã đượ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à một việc mà người lập trình phải cân nhắc và
tính toán. Sự lựa chọn này cũng có thể 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 thuật toán trên một ngôn ngữ cụ thể.
3. Phân tích giải thuật:
Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức:
Cấu trúc dữ liệu + Giải thuật = Chương trình
Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện
chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu
mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại không thể
có Thuật giải khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ có thể được
hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật
xử lý dữ liệu theo yêu cầu của bài toán đặt ra.
3.1 Đánh giá cấu trúc dữ liệu và giải thuật
3.1.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu
Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau:
- Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),
- Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,
- Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.
3.2. Đánh giá độ phức tạp của thuật toán
Việc đánh giá độ phức tạp của một thuật toán quả không dễ dàng chút nào. Ở
dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể
có sự so sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian
thực hiện một thuật toán còn phụ thuộc rất nhiều vào các điều kiện khác như cấu
- 4
tạo của máy tính, dữ liệu đưa vào, ở đây chúng ta chỉ xem xét trên mức độ của lượng
dữ liệu đưa vào ban đầu cho thuật toán thực hiện.
Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện
thuật toán trong hai trường hợp:
- Trong trường hợp tốt nhất: Tmin
- Trong trường hợp xấu nhất: Tmax
Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Tavg
4. Một số giải thuật cơ bản:
4.1: Thuật toán đơn giản
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 đưa vào (input data), dữ liệu trung gian và dữ liệu ra (output
data).
Ví dụ: Nhập vào một số 3 chữ số, in ra tổng của 3 chữ số đó.
#include
int n, dv, ch, tr, tong;
void main()
{
printf(“Nhap vao mot so 3 chu so:”);
scanf(“%d”, &n);
dv = n mod 10;
ch = (n div 10) mod 10;
tr = (n div 100) mod 10;
tong = dv+ ch+ tr;
printf(“Tong 3 so la: %d”, tong);
getchar();
}
4.2: Thuật toán phức tạp:
Ví dụ : Dãy số Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Bắt đầu bằng 0 và 1, các số tiếp theo bằng tổng hai số đi
trước.
Dãy Fibonacci được khai báo đệ quy như sau:
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n – 1) + Fibonacci(n – 2)
4.3: Giải thuật đệ quy:
Bất cứ một hàm nào đó có thể triệu gọi hàm khác, nhưng ở đây một hàm nào đó có thể tự
triệu gọi chính mình. Kiểu hàm như thế được gọi là hàm đệ quy.
- 5
Phương pháp đệ quy thường dùng phổ biến trong những ứng dụng mà cách giải quyết có
thể được thể hiện bằng việc áp dụng liên tiếp cùng giải pháp cho những tập hợp con của
bài toán.
Ví dụ 1: tính n!
n! = 1*2*3*…*(n-2)*(n-1)*n với n >= 1 và 0! = 1.
/* Ham tinh giai thua */
#include
#include
void main(void)
{
int in;
long giaithua(int);
printf("Nhap vao so n: ");
scanf("%d", &in);
printf("%d! = %ld.\n", in, giaithua(in));
getch();
}
long giaithua(int in)
{
int i;
long ltich = 1;
if (in == 0)
return (1L);
else
{
for (i = 1; i
- 6
return (in * giaithua(in – 1));
}
� Chạy lại chương trình, quan sát, nhận xét và đánh giá kết quả
� Giải thích hoạt động của hàm đệ quy giaithua
Ví dụ giá trị truyền vào hàm giaithua qua biến in = 5.
• Thứ tự gọi thực hiện hàm giaithua
giaithua(in) return(in * giaithua(in – 1))
5 * giaithua(4) = 5 * ?
4 * giaithua(3) = 4 * ?
3 * giaithua(2) = 3 * ?
2 * giaithua(1) = 2 * ?
1 * giaithua(0) = 1 * ?
Khi tham số in = 0 thì return về giá trị 1L (giá trị 1 kiểu long). Lúc này các giá trị
?
bắt đầu định trị theo thứ tự ngược lại.
• Định trị theo thứ tự ngược lại
giaithua(in) return(in * giaithua(in – 1))
1 * giaithua(0) = 1 * 1 = 1
2 * giaithua(1) = 2 * 1 = 2
3 * giaithua(2) = 3 * 2 = 6
4 * giaithua(3) = 4 * 6 = 24
5 * giaithua(4) = 5 * 24 = 120
Kết quả sau cùng ta có 5! = 120.
Thứ tự gọi đệ quy Định trị theo thứ tự ngược lạiA
4.4. Bài tập
1. Viết hàm đệ quy tính tổng n số nguyên dương đầu tiên:
tong (n) = n + tong (n – 1).
2. Viết hàm đệ quy tính N!
3. Viết hàm đệ qui.
- 7
Chương 2: Các kiểu dữ liệu cơ sở
1. Khái niệm về kiểu dữ liệu
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 =
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.
2. Các kiểu dữ liệu cơ bản
Kiểu số nguyên là kiểu dữ liệu dùng để lưu các giá trị nguyên hay còn gọi là
kiểu đếm được. Kiểu số nguyên trong C được chia thành các kiểu dữ liệu con, mỗi
kiểu có một miền giá trị khác nhau
2.1. Kiểu số nguyên 1 byte (8 bits)
Kiểu số nguyên một byte gồm có 2 kiểu sau:
1. unsigned char Từ 0 đến 255 (tương đương 256 ký tự trong
bảng mã ASCII)
2. char Từ -128 đến 127
Kiểu unsigned char: lưu các số nguyên dương từ 0 đến 255.
=> Để khai báo một biến là kiểu ký tự thì ta khai báo biến kiểu unsigned char.
Mỗi số trong miền giá trị của kiểu unsigned char tương ứng với một ký tự trong bảng mã
ASCII .
Kiểu char: lưu các số nguyên từ -128 đến 127. Kiểu char sử dụng bit trái nhất
để làm bit dấu.
=> Nếu gán giá trị > 127 cho biến kiểu char thì giá trị của biến này có thể là số
âm (?).
2.2. Kiểu số nguyên 2 bytes (16 bits)
Kiểu số nguyên 2 bytes gồm có 4 kiểu sau:
1. enum Từ -32,768 đến 32,767
2. unsigned int Từ 0 đến 65,535
3. short int Từ -32,768 đến 32,767
4. int Từ -32,768 đến 32,767
Kiểu enum, short int, int : Lưu các số nguyên từ -32768 đến 32767. Sử dụng
- 8
bit bên trái nhất để làm bit dấu.
=> Nếu gán giá trị >32767 cho biến có 1 trong 3 kiểu trên thì giá trị của biến
này có thể là số âm.
Kiểu unsigned int: Kiểu unsigned int lưu các số nguyên dương từ 0 đến 65535.
2.3. Kiểu số nguyên 4 byte (32 bits)
Kiểu số nguyên 4 bytes hay còn gọi là số nguyên dài (long) gồm có 2 kiểu sau:
1. unsigned long Từ 0 đến 4,294,967,295
2. long Từ -2,147,483,648 đến 2,147,483,647
Kiểu long : Lưu các số nguyên từ -2147483658 đến 2147483647. Sử dụng bit
bên trái nhất để làm bit dấu.
=> Nếu gán giá trị >2147483647 cho biến có kiểu long thì giá trị của biến này
có thể là số âm.
Kiểu unsigned long: Kiểu unsigned long lưu các số nguyên dương từ 0 đến
4294967295
Kiểu số thực thường được thực hiện với các phép toán: O =?{+, -, *, /, , =, =,
?}?
2.4. Kiểu số thực:
Kiểu số thực dùng để lưu các số thực hay các số có dấu chấm thập phân gồm có
3 kiểu sau:
1. float 4 bytes Từ 3.4 * 10-38 đến 3.4 * 1038
2. double 8 bytes Từ 1.7 * 10-308 đến 1.7 * 10308
3. long double 10 bytes Từ 3.4 *10-4932 đến 1.1 *104932
Mỗi kiểu số thực ở trên đều có miền giá trị và độ chính xác (số số lẻ) khác
nhau. Tùy vào nhu cầu sử dụng mà ta có thể khai báo biến thuộc 1 trong 3 kiểu trên.
Ngoài ra ta còn có kiểu dữ liệu void, kiểu này mang ý nghĩa là kiểu rỗng không chứa giá
trị gì cả.
Kiểu số nguyên thường được thực hiện với các phép toán: O =?{+, -, *, /, DIV, MOD,
, =, =, ?}?
2.5. Kiểu ký tự: Có thể có các kích thước sau:
+ Kiểu ký tự 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, , =, =, ?}?
- 9
3. Các kiểu dữ liệu có cấu trúc
3.1 Khái niệm:
Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu khác
nhau, mỗi thành phần được gọi là một trường (field)
Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng
kiểu còn các phần tử của kiểu cấu trúc có thể có kiểu khác nhau.
Hình ảnh của kiểu cấu trúc được minh họa:
3.2 Định nghĩa kiểu cấu trúc
struct
{
;
;
……..
;
};
Trong đó:
- : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên
này mang ý nghĩa sẽ là tên kiểu cấu trúc.
- (i=1..n): mỗi trường trong cấu trúc có dữ liệu thuộc kiểu
gì (tên của trường phải là một tên được đặt theo quy tắc đặt tên của danh biểu).
Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai
báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm.
struct NgayThang
{
unsigned char Ngay;
unsigned char Thang;
unsigned int Nam;
};
typedef struct
{
- 10
unsigned char Ngay;
unsigned char Thang;
unsigned int Nam;
} NgayThang;
Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thông tin: mã số sinh viên, họ
tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta có thể khai báo
một struct gồm các thông tin trên.
struct SinhVien
{
char MSSV[10];
char HoTen[40];
struct NgayThang NgaySinh;
int Phai;
char DiaChi[40];
};
typedef struct
{
char MSSV[10];
char HoTen[40];
NgayThang NgaySinh;
int Phai;
char DiaChi[40];
} SinhVien;
3.3 Khai báo biến cấu trúc
Việc khai báo biến cấu trúc cũng tương tự như khai báo biến thuộc kiểu dữ liệu
chuẩn.
Cú pháp:
- Đối với cấu trúc được định nghĩa theo cách 1:
struct [, …];
- Đối với các cấu trúc được định nghĩa theo cách 2:
[, …];
Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc NgayThang; biến SV có kiểu
cấu trúc SinhVien.
struct NgayThang NgaySinh;
struct SinhVien SV;
NgayThang NgaySinh;
SinhVien SV;
4. kiểu tập hợp:
4.1. khái niệm:
Đối với các kiểu dữ liệu ta đã biết như kiểu số, kiểu mảng, kiểu cấu trúc thì dữ
liệu kiểu tập hợp (typedef) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu dữ liệu
giống hoặ khác nhau, mỗi thành phần được gọi là một trường (field).
- 11
4.2.Khai báo biến tập hợp:
Sử dụng từ khóa typedef (Type definitions) để định nghĩa kiểu:
Typedef struct
{
;
;
……..
;
} ;
Trong đó:
- typedef (Type definitions): là kiểu do người dùng định nghĩa.
- : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này
mang ý nghĩa sẽ là tên kiểu cấu trúc.
(i=1..n): mỗi trường trong cấu trúc có dữ liệu thuộc kiểu
dữ liệu cơ bản.
Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai
báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm.
Typedef struct
{
unsigned char Ngay;
unsigned char Thang;
unsigned int Nam;
} NgayThang;
Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thông tin: mã số sinh viên, họ
tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta có thể khai báo một
struct gồm các thông tin trên.
typedef struct
{
char MSSV[10];
char HoTen[40];
NgayThang NgaySinh;
int Phai;
char DiaChi[40];
} SinhVien;
4.3 Khai báo biến kiểu tập hợp:
Việc khai báo biến tập hợp cũng tương tự như khai báo biến thuộc kiểu dữ liệu
chuẩn.
Cú pháp:
- Đối với cấu trúc được định nghĩa theo cách 1:
struct [, …];
- Đối với các cấu trúc được định nghĩa theo cách 2:
[, …];
Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc NgayThang; biến SV có kiểu
- 12
cấu trúc SinhVien.
struct NgayThang NgaySinh;
struct SinhVien SV;
NgayThang NgaySinh;
SinhVien SV;
5.Câu hỏi và Bài tập
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?
2. Các tiêu chuẩn để đánh giá cấu trúc dữ liệu và giải thuật?
3. Khi xây dựng giải thuật có cần thiết phải quan tâm tới cấu trúc dữ liệu hay
không? Tại sao?
4. Liệt kê các kiểu dữ liệu cơ sở, các kiểu dữ liệu có cấu trúc trong C, Pascal?
- 13
Chương 3: Mảng, danh sách và các kiểu dữ liệu trìu tượng
1. Mảng:
Mỗi biến chỉ có thể biểu diễn một giá trị. Để biểu diễn một dãy số hay một bảng
số ta có thể dung nhiều biến nhưng cách này không thuận lợi. trong trường hợp
này ta có khái niệm về mảng. khái niệm về mảng trong ngôn ngữ C cũng giống
như khái niệm về ma trận trong đại số tuyến tính.
Mảng có thể hiểu là một tập hợp nhiều phần tử có cùng kiểu giá trị và cùng cùng
chung một tên. Mỗi phần tử mảng biểu diễn được một giá trị. Có bao nhiêu kiểu
biến thì có bấy nhiêu kiểu mảng. mảng cần được khai báo để định rõ: loại mảng:
int, float, double,….
Tên mảng.
Số chiều dài và kích thước mỗi chiều.
Khái niệm về kiểu mảng và tên mảng cũng giống như khái niệm về kiểu biến và
tên biến. ta sẽ giải thích về số chiều và kích thước mỗi chiều thong qua các ví dụ
cụ thể dưới đây.
Các khai báo:
int a[10],b[4][2];
float x[5],y[3][3];
Chú ý:
Các phần tử của mảng được cấp phát các khoản nhớ lien tiếp nhau trong bộ nhớ. Nói
cách khác, các phần tử của mảng liên tiếp nhau.
Trong bộ nhớ, các phần tử của mảng hai chiều được sắp xếp theo hang.
Chỉ số mảng:
Một phần tử cụ thể của mảng được xác định nhờ các chỉ số của nó. Chỉ số của mảng
phải có giá trị int không vượt quá kích thước tương ứng. số chỉ số bằng số chiều của
mảng.
Giả sử z,b,x,y được khai báo như trên, và giả sử i,j là các biến nguyên trong đó i=2,
J=1, khi đó:
a[j+i-1] là a[2]
b[j+i][2-i] là b[3][0]
y[i][j] là y[2][1]
Chú ý:
Mảng có bao nhiêu chiều thì ta phải viết bấy nhiêu chỉ số. vì thế nếu ta viết như sau sẽ
là sai: y[i]( vì y là mảng hai chiều),vv…
Biểu thức dung làm chỉ số có thể thực hiện. khi đó phần nguyên của biểu thức thực sẽ
là chỉ số mảng.
Ví dụ:
A[2.5] là a[2]
- 14
B[1.9] là a[1]
*Khi chỉ số vượt ra ngoài kích thước mảng, máy sẽ vẫn không báo lỗi, nhưng nó sẽ
truy cập đến một vùng nhớ bên ngoài mảng và có thể làm loạn chương trình.
2. Khái niệm về danh sách:
Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một
mối liên hệ nào đó.
Số phần tử của danh sách gọi là chiều dài của danh sách. Một danh sách có chiều
dài bằng 0 là một danh sách rỗng.
2.1. Danh sách liên kết (Linked List)
2.1.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ẫnnhau 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á
cthao 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.
2.1. Danh sách liên kết (Linked List)
2.1.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ẫnnhau 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á
cthao táctrê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.
2.1. Danh sch lin kết (Linked List)
2.1.1 Định nghĩa
- 15
Danh sch lin kết l tập hợp cc phần tử m giữa chng cĩ một sự nối kết với nhau
thơng qua vng lin kết của chng.
Sự nối kết giữa cc phần tử trong danh sch lin kết đĩ l sự quản lý,
rng buộc lẫnnhau về nội dung của phần tử ny v địa chỉ định vị phần tử kia. Ty thuộc v
o mức độv cch thức nối kết m danh sch lin kết cĩ
thể chia ra nhiều loại khc nhau:
- Danh sch lin kết đơn;
- Danh sch lin kết đơi/kp;
- Danh sch đa lin kết;
- Danh sch lin kết vịng (vịng đơn, vịng đơi).
Mỗi loại danh sch sẽ cĩ cch biểu diễn cc phần tử (cấu trc dữ liệu)ring v ccthao tc
trn đĩ. Trong ti liệu ny chng ta chỉ trình by 02 loại danh sch lin kết cơbản l danh sc
h lin kết đơn v danh sch lin kết đơi.
typedef SLL_OneNode * SLL_Type;
Để quản lý một danh sách liên kết chúng ta có thể sử dụng nhiều
phương pháp khácnhau và tương ứng với các phương pháp này
chúng ta sẽ có các cấu trúc dữ liệukhác nhau, cụ thể:
- Quản lý địa chỉ phần tử đầu danh sách:
SLL_Type SLList1;
Hình ảnh minh họa:
SLList1
N
ULL
15 10 20 18 40 35 30
- Quản lý địa chỉ phần tử đầu và cuối danh sách:
typedef struct SLL_PairNode
{ SLL_Type SLLFirst;
SLL_Type SLLLast;
} SLLP_Type;
SLLP_Type SLList2;
Hình ảnh minh họa:
SLLFirst SLLLast
NULL
15 10 20 18 40 35 30
- Quản lý địa chỉ phần tử đầu, địa chỉ phần tử cuối và số phần tử trong
danh sách:
typedef struct SLL_PairNNode
{ SLL_Type SLLFirst;
SLL_Type SLLLast;
unsigned NumNode;
} SLLPN_Type;
SLLPN_Type SLList3;
Hình aûnh minh hoïa:
- 16
SLLFirst SLLLast
NULL
15 10 20 18 40 35 30
NumNode = 7
B. Các thao tác trên danh sách liên kết đơn:
Với mỗi cách quản lý khác nhau của danh sách liên kết đơn , các
thao tác cũng sẽcó sự khác nhau về mặt chi tiết song nội dung cơ
bản ít có sự khác nhau. Do vậy, ơ đây chúng ta chỉ trình bày các
thao tác theo cách quản lý thứ nhất (quản lý địa chỉcủa phần tử
đầu danh sách liên kết đơn), các cách quản lý khác sinh viên tự
vận dụng để điều chỉnh cho thích hợ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ị con trỏ quản lý địa ch
ỉ phầntử đầ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;
Hình ảnh minh họa:
pNext
Kiểu dữ liệu Data Con trỏ kiểu Node
Ví dụ: Quản lý sinh vin
struct Data
{
int MaSV;
char HoTen[30];
};
b. Tạo mới một phần tử / nút:
Nút đầu, nút cuối:
+Phía sau nút cuối không có nút nào khác nên con trỏ pNext của nút cuối có giá trị
Null
+Nút đầu được quản lý bởi con trỏ pHead. Ta khai báo một cấu trúc List giữ con trỏ
pHead này
pHead NULL
struct Data
{ // Thuộc tính của data };
struct Node
{
Data info;
Node *pNext;
};
- 17
struct List
{
Node * pHead;
};
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à NewDa
ta vàotrong 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:
a) Thêm phần tử mới vào đầu danh sách
void ChenDau(List <, Data x)
{
Node* pNew = new Node;
pNew->Info= x;
pNew->pNext= lt.pHead;
lt.pHead= pNew;
}
void main()
{
Data x;
x.MaSV = 123;
strcpy(x.HoTen, “Nam”);
ChenDau(lop49, x);
}
a) Thêm phần tử mới vào cuối danh sách
- 18
void ChenCuoi(List <, Data x)
{
Node* pNew = new Node;
pNew->Info= x;
pNew->pNext= NULL;
if (lt.pHead==NULL) lt.pHead= pNew;
else{
Node* p = lt.pHead;
while (p->pNext!=NULL) p = p->pNext;
p->pNext = pNew;
}}
e. Tìm kieám moät phaàn töû trong danh saùch:
Thực hiện tìm tuần tự (LinearSearch)
Ví dụ: cần tìm một sinh viên có mã số là x
Node* TimKiem(List <, int x)
{
Node* p = lt.pHead;
while (p!=NULL)
{
if (p->info.MaSV == x) return p;
p = p->pNext;
}
return NULL;
g. Huûy danh saùch:
* Xóa phần tử đầu tiên trong danh sách:
p
Thực hiện tìm tuần tự (LinearSearch)
Ví dụ: cần tìm một sinh viên có mã số là x
Node* TimKiem(List <, int x)
{
Node* p = lt.pHead;
while (p!=NULL)
{
if (p->info.MaSV == x) return p;
- 19
p = p->pNext;
}
return NULL;
}
Xóa toàn bộ danh sách
Lần lượt xóa các phần tử đầu danh sách cho đến khi danh sách
trống
void XoaDanhSach()
{
Node* p;
while (lt.pHead!=NULL)
{
p = lt.pHead;
lt.pHead = p->pNext;
delete p;
}
}
k. 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 quacá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.
- Thuaät toaùn:
B1: NewList = NULL
B2: CurNode = SLList
B3: IF (CurNode = NULL)
Thöïc hieän Bkt
B4: SLL_Add_Last(NewList, CurNode->Key)
B5: CurNode = CurNode->NextNode
B6: Laëp laïi B3
Bkt: Keát thuùc
k. Sắp xếp thứ tự các phần tử trong danh sách:
nguon tai.lieu . vn
