[C căn bản] Danh sách liên kết - Linked List

Danh sách liên kết là một cấu trúc dữ liệu linh hoạt, có thể dễ dàng thay đổi kích thước cũng như phần tử bên trong nó. Hiểu một cách đơn giản là một con trỏ trỏ tới một nút dữ liệu (Node).

Cấu trúc của một phần tử trong danh sách liên kết bao gồm hai phần:

+ Thành phần dữ liệu(Data): Lưu trữ dữ liệu của bản thân phần tử, có thể là các kiểu dữ liệu đơn như int, char hay cấu trúc như struct.
+ Thành phần liên kết(Next): Con trỏ lưu trữ địa chỉ phần tử kế tiếp.

Cấu trúc của một danh sách liên kết (đơn): 

Các Node dữ liệu được móc nối với nhau thông qua con trỏ, phần tử đứng trước trỏ tới phần tử đứng sau nó, phần tử cuối cùng sẽ trỏ tới NULL.

Các phần tử của danh sách liên kết không được lưu liên tiếp với nhau trong bộ nhớ lên không thể truy xuất một cách ngẫu nhiên. Khi muốn tìm một phần tử trong danh sách ta phải duyệt tuần tự từng phần tử từ đầu tiền cho tới vị trí cần tìm kiếm.

Cài đặt danh sách liên kết:

 

struct Sinhvien {char hoTen[50]){ //Định nghĩa phần tử là một struct
   char hoTen[50]
   char lop[10];
   int tuoi;
};
typedef struct Sinhvien SV;

Xây dựng một Node trong danh sách:

struct node { 
    SV sv; //Thành phần dữ liệu sv có kiểu Sinhvien
    struct node *pNext; //Con trỏ pNext trỏ đến node kế tiếp
};
typedef struct node NODE;

struct list {
   NODE *pHead, *pTail; //Hai con trỏ kiểu node dùng để trỏ đến đầu và cuối danh sách
}
typedef struct list LIST;

Khởi tạo danh sách:

void Init(LIST *lt) {
   lt->pHead = lt->pTail = NULL; //Cho hai con trỏ đầu và cuối trỏ đến ô nhớ trống
}

Kiểm tra danh sách rỗng hay không

int isEmpty(LIST lt) {
   if(!lt.pHead )
      return 1;
   return 0;
}

Khởi tạo một node trong danh sách:

NODE *newNode(NODE *pNode, SV sv) {
   pNode = (NODE*)malloc(sizeof(NODE)); //Cấp phát bộ nhớ động cho pNode
   if(!pNode) {
      printf("Cap phat bo nho that bai!");
      return NULL;
   }
   pNode->pNext = NULL; //Cho pNext của pNode trỏ tới ô nhớ trống
   strcpy(pNode->sv.hoTen, sv.hoTen);//--------------------
   strcpy(pNode->sv.lop, sv.lop);//---Ghi dữ liệu vào node
   pNode->sv.tuoi = sv.tuoi;//-----------------------------
   return pNode; //Trả về con trỏ pNode
}

Chèn node vào vị trí đầu tiên trong danh sách:

void addHead(LIST *lt, NODE *pNode) {
   if(lt->pHead == NULL) //Nếu danh sách rỗng thì node đầu bằng node cuối bằng pNode
      lt->pHead = lt->pTail = pNode;
   else {
      pNode->pNext = lt->pHead;//Trỏ tới node đầu của danh sách
      lt->pHead = pNode;//Gán địa chỉ node đầu là node vừa thêm
   }
}

Chèn node vào vị trí cuối cùng trong danh sách:

void addTail(LIST *lt, NODE *pNode) {
   if(lt->pHead == NULL)
      lt->pHead = lt->pTail = pNode;
   else {
      lt-pTail = pNode;//Gán địa chỉ node cuối là node vừa thêm
      pNode->pNext = NULL;//node cuối trỏ tới NULL
   }
}

Nhập dữ liệu vào node:

void input(LIST *lt, int k) {
    Init(lt);
    SV sv[k];
    NODE *pNode;
    int i;
    for(i = 0; i < k; i++) {
        printf("Nhap ho ten sinh vien: ");
        fflush(stdin);
        fgets(sv[i].hoTen, 30, stdin);
        sv[i].hoTen[strlen(sv[i].hoTen)-1] = '\0';
        printf("Lop: ");
        fflush(stdin);
        fgets(sv[i].lop, 10, stdin);
        sv[i].lop[strlen(sv[i].lop)-1] = '\0';
        printf("Tuoi: ");
        scanf("%d", &sv[i].tuoi);
        pNode = makeNode(pNode, sv[i]);
        insertHead(lt, pNode);
    }
}

Với Linux hàm fflush sẽ không hoạt động, khi đó ta phải thay thế bằng hàm __fpurge() Xem thêm...

 Xuất dữ liệu ra màn hình:

void output(LIST lt) {
    NODE *pNode;
    if(isListEmpty(lt))
        printf("Danh sach rong!\n");
    else {
        pNode = lt.pHead;
        while(pNode) {
            printf("Ten sinh vien: ");
            puts(pNode->sv.hoTen);
            printf("Tuoi: %d", pNode->sv.tuoi);
            printf("\nLop: ");
            puts(pNode->sv.lop);
            pNode = pNode->pNext;
        }
    }
}