BÀI GIẢNG
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1
LỜI NÓI

ĐẦU
Để đáp ứng nhu cầu học tập của các bạn sinh viên, nhất là sinh viên
chuyên ngành công nghệ thông tin, chuyên ngành tin học kinh tế, các tác giả
Bộ môn Công nghệ phần mềm - Khoa Công Nghệ Thông Tin - Trường
Đại học Thái nguyên chúng tôi đã tiến hành biên soạn các giáo trình,
bài giảng chính trong chương trình học đào tạo theo tín chỉ. Bài giảng môn
Cấu Trúc Dữ Liệu và thuật toán này được biên soạn cơ bản dựa trên
quyển: “Cấu trúc dữ liệu
&
thuật toán” của tác giả Đinh Mạnh Tường, Nhà
xuất bản Khoa học và Kỹ thuật, 2003. “Cấu trúc dữ liệu và giải thuật”, của
tác giả: Đỗ Xuân Lôi, “ Cấu trúc dữ liệu + giải thuật= Chương trình” của N.
Wirth, 1983. Giáo trình này cũng được biên soạn dựa trên kinh nghiệm
giảng dạy nhiều năm môn Cấu Trúc Dữ Liệu và Giải Thuật của chúng tôi.
Tài liệu này được soạn theo đề cương chi tiết môn Cấu Trúc Dữ
Liệu v à t h u ậ t t o á n của sinh viên chuyên ngành Công nghệ thông tin
của Khoa Công Nghệ Thông Tin Trường Đại Học Thái nguyên. Mục tiêu của
nó nhằm giúp các bạn sinh viên chuyên ngành có một tài liệu cô đọng dùng
làm tài liệu học tập, nhưng chúng tôi cũng không loại trừ toàn bộ các đối
tượng khác tham khảo. Chúng tôi nghĩ rằng các bạn sinh viên không
chuyên tin và những người quan tâm tới cấu trúc dữ liệu và giải thuật sẽ
tìm được trong này những điều hữu ích.
Mặc dù đã rất cố gắng nhiều trong quá trình biên soạn giáo trình nhưng
chắc chắn giáo trình sẽ còn nhiều thiếu sót và hạn chế. Rất mong nhận
được sự đóng góp ý kiến quý báu của sinh viên và các bạn đọc để bài
giảng ngày một hoàn thiện hơn và có thể trở thành một giáo trình thực sự

4. Thử nghiệm
Trong đó:
1) Phân tích để hình thành bài toán: Giai đoạn này ta phải trả lời rõ ràng các câu
hỏi: bài toán cho “ những cái gì?” và "phải làm những gì?"
Một bài toán được hình thành khi ta chỉ rõ các thông tin đầu vào ( input) và các
yêu cầu xử lý trên các thông tin đó (thông tin đầu ra (output))
2) Phân tích và thiết kế chương trình
Trong giai đoạn này ta cần trả lời câu hỏi: “ làm như thế nào” để biểu diễn
các đối tượng dữ liệu của bài toán và thực hiện các yêu cầu của bài toán trên máy tính.
Công việc này còn được gọi là xây dựng mô hình toán học cho bài toán.
4
Thật vậy, thông thường, khi khởi đầu, hầu hết các bài toán là không đơn giản,
không rõ ràng. Để giảm bớt sự phức tạp của bài toán thực tế, ta phải hình thức hóa
nó, nghĩa là phát biểu lại bài toán thực tế thành một bài toán hình thức (hay còn gọi
là mô hình toán học). Có thể có rất nhiều bài toán thực tế có cùng một mô hình toán
học.
Ví dụ 1: Tô màu bản đồ thế giới.
Ta cần phải tô màu cho các nước trên bản đồ thế giới. Trong đó mỗi nước đều
được tô một màu và hai nước láng giềng (cùng biên giới) thì phải được tô bằng hai
màu khác nhau. Hãy tìm một phương án tô màu sao cho số màu sử dụng là ít nhất.
Ta có thể xem mỗi nước trên bản đồ thế giới là một đỉnh của đồ thị, hai nước
láng giềng của nhau thì hai đỉnh ứng với nó được nối với nhau bằng một cạnh.
Bài toán lúc này trở thành bài toán tô màu cho đồ thị như sau: Mỗi đỉnh đều phải
được tô màu, hai đỉnh có cạnh nối thì phải tô bằng hai màu khác nhau và ta cần tìm
một phương án tô màu sao cho số màu được sử dụng là ít nhất. Mô hình toán học
được sử dụng trong bài toán này là mô hình đồ thị.
Ví dụ 2: Đèn giao thông
Cho một ngã năm như hình 1.1, trong đó C và E là các đường một chiều theo
chiều mũi tên, các đường khác là hai chiều. Hãy thiết kế một bảng đèn hiệu điều
khiển giao thông tại ngã năm này một cách hợp lý, nghĩa là: phân chia các lối đi

