Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 1), Cấu Trúc Dữ Liệu & Giải Thuật

Đối với người học lập trình sẵn nói chung, cấu trúc dữ liệu và giải thuật là trong số những môn quan trọng và thường được dạy vào tầm khoảng năm 2 cùng năm 3 đại học. Cảm hứng của rất nhiều người nếu chưa tự tin là dễ bị nản ngay từ quy trình tiến độ đầu và dần dần sẽ trở ngại hơn để bắt nhịp. Đồng thời, học tốt kết cấu dữ liệu với giải thuật để giúp cho các dòng code của bản thân mình trở đề xuất tối ưu hơn.

Bạn đang xem: Giáo trình cấu trúc dữ liệu và giải thuật

Trong bài viết này, mình sẽ tổng hợp các kiến thức cơ bản cùng những kinh nghiệm của chính mình để giúp các bạn đi đúng phía và cảm giác sự độc đáo của môn học này. Tất nhiên xung quanh ta vẫn có khá nhiều cao thủ, việc trình làng các kỹ năng khó sẽ khiến mọi bạn bị ngợp đề nghị trong phạm vi nội dung bài viết này, mình sẽ giới thiệu các vụ việc cơ bạn dạng (ít nhất là trong các bài bình chọn trên trường). Hãy thuộc tham khảo nội dung bài viết dưới đây:

Chuẩn bị đầy đủ gì nhằm học thuật toán?

Đầu tiên, nhằm học được cấu trúc dữ liệu và giải thuật (Từ giờ mang đến cuối bài viết mình sẽ call tắt là thuật toán), các bạn cần phải có kỹ năng tự học tập cao. Phải có chức năng tìm tìm tốt. Phần lớn mọi vật dụng cơ phiên bản đều bao gồm trên google, trong khuôn khổ nội dung bài viết này bản thân sẽ gửi ra những vấn đề quan lại trọng, để các bạn follow theo từ khoá đó, tìm kiếm cho khách hàng một nền tảng vững vàng chắc.

Tiếp theo, các bạn cần chọn cho doanh nghiệp một ngôn ngữ lập trình. Theo mình thì C/C++ là ngôn từ nên được sử dụng lúc học thuật toán vì:

Các kiểu dữ liệu trong ngữ điệu C/C++ được quan niệm rõ ràng, gồm kiểu truyền tham chiếu cùng tham trị tương đối hay.Tốc độ thực thi nhanh.Có các sách, tài liệu tìm hiểu thêm trên internet về kết cấu dữ liệu và lời giải được viết bằng C/C++.

Tuy nhiên, nếu muốn hoặc tất cả nền tảng những ngôn ngữ khác (java, python,...) thì mọi bạn cũng rất có thể sử dụng để học được vì chưng theo bí quyết sau:

Cấu trúc tài liệu + giải thuật = Chương trình

Việc viết một chương trình, giải một việc được phối hợp bởi 2 yếu hèn tố, lựa lựa chọn một cấu trúc dữ liệu phù hợp, tiếp đến tìm ra phương hướng phối kết hợp mọi thứ bằng giải thuật để rất có thể giải được bài toán. Bởi vì đó bạn có thể lựa chọn ngôn ngữ yêu thích cùng bắt đầu.

Các vấn đề cần quan lại tâm

Trong phần này mình sẽ nói tới 7 vấn đề sau:

1. Độ phức tạp thuật toán (big O)

2. Thu xếp và tìm kiếm kiếm nhị phân

3. Các phương thức sinh

4. Đệ quy, quay lui

5. Kết cấu dữ liệu stack, queue, dequeue

6. Quy hướng động

7. Đồ thị.

1. Độ phức tạp thuật toán (big O)

Khái niệm độ phức tạp thuật toán rất có thể hiểu đơn giản và dễ dàng là độ nhanh hay chậm trễ của thuật toán. Chữ O là cam kết hiệu được sử dụng cho độ phức hợp thuật toán. Những loại độ phức tạp thuật toán cơ bản có thể nói tới là:

