Danh sách liên kết dùng cấp phát bộ nhớ động, co giãn tương ứng. Được định nghĩa là tập hợp các nút. Nút có hai phần: dữ liệu và liên kết. Biểu diễn dữ liệu, liên kết và danh sách liên kết:
Các loại danh sách liên kết
Có 4 loại:
- Đơn / Danh sách liên kết đơn
- Đôi / Danh sách liên kết đôi
- Danh sách liên kết đơn vòng
- Danh sách liên kết đôi vòng
Logic tìm độ dài danh sách liên kết bằng đệ quy:
int length(node *temp){
if(temp == NULL)
return l;
else{
l = l + 1;
length(temp->next);
}
}
Chương trình
Chương trình C tìm độ dài danh sách liên kết:
#include <stdio.h>
#include <stdlib.h>
typedef struct linklist{
int data;
struct linklist *next;
} node;
int l = 0;
int main(){
node *head = NULL, *temp, *temp1;
int len, choice, count = 0, key;
do{
temp = (node *)malloc(sizeof(node));
if(temp != NULL){
printf("\nNhap phan tu vao danh sach: ");
scanf("%d", &temp->data);
temp->next = NULL;
if(head == NULL){
head = temp;
}else{
temp1 = head;
while(temp1->next != NULL){
temp1 = temp1->next;
}
temp1->next = temp;
}
}else{
printf("\nBo nho day");
}
printf("\nNhap 1 de tiep tuc them: ");
scanf("%d", &choice);
}while(choice == 1);
len = length(head);
printf("Danh sach co %d nut", l);
return 0;
}
// Ham de quy tim do dai
int length(node *temp){
if(temp == NULL)
return l;
else{
l = l + 1;
length(temp->next);
}
}
Đầu ra
Kết quả chạy chương trình:
Lan 1: Nhap phan tu: 3 Tiep tuc? 1 Nhap phan tu: 56 Tiep tuc? 1 Nhap phan tu: 56 Tiep tuc? 0 Danh sach co 3 nut Lan 2: Nhap phan tu: 12 Tiep tuc? 1 Nhap phan tu: 45 Tiep tuc? 0 Danh sach co 2 nut