Tuesday, May 19, 2015
1. Khái niệm
Danh sách liên kết là một trong các cấu trúc dữ liệu quan trọng bên cạnh các cấu trúc dữ liệu khác như stack, queue, ... trong C/C++.
Bài toán đặt ra là làm thế nào để quản lý danh sách các bài hát trong một usb khi ta không thể biết trước được chúng có số lượng bao nhiêu, điều này không thể làm được khi ta dùng Array, dưới đây là một vài so sánh giữa Array và Linked-List để bạn đọc hiểu được thế nào là Linked-List:
Array
+ Kích thước mảng cố định, nếu số lượng bài hát nhỏ hơn số lượng phần tử của mảng thì lãng phí bộ nhớ, nếu lớn hơn thì lại thiếu nên không quản lý hết được số bài hát
+ Việc add/remove/sort(sắp xếp)/search ... các bài hát trong mảng là vô cùng khó khăn
Linked List
+ Kích thước Linked-List không cố định, được thay đổi dễ dàng theo thời gian, vì thế có bao nhiêu bài hát thì ta chỉ cần cấp phát bấy nhiêu phần tử trong Linked-List, điều này giúp quản lý tối ưu bộ nhớ
+ Mỗi phần tử được đặc trưng bởi cấu trúc sau:
typedef struct slist{
void * data; /**< the pointer to data */
struct slist * next; /**< the pointer to next element of list */
}slist;
Chính nhờ trường next trong struct này đã tạo ra sợi dây liên kết động giữ các phần tử trong Linked-List
+ Dễ dàng add/remove/sort/search ... các phần tử dựa vào sợi dây liên kết next
2. Các API sử dụng với Linked-List
Các thao tác đối với Linked-List bao gồm các loại cơ bản sau:
+ Add
+ Remove/delete
+ Duyệt danh sách
+ Sort
+ Search
Bạn đọc có thể dùng các API được viết sẵn để dễ dàng sử dụng tại đây. Source code được cung cấp trong 2 file là slist.c và slist.h, muốn sử dụng ở đâu chỉ cần #include "slist.h" là được.
Dưới đây là ví dụ đơn giản mô tả các thao tác trên qua bài toán quản lý danh sách bài hát.
main.c
#include <stdio.h>
#include <string.h>
#include "slist.h"
typedef struct music_item_t{
char *name;
char *path; /* location in storage */
int id; /* 5digit, like karaoke */
}music_item_t;
bool find_by_id(void * cp_data, void * slist_data){
int *cp = (int *)cp_data;
music_item_t *song = (music_item_t *)slist_data;
if(*cp == song->id)
return true;
else
return false;
}
bool find_by_name(void * cp_data, void * slist_data){
char *cpname = (char*)cp_data;
music_item_t *song = (music_item_t *)slist_data;
return !strcmp(cpname, song->name);
}
void release_song_list(void *data){
music_item_t *song = (music_item_t *)data;
free(song->name); //strdup
free(song->path); //strdup
free(song); //malloc
}
void add_song_list(slist **song_list){
slist *music_list = NULL;
music_item_t *tmp = NULL;
tmp = (music_item_t *)malloc(sizeof(music_item_t));
tmp->name = strdup("Mai mai mot tinh yeu");
tmp->path = strdup("/run/media/MYUSB/music/mai-mai-mot-tinh-yeu.mp3");
tmp->id = 00001;
music_list = slist_append(music_list, (void*)tmp);
tmp = (music_item_t *)malloc(sizeof(music_item_t));
tmp->name = strdup("Hay nam chat tay anh nhe");
tmp->path = strdup("/run/media/MYUSB/music/hay-nam-chat-tay-anh-nhe.mp3");
tmp->id = 00002;
music_list = slist_append(music_list, (void*)tmp);
tmp = (music_item_t *)malloc(sizeof(music_item_t));
tmp->name = strdup("Co khi nao roi xa");
tmp->path = strdup("/run/media/MYUSB/music/co-khi-nao-roi-xa.mp3");
tmp->id = 00003;
music_list = slist_append(music_list, (void*)tmp);
*song_list = music_list;
}
int main (void)
{
int length=0;
slist *music_list = NULL; //NOTE: always equas NULL at declare
slist *walk=NULL;
add_song_list(&music_list);
/* LENGTH */
length = slist_size(music_list);
printf("Number of song: %d \n", length);
/* DUYET DANH SACH */
walk = music_list;
while(walk){
printf("song name: %s \n", FORCE_DATA_TYPE(music_item_t, walk)->name);
walk=walk->next;
}
/* FIND THEO ID */
int id = 1;
walk = slist_find(music_list, (void*)&id, find_by_id);
if(walk){
printf("found song id<%d>: %s \n", id, FORCE_DATA_TYPE(music_item_t, walk)->name);
}
/* FIND THEO TEN BAI HAT */
char *name = "Co khi nao roi xa";
walk = slist_find(music_list, (void*)name, find_by_name);
if(walk){
printf("found song name: %s \n", FORCE_DATA_TYPE(music_item_t, walk)->name);
}
/* XOA TAT CA LINKED LIST, LUU Y NHO FREE LUON DATA*/
music_list = slist_delete_all_x(music_list, release_song_list);
/* LENGTH */
length = slist_size(music_list);
printf("Number of song: %d \n", length);
return 0;
}
Compile & Execute:
$ gcc slist.h slist.c main.c
$ ./a.out
Number of song: 3
song name: Mai mai mot tinh yeu
song name: Hay nam chat tay anh nhe
song name: Co khi nao roi xa
found song id<1>: Mai mai mot tinh yeu
found song name: Co khi nao roi xa
Number of song: 0
