Danh Sách Liên Kết (Linked List) Trong C

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

• Một số khái niệm về Giải thuật
• Giải thuật là gì ?
• Giải thuật tiệm cận - Asymptotic Algorithms
• Giải thuật tham lam - Greedy Algorithms
• Giải thuật chia để trị - Divide and Conquer
• Giải thuật qui hoạch động - Dynamic Programming
• Giải thuật định lý thợ - Master Theorem

• Cấu trúc dữ liệu mảng (Array)
• Cấu trúc dữ liệu mảng (Array)

• Danh sách liên kết - Linked Lists
• Danh sách liên kết - Linked List
• Danh sách liên kết đôi - Doubly Linked List
• Danh sách liên kết vòng - 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ữ liệu hàng đợ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
• Giải thuật Shell Sort
• Sắp xếp nhanh - Quick Sort
• 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 Traversal
• Tìm kiếm theo chiều rộng - Breadth First Traversal

• Cấu trúc dữ liệu cây
• Cấu trúc dữ liệu cây
• Duyệt cây - Tree Traversal
• Cây tìm kiếm nhị phân - Binary Search Tree
• Cây AVL - AVL Tree
• Cây Slay - splay Tree
• Giải thuật Cây khung - Spanning Tree
• Cấu trúc dữ liệu Heap

• Đệ qui (Recursion)
• Khái niệm cơ bản về Đệ qui
• Bài toán Tháp Hà Nội - Tower of Hanoi
• Dãy Fibonacci

• Tài liệu tham khảo
• Học lập trình C
• Học lập trình C++
• Học lập trình Java

Danh sách liên kết (Linked List) trong C Trang trước Trang sau

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.

Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại vietjack.com:

• Giải thuật tiệm cận - Asymptotic Algorithms
• Cấu trúc dữ liệu mảng (Array)
• Danh sách liên kết - Linked List
• Cấu trúc dữ liệu ngăn xếp - Stack
• Cấu trúc dữ liệu hàng đợi - Queue
• Tìm kiếm tuyến tính - Linear Search
• Tìm kiếm nhị phân - Binary Search
• Sắp xếp nổi bọt - Bubble Sort
• Sắp xếp chèn - Insertion Sort

Trang trước Trang sau cau-truc-du-lieu-danh-sach-lien-ket.jsp Bài viết liên quan

• 160 bài học ngữ pháp tiếng Anh hay nhất

• 155 bài học Java tiếng Việt hay nhất

• 100 bài học Android tiếng Việt hay nhất

• 247 bài học CSS tiếng Việt hay nhất

• 197 thẻ HTML cơ bản

• 297 bài học PHP

• 101 bài học C++ hay nhất

• 97 bài tập C++ có giải hay nhất

• 208 bài học Javascript có giải hay nhất

Học cùng VietJack

Trang web chia sẻ nội dung miễn phí dành cho người Việt.

Lớp 1-2-3 Lớp 4 Lớp 5 Lớp 6 Lớp 7 Lớp 8 Lớp 9 Lớp 10 Lớp 11 Lớp 12 Lập trình Tiếng Anh

Chính sách

Chính sách bảo mật

Hình thức thanh toán

Chính sách đổi trả khóa học

Chính sách hủy khóa học

Tuyển dụng

Liên hệ với chúng tôi

Tầng 2, số nhà 541 Vũ Tông Phan, Phường Khương Đình, Quận Thanh Xuân, Thành phố Hà Nội, Việt Nam

Phone: 084 283 45 85

Email: vietjackteam@gmail.com

CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK

Người đại diện: Nguyễn Thanh Tuyền

Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.

2015 © All Rights Reserved.