Tổ Chức Bộ Nhớ Chương Trình

Giới thiệu

Khi một chương trình được thực thi, nó sẽ được nạp vào trong bộ nhớ, vậy quá trình đó được thực hiện và tổ chức như thế nào?

Đối tượng hướng đến

Những lập trình viên đang nghiên cứu về các vùng nhớ hoặc bắt đầu làm quen với con trỏ

Kiến thức mở đầu

Khi ta khai báo một biến trong C++, thì biến này gồm 2 phần là địa chỉ và giá trị của nó. Không chỉ có biến, mà các đoạn mã nguồn cũng có địa chỉ chỉ và giá trị. Có bao giờ bạn thắc mắc rằng biến hay mã nguồn được lưu trữ như thế nào khi chương trình thực thi?

Khi chương trình được khởi chạy, hệ điều hành sẽ chọn ra 4 vùng nhớ trống trong RAM có kích thước tương ứng với kích thước của 4 vùng nhớ mà chương trình cần sử dụng, mà ta thường gọi là Memory Segment. Biến và mã nguồn sẽ được lưu trữ trong các Segment này, địa chỉ của chúng chính là địa chỉ trong RAM.

Các vùng nhớ

Code Segment

Mã nguồn của chúng ta sau khi hoàn tất quá trình Build sẽ chuyển thành các đoạn mã máy 0 và 1. Khi chương trình khởi chạy, các đoạn mã máy này sẽ được nạp vào Code Segment. Cách duy nhất để truy xuất vào vùng nhớ này là sử dụng Con trỏ hàm.

Code Segment có kích thước cố định.

Data Segment

Khi chương trình được khởi chạy, toàn bộ các biến toàn cục và static đều được lưu trữ ở đây, các đoạn chuỗi cố định cũng được lưu trữ trong Data Segment.

Data Segment có kích thước cố định

Stack Segment

Đây là vùng nhớ mà chúng ta cần quan tâm. Khi một hàm được gọi, hàm đó sẽ được đưa vào vùng nhớ Stack, các biến được khai báo trong hàm đó cũng được đưa vào vùng nhớ Stack. Khi hàm kết thúc, toàn bộ các biến trong hàm cùng với bản thân hàm sẽ được tự động giải phóng để các hàm sau sử dụng.

Stack Segment có kích thước cố định. Khi chúng ta khai báo quá nhiều biến hoặc một mảng có số lượng phần tử quá lớn, một hàm đệ quy vô hạn… bộ nhớ Stack sẽ bị đầy, dẫn đến chương trình bị dừng. Chúng ta cần lưu ý chuyện này.

Heap Segment

Đây là vùng nhớ khác mà chúng ta cần quan tâm, vùng nhớ này chúng ta phải hoàn toàn kiểm soát nó. Khi chúng ta sử dụng con trỏ và cấp phát động một vùng nhớ cho con trỏ quản lý, vùng nhớ này sẽ nằm trong Heap Segment. Những vùng nhớ được cấp phát động sẽ không tự động thu hồi khi khối lệnh kết thúc, lập trình viên phải chủ động thu hồi chúng khi không còn nhu cầu sử dụng.

Heap Segment có kích thước không cố định, nên nó còn được gọi là vùng nhớ động, kích thước của nó có thể tăng hoặc giảm tùy vào sự cấp phát động. Lưu ý là Heap có thể mở rộng cho đến khi RAM đầy, nên chúng ta cần kiểm soát thật tốt, thu hồi các vùng nhớ được cấp phát động ngay khi không còn nhu cầu sử dụng để tránh việc lãng phí bộ nhớ.

Lời kết

Đây là bài viết mở đầu của chương con trỏ, nên các kiến thức này khá quan trọng, đặc biệt là kiến thức về Stack và Heap. Các khái niệm mới được đề cập ở trên như con trỏ, con trỏ hàm, cấp phát động sẽ được giải thích rõ ở các bài viết tiếp theo.

source: http://www.stdio.vn/articles/read/151/to-chuc-bo-nho-chuong-trinh

Posted By Thang Vuong 23:53

0

Continue Reading

Stack - Queue

Giới thiệu

Stack – Ngăn xếp là cấu trúc dữ liệu quan trọng , là kiến thức không thể thiếu trong khoa học máy tính và được ứng dụng rất nhiều trong lập trình. Nó là kiểu dữ liệu cơ bản để giải những bài toán từ đơn giản đến phức tạp, nhiều bài toán phức tạp đã được đơn giản hóa đi rất nhiều nhờ loại cấu trúc dữ liệu này.

