TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA CÔNG NGHỆ THÔNG TIN ========
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Nhóm tác giả:
Dương Phương Hùng Lê Thị Nguyên An Hồ Văn Hùng
Quảng Nam, 04-2021
LỜI NÓI ĐẦU
Cấu trúc dữ liệu và giải thuật là một trong những học phần cơ sở của sinh viên ngành Công nghệ thông tin. Cấu trúc dữ liệu và giải thuật đƣợc xem là hai yếu tố quan trọng nhất trong lập trình, đúng nhƣ câu nói nổi tiếng của Niklaus Wirth: Chƣơng trình = Cấu trúc dữ liệu +Giải thuật (Programs = Data Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng nhƣ sử dụng các công cụ lập trình hiện đại.
Cấu trúc dữ liệu có thể đƣợc xem nhƣ là một phƣơng pháp lƣu trữ dữ liệu trong máy tính nhằm sử dụng một cách có hiệu quả các dữ liệu đã lƣu trữ. Và để sử dụng các dữ liệu một cách hiệu quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là hai yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau. Việc lựa chọn một cấu trúc dữ liệu có thể sẽ ảnh hƣởng lớn tới việc lựa chọn áp dụng giải thuật tác động lên cấu trúc dữ liệu đó và ngƣợc lại.
Tài liệu “Giáo trình Cấu trúc dữ liệu và giải thuật” bao gồm 8 chƣơng, trình bày về các cấu trúc dữ liệu và các giải thuật cơ bản nhất trong tin học.
Chƣơng 1 trình bày các khái niệm về thông tin, dữ liệu, mô hình dữ liệu, cấu trúc dữ liệu, mối quan hệ giữa những đại lƣợng trên trong quá trình phân tích và cài đặt giải thuật. Chƣơng 2 trình bày các khái niệm về giải thuật và các đặc trƣng của giải thuật; các phƣơng pháp diễn đạt giải thuật thƣờng dùng trong thực tế; phân tích và đánh giá giải thuật. Chƣơng 3 nêu định nghĩa của giải thuật đệ qui, cách thiết kế giải thuật đệ qui, khử và phân loại đệ qui. Chƣơng 4 trình bày mô hình dữ liệu danh sách, cài đặt danh sách bằng mảng, danh sách liên kết, các phép toán trên danh sách. Chƣơng 5 trình bày mô hình dữ liệu cây, tập trung chủ yếu vào cây nhị phân, các cách cài đặt và thao tác trên cây nhị phân. Chƣơng 6 trình bày các giải thuật sắp cơ bản và sắp xếp nhanh. Chƣơng 7 trình bày các giải thuật tìm kiếm. Chƣơng 8 trình bày 2 mô hình dữ liệu đặc biệt của danh sách là ngăn xếp và hàng đợi, thao tác trên ngăn xếp và hàng đợi cũng nhƣ ứng dụng của mỗi loại vào giải các bài toán trên thực tế.
Cuối mỗi phần đều có các câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm tra kiến thức của mình.
Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể đƣợc biểu diễn và cài đặt bằng bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có đƣợc các phân tích sâu sắc hơn và có kết quả thực tế hơn, nhóm tác giả đã sử dụng ngôn ngữ tựa C để minh hoạ cho các cấu trúc dữ liệu và thuật toán. Do vậy, ngoài các kiến thức cơ bản về tin học, ngƣời đọc cần có kiến thức về ngôn ngữ lập trình C.
Cuối cùng, mặc dù đã hết sức cố gắng nhƣng chắc chắn không tránh khỏi các thiếu sót. Nhóm tác giả rất mong nhận đƣợc sự góp ý của bạn đọc và đồng nghiệp để tài liệu đƣợc hoàn thiện hơn.
Quảng Nam, tháng 3 năm 2021
Nhóm tác giả
1
CHƢƠNG 1. CẤU TRÚC DỮ LIỆU
Làm rõ các khái niệm về thông tin, dữ liệu, mô hình dữ liệu, cấu trúc dữ liệu, mối liên hệ giữa các khái niệm này. Để học tốt chương này, sinh viên cần nắm vững phần lý thuyết và tìm cách phân tích các ví dụ để hiểu rõ lý thuyết.
1.1. Mở đầu
Khi nói đến việc giải quyết bài toán bằng máy tính, ngƣời ta thƣờng chỉ tập trung nhiều vào giải thuật, đó là cách giải bài toán qua bao nhiêu bƣớc, mỗi bƣớc giải quyết công việc gì và cuối cùng thu đƣợc kết quả nhƣ thế nào. Nhƣng ở một khía cạnh không kém phần quan trọng đó là dữ liệu lƣu trữ cho bài toán. Dữ liệu chính là đối tƣợng cần xử lý trên máy tính, chúng biểu diễn thông tin cho bài toán. Không thể nói đến giải thuật mà không xét nó tác động lên dữ liệu nào. Bản thân các phần tử dữ liệu cũng có mối quan hệ với nhau, ngoài ra nếu biết cách tổ chức dữ liệu theo cấu trúc thích hợp sẽ tạo thuận lợi rất nhiều cho xử lý và mang lại hiệu quả cao hơn. Cấu trúc dữ liệu thay đổi tất yếu giải thuật phải thay đổi theo sao cho thích ứng và ngƣợc lại. Điều này, sẽ đƣợc phân tích rõ hơn khi đi vào các chƣơng sau của giáo trình.
1.2. Dữ liệu và kiểu dữ liệu
1.2.1. Thông tin và Dữ liệu
Thông tin(Information): những yếu tố có cấu trúc nhất định nhằm giúp hiểu biết về một vấn đề hay một sự kiện nào đó; có thể nói mọi yếu tố mang lại sự hiểu biết đều là thông tin.
Các cấu trúc vật chất hoặc bất kỳ một dòng năng lƣợng nào có khả năng mang thông tin đƣợc gọi là những vật mang tin hay giá mang tin.
Dữ liệu(Data): hình thức thể hiện của thông tin trong mục đích thu thập, lƣu trữ và xử lý. Nó đƣợc thể hiện bằng các tín hiệu vật lí và là đối tƣợng xử lý của máy tính.
Trong máy tính điện tử, dữ liệu đƣợc biểu diễn (mã hóa) dƣới dạng nhị phân, đó là dãy các ký hiệu 0 và 1. Các trạng thái 0 và 1 dễ dàng đƣợc thể hiện dƣới dạng các tín hiệu vật lý nhƣ nhiễm từ hay không nhiễm từ trong lƣu trữ từ tính, bị đốt cháy hay không bị đốt cháy trong lƣu trữ quang học,… . Ở đây, ta không quan tâm nhiều đến cách biểu diễn của dữ liệu trong máy tính, cũng nhƣ làm thế nào để đọc ghi dữ liệu trên máy tính, mà chỉ quan tâm đến các mô hình toán học để biểu diễn bài toán và các cấu trúc dữ liệu tƣơng ứng đƣợc trang bị trên các ngôn ngữ lập trình thông dụng.
Trong các ngôn ngữ lập trình bậc cao nhƣ Pascal, C, Java,… đều trang bị các kiểu dữ liệu sẵn có hay gọi là tiền định (Điều này đƣợc hiểu là ta không phải đi xây dựng các kiểu dữ liệu này mà ngôn ngữ đã trang bị sẵn). Những kiểu dữ liệu này giúp cho ngƣời lập trình giải quyết các bài toán trong thế giới thực nên ta có thể hiểu kiểu dữ liệu trong ngôn ngữ lập trình là sự trừu tƣợng hóa các tính chất của các đối tƣợng trong thế giới thực. Trong quá trình phân tích để giải quyết bài toán của thế giới thực, ta bỏ qua những những nhân tố, tính chất không cơ bản, chỉ giữ lại những 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ụ, để giải quyết bài toán thông tin quản lý điểm cho lớp đối tƣợng sinh viên, những thuộc tính cần lƣu trữ là mã sinh viên, họ tên, điểm các học phần, có thể xem đây là những thuộc tính cơ bản nhất. Dƣới góc độ lập trình, ta thấy ngôn ngữ lập trình C có trang bị kiểu dữ liệu cấu trúc
2
(Struct) thích hợp để biểu diễn đối tƣợng sinh viên của bài toán. Trong khi đó, ngôn ngữ lập trình Pascal trang bị kiểu bản ghi (Record). Trong mỗi cấu trúc hay bản ghi thì mã sinh viên, họ tên sinh viên có thể đƣợc lƣu dƣới dạng một chuỗi các ký tự, trong khi đó điểm các học phần đƣợc lƣu dƣới dạng các số thực. Một danh sách các sinh viên có thể đƣợc giải quyết bằng mảng các cấu trúc hay bản ghi.
1.2.2. Các kiểu dữ liệu đơn giản
Dữ liệu đƣợc phân thành các kiểu dữ liệu. Kiểu dữ liệu là cách tổ chức dữ liệu để phục vụ cho lƣu trữ và xử lý tính toán, trên đó xác định những giá trị mà kiểu dữ liệu có thể nhận và những phép toán tác động lên nó. Trên ngôn ngữ lập trình bậc cao, các dữ liệu đƣợc phân thành các lớp dữ liệu dựa vào bản chất của dữ liệu. Mỗi lớp dữ liệu tƣơng ứng với một kiểu dữ liệu. Có thể hiểu, một kiểu dữ liệu là một tập hợp các phần tử hay các giá trị có trong nó. Sau đây ta xem xét một số kiểu dữ liệu thông thƣờng đƣợc trang bị trong hầu hết các ngôn ngữ lập trình:
Kiểu số nguyên, đó là tập các giá trị số trên miền số nguyên (Z). Trong đó, có những kiểu dữ liệu chỉ chứa số nguyên dƣơng, có những kiểu vừa âm vừa dƣơng. Độ dài của miền dữ liệu trong mỗi kiểu nguyên cũng khác nhau tùy thuộc vào kích thƣớc vùng nhớ dùng để lƣu trữ nó và đƣợc định nghĩa cụ thể trong mỗi ngôn ngữ lập trình. Ví dụ, kiểu int trong ngôn ngữ C có kích thƣớc 2 byte nên độ dài của miền dữ liệu là 65536 giá trị (216), dùng để lƣu trữ các số nguyên trong miền xác định từ -32768 đến +32767, nhƣng kiểu unsigned int cũng có kích thức 2 byte nhƣng có miền xác định từ 0 đến 65535. Trong thực tiễn, để biểu diễn tuổi của sinh viên, số năm công tác của cán bộ ta có thể dùng kiểu số nguyên dƣơng, nhƣng để biểu diễn các hệ số trong đa thức ta có thể dùng kiểu số nguyên vừa âm vừa dƣơng.
Kiểu số thực, đó là các giá trị số trên tập số thực (R). Ví dụ, để biểu diễn điểm cho các học phần và toàn khóa học của mỗi sinh viên ta thƣờng dùng kiểu số thực.
Kiểu ký tự, đó là các giá trị trên tập các ký tự chuẩn thƣờng dùng trong máy tính ASCII. Mã ASCII chứa 256 mã tƣơng ứng 256 ký tự, thông thƣờng ta hay sử dụng các chữ cái thƣờng, chữ cái hoa, các ký số từ 0 đến 9, các ký hiệu toán học +,-,*,/, ... . Ví dụ, kiểu ký tự dùng để biểu diễn thang điểm chữ của đào tạo theo tín chỉ(A,B,C,D,F)
Kiểu logic, đó là 2 giá trị đúng và sai. Ví dụ, để biểu diễn giới tính nam hay nữ.
Kiểu chuỗi (xâu ký tự), đó là cấu trúc chứa một dãy ký tự. Ví dụ, để biểu diễn họ
tên của một sinh viên.
Tƣơng ứng với mỗi kiểu có các phép toán thích hợp tác động lên kiểu đó. Chẳng hạn, các kiểu dữ liệu số sẽ đi kèm các phép tính số học cộng, trừ, nhân, chia; kiểu dữ liệu ký tự sẽ đi kèm các phép chuyển đổi từ ký tự hoa sang ký tự thƣờng và ngƣợc lại; kiểu chuỗi sẽ đi kèm phép so sánh, phép tách, ghép chuỗi, ... .
Từ những kiểu dữ liệu đơn giản ta có thể xây dựng nên các cấu trúc dữ liệu phức tạp hơn đáp ứng các mô hình toán học phục vụ cho việc giải quyết các bài toán trong thế giới thực.
1.3. Mô hình dữ liệu và Cấu trúc dữ liệu
1.2.1. Mô hình dữ liệu
3
Mô hình dữ liệu (Data Model): Trong quá trình phát triển chƣơng trình, nhất là các chƣơng trình lớn, cần đến hai dạng biểu diễn dữ liệu, biểu diễn trừu tƣợng và biểu diễn cụ thể. Ở giai đoạn thiết kế, cần sử dụng biểu diễn trừu tƣợng của dữ liệu; khi cài đặt, cần biểu diễn cụ thể của dữ liệu. Biểu diễn trừu tƣợng của dữ liệu đƣợc xác định bởi mô hình dữ liệu, đó là mô hình toán học của các đối tƣợng dữ liệu cùng các phép toán thực hiện trên các đối tƣợng đó. Hay nói cách khác, mô hình dữ liệu là các trừu tƣợng dữ liệu đƣợc dùng để mô tả bài toán. Ví dụ, mô hình dữ liệu danh sách, mô hình dữ liệu cây, mô hình dữ liệu tập hợp, mô hình dữ liệu đồ thị... . Mọi khái niệm toán học đều có thể gọi là một mô hình dữ liệu. Trong khoa học máy tính, một mô hình dữ liệu thƣờng có hai mặt:
- Giá trị mà các đối tƣợng thuộc mô hình đó có thể nhận đƣợc. Chẳng hạn, có mô hình dữ liệu chứa các đối tƣợng nhận giá trị số nguyên, cũng có mô hình chứa các đối tƣợng nhận giá trị số thực, ký tự, xâu ký tự,... . Đây là bình diện tĩnh (Static) của mô hình dữ liệu; nó cho biết những giá trị mà một đối tƣợng thuộc kiểu dữ liệu đó có thể nhận. Thành phần tĩnh ở mô hình dữ liệu trong ngôn ngữ lập trình thƣờng đƣợc gọi là hệ thống kiểu (Type system).
- Các phép toán (Operation) trên dữ liệu. Ví dụ: phép cộng, trừ, nhân, chia trên số nguyên, số thực; phép tách, ghép xâu con trên xâu ký tự. Đây là bình diện động (Dynamic) của mô hình; nó cho biết cách thay đổi giá trị và tạo ra giá trị mới.
Khi xây dựng một mô hình dữ liệu với một số xác định các phép toán trên nó ta sẽ có một kiểu dữ liệu trừu tƣợng (Abstract Data Type). Chẳng hạn, kiểu dữ liệu trừu tƣợng ngăn xếp (Stack) là mô hình dữ liệu danh sách dạng đặc biệt với hai phép toán bổ sung và loại bỏ phần tử đƣợc thực hiện trên cùng một đầu của danh danh sách; kiểu dữ liệu trừu tƣợng hàng đợi (Queue) là mô hình dữ liệu danh sách dạng đặc biệt với hai phép toán bổ sung và loại bỏ phần tử đƣợc thực hiện trên hai đầu khác nhau của danh sách.
Biểu 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ể dữ liệu đƣợc xác định bởi các cấu trúc dữ liệu đƣợc trang bị hay chấp nhận trong các ngôn ngữ lập trình.
1.2.2. Cấu trúc dữ liệu
Cấu trúc dữ liệu (Data structure), là những đơn vị cấu trúc hay còn gọi là kết cấu (Construct) của ngôn ngữ lập trình đƣợc dùng để biểu diễn các mô hình dữ liệu. Trên phƣơng diện khác, có thể xem cấu trúc dữ liệu là cách tổ chức dữ liệu đáp ứng yêu cầu lƣu trữ thông tin của bài toán.
Nhƣ đã nêu trên, để cài đặt lƣu trữ thông tin cho đối tƣợng sinh viên, bao gồm một số thuộc tính nhƣ mã sinh viên, họ và tên sinh viên, ngày tháng năm sinh, quê quán, điện thoại liên lạc; ngôn ngữ lập trình C có trang bị kiểu dữ liệu cấu trúc (Struct) trong khi đó ngôn ngữ lập trình Pascal lại trang bị kiểu dữ liệu bản ghi (Record). Nhƣ vậy, các cấu trúc dữ liệu sẽ đƣợc mô tả trong mỗi ngôn ngữ lập trình. Một mô hình dữ liệu, khi đƣợc cài đặt trên những ngôn ngữ khác nhau bởi các cấu trúc dữ liệu khác nhau; cũng có thể cài trên cùng một ngôn ngữ với các cấu trúc dữ liệu khác nhau. Chẳng hạn, mô hình dữ liệu danh sách với các phép toán (thao tác) nhƣ tạo lập danh sách, thêm một phần tử, loại bỏ một phần tử khỏi danh sách, sắp xếp danh sách, duyệt qua danh sách, ... có thể cài đặt bằng cấu dữ liệu kiểu mảng hoặc danh sách liên kết.
4
Hay nói cách khác, từ một biểu diễn trừu tƣợng có thể chuyển thành các biểu diễn cụ thể khác nhau; từ một mô hình dữ liệu có thể biểu diễn bởi các cấu trúc dữ liệu khác nhau.
Có thể nói cấu trúc dữ liệu là cách lƣu trữ, tổ chức dữ liệu ở mức cao hơn, có thứ tự, có hệ thống dựa trên các kiểu dữ liệu cơ sở để dữ liệu có thể đƣợc sử dụng một cách hiệu quả trên các bài toán lớn.
5
TÓM TẮT CHƢƠNG 1
Chương 1 tập trung vào các khái niệm, các thuật ngữ về cấu trúc dữ liệu và những thành phần liên quan. Trong đó, nêu rõ khái niệm về thông tin, dữ liệu, mô hình dữ liệu, cấu trúc dữ liệu. Các kiểu dữ liệu cơ sở, tiền định được trang bị trong hầu hết ngôn ngữ lập trình. Ở đây, cần phân biệt được thông tin và dữ liệu, mô hình dữ liệu và cấu trúc dữ liệu.
6
Bài tập chƣơng 1.
1. Hãy cho biết những thông tin nào trong thực tế có thể biểu diễn bằng kiểu số nguyên trong máy tính.
2. Hãy cho biết những thông tin nào trong thực tế có thể biểu diễn bằng kiểu số thực trong máy tính.
3. Hãy cho biết những thông tin nào trong thực tế có thể biểu diễn bằng kiểu logic trong máy tính.
4. Hãy cho biết những thông tin nào trong thực tế có thể biểu diễn bằng kiểu ký tự trong máy tính.
5. Hãy cho biết những thông tin nào trong thực tế có thể biểu diễn bằng kiểu xâu ký tự (chuỗi) trong máy tính.
6. Hãy nêu vài cấu trúc dữ liệu sẵn có hay đƣợc định nghĩa trƣớc (tiền định) trong các ngôn ngữ lập trình mà các anh (chị) biết.
7. Theo anh(chị) các cấu trúc dữ liệu tiền định trong một ngôn ngữ có đủ đáp ứng mọi yêu cầu về tổ chức dữ liệu của các bài toán trong thực tế không?
7
CHƢƠNG 2. GIẢI THUẬT
Trình bày các khái niệm về giải thuật hay thuật toán và phương pháp tinh chỉnh từng bước chương trình được thể hiện qua ngôn ngữ diễn đạt giải thuật. Chương này cũng nêu phương pháp phân tích và đánh giá một thuật toán, các khái niệm liên quan đến việc tính toán thời gian thực hiện chương trình.
Để học tốt chương này, sinh viên cần nắm vững phần lý thuyết và tìm các ví dụ tương tự để thực hành phân tích, thiết kế, và đánh giá giải thuật.
2.1. Giải thuật
2.1.1. Giải thuật
Trong thực tế, khi gặp phải một vấn đề cần giải quyết, việc đầu tiên là tìm ra phƣơng pháp để giải quyết vấn đề, tiếp theo mới tiến hành theo các bƣớc của phƣơng pháp đã đề ra. Trong tin học cũng vậy, mỗi bài toán cần đƣa ra lời giải trƣớc khi bắt tay vào viết chƣơng trình điều khiển máy tính thực hiện. Thuật ngữ “Giải thuật ” đƣợc dùng để chỉ lời giải để giải bài toán trong tin học.
Giải thuật(Algorithms) hay thuật toán là một dãy các các bƣớc (các bƣớc) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số đối tƣợng nhằm giải quyết yêu cầu của một vấn đề nào đó, sao cho sau một số hữu hạn bƣớc thực hiện ta đạt đƣợc kết quả mong muốn (thỏa mãn yêu cầu đặt ra).
Chẳng hạn, để đăng ký một hộp thư điện tử bằng máy vi tính, ta có giải thuật:
Bƣớc 1: Bật máy vi tính,
Bƣớc 2: Kết nối vào mạng Internet,
Bƣớc 3: Tìm dịch vụ cung cấp thƣ điện tử mình muốn (Gmail, Yahoo mail,…),
Bƣớc 4: Tiến hành đăng ký theo hƣớng dẫn (tên đăng nhập, mật khẩu, họ tên đầy đủ, ngày sinh, điện thoại,…) đáp ứng yêu cầu của từng dịch vụ thƣ điện tử,
Bƣớc 5. Hoàn tất và sử dụng hộp thƣ.
Hay giải thuật để giải phương trình bậc nhất ax+b=0 có thể trình bày như sau:
Bƣớc 1: Nhập a, nhập b (cung cấp a và b);
Bƣớc 2: Kiểm tra điều kiện, nếu a=0 thì qua bƣớc 3, ngƣợc lại (nghĩa là a≠0) thì qua bƣớc 4;
Bƣớc 3: Kiểm tra điều kiện, nếu b=0 thì thông báo phƣơng trình có vô số nghiệm và qua bƣớc 5, ngƣợc lại (b≠0) thì thông báo phƣơng trình vô nghiệm và qua bƣớc 5;
Bƣớc 4: Thông báo phƣơng trình có nghiệm x= - b/a;
Bƣớc 5: Dừng.
Trong một giải thuật, một bƣớc có thể lặp đi lặp lại nhiều lần, tuy nhiên đối với bất kỳ bộ dữ liệu đầu vào nào, giải thuật phải kết thúc sau khi thực thi một số hữu hạn bƣớc.
Nhƣ đã nói ở trên, mỗi bƣớc trong giải thuật phải có ngữ nghĩa rõ ràng và có thể
8
đƣợc thực thi trong một khoảng thời gian hữu hạn. Tuy nhiên, đôi khi một lệnh có ngữ nghĩa rõ ràng đối với ngƣời này nhƣng lại không rõ ràng đối với ngƣời khác.
Ngoài ra, thƣờng rất khó để chứng minh một lệnh có thể đƣợc thực hiện trong 1 khoảng hữu hạn thời gian. Thậm chí, kể cả khi biết rõ ngữ nghĩa của các lệnh, cũng khó để có thể chứng minh là với bất kỳ bộ dữ liệu đầu vào nào, thuật toán sẽ dừng.
2.1.2. Các đặc trưng của giải thuật
Dữ liệu đầu vào xác định: Một giải thuật nên có không hoặc nhiều hơn dữ liệu đầu vào đã xác định.
Kết quả đầu ra: Một giải thuật nên có một hoặc nhiều dữ liệu đầu ra đã xác định, và nên kết nối với kiểu kết quả bạn mong muốn.
Tính dừng: Các giải thuật phải kết thúc sau một số hữu hạn các bƣớc.
Tính xác định: Giải thuật nên rõ ràng và không mơ hồ. Mỗi một giai đoạn (hay mỗi bƣớc) nên rõ ràng và chỉ mang một mục đích nhất định.
Tính đúng đắn: Trong cùng một điều kiện với cùng bộ dữ liệu vào thì cho ra cùng một kết quả.
Tính hiệu quả: Một giải thuật nên là có thể thi hành đƣợc với các nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong điều kiện thời gian và tài nguyên cho phép.
Tính phổ biến: Một giải thuật có tính phổ biến nếu giải thuật này có thể giải quyết đƣợc một lớp các vấn đề tƣơng tự.
Độc lập: Một giải thuật nên có các chỉ thị độc lập với bất kỳ ngôn ngữ lập trình nào.
2.1.3. Ngôn ngữ diễn đạt giải thuật
Có nhiều cách để diễn đạt giải thuật, thông thƣờng ngƣời ta hay dùng ngôn ngữ tự nhiên, lƣu đồ giải thuật hay tựa một ngôn ngữ lập trình.
2.1.3. 1. Ngôn ngữ tự nhiên
Dùng từ ngữ tự nhiên trong ngôn ngữ giao tiếp hằng ngày để diễn đạt giải thuật. Ví dụ, để diễn đạt giải thuật của bài toán đặt ra là nhập vào hai số a, b từ bàn phím rồi in kết quả của a cộng b; ngôn ngữ tự nhiên diễn đạt nhƣ sau:
Bƣớc 1: Bắt đầu
Bƣớc 2: Nhập vào hai số a,b
Bƣớc 3: Lấy a cộng cho b đƣợc kết quả gán cho c
Bƣớc 4: In ra c
Bƣớc 5: Kết thúc Lấy một ví dụ khác, để trình bày giải thuật giải phƣơng trình bậc 2: ax2+bx+c=0
với a≠0 trong miền số thực ta diễn đạt nhƣ sau:
Bƣớc 1: Bắt đầu
9
Bƣớc 2: Nhập 3 số a,b,c;
Bƣớc 3: Tính delta=b2-4ac;
Bƣớc 4: Nếu delta<0 thì thông báo phƣơng trình vô nghiệm và qua bƣớc 7, ngƣợc
lại (delta>=0) thì qua bƣớc 5;
Bƣớc 5: Nếu delta=0 thì thông báo phƣơng trình có nghiệm kép x= - b/2a và qua
bƣớc 7, ngƣợc lại (delta>0) thì qua bƣớc 6;
√
√
Bƣớc 6: Thông báo phƣơng trình có 2 nghiệm phân biệt:
và
Qua bƣớc 7;
Bƣớc 7: Kết thúc.
2.1.3. 2. Lưu đồ giải thuật
Dùng các hình và các chỉ dẫn để diễn đạt giải thuật theo qui ƣớc sau:
- Bắt đầu và kết thúc:
- Nhập xuất dữ liệu:
- Điều kiện và rẽ nhánh:
- Thực hiện phép toán:
- Chỉ dẫn luồng:
Ví dụ: Lƣu đồ diễn đạt giải thuật của bài toán tính tổng của 2 số a,b ở trên nhƣ sau:
Bắt đầu
Nhập 2 số a,b
c=a+b
In ra c
Kết thúc
10
Bên dƣới là lƣu đồ giải thuật của bài toán giải phƣơng trình bậc 2 đã nêu:
Bắt đầu
Nhập a,b,c
Tính delta=b2-4ac
Delta <0
Phƣơng trình vô nghiệm
Delta =0
Phƣơng trình có nghiệm kép: x=-b/2a;
𝑏 √𝑑𝑒𝑙𝑡𝑎
𝑏 √𝑑𝑒𝑙𝑡𝑎
Phƣơng trình có 2 nghiệm phân biệt:
𝑎
𝑎
Kết thúc
𝑥 và 𝑥
11
2.1.3. 3. Ngôn ngữ lập trình
Để diễn đạt giải thuật bằng ngôn ngữ lập trình ngƣời ta có xu hƣớng chọn tựa một ngôn ngữ lập trình cơ bản nào đó; chẳng hạn, tựa ngôn ngữ lập trình C hoặc tựa ngôn ngữ lập trình Pascal. Sở dĩ không tuân thủ đầy đủ, hoàn toàn theo một ngôn ngữ lập trình nào đó vì giải thuật cần một mức độ linh hoạt nhất định, không quá gò bó, không bắt chặt nhiều về cú pháp nhƣng cũng gần gũi với các ngôn ngữ chuẩn, để khi dễ dàng chuyển đổi cài đặt.
Với bài toán tính tổng 2 số a,b nêu trên, giải thuật tựa ngôn ngữ C trình bày nhƣ sau:
Main()
{
// a,b,c là các số
scanf(a,b); // nhập vào 2 số a,b;
c=a+b; // lấy a + b đƣợc kết quả gán cho c
printf(c); // in ra c
}
Hay với bài toán giải phƣơng trình bậc 2 ở trên ta có giải thuật sau:
Main()
{
// a,b,c là các hệ số của phƣơng trình
scanf(a,b,c); // nhập vào 3 số a,b,c;
delta=b-4ac; // tính delta
if(delta<0)
printf(“Phƣơng trình vô nghiệm”);
else
if(delta==0)
printf(“Phƣơng trình có nghiệm kép x=”, -b/2a);
else
{
printf(“ Phƣơng trình có 2 nghiệm phân biệt:”);
printf(“ x1=”, (-b+sqrt(delta))/2a);
printf(“ x2=”, (-b-sqrt(delta))/2a);
}
}
12
Trong tài liệu này về sau sẽ dùng ngôn ngữ tựa C để biểu diễn các giải thuật.
2.2. Chƣơng trình
Chƣơng trình là một dãy các lệnh (chỉ thị máy tính), là sự cụ thể hóa giải thuật bằng một ngôn ngữ lập trình. Để chƣơng trình có thể dịch và chạy trên máy tính, ngƣời lập trình cần nắm rõ các yêu cầu của ngôn ngữ lập trình. Mỗi ngôn ngữ đều có qui định chặt chẽ về cấu trúc của chƣơng trình, kiểu dữ liệu, cấu trúc lệnh,… .
Sự khác nhau giữa chƣơng trình và giải thuật ở chỗ khi phân tích và thiết kế thuật toán ta dừng lại ở mức “thô”, không bị bó buộc bởi ngôn ngữ lập trình nào, ngƣời đọc thuật toán hiểu đƣợc đƣợc cách giải quyết bài toán, còn lựa chọn ngôn ngữ lập trình nào để cài đặt giải thuật là việc của lập trình viên.
2.3. Từ giải thuật đến chƣơng trình
- Mô đun hóa và việc giải quyết bài toán là việc phân chia bài toán lớn thành các bài toán nhỏ. Việc tổ chức lời giải của bài toán sẽ đƣợc thể hiện theo một cấu trúc phân cấp, đó chính là chiến thuật "chia để trị". Thiết kế "Top - Down" là một trong những cách thiết kế theo kiểu chia để trị.
- Phƣơng pháp tinh chỉnh từng bƣớc là thiết kế giải thuật gắn liền với lập trình. Đầu tiên giải thuật đƣợc trình bày bằng ngôn ngữ tự nhiên phản ánh ý chính của công việc cần làm, sau đó các ý chính sẽ đƣợc chi tiết hóa dần, hƣớng về ngôn ngữ lập trình mà ta đã chọn.
2.4. Phân tích và đánh giá giải thuật
- Đặt vấn đề : khi xây dựng giải thuật và chƣơng trình tƣơng ứng để giải bài toán, một số yêu cầu về phân tích đƣợc đặt ra nhƣ :
+ Tính đúng đắn của giải thuật: có thể hiện lời giải đúng cho bài toán đặt ra hay không?
+ Tính đơn giản: đó là dễ hiểu, dễ lập trình, dễ chỉnh sửa.
- Phân tích thời gian thực hiện giải thuật: đó chính là cơ sở để đánh giá độ tối ƣu của giải thuật. Thời gian thực hiện một giải thuật phụ thuộc vào nhiều yếu tố nhƣ: kích thƣớc của dữ liệu, kiểu lệnh, tốc độ xử lí của máy tính, ngôn ngữ viết chƣơng trình và chƣơng trình dịch,... Tuy nhiên ở đây ta không xét đến các yếu tố mang tính không đồng đều giữa các loại máy tính, đó chỉ là các yếu tố bên ngoài; mà ta cần quan tâm đến kích thƣớc dữ liệu vào và số lần thực hiện phép toán cơ bản trong giải thuật.
2.4.1. Độ phức tạp tính toán của giải thuật
Hàm F(n) = O(g(n)) đƣợc gọi là có cấp g(n) nếu tồn tại hằng số c và một số n0 sao cho:
F(n) cg(n) với mọi n n0 Nếu thời gian thực hiện một giải thuật là T(n)=cn2, với c là hằng số thì ta nói độ phức tạp tính toán của giải thuật này có cấp n2 và ký hiệu T(n)=O(n2). Ngƣời ta gọi O là ký pháp chữ o lớn, dùng trong đánh giá độ phức tạp thuật toán.
2.4.2. Xác định độ phức tạp tính toán
13
Giả sử T1(n), T2(n) lần lƣợt là thời gian thực hiện của đoạn chƣơng trình P1, P2. T1(n) = O(f(n)); T2(n) = O(g(n)). Ta có :
Quy tắc tổng: thời gian thực hiện hết P1 rồi đến P2 (tuần tự) sẽ là T1(n) + T2(n) = O(max(f(n), g(n))).
Quy tắc nhân: thời gian thực hiện của P1 lồng trong P2 hoặc ngƣợc lại (lồng nhau) sẽ là T1(n)*T2(n) = O(f(n)*g(n)).
Để minh họa cho việc phân tích và tính toán thời gian thực hiện của 1 chƣơng trình, ta sẽ xem xét một thuật toán đơn gian để sắp xếp các phần tử của một tập hợp, đó là thuật toán sắp xếp kiểu đổi chỗ (Exchange sort).
Thuật toán nhƣ sau :
Doicho (a[n])
{
// Dãy khóa a, có n phần tử chạy từ a[1] đến a[n]
1. for (i = 1; i 2. for (j = n; j>= i+1; j--) 3. if (a[j-1] > a[j]) { // Đổi chỗ cho a[j] và a[j-1] temp = a[j-1]; 4. a[j-1] = a[j]; 5. a[j]=temp; 6. } } Trong thuật toán này, mỗi lần duyệt của vòng lặp trong (biến duyệt j) sẽ làm “nổi” lên trên phần tử nhỏ nhất trong các phần tử đƣợc duyệt. Dễ thấy rằng kích thƣớc dữ liệu vào chính là số phần tử đƣợc sắp n. Mỗi lệnh gán
sẽ có thời gian thực hiện cố định, không phụ thuộc vào n, do vậy, các lệnh 4, 5, 6 sẽ có
thời gian thực hiện là O(1), tức thời gian thực hiện là hằng số. Theo quy tắc cộng thì
tổng thời gian thực hiện cả 3 lệnh là O(max(1, 1, 1)) = O(1). Tiếp theo ta sẽ xem xét thời gian thực hiện của các lệnh lặp và rẽ nhánh. Lệnh if
kiểm tra điều kiện để thực hiện nhóm lệnh gán 4, 5, 6. Việc kiểm tra điều kiện sẽ có
thời gian thực hiện là O(1). Ngoài ra, chúng ta chƣa biết đƣợc là điều kiện có thoả mãn
hay không, tức là không biết đƣợc nhóm lệnh gán có đƣợc thực hiện hay không. Do
vậy, ta giả thiết trƣờng hợp xấu nhất là tất cả các lần kiểm tra điều kiện đều thoả mãn,
và các lệnh gán đƣợc thực hiện. Nhƣ vậy, toàn bộ lệnh If sẽ có thời gian thực hiện là
O(1). Tiếp tục xét từ trong ra ngoài, ta xét đến vòng lặp trong (biến duyệt j). Số bƣớc lặp của vòng lặp này là n-i, do đó theo quy tắc nhân cấp độ tăng thì tổng thời gian thực hiện của vòng lặp này và lệnh if là O((n-i)*1) = O(n-i). Cuối cùng, ta xét vòng lặp ngoài cùng (biến duyệt i). Vòng lặp này đƣợc thực hiện (n-1) lần; do đó, tổng thời gian thực hiện của chƣơng trình là: O((n-i)*(n-1))=O(n2) Nhƣ vậy, thời gian thực hiện giải thuật sắp xếp nổi bọt là tỷ lệ với n2 a c ng c thể tính độ phức tạp tính toán ng việc tính s l n th c hiện của
phép toán cơ ản. Phép toán cơ ản là phép toán mà s l n th c hiện của n không
ít hơn các phép toán khác trong chương trình. Một số quy tắc chung trong việc phân tích và tính toán thời gian thực hiện chƣơng trình: Thời gian thực hiện các lệnh gán, đọc, ghi,… luôn là O(1). Thời gian thực hiện chuỗi tuần tự các lệnh đƣợc xác định theo quy tắc cộng
cấp độ tăng. Có nghĩa là thời gian thực hiện của cả nhóm lệnh tuần tự đƣợc tính là thời
gian thực hiện của lệnh lớn nhất. Thời gian thực hiện lệnh rẽ nhánh if đƣợc tính bằng thời gian thực hiện các
lệnh khi điều kiện kiểm tra đƣợc thoả mãn và thời gian thực hiện việc kiểm tra điều
kiện. Thời gian thực hiện việc kiểm tra điều kiện luôn là O(1). Thời gian thực hiện 1 vòng lặp đƣợc tính là tổng thời gian thực hiện các lệnh
ở thân vòng lặp qua tất cả các bƣớc lặp và thời gian để kiểm tra điều kiện dừng
(thƣờng là O(1)). Thời gian thực hiện này thƣờng đƣợc tính theo quy tắc nhân cấp độ
tăng số lần thực hiện bƣớc lặp và thời gian thực hiện các lệnh ở thân vòng lặp. Các
vòng lặp phải đƣợc tính thời gian thực hiện một cách riêng rẽ. TÓM TẮT CHƢƠNG 2 Chương 2 trình bày các khái niệm về giải thuật và các thành phần liên quan đến
giải thuật. Các đặc trưng của giải thuật, các cách diễn đạt một giải thuật và chọn biểu
diễn giải thuật bằng tựa ngôn ngữ C làm chính, xuyên suốt cuốn giáo trình. Chương
này cũng trình bày cách đánh giá một giải thuật. BÀI TẬP CHƢƠNG 2 1. Tìm thêm các ví dụ minh họa mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Sau đó hãy xây dựng giải thuật để giải các bài toán sau: a. Tìm phần tử thứ n của dãy Fibonacci b. Tìm phần tử lớn nhất trong mảng A gồm n số nguyên c. Kiểm tra xem số n nguyên dƣơng bất kì có phải là số nguyên tố không? d. Tìm tất cả các số tự nhiên có 2 chữ số sao cho khi đảo trật tự của 2 số đó sẽ
tạo ra một số nguyên tố cùng nhau với nó. Ví dụ: 13 và 31, 17 và 71, … 2. Việc chia bài toán ra thành các bài toán nhỏ có những thuận lợi gì? 3. Hãy nêu một giải thuật mà độ phức tạp tính toán của nó là O(1), và một giải thuật có độ phức tạp O(n). 4. Hãy tính độ phức tạp theo ký pháp O cho các đọan chƣơng trình sau : a) sum=0; for (i=1; i<= n; i++) { scanf(x); sum=sum+x; } b) for (i=1; i<=n; i++) for j=1; j<=n; j++) { c[i,j]=0; for (k=1; k<=n; k++) c[i,j]=c[i,j]+a[i,k]*b[k,j]; } c) for (i=1; i for (j=i+1; j<=n; j++) if (X[i]>X[j]) { temp=X[j]; X[j]=X[i]; X[i]=temp; } } d/ scanf(X); S = 1; For (i=1; i<=n; i++ ) { P = 1; For (j=1; j<=i; j++) p = p * X / j; S = S + P; } e/ Scanf(X); S = 1; P =1; For(i=1; i<=n; i++) { P = P * X / i; S = S + P; } f/ for (i=2; i<=n; i++) { X = A[i]; A[0] = X; j = i - 1; While (X.key < A[j].key) { A[j+1] = A[j]; j = j - 1; } A[j+1] = X; } g/ x=0 for (i=1; i for (j=1; j<=n; j++) for (k=1; k<=j; k++) CHƢƠNG 3. GIẢI THUẬT ĐỆ QUI Chương này trình bày các khái niệm về định nghĩa đệ qui, chương trình đệ qui.
Ngoài việc trình bày các ưu điểm của chương trình đệ qui, các tình huống không nên
sử dụng đệ qui cũng được đề cập cùng với các ví dụ minh hoạ. Chương này cũng đề cập và phân tích một số thuật toán đệ qui tiêu biểu và kinh điển như bài toán tháp Hà nội, các thuật toán quay lui .v.v Để học tốt chương này, sinh viên cần nắm vững phần lý thuyết. Sau đó, nghiên
cứu kỹ các phân tích thuật toán và thực hiện chạy thử chương trình. Có thể thay đổi
một số điểm trong chương trình và chạy thử để nắm kỹ hơn về thuật toán. Ngoài ra,
sinh viên cũng có thể tìm các bài toán tương tự để phân tích và giải quyết bằng
chương trình 3.1. Khái niệm về đệ qui Đệ qui là một khái niệm cơ bản trong toán học và khoa học máy tính. Một đối
tƣợng đƣợc gọi là đệ qui nếu nó hoặc một phần của nó đƣợc định nghĩa thông qua khái
niệm về chính nó. Ví dụ: 1. Ngƣời là con của 2 ngƣời khác 2. Số n đƣợc gọi là số tự nhiên khi số (n-1) là số tự nhiên 3. Giai thừa(n) đƣợc tính bằng (n*giai thừa (n-1)) 4…. Một s ví dụ điển hình về việc định nghĩa ng đệ qui là: 1- Định nghĩa số tự nhiên: - 0 là số tự nhiên. - Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên. Nhƣ vậy, bắt đầu từ phát biểu “0 là số tự nhiên”, ta suy ra 0+1=1 là số tự nhiên. Tiếp theo 1+1=2 là số tự nhiên, … . 2- Định nghĩa xâu ký tự bằng đệ qui: - Xâu rỗng là 1 xâu ký tự. - Một chữ cái bất kỳ ghép với 1 xâu sẽ tạo thành 1 xâu mới. Từ phát biểu “Xâu rỗng là 1 xâu ký tự”, ta ghép bất kỳ 1 chữ cái nào với xâu
rỗng đều tạo thành xâu ký tự. Nhƣ vậy, chữ cái bất kỳ có thể coi là xâu ký tự. Tiếp tục
ghép 1 chữ cái bất kỳ với 1 chữ cái bất kỳ cũng tạo thành 1 xâu ký tự, … . 3- Định nghĩa n giai thừa: - Khi n=0, định nghĩa 0!=1 - Khi n>0, định nghĩa n!=(n-1)! * n Nhƣ vậy, khi n=1, ta có 1!=0! *1 = 1*1=1. Khi n=2, ta có 2!=1! *2=1*2=2,… . Trong lĩnh vực lập trình, một chƣơng trình con gọi là đệ qui nếu trong chƣơng
trình có lời gọi chính nó. Điều này, thoạt tiên, nghe có vẻ hơi vô lý. Một chƣơng trình
không thể gọi mãi chính nó, vì nhƣ vậy sẽ tạo ra một vòng lặp vô hạn. Trên thực tế, một chƣơng trình đệ qui trƣớc khi gọi chính nó bao giờ cũng có một
thao tác kiểm tra điều kiện dừng. Nếu điều kiện dừng thỏa mãn, chƣơng trình sẽ
không gọi chính nó nữa, và quá trình đệ qui chấm dứt. Trong các ví dụ ở trên, ta đều
thấy có các điểm dừng. Chẳng hạn, trong ví dụ thứ nhất, nếu k = 0 thì có thể suy ngay
k là số tự nhiên, không cần tham chiếu xem k-1 có là số tự nhiên hay không. Nhìn chung, các giải thuật đệ qui đều có các đặc điểm sau: Giải thuật này có gọi lại nó một cách trực tiếp hay gián tiếp, Khi gọi nó, mục đích là để giải quyết một vấn đề tƣơng tự, nhƣng nhỏ hơn, hay nói cách khác gọi nó lại với kích thƣớc bài toán nhỏ hơn. Vấn đề nhỏ hơn này, cho tới một lúc nào đó, sẽ đơn giản tới mức có thể tự
giải quyết đƣợc mà không cần gọi tới chính nó nữa. Trƣờng hợp này gọi là suy biến
hay dừng đệ qui. Ƣu điểm của chƣơng trình đệ qui cũng nhƣ định nghĩa bằng đệ qui là có thể thực
hiện một số lƣợng lớn các thao tác tính toán thông qua một đoạn chƣơng trình ngắn
gọn (thậm chí không có vòng lặp, hoặc không tƣờng minh để có thể thực hiện bằng các
vòng lặp) hay có thể định nghĩa một tập hợp vô hạn các đối tƣợng thông qua một số
hữu hạn lời phát biểu. Thông thƣờng, một chƣơng trình đƣợc viết dƣới dạng đệ qui khi
vấn đề cần xử lý có thể đƣợc giải quyết bằng đệ qui. Tức là vấn đề cần giải quyết có thể đƣa đƣợc về vấn đề tƣơng tự, nhƣng đơn giản
hơn. Vấn đề này lại đƣợc đƣa về vấn đề tƣơng tự nhƣng đơn giản hơn nữa,…, cho đến
khi đơn giản tới mức có thể trực tiếp giải quyết đƣợc ngay mà không cần đƣa về vấn
đề đơn giản hơn nữa Giải thuật đệ qui: Nếu lời giải của một bài toán T đƣợc thực hiện bằng lời giải của bài toán T' có
dạng giống nhƣ T nhƣng nhỏ hơn về kích thƣớc (dữ liệu), thì đó là lời giải đệ qui. Giải
thuật tƣơng ứng với với lời giải nhƣ vậy gọi là giải thuật đệ qui. Ví dụ: Giải thuật tìm từ trong từ điển sau là giải thuật đệ qui : SEARCH(dict, word) {//dict là từ điển, word là từ cần tìm trong từ điển 1. IF dict chỉ còn 1 trang tìm word trong trang này; ELSE { 2. Mở dict vào trang giữa; Xác định xem nửa nào của dict chứa word; IF word nằm ở nửa trƣớc (dict1) của dict SEARCH(dict1, word); ELSE SEARCH(dict2, word);//dict2 là nửa sau của cái đang tìm } 3. Return; } Điều kiện để có thể viết một chƣơng trình đệ qui Nhƣ đã nói ở trên, để chƣơng trình có thể viết dƣới dạng đệ qui thì vấn đề cần xử
lý phải đƣợc giải quyết 1 cách đệ qui. Ngoài ra, ngôn ngữ dùng để viết chƣơng trình
phải hỗ trợ đệ qui. Để có thể viết chƣơng trình đệ qui chỉ cần sử dụng ngôn ngữ lập
trình có hỗ trợ chƣơng trình con (hàm, thủ tục). Các ngôn ngữ lập trình thông dụng
hiện nay đều hỗ trợ kỹ thuật này, do vậy vấn đề công cụ để tạo các chƣơng trình đệ qui
không phải là vấn đề cần phải xem xét. Tuy nhiên, cũng nên lƣu ý rằng khi một giải thuật đệ qui gọi đến chính nó, một
bản sao của tập các đối tƣợng đƣợc sử dụng trong giải thuật này nhƣ các biến, hằng,
các giải thuật con, .v.v. cũng đƣợc tạo ra. Do vậy, nên hạn chế việc khai báo và sử
dụng các đối tƣợng này trong giải thuật đệ qui nếu không cần thiết nhằm tránh lãng phí
bộ nhớ, đặc biệt đối với các lời gọi đệ qui đƣợc gọi đi gọi lại nhiều lần. Các đối tƣợng
cục bộ của 1 giải thuật đệ qui khi đƣợc tạo ra nhiều lần, mặc dù có cùng tên, nhƣng do
khác phạm vi nên không ảnh hƣởng gì đến chƣơng trình. Các đối tƣợng đó sẽ đƣợc
giải phóng khi giải thuật chứa nó kết thúc. Nếu trong một giải thuật có lời gọi đến chính nó thì ta gọi đó là đệ qui trực tiếp.
Còn trong trƣờng hợp một giải thuật có một lời gọi giải thuật khác, giải thuật này lại
gọi đến giải thuật ban đầu thì đƣợc gọi là đệ qui gián tiếp. Nhƣ vậy, trong chƣơng trình
khi nhìn vào có thể không thấy ngay sự đệ qui, nhƣng khi xem xét kỹ hơn thì sẽ nhận
ra 3.2. Thiết kế giải thuật đệ qui Ví dụ 1. Tính N! Theo định nghĩa : n! = 1 nếu n=0; ngƣợc lại, n! = (n-1)! * n. giaithua (n) { if (n==0) return 1; else return giaithua(n-1) * n; } Trong chƣơng trình trên, điểm dừng của thuật toán đệ qui là khi n bằng 0. Khi
đó, giá trị của hàm giaithua(0) có thể tính đƣợc ngay lập tức mà không cần gọi hàm đệ
qui khác. Nếu điều kiện dừng không thỏa mãn, sẽ có một lời gọi đệ qui hàm giai thừa
với tham số là n-1, nhỏ hơn tham số ban đầu 1 đơn vị (tức là bài toán tính n! đã đƣợc
qui về bài toán đơn giản hơn là tính (n-1)!). Ví dụ 2. ìm ước s chung lớn nhất của 2 s a, b Ta có công thức biểu diễn toán học: b, nếu (a % b = =0) (suy biến hay điều kiện dừng) UCLN(a,b) = UCLN(b, a% b) nếu (a% b!=0) Ƣớc chung lớn nhất (UCLN) của 2 số nguyên dƣơng m, n là 1 số k lớn nhất sao
cho m và n đều chia hết cho k. Một phƣơng pháp đơn giản nhất để tìm UCLN của m
và n là duyệt từ số nhỏ hơn trong 2 số m, n cho đến 1, ngay khi gặp số nào đó mà m và
n đều chia hết cho nó thì đó chính là UCLN của m, n. Tuy nhiên, phƣơng pháp này
không phải là cách tìm UCLN hiệu quả. Cách đây hơn 2000 năm, Euclid đã phát minh ra một giải thuật tìm UCLN của 2
số nguyên dƣơng m, n rất hiệu quả. Ý tƣởng cơ bản của thuật toán này cũng tƣơng tự
nhƣ ý tƣởng đệ qui, tức là đƣa bài toán về 1 bài toán đơn giản hơn. Cụ thể, giả sử m
lớn hơn n, khi đó việc tính UCLN của m và n sẽ đƣợc đƣa về bài toán tính UCLN của
m mod n và n vì UCLN(m, n) = UCLN(n, m mod n). Thuật toán đƣợc cài đặt nhƣ sau: UCLN(m, n) { // m,n là 2 số tự nhiên, m>=n if (n==0) return m; else return UCLN(n, m % n); } Điểm dừng của thuật toán là khi n=0. Khi đó đƣơng nhiên là UCLN của m và 0
chính là m, vì 0 chia hết cho mọi số. Khi n khác 0, lời gọi đệ qui UCLN(n, m% n)
đƣợc thực hiện. Chú ý rằng ta giả sử m >= n trong giải thuật tính UCLN, do đó, khi
gọi đệ qui ta gọi UCLN (n, m% n) để đảm bảo thứ tự các tham số vì n bao giờ cũng
lớn hơn phần dƣ của phép m cho n. Sau mỗi lần gọi đệ qui, các tham số của giải thuật
sẽ nhỏ dần đi, và sau 1 số hữu hạn lời gọi tham số nhỏ hơn sẽ bằng 0. Đó chính là
điểm dừng của thuật toán. Ví dụ, để tính UCLN của 130 và 45, ta gọi Giải thuật UCLN(130, 45). Khi đó, các Giải thuật sau sẽ lần lƣợt đƣợc gọi: UCLN(130, 45) 130 chia 45 dư 40, do đó tiếp theo gọi UCLN(45, 40) 45 chia 40 dư 5, do đó tiếp theo gọi UCLN(40, 5) 40 chia 5 dư 0, do đó tiếp theo gọi UCLN(5, 0) tham số thứ 2 = 0, do đó kết quả là tham số thứ nhất, tức là 5. Nhƣ vậy, ta tìm đƣợc UCLN của 130 và 45 là 5 chỉ sau 4 lần gọi giải thuật tìm UCLN(m,n). c) Bài toán " Tháp Hà Nội " Giả s c 3 chi c c c đư c đánh k hiệu là C và n chi c đĩa kích thước khác nhau. an đ u n đĩa đư c đặt c c lớn dưới nh tr n. chu ển n đĩa từ c c sang c c C m i l n ch chu ển 1 đĩa sao cho
không c tình trạng đĩa lớn n m tr n đĩa nh và đư c phép dùng c c trung gian . * Với n=1, có thể thực hiện yêu cầu bài toán bằng cách chuyển trực tiếp đĩa 1 từ cọc A sang cọc C. * Với n=2, đánh số cho từng đĩa là đĩa 1, đĩa 2, đĩa 1< đĩa 2 về mặt kích thƣớc, giải thuật có thể trình bày nhƣ sau: Chuyển đĩa 1 từ cọc A sang cọc trung gian B. Chuyển đĩa 2 từ cọc A sang cọc đích C. Cuối cùng, chuyển đĩa 1 từ cọc trung gian B sang cọc đích C. Nhƣ vậy, cả 2 đĩa đã đƣợc chuyển sang cọc đích C và không có tình huống nào đĩa lớn nằm trên đĩa nhỏ. * Với n=3, đánh số cho từng đĩa là đĩa 1, đĩa 2, đĩa 3; đĩa 1< đĩa 2< đĩa 3 về mặt kích thƣớc, giải thuật có thể trình bày nhƣ sau: Chuyển đĩa 1 từ cọc A sang cọc C. Chuyển đĩa 2 từ cọc A sang cọc B. Chuyển đĩa 1 từ cọc C sang cọc B. Chuyển đĩa 3 từ cọc A sang cọc C. Chuyển đĩa 1 từ cọc B sang cọc A. Chuyển đĩa 2 từ cọc B sang cọc C. Chuyển đĩa 1 từ cọc A sang cọc C. Nhƣ vậy, cả 3 đĩa đã đƣợc chuyển sang cọc đích C và không có tình huống nào đĩa lớn nằm trên đĩa nhỏ. Với n > 3, giả sử ta đã có cách chuyển n-1 đĩa, ta thực hiện nhƣ sau: Lấy cọc đích C làm cọc trung gian để chuyển n-1 đĩa bên trên sang cọc B. Chuyển đĩa dƣới cùng (đĩa thứ n) sang cọc đích C Lấy cọc ban đầu A làm cọc trung gian để chuyển n-1 đĩa từ cọc trung gian B sang cọc đích C Có thể minh họa quá trình chuyển này nhƣ sau: Trạng thái ban đầu Bƣớc 1: Chuyển n-1 đĩa bên trên từ cọc A sang cọc B, sử dụng cọc C làm cọc trung gian Bƣớc 2: Chuyển đĩa dƣới cùng từ cọc A thẳng sang cọc C Bƣớc 3: Chuyển n-1 đĩa từ cọc B sang cọc C sử dụng cọc A làm cọc trung gian Nhƣ vậy, ta thấy toàn bộ n đĩa đã đƣợc chuyển từ cọc A sang cọc C và không vi
phạm bất cứ điều kiện nào của bài toán. Ở đây, ta thấy rằng bài toán chuyển n đĩa đã
đƣợc chuyển về bài toán đơn giản hơn là chuyển n-1 đĩa. Điểm dừng của thuật toán đệ
qui này là khi n=1 và ta chuyển thẳng đĩa này từ cọc ban đầu A sang cọc đích C. Tính chất chia để trị của thuật toán này thể hiện ở chỗ: Bài toán chuyển n đĩa
đƣợc chia làm 2 bài toán nhỏ hơn là chuyển n-1 đĩa. Lần thứ nhất chuyển n-1 đĩa từ cọc A sang cọc trung gian B, và lần thứ 2 chuyển n-1 đĩa từ cọc trung gian B sang cọc
đích C Cài đặt đệ qui cho thuật toán nhƣ sau: Hàm chuyen(n, A, C) thực hiện việc chuyển đĩa thứ n từ cọc A sang cọc C Hàm thaphanoi(n, A, C, B) là hàm đệ qui thực hiện việc chuyển n đĩa từ cọc A sang cọc C, sử dụng cọc trung gian là cọc B. Chƣơng trình nhƣ sau: chuyen(n, A, B) { printf(Chuyển đĩa thứ n từ cọc A sang cọc C); return; } thaphanoi(n, A, C, B) { if (n==1) chuyen(1, A, C); else{ thaphanoi(n-1, A, B, C); chuyen(n, A, C); thaphanoi(n-1, B, C,A); } return; } Hàm chuyen thực hiện thao tác in ra 1 dòng cho biết chuyển đĩa thứ mấy từ cọc nào sang cọc nào. Hàm thaphanoi kiểm tra nếu số đĩa bằng 1 thì thực hiện chuyển trực tiếp đĩa từ cọc A sang cọc C. Nếu số đĩa lớn hơn 1, có 3 lệnh đƣợc thực hiện: 1- Lời gọi đệ qui thaphanoi(n-1, A, B, C) để chuyển n-1 đĩa từ cọc A sang cọc B, sử dụng cọc C làm cọc trung gian; 2- Thực hiện chuyển đĩa thứ n từ cọc A sang cọc C; 3- Lời gọi đệ qui thaphanoi(n-1, B, C, A) để chuyển n-1 đĩa từ cọc B sang cọc C, sử dụng cọc A làm cọc trung gian. Một chƣơng trình đã đƣợc cài đặt trên ngôn ngữ lập trình C khi chạy với số đĩa là 4, ta có kết quả bên dƣới: - Qua mỗi lần gọi đệ qui kích thức bài toán phải nhỏ dần (thƣờng để tiến đến trƣờng hợp suy biến hay còn gọi là dừng). - Tồn tại trƣờng hợp kết thúc việc gọi đệ qui gọi là trƣờng hợp suy biến. Thuật toán đệ qui quay lui: Nhƣ chúng ta đã biết, các thuật toán đƣợc xây dựng để giái quyết vấn đề thƣờng
đƣa ra 1 quy tắc tính toán nào đó. Tuy nhiên, có những vấn đề không tuân theo 1 quy
tắc, và khi đó ta phải dùng phƣơng pháp thử - sai (trial-and-error) để giải quyết. Theo
phƣơng pháp này, quá trình thử - sai đƣợc xem xét trên các bài toán đơn giản hơn
(thƣờng chỉ là 1 phần của bài toán ban đầu). Các bài toán này thƣờng đƣợc mô tả dƣới
dạng đệ qui và thƣờng liên quan đến việc giải quyết một số hữu hạn các bài toán con. Để hiểu rõ hơn thuật toán này, chúng ta sẽ xem xét một ví dụ điển hình cho thuật toán quay lui, đó là bài toán Mã đi tuần và bài toán 8 quân hậu. Và kết quả chạy chƣơng trình với bàn cờ 8x8 và ô bắt đầu là ô (0,0): Bài toán 8 quân hậu Bài toán 8 quân hậu là 1 ví dụ rất nổi tiếng về việc sử dụng phƣơng pháp thử - sai
và thuật toán quay lui. Đặc điểm của các bài toán dạng này là không thể dùng các biện
pháp phân tích để giải đƣợc mà phải cần đến các phƣơng pháp tính toán thủ công, với
sự kiên trì và độ chính xác cao. Do đó, các thuật toán kiểu này phù hợp với việc sử
dụng máy tính vì máy tính có khả năng tính toán nhanh và chính xác hơn nhiều so với
con ngƣời. Bài toán 8 quân hậu đƣợc phát biểu ngắn gọn nhƣ sau: Tìm cách đặt 8 quân hậu trên 1 bàn cờ sao cho không có 2 quân hậu nào có thể ăn đƣợc nhau. Các nƣớc chiếu của quân hậu 3.3. Khử đệ qui Trong nhiều trƣờng hợp, một chƣơng trình có thể viết dƣới dạng đệ qui. Tuy
nhiên, đệ qui không hẳn đã là giải pháp tốt nhất cho vấn đề. Nhìn chung, khi chƣơng
trình có thể viết dƣới dạng lặp hoặc các cấu trúc lệnh khác thì không nên sử dụng đệ
qui. Thứ nhất, nhƣ đã nói ở trên, khi một giải thuật đệ qui gọi lại nó, tập các đối
tƣợng đƣợc sử dụng trong giải thuật này nhƣ các biến, hằng, cấu trúc .v.v sẽ đƣợc tạo
ra. Ngoài ra, việc chuyển giao điều khiển từ cácg thuật cũng cần lƣu trữ các thông số
dùng cho việc trả lại điều khiển cho giải thuật ban đầu. Thứ hai là việc sử dụng đệ qui đôi khi tạo ra các tính toán thừa, không cần thiết do tính chất tự động gọi thực hiện giải thuật khi chƣa gặp điều kiện dừng của đệ qui.
Để minh họa cho điều này, chúng ta sẽ xem xét một ví dụ, trong đó cả đệ qui và lặp
đều có thể đƣợc sử dụng. Tuy nhiên, ta sẽ phân tích để thấy sử dụng đệ qui trong
trƣờng hợp này gây lãng phí bộ nhớ và các tính toán không cần thiết nhƣ thế nào. Xét bài toán tính các phần tử của dãy Fibonaci. Dãy Fibonaci đuợc định nghĩa nhƣ sau: F(0) = 0 F(1) =1 Với n >1 thì F(n) = F(n-1) + F(n-2) Rõ ràng là nhìn vào một định nghĩa đệ qui nhƣ trên, chƣơng trình tính phần tử
của dãy Fibonaci có vẻ nhƣ rất phù hợp với thuật toán đệ qui. Phƣơng thức đệ qui để
tính dãy này có thể đƣợc viết nhƣ sau: int Fibonaci(int i){ if (i==0) return 0; if (i==1) return 1; return Fibonaci(i-1) + Fibonaci (i-2) } Kết quả thực hiện chƣơng trình không có gì sai. Tuy nhiên, chú ý rằng một lời
gọi đệ qui Fibonaci (n) sẽ dẫn tới 2 lời gọi đệ qui khác ứng với n-1 và n-2. Hai lời gọi
này lại gây ra 4 lời gọi nữa,…, cứ nhƣ vậy số lời gọi đệ qui sẽ tăng theo cấp số mũ.
Điều này rõ ràng là không hiệu quả vì trong số các lời gọi đệ qui đó có rất nhiều lời
gọi trùng nhau. Ví dụ lời gọi đệ qui Fibonaci (6) sẽ dẫn đến 2 lời gọi Fibonaci (5) và
Fibonaci (4). Lời gọi Fibonaci (5) sẽ gọi Fibonaci (4) và Fibonaci (3). Ngay chỗ này,
ta đã thấy có 2 lời gọi Fibonaci (4) đƣợc thực hiện. Hình 2.1 cho thấy số các lời gọi
đƣợc thực hiện khi gọi Giải thuật Fibonaci (6). Trong hình vẽ trên, ta thấy để tính đƣợc phần tử thứ 6 thì cần có tới 25 lời gọi !
Sau đây, ta sẽ xem xét việc sử dụng vòng lặp để tính giá trị các phần tử của dãy
Fibonaci nhƣ thế nào. Đầu tiên, ta khai báo một mảng F các số tự nhiên để chứa các số Fibonaci. Vòng lặp để tính và gán các số này vào mảng rất đơn giản nhƣ sau: F[0]=0; F[1]=1; for (i=2; i F[i] = F[i-1] + F [i-2]; Rõ ràng là với vòng lặp này, mỗi số Fibonaci (n) chỉ đƣợc tính 1 lần thay vì đƣợc tính toán chồng chéo nhƣ ở trên. 3.4. Một số dạng đệ qui Hai dạng đệ qui thƣờng gặp đệ qui trực tiếp và đệ qui gián tiếp. - Đệ quy trực tiếp là loại đệ quy mà đối tƣợng đƣợc mô tả trực tiếp qua nó: A mô tả
qua A, B, C,...trong đó B, C, ... không chứa A. Ví dụ: giaithua (n) { if (n==0) return 1; else return giaithua(n-1) * n; } - Đệ quy gián tiếp là loại đệ quy mà đối tƣợng đƣợc mô tả gián tiếp qua nó : A mô tả
qua A1 ,A2 ,..., An .Trong đó, có một Ai đƣợc mô tả qua A. Ví dụ: F1(x) { If (x<=0) Return x; else Return F2(x); } F2(y) { Return F1(y-1); } TÓM TẮT CHƢƠNG 3 Định nghĩa bằng đệ qui: Một đối tượng được gọi là đệ qui nếu nó hoặc một phần
của nó được định nghĩa thông qua khái niệm về chính nó. Chương trình đệ qui: Một
chương trình máy tính gọi là đệ qui nếu trong chương trình có lời gọi chính nó (có
kiểm tra điều kiện dừng). Để viết một chương trình dạng đệ qui thì vấn đề cần xử lý phải được giải quyết 1
cách đệ qui. Ngoài ra, ngôn ngữ dùng để viết chương trình phải hỗ trợ đệ qui (có hỗ
trợ hàm và Giải thuật). Nếu chương trình có thể viết dưới dạng lặp hoặc các cấu trúc lệnh khác thì không nên sử dụng đệ qui Các thuật toán đệ qui dạng “chia để trị” là các thuật toán phân chia bài toán
ban đầu thành 2 hoặc nhiều bài toán con có dạng tương tự và lần lượt giải quyết từng
bài toán con này.Các bài toán con này được coi là dạng đơn giản hơn của bài toán
ban đầu, do vậy có thể sử dụng các lời gọi đệ qui để giải quyết. Thuật toán quay lui dùng để giải quyết các bài toán không tuân theo 1 quy tắc,
và khi đó ta phải dùng phương pháp thử - sai (trial-and-error) để giải quyết. Theo
phương pháp này, quá trình thử - sai được xem xét trên các bài toán đơn giản hơn
(thường chỉ là 1 phần của bài toán ban đầu). Các bài toán này thường được mô tả
dưới dạng đệ qui và thường liên quan đến việc giải quyết một số hữu hạn các bài toán
con BÀI TẬP CHƢƠNG 3 1. Hãy trình bày một số ví dụ về định nghĩa ở dạng đệ qui. 2. Một chƣơng trình đệ qui khi gọi chính nó thì bài toán khi đó có kích thƣớc nhƣ
thế nào so với bài toán ban đầu? Để chƣơng trình đệ qui không bị lặp vô hạn thì cần
phải làm gì? 3. Hãy cho biết tại sao khi chƣơng trình có thể viết dƣới dạng lặp hoặc cấu trúc khác thì không nên sử dụng đệ qui? 4. Viết chƣơng trình đệ qui tính tổng các số lẻ trong khoảng từ 1 đến 2n+1. 5. Hãy cho biết các bƣớc thực hiện chuyển đĩa trong bài toán tháp Hà nội với số lƣợng đĩa là 5. 6. Hoàn thiện mã nguồn cho bài toán 8 quân hậu và chạy thử cho ra kết quả. 7. Xét định nghĩa đệ qui: n+1 nếu m=0 Acker(m,n)= Acker(m-1,1)nếu n=0 Acker(m-1,Acker(m,n-1)) với các trƣờng hợp khác. Hàm này đƣợc gọi là hàm Ackermann. Nó có đặc điểm là giá trị của nó tăng rất nhanh, ứng với giá trị nguyên của m và n. - Hãy xác định Acker(1,2); - Viết chƣơng trình con đệ qui thực hiện tính giá trị hàm này. 8. Hàm C(n,k) với n, k là các giá trị nguyên không âm, k<=n, đƣợc định nghĩa: C(n,n)=1 C(n,0)=1 C(n,k)=C(n-1,k-1)+C(n-1,k) nếu 0 a) Viết chƣơng trình con đệ qui thực hiện tính giá trị C(n,k) khi biết n,k. b) Chứng minh kết quả trên đúng với C(n,k)=n!/((n-k)!k!) 9. Viết hàm đệ qui in ngƣợc một xâu ký tự, thủ tục in ngƣợc 1 số tự nhiên n. 10. Viết hàm đệ qui in ra các hoán vị n phần tử của một dãy a=(a1,a2,a3,...,an). CHƢƠNG 4. DANH SÁCH Chương 4 giới thiệu về mô hình dữ liệu danh sách và các cách cài đặt danh sách.
Phần danh sách liên kết đơn giới thiệu các khái niệm danh sách, các thao tác cơ bản
trên danh sách như chèn phần tử, xoá phần tử, duyệt qua toàn bộ danh sách. Cuối
phần là một ví dụ về sử dụng danh sách liên kết đơn để biểu diễn 1 đa thức. Chương này cũng đề cập tới một số kiểu danh sách liên kết khác như danh sách liên kết vòng và danh sách liên kết kép. Để học tốt chương này, sinh viên cần nắm vững lý thuyết và tìm tòi một số ví dụ khác minh hoạ cho việc sử dụng mảng và danh sách liên kết 4.1. Khái niệm Danh sách là một dãy hữu hạn các phần tử thuộc một lớp đối tƣợng cụ thể. Ví dụ,
danh sách sinh viên, danh sách giảng viên, danh sách phòng học,... . Danh sách tuyến
tính là danh sách mà thứ tự các phần tử đƣợc xác định, các phần tử đƣợc bố trí liền kề
và nối tiếp nhau theo một chiều. Trong chƣơng này, tập trung việc thao tác trên danh
sách tuyến tính. 4.2. Các thao tác thƣờng gặp trên danh sách 4.1.1. ổ sung một ph n t vào danh sách Bổ sung là thêm một phần tử vào danh sách đã có, trong trƣờng hợp này cần thực hiện các bƣớc sau: - Sinh ra phần tử mới - Chèn phần tử mới vào một vị trí xác định nhƣ chèn đầu, chèn cuối, chèn giữa hai phần tử nào đó. 4.1.2. ạo lập danh sách - Khởi tạo với một danh sách rỗng; - Liên tục bổ sung các phần tử mới vào danh sách cho đến khi hết phần tử cần bổ sung, danh sách sẽ đƣợc lập. 4.1.3. Du ệt qua danh sách - Bắt đầu từ phần tử đầu tiên trong danh sách; - Lần lƣợt đi qua từng phần tử cho đến cuối danh sách, thông thƣờng khi đến mỗi phần tử sẽ xử lý yêu cầu của bài toán. 4.1.4. X a một ph n t kh i danh sách - Việc xóa bỏ một phần tử khỏi danh sách là việc loại bỏ một phần tử đó khỏi
mối quan hệ thứ tự trong danh sách, một thứ tự mới đƣợc thiết lập đối với những phần
tử còn lại. Thông tin của phần tử đã loại bỏ không còn đƣợc quan tâm nữa. 4.1.5. Sắp x p danh sách - Sắp xếp là việc thiết lập lại quan hệ thứ tự các phần tử theo một tiêu chí nào đó. 4.3. Mảng và cài đặt danh sách bằng mảng 4.3.1. Khái niệm mảng Mảng là một tập có thứ tự bao gồm một số cố định các phần tử. Mỗi phần tử của
mảng còn đƣợc đặc trƣng bởi chỉ số, thể hiện thứ tự của phần tử đó trong mảng. Các
phần tử trong mảng cùng kiểu dữ liệu. Không tồn tại phép bổ sung hay loại bỏ phần tử
trên mảng. Trên mảng thƣờng tồn tại các thao tác sau: - Tạo lập mảng - Duyệt qua các phần tử của mảng để xử lý theo yêu cầu. - Sắp xếp giá trị các phần tử trong mảng. Khi nói đến vectơ là nói đến mảng một chiều, ma trận là mảng hai chiều. 4.3.2. Cấu trúc lưu trữ mảng Một cách đơn giản có thể hình dung bộ nhớ máy tính là một dãy các phần tử nhớ
cơ sở đƣợc đánh số kế tiếp nhau (bắt đầu từ một số nguyên nào đó). Chỉ số vị trí đó là
địa chỉ, một phần tử nhớ cơ sở có địa chỉ gọi là từ máy. Một phần tử dữ liệu có thể lƣu
trong máy bởi một ô nhớ gồm một hay nhiều từ máy. Việc truy cập vào ô nhớ sẽ đƣợc
xác định bởi địa chỉ của từ máy đầu tiên trong ô nhớ đó. Có 2 cách xác định địa chỉ: - Một là dựa vào đặc tả lƣu trữ dữ liệu để tính ra địa chỉ và đƣợc gọi là địa chỉ tính đƣợc(Computered address), mảng thuộc loại này; - Hai là địa chỉ đƣợc lƣu ở nơi nào đó, khi cần sẽ lấy ra, loại này gọi là con trỏ (pointer) hay liên kết (link). Mảng đƣợc lƣu trong máy dƣới dạng một vectơ lƣu trữ. Đó là dãy các từ máy kế
tiếp nhau nên còn gọi là lƣu trữ kế tiếp. Xét mảng một chiều A có n phần tử nếu mỗi
phần tử A[i] (1 i n) chiếm c từ máy thì A sẽ chiếm c*n từ máy và đƣợc bố trí kế
tiếp nhƣ sau : A[1] A[2] ... A[i] ... A[n] Địa chỉ phần tử đầu tiên gọi là địa chỉ gốc, ký hiệu L0
Địa chỉ phẩn tử A[i] sẽ đƣợc tính bởi hàm địa chỉ: Loc(A[i] ) = L0 + (i-1)*c Nếu cận dƣới không phải 1 mà là số b nào đó thì tính địa chỉ: Loc(A[i] ) = L0 + (i-b)*c
Đối với mảng nhiều chiều, việc tổ chức lƣu trữ cũng đƣợc thực hiện tƣơng tự nghĩa là vẫn bằng một vectơ lƣu trữ kế tiếp nhƣ trên. Với mảng hai chiều B gồm m hàng, n cột, mỗi phần tử chiếm c từ máy. Mảng B
sẽ chiếm m*n*c từ máy kế tiếp nhau. Việc bố trí các phần tử của mảng hai chiều có
thể theo ƣu tiên hàng (lần lƣợt hết hàng này đến hàng khác) hoặc ƣu tiên cột (hết cột
này đến cột khác). Ví dụ, một mảng B có 3 hàng, 4 cột. Nếu theo ƣu tiên hàng việc bố trí các phần tử trong mảng: B[1,1] B[1,2] B[1,3] B[1,4] B[2,1] B[2,2] B[2,3] B[2,4] B[3,1] B[3,2] B[3,3] B[3,4] Và địa chỉ phần tử B[i,j] (1im,1jn ) đƣợc tính: Loc(B[i,j] ) = L0 +[(i-1)*n+(j-1)]*c B[1,1] B[2,1] B[3,1] B[1,2] B[2,2] B[3,2] B[1,3] B[2,3] B[3,3] B[1,4] B[2,4] B[3,4] Nếu theo ƣu tiên cột các phần tử sẽ bố trí: Và địa chỉ phần tử B[i,j] đƣợc tính: Loc(B[i,j] ) = L0 +[(j-1)*m+(i-1)]*c
Tóm lại: với đặc trƣng lƣu trữ kế tiếp và mỗi phần tử trong mảng là cùng
kiểu(cùng kích thƣớc) nên việc tính địa chỉ của phẩn tử nào đó là nhanh chóng và dễ
dàng dẫn đến việc truy cập vào từng phần tử trong mảng đơn giản là chỉ ra chỉ số vị trí
của nó. Khi lập trình trên một ngôn ngữ cần ghi nhớ số phần tử của mảng là cố định và
hữu hạn nên trong khai báo phải chỉ rõ số lƣợng này. 4.3.3. Cài đặt danh sách ng mảng - Mảng là cấu trúc dữ liệu có thể dùng để cài đặt danh sách, mỗi phần tử của mảng ứng với một phần tử trong danh sách. Ví dụ: Nhập danh sách gồm n (n là hữu hạn và xác định) số nguyên. Yêu cầu : tìm số các phần tử dƣơng, số các phần tử âm, số các phần tử bằng 0 trong danh sách. Giải thuật : Main() { //1. nhập mảng for (i=0; i //2. khởi tạo các giá trị ban đầu cho các biến đếm Sa=0 ; Sd=0 ; Sk=0; //3. Duyệt qua mảng và kiểm tra điều kiện, xử lý For (i=0; i If (a[i] >0) Sd = Sd + 1; Else If (a[i] < 0) Sa = Sa +1; Else Sk = Sk +1; //4. in kết quả printf(sd,sa,sk); } 4.4. Con trỏ và danh sách móc nối 4.4.1. Khái niệm Khác với mảng, danh sách liên kết là 1 cấu trúc dữ liệu mà mỗi phần tử trong
danh sách liên kết có chứa thông tin về phần tử tiếp theo, qua đó ta có thể truy cập tới
phần tử này. Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử, trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới nút kế tiếp. Nói “mỗi phần tử là 1 phần của 1 nút” bởi vì mỗi nút ngoài việc chứa thông tin về phần tử còn chứa thông tin về liên kết tới nút tiếp theo trong danh sách. Có thể nói danh sách liên kết là 1 cấu trúc dữ liệu đƣợc định nghĩa kiểu đệ qui, vì
trong địnhnghĩa 1 nút của danh sách có tham chiếu tới khái niệm nút. Thông thƣờng,
một nút thƣờng có liên kết trỏ tới một nút khác, tuy nhiên nó cũng có thể trỏ tới chính
nó. Danh sách liên kết có thể đƣợc xem nhƣ là 1 sự bố trí tuần tự các phần tử trong 1
tập. Bắt đầu từ 1 nút, ta coi đó là phần tử đầu tiên trong danh sách. Từ nút này, theo
liên kết mà nó trỏ tới, ta có nút thứ 2, đƣợc coi là phần tử thứ 2 trong danh sách, v.v.
cứ tiếp tục nhƣ vậy cho đến hết danh sách. Nút cuối cùng có thể có liên kết là một liên
kết null, tức là không trỏ tới nút nào, hoặc nó có thể trỏ về nút đầu tiên để tạo thành 1
vòng. Danh sách liên kết Nhƣ vậy, mặc dù cùng là cấu trúc dữ liệu bao gồm 1 tập các phần tử, nhƣng giữa danh sách liên kết và mảng có 1 số điểm khác biệt sau: Mảng có thể đƣợc truy cập ngẫu nhiên thông qua chỉ số, còn danh sách chỉ có
thể truy cập tuần tự. Trong danh sách liên kết, muốn truy cập tới 1 phần từ phải bắt
đầu từ đầu danh sách sau đó lần lƣợt qua các phần tử kế tiếp cho tới khi đến phần tử
cần truy cập Việc bố trí, sắp đặt lại các phần tử trong 1 danh sách liên kết đơn giản hơn
nhiều so với mảng. Bới vì đối với danh sách liên kết, để thay đổi vị trí của 1 phần tử,
ta chỉ cần thay đổi các liên kết của một số phần tử có liên quan, còn trong mảng, ta
thƣờng phải thay đổi vị trí của rất nhiều phần tử Do bản chất động của danh sách liên kết, kích thƣớc của danh sách liên kết có
thể linh hoạt hơn nhiều so với mảng. Kích thƣớc của danh sách không cần phải khai
báo trƣớc, bất kỳ lúc nào có thể tạo mới 1 phần tử và thêm vào vị trí bất kỳ trong danh
sách. Nói cách khác, mảng là 1 tập có số lƣợng cố định các phần tử, còn danh sách liên
kết là 1 tập có số lƣợng phần tử không cố định. Để khai báo một danh sách trong C, ta có thể dùng cấu trúc tự trỏ. Ví dụ, để khai báo một danh sách liên kết mà mỗi nút chứa một phần tử là số nguyên nhƣ sau: struct node { int item; struct node *next; }; typedef struct node *listnode; Đầu tiên, ta khai báo một cấu trúc node bao gồm 2 thành phần. Thành phần thứ
nhất là 1 biến nguyên chứa dữ liệu, thành phần thứ 2 là một con trỏ chứa địa chỉ của
nút kế tiếp. Tiếp theo, ta định nghĩa một kiểu dữ liệu con trỏ tới nút có tên là listnode.
Với các danh sách liên kết có kiểu phần tử phức tạp hơn, ta phải khai báo cấu trúc của
phần tử này trƣớc (itemstruct), sau đó đƣa kiểu cấu trúc đó vào kiểu phần tử trong cấu
trúc node. struct node { itemstruct item; struct node *next; }; typedef struct node *listnode; 4.4.2. Các thao tác cơ ản tr n danh sách li n k t Nhƣ đã nói ở trên, với tính chất động của danh sách liên kết, các nút của danh
sách không đƣợc tạo ra ngay từ đầu mà chỉ đƣợc tạo ra khi cần thiết. Do vây, thao tác
đầu tiên cần có trên danh sách là tạo và cấp phát bộ nhớ cho 1 nút. Tƣơng ứng với nó
là thao tác giải phóng bộ nhớ và hủy 1 nút khi không dùng đến nữa Thao tác tiếp theo cần xem xét là việc chèn 1 nút đã tạo vào danh sách. Do cấu
trúc đặt biệt của danh sách liên kết, việc chèn nút mới vào đầu, cuối, hoặc giữa danh
sách có một số điểm khác biệt. Do vậy, cần xem xét cả 3 trƣờng hợp. Tƣơng tự nhƣ
vậy, việc loại bỏ 1 nút khỏi danh sách cũng sẽ đƣợc xem xét trong cả 3 trƣờng hợp.
Cuối cùng là thao tác duyệt qua toàn bộ danh sách. Trong phần tiếp theo, ta sẽ xem xét chi tiết việc thực hiện các thao tác này, đƣợc
thực hiệntrên danh sách liên kết có phần tử của nút là 1 số nguyên nhƣ khai báo đã
trình bày ở trên. Qui ƣớc: Tạo, cấp phát, và giải phóng bộ nhớ cho 1 nút listnode p; // Khai báo biến p new(p);//cấp phát bộ nhớ cho p delete(p); //giải phóng bộ nhớ đã cấp phát cho nút p; Chèn một nút vào đ u danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p Các bƣớc để chèn 1 nút mới vào đầu danh sách nhƣ sau: - Tạo và cấp phát bộ nhớ cho 1 nút mới. Nút này đƣợc trỏ tới bởi q - Sau khi gán các giá trị thích hợp cho phần tử của nút mới, cho con trỏ tiếp của nút mới trỏ đến phần tử đầu tiên của nút - Cuối cùng, để p vẫn trỏ đến nút đầu danh sách, ta cần cho p trỏ đến nút mới tạo Chú ý rằng các bƣớc trên phải làm đúng trình tự, nếu làm sai sẽ dẫn đến mất dữ
liệu. Chẳng hạn, nếu ta cho con trỏ p trỏ đến nút mới tạo trƣớc, thì khi đó nút mới tạo
sẽ không trỏ tới đƣợc nút đầu danh sách cũ, vì không còn biến nào lƣu trữ vị trí này
nữa void Insert_Begin(listnode *p, int x){ listnode q; new(q); q-> item = x; q-> next = *p; *p = q; } Chèn một nút vào cu i danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p Các bƣớc để chèn 1 nút mới vào cuối danh sách nhƣ sau (thực hiện đúng theo trình tự): - Tạo và cấp phát bộ nhớ cho 1 nút mới. Nút này đƣợc trỏ tới bởi q - Dịch chuyển con trỏ tới nút cuối của danh sách. Để làm đƣợc việc này, ta phải
khai báo 1 biến con trỏ mới r. Ban đầu, biến này, cũng với p, trỏ đến đầu danh sách.
Lần lƣợt dịch chuyển r theo các nút kế tiếp cho tới khi đến cuối danh sách - Cho con trỏ tiếp của nút cuối (đƣợc trỏ tới bởi r) trỏ đến nút mới tạo là q, và cho con trỏ tiếp của q trỏ tới null void Insert_End(listnode *p, int x){ listnode q, r; new(q); q-> item = x; q->next = NULL; if (*p==NULL) *p = q; else{ r = *p; while (r->next != NULL) r = r->next; r->next = q; } } Chèn một nút vào trước nút r trong danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p, và 1 nút r trong danh sách Ta giả thiết rằng nút r không phải là nút cuối cùng của danh sách, vì nếu nhƣ vậy, ta chỉ cần thực hiện thao tác chèn 1 nút vào cuối danh sách nhƣ đã trình bày ở trên. Các bƣớc để chèn 1 nút mới vào trƣớc nút r trong danh sách nhƣ sau (thực hiện đúng theo trình tự): - Tạo và cấp phát bộ nhớ cho 1 nút mới. Nút này đƣợc trỏ tới bởi q - Cho con trỏ tiếp của nút mới trỏ đến nút kế tiếp của nút r - Cho con trỏ tiếp của nút r trỏ đến q void Insert_Middle(listnode *p, int position, int x){ int count=1, found=0; listnode q, r; r = *p; while ((r != NULL)&&(found==0)){ if (count == position){ new(q); q-> item = x; q-> next = r-> next; r-> next = q; found = 1; } count ++; r = r-> next; } if (found==0) printf(“Khong tim thay vi tri can chen !”); } Xóa một nút đ u danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p Chú ý rằng để xóa 1 nút trong danh sách thì danh sách đó không đƣợc rỗng. Các bƣớc để xóa 1 nút ở đầu danh sách nhƣ sau: - Dùng 1 con trỏ tạm q trỏ đến đầu danh sách - Dịch chuyển con trỏ p qua phần tử đầu tiên đến phần tử kế tiếp - Ngắt liên kết của biến tạm q với nút tiếp theo, giải phóng bộ nhớ cho q void Remove_Begin(listnode *p){ listnode q; if (*p == NULL) return; q = *p; *p = (*p)-> next; q-> next = NULL; delete(q); } Xóa một nút cu i danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p Các bƣớc để xóa 1 nút ở cuối danh sách nhƣ sau: - Dịch chuyển con trỏ tới nút gần nút cuối của danh sách. Để làm đƣợc việc này,
ta phải dùng 2 biến tạm là q và r. Lần lƣợt dịch chuyển q và r từ đầu danh sách tới cuối
danh sách, trong đó q luôn dịch chuyển sau r 1 nút. Khi r tới nút cuối cùng thì q là nút
gần nút cuối cùng nhất. - Cho con trỏ tiếp của nút gần nút cuối cùng nhất (đang đƣợc trỏ bởi q) trỏ tới null. Giải phóng bộ nhớ cho nút cuối cùng (đang đƣợc trỏ bởi r) void Remove_End(listnode *p){ listnode q, r; if (*p == NULL) return; if ((*p)-> next == NULL){ Remove_Begin(*p); return; } r = *p; while (r-> next != NULL){ q = r; r = r-> next; } q-> next = NULL; delete(r); } X a một nút trước nút r trong danh sách Giả sử ta có 1 danh sách mà đầu của danh sách đƣợc trỏ tới bởi con trỏ p, và 1 nút r trong danh sách Ta giả thiết rằng nút r không phải là nút cuối cùng của danh sách, vì nếu nhƣ vậy thì sẽ không có nút đứng trƣớc nút r. Các bƣớc để xóa 1 nút ở trƣớc nút r trong danh sách nhƣ sau: - Sử dụng 1 biến tạm q trỏ đến nút đứng trƣớc nút r - Cho con trỏ tiếp của nút r trỏ tới nút đứng sau nút q - Ngắt liên kết của nút q và giải phóng bộ nhớ cho q. void Remove_Middle(listnode *p, int position){ int count=1, found=0; listnode q, r; r = *p; while ((r != NULL)&&(found==0)){ if (count == position){ q = r-> next; r-> next = q-> next; q-> next = NULL; delete (q); found = 1; } count ++; r = r-> next; } if (found==0) printf(“Khong tim thay vi tri can xoa !”); } Du ệt toàn ộ danh sách Thao tác duyệt danh sách cho phép duyệt qua toàn bộ các phần tử của danh sách, từ phần tử đầu tiền cho tới phần tử cuối cùng. Để thực hiện thao tác này, ta cần một biến tạm r trỏ tới đầu danh sách. Từ vị trí
này, theo liên kết của các nút, thực hiện duyệt qua từng phần tử trong danh sách.
Trong quá trình duyệt, tại mỗi nút ta có thể thực hiện các thao tác cần thiết nhƣ lấy
thông tin phần tử, sửa thông tin, so sánh, v.v. r = p; while (r-> next != null){ //thực hiện các thao tác cần thiết r = r-> next; } 4.4.3. Một s dạng khác của danh sách li n k t Danh sách nối vòng Trong danh sách liên kết đơn, nút cuối cùng của danh sách sẽ có liên kết trỏ đến
một giá trị null cho biết danh sách đã kết thúc. Nếu liên kết này không trỏ đến null mà
trỏ về nút đầu tiên thì ta sẽ có một danh sách liên kết vòng Ƣu điểm của danh sách liên kết vòng là bất kỳ nút nào cũng có thể coi là đầu của
danh sách. Có nghĩa là từ một nút bất kỳ, ta có thể tiến hành duyệt qua toàn bộ các
phần tử của danh sách mà không cần trở về nút đầu tiên nhƣ trong danh sách liên kết
thông thƣờng. Tuy nhiên, nhƣợc điểm của danh sách loại này là có thể không biết khi nào thì đã
duyệt qua toàn bộ phần tử của danh sách. Điều này dẫn đến 1 quá trình duyệt vô hạn,
không có điểm dừng. Để khắc phục nhƣợc điểm này, trong quá trình duyệt luôn phải
kiểm tra xem đã trở về nút ban đầu hay chƣa. Việc kiểm tra này có thể dựa trên giá trị
phần tử hoặc bằng cách thêm vào 1 nút đặc biệt. Sau đây, chúng ta sẽ xem xét việc sử dụng danh sách liên kết vòng để giải quyết bài toán Josephus. Bài toán nhƣ sau: Có 1 nhóm N ngƣời muốn lựa chọn ra 1 thủ lĩnh. Các lựa chọn nhƣ sau: N ngƣời
xếp thành vòng tròn. Bắt đầu từ 1 ngƣời nào đó, duyệt qua vòng và đến ngƣời thứ M
thì ngƣời đó bị loại khỏi vòng. Quá trình duyệt bắt đầu lại, và ngƣời thứ M tiếp theo lại
bị loại khỏi vòng. Lặp lại nhƣ vậy cho tới khi chỉ còn 1 ngƣời trong vòng và ngƣời đó
là thủ lĩnh. Chẳng hạn, với N = 9 ngƣời và M = 5, ta có quá trình duyệt và loại nhƣ
sau: Vòng ban đầu: Duyệt lần 1: Loại 5 Duyệt lần 2: Loại 1 Duyệt lần 3: Loại 7 Duyệt lần 4: Loại 4 Duyệt lần 5: Loại 3 Duyệt lần 6: Loại 6 Duyệt lần 7: Loại 9 Duyệt lần 8: Loại 2 Phần tử còn lại sau cùng: Việc sử dụng danh sách liên kết vòng có thể cung cấp 1 lời giải hiệu quả cho bài
toán. Theo đó, N ngƣời sẽ lần lƣợt đƣợc đƣa vào 1 danh sách liên kết vòng. Quá trình
duyệt bắt đầu từ ngƣời đầu tiên, và đếm đến M lần duyệt thì loại nút ra khỏi danh sách
và tiếp tục quá trình duyệt. Danh sách liên kết vòng sẽ thu hẹp dần, và đến khi chỉ còn
1 nút thì kết thúc quá trình duyệt. Rõ ràng là nếu sử dụng mảng cho bài toán Josephus
sẽ không đem lại hiệu quả cao, vì quá trình loại bỏ 1 phần tử ra khỏi mảng phức tạp
hơn nhiều so với danh sách liên kết Danh sách nối kép Trong danh sách liên kết đơn, mỗi nút chỉ có một liên kết trỏ tới nút kế tiếp. Điều
này có nghĩa danh sách liên kết đơn chỉ cho phép duyệt theo 1 chiều, trong khi thao tác
duyệt chiều ngƣợc lại đôi khi cũng rất cần thiết. Để giải quyết vấn đề này, ta có thể tạo
cho mỗi nút hai liên kết: một để trỏ tới nút đứng trƣớc, một để trỏ tới nút đứng sau.
Những danh sách nhƣ vậy đƣợc gọi là danh sách liên kết kép Việc khai báo danh sách liên kết kép cũng tƣơng tự nhƣ khai báo danh sách liên kết đơn, chỉ có điểm khác biệt là có thêm 1 liên kết nữa cho mỗi nút. struct node { itemstruct item; struct node *left; struct node *right; }; typedef struct node *doublelistnode; TÓM TẮT CHƢƠNG Một mảng là 1 tập hợp cố định các thành phần có cùng 1 kiểu dữ liệu, được lưu
trữ kế tiếp nhau và có thể được truy cập thông qua một chỉ số. Mảng có thể có một
hoặc nhiều chiều. Mảng có ưu điểm là dễ sử dụng, tốc độ truy cập cao. Tuy nhiên, mảng có nhược điểm là không linh hoạt về kích thước và phức tạp khi bố trí lại các phần tử. Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử, trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới nút kế tiếp. Danh sách liên kết có kiểu truy cập tuần tự, có kích thước linh hoạt và dễ dàng trong việc bố trí lại các phần tử. Các thao tác cơ bản trên danh sách liên kết bao gồm: Khởi tạo danh sách, chèn
1 phần tử vào đầu, cuối, giữa danh sách, xoá 1 phần tử khỏi đầu, cuối, giữa danh
sách, duyệt qua toàn bộ danh sách. Ngoài danh sách liên kết đơn còn một số loại danh sách liên kết khác như danh sách vòng, danh sách liên kết kép .v.v =========================== BÀI TẬP CHƢƠNG 4 1. Khi lập trình bằng ngôn ngữ C, nếu khai báo ma trận A theo kiểu float A[1..5,1..4] thì máy sẽ lƣu trữ nhƣ thế nào? Minh họa cấu trúc lƣu trữ bằng hình vẽ. 2. Cho mảng một chiều A[5..50] và B[-5..10] a) Hãy tính số phần tử của mỗi mảng b) Đối với mảng A, biết địa chỉ gốc L0=300 và mỗi phần tử chiếm 4 từ máy. Hãy tính địa chỉ của A[17] và A[35] 3. Giả sử 3 từ máy mới đủ lƣu trữ một phần tử của mảng C[1..6,1..3]. Hãy tính
địa chỉ của C[4,2] biết rằng địa chỉ lƣu trữ theo thứ tự ƣu tiên hàng và địa chỉ gốc
L0=1000 4. Hãy nêu tóm tắc ƣu và nhƣợc điểm của lƣu trữ kế tiếp và lƣu trữ móc nối đối với danh sách. 5. Việc chèn một phần tử vào giữa danh sách khi lƣu trữ kế tiếp có gì khác với lƣu trữ móc nối. 6. Với danh sách nối đơn việc truy cập vào phần tử nào đƣợc thực hiện trực tiếp. 7. Cho một danh sách nối đơn, có con trỏ list trỏ tới nút đầu tiên trong sách. Giả sử trƣờng INFO của mỗi nút chỉ chứa một giá trị kiểu số. Hãy viết giải thuật: a) Cộng thêm một lƣợng là A vào giá trị trƣờng INFO của mỗi nút. b) Đếm số lƣợng các nút có trong danh sách c) Đếm số lƣợng các nút đang chứa số dƣơng trong danh sách. 8. Cho một danh sách nối đơn có con trỏ P trỏ tới nút đầu danh sách. Biết rằng, danh sách không rỗng. Hãy viết giải thuật: a) Bổ sung nút mới có giá trị INFO bằng X vào sau nút có địa chỉ trỏ bởi T. b) Bổ sung nút mới có giá trị INFO bằng Y vào trƣớc nút có địa chỉ trỏ bởi T. 9. Cho một danh sách nối đơn có con trỏ Q trỏ tới nút đầu danh sách. Biết rằng, danh sách không rỗng. Hãy viết giải thuật: a) Loại bỏ nút đầu tiên trong danh sách. b) Loại bỏ nút có địa chỉ trỏ bởi T trong danh sách, với T là nút giữa. c) Loại bỏ nút có địa chỉ trỏ bởi T trong danh sách, với T là nút bất kỳ. 10. Tính giá trị cộng hai đa thức CHƢƠNG 5. CÂY Chương 5 giới thiệu một cấu trúc dữ liệu rất gần gũi và có nhiều ứng dụng trong thực tế, đó là cấu trúc dữ liệu kiểu cây. Các nội dung chính được trình bày trong chương bao gồm: Định nghĩa và các khái niệm về cây. Cài đặt cây: Cài đặt bằng mảng hoặc danh sách liên kết. Phép duyệt cây: Duyệt thứ tự trước, thứ tự giữa, và thứ tự sau Ngoài ra, chương này còn giới thiệu một loại cây đặc biệt, có nhiều ứng dụng
trong thực tiễn và nghiên cứu khoa học, đó là cây nhị phân. Loại cây đặc biệt hơn nữa
là cây nhị phân tìm kiếm sẽ được giới thiệu trong chương 7 5.1. Các khái niệm - Trên thực tế ta hay gặp các cấu trúc phân cấp dạng cây + Mục lục của giáo trình (Hình 5.1.a) + Cây gia phả + Cây biểu thức. (Hình 5.1.b) Chƣơng 1 1.1 1.2 1.3 14 1.5 1.2.1 1.2.2 1.5.1 1.5.2 1.5.3 Hình 5.1.a Hình 5.1.b - Cây là cấu trúc phi tuyến. Một cây là tập hữu hạn các phần tử mà ta gọi là "nút"
(node), trong đó có một nút đặc biệt gọi là nút gốc (Root). Giữa các nút có một quan
hệ phân cấp gọi là quan hệ cha-con. - Định nghĩa đệ qui : + Một nút là một cây, nút đó cũng là gốc của cây. + Nếu n là một nút, và t1,t2,..,tk là các cây với n1, n2,..nk lần lƣợt là các gốc.
Cho n thành cha của các n1,n2, ,nk (các ni thành con của n, với i=1..k) ta đƣợc cây mới
T với n là gốc. Vậy cây T có các cây con là t1,t2,…,tn. Một số khái niệm trên cây : - Cấp: số nút con của một nút gọi là cấp của nút đó. Nút có cấp bằng không gọi là
nút lá. Nút không phải lá (trừ nút gốc) gọi là nhánh. Cấp cao nhất của nút trên cây gọi
là cấp của cây cây đó. - Mức: gốc của cây có mức bằng 1. Nếu nút cha có mức i thì nút con có mức i+1. - Chiều cao (sâu) của cây là mức lớn nhất của nút có trên cây đó. - Nếu n1,n2,..nk là dãy các nút mà ni là cha của ni+1 thì dãy đó gọi là đƣờng đi từ n1 đến nk. Độ dài của đƣờng đi bằng số nút trên đƣờng đi trừ 1. - Nếu thứ tự các cây con của một nút đƣợc coi trọng thì ta gọi cây có thứ tự ngƣợc lại cây không có thứ tự. - Tập hữu hạn các cây phân biệt gọi là rừng. Ví dụ: cây ở hình 5.2 có: Gốc là A; Con của A là B,C,D; A có cấp bằng 3, D có cấp bằng 4, cấp của cây bằng 4; Các nút C,E,F,G,I,J,K,L,M là các nút lá; Các nút B,D,H là các nút nhánh; A có mức bằng 1, B,C,D có mức bằng 2,…, các nút K,L,M có mức bằng 4; Chiều cao của cây bằng 4; độ dài đƣờng đi từ A đến H bằng 2, từ A đến M bằng 3 A C B D E F G H I J K L M Hình 5.2 5.2. Cây nhị phân 5.2.1. Định nghĩa 21 - Cây nhị phân là cây có thứ tự, mỗi nút chỉ có tối đa 2 con, gọi là con trái và con phải. (Hình 5.3) 15 27 12 17 22 40 45 28 33 20 9 13 19 14 Hình 5.3a 63 47 76 25 58 55 91 21 29 Hình 5.3b - Các dạng đặc biệt của cây nhị phân: + Cây lệch trái (Hình 5.4a), + Cây lệch phải (Hình 5.4b), + Cây zíc zắc (Hình 5.4c) - Cây nhị phân hoàn chỉnh là cây số nút ứng với các mức trừ mức cuối đều đạt tối đa. - Cây nhị phân đầy đủ là cây nhị phân có số nút ở các mức đều đạt tối đa. A A A B B B C C C D D D Hình 5.4b Hình 5.4c Hình 5.4a Tính chất : Bổ đề :
1) Số luợng tối đa các nút ở mức i trên cây nhị phân là 2i-1
2) Số luợng tối đa các nút trên cây nhị phân có chiều cao h là 2h-1 Chứng minh : 1) Ta sẽ chứng minh tính đúng đắn của bổ đề bằng qui nạp.
Ta thấy : ở mức i=1 cây nhị phân có tối đa là 1 nút =20 nút = 2i-1 nút, mệnh đề đúng với i=1. Giả sử mệnh đề đúng với mức i=k, tức là số nút tối đa ở mức k bằng 2k-1, Xét mức k+1, để có số nút tối đa ở mức này thì mỗi nút ở mức k+1 phải có 2 con.
Nhƣ giả thiết ở mức k ta đã có 2k-1 nút, vậy số nút ở mức k+1 sẽ là: (2k-1)x2= 2(k-
1)+1=2(k+1)-1. Bổ đề 1 đã đƣợc chứng minh. 2) Theo định nghĩa chiều cao của cây là số mức lớn nhất có trong cây đó. Vậy cây có chiều cao h thì số mức lớn nhất có trong cây đó cũng là h. Theo 1) suy ra tổng số nút tối đa có đƣợc của cây có chiều h sẽ là:
20 + 21 + 22 + …+2h-2 + 2h-1= (2h-1)/(2-1)=2h-1. Bổ đề 2 đã đƣợc chứng minh 5.2.2. Cấu trúc lưu trữ 5.2.2.1. Lưu trữ kế tiếp - Dùng một mảng một chiều để lƣu trữ. Số lƣợng phần tử trong mảng phải bằng số nút tối đa trong cây. - Ta đánh số thứ tự các nút trong cây theo dạng cây đầy đủ, bắt đầu từ mức 1 đến
mức cao nhất, mỗi mức đánh từ trái sang phải. Vậy một mức cha có số là i thì hai con
sẽ là 2i và 2i+1, nếu nút con có số là j thì nút cha sẽ là j/2 (chỉ số nguyên dƣới). - Với số thứ tự đã đánh của nút sẽ tƣơng ứng với một chỉ số vị trí trên mảng. Ví dụ : Cho cây nhị phân nhƣ hình 5.5, cấu trúc lƣu trữ nối tiếp: 1
A 2
B 3
C 5
D 6
E 7
F 4
Ta thấy vị trí con trái của B là không có nên vị trí số 4 mang giá trị rỗng. A C B F E D Hình 5.5 - Tổ chức một nút nhƣ sau: LEFT INFO RIGHT Trong đó : Trƣờng INFO: dùng lƣu dữ liệu của nút. Trƣờng LEFT: con trỏ, chứa địa chỉ nút con trái, nếu không có con trái LEFT chứa địa chỉ rỗng (null). Trƣờng RIGHT: con trỏ, chứa địa chỉ nút con phải, nếu không có con phải RIGHT chứa địa chỉ rỗng (null). T là con trỏ chứa địa chỉ nút gốc, ta nói cây đƣợc quản lý bởi con trỏ T. Minh họa lƣu trữ móc nối với cây ở hình 3.5 T A B C D E F Hình 5.6 5.2.3. Các phép du ệt câ Có rất nhiều ứng dụng đòi hỏi phải xử lý lần lƣợt các nút trên cây nhị phân theo
một thứ tự nào đó, có nghĩa phải đi qua các nút trên cây mỗi nút một lần. Ta gọi thao
tác này là phép duyệt cây. 5.2.3.1. Duyệt trước (duyệt theo thứ tự trước) Nếu cây rỗng thì không làm gì cả, Nếu cây khác rỗng thì : - Thăm gốc, - Duyệt con cây trái theo thứ tự trƣớc, - Duyệt cây con phải theo thứ tự trƣớc. Giải thuật duyệt trƣớc: Duyettruoc(T) {// T : trỏ đến gốc của cây //1. Kiểm tra T có rỗng không If (T !=null) { //2. In thông tin nút gốc printf(INFO(T)); //3. Gọi lại duyệt trƣớc cho nhánh con trái Duyettruoc(LEFT(T)); //4. Gọi lại duyệt trƣớc cho nhánh con phải Duyettruoc(RIGHT(T)); } //5. Kết thúc Return; } Ví dụ : - Cây ở hình 5.6 kết quả duyệt trƣớc: A, B, D, C, E, F - Cây ở hình 5.3b kết quả duyệt trƣớc: 63, 47, 25, 21, 29, 58, 76, 55, 91. 5.2.3.2. Duyệt theo thứ tự giữa Nếu cây rỗng thì không làm gì cả, Nếu cây khác rỗng thì : - Duyệt con cây trái theo thứ tự giữa, - Thăm gốc, - Duyệt cây con phải theo thứ tự giữa. Giải thuật duyệt giữa: Duyetgiua(T) { //T : trỏ đến gốc của cây if (T !=null) { Duyetgiua(LEFT(T)); printf(INFO(T)); Duyetgiua(RIGHT(T)); } Return } Ví dụ : - Cây ở hình 3.6 kết quả duyệt giữa: B, D, A, E, C, F - Cây ở hình 3.3b kết quả duyệt giữa: 21, 25, 29, 47, 58, 63, 55, 76, 91. 5.2.3.3. Duyệt theo thứ tự sau Nếu cây rỗng thì không làm gì cả, Nếu cây khác rỗng thì : - Duyệt con cây trái theo thứ tự sau, - Duyệt cây con phải theo thứ tự sau. - Thăm gốc Giải thuật duyệt sau: Duyetsau(T) { T : trỏ đến gốc của cây} If (T !=null) { Duyetsau(LEFT(T)); Duyetsau(RIGHT(T)); printf(INFO(T)); } 5. return Ví dụ : - Cây ở hình 3.6 kết quả duyệt giữa: D, B, E, F, C, A - Cây ở hình 3.3b kết quả duyệt giữa: 21, 29, 25, 58, 47, 55, 91, 76, 63. 5.3. Cây nhị phân tìm kiếm 5.3.1. Định nghĩa : Cây nhị phân tìm kiếm là cây nhị phân chứa dãy khóa (mỗi nút 1 khóa) sao cho: - Mọi giá trị khóa thuộc cây con trái đều nhỏ hơn giá trị khóa của nút đó. Vì vậy
khi duyệt cây nhị phân tìm kiếm theo thứ tự giữa (trái-gốc-phải) kết quả thu đƣợc là
dãy khóa theo thứ tự tăng dần và đây cũng là lƣu ý khi chúng ta muốn xây dựng cây
nhị phân tìm kiếm. - Mọi giá trị khóa thuộc cây con phải đều lớn hơn giá trị khóa của nút đó. 58 Ví dụ, cây ở hình 5.7 là cây nhị phân tìm kiếm 47 76 25 55 63 91 21 29 Hình 5.7 5.3.2. ìm ki m tr n câ nhị phân tìm ki m. BST(T,X) { //Giả sử cây đƣợc lƣu trữ móc nối và trƣờng INFO cũng chính là thông tin
tìm kiếm. T là con trỏ chứa địa chỉ gốc cây. X là giá trị khóa cần tìm. Nếu tìm thấy trả
lại địa chỉ nút tìm thấy, ngƣợc lại trả về địa chỉ null If (T==null) then return(null) If (X>INFO(T)) BST(RIGHT(T),X); else If (X else return(T); } *Nhận xét, đánh giá : Với một cây nhị phân tìm kiếm có n nút, ƣớc tính giải thuật tốn 1.386log2n phép so sánh. Vậy độ phức tạp trung bình của giải thuật là Ttb(n)=O(log2n). Ta thấy chiều cao của cây càng thấp thì tìm kiếm càng nhanh. Do vậy trong cây nhị phân tìm kiếm ngƣời ta quan tâm đến tính cân đối của cây. 5.3.3. Loại tr n câ nhị phân tìm ki m: Khi loại bỏ một nút trên cây tìm kiếm, cần quan tâm sao cho cây vẫn là cây tìm kiếm. Các trƣờng hợp loại bỏ và cách điều chỉnh : - Nút loại bỏ là nút lá: trƣờng con trỏ trỏ đến nó bây giờ cho trỏ về null. - Nút loại bỏ là nút nửa lá (chỉ có một con trái hoặc 1 con phải): trƣờng con trỏ trỏ đến nó bây giờ trỏ về con (trái hoặc phải) của nó. - Trƣờng hợp tổng quát: thay giá trị bị loại bỏ bằng giá trị của nút cực phải của
cây con trái hoặc giá trị của nút cực trái của cây con phải, và chỉnh lại các mối nối ở
một số nút có liên quan (nút cha của nút loại bỏ, nút đƣợc chọn là nút thay thế, nút cha
của nút đƣợc chọn làm nút thay thế). Ngoài ra trên cây nhị phân tìm kiếm ngƣời ta còn quan tâm đến cây nhị phân cân đối AVL, cây nhị phân tìm kiếm tối ƣu… TÓM TẮT CHƢƠNG 5 Định nghĩa đệ qui của cây:Cây có thể là: Một nút đứng riêng lẻ (và nó chính là gốc của cây này). Hoặc một nút kết hợp với một số cây con bên dưới Mỗi nút trong cây (trừ nút gốc) có đúng 1 nút nằm trên nó, gọi là nút cha
(parent). Các nút nằm ngay dưới nút đó được gọi là các nút con (subnode). Các nút
nằm cùng cấp được gọi là các nút anh em (sibling). Nút không có nút con nào được
gọi là nút lá (leaf) hoặc nút tận cùng. Chiều cao của nút là đường đi dài nhất từ nút tới một lá. Chiều cao của cây
chính là chiều cao của nút gốc. Độ sâu của 1 nút là độ dài đường đi duy nhất giữa nút
gốc và nút đó. Cây có thể được cài đặt bằng mảng các nút cha hoặc thông qua danh sách các nút con. Duyệt cây là thao tác thăm tất cả các nút của cây, mỗi nút đúng 1 lần. Duyệt cây có thể theo 3 phương pháp: Duyệt thứ tự đầu, thứ tự giữ, và thứ tự cuối. Cây nhị phân là một loại cây đặc biệt mà mỗi nút của nó chỉ có nhiều nhất là 2 nút con. Khi đó, 2 cây con của mỗi nút được gọi là cây con trái và cây con phải. Cây nhị phân tìm kiếm là cây nhị phân có tính chất sau: Với mỗi nút của cây,
khoá của các nút của cây con bên trái bao giờ cũng nhỏ hơn và khoá của các nút của
cây con bên phải bao giờ cũng lớn hơn hoặc bằng khoá của nút đó. Quá trình tìm kiếm trên cây nhị phân tìm kiếm như sau: Để tìm một nút có khoá
là x, đầu tiên tiến hành so sánh nó với khoá của nút gốc. Nếu nhỏ hơn, tiến hành tìm
kiếm ở cây con bên trái, nếu bằng nhau thì dừng quá trình tìm kiếm, và nếu lớn hơn thì
tiến hành tìm kiếm ở cây con bên phải. Quá trình tìm kiếm trên cây con lại được lặp
lại tương tự. BÀI TẬP CHƢƠNG 5. 1. Cho cây : A B C D E F G H I J K L M N O Hãy trả lời các câu hỏi sau : a) Các nút nào là nút lá? b) Các nút nào là nút nhánh? c) Cha của nút G là nút nào? d) Con của nút C là các nút nào? e) Các nút nào là anh em của B? f) Mức của D, của L là bao nhiêu? g) Cấp của D, của B là bao nhiêu? Cấp của cây làbao nhiêu/ h) Chiều cao của cay là bao nhiêu? i) Độ dài đƣờng đi từ A tới F, từ A tới O là bao nhiêu? j) Có bao nhiêu đƣờng đi có độ dài 3 trên cây này? 3. Cho cây nhị phân: A D E F C B G H I K L Hãy cho biết kết quả duyệt cây : a) Theo thứ tự trƣớc b) Theo thứ tự giữa c) Theo thứ tự sau d) Minh họa lƣu trữ kế tiếp với cây e) Minh họa lƣu trữ móc nối với cây, vẽ cây nối vòng với lƣu trữ móc nối. 3. Vẽ cây nhị phân biểu diễn biểu thức sau đây và và viết lại chúng dƣới dạng tiền tố, hậu tố. a) (a*b+c)/(d-e*f) b) A/(B+C)+D*E-A*C 4. Viết giải thuật tính số nút trên cây nhị phân 5. Viết giải thuật dựng cây nhị phân móc nối từ cây nhị phân nối tiếp. 6. Dựng cây nhị phân tƣơng ứng với cây tổng quát ở hình 6.1 7. Viết các giải thuật duyệt cây nhị phân theo giải thuật lặp(khử đệ qui). 8. Dựng cây nhị phân tìm kiếm với dãy khóa nhƣ sau : HAIPHONG, CANTHO,
NHATRANG, DALAT, THAINGUYEN, HANOI, DANANG, HUE, VINH,
NAMDINH, SAIGON. Đánh dấu đƣơng đi khi tim một khóa có giá trị là HONGAI
trong cây trên. 9. Xây dựng cây biểu thức. =================== CHƢƠNG 6. SẮP XẾP 6.1. Đặt vấn đề Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ
tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lƣu giữ tại mỗi phần tử. Ví dụ : - Sắp một dãy số theo thứ tự tăng dần - Sắp một danh sách sinh viên theo thứ tự giảm dần của điểm trung bình…. Ta gọi thông tin chọn làm tiêu chí sắp xếp là khóa sắp xếp. Từ đây, ta chỉ quan tâm đến thông tin chọn làm khóa sắp xếp. Cho dãy khóa k=(k1,k2,...,kn). Thực hiện sắp xếp dãy k theo thứ tự tăng dần. 6.2. Các phƣơng pháp sắp xếp đơn giản 6.2.1. Phương pháp sắp x p kiểu l a ch n(Selection Sort) - Ý tƣởng giải thuật : + Thực hiện n-1 bƣớc (1..n-1) công việc sau, + Ở bƣớc thứ i tìm khóa đúng cho vị trí thứ i, bằng cách so sánh ki với các giá trị
khóa ki+1, ki+2,...,kn để chọn ra giá trị khóa nhỏ nhất sau đó đổi chỗ với ki. Nhƣ vậy, giá
trị khóa đúng cho vị trí i đã tìm ra và đƣa về đúng chỗ Giải thuật sắp xếp kiểu lựa chọn: Select_Sort(K,n); { //K là dãy khóa cần sắp tăng dần, n là số phần tử trong K For (i=1; i { vt=i; for (j=i+1; j<=n; j++) if (kj < kvt ) vt=j; if (vt!=i) { tg=ki;
ki=kvt;
kvt=tg; } } Return; } Ví dụ minh họa, cho một mảng A gồm 8 phần tử : A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
75
32 83 66 11 51 27 45 Quá trình sắp xếp diễn ra nhƣ sau: Bƣớc 1
2
3
4
5
6
7 số nhỏ nhất A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
75
75
75
75
75
75
75
75 11
32
32
51
51
66
66
66 83
83
83
83
45
45
45
45 45
45
45
45
83
83
83
83 32
11
11
11
11
11
11
11 51
51
27
27
27
27
27
27 66
66
66
66
66
51
51
51 27
27
51
32
32
32
32
32 11
27
32
45
51
66
75 6.2.2. Phương pháp sắp x p kiểu th m d n ha chèn (Insert Sort) Ý tƣởng : Giống nhƣ những ngƣời chơi bài, khi bắt 1 quân bài ta tìm và chèn nó vào vị trí thích hợp trong tay bài. - Ban đầu dãy đã sắp chỉ có 1 phần tử k1
- Thực hiện n-1 bƣớc, bƣớc thứ i đƣa ki (i=2..n) vào đúng vị trí của nó trong dãy
đã sắp, bằng cách so sánh nó với các khóa đã sắp và dời chỗ: chừng nào ki còn nhỏ
hơn các khóa ki-1, ki-2, .., k1 thì dời lui mỗi phần tử đƣợc so sánh với ki về vị trí liền sau
nó, nếu tìm thấy vị trí j mà kj<=ki thì đƣa ki vào vị trí j+1. Để dễ cài đặt ngƣời ta đƣa thêm vào một khóa giả k0 có giá trị nhỏ hơn mọi giá trị khóa và ký hiệu là -. Giải thuật sắp xếp kiểu thêm dần Insert_Sort(K,n); { //K là dãy khóa cần sắp tăng dần, n là số phần tử trong K K0=-; // đặt khóa giả K0 bằng số nhỏ nhất trong miền giá trị
For (i=2;i<=n; i++) { X=Ki;
j=i-1; While (X { Kj+1=Kj;
j=j-1; } Kj+1=X; } Return; } Ví dụ minh họa, cho một mảng A gồm 8 phần tử : A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
75
32 83 66 11 51 27 45 Quá trình sắp xếp diễn ra nhƣ sau Bƣớc 1
2
3
4
5
6
7 số đƣợc xét A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
75
75
75
75
75
75
75
83 11
11
11
11
11
83
66
66 45
45
45
45
45
45
83
75 32
32
27
27
27
11
11
11 83
83
83
83
66
51
45
45 27
27
51
51
51
32
32
32 51
51
32
32
32
27
27
27 66
66
66
66
83
66
51
51 51
27
83
66
11
45
75 6.2.3. Phương pháp sắp x p kiểu đổi chổ (Exchange Sort) Ý tƣởng : + Thực hiện n-1 bƣớc (1..n-1) + Tại bƣớc thứ i(i=1..n) tìm ra phần tử khóa đúng cho vị trí i, bằng cách đi từ
cuối dãy lên vị trí thứ i+1, dọc đƣờng gặp 2 khóa kế cận ngƣợc thứ tự thì đổi chỗ
chúng cho nhau. Nhƣ vậy khóa nhỏ hơn sẽ nổi dần lên qua mỗi lƣợt, do vậy giải thuật
còn có tên giải thuật nổi bọt Buble sort). Giải thuật sắp xếp kiểu đổi chỗ Exchange_Sort(K,n); { //K là dãy khóa cần sắp tăng dần, n là số phần tử trong K For (i=1; i (j=n; j>=i+1; j--) if (Kj < Kj-1 )
{ tg=Kj;
Kj=Kj-1;
Kj-1=tg; } Return; } Ví dụ minh họa, cho một mảng A gồm 8 phần tử : A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
75
32 83 66 11 51 27 45 Quá trình sắp xếp diễn ra nhƣ sau Ban đầu Lƣợt thứ 5
11
27
32 6
11
27
32 7
11
27
32 A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8] 32
51
27
83
66
11
45
75 1
2
11 11
32
51
27
83
66
45
75 3
11
27 27
32
51
45
83
66
75 4
11
27
32 32
45
51
66
83
75 45
51
66
75
83 45
51
66
75
83 45
51
66
75
83 45
51
66
75
83 Nhận xét, đánh giá 3 phƣơng pháp : Độ phức tạp giải thuật: - Phƣơng pháp sắp xếp kiểu lựa chọn : độ phức tạp bằng với số lần thực hiện phép so sánh, do đó : Tt(n)=Tx(n)=Ttb(n)=O((n(n-1))/2)=O(n2) - Phƣơng pháp sắp xếp kiểu đổi chỗ cũng tƣơng tự : Tt(n)=Tx(n)=Ttb(n)=O(n2)
- Riêng phƣơng pháp sắp xếp kiểu thêm dần tùy thuộc vào tình trạng dữ liệu ban
đầu của dãy. Nếu dãy ban đầu đã sắp tăng dần thì chỉ cần (n-1) phép so sánh, vậy
Tt(n)=O(n). Ngƣợc lại, nếu dãy ban đầu đã sắp giảm dần thì cần (n(n-1))/2 phép so
sánh, vậy Tx(n)=O(n2). Ngƣời ta chứng minh đƣợc độ phức tạp trung bình của dãy này
Ttb(n)=O(n2). Tóm lại, 3 giải thuật đều có độ phức tạp trung bình là O(n2). Điều này dẫn đến tính hiệu quả sẽ giảm khi n lớn. 6.2.4.Sắp x p nhanh (Quick Sort) ha sắp x p kiểu phân đoạn (Partition Sort) Ý tƣởng : Sử dụng chiến thuật "chia để trị", điều này dẫn đến 1 giải thuật sắp xếp
đệ qui. Với một dãy khóa chƣa sắp, chọn ngẫu nhiên 1 khóa trong dãy làm "chốt",
những phần tử nhỏ hơn khóa chốt phải đƣợc xếp trƣớc chốt, những phần tử lớn hơn
chốt phải đƣợc xếp sau chốt. Dãy khóa lúc này phân thành 2 dãy con chƣa sắp và một
khóa chốt đã sắp. Cứ thế lặp lại công việc trên cho mỗi dãy con chƣa sắp cho đến khi
dãy chƣa sắp chỉ còn 1 phần tử hoặc rỗng. Để đƣa những giá trị khóa nhỏ hơn chốt về
trƣớc chốt và những giá trị khóa lớn hơn chốt về sau chốt ta thực hiện các phép so
sánh và đổi chỗ. Giải thuật sắp xếp nhanh: Quick Sort(K,LB,UB) { /K: dãy khóa với n phần tử, //LB: cận dƣới của dãy, UB: cận trên của dãy //Sử dụng khóa giả Kn+1 có giá trị lớn hơn mọi khóa để chặn trên}
//Sử dụng biến Kt kiểu boolean để kiểm soát quá so sánh, đổi chổ để phân dãy //1. ban đầu kt=true; //2. thực hiện phân đoạn và gọi đệ qui cho các đoạn if (LB { i=LB; j=UB+1; key =KLB; While (kt) { i=i+1; i=i+1; while (Ki j=j+1; while (Kj>key)
if (i { tg=Ki;
Ki=Kj;
Kj=tg; } else kt=false; } tg=KLB;
KLB=Kj;
Kj=tg; Quick_Sort(K,LB,j-1); Quick_Sort(K,j+1,UB); } //3. Kết thúc Return; } Ví dụ minh họa, cho dãy khóa: A =(75, 70, 65, 84, 98, 78, 100, 93, 55, 61, 81, 68) A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11] A[12] 75 70 65 84 98 78 100 93 55 61 81 68 Lƣợt 1: gọi Quick_Sort(A,1,12) và quá trình phân đoạn diễn ra nhƣ sau: LB=1, UB=12, chọn chốt key=A[LB]=75, kt=true 70 65 84 98 78 100 93 55 61 81 68 75
i=2 +
j=13 Tăng i : 98 78 100 93 55 61 81 75 70 65 68
j=12 84
i=4 Giảm j : 98 78 100 93 55 61 81 75 70 65 68
j=12 84
i=4 i 98 78 100 93 55 61 81 75 70 65 84
j=12 68
i=4 Tiếp tục tăng i 78 100 93 55 61 81 75 70 65 68 78 100 93 55 81 84
j=12
84 75 70 65 68 98
i=5
98
i=5 61
j=10 i 78 100 93 55 81 84 75 70 65 68 61
i=5 98
j=10 Tiếp tục tăng i 75 70 65 68 61 55 81 84 78 100 93
i=6 98
j=10 Tiếp tục giảm j 75 70 65 68 61 98 81 84 78 100 93
i=6 55
j=9 i 75 70 65 68 61 98 81 84 55 100 93
i=6 78
j=9 Tiếp tục tăng i 75 70 65 68 61 55 100 93 78 98 81 84 i=7 j=9 Tiếp tục giảm j 75 70 65 68 61 78 98 81 84 55 100 93
i=7
j=6 j 55 70 65 68 61 75 100 93 78 98 81 84 Dãy tách làm 2 dãy con: + Dãy con gồm những khóa nhỏ hơn chốt: 55 70 65 68 61 + Dãy con gồm những khóa lớn hơn chốt: 100 93 78 98 81 84 Gọi đệ qui cho mỗi dãy con nhỏ: Quick_Sort(A,1,5); Gọi đệ qui cho mỗi dãy con lớn: Quick_Sort(A,7,12); Quá trình trở lại với mỗi dãy con. *Nhận xét, đánh giá: - Vấn đề chọn chốt: giải thuật hoạt động tốt nhất khi chốt đƣợc chọn rơi vào
trung vị của dãy, lúc này chốt sẽ tách dãy thành hai dãy con có độ dài tƣơng đƣơng
nhau. Giải thuật xấu nhất khi chốt đƣợc chọn là giá trị lớn nhất hoặc nhỏ nhất trong
dãy, lúc này chỉ tách đƣợc một dãy còn dãy kia là rỗng. Nhƣng việc chọn đúng trung
vị là rất khó, để dung hòa ngƣời ta đƣa ra cách chọn chốt nhƣ sau: key là chốt với key
là trung vị của 3 khóa KLB, K(LB+UB/2), và KUB. - Độ phức tạp tính đƣợc: Tt(n)=O(nlog2n), Tx(n)=O(n2), Ttb(n)=O(nlog2n), Ta thấy giải thuật Quick sort có hiệu lực hơn 3 giải thuật trƣớc. Thông thƣờng
ngƣời ta áp dụng Quick sort cho kích thƣớc dữ liệu lớn, đến khi kích thƣớc nhỏ hơn
hoặc bằng 9 thì chuyển sang dùng các giải thuật cơ bản. 6.2.5.Sắp x p vun đ ng ( eap Sort) Ý tƣởng cơ bản của giải thuật này là thực hiện sắp xếp thông qua việc tạo các
heap, trong đó heap là 1 cây nhị phân hoàn chỉnh có tính chất là khóa ở nút cha bao
giờ cũng lớn hơn khóa ở các nút con. Việc thực hiện giải thuật này đƣợc chia làm 2 giai đoạn. Đầu tiên là việc tạo heap
từ dãy ban đầu. Theo định nghĩa của heap thì nút cha bao giờ cũng lớn hơn các nút
con. Do vậy, nút gốc của heap bao giờ cũng là phần tử lớn nhất. Giai đoạn thứ 2 là việc sắp dãy dựa trên heap tạo đƣợc. Do nút gốc là nút lớn
nhất nên nó sẽ đƣợc chuyển về vị trí cuối cùng của dãy và phần tử cuối cùng sẽ đƣợc
thay vào gốc của heap. Khi đó ta có 1 cây mới, không phải heap, với số nút đƣợc bớt
đi 1. Lại chuyển cây này về heap và lặp lại quá trình cho tới khi heap chỉ còn 1 nút. Đó chính là phần tử bé nhất của dãy và đƣợc đặt lên đầu. Các thuật toán trên heap Nhƣ vậy, việc đầu tiên cần làm là phải tạo đƣợc 1 heap từ 1 dãy phần tử cho
trƣớc. Để làmviệc này, cần thực hiện thao tác chèn 1 phần tử vào 1 heap đã có. Khi đó,
kích thƣớc của heap tăng lên 1, và ta đặt phần tử mới vào cuối heap. Việc này có thể
làm vi phạm định nghĩa heap vì nút mới có thể lớn hơn nút cha của nó. Vấn đề này
đƣợc giải quyết bằng cách đổi vị trí nút mới cho nút cha, và nếu vẫn vi phạm định
nghĩa heap thì ta lại giải quyết theo cách tƣơng tự cho đến khi có một heap mới hoàn
chỉnh. Giả sử ta đã có 1 heap nhƣ sau: Để chèn phần tử 61 vào heap, đầu tiên, ta đặt nó vào vị trí cuối cùng trong cây Rõ ràng cây mới vi phạm định nghĩa heap vì nút con 61 lớn hơn nút cha 17. Tiến hành đổi vị trí 2 nút này cho nhau: Cây này vẫn tiếp tục vi phạm định nghĩa heap do nút con 61 lớn hơn nút cha 49. Lại đổi vị trí 61 cho 49 Do nút con 61 nhỏ hơn nút cha 98 nên cây thoả mãn định nghĩa heap. Nhƣ vậy, ta đã có một heap với nút mới đƣợc thêm vào là 61. Để chèn một phần tử x vào 1 heap đã có k phần tử, ta gán phần tử thứ k +1, a[k], bằng x, rồi gọi Giải thuật upheap(k). upheap(m) { x=a[m]; while ((a[(m-1)/2]<=x) && (m>0)){ a[m]=a[(m-1)/2]; m=(m-1)/2; } a[m]=x; } void insert_heap(int x){ a[m]=x; upheap(m); m++; } Nhƣ vậy, với heap ban đầu chỉ có 1 phần tử là phần tử đầu tiên của dãy, ta lần
lƣợt lấy các phần tử tiếp theo của dãy chèn vào heap sẽ tạo đƣợc 1 heap gồm toàn bộ n
phần tử. Ta hãy xem xét quá trình tạo heap với dãy số đã cho: 32 17 49 98 06 25 53 61 Đầu tiên, tạo 1 heap với chỉ 1 phần tử là 32: Bƣớc 1: Tiến hành chèn 17 vào heap. không vi phạm định nghĩa heap nên không thay đổi gì Bƣớc 2: Tiến hành chèn 49 vào heap Cây mới thoả mãn định nghĩa heap. Bƣớc 3: Tiến hành chèn 98 vào heap Cây này vi phạm định nghĩa heap do 98>17 nên đổi vị trí 98 và 17 cho nhau . Cây mới lại vi phạm định nghĩa heap, do 98>49, nên đổi vị trí 98 cho 49. Cây này thoả mãn định nghĩa heap. Bƣớc 4: Tiến hành chèn 06 vào heap Cây này thoả mãn định nghĩa heap do 06<49 Bƣớc 5: Tiến hành chèn 25 vào heap Cây này thoả mãn định nghĩa heap do 25<32. Bƣớc 6: Tiến hành chèn 53 vào heap Cây này vi phạm định nghĩa heap do 53>32 nên đổi vị trí 53 và 32 cho nhau Cây mới thoả mãn định nghĩa heap Bƣớc 7: Tiến hành chèn 61 vào heap. Cây này vi phạm định nghĩa heap do 61>17 nên đổi vị trí 61 và 17 cho nhau Cây mới tiếp tục vi phạm định nghĩa heap do 61>49 nên đổi vị trí 61 và 49 cho nhau Cây này thoả mãn định nghĩa heap và chính là heap cần tạo. Sau khi tạo đƣợc heap, để tiến hành sắp xếp, ta cần lấy phần tử đầu và là phần tử
lớn nhất của cây và thay thế nó bằng phần tử cuối của dãy. Điều này có thể làm vi
phạm định nghĩa heap vì phần tử mới đƣa lên gốc có thể nhỏ hơn 1 trong 2 nút con. Do đó, thao tác thứ 2 cần thực hiện trên heap là tiến hành chỉnh lại heap khi có 1
nút nào đó nhỏ hơn 1 trong 2 nút con của nó. Khi đó, ta sẽ tiến hành thay thế nút này
cho nút con lớn hơn Nếu vẫn vi phạm định nghĩa heap thì ta lại lặp lại quá trình cho tới khi nó lớn hơn cả 2 nút con hoặc trở thành nút lá. Ta xem xét ví dụ với heap vừa tạo đƣợc ở phần trƣớc Lấy nút gốc 98 ra khỏi heap và thay thế bởi nút cuối là 17 Cây này không thoả mãn định nghĩa heap vì 17 nhỏ hơn cả 2 nút con là 61 và 53. Tiến hành đổi chỗ 17 cho nút con lớn hơn là 61 Vẫn tiếp tục vi phạm định nghĩa heap do 17 nhỏ hơn nút con là 49. Tiến hành đổi chỗ 17 cho 49, ta có heap mới hoàn chỉnh Ta có Giải thuật downheap để chỉnh lại heap khi nút k không thoả mãn định nghĩa heap nhƣ sau: downheap(k) { int j, x; x=a[k]; while (k<=(m-2)/2){ j=2*k+1; if (j if (x>=a[j]) break; a[k]=a[j]; k=j; } a[k]=x; } Cuối cùng, Giải thuật heap sort thực hiện việc sắp xếp trên heap đã tạo nhƣ sau: remove_node() { int temp; temp=a[0]; a[0]=a[m]; m--; downheap(0); return temp; } heap_sort(){ int i; m=0; for (i=0; i<=n-1; i++) insert_heap(a[i]); m=n-1; for (i=n-1; i>=0; i--) a[i]=remove_node(); } TÓM TẮT CHƢƠNG 6 Sắp xếp là quá trình bố trí lại các phần tử của 1 tập hợp theo thứ tự nào đó đối với 1 tiêu chí nào đó. Các giải thuật sắp xếp đơn giản dễ dàng trong việc cài đặt nhưng thời gian thực hiện lớn. Các giải thuật sắp xếp phức tạp cài đặt khó khăn hơn nhưng có thời gian chạy nhanh hơn. Các giải thuật sắp xếp đơn giản có thời gian thực hiện là O(N2) trong khi các giải thuật sắp xếp phức tạp có thời gian thực hiện là O(NlogN) Quick sort là giải thuật sắp xếp dựa trên phương pháp chia để trị: Chia dãy cần
sắp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập với nhau. Các
phần tử trong 1 phần luôn nhỏ hơn 1 giá trị khoá, còn các phần tử trong phần còn lại
luôn lớnhơn giá trị khoá. Heap sort là 1 giải thuật sắp xếp dựa trên heap. Đó là một cây nhị phân hoàn
chỉnh có tính chất khoá của nút cha bao giờ cũng lớn hơn khoá của các nút con. Quá
trình sắp xếp sẽ đổi chỗ nút gốc của heap cho nút cuối, chỉnh lại heap và lại lặp lại
qúa trình cho tới khi dãy được sắp hoàn toàn. ======================== BÀI TẬP CHƢƠNG 6 1. Hãy viết lại các giải thuật sắp xếp trên theo tiêu chí giảm dần của giá trị khóa. 2. Cho dãy khóa : 50, 08, 34, 06, 98, 17, 83, 25, 66, 42, 21, 59, 62, 71, 85, 76. Hãy minh họa tình trạng thay đổi dữ liệu khi sử dụng các phƣơng pháp sắp xếp đã học để sắp dãy theo thứ tự tăng dần, giảm dần. 3. Với giải thuật đổi chỗ có thể duyệt từ trên xuống thay cho đi từ dƣới lên không. Nếu đƣợc thì viết nhƣ thế nào? Cho ví dụ minh họa. 4. Dùng ngôn ngữ C cài đặt các giải thuật sắp xếp trên mảng một chiều và trên danh sách liên kết. Rút ra nhận xét của 2 cách lƣu trữ ứng với các tác động giải thuật. ============== CHƢƠNG 7. TÌM KIẾM 7.1. Đặt vấn đề Tìm kiếm là vấn đề rất thƣờng xuyên xảy ra trong Tin học. Ví dụ: tìm một tên
trong danh sách lớp, tìm một số báo danh trong danh sách thí sinh, tìm một mã sách
trong chƣơng trình quản lý thƣ viện,... . Nhƣ trong phần sắp xếp, ta gọi tiêu chí dùng
để tìm kiếm là khóa. Cho dãy khóa k=(k1, k2,..,kn), và một giá trị x. Tìm ki=x. Một trong hai trƣờng hợp sau sẽ xảy ra: + Tìm thấy ki =x, chỉ ra vị trí tìm thấy i.
+ Không tìm thấy ki nào bằng với x, trả về một vị trí rỗng. 7.2. Tìm kiếm tuần tự Ý tƣởng : lần lƣợt so sánh x với các giá trị trong dãy khóa, bắt đầu từ k1, cho đến
khi gặp giá trị khóa đầu tiên bằng với x thì dừng hoặc tìm đến cuối dãy mà vẫn không
thấy. Giải thuật tìm tuần tự : Sequen_Search(K,n,X) { //K là dãy khóa gồm n phần tử. X là giá trị cần tìm. //Sử dụng khóa giả kn+1 bằng với X để làm điều kiện dừng //1. khởi đầu từ k1 i =1; kn+1=x; //2. {tìm khóa trong dãy} i=i+1; While (ki!=X)
If (i = n+1)
// 3. return(0); Else return(i); } Ví dụ: Minh họa các bƣớc của giải thuật khi tìm X=40, trong dãy: K= 12, 37, 25, 41, 35, 40, 69, 29, 71, 53, 64. N=11; X=40; K[11]=40; i=1; k[1]=12!=40; tăng i lên 1 đơn vị i=2; k[2]=37!=40; tăng i lên 1 đơn vị i=3; k[3]=25!=40; tăng i lên 1 đơn vị i=4; k[4]=41!=40; tăng i lên 1 đơn vị i=5; k[5]=35!=40; tăng i lên 1 đơn vị i=6; k[6]=40=40; dừng trả về 6 7.3. Tìm kiếm nhị phân Yêu cầu : dãy khóa k=(k1, k2,..,kn), phải đƣợc sắp xếp tăng hoặc giảm. Giả sử dãy đƣợc xếp tăng dần. Ý tƣởng : nếu gọi l là vị trí đầu dãy, r là vị trí cuối dãy, j=(l+r)/2 là vị trí giữa
của dãy. Tìm nhị phân sẽ so sánh X với kj. Nếu X=kj thì tìm thấy chỉ ra vị trí j và
dừng, nếu X>kj thì tìm X ở nửa sau (kj+1 ..kn), nếu X Giải thuật tìm kiếm nhị phân: Binary_Search(K,n,X) { //K là dãy khóa gồm n phần tử. X là giá trị cần tìm. //Sử dụng khóa giả kn+1 bằng với X để làm điều kiện dừng //1. khởi đầu l=1; r=n; //2. tìm while (l<=r) { //3. xác định vị trí giữa j= (l+r)/2 ; //4. so sánh vị trí giữa với X r=j-1 ; { đổi cận trên} if (X {đổi cận dƣới} if (X>kj) l=j+1;
else return(j) {tìm thấy và trả về vị trí} } //5.không tìm thấy Return(0); } Ví dụ: Minh họa các bƣớc của giải thuật khi tìm X=40, trong dãy: K= 12, 25, 40, 49, 55, 71, 83, 94, 99. l=1; r=9; bƣớc 1: 1<9; j=(1+9)/2=5; k[5]=55>40; r=5-1=4; bƣớc 2: 1<4; j=(1+4)/2=3; k[3]=40=40; dừng; trả về 3 7.4. Nhận xét đánh giá: - Với giải thuật tìm tuần tự, độ phức tạp tốt nhất khi X=k1, lúc này chỉ dùng 1
phép so sánh, do đó Tt(n)=O(1). Xấu nhất là không tìm thấy, dùng n+1 phép so sánh
Tx(n)=O(n+1)=O(n). Ngƣời ta cũng tính đƣợc độ phức tạp trung Ttb(n)=O(n). - Với giải thuật tìm nhị phân, độ phức tạp tốt nhất khi X=k(1+n)/2 , chỉ dùng 1
phép so sánh, Tt(n)=O(1). Xấu nhất là không tìm thấy, ngƣời ta tính đƣợc
Tx(n)=O(log2n). Ngƣời ta cũng tính đƣợc Ttb(n)=O(log2n). Ta thấy tìm tuần tự chậm hơn tìm nhị phân, tuy nhiên với giải thuật tìm nhị phân
ta phải tốn chi phí sắp xếp. Vậy tùy thuộc vào tình trạng dữ liệu mà quyết định phƣơng
pháp. TÓM TẮT CHƢƠNG 7 Tìm kiếm là việc thu thập một số thông tin nào đó từ một khối thông tin lớn đã được lưu trữ trước đó. Tìm kiếm tuần tự lần lượt duyệt qua toàn bộ các bản ghi một cách tuần tự. Tại
mỗi bước, khoá của bản ghi sẽ được so sánh với giá trị cần tìm. Quá trình tìm kiếm kết
thúc khi đã tìm thấy bản ghi có khoá thoả mãn hoặc đã duyệt hết danh sách. Tìm kiếm nhị phân sử dụng phương pháp chia để trị: Chia tập cần tìm làm 2 nửa, xác định nửa chứa bản ghi cần tìm và tập trung tìm kiếm trên nửa đó. BÀI TẬP CHƢƠNG 7 1. Viết giải thuật tìm kiếm tuần tự cho dãy khóa đƣợc lƣu trữ móc nối. 2. Hãy dùng cây nhị phân để biểu diễn giải thuật tìm kiếm nhị phân ứng với n=9. CHƢƠNG 8. NGĂN XẾP VÀ HÀNG ĐỢI Chương 8 trình bày về hai cấu trúc dữ liệu rất gần gũi với các hoạt động trong thực tế, đó là ngăn xếp và hàng đợi. Phần 1 trình bày các khái niệm, định nghĩa liên quan đến ngăn xếp, khai báo
ngăn xếp bằng mảng và các thao tác cơ bản như kiểm tra ngăn xếp rỗng, đưa phần tử
vào ngăn xếp, lấy phần tử ra khỏi ngăn xếp. Một cách cài đặt ngăn xếp khác cũng
được giới thiệu, đó là dùng danh sách liên kết. Việc sử dụng danh sách liên kết để cài
đặt sẽ cho một ngăn xếp có kích thước linh hoạt hơn. Phần 2 trình bày về hàng đợi. Tương tự như phần 1, các khái niệm, các cách cài đặt và các thao tác cơ bản trên ngăn xếp cũng được trình bày chi tiết. Để học tốt chương 8, sinh viên cần có liên hệ với các hoạt động thực tế để
hình dung về ngăn xếp và hàng đợi. Nắm vững cách cài đặt và các thao tác trên 2 kiểu
dữ liệu này. Tự đặt ra các bài toán ứng dụng thực tế để thực hiện. 8.1. Stack 8.1.1. Định nghĩa Stack là một danh sách tuyến tính đặc biệt mà phép bổ sung và phép loại bỏ luôn luôn thực hiện ở một đầu gọi là đỉnh (Top). Có thể hình dung trong Stack các phần tử đƣợc xếp chồng lên nhau, phần tử nào
đƣa vào đầu tiên sẽ xếp dƣới cùng, phần tử nào đƣa vào sau cùng sẽ nằm trên hết. Việc
lấy các phần tử ra là quá trình ngƣợc lại, phần tử trên cùng sẽ lấy ra trƣớc. Minh họa stack với 6 phần tử: đỉnh đáy 6
5
4
3
2
1 Nhƣ vậy stack hoạt động theo cơ chế: "vào sau ra trƣớc" (last in - first out). 8.1.2. Lưu trữ k ti p đ i với Stack Dùng một mảng một chiều S có n phần tử để cài đặt Stack. Mỗi phần tử của S lƣu đƣợc 1 phần tử trong danh sách. Gọi T là đỉnh của của stack S. T=0 thì Stack rỗng. T=n stack đầy, T>n Stack tràn. S1 S2 S3 Sn ... đáy T Khởi tạo T=0, bổ sung (thêm vào) một phần tử vào stack thì T tăng 1, lấy ra (loại bỏ) 1 phần tử T giảm 1. 8.1.2.1. Bổ sung 1 phần tử vào stack PUSH(S,T,X) /* S là mảng n phần tử dùng cài đặt stack, T: chỉ số đỉnh X: giá trị cần bổ sung*/ 1. //Kiểm tra đầy if (T==n) { printf(' stack đầy'); return; } 2.//tăng đỉnh T lên 1 T=T+1; 3. //đƣa giá trị bổ sung vào S[T]=X; 4. return 8.1.2.2. Loại bỏ phẩn tử khỏi Stack POP(S,T) 1. //kiểm tra cạn if (T==0) { printf(' stack cạn'); return } 2. {giảm đỉnh T xuống 1} T=T-1; 3. { đƣa giá trị bị loại ra } POP=S[T+1]; 4. return 8.1.3. Lưu trữ m c n i với satck - Dùng danh sách liên kết đơn, theo cơ chế vào sau ra trƣớc. Con trỏ đầu danh sách cũng chính là đỉnh của stack. T INFO LINK Null 8.2. Ứng dụng ngăn xếp 8.2.1. Ví dụ áp dụng - Đổi cơ số - Định giá biểu thức số học theo ký pháp nghịch đảo Balan Ví dụ 1: Giả sử ngƣời ta cần chuyển một biểu thức dƣới dạng TRUNG TỐ về dạng HẬU TỐ bằng cách sử dụng STACK theo cách sau: Duyệt biểu thức từ trái sang phải Nếu gặp dấu mở ngoặc: bỏ qua Nếu gặp toán hạng: đƣa vào biểu thức mới Nếu gặp toán tử: đƣa vào stack Nếu gặp dấu đóng ngoặc: lấy toán tử trong stack đƣa vào biểu thức mới Áp dụng để chuyển biểu thức đƣợc cho ở dạng trung tố: (2*(((4-6)*(8+10))- 6))sang dạng hậu tố Thứ tự thực hiện: Gặp dấu (: bỏ qua Gặp số 2: đƣa vào biểu thức mới = 2 Gặp phép toán *: đƣa vào stack Gặp dấu (: bỏ qua Gặp dấu (: bỏ qua Gặp dấu (: bỏ qua Gặp số 4: đƣa vào biểu thức mới =2 4 Gặp phép toán -: đƣa vào stack Gặp số 6: đƣa vào biểu thức mới = 2 4 6 Gặp dấu ): lấy ra phép -, biểu thức mới = 2 4 6 – Gặp phép toán *: đƣa vào stack Gặp dấu (: bỏ qua Gặp số 8: đƣa vào biểu thức mới = 2 4 6 - 8 Gặp phép toán +: đƣa vào stack Gặp số 10: đƣa vào biểu thức mới = 2 4 6 – 8 10 Gặp dấu ): lấy ra phép +, biểu thức mới = 2 4 6 – 8 10 + Gặp dấu ): lấy ra phép *, biểu thức mới = 2 4 6 – 8 10 + * Gặp phép toán -: đƣa vào stack Gặp số 12: đƣa vào biểu thức mới = 2 4 6 – 8 10 + * 12 Gặp dấu ): lấy ra phép -, biểu thức mới = 2 4 6 – 8 10 + * 12- Gặp dấu ): lấy ra phép *, biểu thức mới = 2 4 6 – 8 10 + * 12 - * KẾT QUẢ BIỂU THỨC Ở DẠNG HẬU TỐ TƢƠNG ỨNG: = 2 4 2 – 8 10 + * 12 - * Ví dụ 2: Ta có thuật toán để tính giá trị biểu thức ở dạng hậu tố bằng cách sử dụng stack nhƣ sau: Duyệt biểu thức từ trái sang phải Nếu gặp toán hạng đƣa vào stack Nếu gặp toán tử lấy hai toán hạng từ stack, sử dụng toán tử trên để tính giá trị rồi đƣa lại kết quả vào stack Áp dụng: tính giá trị của biểu thức sau: 3 5 2 – 7 1 + * 6 - * Thứ tự thực hiện: Gặp số 3: đƣa vào stack Gặp số 5: đƣa vào stack Gặp số 2: đƣa vào stack Gặp phép toán -: lấy 2 và 5 ra khỏi stack, thực hiện 5-2=3, đƣa 3 vào stack Gặp số 7: đƣa vào stack Gặp số 1: đƣa vào stack Gặp phép toán +: lấy 7 và 1 ra khỏi stack, thực hiện 7+1=8, đƣa 8 vào stack Gặp phép toán *: lấy 8 và 3 ra khỏi stack, thực hiện 8*3=24, đƣa 24 vào stack Gặp số 6: đƣa vào stack Gặp phép toán -: lấy 6 và 24 ra khỏi stack, thực hiện 24-6=18, đƣa 18 vào stack Gặp phép toán *: lấy 18 và 3 ra khỏi stack, thực hiện 18*3=54, đƣa 54 vào stack Dừng. Kết quả=54 8.2.2. Stack và việc vài đặt Giải thuật đệ qui - Khi một Giải thuật đệ qui đƣợc gọi tới từ chƣơng trình chính ta nói : Giải thuật
thực hiện ở mức 1. Nhƣng khi thực hiện ở mức một thì lại gặp lời gọi tới chính nó,
nghĩa là phải đi sâu vào mức 2 và cứ nhƣ vậy cho tới một mức k nào đó. Rõ ràng mức
k hoàn thành xong thì mức k-1 mới đƣợc thực hiện và cứ nhƣ thế cho đến khi về đến
mức 1, lúc này ta có đƣợc kết quả cuối cùng. vậy cơ chế đệ qui cũng là cơ chế hoạt
động của stack. 8.3. Queue 8.3.1. Định nghĩa : Queue là kiểu danh sách tuyến tính mà phép bổ sung đƣợc thực hiện ở một đầu, gọi là lối sau và phép loại bỏ thực hiện ở một đầu khác, gọi là lối trƣớc. Cơ chế của queue giống nhƣ một hàng đợi, ngƣời nào đến trƣớc đứng trƣớc và
đƣợc xử lý trƣớc, ngƣời nào đến sau đứng sau và đƣợc xử lý sau. Vậy cơ chế của
queue là" vào trƣớc ra trƣớc"(first in - first out) 8.3.2. Lưu trữ k ti p với Queue Có thể dùng một mảng một chiều Q có n phàn tử để cài đặt Queue. Q1 Q2 Q3 Qn ... F R Gọi F(front) là chỉ số lối trƣớc, hay lối ra. R là chỉ số lối sau, hay lối vào. Khởi tạo(queue rỗng) F=R=0, bổ sung phẩn tử đầu tiên F=R=1, bổ sung một
phần tử tiếp R tăng lên 1, loại bỏ một phần tử F tăng lên 1. Nếu thực hiện liên tiếp các
phép bổ sung và loại bỏ thì F và R tiến đều về n và có khả năng xãy ra tình trạng R=n
(queue đầy), không thể bổ sung đƣợc nữa nhƣng thực chất trƣớc F còn rất nhiều
khoảng trống mà các phần tử đã loại bỏ để lại. Minh họa: Q với 5 phần tử. - Ban đầu F=R=0 (queue rỗng) 1 2 3 4 5 F=R - Bổ sung phần tử đầu có giá trị A: 2 3 4 5 1
A
F,R - Bổ sung tiếp 2 phần tử B và C: 4 5 2
B 1
A
F 3
C
R - Loại bỏ 1 phần tử: 1 4 5 2
B
F 3
C
R - Bổ sung tiếp 2 phần tử D và E: 1 3
C 4
D 2
B
F 5
E
R - Loại bỏ 2 phần tử: 1 2 3 4
D
F 5
E
R - Bổ sung phẩn tử có giá trị X, với queue không nối vòng lúc này đã đầy, không thể bổ sung đƣợc mặc dù còn tới 3 khoảng trống phía trƣớc. Ngƣời ta khắc phục hạn chế trên bằng cách tổ chức queue nối vòng, khi R=n bổ
sung thêm phần tử thì cho R trở về bằng 1 với điều kiện lúc này RF. Tƣơng tự nhƣ
vậy khi F=n thì cho F về 1. Minh họa bổ sung giá trị X vào queue nối vòng: 2 3 5
E 1
X
R 4
D
F 8.3.2.1. Bổ sung một phần tử vào Queue nối vòng QINSERT(Q,F,R,X); //Q là mảng một chiều, F là chỉ số lối ra, R là chỉ số lối vào, X giá trị cần bổ sung 1. //kiểm tra đầy If( (F==1 && R==)||(F=R+1)) { printf('Q đầy'); return; } 2.//chỉnh lại R để bổ sung If (F==0) F=R=1 //queue rỗng Else If (R==n) R=1 else R=R+1; 3.//đƣa X vào Q[R]=X; 4. Return 8.3.2.2. Loại bỏ 1 phần tử khỏi Q QDELETE(Q,F,R); //Q là mảng một chiều, F là chỉ số lối ra, R là chỉ số lối vào 1. //kiểm tra cạn If (F==0) then { printf('Q cạn'); return(0) } 2.//lấy thông tin phần tử bị loại Y=Q[F]; 3.//Chỉnh lại F If (F==R) F=R=0; //queue rỗng Else if (F==n) F=1 else F=F+1; 4. Return(Y) 8.3.3. Lưu trữ m c n i với Queue - Sử dụng danh sách liên kết đơn theo cơ chế vào trƣớc ra trƣớc, trỏ lối vào R chính là nút cuối danh sách, trỏ lối ra F chính là nút đầu danh sách. F INFO LINK Null R 8.3.4. Áp dụng Một số ví dụ về ứng dụng của ngăn xếp đƣợc xem xét trong phần này bao gồm: - Đảo ngƣợc xâu ký tự. - Tính giá trị một biểu thức dạng hậu tố (postfix). - Chuyển một biểu thức dạng trung tố sang hậu tố (infix to postfix). TÓM TẮT CHƢƠNG 8 Ngăn xếp là một dạng đặc biệt của danh sách mà việc bổ sung hay loại bỏ một
phần tử đều được thực hiện ở 1 đầu của danh sách. Ngăn xếp còn được gọi là kiểu dữ
liệu có nguyên tắc LIFO (Last In First Out - Vào sau ra trước). Ngăn xếp có thể được cài đặt bằng mảng hoặc danh sách liên kết. Các thao tác cơ bản trên ngăn xếp bao gồm: Khởi tạo ngăn xếp, kiểm tra ngăn xếp rỗng (đầy), thêm 1 phần tử vào ngăn xếp, loại bỏ 1 phần tử khỏi ngăn xếp. Hàng đợi là một cấu trúc dữ liệu gần giống với ngăn xếp, nhưng phần tử được
lấy ra khỏi hàng đợi không phải là phần tử mới nhất được đưa vào mà là phần tử đã
được lưu trong hàng đợi lâu nhất. Quy luật của hàng đợi là vào trước ra trước (FIFO
- First In First Out). Hàng đợi cũng có thể được cài đặt bằng mảng hoặc danh sách liên kết. Các thao
tác cơ bản cũng bao gồm: Khởi tạo hàng đợi, kiểm tra hàng đợi rỗng (đầy), thêm 1
phần tử vào hàng đợi, loại bỏ 1 phần tử khỏi hàng đợibản cũng bao gồm: Khởi tạo
hàng đợi, kiểm tra hàng đợi rỗng (đầy), thêm 1 phần tử vào hàng đợi, loại bỏ 1 phần
tử khỏi hàng đợi ===================== BÀI TẬP CHƢƠNG 8 1. Hãy nêu ví dụ thực tế mà ở đó có cơ chế hoạt động "vào sau ra trƣớc" 2. Theo anh(chị) có những cách cài đặt nào cho stack và queue, so sánh đặc điểm của các cách đó. 3. Hãy nêu các bƣớc thực hiện tính giá trị của biểu thức tiền tố và nhận xét những chỗ khác nhau so với cách tính giá trị biểu thức hậu tố. 4. Cho một stack, đƣợc cài đặt bởi một mảng một chiều S có n=6 phần tử và có con trỏ T là đỉnh. Ban đầu T=0. Hãy xác định kết quả xuất hiện và vẽ tình trạng thay đổi của S qua từng bƣớc của đoạn giải thuật sau: b1. A=2; B=5; b2. Call Push(S,T,A); Call Push(S,T,4); Call Push(S,T,B+2); Call Push(S,T,9); Call Push(S,T,A+B); b3. While (T!=0) { x=Pop(S,T); Printf(x); } b4. Return 5. Hãy biến đổi các biểu thức trung tố sau sang dạng tiền tố và hậu tố: a) (x+y)*z b) x-y-z*(A+B) c) A+B*CD/E-F d)((A+B)*D)(E-F) 6. Cho một queue đƣợc lƣu bởi một mảng một chiều Q có n=6 phần tử đƣợc tổ chức theo kiểu nối vòng. Tình trạng lúc này của Q : 1 2 3 4 5 6 London Berlin Rome Paris
F
R Hãy minh họa tình trạng của Q, nêu rõ giá trị tƣơng ứng của F và R sau mỗi lầ thực hiện các thao tác dƣới đây: a) "Madrid" đƣợc bổ sung vào queue b) Loại khỏi queue 2 phần tử c) "Oslo" đƣợc bổ sung vào queue d) Loại 3 phần tử khỏi queue 7. Cho một queue đƣợc cài đặt bởi vectơ Q có 12 phần tử, hoạt động theo cấu trúc vòng tròn. Hãy xác định số phần tử của queue nếu: a) F=4 và R=8 b) F=10 và R=3 c) F=5 và R=6. PHẦN KẾT LUẬN – KIẾN NGHỊ Ấn phẩm sẽ là tài liệu cần thiết cho việc giảng dạy và học tập chuyên ngành Đại học Công nghệ thông tin tại trƣờng Đại học Quảng Nam. Kiến nghị các đơn vị liên quan tạo điều kiện để nhóm tác giả thực hiện đề tài thuận lợi. PHẦN TÀI LIỆU THAM KHẢO [1] Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, nhà xuất bản Khoa học và Kỹ thuật, 1998. [2] Đinh Mạnh Tƣờng, Cấu trúc dữ liệu và thuật toán, nhà xuất bản Khoa học và Kỹ thuật, 2000. [3] Nguyễn Trung Trực, Cấu trúc dữ liệu, Khoa Công nghệ Thông tin trƣờng Đại học Bách khoa thành phố Hồ Chí Minh, 1997. [4] Lê Minh Trung, Bài tập Cấu trúc dữ liệu và giải thuật, nhà xuất bản Thống kê, Hà Nội, 2000. [5] Robert Sedgewick, biên dịch Trần Đan Thƣ, Vũ Mạnh Tƣờng, Dƣơng Vũ
Diệu Hà, Nguyễn Tiến Huy, Cẩm nang Thuật toán (tập1&2), nhà xuất bản Khoa học
và Kỹ thuật, 1994. [6] Trần Thị Tĩnh, Nguyễn Xuân My, Đặng Cao Tùng, Hồ Cẩm Hà, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học Sƣ phạm, 2005. - Khác: các tài liệu trên mạng14
15
16
17
x=x+1;
18
19
20
21
22
23
24
25
Bài toán mã đi tuần: Cho bàn cờ có kích thƣớc n x n (có n2 ô). Một quân mã
đƣợc đặt tại ô ban đầu có toạ độ x0, y0 và đƣợc phép dịch chuyển theo luật cờ thông
thƣờng. Bài toán đặt ra là từ ô ban đầu, tìm một chuỗi các nƣớc đi của quân mã, sao
cho quân mã này đi qua tất cả các ô của bàn cờ, mỗi ô đúng 1 lần.
Các nƣớc đi của quân mã
26
27
28
Tóm lại, khử đệ qui là việc thay thế một giải thuật đệ qui bằng một giải thuật
không đệ qui. Về nguyên tắc, bất cứ giải thuật đệ qui nào cũng có thể đƣợc thay bằng
giải thuật không đệ qui, có nhiều cách phân tích giải thuật đệ qui về giải thuạt không
đệ qui, tuy nhiên cũng không có phƣơng pháp tổng quát nào cho mọi giải thuật, nên
tránh sử dụng đệ qui nếu có một giải pháp khác cho bài toán. Mặc dù vậy, một
số bài toán tỏ ra rất phù hợp với phƣơng pháp đệ qui. Việc sử dụng đệ qui để
giải quyết các bài toán này hiệu quả và rất dễ hiểu.
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
5.2.2.2. Lưu trữ móc nối
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
