Like and subscribed để đón đọc nhé
Series: Cấu trúc dữ liệu và thuật toán dành cho các bạn fresher
Phong cách ngôn tình
Chuyện kể về tình yêu của một em fresher IT dành cho anh Technical Leader của mình. Nhưng anh chỉ coi em ấy như một người em gái…
Mưa rơi nặng hạt, từng hạt mưa rơi lộp bộp tạo nên những âm thanh thật vui tai. Tôi nhoẻn miệng cười đưa tay đón từng hạt mưa. 4 năm đại học trôi đi thật nhanh để lại nhiều kỉ niệm trong tâm hồn của cô sinh viên thơ ngây, trong trắng. Hôm nay là ngày đầu tiên tôi đi làm ở Fsoft, thật hồi hộp như ngày đầu thi đại học
Chào em, anh là Nam, technical leader của đơn vị Fsoft ABC, chào mừng em đã gia nhập công ty.
Tôi giật mình, trước mặt tôi là một chàng trai với cặp kính cận, và đẹp trai như một thiên thần. Anh cười, nụ cười anh bừng sáng cả một bầu trời mưa.
Tôi chỉ biết lí nhí
Chào anh ạ, em tên Ngọc Lan, vừa tốt nghiệp CNTT đại học FPT, em chưa có kinh nghiệm gì cả. Mong anh chỉ bảo thêm ạ
Tên em thật đẹp, nó làm anh nghĩ đến tên một loại hoa có mùi thơm ngất ngây
Trời giọng anh ấm quá, Tim tôi đập thình thịch. Tôi ôm lồng ngực sợ anh nghe thấy tiếng trái tim mình
Anh chợt nhìn tôi, mỉm cười
Hồi sinh viên, em đã được học nhiều về Cấu trúc dữ liệu và giải thuật chứ
Dạ có ạ
Em có thể trình bày cho anh về Lý thuyết đồ thị, cấu trúc dữ liệu cây được không??
Tôi bẽn lẽn
Dạ hồi sinh viên em học chỉ để lấy điểm, nên thì qua xong là … quên hết rồi ạ
Anh nhẹ nhàng đặt bàn tay ấm áp lên bờ vai tôi
Sinh viên bây giờ thiếu quá nhiều kĩ năng làm việc, em cần phải được đào tạo lại từ đầu. Ngày mai anh sẽ dậy cho em những kiến thức cơ bản về Cấu trúc dữ liệu và giải thuật. Đây là những kiến thức nền tảng mà bất kì ai cũng cần phải nắm vững khi làm trong ngành CNTT. Ngay cả những tập đoàn lớn nhưng Amazon, hay Google khi phỏng vấn họ cũng hỏi em những câu hỏi về lĩnh vực này
Kể từ đó, ngày nào anh cũng tận tình chỉ bảo tôi những kiến thức về cấu trúc dữ liệu và giải thuật…
Cấu trúc dữ liệu là cách để tổ chức data trong máy tính để có thể sử dụng một cách hiệu quả. Thuật toán , là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước
Em cứ hình dung, ngôn ngữ lập trình thì cũng như tiếng Việt hay tiếng Anh, biết thì nói chuyện được sơ sơ, nói và viết được các nội dung đơn giản. Cấu trúc dữ liệu thì như ngữ pháp, biết cách dùng rồi thì viết câu sẽ chuẩn hơn, ai cũng hiểu, không hiểu nhầm. Còn giải thuật thì như là nội dung nói (hoặc viết) vậy, trong đó có cách tổ chức bài nói (hoặc bài viết), nói gì, ý trước ý sau ra sao, phân tích, lập luận thế nào…
Anh sẽ giảng giải cho em những kiến thức về Cấu trúc dữ liệu và thuật toán từ đơn giản đến nâng cao. Từ dữ liệu stack, tree cho tới lý thuyết đồ thị, kĩ thuật duyệt cây nhị phân, duyệt đồ thị…
Cấu trúc dữ liệu thì bao gồm cấu trúc đơn giản và nâng cao như sau
Array
Mảng có thể lưu giữ một số phần tử cố định và các phần tử này nền có cùng kiểu. Hầu hết các cấu trúc dữ liệu đều sử dụng mảng để triển khai giải thuật.
Hãy tưởng tượng có rất nhiều chàng trai yêu em, mỗi người được lưu vào trong 1 mảng. Mỗi chàng trai là 1 phần tử của mảng, được đánh index theo thứ tự từ 0 để nhận dạng và được lưu liên tục trong RAM như hình trên
Em có thể dễ dàng tìm kiếm các chàng trai trong mảng, thêm, sửa, và loại đi những chàng trai mà em không thích bằng đoạn code như sau
public class TestArray {
public static void main(String[] args) {
// Declare array
string[] myLoveList = {'Minh','Nam', 'Nguyen', 'Hung'};
// Print all the array elements
for (int i = 0; i < myLoveList.length; i++) {
System.out.println(myLoveList[i] + " ");
}
// Choose a lover : Nam
System.out.println(myLoveList[1] + " ");
}
}
Ưu điểm
Ưu điểm của mảng là tốc độ truy cập nhanh và có thể truy cập đến các vị trí ngẫu nhiên.
Nhược điểm
Kích thước của mảng luôn phải cố định và phải dc khai báo trước khi chạy chương trình. Em tưởng tượng em tạo một mảng gồm 4 người thích em. Điều gì xảy ra nều em muốn có 10, 20 người thích em sau này. Thực tế vùng nhớ chương trình là ko thể dự báo trước, cũng như ko thể đoán trước có bao nhiêu người yêu em. Khai báo mảng quá lớn hay quá nhỏ đếu dẫn tới thiếu hoặc dư thừa bộ nhớ
Một điều quan trọng nữa có thể em chưa biết. Các byte vùng nhớ cấp phát mảng được sắp xếp liên tục. Nếu như vùng nhớ bị phân mảnh giống như phân mảnh đĩa thì chương trình sẽ báo lỗi không đủ vùng nhớ liên tục.
Ngay cả việc chèn, hay xóa phần tử ở vị trí N trong mảng cũng sẽ ảnh hưởng performance, khi các toàn bộ phần tử từ N trở đi phải dịch đi
Em muốn thêm Linh vào vị trí thứ 3 thì Minh và Hoang phải lùi lại làm người đến sau. Nếu người yêu em có hàng triệu thì em sẽ thấy performance ảnh hưởng thế nào chứ.
Vì thế có một loại cấu trúc dữ liệu mới được sử dụng đó là
LinkedList
Em hãy tưởng tượng những chàng trai của em sẽ xếp thành hàng dài để đợi em, tay người này nắm lấy áo của người kia. Em sẽ có dữ liệu LinkedList
Có 3 loại LinkedList
Linked List Basic
Doubly Linked List
Circular Linked List
Linked List Basic (Danh sách liên kết đơn)
Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi.
Đây là hình ảnh mô tả một danh sách liên kết.
Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next.
First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First
Đây là code sample của LinkedList. Có 3 chàng trai Nam, Minh, Trung cùng xếp hàng chờ đợi em .Mỗi node đại diện cho 1 chàng trai, tay chàng trai này nắm lấy áo của người trước đó. Trung là người cuối hàng, sẽ không có ai nắm lấy áo bạn ấy (Link là null)
// A simple Java program to introduce a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
String data;
Node next;
Node(String d) { data = d; next=null; } // Constructor
}
/* method to create a simple linked list with 3 nodes*/
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node('Nam');
Node second = new Node('Minh');
Node third = new Node('Trung');
/* Three nodes have been allocated dynamically.
We have refernces to these three blocks as first,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| Nam | null | | Minh | null | | Trung | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next = second; // Link first node with the second node
/* Now next of first Node refers to second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| Nam | o----->| Minh | null | | Trung | null |
+----+------+ +----+------+ +----+------+ */
second.next = third; // Link second node with the third node
/* Now next of second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| Nam | o---->| Minh | o--- ->| Trung | null |
+----+------+ +----+------+ +----+------+ */
}
}
Tuy nhiên danh sách liên kết đơn lại có một số ưu nhược điểm mà em cần chú ý
Ưu điểm
Em có thể lưu những chàng trai đang yêu em một cách dễ dàng, thêm hoặc xóa các chàng trai trong danh sách mà không cần phải cấp phát hoặc tổ chức lại trật tự của mảng. Hơn nữa bộ nhớ được cấp phát động nên em sẽ tối ưu hóa memory hơn là khai báo kiểu mảng tĩnh như ở trên
Nhược điểm
Hãy tưởng tượng 3 chàng trai Nam, Minh, Trung đợi em những em muốn chọn chàng trai cuối cùng, hoặc thêm một người em thích vào danh sách, em đều phải duyệt từ đầu vì một danh sách liên kết đơn không cho phép truy cập ngẫu nhiên dữ liệu
Do đó em cần phải học thêm nhiều loại cấu trúc dữ liệu nữa
Còn nhiều những kiến thức nữa Lý thuyết đồ thị, duyệt cây, tree…, em hãy đến học vào những buổi sau…
Kể từ đó, tôi chỉ mong thời gian trôi nhanh để được anh chỉ dậy những kiến thức về cấu trúc dữ liệu và giải thuật. Cả một bầu trời tình yêu mà tôi đã dành cho anh.
Có những duyên phận mà ta ngỡ đó là tình yêu. Tôi dành cho anh những khoảng thời gian thanh xuân ngọt ngào. Liệu đó có phải là duyên phận…
(Còn tiếp)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?