Các thuật toán cơ bản của danh sách liên kết năm 2024

Question

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.

Chương trình minh họa Danh sách liên kết (Linked List) trong C

include <stdio.h>

include <string.h>

include <stdlib.h>

include <stdbool.h>

struct node { int data; int key; struct node next; }; struct node *head = NULL; struct node *current = NULL; //hien thi danh sach void printList() { struct node *ptr = head; printf("\n[ "); //bat dau tu phan dau danh sach while(ptr != NULL) {

  printf("(%d,%d) ",ptr->key,ptr->data);
  ptr = ptr->next;

} printf(" ]"); } //chen link tai vi tri dau tien void insertFirst(int key, int data) { //tao mot link struct node *link = (struct node) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro link nay toi first node cu link->next = head; //tro first toi first node moi head = link; } //xoa phan tu dau tien struct node* deleteFirst() { //luu tham chieu toi first link struct node tempLink = head; //danh dau next toi first link la first head = head->next; //tra ve link bi xoa return tempLink; } //kiem tra list co trong hay khong bool isEmpty() { return head == NULL; } int length() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) {
length++;
} return length; } //tim mot link voi key da cho struct node find(int key){ //bat dau tim tu first link struct node* current = head; //neu list la trong if(head == NULL) {

  return NULL;

} //duyet qua list while(current->key != key){

  //neu day la last node
  if(current->next == NULL){
     return NULL;
  }else {
     //di chuyen toi next link
     current = current->next;
  }

} //neu tim thay du lieu, tra ve link hien tai return current; } //xoa mot link voi key da cho struct node* deleteKey(int key){ //bat dau tu first link struct node* current = head; struct node* previous = NULL; //neu list la trong if(head == NULL){

  return NULL;

} //duyet qua list while(current->key != key){

  //neu day la last node
  if(current->next == NULL){
     return NULL;
  }else {
     //luu tham chieu toi link hien tai
     previous = current;
     //di chuyen toi next link
     current = current->next;             
  }

} //cap nhat link if(current == head) {

  //thay doi first de tro toi next link
  head = head->next;

}else {

  //bo qua link hien tai
  previous->next = current->next;

} return current; } // ham sap xep void sort(){ int i, j, k, tempKey, tempData ; struct node current; struct node next; int size = length(); k = size ; for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ; next = head->next ; for ( j = 1 ; j < k ; j++ ) { if ( current->data > next->data ) { tempData = current->data ; current->data = next->data; next->data = tempData ; tempKey = current->key; current->key = next->key; next->key = tempKey; } current = current->next; next = next->next; }
} } // ham dao nguoc list void reverse(struct node head_ref) { struct node* prev = NULL; struct node* current = head_ref; struct node next; while (current != NULL) {

  next  = current->next;  
  current->next = prev;   
  prev = current;
  current = next;

} *head_ref = prev; } main() { insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("Danh sach ban dau: "); //in danh sach printList(); while(!isEmpty()){

  struct node *temp = deleteFirst();
  printf("\nGia tri bi xoa:");  
  printf("(%d,%d) ",temp->key,temp->data);

} printf("\nDanh sach sau khi da xoa gia tri: "); printList(); insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("\nPhuc hoi danh sach: "); printList(); printf("\n"); struct node *foundLink = find(4); if(foundLink != NULL){

  printf("Tim thay phan tu: ");  
  printf("(%d,%d) ",foundLink->key,foundLink->data);  
  printf("\n");

}else {

  printf("Khong tim thay phan tu.");

} deleteKey(4); printf("Danh sach, sau khi xoa mot phan tu: "); printList(); printf("\n"); foundLink = find(4); if(foundLink != NULL){

  printf("Tim thay phan tu: ");  
  printf("(%d,%d) ",foundLink->key,foundLink->data);  
  printf("\n");

}else {

  printf("Khong tim thay phan tu.");

} printf("\n"); sort(); printf("Danh sach sau khi duoc sap xep: "); printList(); reverse(&head); printf("\nDanh sach sau khi bi dao nguoc: "); printList(); }

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

mẹo hay Học Tốt Sách Top List Danh sách List trong C++ Linked list C