XEM BÀI VIẾT THEO TỪ KHÓA
angular aspnetcore bkap books csharp eclipse frontend giai-thuat java jsp labguides laravel mongodb nosql opencv oracle php postgresql project python restful review servlet slides sql webapi webservice website xml xsd xslt
CÔNG NGHỆ THÔNG TIN >> SINH VIÊN BKAP

Tìm hiểu danh sách liên kết đơn-Single Linked List [Cấu trúc dữ liệu và giải thuật]

Đăng lúc: 11:39 AM - 24/06/2023 bởi Charles Chung - 342

Trong khoa học máy tính, danh sách liên kết (linked list) là tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý nào của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử sẽ trỏ đến phần tử tiếp theo. Trong bài này chúng ta sẽ tìm hiểu về danh sách liên kết đơn.

1. Danh sách liên kết đơn là gì? (Single Linked List)

Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa một dữ liệu (Data) và một con trỏ (Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, đó chính là phần của cuối cùng của danh sách. Sau đây là hình minh họa 1 phần tử

alt text

Trong danh sách liên kết đơn luôn có một con trỏ head trỏ tới phần tử đầu tiên của danh sách để xác định bắt đầu của một danh sách. Sau đây là hình minh họa một danh sách với con trỏ head

alt text

2. Các thao tác với danh sách trên ngôn ngữ C/C++

  • Tạo cấu trúc dữ liệu
typedef struct SLL{
    int data;
    struct SLL* next;
} NodeS;
  • Hàm tạo 1 nút mới
NodeS* create(int value)
{
    NodeS* temp=malloc(sizeof(struct SLL));
    temp->data=value;
    temp->next=NULL;
    return temp;
}
  • Hàm thêm 1 nút vào đầu danh sách
NodeS* addToHead(NodeS* head, int value)
{
    NodeS* temp=create(value);
    if(head==NULL)
        head=temp;
    else
    {
        temp->next=head;
        head=temp;
    }
    return head;
}
  • Hàm thêm 1 nút vào cuối danh sách
NodeS* addToEnd(NodeS* head, int value)
{
    NodeS* temp=create(value);
    if(head==NULL)
        head=temp;
    else
    {
        NodeS* p=head;
        while(p->next!=NULL)
            p=p->next;
        p->next=temp;
    }
    return head;
}
  • Hàm thêm 1 nút vào vị trí xác định
NodeS* addAt(NodeS* head, int value, int position)
{
    if(position<=0 || head==NULL)
        head=addToHead(head,value);
    else
    {
        int k=1;
        NodeS* p=head;
        while(p!=NULL && k!=position)
        {
            p=p->next;
            k++;
        }
        if(k!=position)
        {
            head=addToEnd(head,value);
        }else
        {
            NodeS* temp=create(value);
            temp->next=p->next;
            p->next=temp;
        }
    }
    return head;
}
  • Hàm xóa 1 nút ở đầu
NodeS* deleteHead(NodeS* head)
{
    if(head==NULL)
        printf("\n Danh sach trong!");
    else
        head=head->next;
    return head;
}
  • Hàm xóa 1 nút ở cuối
NodeS* deleteEnd(NodeS* head)
{
    NodeS* p=head;
    if(head==NULL || head->next==NULL)
        head=deleteHead(head);
    else
    {
        while(p->next->next!=NULL)      
            p=p->next;
    }
    p->next=NULL;
    return head;
}
  • Hàm xóa 1 nút ở vị trí xác định
NodeS* deleteAt(NodeS* head, int position)
{
    if(position<=0)
    {
        head=head->next;
       
    }else
    {
        NodeS* temp=head;
        int k=0;
        while(temp->next->next!=NULL)
        {
            if(++k==position)
            {
                temp->next=temp->next->next;
                break;
            }else
            {
                temp=temp->next;
            }
        }
        if(k!=position)
        {
            temp->next=NULL;
        }
    }
    return head;
}
  • Hàm lấy  dữ liệu 1 nút ở vị trí xác định
int getAt(NodeS* head, int position)
{
    int k=0;
    NodeS* p=head;
    while(p->next!=NULL && k!=position)
    {
        ++k;
        p=p->next;  
    }
    return p->data;
}
  • Hàm tìm kiếm
int search(NodeS* head, int value)
{
    int position=0;
    for(NodeS* p=head;p!=NULL;p=p->next)
    {
        if(p->data==value)
            return position;
        position++;    
    }
    return -1;
}
  • Hàm hiển thị toàn bộ danh sách
void display(NodeS* head)
{
    for(NodeS* p=head;p!=NULL;p=p->next)
        printf("%5d",p->data);
}
  • Chương trình main gọi các hàm
void main()
{
    //tao nut dau danh sach
    NodeS* head=NULL;
    //them 2 phan tu vao dau danh sach
    head=addToHead(head,5);
    head=addToHead(head,2);
    //them 3 phan tu vao cuoi danh sach
    head=addToEnd(head,8);
    head=addToEnd(head,1);
    head=addAt(head,10,2);
    //hien thi danh sach
    printf("\nDu lieu trong danh sach truoc:");
    display(head);
    head=deleteAt(head, 0);
    //hien thi danh sach
    printf("\nDu lieu trong danh sach sau:");
    display(head);
    //tim kiem phan tu co gia tri 8
    printf("\nTim thay phan tu 8 tai vi tri %d\n",search(head,8));
}
  • Kết quả

alt text

thay lời cảm ơn!

QUẢNG CÁO - TIẾP THỊ