Tiền đề bài viết

Sau một thời gian tìm hiểu và ứng dụng Stack, tôi đã có được một số kinh nghiệm và muốn chia sẻ những kiến thức của bản thân.

Đối tượng hướng đến

Vì trong bài này tôi xây dựng Stack bằng Linked List - các bạn có thể tham khảo thêm vấn đề nàycủa tác giả Hòa Đinh - do đó bài viết này hướng đến những bạn có kiến thức về con trỏ và Linked List (danh sách liên kết).
Toàn bộ những ví dụ trong bài này tôi sử dụng ngôn ngữ C++ và Visual Studio Utimate 2013 trênWindows 8.1.

Stack là gì?

Stack là một kiểu cấu trúc dữ liệu và cơ chế của nó là LIFO (Last In First Out) nghĩa là vào sau ra trước. Ta có thể hình dung Stack như một chồng đĩa ,ta chỉ có thể lấy chiếc đĩa ra hoặc thêm một chiếc đĩa khác vào trên đỉnh của nó và chiêc đĩa nằm trên đỉnh đó được gọi là Top.

Các phương thức của Stack

Cài đặt cấu trúc stack

Trong bài này tôi sử dụng struct để tạo cấu trúc stack.

struct Number
{
 int number;
 Number *pNextNum;
};
Number *top;

Trên đây tôi tạo một struct tên là Number, trong struct này gồm có một field kiểu int để lưu trữ giá trị của một phần tử và con trỏ kiểu Number để trỏ tới phần tử kế tiếp trên nó trong stack. Con trỏ top kiểuNumber dùng để trỏ tới phần tử trên cùng của stack.

isEmpty()

Phương thức isEmpty này giúp kiểm tra stack có rỗng hay không, nếu rỗng sẽ trả về true nếu không rỗng sẽ trả về false.

int isEmpty()
{
    if (top == NULL)
        return true;
    return false;
}

Push()

Phương thức Push là thêm một phần tử vào trên cùng của stack.

-> Phương thức này tương đương với việc thêm một Node vào đầu danh sách liên kết

void pushNum(int value)
{
    Number *ptr = new Number;//tạo mới một phần tử
    ptr->number = value;     //gán giá trị cho phần tử
    ptr->pNextNum = top; //phần tử này trỏ tới phần tử dưới nó trong stack
    top = ptr;    //đánh dấu phần tử này hiện đang nằm trên đỉnh của stack
}

Trước tiên ta tạo ra một con trỏ mới kiểu Number và gán giá trị cho phần tử này. Cho phần tử này liên kết đến phần tử nằm ngay dưới nó bằng cách sử dụng field pNextNum trỏ tới phần tử đó. Cuối cùng ta dùng con trỏ top trỏ tới phần tử vừa được thêm vào stack để có thể lấy phần tử đó ra.

Pop()

Phương thức Pop là lấy một phần tử nằm trên đỉnh của stack.

-> Phương thức này tương đương với việc Delete một Node đứng đầu danh sách liên kết

int popNumber()
{
 int result = 0;
 if (isEmpty())
 {
  return NULL; //nếu stack rỗng thì return về NULL
 }
 else
 {
  Number *ptr = top; //dùng một con trỏ trỏ tới phần tử đầu tiên của stack
  result = top->number; //lấy giá trị 
  top = top->pNextNum; //gán con trỏ top cho phần tử ngay dưới nó
  delete ptr;  //delete phần tử vừa được lấy
  return result; // trả kết quả
 }
}

Nhiệm vụ của phương thức này là lấy một phần tử ở trên đỉnh của stack và trả về giá trị của phần tử đó. Ngay sau khi lấy một phần tử ra thì ta phải xóa phần tử đó đi để tránh memory leak.

Chúng ta có thể hình dung stack được xây dựng bằng linked list qua sơ đồ sau:

Source: http://www.stdio.vn/articles/read/104/stack-ngan-xep

Posted By Thang Vuong 00:12

0

Continue Reading

Danh sách liên kết đơn

1. Danh sách liên kết đơn là gì?
2. Tại sao phải dùng danh sách liên kết để lưu trữ dữ liệu?

Kiến thứ Yêu cầu:

Linked List = Pointer + Struct (class)

I. Danh sách liên kết đơn là gì?

- Cấu tạo

Gồm dãy các Node liên kết với nhau, mỗi Node gồm 2 thành phần:

- Data: là dữ liệu của node

- pNext: Con trỏ trỏ tới node kế tiếp

