Bài giảng Cấu trúc dữ liệu - ĐH Hàng Hải VN

Chia sẻ: Tri Thu | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

27
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu cung cấp kiến thức và rèn luyện kỹ năng thực hành cấu trúc dữ liệu cho sinh viên. Bài giảng gồm có 4 chương như sau: Chương I khái niệm liên quan đến cấu trúc dữ liệu, chương II các kiểu dữ liệu trừu tượng cơ bản, chương III cây (tree), chương IV bảng băm (hash table). Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - ĐH Hàng Hải VN

BỘ GIAO THÔNG VẬN TẢI TRƢỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: KHOA HỌC MÁ Y TÍ NH 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 CHƢƠNG 2. CÁC KIỂU DỮ LIỆU TRỪU TƢỢNG CƠ BẢN ............................................... 6 2. 1. Ngăn xế p - Stack ............................................................................................................ 6 2.1.1 Khái niệm .................................................................................................................. 6 2.1.2 Các thao tác của ngăn xếp ......................................................................................... 6 2.1.3 Ví dụ về hoạt động của một stack ............................................................................. 7 2.1.4 Cài đặt stack bằng mảng ............................................................................................ 7 2.1.5 Ứng dụng củ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 của một hàng đợi ..................................................................... 13 2.2.3 Cài đặt hàng đợi sử dụng mảng ............................................................................... 13 2.2.4 Ví dụ về hoạt động của hàng đợi với cài đặt bằng mảng vòng tròn ........................ 16 2.2.5 Ứng dụng của hàng đơ ̣i ........................................................................................... 16 2.3. Danh sách liên kế t – Linked list .................................................................................... 17 2.3.1 Đinḥ nghiã ............................................................................................................... 17 2.3.2 Các thao tác trên danh sách liên kế t . ....................................................................... 17 2.3.3 Cài đặt danh sách liên kết sử dụng con trỏ .............................................................. 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ƣ̉ du ̣ng cấ u trúc danh sách liên kế t .................................................... 26 2.3.6. Cài đặt stack và queue bằng con trỏ ....................................................................... 26 2.4. Bài tập áp dụng ............................................................................................................. 26 CHƢƠNG 3. CÂY (TREE). ..................................................................................................... 28 3.1. Đinh ̣ nghĩa..................................................................................................................... 28 3.1.1. Đồ thị (Graph) ........................................................................................................ 28 3.1.2. Cây (tree) ................................................................................................................ 29 3.3. Cây tìm kiế m nhi ̣phân (Binary Search Tree - BST) .................................................... 31 3.3.1. Đinḥ nghiã .............................................................................................................. 31 3.3.2. Khởi ta ̣o cây rỗng ................................................................................................... 32 3.3.3. Chèn thêm một nút mới vào cây ............................................................................. 32 3.3.4. Xóa bỏ khỏi cây một nút ........................................................................................ 33 3.3.5. Tì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. Định nghĩa bảng băm ................................................................................................... 54 4.1.1.Định nghĩa : ............................................................................................................. 54 4.1.2.Kích thƣớc củ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. Định nghĩ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 dụng ............................................................................................................. 72 TÀI LIỆU THAM KHẢO. ....................................................................................................... 75 ii
Tên học phần: Cấu trúc dữ liệu Loại học phần: 2 Bộ môn phụ trách giảng dạy: Khoa học Máy tính Khoa phụ trách: CNTT Mã học phần: 17207 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à rè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 TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT Chƣơng I : Khái niệm liên quan đến CTDL 2 2 0 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. Chƣơng II : Các kiểu dữ liệu trừu tƣợng cơ bản 12 6 6 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, vò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 dụ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 dụng 2.4. Bài tập áp dụng Chƣơng III: Cây (tree). 18 9 8 1 3.1. Khái niệm. 3.2. Cây tổng quát. iii
PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 3.2.1. Biểu diễn cây tổng quát. 3.2.2. Duyệt cây tổng quát. 3.2.3. Vài ví dụ áp dụng. 3.3. Cây nhị phân. 3.3.1. Định nghĩa và tính chất 3.3.2. Lƣu trữ cây. 3.3.3. Duyệt cây. 3.3.4. Cây nhị phân nối vòng. 3.4. Các phép toán thực hiện trên cây nhị phân. 3.4.1. Dựng cây 3.4.2. Duyệt cây để tìm kiếm 3.4.3. Sắp xếp cây nhị phân 3.5. Cây tìm kiếm nhị 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 Chƣơng IV: Bảng băm (hash table) 14 7 6 1 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 dụng Nhiệm vụ của sinh viên : Tham dự các buổi thuyết trình củ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 đị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: - Hì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ế của Nhà trƣờng và củ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 của Bộ môn Khoa học máy tí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 tính ta phải bắt đầu từ việc xác định bài toán. Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phải trả lời rõ ràng câu hỏi "phải làm gì?" sau đó 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 của bài toán thực tế, ta phải hình thức hóa nó, nghĩa là phát biểu lại bài toán thực tế thành một bài toán hình thức (hay còn gọi là mô hình toán). Có thể có rất nhiều bài toán thực tế có cùng một mô hình toán. Ví dụ : 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 đó 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) thì phải đƣợc tô bằng hai màu khác nhau. Hãy tìm một phƣơng án tô màu sao cho số màu sử dụng là ít nhất. Ta có thể xem mỗi nƣớc trên bản đồ thế giới là một đỉnh của đồ thị, hai nƣớc láng giềng của nhau thì hai đỉnh ứng với nó đƣợ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 đồ thị nhƣ sau: Mỗi đỉnh đều phải đƣợc tô màu, hai đỉnh có cạnh nối thì phải tô bằng hai màu khác nhau và ta cần tìm một phƣơng án tô màu sao cho số màu đƣợc sử dụng là ít nhất. Ðối với một bài toán đã đƣợc hình thức hoá, chúng ta có thể tìm kiếm cách giải trong thuật ngữ của mô hình đó và xác định có hay không một chƣong trình có sẵn để giải. Nếu không có một chƣơng trình nhƣ vậy thì ít nhất chúng ta cũng có thể tìm đƣợc những gì đã biết về mô hình và dùng các tính chất của mô hình để xây dựng một giải thuật tốt. Khi đã có mô hình thích hợp cho một bài toán ta cần cố gắng tìm cách giải quyết bài toán trong mô hình đó. Khởi đầu là tìm một giải thuật, đó là một chƣỗi hữu hạn các chỉ thị (instruction) mà mỗi chỉ thị có một ý nghĩ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ý, còn đói tƣợng để xử lý trong máy tính chí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ể nói tới giải thuật mà không nghĩ tới: giải thuật đó đƣợc tác động trên dữ liệu nào, còn xét tới dữ liệu thì phải biết dữ liệu ấy cần đƣợc giải thuật gì 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 có 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ử có thể là một chữ số, một ký tự, … cũng có 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ả dĩ theo đó 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 thích hợp để tổ chức dữ liệu vào và trên cơ sở đó 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 chính là cách cài đặt cấu trúc ấy trên máy tí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ý. Có thể có 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 có đặ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ử dụng một ngôn ngữ lập trì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 thủ các quy tắc chặt chẽ về cú pháp của ngôn ngữ khiến cho việc trình bày về giải thuật và cấu trúc dữ liệu có thiên hƣớng nặng nề, gò bó. - Phải phụ thuộc vào cấu trúc dữ liệu tiền định của ngôn ngữ nên có lúc không thể hiện đƣợc đầy đủ các ý về cấu trúc mà ta muỗn biểu đạt Một khi đã có mô hình thích hợp cho bài toán, ta cần hình thức hoá một giải thuật, một cấu trúc dữ liệu trong thuật ngữ của mô hình đó. 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 đề cụ thể hơn, cuối cùng là các chỉ thị thích hợp trong một ngôn ngữ lập trình. Ở bƣớc này, nói chung, ta có một giải thuật, một cấu trúc dữ liệu tƣơng đói rõ ràng, nó gần giống nhƣ một chƣơng trình đƣợc viết trong ngôn ngữ lập trình, nhƣng nó không phải là một chƣơng trình chạy đƣợc vì trong khi viết giải thuật ta không chú trọng nặng đến cú pháp của ngôn ngữ và các kiểu dữ liệu cò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 trình. Chẳng hạn với giải thuật tô màu đồ thị GREEDY, giả sử đồ thị là G, giải thuật sẽ xác định một tập hợp Newclr các đỉnh củ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 đồ thị G thì 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 củ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 thủ tục bằng ngôn ngữ giả này chúng ta đã dùng một số từ khoá củ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 có 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 trình cụ thể. Dĩ nhiên, để cài đặt thủ tục này ta phải cụ 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ã thích hợp của ngôn ngữ lập trình. Chẳng hạn mệnh đề if ở /*3*/ có 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 của G) /*2*/ { int found=0; /*3.1*/ for (mỗi đỉnh w trong Newclr) /*3.2*/ if (có 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. Có nhiều cách để biểu diễn tập hợp trong ngôn ngữ lập trì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ố của các đỉnh và kết thúc bằng một giá trị đặc biệt NULL. Với những qui ƣớc nhƣ vậy ta có 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 (vnull) { found=0; w=đỉnh đầu tiên trong newclr; while( wnull) && (found=0) { if ( có 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 hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn và dễ hiểu hơn. Cụ thể trừu tƣợng hóa là che di những chi tiết, làm nổi bật cái tổng thể. Trừu tƣợng hóa có thể thực hiện trên hai khía cạnh là trừu tƣợng hóa dữ liệu và trừu tƣợng hóa chƣơng trình. Trừu tƣợng hóa chƣơng trình Trừu tƣợng hóa chƣơng trình là sự định nghĩa các chƣơng trình con để tạo ra các phép toán trừu tƣợng (sự tổng quát hóa của các phép toán nguyên thủy). Chẳng hạn ta có thể tạo ra một chƣơng trì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 có thể dùng nó nhƣ một phép toán nguyên thủy (chẳng hạn phép cộng hai số). Trừu tƣợng hóa chƣơng trình cho phép phân chia chƣơng trình thành các chƣơng trì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 trình con. Ở cấp độ chƣơng trình chính, ta chỉ thấy lời gọi các chƣơng trình con và điều này đƣợc gọi là sự bao gói. Ví dụ nhƣ một chƣơng trình quản lý sinh viên đƣợc viết bằng trừu tƣợng hóa có thể là: void main() { Nhap(Lop); 3
Xu_ly (Lop); Xuat (Lop); } Trong chƣơng trì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 trình chính ta không nhìn thấy đƣợc. Cò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 trình đƣợc viết theo cách gọi các phép toán trừu tƣợng có 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 hóa dữ liệu là định nghĩ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 đó. Ví dụ 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 có thể thực hiện trên các đói tƣợng (toán hạng) không chỉ thuộc ADT đó, cũng nhƣ kết quả không nhất thiết phải thuộc ADT. Tuy nhiên, phải có í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 có thể xét bản phác thảo cuối cùng của thủ tụ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á trị null nếu danh sách rỗng. - Lấy phần tử kế tiếp trong danh sách và trả về giá trị null nếu không còn phần tử kế tiếp. - h. Nếu chúng ta viết các chƣơng trình con thực hiện các phép toán này, thì ta dễ dàng thay các mệnh đề hì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 đề hình thức MAKENULL(newclr) newclr=; w=FIRST(newclr) w=phần tử đầu tiên trong newclr w=NEXT(w,newclr) w=phần tử kế tiếp trong newclr INSERT( v,newclr) Thêm v vào newclr Ðiều này cho thấy sự thuận lợi của ADT, đó là ta có thể định nghĩ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 nó rồi chúng ta dùng nhƣ là các đói tƣợng nguyên thuỷ. Hơn nữa chúng ta có thể cài đặt một ADT bằng bất kỳ cách nào, chƣơng trình dùng chúng cũng không thay đổi, chỉ có các chƣơng trình con biểu diễn cho các phép toán củ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 của ngôn ngữ lập trình, bao gồm các khai báo thích hợp và các thủ tụ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 thích hợp có trong ngôn ngữ lập trì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 của ngôn ngữ lập trình. Sự khác nhau giữa kiểu dữ liệu và kiểu dữ liệu trừu tƣợng là gì? 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 có ý nghĩa rất khác nhau. Kiểu dữ liệu là một tập hợp các giá trị và một tập hợp các phép toán trên các giá trị đó. Ví dụ kiểu Boolean là một tập hợp có 2 giá trị TRUE, FALSE và các phép toán trên nó nhƣ OR, AND, NOT …. Kiểu Integer là tập hợp các số nguyên có giá trị 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 có hai loại là kiểu dữ liệu sơ cấp và kiểu dữ liệu có cấu trúc hay cò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á trị dữ liệu của nó là đơn nhất. Ví dụ: kiểu Boolean, Integer…. Kiểu dữ liệu có cấu trúc hay còn gọi là cấu trúc dữ liệu là kiểu dữ liệu mà giá trị dữ liệu của nó là sự kết hợp của các giá trị khác. Ví dụ: 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ô hình toán học cùng với một tập hợp các phép toán trên nó. Có thể nói kiểu dữ liệu trừu tƣợng là một kiểu dữ liệu do chúng ta định nghĩa ở mức khái niệm (conceptual), nó chƣa đƣợc cài đặt cụ thể bằng một ngôn ngữ lập trì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 trình cụ thể, chúng ta phải thực hiện hai nhiệm vụ: 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 trì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. Tìm hiểu các kiểu dữ liệu cơ sở trong C 2. Tì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ế p (stack) là một tập hợp các phần tử (items) cùng kiểu đƣợc tổ chƣ́c mô ̣t cách tuầ n tƣ̣ (chính vì thế một số tài liệu còn định nghĩa ngăn xếp là một danh sách tuyế n tiń h các phầ n tƣ̉ với các thao tác truy câ ̣p ha ṇ chế tới các phầ n tƣ̉ của danh sách đó ) trong đó phầ n tƣ̉ đƣơ ̣c thêm vào cuố i cùng của tâ ̣p hơ ̣p sẽ là phầ n tƣ̉ bi ̣loa ̣i bỏ đầ u tiên khỏi 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). Ví dụ về ngăn xế p: Chồ ng tài liê ̣u của mô ̣t công chƣ́c văn phòng, chồ ng điã … là các ví dụ về ngăn xếp. Chú ý: Phầ n tƣ̉ duy nhấ t có thể truy câ ̣p tới của mô ̣t ngăn xế p là phầ n tƣ̉ mới đƣơ ̣c thêm vào gầ n đây nhấ t (theo thời gian) của ngăn xếp. 2.1.2 Các thao tác của ngăn xếp Đối với một ngăn xếp chỉ có 2 thao tác cơ bản, thao tác thƣ́ nhấ t thƣ̣c hiê ̣n thêm mô ̣t phầ n tƣ̉ vào stack go ̣i là push, thao tác thƣ́ hai là đo ̣c giá tri ̣của mô ̣t phầ n tƣ̉ và loa ̣i bỏ nó khỏi stack go ̣i là pop. Để nhấ t quán với các thƣ viê ̣n cài đă ̣t cấ u trúc stack chuẩ n STL (và một số tài liệu cũng phân chia nhƣ vậy), ta xác đinh ̣ các thao tác đố i với mô ̣t stack gồ m có : 1. Thao tác push(d) sẽ đặt phần tử d lên đỉnh của stack. 2. Thao tác pop() loại bỏ phần tử ở đỉnh stack. 3. Thao tác top() sẽ trả về giá trị phần tử ở đỉnh stack. 4. Thao tác size() cho biế t số phầ n tƣ̉ hiê ̣n ta ̣i đang lƣu trong stack Ngoài hai thao tác cơ bản trên chúng ta cầ n có mô ̣t số thao tác phu ̣ trơ ̣ khác: chẳ ng ha ̣n làm thế nào để biết là một stack không có phần tử nào – tƣ́c là rỗng (empty) hay là đầ y (full) tƣ́c là không thể thêm vào bấ t cƣ́ mô ̣t phầ n tƣ̉ nào khác nƣ̃a. Để thƣ̣c hiê ̣n điề u này ngƣời ta thƣờng thêm hai thao tác tiế n hành kiể m tra là empty() và full(). Để đảm bảo không xảy ra tin ̀ h tra ̣ng go ̣i 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 có thể cho hàm push trả về chẳ ng ha ̣n 1 trong trƣờng hơ ̣p thƣ̣c hiê ̣n thành công và 0 nế u không thành công. 6
2.1.3 Ví dụ về hoạt động của một stack Giả sử chúng ta có một stack kích thƣớc bằng 3 (có thể chứa đƣợc tối đa 3 phầ n tƣ̉) và các phần tử của stack là các số nguyên trong khoảng từ -100 đến 100. Sau đây là minh ho ̣a các thao tác đối với stack và kết quả thực hiện của các thao tác đó. Thao tác Nô ̣i dung stack Kế t quả Khởi ta ̣o () push(55) (55) 1 push(-7) (-7, 55) 1 push(16) (16, -7, 55) 1 pop (-7, 55) 16 push(-8) (-8, -7, 55) 1 push(23) (-8, -7, 55) 0 pop (-7, 55) -8 pop (55) -7 pop () 55 pop () 101 2.1.4 Cài đặt stack bằng mảng Cấ u trúc dƣ̃ liê ̣u stack có thể cài đă ̣t bằ ng cách sƣ̉ dụng một mảng và một số nguyên top_idx để chƣ́a chỉ số của phầ n tƣ̉ ở đỉnh stack. Ngăn xế p rỗng khi top_idx = -1 và đầy khi top_idx = n-1 trong đó n là kích thƣớc của mảng. Khi thƣ̣c hiê ̣n thao tác push chúng ta tăng top_idx lên 1 và ghi dữ liệu vào vị trí tƣơng ứng của mảng. Khi thƣ̣c hiê ̣n thao tác pop chúng ta chỉ viê ̣c giảm chỉ số top_idx đi 1. Ví dụ về ngăn xếp cài đặt bằng mảng: Giả sử chúng ta sử dụng mảng E[0..4] để chứa các phần tử của stack và biế n top_idx để lƣu chỉ số của phần tử ở đỉnh stack. Trong bảng sau cô ̣t cuố i cùng kế t quả là giá tri ̣trả về của việc gọi hàm. Thao tác top_idx E[0] E[1] E[2] E[3] E[4] Kế t quả khởi ta ̣o -1 ? ? ? ? ? push(55) 0 55 ? ? ? ? 1 push(-7) 1 55 -7 ? ? ? 1 push(16) 2 55 -7 16 ? ? 1 pop 1 55 -7 16 ? ? 16 push(-8) 2 55 -7 -8 ? ? 1 pop 1 55 -7 -8 ? ? -8 pop 0 55 -7 -8 ? ? -7 Chú ý rằng trong minh họa này chúng ta thấy rằng một số giá trị vẫn còn trong mảng nhƣng chúng đƣơ ̣c xem nhƣ không có trong stack vì không có thao tác nào truy câ ̣p tới chúng . Nói chúng thì phần tử E[i] đƣơ ̣c xem là rác nế u nhƣ i>top_idx. Tại sao chúng ta không xóa bỏ các phần tử này (chẳ ng ha ̣n nhƣ đă ̣t chúng bằng các giá trị mặc định nào đó?). 7
Cài đặt của stack bằng ngôn ngữ C nhƣ sau (áp dụng stack cho bài toán chuyển số từ cơ số 10 sang cơ số 2): #include #include 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 trúc stack có thể cài đă ̣t bằ ng mảng theo các cách khác , hoă ̣c cài đă ̣t bằ ng con trỏ (chúng ta sẽ học về phầ n cài đă ̣t này sau phầ n danh sách liên kế t ). Stack có thể đƣơ ̣c cài đă ̣t bằ ng cả mảng và danh sách liên kế t vâ ̣y khi nào chúng ta sƣ̉ dụng mảng và khi nào dùng danh sách liên kết? Danh sách liên kế t Mảng Cƣ́ mỗi phầ n tƣ̉ của stack cầ n Xin cấ p phát mô ̣t vùng nhớ có kić h có thêm 2 byte (1 con trỏ). thƣớc cố đinh ̣ và có thể mô ̣t phầ n 9
Nế u kích thƣớc của mô ̣t phầ n trong số đó không bao giờ đƣơ ̣c dùng tƣ̉ lớn thì không đáng kể đến và nếu nhƣ kích thƣớc của một nhƣng nế u là kiể u int thì kích phầ n tƣ̉ lớn thì vùng nhớ lañ g phí này thƣớc sẽ tăng gấ p đôi. cũng rất lớn. Không có giới ha ̣n về số phầ n Kích thƣớc tối đa của stack đƣợc xác tƣ̉ của stack. đinh ̣ ngay khi nó đƣơ ̣c ta ̣o ra. 2.1.5 Ứng dụng của stack Ví dụ 1 Stack có thể dùng để kiể m tra các că ̣p ký hiê ̣u cân bằ ng trong mô ̣t chƣơng triǹ h (chẳ ng hạn {}, (), []). Ví dụ {()} và {()({})} là các biểu thức đúng còn {((} và {(}) không phải là các biể u thƣ́c đúng. Chúng ta thấy rằng nếu nhƣ một biểu thức là đúng thì trong quá trình đọc các ký hiệu của biểu thức đó nếu chúng ta thấy một ký hiệu đóng (chẳ ng ha ̣n ), } hay ]) thì 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 đó việc sử dụng stack cho các bài toán nhƣ thế này là hoàn toàn hơ ̣p lý . Chúng ta có thể sử dụ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 đóng 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 Ví dụ: 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̀ đúng. Ví dụ: Input = { ( ) ( { ) } } (sai) Input = { ( { } ) { } ( ) } 10
Ví dụ 2 Sƣ̉ du ̣ng Stack để chuyể n đổ i các dạng biểu thức đại số. Trong ví du ̣ này chúng ta sẽ xem xét các thuâ ̣t toán sƣ̉ du ̣ng stack để chuyể n đổ i tƣ̀ biể u đa ̣i số ở da ̣ng trung tố (dạng thông thƣờng, hay còn go ̣i là infix notation) thành các biểu thức ở dạng tiền tố (prefix notation, hay cò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 đa ̣i số là mô ̣t sƣ̣ kế t hơ ̣p đúng đắ n giƣ̃a các toán ha ̣ng (operand) và các toán tƣ̉ (operator). Toán hạng là các số liệu có thể thực hiện đƣợc các thao tác tính toán toán học. Toán hạng cũng có thể là các biến số x, y, z hay các hằ ng số . Toán tử là một ký hiệu chỉ ra thao tác tính toán toán ho ̣c hay logic giƣ̃a các toán ha ̣ng, chẳ ng ha ̣n nhƣ các toán ha ̣ng +, -, *, /, ^ (toán tử mũ hóa). Viê ̣c đinh ̣ nghiã các biể u thƣ́c đa ̣i số mô ̣t cách chă ̣t chẽ về lý thuyế t là nhƣ sau:  Mô ̣t toán ha ̣ng là mô ̣t biể u thƣ́c hơ ̣p lê ̣  Nế u express ion1 và expression 2 là hai biểu thức hợp lệ và op là một toán tử thì mô ̣t kế t hơ ̣p hơ ̣p lê ̣ giƣ̃a biể u thƣ́c expression 1 với biể u thƣ́c expression 2 sƣ̉ du ̣ng toán tử op sẽ cho ta một biểu thức đại số hợp lệ Theo đinh ̣ nghiã trên ta có x + y*z là mô ̣t biể u thƣ́c đa ̣i số hơ ̣p lê ̣ nhƣng *x y z+ không phải là mô ̣t biể u thƣ́c hơ ̣p lê ̣. Trong các biể u thƣ́c đa ̣i số ngƣời ta có thể sƣ̉ du ̣ng các dấ u đóng và mở ngoă ̣c. Mô ̣t biể u thƣ́c đa ̣i số có thể đƣơ ̣c biể u diễn bằ ng 3 dạng khác nhau. Biể u thƣ́c trung tố (infix notation): đây là da ̣ng biể u diễn phổ biế n nhấ t của các biể u thƣ́c đa ̣i số , trong các biể u thƣ́c trung tố , toán tử nằm giữa các toán hạng. Ví dụ nhƣ 2 + 3 * (7 – 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 Jan Lukasiewicz đƣa ra vào nhƣ̃ng năm 1920. Trong da ̣ng biể u diễn này , toán tử đứng trƣớc các toán hạng. Ví dụ nhƣ + * 2 3 7 Biể u thƣ́c hâ ̣u tố (postfix notation): hay còn go ̣i là biể u thƣ́c Balan ngƣơ ̣c, toán tử đƣ́ng sau các toán ha ̣ng. Ví dụ nhƣ 2 3 – 7 *. Câu hỏi mà chúng ta có thể đă ̣t ra ngay lâ ̣p tƣ́c ở đây là : tại sao lại cần sử dụng tới các 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ử dụng đƣợc các biểu thƣ́c ở da ̣ng trung tố . Lý do là các biểu thức trung tố không đơn giản và dễ dàng khi tính giá trị của chúng nhƣ chúng ta vẫn tƣởng. Để tiń h giá tri ̣của mô ̣t biể u thƣ́c trung tố chúng ta cầ n tiń h tới đô ̣ ƣu tiên của các toán tƣ̉ của biể u thƣ́c và các qui tắ c kế t hơ ̣p. Độ ƣu tiên của các toán tử và các qui tắ c kế t hơ ̣p sẽ quyế t đinh ̣ tới quá trình tính toán giá tri ̣của mô ̣t biể u thức trung tố. Chúng ta có bảng độ ƣu tiên của các toán tử thƣờng gặp nhƣ sau: Toán tử Độ ƣu tiên () + (mô ̣t ngôi), - (mô ̣t ngôi), ! + (cô ̣ng), - (trƣ̀) = ==, != 11
&& || Khi đã biế t đô ̣ ƣu tiên toán tƣ̉ chúng ta có thể tính toán các biểu thức chẳng hạn 2 + 4 * 5 sẽ bằng 22 vì 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 vì phép nhân có độ ƣu tiên cao hơn phép cộng. Nhƣng với biể u thƣ́c 2*7/3 thì ta không thể tiń h đƣơ ̣c vì phép nhân và phép chia có đô ̣ ƣ̣u tiên bằ ng nhau, khi đó cầ n sƣ̉ du ̣ng tới các qui tắ c kế t hơ ̣p các toán tƣ̉. Qui tắ c kế t hơ ̣p sẽ cho chúng ta biế t thƣ́ tƣ̣ thƣ̣c hiê ̣n các toán tƣ̉u có cùng đô ̣ ƣu tiên. Chẳ ng ha ̣n chúng ta có qui tắ c kế t hơ ̣p trái , nghĩa là các toán tử cùng độ ƣu tiên sẽ đƣơ ̣c thƣ̣c hiê ̣n tƣ̀ trái qua phải, hay qui tắ c kế t hơ ̣p phải . Nế u theo qui tắ c kế t hơ ̣p trái thì phép toán trên sẽ có kết quả là 4 (lấ y kế t quả nguyên). Vì 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 thƣờng sƣ̉ du ̣ng các da ̣ng biể u diễn tiề n tố và hâ ̣u tố trong viê ̣c tiń h toán các biể u thƣ́c đa ̣i số . Cả biểu thức hậu tố và tiền tố đều có một ƣu điểm hơn so với cách biểu diễn trung tố: đó là khi tính toán các biể u thƣ́c ở da ̣ng tiề n tố và hâ ̣u tố chúng ta không cầ n phải để ý tới đô ̣ ƣu tiên toán tƣ̉ và các luâ ̣t kế t hơ ̣p. Tuy nhiên so với biể u thƣ́c trung tố , các biểu thức tiền tố và hậu tố khó hiểu hơn và vì thế nên khi biểu diễn chúng ta vẫn sử dụng dạng biểu thức trung tố , nhƣng khi tiń h toán sẽ sƣ̉ du ̣ng da ̣ng tiề n tố hoă ̣c hâ ̣u tố , điề u này 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ố . Viê ̣c chuyể n đổ i của chúng ta có thể thƣ̣c hiê ̣n bằ ng cách sƣ̉ du ̣ng cấ u trúc stack hoă ̣ cây biể u thƣ́c (chƣơng 5), phầ n này chúng ta sẽ chỉ xem xét cá c thuâ ̣t toán sƣ̉ du ̣ng stack vì thuâ ̣t toán sƣ̉ du ̣ng cây biể u thƣ́c khá phƣ́c ta ̣p. Thuâ ̣t toán chuyể n đổ i biể u thƣ́c da ̣ng trung tố thành da ̣ng hâ ̣u tố sƣ̉ du ̣ng stack . Ví dụ 3 Phân tić h đô ̣ ƣu tiên toán tƣ̉ Chúng ta có thể sử dụng cấ u trúc stack để phân tić h và lƣơ ̣ng giá các biể u thƣ́c toán học kiểu nhƣ: 5 * (( (9+8) * (4 * 6) ) + 7) Trƣớc hế t chúng ta chuyể n chúng thành da ̣ng hâ ̣u tố (postfix): 589+46**7+* Sau đó sƣ̉ du ̣ng mô ̣t stack để thƣ̣c hiê ̣n viê ̣c tính toán giá tri ̣của biể u thƣ́c hâ ̣u tố nhâ ̣n đƣơ ̣c. Ngoài ra các stack còn có 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ế n tính) trong đó phầ n tƣ̉ đƣơ ̣c thêm vào đầ u tiên sẽ là phầ n tƣ̉ đƣơ ̣c loa ̣i bỏ đầ u tiên khỏi hàng đơ ̣i. Các hàng đợi thƣờng đƣợc gọi là các cấu trúc FIFO (First In First Out). Các ví dụ thực tế về hàng đợi mà chúng ta có thể thấy trong cuộc sống hàng ngày đó là đoàn ngƣời xế p hàng chờ mua vé tầ u, danh sách các cuô ̣c he ̣n của mô ̣t giám đố c, danh sách các công viê ̣c cầ n làm của mô ̣t ngƣời … 12
Cũng có thể định nghĩa hàng đợi là một danh sách tuyến tính các phần tử giống nhau với mô ̣t số thao tác ha ̣n chế tới các phầ n tƣ̉ trên danh sách đ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 trúc ngăn xế p , chúng ta định nghĩa các thao tác trên hàng đợi tuân theo cài đă ̣t chuẩ n của hàng đơ ̣i trong thƣ viê ̣n STL và các tài liê ̣u khác , gồ m có: 1. push(d): thêm phầ n tƣ̉ d vào vi ̣trí ở cuố i hàng đơị . 2. pop(): loại bỏ phần tử ở đầu hàng đợi. 3. front(): trả về giá trị phần tử ở đầu hàng đợi. 4. back(): trả về giá trị 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 hàng đơ ̣i có rỗng hay không. 7. full(): kiể m tra hàng đơ ̣i đầ y (chỉ cần khi cài đặt hàng đợi bằng mảng). Ví dụ: Thao tác Nô ̣i dung Giá trị trả về Khởi ta ̣o () push(7) (7) push(8) ( 7, 8 ) push(5) ( 7, 8, 5 ) pop() ( 8, 5 ) 7 pop() (5) 8 2.2.3 Cài đặt hàng đợi sử dụng mảng Để cài đă ̣t cấ u trúc hàng đơ ̣i chúng ta có thể sƣ̉ du ̣ng mảng hoă ̣c sƣ̉ du ̣ng con trỏ (phầ n này sẽ học sau phần danh sách liên kết):  Ta lƣu các phầ n tƣ̉ của hàng đơ ̣i trong mô ̣t mảng data . Đầu của hàng đợi là phần tử đầ u tiên, và đuôi đƣợc chỉ ra bằng cách sử dụng một biến tail.  push(d) đƣơ ̣c thƣ̣c hiê ̣n mô ̣t cách dễ dàng : tăng tail lên 1 và chèn phần tử vào vị trí đó  pop() đƣơ ̣c thƣ̣c hiê ̣n không hiê ̣u quả : tấ t cả các phầ n tƣ̉ đề u sẽ bi ̣dồ n về đầ u mảng do đó đô ̣ phƣ́c ta ̣p là O(n). Làm thế nào chúng ta có thể cải thiện tình hình này? Thay vì chỉ sƣ̉ du ̣ng mô ̣t biế n chỉ số tail chúng ta sƣ̉ dụng hai biến tail và head, khi cầ n loại bỏ (pop) mô ̣t phầ n tƣ̉ khỏi hàng đơ ̣i chúng ta sẽ tăng biế n head lên 1: Tuy vâ ̣y vẫn còn có vấ n đề , đó là sau n lầ n push() (n là kić h thƣớc mảng) mảng sẽ đầy kể cả trong trƣờng hơ ̣p nó gần nhƣ rỗng về mặt logic. Để giải quyế t vấ n đề này chúng ta sẽ sƣ̉ dụng lại các phần tử ở đầu mảng. Khi push() mô ̣t phầ n tƣ̉ mới tail sẽ đƣơ ̣c tăng lên 1 nhƣng nế u nhƣ nó ở cuố i mảng thì sẽ đă ̣t nó bằ ng 0. Vấ n đề mới nảy sinh ở đây là làm thế nào chúng ta có thể xác định đƣợc khi nào hàng đơ ̣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ự của hàng đợi để giải quyết cho tất cả các thao tác kiể m tra hàng đơ ̣i rỗng, đầ y hoă ̣c lấ y số phầ n tƣ̉ của hàng đơ ̣i. #include #include 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
} 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