<p>Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!</p>
<p>Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.</p>
<p>Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.</p>
<p>Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.</p>
<p>Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.</p>
<p>H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.</p>

Cấu trúc dữ liệu và Giải thuật

<p dir="ltr" style="text-align: justify;">Trong c&aacute;c chủ đề trước, ta đ&atilde; t&igrave;m hiểu sơ bộ về mối tương quan giữa cấu tr&uacute;c dữ liệu v&agrave; giải thuật. Trong c&aacute;c chương ph&iacute;a sau n&agrave;y, ta sẽ đi chi tiết v&agrave;o c&aacute;c nội dung li&ecirc;n quan đến từng dạng cấu tr&uacute;c dữ liệu v&agrave; giải thuật từ cơ bản đến n&acirc;ng cao để l&agrave;m quen v&agrave; vận dụng ch&uacute;ng để giải quyết c&aacute;c b&agrave;i to&aacute;n trong thực tế. Trong Chương n&agrave;y, ta sẽ bắt đầu với một kiểu cấu tr&uacute;c dữ liệu kh&aacute; phổ biến v&agrave; được sử dụng thường xuy&ecirc;n nhất trong lập tr&igrave;nh đ&oacute; l&agrave; c&aacute;c mảng v&agrave; chuỗi k&yacute; tự.</p>
<p dir="ltr" style="text-align: justify;">Khi x&eacute;t trong thuật to&aacute;n, mảng một chiều (1D) v&agrave; chuỗi k&yacute; tự kh&aacute; giống nhau: cả hai đều biểu thị một nh&oacute;m phần tử c&oacute; thứ tự. Hầu hết c&aacute;c b&agrave;i to&aacute;n về thuật to&aacute;n sẽ c&oacute; mảng hoặc chuỗi l&agrave; một phần của dữ liệu đầu v&agrave;o, v&igrave; vậy, bạn cần l&agrave;m quen với c&aacute;ch xử l&yacute; v&agrave; c&aacute;c thao t&aacute;c cơ bản đối với hai kiểu dữ liệu n&agrave;y.</p>
<h2 dir="ltr" style="text-align: justify;">Mảng</h2>
<p style="text-align: justify;">Mảng l&agrave; một v&ugrave;ng chứa c&oacute; thể chứa một số phần tử cố định v&agrave; những phần tử n&agrave;y phải c&ugrave;ng kiểu dữ liệu. Hầu hết c&aacute;c cấu tr&uacute;c dữ liệu sử dụng mảng để triển khai c&aacute;c thuật to&aacute;n. Hai yếu tố cốt l&otilde;i để thực hiện c&aacute;c thao t&aacute;c tr&ecirc;n mảng đ&oacute; l&agrave;:</p>
<ul style="text-align: justify;">
<li><strong>Phần tử:</strong> Mỗi đơn vị dữ liệu được lưu trữ trong một mảng được gọi l&agrave; một phần tử.</li>
<li><strong>Chỉ số: </strong>Mỗi vị tr&iacute; của một phần tử trong một mảng c&oacute; một chỉ số, được sử dụng để x&aacute;c định phần tử đ&oacute;.</li>
</ul>
<p style="text-align: justify;">Mảng c&oacute; thể được khai b&aacute;o theo nhiều c&aacute;ch kh&aacute;c nhau trong c&aacute;c ng&ocirc;n ngữ lập tr&igrave;nh kh&aacute;c nhau. Chẳng hạn dưới đ&acirc;y l&agrave; c&uacute; ph&aacute;p khai b&aacute;o mảng của một số ng&ocirc;n ngữ lập tr&igrave;nh phổ biến:</p>
<div class="code-editor__wrapped code-editor__read__wrapped" data-id="c0e78e9b-1216-4f6e-8a06-518a05cd49f5">
<div class="code-editor__read__tabbed"><input id="80c6d6e8-8cd0-4210-bddd-e49f88a25c32" checked="checked" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="d335c4b3-d5f8-442a-9d0c-b1be46ae3774" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="879e334f-a392-4555-bbe9-73b33536f90c" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="e8268245-9d1c-45cd-a23c-a11947baaf0a" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="aeb29037-5b53-4e27-b88b-ac448c9551bf" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="852d6739-c8ab-4cd5-ac15-8d20f41310c7" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="0b17f425-2f7f-43e1-8961-dd2553cd3d48" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" /><input id="0cda4bf4-6068-4f46-8f82-af02f3657c3a" name="d891381a-ce4a-4b89-af8d-b019cfd3945a" type="radio" />
<ul class="code-editor__read__tabs">
<li class="code-editor__read__tab"><label for="80c6d6e8-8cd0-4210-bddd-e49f88a25c32">C</label></li>
<li class="code-editor__read__tab"><label for="d335c4b3-d5f8-442a-9d0c-b1be46ae3774">C++</label></li>
<li class="code-editor__read__tab"><label for="879e334f-a392-4555-bbe9-73b33536f90c">Java</label></li>
<li class="code-editor__read__tab"><label for="e8268245-9d1c-45cd-a23c-a11947baaf0a">Python 3</label></li>
<li class="code-editor__read__tab"><label for="aeb29037-5b53-4e27-b88b-ac448c9551bf">HTML</label></li>
<li class="code-editor__read__tab"><label for="852d6739-c8ab-4cd5-ac15-8d20f41310c7">Python ML</label></li>
<li class="code-editor__read__tab"><label for="0b17f425-2f7f-43e1-8961-dd2553cd3d48">javascript</label></li>
<li class="code-editor__read__tab"><label for="0cda4bf4-6068-4f46-8f82-af02f3657c3a">C#</label></li>
</ul>
<pre class="language-c" data-content="int%20myNumbers%5B%5D%20%3D%20%7B25%2C%2050%2C%2075%2C%20100%7D%3B" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-type="read-code" data-name="80c6d6e8-8cd0-4210-bddd-e49f88a25c32" data-main-file="main.c"><code> int myNumbers[] = {32, 12, 31, 44, 56};</code></pre>
<pre class="language-cpp" data-content="int%20myNum%5B5%5D%20%3D%20%7B10%2C%2020%2C%2030%2C40%2C50%7D%3B" data-language="cpp" data-ace-language="c_cpp" data-name-language="C++" data-type="read-code" data-name="d335c4b3-d5f8-442a-9d0c-b1be46ae3774" data-main-file="main.cpp"><code> int myNum[5] = {32, 12, 31, 44, 56};</code></pre>
<pre class="language-java" data-content="int%5B%5D%20myNum%20%3D%20%7B10%2C%2020%2C%2030%2C%2040%7D%3B" data-language="java" data-ace-language="java" data-name-language="Java" data-type="read-code" data-name="879e334f-a392-4555-bbe9-73b33536f90c" data-main-file="Main.java"><code>int[] myNum = {32, 12, 31, 44, 56};</code></pre>
<pre class="language-python" data-content="mylist%20%3D%20%5B10%2C20%2C30%2C40%2C50%5D" data-language="python" data-ace-language="python" data-name-language="Python 3" data-type="read-code" data-name="e8268245-9d1c-45cd-a23c-a11947baaf0a" data-main-file="main.python"><code> mylist = [32, 12, 31, 44, 56] </code></pre>
<pre class="language-html" data-content="" data-language="html" data-ace-language="html" data-name-language="HTML" data-type="read-code" data-name="aeb29037-5b53-4e27-b88b-ac448c9551bf" data-main-file="index.html"><code>
</code></pre>
<pre class="language-python-ml" data-content="" data-language="python-ml" data-ace-language="python" data-name-language="Python ML" data-type="read-code" data-name="852d6739-c8ab-4cd5-ac15-8d20f41310c7" data-main-file="main.python"><code>
</code></pre>
<pre class="language-javascript" data-content="let%20fruits%20%3D%20%5B%22Apple%22%2C%20%22Orange%22%2C%20%22Pear%22%5D%3B" data-language="javascript" data-ace-language="javascript" data-name-language="javascript" data-type="read-code" data-name="0b17f425-2f7f-43e1-8961-dd2553cd3d48" data-main-file="main.js"><code>let fruits = [32, 12, 31, 44, 56];</code></pre>
<pre class="language-csharp" data-content="int%5B%5D%20myNum%20%3D%20%7B10%2C%2020%2C%2030%2C%2040%2C50%7D%3B" data-language="csharp" data-ace-language="csharp" data-name-language="C#" data-type="read-code" data-name="0cda4bf4-6068-4f46-8f82-af02f3657c3a" data-main-file="Program.cs"><code>int[] myNum = {10, 20, 30, 40,50};</code></pre>
</div>
</div>
<p style="text-align: justify;">&nbsp;H&igrave;nh vẽ dưới đ&acirc;y m&ocirc; phỏng dạng của mảng n&agrave;y:</p>
<p><img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/f3143376-10df-445a-8f70-48cdb0c5577b" alt="a2" /></p>
<p style="text-align: justify;">Theo h&igrave;nh minh họa ở tr&ecirc;n:</p>
<ul style="text-align: justify;">
<li style="text-align: justify;">Ta c&oacute; chỉ số của mảng bắt đầu bằng gi&aacute; trị <code>0</code>. Do đ&oacute;, nếu ta c&oacute; 10 phần tử th&igrave; chỉ số của phần tử cuối c&ugrave;ng trong mảng l&agrave; <code>9</code>. Hầu hết c&aacute;c ng&ocirc;n ngữ đều quy ước chỉ số của mảng bắt đầu từ <code>0</code>.</li>
<li>Độ d&agrave;i của mảng l&agrave; <code>5</code>, c&oacute; nghĩa l&agrave; n&oacute; c&oacute; thể lưu trữ 5 phần tử.</li>
<li>Mỗi phần tử c&oacute; thể được truy cập th&ocirc;ng qua chỉ số. V&iacute; dụ, ta c&oacute; thể t&igrave;m một phần tử ở chỉ số <code>3</code> l&agrave; <code>44</code>.</li>
</ul>
<p dir="ltr" style="text-align: justify;">[___WARNING_Lưu &yacute; rằng: "Mảng" c&oacute; thể c&oacute; &yacute; nghĩa kh&aacute;c nhau giữa c&aacute;c ng&ocirc;n ngữ._WARNING___]</p>
<p dir="ltr" style="text-align: justify;">V&iacute; dụ: Python sử dụng "danh s&aacute;ch" thay v&igrave; mảng để cho dễ d&agrave;ng hơn. C&aacute;ch khởi tạo cũng kh&aacute; đơn giản:&nbsp;<code>arr = []</code>&nbsp;v&agrave; bạn kh&ocirc;ng cần phải lo lắng về kiểu dữ liệu lưu trữ trong danh s&aacute;ch hoặc k&iacute;ch thước của danh s&aacute;ch. Những ng&ocirc;n ngữ kh&aacute;c như C++ y&ecirc;u cầu bạn phải chỉ định k&iacute;ch thước v&agrave; kiểu dữ liệu của mảng trong qu&aacute; tr&igrave;nh khởi tạo, nhưng cũng c&oacute; hỗ trợ kiểu dữ liệu danh s&aacute;ch (như&nbsp;<code>std::vector</code>&nbsp;trong C++). Về bản chất mảng v&agrave; danh s&aacute;ch l&agrave; hai kiểu dữ liệu kh&aacute;c nhau. Tuy nhi&ecirc;n, trong nội dung của kh&oacute;a học n&agrave;y, ta coi tất cả c&aacute;c kiểu dữ liệu n&agrave;y tương đồng bởi n&oacute; c&ugrave;ng l&agrave; kiểu dữ liệu của một nh&oacute;m c&aacute;c phần tử v&agrave; c&oacute; thứ tự.</p>
<p dir="ltr" style="text-align: justify;">Về mặt kỹ thuật, mảng kh&ocirc;ng thể thay đổi k&iacute;ch thước. Tuy nhi&ecirc;n, mảng động hoặc danh s&aacute;ch th&igrave; lại c&oacute; thể. Trong c&aacute;c b&agrave;i to&aacute;n về thuật to&aacute;n, th&ocirc;ng thường khi nhắc đến mảng th&igrave; tức l&agrave; ta đang &aacute;m chỉ đến mảng động. Trong to&agrave;n bộ kh&oacute;a học n&agrave;y, ta sẽ n&oacute;i về mảng động/danh s&aacute;ch nhưng để thống nhất ta sẽ chỉ sử dụng từ "mảng".</p>
<p dir="ltr" style="text-align: justify;">[___NOTE_N&oacute;i t&oacute;m lại, kh&aacute;i niệm chung nhất th&igrave; mảng l&agrave; một tập phần tử c&oacute; thứ tự v&agrave; được đ&aacute;nh chỉ số. Ta c&oacute; thể thao t&aacute;c với mảng th&ocirc;ng qua c&aacute;c chỉ số của n&oacute;._NOTE___]</p>
<h2 dir="ltr" style="text-align: justify;">Chuỗi k&yacute; tự</h2>
<p dir="ltr" style="text-align: justify;">Tương tự như mảng, chuỗi k&yacute; tự cũng c&oacute; c&aacute;c c&aacute;ch triển khai kh&aacute;c nhau trong c&aacute;c ng&ocirc;n ngữ lập tr&igrave;nh. Trong Python v&agrave; Java, chuỗi l&agrave; bất biến, tức l&agrave; ta kh&ocirc;ng thể sửa đổi c&aacute;c phần tử trong chuỗi m&agrave; chỉ c&oacute; thể tạo hoặc g&aacute;n lại chuỗi mới. Ngược lại, trong C++, chuỗi lại c&oacute; thể thay đổi được. Bạn n&ecirc;n nắm được sự kh&aacute;c biệt n&agrave;y để c&oacute; thể &aacute;p dụng một c&aacute;ch ch&iacute;nh x&aacute;c khi triển khai lập tr&igrave;nh. Tuy nhi&ecirc;n, trong khu&ocirc;n khổ kh&oacute;a học n&agrave;y, ta kh&ocirc;ng c&oacute; thời gian để xem qua tất cả c&aacute;c c&aacute;ch triển khai kh&aacute;c nhau cho từng ng&ocirc;n ngữ, v&igrave; vậy bạn h&atilde;y tự nghi&ecirc;n cứu c&aacute;ch triển khai cho ng&ocirc;n ngữ m&agrave; m&igrave;nh định sử dụng nếu chưa nắm r&otilde;.</p>
<p dir="ltr" style="text-align: justify;">[___NOTE_</p>
<ul>
<li dir="ltr" style="text-align: justify;">Dữ liệu c&oacute; thể thay đổi được (Mutable): Bạn c&oacute; thể dễ d&agrave;ng thay đổi gi&aacute; trị cho n&oacute;.</li>
<li dir="ltr" style="text-align: justify;">Dữ liệu bất biến (Immutable): Nếu bạn muốn thay đổi một thứ g&igrave; đ&oacute; thuộc dạng dữ liệu bất biến, bạn sẽ cần phải khởi tạo lại to&agrave;n bộ gi&aacute; trị của n&oacute;.</li>
</ul>
<p dir="ltr" style="text-align: justify;">_NOTE___]</p>
<p dir="ltr" style="text-align: justify;">Tại sao ta n&ecirc;n quan t&acirc;m đến việc một đối tượng l&agrave; c&oacute; thể thay đổi hay bất biến? Nếu bạn c&oacute; một mảng <code>arr = ["a", "b", "c"]</code>&nbsp;v&agrave; một chuỗi bất biến&nbsp;<code>s = "abc"</code>, để c&oacute; chuỗi&nbsp;<code>"abd"</code>, bạn c&oacute; thể dễ d&agrave;ng thực hiện&nbsp;<code>arr[2] = "d"</code>, nhưng bạn kh&ocirc;ng thể thực hiện&nbsp;<code>s[2] = "d"</code>.&nbsp;</p>
<p dir="ltr" style="text-align: justify;">[___NOTE_Ta thường x&eacute;t đến c&aacute;c chỉ số bắt đầu từ <code>0</code>, tức l&agrave; mảng <code>arr</code> c&oacute; 3 phần tử thứ nhất, thứ hai v&agrave; thứ ba với chỉ số tương ứng l&agrave;: <code>0</code>, <code>1</code>, <code>2</code>. Tức l&agrave; <code>arr[2]=&rdquo;c&rdquo;</code>._NOTE___]</p>
<p dir="ltr" style="text-align: justify;">Như vậy, nếu bạn muốn c&oacute; chuỗi&nbsp;<code>s = "abd"</code>, bạn cần phải tạo lại to&agrave;n bộ chuỗi từ đầu. Với một chuỗi nhỏ như vậy, đ&oacute; kh&ocirc;ng phải l&agrave; vấn đề lớn, nhưng đ&ocirc;i khi bạn cần phải xử l&yacute; c&aacute;c chuỗi c&oacute; $100000$ k&yacute; tự, v&igrave; vậy việc tạo chuỗi mới chỉ để sửa đổi một k&yacute; tự l&agrave; rất tốn k&eacute;m ($O(n)$, trong đ&oacute; $n$ l&agrave; k&iacute;ch thước của chuỗi).</p>
<p dir="ltr" style="text-align: justify;">Như đ&atilde; đề cập trước đ&oacute;, phần lớn c&aacute;c b&agrave;i to&aacute;n về thuật to&aacute;n sẽ li&ecirc;n quan đến mảng hoặc chuỗi. Ch&uacute;ng l&agrave; những cấu tr&uacute;c dữ liệu cực kỳ linh hoạt v&agrave; kh&ocirc;ng thể liệt k&ecirc; hết tất cả c&aacute;c kỹ thuật giải quyết vấn đề li&ecirc;n quan ngay ở b&agrave;i n&agrave;y. Trong c&aacute;c b&agrave;i tiếp theo, ta sẽ đi cụ thể chi tiết về những kỹ thuật phổ biến nhất để l&agrave;m việc với hai kiểu dữ liệu n&agrave;y. Nhưng trước khi l&agrave;m điều đ&oacute;, ta h&atilde;y xem qua một số thao t&aacute;c nguy&ecirc;n thủy cơ sở đối với mảng v&agrave; chuỗi.</p>

Mảng và chuỗi ký tự