-----------------------------------------------------------

2 điều cơ bản cần nắm cho sự khác biệt của Linked List mạnh hơn mảng là

- cấp phát động, dùng bao nhiêu cấp phát bấy nhiêu khiến cho bộ nhớ cần dùng không bị dư lãng phí cũng như không bị thiếu. dễ dàng thêm vào

- đối với mạng các dự liệu phải liền kề nhau nhưng đối với Linked List thì các member không nhất thiết phải gần nhau vì nó quản lý theo kiểu con trỏ, dùng địa chỉ nên nếu trong trường hợp bộ nhớ còn 5 bộ nhớ trống nhưng 5 cái đó nó không nằm gần nhau khi đó chỉ có thể dùng Linked List để lưu trữ.

/*------------------------------------------------------------------------------------------------------*/

Giới thiệu

Danh sách liên kết là 1 cấu trúc dữ liệu cơ bản, được sử dụng để khắc phục hạn chế của mảng (cố định về kích thước). C++ nói chung và cụ thể là thư viện STL đã cung cấp sẵn một kiểu dữ liệu List. Tuy nhiên tôi vẫn muốn chia sẻ bài viết này để nêu rõ về bản chất của danh sách liên kết và một số thao tác cơ bản trên nó.

Tiền đề bài viết

Trong quá trình nghiên cứu tôi nhận thấy danh sách liên kết đơn là một cấu trúc dữ liệu khá thú vị,  và nhờ nó tôi hình dung rõ hơn về chức năng lưu trữ địa chỉ của con trỏ. Do đó, tôi muốn chia sẻ với mọi người một số kiến thức cơ bản về danh sách liên kết (linked-list).

Đối tượng hướng đến

Bài viết dành cho các bạn lập trình viên đã có kiến thức cơ bản về struct và pointer trong ngôn ngữ C++, có nhu cầu tìm hiểu về cấu trúc dữ liệu danh sách liên kết (linked list).

Toàn bộ code trong các ví dụ minh họa bên dưới được tôi thực hiện với Visual Studio Propressional 2013trên môi trường Windows 8.1.

Tổ chức danh sách liên kết đơn

Cũng giống như mảng, danh sách liên kết cũng bao gồm các phần tử, có mối liên hệ với nhau. Tôi gọi mỗi phần tử đó là một Node. Node được xem là trái tim của danh sách liên kết, mỗi Node sẽ lưu trữ 2 thông tin:

• Thông tin dữ liệu: Lưu trữ các thông tìn về chính Node đó.
• Thông tin liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu phần tử đó nằm cuối danh sách. 

Một cách tổng quát ta có:

struct SNode
{
 Data Info;
 SNode* pNext;
};

Mỗi phần tử trong trong danh sách liên kết đơn là một biến động sẽ được yêu cầu cấp phát khi cần thiết, danh sách liên kết đơn chính là sự liên kết các biến này với nhau do đó ta hoàn toàn chủ động về số lượng các phần tử.

Để đơn giản, trong bài viết này tôi sẽ lấy ví dụ danh sách liên kết đơn lưu trữ các số nguyên.

Node của danh sách liên kết sẽ được định nghĩa như sau:

struct SNode
{
 int Data;
 SNode* pNext;
};

 Tôi sử dụng một phương thức GetNode để cấp phát động một Node khi cần thiết:

SNode* GetNode(int x)
{
 SNode *p = new SNode;
 
 p->Data = x;
 p->pNext = NULL;
 
 return p;
}

Bây giờ chúng ta bắt đầu tìm hiểu một số phương thức đơn giản tạo nên sự liên kết các Node để tạo ra một danh sách liên kết đơn hoàn chỉnh.

Một số thao tác cơ bản trên danh sách liên kết đơn

Trong danh sách liên kết đơn, các Node sẽ không được lưu liên tiếp nhau trên bộ nhớ, Node trước sẽ mang thông tin địa chỉ của Node sau, như vậy nếu bạn xử lý lỗi một Node sẽ dẫn đến tính huống xấu nhất, ta sẽ mất toàn bộ thông tin của các Node phía sau.

Chúng ta sẽ bắt đầu làm việc với các thao tác cơ bản trên một danh sách liên kết đơn. Giả sử tôi có định nghĩa sau:

struct SNode
{
 int Data;
 SNode* pNext;
};
 
struct SList
{
 SNode* pHead;
 SNode* pTail;
 
 SList(){}
 SList(SNode* Head, SNode* Tail)
 {
  this->pHead = Head;
  this->pTail = Tail;
 }
};

