Học tập‎ > ‎C++‎ > ‎

Danh sách liên kết (DSLK)

Danh sách liên kết (DSLK) là 1 phần rất quan trọng trong bộ môn Cấu trúc dữ liệu tại các trường Đại
học. Và đa số các SV khi mới tiếp cận với cấu trúc này đều tỏ ra khá bối rối.

1. Khái niệm DSLK
Có lẽ trước hết bạn cần nắm vững khái niệm ô nhớ và con trỏ. Trong tư duy của bạn cần tách biệt
rõ ràng 2 khái niệm này. Ô nhớ luôn nằm cố định rải rác đâu đó trên bộ nhớ máy tính, con trỏ là 1
công cụ giúp ta biết được địa chỉ ô nhớ đó, truy xuất, chỉnh sữa dữ liệu trên ô nhớ, hay thậm chí là
giải phóng ô nhớ. Như vậy 1 con trỏ khi đang trỏ vào 1 ô nhớ, nó chỉ có thể cho ta thông tin trên ô
đó mà thôi, làm thế nào để có thể lấy thông tin ở 1 ô nhớ khác? Và DSLK ra đời từ đây!
Chúng ta xem qua cách định nghĩa sau:
Code:

struct node {
    int value;
    node* next;
**;


Có 1 điều thú vị trong định nghĩa này đó là sự đệ quy, chúng ta sử dụng node trong lúc đang định
nghĩa node. Trường next có 1 ý nghĩa rất quan trọng, và nó chính là chiếc cầu dẫn bạn từ ô nhớ này
đi sang ô nhớ khác.

Cấp phát bộ nhớ: giả sử bạn đang có 1 con trỏ t kiểu node, nó chưa trỏ vào đâu cả, bạn cần xin cấp
phát 1 ô nhớ mới kiểu node cho t trỏ vào, dùng lệnh:
Code:

t = (node*)malloc(sizeof(node));

Hàm malloc(int size) sẽ tạo ra 1 ô nhớ mới trên bộ nhớ có kích thước size byte đồng thời trả về 1
con trỏ kiểu tổng quát đang trỏ vào ô nhớ đấy, ta phải ép kiểu thành con trỏ kiểu node. Lúc này ta có
thể thoải mái thao tác trên ô nhớ thông qua con trỏ t.
Bây giờ ta tạo ra 1 con trỏ z tương tự như vậy, hãy xem đoạn code sau:
Code:

