2
Đặc điểm và cách cài đặt của danh sách liên kết trong C/C++?
1
kieumy199810 đã đăng:

Mình đang có bài tập về so sánh danh sách liên kết với mảng trong C/C++ nhưng không hiểu lắm về tính chất của hai loại này. Cho mình hỏi danh sách liên kết khác với mảng như thế nào trong C? Mỗi cấu trúc có ưu, nhược điểm gì? Cụ thể các bước cài đặt một danh sách liên kết ra sao? Thanks,

Theo mình biết thì danh sách liên kết khác với mảng về cách lưu trữ trong bộ nhớ. Đối với danh sách liên kết, các phần tử trong danh sách liên kết nằm rải rác trong bộ nhớ vì bản chất của danh sách liên kết là một phần tử có con trỏ trỏ tới một phần tử khác. Còn đối với mảng thì không như vậy, mảng bao gồm các phần tử nằm liền kề nhau trong bộ nhớ.

Vân Khánh 25.11.2017
thêm bình luận...
1
quangvu30 đã đăng:

Từ câu trả lời của Vân Khánh, bạn có thể dễ dàng suy ra ưu, nhược điểm của nó.

Ưu điểm của danh sách liên kết: Danh sách liên kết có phần tử nằm rải rác trong bộ nhớ cho nên vấn đề về phân mảnh bộ nhớ sẽ không xảy ra.

Nhược điểm của mảng: Mảng có các phần tử nằm liên tục, nên giả sử một vùng nhớ nhỏ chưa được cấp phát trong RAM không chứa đủ các phần tử trong mảng, hệ điều hành sẽ cấp phát vùng nhớ mới gây tốn bộ nhớ.

Nhược điểm của danh sách liên kết: Vì các phần tử có các con trỏ trỏ tới bộ nhớ khác cho nên khi muốn tìm một phần tử trong danh sách liên kết ta phải duyệt từ phần tử đầu đến phần tử cần tìm. Giả sử trường hợp xấu nhất phần tử đó nằm ở cuối danh sách liên kết thì sao?

Ưu điểm của mảng: Truy xuất đến một phần tử trong mảng chỉ cần biết chỉ số index của phần tử đó, không cần phải duyệt từng phần tử như ở danh sách liên kết cho nên tốc độ truy xuất nhanh hơn danh sách liên kết.

thêm bình luận...
1
Quang Thuận10 đã đăng:

Bạn có thể tham khảo đoạn code mẫu của mình dưới đây. Khi xây dựng danh sách liên kết bạn cần nhớ các bước chính sau:

  1. Xây dựng cấu trúc dữ liệu của cây (Node)
  2. Khởi tạo danh sách liên kết (cũng có thể khởi tạo trong hàm main)
  3. Tạo Node (cấp phát bộ nhớ để chứa Node)
  4. Thêm Node vào danh sách liên kết (có thể thêm vào đầu hoặc cuối danh sách)
  5. Nhập dữ liệu cho danh sách liên kết
  6. Xuất dữ liệu hoặc thực thiện các thao tác khác

Ở đoạn code bên dưới, mình đã chú thích rất rõ, có gì thắc mắc bạn để lại bình luận bên dưới nha.

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


//1. Xây dựng cấu trúc dữ liệu danh sách liên kết
//---> Cấu trúc dữ liệu 1 Node
struct Node
{
    int Data;
    struct Node *pNext;
};
//--->Xây dựng node đầu và node cuối của danh sách liên kết
struct List
{
    Node *pHead;
    Node *pTail;
};

//2. Khởi tạo danh sách liên kết
void khoiTao(List &l)
{
    l.pHead = l.pTail = NULL;
}

//3. Tạo node 
Node* taoNode(int newData)
{
    //Cấp phát bộ nhớ cho 1 Node
    Node *p = new Node;

    //Kiểm tra xem bộ nhớ có đủ cấp phát không
    if(p == NULL)
    {
        return NULL;
    }

    //Truyền dữ liệu được nhập vào Data trong Node
    p ->Data = newData;

    //Khởi tạo node đã có dữ liệu với con trỏ pNext = NULL
    p ->pNext = NULL;

    return p;
}

//4. Thêm Node(Thêm đầu và thêm cuối)
//-->Thêm vào đầu danh sách liên kết
void themDau(List &l, Node *p)
{
    //Kiểm tra xem danh sách liên kết có rỗng không
    if(l.pHead == NULL)
    {
        l.pHead = l.pTail = p; //Nếu rỗng, node đầu tiên cũng chính là p
    }

    // Nếu không?
    else
    {
        p ->pNext = l.pHead;//p trỏ vào pHead, 
        l.pHead = p;//Node đầu tiên được cập nhật lại thành p
    }
}
//-->Thêm vào cuối danh sách liên kết
void themCuoi(List &l, Node *p)
{
    //Kiểm tra xem danh sách liên kết có rỗng hay không
    if(l.pHead == NULL)
    {
        l.pHead = l.pTail = p; //Nếu rỗng, node đầu tiên cũng chính là p
    }

    //Nếu không?
    else
    {
        l.pTail ->pNext = p; //Node cuối của DSKL (pTail) trỏ vào p
        l.pTail = p;// Node cuối được cập nhật lại thành p
    }
}

//5. Nhập dữ liệu vào DSLK
void nhapDuLieu(List &l, int &n)
{
    khoiTao(l);//Khởi tạo danh sách liên kết
    for(int i = 0; i < n; i++)
    {
        int newData;
        printf("Nhap vao gia tri phan tu thu %d: ", i+1);
        scanf("%d", &newData);

        Node *p = taoNode(newData);//Cấp phát bộ nhớ cho 1 Node

        // Thêm node đã được tạo vào cuối danh sách liên kết
        themCuoi(l, p);
        //themDau(l, p); Hoặc sử dụng node vào đầu danh sách liên kết
    }
}

//6. Xuất dữ liệu
void xuatDuLieu(List l)
{
    for(Node *i = l.pHead; i != NULL; i = i ->pNext)
    {
        printf("%5d", i ->Data);
    }
}

int main()
{
    // Khởi tạo danh sách liên kết
    List l;
    int n;


    // Nhập số lượng Node cho danh sách liên kết
    do{
        printf("Nhap vao so luong phan tu cua danh sach lien ket = ");
        scanf("%d", &n);

        if(n < 0)
            printf("\nSo phan tu khong hop le. Xin kiem tra lai!!\n");

    }while(n < 0);

    // Nhập dữ liệu cho danh sách liên kết
    nhapDuLieu(l, n);

    // Xuất dữ liệu từ danh sách liên kết
    printf("Danh sach lien ket da nhap la: \n");
    xuatDuLieu(l);


    getch();
    return 0;
}
đã bổ sung 6.3 năm trước bởi
Sóc Trăng
thêm bình luận...
Bạn đang thắc mắc? Ghi câu hỏi của bạn và đăng ở chế độ cộng đồng (?)