-
Các lối đi cho phép cùng đi đồng thời sẽ có cùng một màu: Dễ dàng nhận
thấy rằng hai đỉnh có cạnh nối nhau sẽ không được tô cùng màu.
- Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là
ít nhất. Tóm lại, ta phải giải quyết bài toán sau:
"Tô màu cho đồ thị ở hình 1.2 sao cho:
6
AB AC AD
BA BC
BD
DA DB DC
EA EB EC ED
Hình 1.2
- Hai đỉnh có cạnh nối với nhau (hai còn gọi là hai đỉnh kề nhau) không cùng
màu.
- Số màu được dùng là ít nhất."
Như vậy:
Cả hai bài toán trên, ban đầu có vẻ rất khác nhau, nhưng sau khi phân tích để hình
thức hóa thì chúng đều được đưa về mô hình toán học đồ thị, và áp dụng thuật toán tô
mầu trên đồ thị để giải quyết các bài toán này.
Chú ý: Có rất nhiều các cấu trúc toán học có thể làm mô hình dữ liệu trong tin học, ví
dụ dãy, tập hợp, ánh xạ, cây, đồ thị,
- Một bài toán thực tế bất kỳ thường 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 đó, cho nên trong giai đoạn phân tích và thiết kế, khi xây
dựng mô hình toán học cho bài toán cần chú trọng đến hai vấn đề :
+ Tổ chức biểu diễn các đối tượng dữ liệu của bài toán trong mô hình toán học
như thế nào? mô hình này ta còn gọi là mô hình dữ liệu
+ Xây dựng các thao tác xử lý trên đối tượng ra sao
Khi cài đặt chương trình giải quyết bài toán tương ứng ta quan tâm đến hai vấn đề:
+ Biểu diễn mô hình toán học của bài toán trên máy tính như thế nào để máy