    z->value = 2006;
    z->next = NULL;
    t->value = 3006;
    t->next = z;


Câu lệnh cuối cùng đáng xem, trường next của t (là 1 con trỏ kiểu node) được trỏ vào z, hay chính
xác hơn là vào ô nhớ mà z đang trỏ vào. Vậy là từ ô nhớ này ta đã có thể nhảy sang ô nhớ khác.
Chú ý câu lệnh có chữ NULL, có nghĩa rằng từ ô nhớ mà z đang trỏ vào này, bạn chẳng thể nhảy đi
đâu được nữa, kĩ thuật này dùng để nhận biết phần tử nằm cuối danh sách.

Như vậy, chỉ cần có trong tay 1 con trỏ (chính xác là 1 ô nhớ và con trỏ đang trỏ vào đó), thông qua
trường next bạn có thể nhảy tuần tự đến các ô nhớ khác, lấy thông tin trên đó, cho đến khi nào
không nhảy được nữa. Đó chính là 1 DSLK. Tuy nhiên để có thể nhảy nhót thoái mái như thế bạn
cần phải biết cách tạo ra trước đó 1 DSLK đã. Chúng ta chuyển qua phần 2.

2. Các thao tác căn bản với DSLK:

a. Tạo 1 DSLK mới
Code:

head = NULL;
for (i = 0; i < N; i++) {
    scanf("%d", &x);
    t = (node*)malloc(sizeof(node));
    t->value = x;
    t->next = head;
    head = t;

Mỗi 1 lần đọc vào 1 số nguyên x, ta xin cấp phát bộ nhớ và t trỏ vào ô nhớ đó, giá trị x được
chuyển vào trường value, để kết nạp thêm ô nhớ này vào danh sách, ta đưa t lên đầu danh sách
bằng 2 câu lệnh cuối.

b. Xóa
Để xóa 1 phần tử cho trước ta cần phải biết 2 con trỏ đứng kề trước và sau nó.
Giả sử t là con trỏ đang trỏ vào ô nhớ cần xóa, p là con trỏ kề trước nó (p->next == t) và q là
con trỏ kề sau nó (t->next == q). Xóa đơn giản là:
Code:

    free(t);
    p->next = q;


c. Chèn
Ta đang có 1 ô nhớ mà con trỏ t trỏ vào, giờ ta muốn chèn nó vào giữa 2 con trỏ p, q trong danh
sách:
Code:

    p->next = t;
    t->next = q;


d. Duyệt qua DSLK
Ta có 1 con trỏ head trỏ vào ô nhớ đầu tiên của DSLK, duyệt qua chúng như sau:
Code:

t = head;
while (t != NULL) {
    x = t->value;
    // làm gì đó với giá trị x
    t = t->next; // nhảy sang ô nhớ kế tiếp

3. So sánh giữa mảng và DSLK
Ưu điểm lớn nhất của DSLK là sự linh hoạt, mềm dẻo thể hiện qua các thao tác căn bản ở trên.
Nhược điểm của nó là ta không thể truy xuất đến ngay 1 phần tử khi biết số thứ tự. Trong khi,
đó là chuyện dễ dàng đối với mảng và mảng phải trả giá bằng việc các thao tác xóa, chèn rất vất
vả. Dùng DSLK thì không cần biết trước số phần tử còn mảng thì ngược lại.
Nhìn chung tùy từng bài toán, mục đích mà ta chọn cấu trúc nào cho phù hợp.

DSLKD

#include <iostream.h>
#include <conio.h>

class Node
{
    private:
        float data;
        Node *next;
    public:
        Node()
        {
            data = 0;
            next = NULL;
        **
        Node(float x)
        {
            data = x;
            next = NULL;
       **
        void setnext(Node *p)
        {
            next = p;
        **
        Node * getnext()
        {
            return next;
        **
        void setdata(float x)
        {
           data = x;
        **
      float getdata()
        {
            return data;
        **
**;

class List
{
    private:
        Node *head;
    public:
        List()
        {head = NULL;**
        List(Node *x)
        {head = x;**

    void chensapxep(float x)
        Node *p,*q;
        p = new Node(x);
        q = head;
        if(head == NULL)
        head = p;
        else
        {
            if(p->getdata() < head->getdata())
            {
                p->setnext(head);
                head = p;
            **
            else
            {
                while ( q->getnext()!= NULL)
                {
                    if ((q->getdata()< p->getdata() && q->getnext()->getdata() >p->getdata())
                    || (q->getdata()==p->getdata() && q->getnext()->getdata() >=p->getdata()))
                    {

                        p->setnext(q->getnext());
                        q->setnext(p);
                        break;
                    **
                    else
                   q = q->getnext();
                **
                if (q->getnext()==NULL)
                    q->setnext(p);

            **
        **
    **

    void show()
    {
        Node *p = head;
       p = p->getnext();
        if( head != NULL)
       {
            while(p != NULL)
            {
                cout<<p->getdata()<<" ";
                p = p->getnext();
            **
        **
    **
**;
void main()
{
    float so;
    List p;
    do
    {
        cout<<"Nhap vao so (nhap 0 de thoat):";
        cin>>so;
        p.chensapxep(so);
    **while(so != 0);
    p.show();
    getch();
**

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

struct Node
{
    int n;

    Node *next;

**;

typedef Node* link;

void main()

{

 link head, p;

 link temp;

 int i;

 clrscr();

 head=new Node;

 head->n=1;

 p=head;

 for(i=2;i<=40;i++)

 {

     p->next=new Node;

     p=p->next;

     p->n=i;

  **

  p->next=head;

  while (p->next!=p)

  {

     for(i=0;i<2;i++) p=p->next;

     temp=p->next;

     p->next=temp->next;

     cout<<temp->n<<" t";

     delete temp;

   **

   cout<<p->n;

   delete p;

   getch();

**

Comments