Trong đó, n là thể hiện kích thước đầu vào.

Lưu ý rằng nếu chúng ta sử dụng 2 vòng lặp cùng cấp cho thì kích thước sẽ là 2*n, nhưng độ tinh vi thuật toán biểu diễn vẫn chính là O(n) vì mình chỉ lấy dao động thôi.

Và nếu như bạn của chúng ta nói là 2 vòng lặp lồng nhau thì độ phức tạp sẽ là O(n^2) thì chúng ta đôi khi đề xuất xem xét kỹ rộng thuật toán. Như lấy một ví dụ sau:

int i = 0;int n = 1000;while (i giả dụ không chú ý thì rất có thể sẽ nhầm hàm này là O(N^2), nhưng thực tế độ tinh vi của nó là O(n). Bởi vì nếu như i

2. Sắp xếp và search kiếm nhị phân

a. Sắp xếp

Để có thể hiểu rõ những thuật toán chạy như nào, chúng ta nên tìm những source code bên trên mạng về và chạy thử, tiếp đến tự ngẫm xem các hàm của chính nó chạy như nào, các phép toán có tính năng gì. Trong số thuật toán sắp xếp thì bản thân thấy có tương đối nhiều thuật toán như:

Bubble sort
Selection sort
Insertion sort
Quick sort
Heap sort...

Ngoài ra còn không hề ít thuật toán bố trí khác nữa, tùy vào đk môn học trên ngôi trường yêu cầu gì thì mình học tập theo. Còn theo khiếp nghiệm của bản thân mình thì để triển khai bài tập với code thuật toán thì học bubble sort (O(n)) cùng quick sort(~O(nlog(n))) thôi là đủ code được cả nghìn bài bác rồi. Đa số đều thực hiện quick sort giỏi dùng luôn luôn hàm sort trong thư viện( trong C++ là hàm sort trong thư viện algorithm có độ phức hợp ~ O(nlog(n))).

Còn việc reviews nhiều thuật toán sort là tùy từng điều kiện ví dụ thì từng thuật toán gồm những điểm mạnh và điểm yếu riêng, vận dụng trong thực tế. Lấy một ví dụ nhưinsertion sorthay thu xếp chènthường được áp dụng trong bảng xếp hạng,đâylà thuật toán sắp xếp xử lý chèn bộ phận đang xét vào vị trí phù hợp của hàng số đã thu xếp phía trước sao để cho dãy số vẫn luôn là dãy sắp xếp có thiết bị tự.

Xem thêm: #1 báo giá thay màn hình samsung j7 prime giá bao nhiêu, thay màn hình samsung j7 prime

b. Tra cứu kiếm nhị phân

Ý tưởng thiết yếu của tra cứu kiếm có thể biểu diễn dễ dàng bằng một vấn đề như sau:

Có n các bạn được xếp thành một mặt hàng theo đồ vật tự độ cao tăng dần. Thầy giáo nhìn vào danh sách học viên mà không tồn tại tên, chỉ gồm chiều cao, vì thế cần tìm các bạn có chiều cao là X trong hàng.

Bình thường xuyên thì giải pháp làm dễ dàng và đơn giản nhất là duyệt từ đầu hàng đến cuối hàng một cách lần lượt, khi đó chắc chắn sẽ tìm được bạn có chiều cao là X đó (độ phức tạp thuật toán sẽ là O(n)). Có một cách nhanh hơn để giải bài toán này, đó là ta sẽ nhìn vào người ở giữa dãy, nếu bạn đó có chiều cao bằng X thì ta sẽ tìm được luôn, còn nếu không thì ta sẽ biết chắc chắn người đó sẽ đứng ở nửa nào trong 2 nửa còn lại của hàng, qua đó lặp lại phương pháp bên trên đến lúc tìm ra bạn đó, phía trên chính là ý tưởng chính của thuật toán tìm kiếm nhị phân với độ phức tạp chỉ còn O(nlog(n)).

3. Các phương pháp sinh

Có thể bạn không biết, gần như tất cả các bài toán đều có thể giải bằng cách duyệt trâu từng trường hợp. Vày đó các phương pháp sinh là ko thể thiếu lúc học thuật toán. Có 4 phương pháp sinh mà các bạn nhất định phải học:

Sinh nhị phân
Sinh hoán vịSinh tổ hợp
Sinh chỉnh hợp

Các bạn có thể tìm hiểu các thuật toán bên trên và submit trong trang sau nhé:

https://www.spoj.com/PTIT/problems/basic/

4. Đệ quy, tảo lui

Nói đối chọi giản thì đệ quy là hàm gọi lại chính nó, biểu diễn đối tượng được định nghĩa quy nạp theo các đối tượng bé đồng dạng với nó. Dưới đây là một số ví dụ của hàm sử dụng vòng lặp bình thường và hàm đệ quy:

int giaithua(int n) {int res=1;for (int i = 1; i Bây giờ hãy cùng mình xem qua một số cách viết hàm tính a^b ( với a khác 0). Tất nhiên với các bài toán giới hạn lớn thì a^b sẽ rất lớn, bởi vì đó mình sẽ lấy phần dư đến mod nhé.

// dpt O(n)long long cal_pow(int a, int b, int mod) long long res=1;for (int i = 1; i > 1, mod);Qua đó các bạn có thể thấy các hàm đệ quy rất thú vị. Các phương pháp sinh ở trên, ngoài cách code chay sinh từng cấu hình thì cũng có thể sử dụng đệ quy để viết một cách gọn gàng hơn. Thuật toán xoay lui cũng dựa trên tư tưởng của hàm đệ quy như trên, suy cho cùng các thuật toán sinh được dùng để duyệt hết các cấu hình có thể, trong một số bài toán thì có thể sử dụng nhánh cận, cài cắm các đoạn xử lý loại bỏ các trường hợp không cần thiết để chương trình được tối ưu hơn.

Tạm kết

Mình tạm dừng phần 1 ở đây, vào bài viết sau mình sẽ nói tiếp các vấn đề cần nhiệt tình khác, các nguồn tài liệu và website mình giỏi dùng trong quá trình học. Các bạn đón xem nhé :))

Đh Khoa Học tự nhiên và thoải mái Hcm - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến - triết lý - bài tập, thực hành thực tế





homework 2_cài đặt giải mã sắp xếp selection sort, heap sort để thu xếp một mảng số nguyên theo_thứ tự tăng dần.pdf

Giới thiệu, nội dung môn học tập

Môn học tập nhằm cung cấp cho sinh viên kỹ năng sử dụng các cấu tạo dữ liệu nền tảng. Môn học cũng trả lời sinh viên hiểu, đối chiếu và review được các giải thuật thao tác làm việc với các kết cấu dữ liệu đó.Ôn lại về lập trình, những kiểu tài liệu trong C/C++, đặc biệt quan trọng là cấu tạo và con trỏ.Giới thiệu về độ phức tạp tính toán và đệ qui.Các cấu trúc dữ liệu và sự phân tích chúng: danh sách; ck và hàng; cây, cây nhị phân, cây nhị phân tìm kiếm kiếm, AVL cùng đa phân; heap; giải thuật sắp xếp; bảng băm; và đồ thị.

kết quả cần đã có được

Phân tích giải mã L.O.1.1 – Định nghĩa được các khái niệm độ phức hợp và độ phức hợp trong các trường vừa lòng “tốt nhất”, “xấu nhất”, cùng “trung bình”.L.O.1.2 – đối chiếu được những giải thuật và áp dụng được ký kết hiệu “Big O” để ghi ra độ tinh vi của lời giải cấu thành trường đoản cú các cấu trúc điều khiển: tuần tự, rẽ nhánh cùng lặp.L.O.1.3 – Liệt kê được, đến được ví dụ và đối chiếu được các lớp độ phức tạp, như, hằng số, log, con đường tính, etc.L.O.1.4 – dấn thức được sự cân bằng giữa bộ lưu trữ và thời hạn trong giải thuật.L.O.1.5 – biểu thị được các chiến lược xây đắp giải thuật và giải quyết và xử lý bài toán.Sử dụng cấu trúc dữ liệu danh sách, ck và hàng L.O.2.1 – vạc họa được bởi hình ảnh cho: (a) danh sách hiện thực bởi mảng với bằng liên kết (con trỏ); (b) cho chồng; với (c) mang đến hàng ngóng và hàng hóng vòng (mức logic).L.O.2.2 – Viết được bằng mã mang mô tả kết cấu lưu trữ cho: (a) danh sách hiện thực bằng mảng và bởi liên kết; (b) cho chồng; và (c) mang đến hàng đợi và hàng chờ vòng (mức logic).L.O.2.3 – Liệt kê được các phương thức cần thiết cho từng cấu trúc như danh sách, ck và sản phẩm đợi; cũng như mô tả được chúng bằng mã trả (mức logic).L.O.2.4 – hiện thực được các kết cấu danh sách, ông chồng và mặt hàng đợi bằng C/C++ (mức physics)L.O.2.5 – áp dụng được danh sách, chồng, với hàng để xử lý bài toán thực, cũng như suy nghĩ chọn lựa kiểu hiện thực buổi tối ưu.L.O.2.6 – so với được và làm cho thí nghiệm review các cách thức đã hổ trợ đến các cấu trúc danh sánh, chồng, và hàng.Sử dụng kết cấu cây L.O.3.1 – phát họa được bằng hình ảnh cho những cây tiêu biểu, như, cây nhị phân, cây nhị phân đầy đủ, cây nhị phân cân nặng bằng, cây AVL, cây đa phân, v.v. (mức logic).L.O.3.2 – Viết được bằng mã đưa mô tả cấu trúc lưu trữ cho các loại cây (mức logic)L.O.3.3 – Liệt kê được các phương thức cần thiết cho mang lại các kết cấu cây; cũng giống như mô tả được chúng bằng mã trả (mức logic).L.O.3.4 – chỉ ra được và mang đến ví dụ minh họa về tầm đặc biệt của tính cân đối trong cây.L.O.3.5 – chỉ ra rằng được với vẽ hình minh họa về toàn bộ các trường mất cân đối trong cây AVL cùng cây B, tương tự như thực hiện từng bước một để tái thăng bằng chúng trên hình vẽ (mức logic).L.O.3.6 – thực tại được các kết cấu cây nhị phân và cây AVL bởi C/C++L.O.3.7 – áp dụng được cây nhị phân cùng cây AVL để giải quyết bài toán thực, đặc biệt là liên quan mang đến tìm kiếm.L.O.3.8 – đối chiếu được và làm thực nghiệm nhận xét được những phương thức đang hổ trợ đến các kết cấu cây nhị phân với cây AVL.Sử dụng Heap L.O.4.1 – đã cho thấy được những vận dụng cần mang đến Heap L.O.4.2 – tổng quát được bằng hình hình ảnh cho cấu trúc Heap và nêu ra sự tương quan đến tàng trữ ở dạng mảng.L.O.4.3 – Liệt kê được các phương thức cần thiết cho cho cấu trúc heap; cũng giống như mô tả được chúng bằng mã đưa (mức logic).L.O.4.4 – phác họa được bởi hình hình ảnh các cách tiến hành để bảo đảm tính hóa học của cấu trúc Heap khi gửi vào hay lấy ra bộ phận trong heap (mức logic).L.O.4.5 – hiện nay được cấu trúc heap bởi C/C++.L.O.4.6 – đối chiếu được và làm thực nghiệm đánh giá được những phương thức đã hổ trợ cho cấu tạo Heap.Sử dụng bảng băm L.O.5.1 – Vẽ được hình minh họa một bảng băm cùng với định nghĩa về khóa, đụng độ và giải quyết đụng độ.L.O.5.2 – biểu lộ được bởi mã giả và đến ví dụ minh họa cho các hàm băm cơ bản.L.O.5.3 – trình bày được bởi mã trả và cho ví dụ minh họa cho những phương thức xử lý đụng độ.L.O.5.4 – hiện thực được kết cấu bảng băm bởi C/C++.L.O.5.5 – so với được và làm cho thực nghiệm reviews được những phương thức đã hổ trợ cho kết cấu bảng băm.Phát triển các giải thuật chuẩn bị xếp L.O.6.1 – Minh họa được bằng hình vẽ từng bước buổi giao lưu của các lời giải sắp xếp.L.O.6.2 – diễn tả được bằng mã giả cho các giải thuật chuẩn bị xếp. L.O.6.3 – hiện thực được những giải thuật bố trí bằng C/C++ .L.O.6.4 – so sánh được và có tác dụng thực nghiệm nhận xét các giải thuật sắp xếp.L.O.6.5 – thực hiện được lời giải sắp xếp trong câu hỏi thực.Hiểu biết cơ bạn dạng về đồ thị L.O.7.1 – vạc họa được bằng hình ảnh cho những khái niệm như vật dụng thị liên thông với không liên thông, thiết bị thị được bố trí theo hướng và không hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa với mô tả kết cấu lưu trữ mang đến đồ thị ở những dạng ma trận kề và list kề bằng mã giả (mức logic).L.O.7.3 – Liệt kê được những phương thức quan trọng cho đến các cấu trúc đồ thị; cũng giống như mô tả được chúng bằng mã giả (mức logic).L.O.7.4 – Minh họa được bởi hình hình ảnh các phương pháp duyệt vật dụng thị cơ phiên bản (depth first & bread-first).L.O.7.5 – hiện nay được kết cấu lưu trữ đồ gia dụng thì bằng C/C++.L.O.7.6 – hiện tại được các cách thức duyệt nói trên bởi C/C++ và sử dụng chúng giải quyết bài toán thực.L.O.7.7 – Minh họa bởi hình vẽ từng bước hoạt động vui chơi của các giải mã tìm con đường ngắn nhất bởi Dijktra và giải mã tìm cây phủ tối tiểu bằng giải thuật Prim.Sử dụng đệ quy L.O.8.1 – thể hiện được những thành phần cơ bản của một giải thuật đệ quy.L.O.8.2 – Vẽ được cây mô tả các lần gọi hàm và giá trị của những tham số được truyền vào các hàm đó.L.O.8.3 – mang lại được lấy một ví dụ về một hàm điện thoại tư vấn đệ quy viết bằng C/C++.L.O.8.4 – cải cách và phát triển được giải thuật đệ quy cho những phương thức cần thiết của những cấu trúc: danh sách, cây, heap, tìm kiếm trên cây với tìm kiếm nhị phân, cùng đồ thị.L.O.8.5 – làm cho được thí nghiệm để so sánh cách tiếp cận đệ quy và cách lặp.L.O.8.6 – mang đến được lấy ví dụ minh họa sự liên quan giữa Backtracking và đệ quy.

Tài liệu xem thêm

Sách, Giáo trình chính:<1>. “Data Structures: a Pseudocode Approach with C++”, R.F.Gilberg and B.A. Forouzan, Thomson Learning Inc., 2001.Sách tham khảo:<1> “Data Structures và Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005.<2> “C/C++: How khổng lồ Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012.<3> Internet.<4> Minh họa kết cấu dữ liệu và giải thuật