Giáo trình Cấu trúc dữ liệu - Trường Đại học Hàng Hải
BỘ GIAO THÔNG VẬN TẢI
TRƢỜNG ĐẠI HỌC HÀNG HẢI
́ ́
BỘ MÔN: KHOA HOC MAY TINH
̣
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
CẤU TRÚC DỮ LIỆU
TÊN HỌC PHẦN : CẤU TRÚC DỮ LIỆU
MÃ HỌC PHẦN : 17207
TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2008
MỤC LỤC
CHƢƠNG 1. CÁC KHÁI NIỆM MỞ ĐẦU .............................................................................. 1
1.1. Giải thuật và cấu trúc dữ liệu..........................................................................................1
1.2. Cấu trúc dữ liệu và các vấn đề liên quan. .......................................................................1
1.3. Ngôn ngữ diễn đạt giải thuật...........................................................................................2
1.4. Kiểu dữ liệu, cấu trúc dữ liệu, kiểu dữ liệu trừu tƣợng...................................................3
2. 1. Ngăn xếp - Stack............................................................................................................6
2.1.1 Khái niệm .................................................................................................................. 6
2.1.2 Các thao tác cꢀa ngăn xꢁp ......................................................................................... 6
2.1.3 Vꢂ dꢃ về hoạt động cꢀa một stack ............................................................................. 7
2.1.4 Cài đꢄt stack bꢅng mảng............................................................................................ 7
2.1.5 ꢆng dꢃng cꢀa stack ................................................................................................. 10
2.2. Hàng đợi - Queue..........................................................................................................12
2.2.1 Khái niệm ................................................................................................................ 12
2.2.2 Các thao tác cơ bản cꢀa một hàng đợi..................................................................... 13
2.2.3 Cài đꢄt hàng đợi sꢇ dꢃng mảng ............................................................................... 13
t – Linked list....................................................................................17
h nghia ............................................................................................................... 17
2.3.3 Cài đꢄt danh sách liên kꢁt sꢇ dꢃng con trꢊ .............................................................. 18
2.3.4 Các kiểu danh sách liên kꢁt khác............................................................................. 25
2.3.5 Môt số vi du sƣ dung cấu truc danh sach liên kết.................................................... 26
2.3.6. Cài đꢄt stack và queue bꢅng con trꢊ ....................................................................... 26
2.4. Bài tập áp dꢃng .............................................................................................................26
CHƢƠNG 3. CÂY (TREE)...................................................................................................... 28
3.1. Đinh nghꢋa.....................................................................................................................28
3.1.1. Đꢌ thꢍ (Graph) ........................................................................................................ 28
3.1.2. Cây (tree)................................................................................................................ 29
h nghia .............................................................................................................. 31
cây rông ................................................................................................... 32
3.3.3. Chꢎn thêm một nút mꢈi vào cây............................................................................. 32
3.3.4. Xꢏa bꢊ khꢊi cây một nút ........................................................................................ 33
3.3.5. Tꢐm kiꢁm trên cây................................................................................................... 34
3.3.6. Duyêt cây................................................................................................................ 35
3.3.7. Cài đꢄt cây BST...................................................................................................... 36
3.4.Cây cân bꢅng – AVL .....................................................................................................39
CHƢƠNG 4. BẢNG BĂM (HASH TABLE).......................................................................... 54
4. 1. Đꢍnh nghꢋa bảng băm...................................................................................................54
4.1.1.Đꢍnh nghꢋa : ............................................................................................................. 54
4.1.2.Kꢂch thƣꢈc cꢀa bảng băm :...................................................................................... 55
4.1.3. Phân loại :............................................................................................................... 55
4.1.4.Các phép toán trên bảng băm : ................................................................................ 57
4.2.Hàm băm và các loại hàm băm :....................................................................................57
4.2.1.Hàm băm (Hash Function): ..................................................................................... 57
4.2.2.Một số loại hàm băm :............................................................................................. 58
i
4.3.Xung đột và cách xꢇ lý xung đột...................................................................................61
4.3.1. Đꢍnh nghꢋa : ............................................................................................................ 61
4.3.2.Hệ số tải (Load Factor - ) : .................................................................................... 61
4.3.3.Một số phƣơng pháp xꢇ lý xung đột : ..................................................................... 61
4.3.4. Đánh giá : ............................................................................................................... 71
4.4.4.Kꢁt luận :.....................................................................................................................72
4.5. Bài tập áp dꢃng .............................................................................................................72
TÀI LIỆU THAM KHẢO........................................................................................................ 75
ii
Tên học phần: Cấu trúc dữ liệu
Bộ môn phụ trách giảng dạy: Khoa học Máy tꢂnh
Mã học phần: 17207
Loại học phần: 2
Khoa phụ trách: CNTT
Tổng số TC: 3
TS tiꢁt Lý thuyꢁt Thực hành/Xemina Tự học Bài tập lꢈn
Đꢌ án môn học
60
30
30
0
0
0
Điều kiện tiên quyết:
Sinh viên phải học xong các học phần sau mꢈi đƣợc đăng ký học phần này:
Toán cao cấp, Toán rời rạc, Ngôn ngữ C, Tin học đại cƣơng.
Mục tiêu của học phần:
Cung cấp kiꢁn thức và rꢎn luyện kỹ năng thực hành cấu trúc dữ liệu cho sinh viên.
Nội dung chủ yếu
- Những vấn đề cơ bản về cấu trúc dữ liệu;
- Các cấu trúc dữ liệu cơ bản
- Danh sách liên kꢁt;
- Ngăn xꢁp, hàng đợi;
- Cấu trúc cây;
- Bảng băm, ...
Nội dung chi tiết của học phần:
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
TÊN CHƢƠNG MỤC
Chƣơng I : Khái niệm liên quan đến CTDL
1.1. Giải thuật và cấu trúc dữ liệu.
1.2. Giải thuật và các vấn đề liên quan.
1.3. Ngôn ngữ diễn đạt giải thuật.
1.4. Kiểu dữ liệu, cấu trúc dữ liệu, kiểu dữ liệu trừu
tƣợng.
KT
2
2
0
12
6
6
Chƣơng II : Các kiểu dữ liệu trừu tƣợng cơ bản
2.1. Danh sách
2.1.1. Khái niệm danh sách
2.1.2. Các phép toán trên danh sách
2.1.3. Cài đꢄt danh sách
2.1.4. Các dạng danh sách liên kꢁt (DSLK): DSLK
đơn, vꢉng, kép, …
2.2. Ngăn xꢁp (stack)
2.2.1. Khái niệm
2.2.2. Cài đꢄt ngăn xꢁp bởi mảng, DSLK
2.2.3. ꢆng dꢃng
2.3. Hàng đợi (queue)
2.3.1. Khái niệm
2.3.2. Cài đꢄt hàng đợi bởi mảng, DSLK
2.3.3. ꢆng dꢃng
2.4. Bài tập áp dꢃng
18
9
8
1
Chƣơng III: Cây (tree).
3.1. Khái niệm.
3.2. Cây tổng quát.
iii
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
TÊN CHƢƠNG MỤC
3.2.1. Biểu diễn cây tổng quát.
KT
3.2.2. Duyệt cây tổng quát.
3.2.3. Vài vꢂ dꢃ áp dꢃng.
3.3. Cây nhꢍ phân.
3.3.1. Đꢍnh nghꢋa và tꢂnh chất
3.3.2. Lƣu trữ cây.
3.3.3. Duyệt cây.
3.3.4. Cây nhꢍ phân nối vꢉng.
3.4. Các phép toán thực hiện trên cây nhꢍ phân.
3.4.1. Dựng cây
3.4.2. Duyệt cây để tꢐm kiꢁm
3.4.3. Sắp xꢁp cây nhꢍ phân
3.5. Cây tꢐm kiꢁm nhꢍ phân (binary search tree)
3.5.1. Khái niệm, cài đꢄt.
3.5.2. Cây AVL
3.6. Bài tập
14
7
6
1
Chƣơng IV: Bảng băm (hash table)
4.1. Khái niệm
4.2. Các loại hàm băm
4.3. Các phƣơng pháp giải quyꢁt xung đột
4.4. Đánh giá hiệu quả các phƣơng pháp băm
4.5. Bài tập áp dꢃng
Nhiệm vụ của sinh viên :
Tham dự các buổi thuyꢁt trꢐnh cꢀa giáo viên, tự học, tự làm bài tập do giáo viên giao,
tham dự các bài kiểm tra đꢍnh kỳ và cuối kỳ.
Tài liệu học tập :
1. Đinh Mạnh Tƣờng, Cấu trúc dữ liệu và thuật toán, Nhà xuất bản ĐH QG Hà Nội,
2004.
2. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản ĐH QG Hà Nội, 2004.
3. Robert Sedgewick, Cẩm nang thuật toán, NXB Khoa học kỹ thuật, 2000.
Hình thức và tiêu chuẩn đánh giá sinh viên:
-
-
Hꢐnh thức thi cuối kỳ : Thi viꢁt.
Sinh viên phải đảm bảo các điều kiện theo Quy chꢁ cꢀa Nhà trƣờng và cꢀa Bộ
Thang điểm: Thang điểm chữ A, B, C, D, F
Điểm đánh giá học phần: Z = 0,3X + 0,7Y.
Bài giảng này là tài liệu chính thức và thống nhất cꢀa Bộ môn Khoa học máy tꢂnh,
Khoa Công nghệ thông tin và đƣợc dùng để giảng dạy cho sinh viên.
Ngày phê duyệt:
/
/20
Trƣởng Bộ môn: ThS. Nguyễn Hữu Tuân (ký và ghi rõ họ tên)
iv
CHƢƠNG 1. CÁC KHÁI NIỆM MỞ ĐẦU
1.1. Giải thuật và cấu trúc dữ liệu.
Ðể giải một bài toán trong thực tꢁ bꢅng máy tꢂnh ta phải bắt đầu từ việc xác đꢍnh bài
toán. Nhiều thời gian và công sức bꢊ ra để xác đꢍnh bài toán cần giải quyꢁt, tức là phải trả lời
rõ ràng câu hꢊi "phải làm gꢐ?" sau đꢏ là "làm nhƣ thꢁ nào?". Thông thƣờng, khi khởi đầu, hầu
hꢁt các bài toán là không đon 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). Cꢏ thể cꢏ rất nhiều bài toán thực tꢁ cꢏ cùng một mô hình
toán.
Vꢂ dꢃ : 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.
Ðối vꢈi một bài toán đã đƣợc hꢐnh thức hoá, chúng ta cꢏ thể tꢐm kiꢁm cách giải trong
thuật ngữ cꢀa mô hꢐnh đꢏ và xác đꢍnh cꢏ hay không một chƣong trꢐnh cꢏ sẵn để giải. Nꢁu
không cꢏ một chƣơng trꢐnh nhƣ vậy thꢐ ꢂt nhất chúng ta cũng cꢏ thể tꢐm đƣợc những gꢐ đã biꢁt
về mô hꢐnh và dùng các tꢂnh chất cꢀa mô hꢐnh để xây dựng một giải thuật tốt.
Khi đã cꢏ mô hꢐnh thꢂch hợp cho một bài toán ta cần cố gắng tꢐm cách giải quyꢁt bài
toán trong mô hꢐnh đꢏ. Khởi đầu là tꢐm một giải thuật, đꢏ là một chƣỗi hữu hạn các chỉ thꢍ
(instruction) mà mỗi chỉ thꢍ cꢏ một ý nghꢋa rõ ràng và thực hiện đƣợc trong một lƣợng thời
gian hữu hạn.
Nhƣng xét cho cùng, giải thuật chỉ phản ánh các phép xꢇ lý, cꢉn đꢏi tƣợng để xꢇ lý
trong máy tꢂnh chꢂnh là dữ liệu (data ), chúng biểu diễn các thông tin cần thiꢁt cho bài toán:
các dữ liệu vào, các dữ liệu ra, dữ liệu trung gian, … Không thể nꢏi tꢈi giải thuật mà không
nghꢋ tꢈi: giải thuật đꢏ đƣợc tác động trên dữ liệu nào, cꢉn xét tꢈi dữ liệu thꢐ phải biꢁt dữ liệu
ấy cần đƣợc giải thuật gꢐ tác động để đƣa ra kꢁt quả mong muốn.. Nhƣ vậy, giữa cấu trúc dữ
liệu và giải thuật cꢏ mối liên quan mật thiꢁt vꢈi nhau.
1.2. Cấu trúc dữ liệu và các vấn đề liên quan.
Trong một bài toán, dữ liệu bao gꢌm một tập các phần tꢇ cơ sở, đƣợc gọi là dữ liệu
nguyên tꢇ. Dữ liệu nguyên tꢇ cꢏ thể là một chữ số, một ký tự, … cũng cꢏ thể là một số, một
xâu, … tùy vào bài toán. Trên cơ sở các dữ liệu nguyên tꢇ, các cung cách khả dꢋ theo đꢏ lien
kꢁt chúng lại vꢈi nhau, sẽ đãn đꢁn các cấu trúc dữ liệu khác nhau.
Lựa chọn một cấu trúc dữ liệu thꢂch hợp để tổ chức dữ liệu vào và trên cơ sở đꢏ xây
dựng đƣợc giải thuật xꢇ lý hữu hiệu đƣa tꢈi kꢁt quả mong muốn cho bài toán (dữ liệu ra), là
một khâu quan trọng.
Cách biểu diễn một cấu trúc dữ liệu trong bộ nhꢈ đƣợc gọi là cấu trúc lƣu trữ. Đây chꢂnh
là cách cài đꢄt cấu trúc ấy trên máy tꢂnh và trên cơ sở các cấu trúc lƣu trữ này mà thực hiện
các phép xꢇ lý. Cꢏ thể cꢏ nhiều cấu trúc lƣu trữ khác nhau cho cùng một cấu trúc dữ liệu và
ngƣợc lại.
Khi đề cập tꢈi cấu trúc lƣu trũ, cần phân biệt: cấu trúc lƣu trữ tƣơng ứng vꢈi bộ nhꢈ
trong – lƣu trữ trong; cấu trúc lƣu trữ ứng vꢈi bộ nhꢈ ngoài – lƣu trữ ngoài. Chúng cꢏ đꢄc
điểm và cách xꢇ lý riêng.
1
1.3. Ngôn ngữ diễn đạt giải thuật.
Việc sꢇ dꢃng một ngôn ngữ lập trꢐnh bậc cao để diễn đạt giải thuật, nhƣ Pascal, C, C++,
… sẽ gꢄp một số hạn chꢁ sau:
- Phải luôn tuân thꢀ các quy tắc chꢄt chẽ về cú pháp cꢀa ngôn ngữ khiꢁn cho việc trꢐnh
bày về giải thuật và cấu trúc dữ liệu cꢏ thiên hƣꢈng nꢄng nề, gꢉ bꢏ.
- Phải phꢃ thuộc vào cấu trúc dữ liệu tiền đꢍnh cꢀa ngôn ngữ nên cꢏ lúc không thể hiện
đƣợc đầy đꢀ các ý về cấu trúc mà ta muỗn biểu đạt
Một khi đã cꢏ mô hình thích hợp cho bài toán, ta cần hꢐnh thức hoá một giải thuật, một
cấu trúc dữ liệu trong thuật ngữ cꢀa mô hꢐnh đꢏ. Khởi đầu là viꢁt những mệnh đề tổng quát
rꢌi tinh chꢁ dần thành những chuỗi mệnh đề cꢃ thể hơn, cuối cùng là các chỉ thꢍ thꢂch hợp
trong một ngôn ngữ lập trꢐnh.
Ở bƣꢈc này, nꢏi chung, ta cꢏ một giải thuật, một cấu trúc dữ liệu tƣơng đꢏi rõ ràng, nꢏ
gần giống nhƣ một chƣơng trꢐnh đƣợc viꢁt trong ngôn ngữ lập trꢐnh, nhƣng nꢏ không phải là
một chƣơng trꢐnh chạy đƣợc vꢐ trong khi viꢁt giải thuật ta không chú trọng nꢄng đꢁn cú pháp
cꢀa ngôn ngữ và các kiểu dữ liệu cꢉn ở mức trừu tƣợng chứ không phải là các khai báo cài đꢄt
kiểu trong ngôn ngữ lập trꢐnh.
Chẳng hạn vꢈi giải thuật tô màu đꢌ thꢍ GREEDY, giả sꢇ đꢌ thꢍ là G, giải thuật sẽ xác
đꢍnh một tập hợp Newclr các đỉnh cꢀa G đƣợc tô cùng một màu, mà ta gọi là màu mꢈi C ở
trên. Ðể tiꢁn hành tô màu hoàn tất cho đꢌ thꢍ G thꢐ giải thuật này phải đƣợc gọi lꢄp lại cho đꢁn
khi toàn thể các đỉnh đều đƣợc tô màu.
void GREEDY ( GRAPH *G, SET *Newclr )
{
Newclr = ; /*1*/
for (mỗi đỉnh v chƣa tô màu cꢀa G) /*2*/
if (v không đƣợc nối vꢈi một đỉnh nào trong Newclr) /*3*/
{
đánh dấu v đã đƣợc tô màu; /*4*/
thêm v vào Newclr; /*5*/
}
}
Trong thꢀ tꢃc bꢅng ngôn ngữ giả này chúng ta đã dùng một số từ khoá cꢀa ngôn ngữ C
xen lẫn các mệnh đề tiꢁng Việt. Ðiều đꢄc biệt nữa là ta dùng các kiểu GRAPH, SET cꢏ vẻ xa
lạ, chúng là các "kiểu dữ liệu trừu tƣợng" mà sau này chúng ta sẽ viꢁt bꢅng các khai báo thích
hợp trong ngôn ngữ lập trꢐnh cꢃ thể. Dꢋ nhiên, để cài đꢄt thꢀ tꢃc này ta phải cꢃ thể hoá dần
những mệnh đề bꢅng tiꢁng Việt ở trên cho đꢁn khi mỗi mệnh đề tƣơng ứng vꢈi một doạn mã
thꢂch hợp cꢀa ngôn ngữ lập trꢐnh. Chẳng hạn mệnh đề if ở /*3*/ cꢏ thể chi tiꢁt hoá hơn nữa
nhƣ sau:
void GREEDY ( GRAPH *G, SET *Newclr )
{
Newclr= ; /*1*/
for (mỗi đỉnh v chƣa tô màu cꢀa G) /*2*/
{
int found=0; /*3.1*/
for (mỗi đỉnh w trong Newclr) /*3.2*/
if (cꢏ cạnh nối giữa v và w) /*3.3*/
found=1; /*3.4*/
if (found==0)/*3.5*/
{
đánh dấu v đã đƣợc tô màu; /*4*/
thêm v vào Newclr; /*5*/
}
2
}
}
GRAPH và SET ta coi nhƣ tập hợp. Cꢏ nhiều cách để biểu diễn tập hợp trong ngôn ngữ
lập trꢐnh, để đơn giản ta xem các tập hợp nhƣ là một danh sách (LIST) các số nguyên biểu
diễn chỉ số cꢀa các đỉnh và kꢁt thúc bꢅng một giá trꢍ đꢄc biệt NULL. Vꢈi những qui ƣꢈc nhƣ
vậy ta cꢏ thể tinh chꢁ giải thuật GREEDY một bƣꢈc nữa nhƣ sau:
void GREEDY ( GRAPH *G, LIST *Newclr )
{
int found;
int v,w ;
Newclr= ;
v= đỉnh đầu tiên chƣa đƣợc tô màu trong G;
while (v<>null)
{
found=0;
w=đỉnh đầu tiên trong newclr;
while( w<>null) && (found=0)
{
if ( cꢏ cạnh nối giữa v và w )
found=1;
else w= đỉnh kꢁ tiꢁp trong newclr;
}
if (found==0 )
{
Ðánh dấu v đã đƣợc tô màu;
Thêm v vào Newclr;
}
v= đỉnh chƣa tô màu kꢁ tiꢁp trong G;
}
}
1.4. Kiểu dữ liệu, cấu trúc dữ liệu, kiểu dữ liệu trừu tƣợng
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 và dễ hiểu
hơn. Cꢃ thể trừu tƣợng hꢏa là che di những chi tiꢁt, làm nổi bật cái tổng thể. Trừu tƣợng hꢏa
cꢏ thể thực hiện trên hai khꢂa cạnh là trừu tƣợng hꢏa dữ liệu và trừu tƣợng hꢏa chƣơng trꢐnh.
Trừu tƣợng hóa chƣơng trình
Trừu tƣợng hꢏa chƣơng trꢐnh là sự đꢍnh nghꢋa các chƣơng trꢐnh con để tạo ra các phép
toán trừu tƣợng (sự tổng quát hꢏa cꢀa các phép toán nguyên thꢀy). Chẳng hạn ta cꢏ thể tạo ra
một chƣơng trꢐnh con Matrix_Mult để thực hiện phép toán nhân hai ma trận. Sau khi
Matrix_mult đã đƣợc tạo ra, ta cꢏ thể dùng nꢏ nhƣ một phép toán nguyên thꢀy (chẳng hạn
phép cộng hai số).
Trừu tƣợng hꢏa chƣơng trꢐnh cho phép phân chia chƣơng trꢐnh thành các chƣơng trꢐnh
con. Sự phân chia này sẽ che dấu tất cả các lệnh cài đꢄt chi tiꢁt trong các chƣơng trꢐnh con. Ở
cấp độ chƣơng trꢐnh chꢂnh, ta chỉ thấy lời gọi các chƣơng trꢐnh con và điều này đƣợc gọi là sự
bao gói.
Vꢂ dꢃ nhƣ một chƣơng trꢐnh quản lý sinh viên đƣợc viꢁt bꢅng trừu tƣợng hꢏa cꢏ thể
là:
void main()
{
Nhap(Lop);
3
Xu_ly (Lop);
Xuat (Lop);
}
Trong chƣơng trꢐnh trên, Nhap, Xu_ly, Xuat là các phép toán trừu tƣợng. Chúng che dấu
bên trong rất nhiều lệnh phức tạp mà ở cấp độ chƣơng trꢐnh chꢂnh ta không nhꢐn thấy đƣợc.
Cꢉn Lop là một biꢁn thuộc kiểu dữ liệu trừu tƣợng mà ta sẽ xét sau.
Chƣơng trꢐnh đƣợc viꢁt theo cách gọi các phép toán trừu tƣợng cꢏ lệ thuộc vào cách
cài đꢄt kiểu dữ liệu không?
Trừu tƣợng hóa dữ liệu
Trừu tƣợng hꢏa dữ liệu là đꢍnh nghꢋa các kiểu dữ liệu trừu tƣợng
Một kiểu dữ liệu trừu tƣợng là một mô hình toán học cùng với một tập hợp các phép
toán (operator) trừu tƣợng đƣợc định nghĩa trên mô hình đó. Vꢂ dꢃ tập hợp số nguyên cùng
vꢈi các phép toán hợp, giao, hiệu là một kiểu dữ liệu trừu tƣợng.
Trong một ADT các phép toán cꢏ thể thực hiện trên các đꢏi tƣợng (toán hạng) không chỉ
thuộc ADT đꢏ, cũng nhƣ kꢁt quả không nhất thiꢁt phải thuộc ADT. Tuy nhiên, phải cꢏ ꢂt nhất
một toán hạng hoꢄc kꢁt quả phải thuộc ADT đang xét.
ADT là sự tổng quát hoá của các kiểu dữ liệu nguyên thƣỷ.
Ðể minh hoạ ta cꢏ thể xét bản phác thảo cuối cùng cꢀa thꢀ tꢃc GREEDY. Ta đã dùng
một danh sách (LIST) các số nguyên và các phép toán trên danh sách newclr là:
- Tạo một danh sách rỗng.
- Lấy phần tꢇ đầu tiên trong danh sách và trả về giá trꢍ null nꢁu danh sách rỗng.
- Lấy phần tꢇ kꢁ tiꢁp trong danh sách và trả về giá trꢍ null nꢁu không cꢉn phần tꢇ kꢁ
tiꢁp.
-
h.
Nꢁu chúng ta viꢁt các chƣơng trꢐnh con thực hiện các phép toán này, thꢐ ta dễ dàng thay
các mệnh đề hꢐnh thức trong giải thuật bꢅng các câu lệnh đơn giản
Câu lệnh
Mệnh đề hꢐnh thức
MAKENULL(newclr)
newclr=;
w=FIRST(newclr)
w=NEXT(w,newclr)
INSERT( v,newclr)
w=phần tꢇ đầu tiên trong newclr
w=phần tꢇ kꢁ tiꢁp trong newclr
Thêm v vào newclr
Ðiều này cho thấy sự thuận lợi cꢀa ADT, đꢏ là ta cꢏ thể đꢍnh nghꢋa một kiểu dữ liệu tuỳ
ý cùng vꢈi các phép toán cần thiꢁt trên nꢏ rꢌi chúng ta dùng nhƣ là các đꢏi tƣợng nguyên
thuỷ. Hơn nữa chúng ta cꢏ thể cài đꢄt một ADT bꢅng bất kỳ cách nào, chƣơng trꢐnh dùng
chúng cũng không thay đổi, chỉ cꢏ các chƣơng trꢐnh con biểu diễn cho các phép toán cꢀa
ADT là thay đổi.
Cài đặt ADT là sự thể hiện các phép toán mong muốn (các phép toán trừu tƣợng) thành
các câu lệnh cꢀa ngôn ngữ lập trꢐnh, bao gꢌm các khai báo thꢂch hợp và các thꢀ tꢃc thực hiện
các phép toán trừu tƣợng. Ðể cài đꢄt ta chọn một cấu trúc dữ liệu thꢂch hợp cꢏ trong ngôn
ngữ lập trꢐnh hoꢄc là một cấu trúc dữ liệu phức hợp đƣợc xây dựng lên từ các kiểu dữ liệu cơ
bản cꢀa ngôn ngữ lập trꢐnh.
Sự khác nhau giữa kiểu dữ liệu và kiểu dữ liệu trừu tƣợng là gꢐ?
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
4
structure), kiểu dữ liệu trừu tƣợng (abstract data type) nghe 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 sơ cấp 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 toán học cùng vꢈi một tập hợp các phép
toán 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 ngữ lập trꢐnh cꢃ thể, chúng ta phải
thực hiện hai nhiệm vꢃ:
1. Biểu diễn kiểu dữ liệu trừu tƣợng bꢅng một cấu trúc dữ liệu hoꢄc một kiểu dữ liệu
trừu tƣợng khác đã đƣợc cài đꢄt.
2. Viꢁt các chƣơng trꢐnh con thực hiện các phép toán trên kiểu dữ liệu trừu tƣợng mà ta
thƣờng gọi là cài đꢄt các phép toán.
Bài tập:
1. Tꢐm hiểu các kiểu dữ liệu cơ sở trong C
2. Tꢐm hiểu các cấu trúc dữ liệu mảng, cấu trúc trong C và thực hiện một số bài tập cơ
bản nhƣ nhập, xuất
5
CHƢƠNG 2. CÁC KIỂU DỮ LIỆU TRỪU TƢỢNG CƠ BẢN
́
2. 1. Ngăn xêp - Stack
2.1.1 Khái niệm
Khái niệm: Ngăn xê
chƣc môt cach tuân tƣ (chꢂnh vꢐ thꢁ một số tài liệu cꢉn đꢍnh nghꢋa ngăn xꢁp là một danh sách
n tƣ vơi cac thao tac truy câp han chê tơi cac phân tƣ cua danh sach đo)
i cung cua tâp hơp
. Các ngăn xꢁp thƣờng đƣợc gọi là các cấu trúc LIFO (Last In First Out).
́p (stack) là một tập hợp các phần tꢇ (items) cùng kiểu đƣợc tổ
̣
̀
̣
́
́
tuyê
́
n tinh cac phâ
̀
̣
̣
́
̀
̉
̉
̉
́
́
́
́
́
́
́
́
́
trong đo phâ
̀
n tƣ đƣơc
̣
thêm vao cuô
́
̣
̣
se la phâ
̀
n tƣ bi
loai
̣
bo đâ
̀
u tiên khoi
̉
̉
̃
̀
̉
̉
̉
́
̀
̀
tâp
̣
hơp
Ví dụ vê ngăn xêp: Chô
vꢂ dꢃ về ngăn xꢁp.
Chú ý: Phâ
thêm vao gân đây nhất (theo thơi gian) cꢀa ngăn xꢁp.
̀
̣
̀
́
̀
ng tai liêu
̣
cua môt
̣
công chƣc văn phong, chô
̀
ng đia … la cac
̉
̀
́
̀
̀
́
̃
̉
̣ ̣ ̣
n tƣ duy nhất co thê truy câp tơi cua môt ngăn xếp la phần tƣ mơi đƣơc
̉ ̉ ̉
́ ́ ̀ ́
̀
̀
̀
2.1.2 Các thao tác của ngăn xếp
Đối vꢈi một ngăn xꢁp chỉ cꢏ 2 thao tac cơ ban, thao tac thƣ nhâ
́
t thƣc
̣
hiên
̣
thêm môt
̣
̉
́
́
́
phâ
̀
n tƣ vao stack goi
̣
la push, thao tac thƣ hai la đoc
̣
gia tri
cua môt
̣
phân tƣ va loai
̀
̣
bo nꢏ khꢊi
̉
̉
̉
̉
̀
̀
́
́
̀
́
̀
stack goi
̣
la pop.
̀
̉
̉
cấu truc stack chuân STL (và một số tài liệu
́
Đê nhâ
́
t quan vơi cac thƣ viên
̣
cai đăt
̣
́
́
́
̀
cũng phân chia nhƣ vậy), ta xac đin
̣
h cac thao tac đô
́
i vơi môt
̣
stack gồm co:
́
́
́
́
́
1. Thao tac push(d) sẽ đꢄt phần tꢇ d lên đinh cua stack.
̉
́
̉
2. Thao tac pop() loại bꢊ phần tꢇ ở đỉnh stack.
́
3. Thao tac top() sẽ trả về giá trꢍ phần tꢇ ở đỉnh stack.
́
4. Thao tac size() cho biê
́
t sô
Ngoài hai thao tác cơ bản trên chúng ta câ
làm thꢁ nào để biꢁt là một stack không cꢏ phần tꢇ nào – tƣc la rô
́
phâ
̀
n tƣ hiên
̣
tai
̣
đang lƣu trong stack
sô thao tac phu trơ
ng (empty) hay la đâ
̉
́
̉
̣ ̣
khac: chăng han
́
̀
n co môt
̣
́
̣
́
́
̃
̀
y (full)
̉
̣ ̣ ̣
tƣc la không thê thêm vao bất cƣ môt phần tƣ nao khac nƣa. Đê thƣc hiên điều nay ngƣơi ta
̉
̃
́ ̀ ́
́
̀
̀
̉
́
̀
̀
̀
̀
̉
thƣơng thêm hai thao tac tiến hanh kiêm tra la empty() và full().
̀ ̀
̀
́
̉
̉
̣ ̣
Đê đam bao không xay ra tinh trang goi la stack overflow (tràn stack – không thê thêm
̀
̉
̉
̉
̀
̉
̣
vào stack bất cứ phần tꢇ nào) chúng ta cꢏ thể cho hàm push tra về chăng han 1 trong trƣơng
̀
̉
̣ ̣ ̣
hơp thƣc hiên thanh công va 0 nếu không thanh công.
̀ ̀ ̀
6
2.1.3 Ví dụ về hoạt động của một stack
Giả sꢇ chúng ta cꢏ một stack kꢂch thƣꢈc bꢅng 3 (cꢏ thể chứa đƣợc tối đa 3 phâ
các phần tꢇ cꢀa stack là các số nguyên trong khoảng từ -100 đꢁn 100. Sau đây la minh hoa
̀
n tƣ) và
̉
̣
̀
các thao tác đối vꢈi stack và kꢁt quả thực hiện cꢀa các thao tác đꢏ.
́
Kêt qua
̉
Thao tac
Nôi
()
(55)
̣
dung stack
́
Khơi tao
̣
̉
push(55)
push(-7)
push(16)
pop
1
(-7, 55)
(16, -7, 55)
(-7, 55)
(-8, -7, 55)
(-8, -7, 55)
(-7, 55)
(55)
1
1
16
1
push(-8)
push(23)
pop
0
-8
-7
55
pop
pop
()
pop
()
101
2.1.4 Cài đặt stack bꢀng mảng
̉
Câ
́
u truc dƣ liêu
̣
stack co thê cai đăt
̣
bă
top_idx đê chƣa chi số cua phần tƣ ơ đinh stack.
̉
̀ng cach sƣ dꢃng một mảng và một số nguyên
̉
́
́
̃
́
̀
̉
̉
̉
́
̉
̉
Ngăn xê
́
p rô
hiên
hiên
̃
ng khi top_idx = -1 và đầy khi top_idx = n-1 trong đo n la kich thƣơc cua
̉
́
̀
́
́
mảng.
Khi thƣc
ứng cꢀa mảng.
Khi thƣc
Vꢂ dꢃ về ngăn xꢁp cài đꢄt bꢅng mảng:
Giả sꢇ chúng ta sꢇ dꢃng mảng E[0..4] để chứa các phần tꢇ cꢀa stack va biê
̣
̣
thao tac push chung ta tăng top_idx lên 1 và ghi dữ liệu vào vꢍ trꢂ tƣơng
́
́
̣
̣ ̣
thao tac pop chung ta chi viêc giam chi số top_idx đi 1.
̉
́ ́
̉ ̉
́
n top_idx
̀
để lƣu chỉ số cꢀa phần tꢇ ở đỉnh stack. Trong bang sau côt
̣
cuô
́
i cung kê
́
t qua la gia tri tra vê
̣
̉
̀
̉
̉
̀
̀
́
cꢀa việc gọi hàm.
Thao tac
́
top_idx E[0] E[1] E[2] E[3] E[4] Kêt qua
́
̉
khơi tao
̣
-1
0
1
2
1
2
1
0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
̉
push(55)
push(-7)
push(16)
pop
55
55
55
55
55
55
55
?
?
1
-7
-7
-7
-7
-7
-7
?
1
16
16
-8
-8
-8
1
16
1
push(-8)
pop
-8
-7
pop
Chú ý rꢅng trong minh họa này chúng ta thấy rꢅng một số giá trꢍ vẫn cꢉn trong mảng
nhƣng chung đƣơc xem nhƣ không co trong stack vi không co thao tac nao truy câp tơi chung.
̣
̣
́
́
́
́
̀
́
́
̀
Nꢏi chúng thꢐ phần tꢇ E[i] đƣơc
̣
xem la rac nê
́
u nhƣ i>top_idx. Tại sao chúng ta không xꢏa bꢊ
̀
́
̉
các phần tꢇ này (chăng han nhƣ đăt chung bꢅng các giá trꢍ mꢄc đꢍnh nào đꢏ?).
̣
̣
́
7
Cài đꢄt cꢀa stack bꢅng ngôn ngữ C nhƣ sau (áp dꢃng stack cho bài toán chuyển số từ
10 sang cơ sô 2):
cơ sô
́
́
#include <stdio.h>
#include <stdlib.h>
const int MAX_ELEMENT = 100; // so phan tu toi da cua stack la 100
// khai bao stack chua cac so nguyen
typedef struct
{
int * data; // khai bao mang dong
int top_idx;
} stack;
// ham khoi tao stack rong
void init(stack *s);
void push(stack * s, int d);
void pop(stack *s);
int top(const stack *s);
int size(const stack *s);
int empty(const stack *s);
int full(const stack *s);
// ham giai phong bo nho danh cho stack
void clear(stack *s);
int main()
{
int n;
int bit;
stack s;
init(&s);
printf("Nhap so nguyen n = ");
scanf("%d", &n);
while(n)
{
push(&s, n%2);
n /= 2;
}
while(!empty(&s))
{
bit = top(&s);
pop(&s);
printf("%d", bit);
}
clear(&s);
return 0;
8
}
void init(stack *s)
{
s->data = (int*)malloc(MAX_ELEMENT * sizeof(int));
s->top_idx = -1;
}
void clear(stack *s)
{
if(s->data != NULL)
free(s->data);
s->top_idx = -1;
}
void push(stack *s, int d)
{
s->data[++s->top_idx] = d;
}
void pop(stack *s)
{
s->top_idx --;
}
int top(const stack *s)
{
return s->data[s->top_idx];
}
int size(const stack *s)
{
return s->top_idx+1;
}
int empty(const stack * s)
{
return (s->top_idx==-1)?(1):(0);
}
int full(const stack * s)
{
return (s->top_idx==MAX_ELEMENT-1)?(1):(0);
}
̉
Câ
́
u truc stack co thê cai đăt
̣
bă
̀
ng mang theo cac cach khac, hoăc
̣
cai đăt
̣
bă
̀
ng con tro
̉
̉
́
́
̀
́
́
́
̀
(chúng ta sẽ học vê
̀
phâ
̀
n cai đăt
̣
nay sau phâ
̀
n danh sach liên kê
́
t).
̀
̀
́
̉
Stack co thê đƣơc
̣
cai đăt
̣
bă
̀
ng ca mang va danh sach liên kê
́
t vây
̣
khi nao chung ta sƣ
̉
̉
̉
́
̀
̀
́
̀
́
dꢃng mảng và khi nào dùng danh sách liên kꢁt?
́
Danh sach liên kêt
Mảng
p phat môt
́
Cƣ mô
̃
i phâ
̀
n tƣ cua stack câ
̀
n
Xin câ
́
̣
vung nhơ co kich
̉
̉
́
́
̀
́
́
́
̉
cꢏ thêm 2 byte (1 con tro).
thƣơc cô
́
đin
̣
h va co thê môt
̣
phâ
̀
n
̉
́
̀
́
9
Nê
́
u kich thƣơc cua môt
̣
phâ
̀
n
trong sô
đꢁn và nꢁu nhƣ kꢂch thƣꢈc cꢀa một
phân tƣ lơn thi vung nhơ lang phi nay
cũng rất lꢈn.
Kꢂch thƣꢈc tối đa cꢀa stack đƣợc xác
đinh ngay khi no đƣơc tao ra.
́ đo không bao giơ đƣơc dung
̣
̉
́
́
̀
̀
́
̉
tƣ lơn thi không đang kê
̉
nhƣng nê
́
́
̀
̉
́
u la kiêu int thi kich
̀
̉
̃
̀
́
̀
́
̀
̀
́
̀
́
thƣơc se tăng gâ
́
p đôi.
́
̃
Không co giơi han về số phần
̣
́
́
tƣ cua stack.
̉
̣
̣
̣
̉
́
2.1.5 ꢁng dụng của stack
Ví dụ 1
̉
̉
̉
̉
̣ ̣ ̣
Stack co thê dung đê kiêm tra cac căp ky hiêu cân bằng trong môt chƣơng trinh (chăng
́
̀
́
̀
́
hạn {}, (), []).
̉
Vꢂ dꢃ {()} và {()({})} là các biểu thức đúng cꢉn {((} và {(}) không phai la cac biêu
̉
̀
́
thƣc đung.
́
́
Chúng ta thấy rꢅng nꢁu nhƣ một biểu thức là đúng thꢐ trong quá trꢐnh đọc các ký hiệu
̉
cꢀa biểu thức đꢏ nꢁu chúng ta thấy một ký hiệu đꢏng (chăng han
̣
), } hay ]) thꢐ ký hiệu này
phải khꢈp vꢈi ký hiệu mở đƣợc đọc thấy gần nhất (theo thơi gian), và khi đꢏ việc sꢇ dꢃng
̀
̣
stack cho cac bai toan nhƣ thế nay la hoan toan hơp ly.
̀ ̀ ̀ ̀ ́
́
̀
́
Chúng ta cꢏ thể sꢇ dꢃng thuật toán sau đây:
while not end of Input
S = next sumbol
if(s is opening symbol)
push(s)
else // s la dấu đong ngoăc
̣
́
̀
if(stack.empty)
Báo lỗi
else
R = stack.top()
stack.pop()
if(!match(s,r))
Báo lỗi
If(!stack.empty())
Báo lỗi
Vꢂ dꢃ:
1. Input: {()}
s = {, push{,
s = (, push (,
s = ), r = pop = (, r,s match
s = }, r = pop = {, r,s match
End of Input, stack rông => biêu thƣc la đung.
̃
̉
́ ̀ ́
Vꢂ dꢃ: Input = { ( ) ( { ) } } (sai)
Input = { ( { } ) { } ( ) }
10
Ví dụ 2
̣
Sƣ dung Stack đê chuyên đôi cac dạng biểu thức đại số. Trong vi du nay chung ta se
̀ ́
̃
̉
̉
̉
̣
̉
́
́
̉
̉
̉
̉
xem xet cac thuât
̣
toan sƣ dun
̣
g stack đê chuyên đôi tƣ biêu đai
̣
số
ơ dan
̣
g trung tố (dạng thông
̉
̉
́
́
́
̀
thƣơng, hay con goi
̀
̣
la infix notation) thành các biểu thức ở dạng tiền tố (prefix notation, hay
̀
̀
̉
cꢉn gọi là biểu thức Balan – Polish notation) và biểu thức hậu tố (postfix notation, hay biêu
thƣc Balan ngƣơc).
̣ ̣ ̣
Biêu thƣc đai kết hơp đung đắn giƣa cac toan hang (operand) và các toán
́ ́ ́
̃
̣
́
̉
̣
số
la môt
̣
sƣ
́
̀
tƣ (operator). Toán hạng là các số liệu cꢏ thể thực hiện đƣợc các thao tác tꢂnh toán toán học.
̉
Toán hạng cũng cꢏ thể là các biꢁn số x, y, z hay cac hằng số . Toán tꢇ là một ký hiệu chỉ ra
́
̉
thao tac tinh toan toan hoc
̣
hay logic giƣa cac toan han
̣
g, chăng han
̣
nhƣ cac toan han
̣
g +, -, *,
́
́
́
̃
́
́
́
́
́
̉
/, ^ (toán tꢇ mũ hꢏa). Viêc
̣
đin
̣
h nghia cac biêu thƣc đai sô môt cach chăt
̣
́
̣
̣
che vê
̀
ly thuyêt la
́
́
́
́
̃
́
̀
̃
nhƣ sau:
̉
̣ ̣ ̣ ̣ ̣
toan hang la môt biêu thƣc hơp lê
́ ̀ ́
Môt
Nêu expression1 và expression2 là hai biểu thức hợp lệ và op là một toán tꢇ thꢐ
môt
toán tꢇ op sẽ cho ta một biểu thức đại số hợp lệ
́
̉
̉
̣
kê
́
t hơp
̣
hơp
̣
lê
̣
giƣa biêu thƣc expression 1 vơi biêu thƣc expression 2 sƣ dun
̣
g
̃
́
́
́
̉
̉
Theo đin
̣
h nghia trên ta co x + y*z la môt
̣
biêu thƣc đai
̣
số
hơp
̣
lê
̣
nhƣng *x y z+
́
̀
́
̃
̉
̉
̉
không phai la môt
̣
biêu thƣc hơp
̣
lê.
̣
Trong cac biêu thƣc đai
̣
số
ngƣơi ta co thê sƣ dun
̣
g cac
́
̉
̉
̀
́
́
́
̀
́
̣
dấu đong va mơ ngoăc.
̉
́ ̀
̉
̉
̉
̃
Môt
̣
biêu thƣc đai
̣
số
co thê đƣơc
̣
biêu diên bă
g biêu diên phô biê
, toán tꢇ nꢅm giữa các toán hạng. Vꢂ dꢃ nhƣ 2 + 3 * (7
̀ng 3 dạng khác nhau.
́
́
̉
̉
̃
̉
̉
́n nhất cua cac biêu
̉
́
Biêu thƣc trung tô
́
(infix notation): đây la dan
̣
́
̀
̉
thƣc đai
̣
số
, trong cac biêu thƣc trung tô
́
́
́
́
– 3)
̉
Biêu thƣc tiê
̀
n tố (prefix notation): dạng biểu diễn này do nhà toán học ngƣời Balan
́
̉
̃
g biêu diên nay, toán tꢇ đứng trƣꢈc
̀
Jan Lukasiewicz đƣa ra vao nhƣng năm 1920. Trong dan
̣
̀
̃
các toán hạng. Vꢂ dꢃ nhƣ + * 2 3 7
̉
̉
Biêu thƣc hâu
̣
tô
́
(postfix notation): hay con goi
̣
la biêu thƣc Balan ngƣơc
̣
, toán tꢇ
̣ ̣
Câu hoi ma chung ta co thê đăt ra ngay lâp tƣc ơ đây la: tại sao lại cần sꢇ dꢃng tꢈi các
́
́
̀
̀
́
đƣng sau cac toan hang. Vꢂ dꢃ nhƣ 2 3 – 7 *.
̣
́
́
́
̉
̉
̉
̀
́
́
̀
dạng biểu diễn tiền tố và hậu tố trong khi chúng ta vẫn quen và vẫn sꢇ dꢃng đƣợc các biểu
thƣc ơ dang trung tô
Lý do là các biểu thức trung tố không đơn giản và dễ dàng khi tꢂnh giá trꢍ cꢀa chúng
̣
́.
̉
́
nhƣ chung ta vân
̃
tƣơng. Đê tinh gia tri
̉
cua môt
̣
biêu thƣc trung tô
̉
́
chung ta câ
̀
n tinh tơi đô
̣
ƣu
̉
̉
́
́
́
́
́
́
́
̉
tiên cua cac toan tƣ cua biêu thƣc va cac qui tă
́
c kê
́
t hơp
̉
̣
cua môt biêu thức trung tố.
̣
. Độ ƣu tiên cꢀa các toán tꢇ và các qui
̉
̉
̉
́
́
́
̀
́
tă
́
c kê
́
t hơp
Chúng ta cꢏ bảng độ ƣu tiên cꢀa các toán tꢇ thƣờng gꢄp nhƣ sau:
Toán tꢂ Độ ƣu tiên
̣
se quyê
́
t đin
̣
h tơi qua trinh tinh toan gia tri
̣
̃
́
́
́
́
̉
̀
́
()
+ (môt
+ (công), - (trƣ)
̣
̣
ngôi), - (môt ngôi), !
̣
̀
<, <=, >, >=
==, !=
11
&&
||
Khi đa biê
́
t đô
̣
ƣu tiên toan tƣ chung ta cꢏ thể tꢂnh toán các biểu thức chẳng hạn 2 + 4
̉
́ ́
̃
* 5 sẽ bꢅng 22 vꢐ trƣꢈc hꢁt cần lấy 4 nhân vơi 5, sau đo kê
́
t qua nhân
̣
̣ ̣
đƣơc đem công vơi 2 vꢐ
́
̉
́
́
̉
̉
phép nhân cꢏ độ ƣu tiên cao hơn phép cộng. Nhƣng vơi biêu thƣc 2*7/3 thꢐ ta không thê tinh
́
́
́
đƣơc
kêt hơp
đô ƣu tiên. Chăng han
đƣơc thƣc hiên tƣ trai qua phai, hay qui tă
phép toán trên sẽ cꢏ kꢁt quả là 4 (lâ
Vꢐ những vấn đề liên quan tꢈi độ ƣu tiên toán tꢇ và các qui luật kꢁt hợp nên chúng ta
̣ ̣ ̣ ̣
vi phep nhân va phep chia co đô tiên bằng nhau, khi đo cần sƣ dung tơi cac qui tắc
̉
́ ̀ ́ ́ ́ ́ ́
̀
ƣu
́
̣
cac toan tƣ. Qui tă
́
c kê
́
t hơp
̣
se cho chung ta biê
́
t thƣ tƣ
̣
thƣc
̣ ̣
hiên cac toan tƣu co cung
̉
́ ́ ́ ̀
̉
̃
́
́
́
́
̉
̣
̣
chung ta co qui tă
́
c kê
c kê
y kết qua nguyên).
́
t hơp
̣ ̣
t hơp phai. Nếu theo qui tắc kết hơp trai thi
̉
́
̀
̣
trai, nghꢋa là các toán tꢇ cùng độ ƣu tiên sẽ
́
́
́
̣
̣
̣
́
́
̉
̀
́
́
̉
̉
̃
̉
̣ ̣ ̣
̀n tố va hâu tố trong viêc tinh toan cac biêu thƣc đai số .
̀ ́ ́ ́
́
thƣơng sƣ dun
̣
g cac dan
̣
g biêu diên tiê
̉
̀
́
Cả biểu thức hậu tố và tiền tố đều cꢏ một ƣu điểm hơn so vꢈi cách biểu diễn trung tố:
̉
̉
́
đo la khi tinh toan cac biêu thƣc ơ dan
̣
g tiê
̣ ̣
̀n tố va hâu tố chung ta không cần phai đê y tơi đô
̉
̀ ́ ́
̉
́
̀
́
́
́
́
̉
ƣu tiên toan tƣ va cac luât
̣
kê
và hậu tố khꢏ hiểu hơn và vꢐ thꢁ nên khi biểu diễn chúng ta vẫn sꢇ dꢃng dạng biểu thức trung
tô, nhƣng khi tinh toan se sƣ dung dang tiên tô hoăc hâu tô, điêu nay yêu câu cân co các thuật
toán chuyển đổi từ dạng trung tố sang dạng tiền tố hoꢄc hậu tố.
́
t hơp
̣
. Tuy nhiên so vơi biêu thƣc trung tố, các biểu thức tiền tố
̉
́
̀
́
́
́
́
̣
̣
̀
́
̣
̣
́
̀
̀
̀
̃
̉
̀
́
́
́
̉
̉
̉
Viêc
̣
chuyên đôi cua chung ta co thê thƣc
̣
hiên
̣
bă
̀
ng cach sƣ dun
̣
g câ
̣
toan sƣ dung stack vi
̀
́u truc stack hoă
̣
̉
̉
́
́
́
́
̉
cây biêu thƣc (chƣơng 5), phâ
̀
n nay chung ta se chi xem xet cac thuât
̣
̃
́
́
́
̉
́
̀
́
̉
̉
̣ ̣ ̣
thuât toan sƣ dung cây biêu thƣc kha phƣc tap.
̉
́ ́ ́ ́
̉ ̉ ̉
̣ ̣ ̣ ̣ ̣
Thuât toan chuyên đôi biêu thƣc dang trung tố thanh dang hâu tố sƣ dung stack.
̉
́ ́ ̀
Ví dụ 3
Phân tich đô
̣
ƣu tiên toan tƣ
̉
́
́
̉ ̉
̣
́u truc stack đê phân tich va lƣơng gia cac biêu thƣc toan
́ ̀ ́ ́ ́ ́
́
Chúng ta cꢏ thể sꢇ dꢃng câ
học kiểu nhƣ:
5 * (( (9+8) * (4 * 6) ) + 7)
̉
Trƣơc hê
́
t chung ta chuyên chung thanh dan
̣
g hâu
̣
tô
́
(postfix):
̣ ̣
cua biêu thƣc hâu tố nhân
́
́
́
̀
5 8 9 + 4 6 * * 7 + *
̉
̉
Sau đo sƣ dung môt
̣
̣
stack đê thƣc
̣
hiên
̣
viêc
̣
tinh toan gia tri
́
̣
̉
̉
́
́
́
́
̣
đƣơc.
Ngoài ra các stack cꢉn cꢏ thể dùng để cài đꢄt các thuật toán đệ qui và khꢇ đệ qui các
cài đꢄt thuật toán.
2.2. Hàng đợi - Queue
2.2.1 Khái niệm
Hàng đợi là một tập hợp các phần tꢇ cùng kiểu đƣợc tổ chức một cách tuần tự (tuyê
tꢂnh) trong đo phân tƣ đƣơc thêm vao đâu tiên se la phân tƣ đƣơc loai bo đâu tiên khoi hang
. Các hàng đợi thƣờng đƣợc gọi là các cấu trúc FIFO (First In First Out).
Các vꢂ dꢃ thực tꢁ về hàng đợi mà chúng ta cꢏ thể thấy trong cuộc sống hàng ngày đꢏ là
đoan ngƣơi xêp hang chơ mua ve tâu, danh sach cac cuôc hen cua môt giam đôc, danh sach
́n
̀
̣
̀
̀
̣
̣
̀
̉
̃
̉
̉
̉
́
̀
̀
̀
đơi
̣
́
̀
̣
̣
̣
́
̉
̀
̀
̀
̀
́
́
́
́
́
̣ ̣
các công viêc cần lam cua môt ngƣơi …
̉
̀ ̀
12
Cũng cꢏ thể đꢍnh nghꢋa hàng đợi là một danh sách tuyꢁn tꢂnh các phần tꢇ giống nhau
vơi môt sô thao tac han chê tơi cac phân tƣ trên danh sach đo.
̣
́
̣
́
̀
̉
́
́
́
́
́
́
2.2.2 Các thao tác cơ bản của một hàng đơi
Tƣơng tƣ nhƣ câu truc ngăn xêp, chúng ta đꢍnh nghꢋa các thao tác trên hàng đợi tuân
trong thƣ viên STL va cac tai liêu khac, gôm co:
n tƣ d vao vi tri ơ cuô
̣
̣
́
́
́
̉
theo cai đăt
̣
chuân cua hang đơi
̣
̣
̣
̀
̉
̀
̀
̀
́
̀
́
́
1. push(d): thêm phâ
̀
̣
̣
́i hang đơi.
̀
̉
̉
̀
́
2. pop(): loại bꢊ phần tꢇ ở đầu hàng đợi.
3. front(): trả về giá trꢍ phần tꢇ ở đầu hàng đợi.
4. back(): trả về giá trꢍ phần tꢇ ở cuối hàng đợi.
5. size(): trả về số phần tꢇ đang ở trong hàng đợi.
̉
̃
6. empty(): kiêm tra hang đơi co rông hay không.
̣
̀
́
̉
̣
7. full(): kiêm tra hang đơi đầy (chỉ cần khi cài đꢄt hàng đợi bꢅng mảng).
̀
Vꢂ dꢃ:
Thao tac
Nôi
̣
dung
Giá trị trả về
́
Khơi tao
̣
( )
( 7 )
( 7, 8 )
̉
push(7)
push(8)
push(5)
pop()
( 7, 8, 5 )
( 8, 5 )
( 5 )
7
pop()
8
2.2.3 Cài đặt hàng đợi sꢂ dụng mảng
̉
̉
̣ ̣ ̣ ̣
cấu truc hang đơi chung ta co thê sƣ dung mang hoăc sƣ dung con tro (phần
̉ ̉ ̉ ̉
́ ̀ ́ ́
Đê cai đăt
̣
̀
này sẽ học sau phần danh sách liên kꢁt):
Ta lƣu cac phân tƣ cua hang đơi
̀
̣
trong môt
u tiên, và đuôi đƣợc chỉ ra bꢅng cách sꢇ dꢃng một biꢁn tail.
push(d) đƣơc thƣc hiên môt cach dê dang: tăng tail lên 1 và chꢎn phần tꢇ vào vꢍ trꢂ
đo
̣
mang data . Đầu cꢀa hàng đợi là phần tꢇ
̉
̉
̉
́
̀
đâ
̀
̃
̣
̣
̣
̣
́
̀
́
pop() đƣơc
do đo đô phƣc tap
̀
̣
thƣc
̣
hiên
̣
không hiêu qua: tất ca cac phần tƣ đều se bi dồn về đầu mang
̣
̣
̉
̉
̉
̃
̉
́
̣
̣
la O(n).
́
́
Làm thꢁ nào chúng ta cꢏ thể cải thiện tꢐnh hꢐnh này?
Thay vi chi sƣ dung môt biên chi sô tail chung ta sƣ dꢃng hai biꢁn tail và head, khi câ
n tƣ khoi hang đơi
̣
̣
́
́
̀n
̉
̉
̉
̉
́
̀
loại bꢊ (pop) môt
Tuy vây vân
kê ca trong trƣơng hơp
̣
phâ
̀
̣
chung ta se tăng biê
́
n head lên 1:
̀ , đo la sau n lần push() (n la kich thƣơc mang) mảng sẽ đầy
́ ̀
̉
̉
̃
̀
́
̃
con co vâ
́
n đê
nꢏ gần nhƣ rỗng về mꢄt logic. Đê giai quyê
̣
̉
̀
́
̀
́
́
̉
̉
̣
́
t vâ
́
n đê
tăng lên 1 nhƣng
̃
̀
nay chung ta se sƣ
̉
̉
̃
̉
̀
̀
́
dꢃng lại các phần tꢇ ở đầu mảng. Khi push() môt
nêu nhƣ no ơ cuôi mang thi se đăt no băng 0.
mơi nảy sinh ở đây là làm thꢁ nào chúng ta cꢏ thể xác đꢍnh đƣợc khi nào hàng
̣
phâ
̀
n tƣ mơi tail se đƣơc
̣
̉
́
́
́
̣
̀
̉
̉
̃
́
́
̀
Vâ
́
n đê
̀
́
đơi
̣
rô
̃
ng hoăc
̣
đầy?
13
Cách giải quyꢁt đơn giản là ta sẽ dùng một biꢁn lƣu số phần tꢇ thực sự cꢀa hàng đợi
̉
̣ ̣
để giải quyꢁt cho tất cả các thao tác kiêm tra hang đơi rông, đầy hoăc lấy số phần tƣ cua hang
̃
̉ ̉
̀
̀
̣
đơi.
#include <stdio.h>
#include <stdlib.h>
const int MAX_ELEMENT = 100; // so phan tu toi da cua queue la 100
// khai bao queue chua cac so nguyen
typedef struct
{
int * data; // khai bao mang dong
int head;
int tail;
int cap; // luu so phan tu cua hang doi
} queue;
// ham khoi tao queue rong
void init(queue *q);
void push(queue * s, int d);
void pop(queue *q);
int front(const queue *q);
int back(const queue *q);
int size(const queue *q);
int empty(const queue *q);
int full(const queue *q);
// ham giai phong bo nho danh cho queue
void clear(queue *q);
int main()
{
int a[] = {3, 5, 1, 8};
int n = 4;
int i;
int d;
queue q;
init(&q);
for(i=0;i<n;i++)
push(&q, a[i]);
while(!empty(&q))
{
d = front(&q);
printf("%d ", d);
pop(&q);
}
clear(&q);
return 0;
14
}
void init(queue *q)
{
q->data = (int*)malloc(MAX_ELEMENT * sizeof(int));
q->head = q->tail = -1;
q->cap = 0;
}
void clear(queue *q)
{
if(q->data != NULL)
free(q->data);
q->head = q->tail = -1;
q->cap = 0;
}
void push(queue *q, int d)
{
q->tail = (q->tail + 1) % MAX_ELEMENT;
q->data[q->tail] = d;
if(q->cap==0)
// neu hang doi rong thi sau khi push
// ca head va tail deu chi vao 1 phan tu
q->head = q->tail;
q->cap++;
}
void pop(queue *q)
{
q->head = (q->head + 1)%MAX_ELEMENT;
q->cap--;
if(q->cap==0)
q->head = q->tail = -1;
}
int front(const queue *q)
{
return q->data[q->head];
}
int back(const queue *q)
{
return q->data[q->tail];
}
int size(const queue *q)
{
return q->cap;
}
15
Tải về để xem bản đầy đủ
80 trang
19780
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_truong_dai_hoc_hang_hai.pdf