diễn cụ thể của dữ liệu: Là biểu diễn xác định cách lưu trữ vật lý của
dữ liệu trong bộ nhớ máy tính. Biểu diễn cụ thể của dữ liệu được xác
định bởi các cấu trúc dữ liệu. Các cấu trúc dữ liệu được mô tả trong
ngôn ngữ lập trình cụ thể mà ta sử dụng
=> Dạng biểu diễn này phụ thuộc vào ngôn ngữ lập trình cụ thể
Từ biểu diễn trừu tượng, ta có thể chuyển dịch thành các biều diễn cụ thể khác
nhau, hay nói cách khác, từ các mô hình dữ liệu hoặc từ các kiểu dữ liệu trừu tượng, ta
có thể chuyển dịch thành các cấu trúc dữ liệu khác nhau. Ví dụ, ta có thể cài đặt danh
sách bởi cấu trúc dữ liệu mảng hoặc cấu trúc dữ liệu danh sách liên kết. Khi cài đặt
mô hình dữ liệu bởi cấu trúc dữ liệu nào đó, thì các phép tóa trên mô hình được thực
hiện bởi các thao tác cần thiết trên cấu trúc dữ liệu đó.
2) Về mặt xử lý dữ liệu: Giải thuật không hình thức ->giải thuật bằng ngôn ngữ giả
->Giải thuật được mã hóa hoàn toàn bởi ngôn ngữ lập trình cụ thể, ví dụ: Pascal, C,
Thật vây:
Từ những yêu cầu xử lý thực tế, ta tìm các giải thuật trên mô hình dữ liệu
đã xây dựng. Giải thuật có thể mô tả một cách không hình thức ( tức là nó chỉ
nêu phương hướng giải hoặc các bước giải một cách tổng quát).
Tiếp theo ta hình thức hoá giải thuật bằng ngôn ngữ giả, rồi chi tiết hoá dần
("mịn hoá") các bước giải tổng quát ở trên ( làm mịn dấn) . Ở bước này ta cần dùng các
kiểu dữ liệu trừu tượng (không phải là các khai báo cài đặt trong ngôn ngữ lập trình
cụ thể) và các cấu trúc lệnh điều khiển trong ngôn ngữ lập trình (không chú trọng đến
cú pháp ngôn ngữ) , kêt hợp ngôn ngữ tự nhiên để mô tả giải thuật.
8
Cuối cùng trong pha cài đặt, ta tiến hành mã hóa hoàn toàn giải thuật được mô
tả bởi ngôn ngữ giả, sử dụng ngôn ngữ lập trình cụ thể, thao tác trên cấu trúc dữ liệu
cụ thể.
1.2 Các khái niệm cơ bản
1.2.1 Mô hình dữ liệu ( Data model )
Mô hình dữ liệu là gì?: Mô hình dữ liệu được sử dụng để mô tả cấu trúc logic của dữ
liệu được xử lý bởi hệ thống. Là mô hình toán học cùng với các phép toán có thể thực

tử hậu bối (đứng ngay sau). Hình 1.3 biểu diễn một ví dụ về mô hình dữ liệu
tuyến tính.
2- Mô hình dữ liệu phân cấp (cây): có quan hệ 1:n giữa các phần tử; tức là, mỗi
phần tử trong mô hình có nhiều hậu bối, nhưng chỉ có một tiền bối. Hình 1.4 biểu diễn
một ví dụ cụ thể về mô hình này. Nếu ta di chuyển từ trên xuống dưới trong Hình 1.4
thì mỗi nút có thể trỏ đến nhiều nút khác, nhưng nếu ta di chuyển từ dưới lên thì mỗi
nút (trừ nút ở gốc) chỉ có quan hệ với 1 nút. Mô hình dữ liệu phân cấp như vậy thường
được gọi là cây, và đây là một loại mô hình dữ liệu quan trọng trong khoa học máy
tính:
10
Phần tử
cuối
Hình 1.3 – Mô hình dữ liệu tuyến tính
3 - Mô hình dữ liệu thứ ba là đồ thị: đây là mô hình dữ liệu phong phú và phức
tạp nhất. Trong đồ thị, các phần tử có mối quan hệ n:m. Tức là, mỗi phần tử có thể có
quan hệ với một hoặc nhiều phần tử khác. Hình 1.5 biểu diễn một ví dụ cụ thể về mô
hình này.
4 - Loại mô hình dữ liệu cuối cùng là tập hợp. Trong một tập hợp, các phần tử
không có mối quan hệ trực tiếp với nhau, giữa chúng chỉ có một mối quan hệ là thành
viên của tập hợp, ta không cần quan tâm tới vị trí chính xác của một phần tử nào đó
trong tập hợp. Hình 1.6 biểu diễn một ví dụ cụ thể về mô hình này.
11
Hình 1.4 – Mô hình dữ liệu phân cấp
Hình 1.5 – Mô hình dữ liệu đồ thị
Trên đây là bốn loại mô hình dữ liệu mà ta sẽ nghiên cứu. Ta cũng sẽ nghiên cứu
các dạng biểu diễn của các mô hình này bởi các cấu trúc dữ liệu khác nhau trong pha
cài đặt chương trình. Nói chung, hầu hết các cấu trúc dữ liệu đều rơi vào một trong
bốn dạng cơ bản này.
1.2.2. Khái niệm trừu tượng hóa
Trong tin học, trừu tượng hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn

