VietTuts

Tự Học Lập Trình Online

  • Home
  • Java
  • Servlet
  • JSP
  • Struts2
  • Hibernate
  • Spring
  • MyBatis
  • Java WS
  • C
  • C++
  • C#
  • Python
  • PHP
  • Excel
  • VBA
  • Web
    • JavaScript
    • JQUERY
    • JSON
    • AJAX
    • CSS
    • HTML
    • HTML5
    • Node.js
    • Angular 7
  • SQL
    • MySQL
    • SQL Server
  • Misc
    • Eclipse
    • Phần mềm tiện ích
    • Cấu trúc DL&GT
    • Selenium Test

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search
1 / 3
❮ ❯

Cấu trúc dữ liệu danh sách liên kết vòng (Circular Linked List)


Cấu trúc dữ liệu danh sách liên kết đôi (Doubly Linked List)
Cấu trúc dữ liệu ngăn xếp (Stack)

Nội dung chính

  • Danh sách liên kết vòng (Circular Linked List) là gì?
  • Tạo Danh sách liên kết vòng từ Danh sách liên kết đơn
  • Tạo Danh sách liên kết vòng từ Danh sách liên kết đôi
  • Các hoạt động cơ bản trên Danh sách liên kết vòng
  • Hoạt động chèn trong Danh sách liên kết vòng
  • Hoạt động xóa trong Danh sách liên kết vòng
  • Hiển thị Danh sách liên kết vòng

Danh sách liên kết vòng (Circular Linked List) là gì?

Danh sách liên kết vòng (Circular Linked List) là một biến thể của danh sách liên kết (Linked List), trong đó phần tử đầu tiên trỏ tới phần tử cuối cùng và phần tử cuối cùng trỏ tới phần tử đầu tiên.

Cả hai loại Danh sách liên kết đơn (Singly Linked List) và Danh sách liên kết đôi (Doubly Linked List) đều có thể được tạo thành dạng Danh sách liên kết vòng. Phần dưới chúng ta sẽ tìm hiểu từng cách tạo một.



Tạo Danh sách liên kết vòng từ Danh sách liên kết đơn

Trong Danh sách liên kết đơn, điểm trỏ tới kế tiếp của nút cuối sẽ trỏ tới nút đầu tiên, thay vì sẽ trỏ tới NULL.

Tạo Danh sách liên kết vòng từ Danh sách liên kết đơn

Tạo Danh sách liên kết vòng từ Danh sách liên kết đôi

Trong Danh sách liên kết đôi, điểm trỏ tới kế tiếp của nút cuối trỏ tới nút đầu tiên và điểm trỏ tới phía trước của nút trước sẽ trỏ tới nút cuối cùng. Quá trình này sẽ tạo thành vòng ở cả hai hướng.

Tạo Danh sách liên kết vòng từ Danh sách liên kết đôi

Nhìn vào hai hình minh họa trên, bạn cần ghi nhớ:

  • Next của Last Link trỏ tới First Link trong cả hai trường hợp với Danh sách liên kết đơn cũng như Danh sách liên kết đôi.

  • Prev của First Link trỏ tới phần tử cuối của Danh sách liên kết với trường hợp Danh sách liên kết đôi.



Các hoạt động cơ bản trên Danh sách liên kết vòng

Dưới đây là một số hoạt động cơ bản được hỗ trợ bởi Danh sách liên kết vòng:

  • Hoạt động chèn: chèn một phần tử vào vị trí bắt đầu của Danh sách liên kết vòng.

  • Hoạt động xóa: xóa một phần tử của Danh sách liên kết vòng.

  • Hiển thị: hiển thị toàn bộ Danh sách liên kết vòng.


Hoạt động chèn trong Danh sách liên kết vòng

Dưới đây là giải thuật minh họa hoạt động chèn trong danh sách liên kết vòng dựa trên danh sách liên kết đơn.


//Chèn link tại vị trí đầu tiên
void insertFirst(int key, int data) {
   //tạo một link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;
 
   if (isEmpty()) {
      head = link;
      head->next = head;
   }else {
      //trỏ nó tới first node cũ
      link->next = head;
  
      //trỏ first tới first node mới
      head = link;
   }   
   
}


Hoạt động xóa trong Danh sách liên kết vòng

Dưới đây là giải thuật minh họa hoạt động xóa trong Danh sách liên kết vòng dựa trên Danh sách liên kết đơn.


//Xóa phần tử đầu tiên
struct node * deleteFirst() {
   //Lưu tham chiếu tới first link
   struct node *tempLink = head;
 
   if(head->next == head){  
      head = NULL;
      return tempLink;
   }        //Đánh dấu next tới first link là first 
   head = head->next;
 
   //trả về link đã bị xóa
   return tempLink;
}

Hiển thị Danh sách liên kết vòng

Dưới đây là giải thuật minh họa hoạt động hiển thị toàn bộ Danh sách liên kết vòng.


//Hiển thị danh sách liên kết vòng
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
 
   //Bắt đầu từ vị trí đầu tiên
   if(head != NULL) {
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
 
   printf(" ]");
}

Cấu trúc dữ liệu danh sách liên kết đôi (Doubly Linked List)
Cấu trúc dữ liệu ngăn xếp (Stack)

Recent Updates

Sắp Tết 2024 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2024?Java Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelĐịnh hướng văn bản trong ExcelTrang trí văn bản trong Excel

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring
Học Excel | Excel VBA
Học Servlet | JSP | Struts2
Học C | C++ | C#
Học Python
Học SQL

Bài Tập Có Lời Giải

Bài tập Java
Bài tập C
Bài tập C++
Bài tập C#
Bài tập Python
Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java
25 câu hỏi phỏng vấn servlet
75 câu hỏi phỏng vấn jsp
52 câu hỏi phỏng vấn Hibernate
70 câu hỏi phỏng vấn Spring
57 câu hỏi phỏng vấn SQL

Scroll back to top

Copyright © 2016 VietTuts.Vn all rights reserved. | Liên hệ | Chính sách - riêng tư | sitemap.html | sitemap_index.xml