Danh sách liên kết đơn

Danh sách liên kết đơn gồm nhiều thành phần động, mỗi thành phần được tổ chức thành 1 node, gồm:
- Thông tin dữ liệu : int, float,... hoặc là kiểu struct do ta tự định nghĩa.
- Nơi chứa địa chỉ của thành phần kế tiếp trong danh sách.

Ví dụ:
struct Node                                           struct Node
{                                                           {
         int Info;                                                 SINHVIEN Info; // SINHVIEN là struct đã định nghĩa
         Node *pNext;                                        Node *pNext;
};                                                           }  

Danh sách liên kết đơn có dữ liệu là kiểu số nguyên

         1. Khởi tạo danh sách:
             Ta cần định nghĩa về Node và List.

typedef int Data                  // Đặt Data là tên gọi khác của kiểu int

struct Node

{

          Data Info;

          Node *pNext;

};

struct List

{

          Node *pHead, *pTail;

};

void Init(List &list)

{

          list.pHead = list.pTail = NULL;

}

          2. Các tác vụ:

Tạo node

Node* GetNode(Data x)

{

           Node *p = new Node;

           if(p)                            // ~ if(p != NULL)

           {

                   p->Info = x;

                   p->pNext = NULL;

            }

            return p;

}

Chèn đầu

void InsertHead(List &list, Data x)

{

            Node *p = GetNode(x);

            if(!p)                           // ~ if(p == NULL)

                    return;

            if(list.pHead == NULL)

                    list.pHead = list.pTail = p;

            else

            {

                    p->pNext = list.pHead;

                    list.pHead = p;

            }

}

Chèn đuôi

void InsertTail(List &list, Data x)

{

             Node *p = GetNode(x);

             if(!p)

                     return;

             if(list.pHead == NULL)

                     list.pHead = list.pTail = p;

             else

             {

                     list.pTail->pNext = p;

                     list.pTail = p;

              }

}

Chèn vào sau 1 node

void InsertAfterNode(List &list, Node *q, Data x)

{

              Node *p = GetNode(x);

              if(!p)

                      return;

              if(q == NULL)

                      InsertHead(list, x);

              else if(q == list.pTail)

                      InsertTail(list, x);

              else

              {

                      p->pNext = q->pNext;

                      q->pNext = q;

              }

}

Tìm kiếm

Node* Search(List &list, Data x)

{

              Node *p = list.pHead;

              while(p)

              {

                       if(p->Info == x)

                                 return p;

                       else

                                 p = p->pNext;

               }

               return NULL; 

}

Xóa node

void DelNode(List &list, Data x)

{

               Node *p = list.pHead, *q = NULL;

               if(p->Info == x)

               {

                       list.pHead = p->pNext;

               }

               else

               {

                       q = p;

                       p =p->pNext;

                       while(p)

                       {

                                  if(p->Info == x)

                                  {

                                             q->pNext = p->pNext;

                                             break;

                                   }

                                   else

                                   {

                                              q = p;

                                              p = p->pNext;

                                    }

                         }

                 if(p == list.pTail)

                 list.pTail = q;

                 }

                 delete p;

}

Sắp xếp

Ta có thể sắp xếp theo nhiều cách khác nhau theo các thuật toán sắp xếp đã biết. Nhưng một trong những cách hiệu quả nhất là QuickSort.

void QuickSort(List &list)

{

             if(list.pHead == list.pTail)

                        return;

             List a, b;

             Node *p = list.pHead, *q = NULL;

             Init(a);

             Init(b);

             list.pHead = p->pNext;

             p->pNext = NULL;

             q = list.pHead;

             while(q)

             {

                          list.pHead = q->pNext;

                          q->pNext = NULL;

                          if(q->Info < p->Info)

                                     InsertTail(a, q->Info);

                          else

                                     InsertTail(b, q->Info);

                          q = list.pHead;

             }

QuickSort(a);

QuickSort(b);

if(a.pHead)

{

              list.pHead = a.pHead;

              a.pTail = p;

}

else

              list.pHead = p;

p->pNext = b.pHead;

if(b.pHead)

              list.pTail = b.pTail;

else

              list.pTail = p;

}