tính chất đặc trưng cho các đối tượng thuộc phạm vi bài toán đang xét)
Ví dụ: Ứng với các dữ liệu dạng số, tương ứng ta có các kiểu dữ liệu số
nguyên, số thực, số phức, … trong ngôn ngữ lập trình,
+ Như vậy tất cả các dữ liệu mô tả trong ngôn ngữ lập trình bậc cao được máy tính xử
lý đu phải thuộc một kiểu dữ liệu xác định.
1.2.6 Kiểu dữ liệu
Kiểu dữ liệu T được xác định bởi một bộ <V,O> , với :
V : tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ
O : tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T.
Ví du: Giả sử có kiểu dữ liệu mẫu tự = <Vc ,Oc> với
Vc = { a-z,A-Z}
Oc

= { lấy mã ASCII của ký tự, biến đổi ký tự
thường thành ký tự hoa…}
Giả sử có kiểu dữ liệu số nguyên = <Vi ,Oi> với
Vi = { -32768 32767}
13
Dữ liệu
Dữ liệu vào: Các đối tượng cần xử lý của bài toán
Kết quả trung gian
Dữ liệu đầu ra: Kết quả xử lý
Oi

= { +, -, *, /, %}
Như vậy: muốn sử dụng một kiểu dữ liệu trong cài đặt cần nắm vững các thuộc tính
của kiểu dữ liệu đó. Các thuộc tính của 1 kiểu dữ liệu bao gồm:
• Tên kiểu dữ liệu: Từ khóa thể hiện cho kiểu đó
• Miền giá trị: Một biến có kiểu dữ liệu đó có thể nhận các giá trị trong phạm vi
nào

- Tên sinh viên: chuỗi ký tự
- Ngày sinh: kiểu ngày tháng
- Nơi sinh: chuỗi ký tự
- Điểm thi: số nguyên
Các kiểu dữ liệu cơ sở cho phép mô tả một số thông tin như :
Diemthi: integer;
Các thông tin khác đòi hỏi phải sử dụng các kiểu có cấu trúc như :
Masv: string[15];
Tensv: string[15];
Noisinh: String[15];
Để thể hiện thông tin về ngày tháng năm sinh cần phải xây dựng một kiểu dữ liệu có
cấu trúc bản ghi,
Type Date = record
Ngay: byte;
Thang: byte;
Năm: integer;
End;
Cuối cùng, ta có thể xây dựng kiểu dữ liệu có cấu trúc thể hiện thông tin về một sinh
viên :
Type SinhVien = Record
Masv: String[15];
Tensv: String[15];
Noisinh: String[15];
Diem thi: Integer;
Ngaysinh: Date
End;
Giả sử đã có cấu trúc phù hợp để lưu trữ một sinh viên, nhưng thực tế lại cần
quản lý nhiều sinh viên, lúc đó nảy sinh nhu cầu xây dựng kiểu dữ liệu có cấu trúc
mới, ví dụ danh sách hoặc mảng
Mục tiêu của việc nghiên cứu cấu trúc dữ liệu chính là tìm những phương cách