Nếu biết được địa chỉ đầu tiên trong danh sách liên kết ta có thể dựa vào thông tin pNext để truy xuất đến các phần tử còn lại, do đó ta sẽ dùng một con trỏ pHead để lưu lại địa chỉ Node đầu tiên của danh sách. Trong một số trường hợp ta cũng cần thao tác trên phần tử cuối cùng của danh sách, nên tôi dùng thêm một con trỏ pTail để lưu trữ địa chỉ của Node cuối cùng trong danh sách.

Chèn vào đầu danh sách

Như đã trình bày ở trên, khi thao tác với mỗi Node trên danh sách liên kết ta cần thực hiện cẩn thận, đúng thứ tự để tránh mất thông tin của các Node phía sau. Dưới đây là thứ tự các bước chèn một phần tử vào đầu mảng.

Bước 1: cấp phát một Node mới (new_element).

Bước 2: gán pNext của Node mới trỏ đến Node đầu (cũ).

new_element->pNext = pHead;

Bước 3: cập nhập lại giá trị pHead. Chính là cập nhật lại địa chỉ, thay đổi địa chỉ của nó về với node đầu mình tạo ra. và do node này cần phải đứng đầu tiên trong Linked List nên nó sẽ chứa địa chỉ của pHead.

pHead = new_element;

Lưu đồ bên dưới thể hiện từng bước để thêm vào một Node mới ở đầu danh sách

Chèn vào cuối danh sách

Tương tự với thao tác chèn vào đầu danh sách, chèn vào cuối danh sách chúng ta chỉ cần cập nhập lại con trỏ pTail.

Bước 1: cấp phát một Node mới (new_element).

Bước 2: gán lại pNext của Node cuối cùng (cũ) sẽ trỏ đến Node mới. 

pTail->pNext = new_element;

Bước 3: cập nhập lại giá trị pTail, bây giờ Node cuối của danh sách là Node chúng ta vừa thêm.

pTail = new_element;

Đây là lưu đồ thứ tự thực hiên các bước ở trên

Chèn vào danh sách sau một phần tử q

Chèn vào danh sách sau một phần tử q nào đó, chèn vào giữa danh sách không cần cập nhập lại hai con trỏ pHead và pTail tuy nhiên chúng ta cần hết sức cần thận để tránh mất dữ liệu phía sau.

Bước 1: cấp phát một Node mới - new_element.

Bước 2: gán pNext của Node mới bằng địa chỉ của Node sau q.

new_element ->pNext = q-> pNext;

Bước 3: cập nhập lại pNext của Node q trỏ đến Node mới.

q-> pNext = new_element;

Xóa một phần tử đầu danh sách

Tương tự như thao tác xóa phần tử đầu danh sách, để xóa một phần tử đứng sau phần tử q, ta thực hiện các bước sau:

Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.

SNode* p = pHead;

Bước 2: cập nhập lại giá trị của pHead.

pHead = pHead->pNext;

Bước 3: giải phóng vùng nhớ của Node cần xóa.

delete p;

Xóa một phần tử đứng sau phần tử q

Xóa 1 phần tử ở đầu danh sách không chỉ đơn giản là cập nhập lại biến con trỏ pHead, mà ta phải giải phóng được vùng nhớ của Node cần xóa.

Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.

SNode* p = q;

Bước 2: cập nhập lại giá trị pNext của Node q.

q->pNext = p->pNext;

Bước 3: giải phóng vùng nhớ của Node cần xóa.

delete p;

Duyệt danh sách

Khi có được giá trị của pHead ta có thể dựa và thông tin pNext để duyệt lần lượt các phần tử của danh sách.

SNode* p;
 
p = list.pHead;
while (p != NULL)
{
 // Process Node
 p = p->pNext;
}

Lời kết

Source code được viết theo hướng cấu trúc để các bạn chưa có khái niệm về hướng đối tượng có thể tiếp cận một cách dễ dàng.

Có thể thấy được, danh sách liên kết đã khắc phục được nhược điểm của mảng - đó là kích thước cố định.Với bài viết này, hy vọng các bạn đã có cái nhìn tổng quát hơn về danh sách liên kết và các thao tác liên quan như: thêm phần tử, xóa phần tử ... và có thể ứng dụng được vào các dự án của mình.

Posted By Thang Vuong 23:25

0

Continue Reading

DATA STRUCTURE AND ALGORITHM

data structure and algorithm's knowledge shall be posted

Posted By Thang Vuong 10:16

0

Continue Reading