giải thuật, cụ thể là 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ớ
16
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.
3 - 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 viết chương trình. Nếu cần một chương trình có tốc độ 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 integer (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 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 30, 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ụ danh sách
liên kết – ta sẽ đề cập đến trong các tiếp theo.
Như vậy:
Kiểu dữ liệu phức, hay còn gọi là cấu trúc dữ liệu, là kiểu dữ liệu trong đó các phần
tử của nó có thể phân tách thành các kiểu dữ liệu đơn hoặc kiểu dữ liệu phức khác. Ví
dụ, kiểu dữ liệu phức trong Pascal bao gồm: array và record.

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 chương trình máy tính, 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 bộ nhớ, giải thuật cũng dễ hiễu và đơn giản hơn.
* Cấu trúc lưu trữ ( Storange structures)
+ CTDL được biểu diễn trong bộ nhớ máy tính còn được gọi là Cấu trúc lưu
trữ
18
+ CTDL được
lưu trữ ở:
Bộ nhớ trong còn gọi là cấu trúc lưu trữ trong, ví dụ:
Mảng, danh sách kế tiếp, ….,
Bộ nhớ ngoài còn gọi là cấu trúc lưu trữ ngoài, ví
dụ: Tệp tin, bảng,….
1.3 Ngôn ngữ diễn đạt giải thuật
- Là công cụ trung gian giúp giao tiếp giữa người và MTĐT.
- Mỗi ngôn ngữ lập trình có một hệ kiểu, trong đó có một số là kiểu dữ liệu đơn hay
nguyên tử, một số là các cấu trúc dữ liệu bao gồm các kiểu đơn.
- Ngôn ngữ diễn đạt giải thuật bao gồm một tập hợp các câu lệnh tuân theo một cú
pháp nhất định. Thông qua các câu lệnh mà MT có thể hiểu và thực hiện những công
việc mà người dùng muốn MT làm
=> Ta sử dụng công cụ này để diễn đạt giải thuật.

{dict1, dict2 là 2 đầu mối có thể truy cập được vào đầu trước và đầu sau của từ điển }
2) Return
b) Đặc điểm của thủ tục đệ quy
+ Trong thủ tục đệ quy có lời gọi đến chính nó.
+ Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước
+ Có một trường hợp đặc biệt, trường hợp suy biến: Bài toán sẽ được giải
quyết theo một cách khác hẳn và gọi đệ quy cũng kết thúc.
Đệ quy gồm : Đệ quy trực tiếp (thủ tục chứa lời gọi đến chính nó) và đệ quy gián tiếp
(thủ tục chứa lời gọi đến thủ tục khác mà thủ tục này lại chứa lời gọi đến chính nó )
Tóm lại
Mặc dù các thuật ngữ kiểu dữ liệu (hay kiểu - data type), cấu trúc dữ liệu (data
structure), kiểu dữ liệu trừu tượng (abstract data type), mô hình dữ liệu (data model)
nghe có vẻ như nhau, nhưng chúng có ý nghĩa rất khác nhau.
Kiểu dữ liệu: là một tập hợp các giá trị và một tập hợp các phép toán trên các giá
trị đó. Ví dụ kiểu Boolean là một tập hợp có 2 giá trị TRUE, FALSE và các phép
toán trên nó như OR, AND, NOT …. Kiểu Integer là tập hợp các số nguyên có giá
trị từ -32768 đến 32767 cùng các phép toán cộng, trừ, nhân, chia, Div, Mod…
Kiểu dữ liệu có hai loại là kiểu dữ liệu sơ cấp và kiểu dữ liệu có cấu trúc hay
còn gọi là cấu trúc dữ liệu.
Kiểu dữ liệu cơ sở : là kiểu dữ liệu mà giá trị dữ liệu của nó là đơn nhất. Ví
dụ: kiểu Boolean, Integer….
Kiểu dữ liệu có cấu trúc hay còn gọi là cấu trúc dữ liệu: là kiểu dữ liệu mà
giá trị dữ liệu của nó là sự kết hợp của các giá trị khác. Ví dụ: ARRAY là một cấu
trúc dữ liệu.
Một kiểu dữ liệu trừu tượng: là một mô hình dữ liệu cùng với một tập hợp các
phép toán điển hình trên nó. Có thể nói kiểu dữ liệu trừu tượng là một kiểu dữ liệu
do chúng ta định nghĩa ở mức khái niệm (conceptual), nó chưa được cài đặt cụ thể
bằng một ngôn ngữ lập trình.
Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn gnữ lập trình cụ thể, chúng
20

+ Nếu n=0 ta nói danh sách rỗng (empty list).
+ Nếu n > 0 ta gọi a
1
là phần tử đầu tiên và a
n
là phần tử cuối cùng của danh
sách.
+ Số phần tử của danh sách ta gọi là độ dài của danh sách.
+ Một tính chất quan trọng của danh sách đó là tính tuyến tính: Các phần tử của
danh sách có thứ tự tuyến tính theo vị trí (position) xuất hiện của các phần tử.
Ta nói a
i
đứng trước a
i+1
, với i từ 1 đến n-1; Tương tự ta nói a
i
là phần tử
đứng sau a
i-1
, với i từ 2 đến n. Ta cũng nói a
i
là phần tử tại vị trí thứ i, hay
phần tử thứ i của danh sách.
Ví dụ: Tập hợp họ tên các sinh viên của lớp TINHOC được liệt kê trên giấy như sau:
1. Nguyễn Trung Cang
2. Nguyễn Ngọc Chương
3. Lê Thị Lệ Sương
22
4. Trịnh Vũ Thành
5. Nguyễn Phú Vĩnh

,. . , a
n
thì sau khi xen ta có kết quả a
1
, a
2
, . . ., a
p-1
, x,
a
p
, . . . , a
n
. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được xác
định.
2) Tìm vị trí của một phần tử trong danh sách
LOCATE(x,L) thực hiện việc xác định vị trí phần tử có nội dung x đầu tiên trong
danh sách L. Locate trả kết quả là vị trí của phần tử x trong danh sách. Nếu x
không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách
được trả về, tức là ENDLIST(L).
3) Lấy giá trị của phần tử ở vị trí nào đó
RETRIEVE(p,L) lấy giá trị của phần tử ở vị trí p của danh sách L; nếu vị trí p
không có trong danh sách thì kết quả không xác định (có thể thông báo lỗi).
4) Xoá một phần tử ở vị trí nào đó trong danh sách
DELETE_LIST(p,L): xoá phần tử ở vị trí p trong danh sách L. Nếu vị trí p
không có trong danh sách thì phép toán không được định nghĩa và danh sách L sẽ
không thay đổi
23
5) Tìm vị trí của phần tử đứng sau phần tử có vị trí xác đinh
LINK(p,L) cho kết quả là vị trí của phần tử đi sau phần tử p; nếu p là phần tử cuối

? Muốn thêm 1 phần tử vào

đầu hay cuối danh sách ta cần gọi các phép toán nào và gọi các
phép toán

đó như thế nào?
2.1.3.1 Danh sách cài đặt bằng mảng
Cài đặt danh sách bởi mảng hay còn gọi là cấu trúc dữ liệu danh sách đặc, hoặc
cấu trúc dữ liệu danh sách kế tiếp, gọi tắt là: Danh sách đặc, hoặc danh sách kế tiếp, nó
thuộc loại cấu trúc dữ liệu tĩnh
a) Mô tả cài đặt :

- Giá sử N là số phân tử tối đa trong danh sách: Với cách cài đặt này, dĩ nhiên,
ta phải ước lượng số phần tử tối đa của danh sách để khai báo số phần tử của
mảng cho thích hợp. Dễ thấy rằng số phần tử của mảng phải được khai báo
lớn hơn số phần tử của danh sách. Nói chung là mảng còn thừa một số chỗ
trống, giả sử Item: Là kiểu dữ liệu của các phần tử trong danh sách
- Dùng một mảng để lưu giữ các phần tử của danh (giả sử mảng Elements).
- Count là một biến đếm đếm số lượng phần tử hiện có trong danh sách
Như vậy ta có thể định nghĩa danh sách như một cấu trúc bản ghi gồm 2 trường:
Elements: Chứa các phần tử trong danh sách
Count: Đếm số phần tử hiện có trong danh sách (chiều dài danh sách)
=> Khi đó mảng chứa các phần tư trong danh sách có dạng như sau
chỉ số
mảng(vị trí
phần tử)
1 2 …. count …. n
Nội dung
phần tử
Phần