danh sách liên kết kép

Cấu Trúc Dữ Liệu



Cấu trúc dữ liệu 1 nút
 typedef struct tagDnode
{   Data Info;
  struct tagDnode *pPre;
  struct tagDnode *pNext;
}DNode;


Cấu trúc List kép
Typedef struct tagDList
{  DNode *pHead;
  DNode *pTail;
}DList;
void CreateDList(DList &l)
{
  l.DHead=NULL;
  l.DTail=NULL;
}



Tạo 1 Nút Có Thành Phần Dữ Liệu = X
DNode *CreateDNode(int x)
{ DNode *tam;
 tam=new DNode;
 if(tam==NULL)
 { printf("khong con du bo nho");
  exit(1);
 }
 else
 { tam->Info=x;
  tam->pNext=NULL;
  tam->pPre=NULL;
  return tam;
 }
}


Cài Đặt Thêm 1 Nút Vào Đầu Danh Sách
void AddFirst(DList &l, DNode *tam)
{
 if(l.pHead==NULL)//xau rong
 {
  l.pHead=tam;
  l.pTail=l.pHead;
 }
 else
 {
  tam->pNext=l.pHead;
  l.pHead->pPre=tam;
  l.pHead=tam;
 }
}


Cài Đặt Thêm 1 Nút Vào Cuối Danh Sách
void AddEnd(DList &l,DNode *tam)
{
 if(l.pHead==NULL)
 {
  l.pHead=tam;
  l.pTail=l.pHead;
 }
 else
 {
  tam->pPre=l.pTail;
  l.pTail->pNext=tam;
  tam=l.pTail;
 }
}


Cài Đặt Thêm 1 Nút Vào Sau Nút Q
void AddLastQ(DList &l,DNode *tam, DNode *q)
{
 DNode *p;
 p=q->pNext;
 if(q!=NULL)//them vao duoc  
 {
  tam->pNext=p;
  tam->pPre=q;
  q->pNext=tam;
  if(p!=NULL)
   p->pPre=tam;
  if(q==l.pTail) //them vao sau danh sach lien ket. 
   l.pTail=tam;
 }
 else
  AddFirst(l,tam);
}


Cài Đặt Thêm 1 Nút Vào Trước Nút Q
void AddBeforeQ(DList &l,DNode *tam,DNode *q)
{ DNode *p;
 p=q->pPre;
 if(q!=NULL)
 {
  tam->pNext=q;
  q->pPre=tam;
  tam->pPre=p;
  if(p!=NULL)
   p->pNext=tam;
  if(q==l.pHead)
   l.pHead = tam;
 }
 else
  AddEnd(l,tam);
}


Xoá Phần Tử Đầu Danh Sách
void DeleteFirst(DList &l)
{
 DNode *p;
 if(l.pHead!=NULL)
 {
  p=l.pHead;
  l.pHead=l.pHead->pNext;
  l.pHead->pPre=NULL;
  delete p;
  if(l.pHead==NULL)
   l.pTail=NULL;
 }
}


Xoá 1 Phần Tử Cuối Danh Sách
void DeleteEnd(DList &l )
{
 DNode *p;
 if(l.pHead!=NULL) //tuc xau co hon mot phan tu  
 {
  p=l.pTail;
  l.pTail=l.pTail->Pre;
  l.pTail->pNext=NULL;
  delete p;
  if(l.pTail==NULL)
   l.pHead=NULL;
 }
}


Hủy 1 Nút Sau Nút Q
void DeleteLastQ(DList &l,DNode *q)
{
 DNode *p;//luu node dung sau node q
 if(q!=NULL) 
 {
  p=q->pNext;
  if(p!=NULL)
  {
   q->pNext=p->pNext;
   if(p==l.pTail)//xoa dung nu't cuoi 
    l.pTail=q;
   else //Nut xoa khong phai nut cuoi
    p->pNext->pPre=q;
   delete p;
  }
 }
 else
  DeleteFirst(l);
}


Huỷ 1 Nút Đứng Trước Nút Q
void DeleteBeforeQ(DList &l,DNode *q)
{
 DNode *p;
 if(q!=NULL) //tuc ton tai node q
 {
  p=q->pPre;
  if(p!=NULL)
  {
   q->pPre=p->pPre;
   if(p==l.pHead)//p la Node dau cua danh sach
    l.pHead=q;
   else //p khong phai la node dau
    p->pPre->pNext=q;
   delete p;
  }
 }
 else
  DeleteEnd(l);
}


Xoá 1 Phần Tử Có Khoá = X
int DeleteX(DList &l,int x)
{
 DNode *p;
 DNode *q;
 q=NULL;
 p=l.pHead;
 while(p!=NULL)
 {
  if(p->Info==x)  
   break;
  q=p;//q la Node co truong Info = x
  p=p->pNext;
 }
 if(q==NULL) return 0;//khong tim thay Node nao co truong Info =x
 if(q!=NULL) 
  DeleteLastQ(l,q);  
 else
  DeleteFirst(l);
 return 1;
}


Sắp Xếp
void DoiChoTrucTiep(DList &l)
{ DNode *p,*q;
 p=l.pHead;
 while(p!=l.pTail)
 {
  q=p->pNext;
  while(q!=NULL)
  {
   if(p->Info>q->Info)
    HV(p,q);
   q=q->pNext;
  }
  p=p->pNext;
 }} 

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

Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách
Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần
Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử
Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách.
Cấu trúc dữ liệu của 1 nút trong List đơn
typedef   struct  tagNode 
{ Data    Info;   // Lưu thông tin bản thân
  struct  tagNode  *pNext; //Lưu địa chỉ của Node đứng sau
}Node; 
Cấu trúc dữ liệu của DSLK đơn
typedef   struct  tagList 
{ Node  *pHead;//Lưu địa chỉ Node đầu tiên trong List
  Node  *pTail; //Lưu địa chỉ của Node cuối cùng trong List
}LIST;    // kiểu danh sách liên kết đơn

*các thao tác cơ bản trên danh sách liên kết
Tạo 1 danh sách liên kết đơn rỗng
Tạo 1 nút có trường Infor bằng x
Tìm một phần tử có Info bằng x
Thêm một phần tử có khóa x vào danh sách
Hủy một phần tử trong danh sách
Duyệt danh sách
Sắp xếp danh sách liên kết đơn

*khởi tạo danh ách liên kết
Địa chỉ của nút đầu tiên, địa chỉ của nút cuối cùng đều không có
  void CreateList(List &l) 
  {   
    l.pHead=NULL;
    l.pTail=NULL;
  }
*tạo 1 phần tử mới
Hàm trả về địa chỉ phần tử mới tạo
Node* CreateNode(Data x) // trong bài học là int
{ Node *p;
  p = new Node;//Cấp phát vùng nhớ cho phần tử
  if ( p==NULL)  exit(1); 
  p ->Info = x;   //gán dữa liệu cho nút
  p->pNext = NULL;
  return p; 
   }
*thêm 1 phần tử vào sánh sách liên kết
Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi?
Các vị trí cần thêm 1 phần tử vào List:
+)Thêm vào đầu List đơn
Thêm nút p vào đầu danh sách liên kết đơn
  Bắt đầu:
    Nếu List rỗng thì
      + pHead = p;
      + pTail = pHead;
    Ngược lại
      + p->pNext = pHead;
      + pHead = p
void AddHead(LIST &l, Node* p)
{
    if (l.pHead==NULL) 
    { 
      l.pHead = p; 
      l.pTail = l.pHead; 
    }
    else
    { 
      p->pNext = l.pHead;
        l.pHead = p;  
    }
}

+)Thêm vào cuối List
Ta cần thêm nút p vào cuối list đơn
  Bắt đầu:
    Nếu List rỗng thì
      + pHead = p;
      + pTail = pHead;
    Ngược lại
      + pTail->pNext=p;
      + pTail=p
  void AddTail(LIST &l, Node *p)
  {
    if (l.pHead==NULL)  
    { 
      l.pHead = p; 
      l.pTail = l.pHead; 
    }
    else
    { 
      l.pTail->Next = p;  
        l.pTail = p; 
    }
  }

+)Thêm vào sau 1 phần tử q trong list
Ta cần thêm nút p vào sau nút q trong list đơn
  Bắt đầu:
    Nếu (q!=NULL) thì
      B1: p->pNext = q->pNext
      B2:
    + q->pNext = p
        + nếu q = pTail thì
          pTail=p

  void InsertAfterQ(List &l, Node *p, Node *q)
  {
    if(q!=NULL)
    {
    p->pNext=q->Next;
    q->pNext=p;
    if(l.pTail==q) 
      l.Tail=p;
   }
   else
    AddHead(l,p);// thêm q vào đầu list
}

*hủy phần tử trong sanh sách liên kết
Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy.
Các vị trị cần hủy
Hủy phần tử đứng đầu List
Hủy phần tử có khoá bằng x
Huỷ phần tử đứng sau q trong danh sách liên kết đơn
Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete.
 Bắt đầu:
Nếu (pHead!=NULL) thì
B1: p=pHead
B2:
+ pHead = pHead->pNext
+ delete (p)
B3:
 Nếu pHead==NULL thì pTail=NULL

Hủy được hàm trả về 1, ngược lại hàm trả về 0
  int   RemoveHead(List &l, int &x)
  { Node *p;
    if(l.pHead!=NULL)
    { p=l.pHead; 
      x=p->Info; //lưu Data của nút cần hủy 
      l.pHead=l.pHead->pNext;
      delete p;
      if(l.pHead==NULL)
        l.pTail=NULL;
      return 1;
    }
    return 0;
  }
Hủy phần tử sau phần tử q trong List
Bắt đầu
Nếu (q!=NULL) thì //q tồn tại trong List
B1: p=q->pNext;// p là phần tử cần hủy
B2: Nếu (p!=NULL) thì // q không phải là phần tử cuối
      + q->pNext=p->pNext;// tách p ra khỏi xâu
      + nếu (p== pTail) // nút cần hủy là nút cuối
        pTail=q;
      + delete p;// hủy p
      
  int RemoveAfterQ(List &l, Node *q, int &x)
  { Node *p;
    if(q!=NULL)
    { p=q->pNext; //p là nút cần xoá
      if(p!=NULL) // q không phài là nút cuối
      { if(p==l.pTail) //nút cần xoá là nút cuối cùng 
          l.pTail=q;// cập nhật lạ pTail
        q->pNext=p->pNext; x=p->Info;
        delete p;
      }
      return 1;
    }
    else 
         return 0;  }
Thuật toán hủy phần tử có khoá x
Bước 1:
    Tìm phần tử p có khoá bằng x, và q đứng trước p
Bước 2:
    Nếu (p!=NULL) thì //tìm thấy phần tử có khoá bằng x
      Hủy p ra khỏi List bằng cách hủy phần tử    đứng sau q
    Ngược lại
      Báo không tìm thấy phần tử có khoá
int RemoveX(List &l, int x)
{ Node *p,*q = NULL; p=l.Head;
  while((p!=NULL)&&(p->Info!=x)) //tìm
  { q=p;
    p=p->Next;
  }
  if(p==NULL) //không tìm thấy phần tử có khoá bằng x
    return 0;
  if(q!=NULL)//tìm thấy phần tử có khoá bằng x
    DeleteAfterQ(l,q,x);
  else //phần tử cần xoá nằm đầu List 
    RemoveHead(l,x);
  return 1;
}
Hàm tìm 1 phần tử trong DSLK đơn
  Hàm tìm phần tử có Info = x, hàm trả về địa chỉ của nút có Info = x, ngược lại hàm trả về NULL
Node *Search(LIST l, Data  x) 
{ 
    Node    *p;
    p = l.pHead;
    while((p!= NULL)&&(p->Info != x)) 
      p = p->pNext;
   return p;
}
Duyệt danh sách
Duyệt danh sách là thao tác thường được thực hiện khi có nhu cầu cần xử lý các phần tử trong danh sách như:
Đếm các phần tử trong danh sách
Tìm tất cả các phần tử trong danh sách thảo điều kiện
Hủy toàn bộ danh sách

Bước 1:
p = pHead;// p lưu địa chỉ của phần tử đầu trong List
Bước 2:
Trong khi (danh sách chưa hết) thực hiện
    + xử lý phần tử p
    + p=p->pNext;// qua phần tử kế

  void PrintList(List l)
  {
    Node *p;
    p=l.pHead;
    while(p!=NULL)
    { printf(“%d     ”, p->Info);
      p=p->pNext;
    }
  }
Hủy danh sách liên kết đơn
Bước 1:
Trong khi (danh sách chưa hết) thực hiện
B11:
  p = pHead;
  pHead = pHead->pNext;// cập nhật pHead
B12:
Hủy p
Bước 2:
  pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng

  void RemoveList(List &l)
  { 
    Node *p;
    while(l.pHead!=NULL)//còn phần tử trong List
    {
      p = l.pHead;
      l.pHead = p->pNext;
      delete p;
    }
  } 
Sắp xếp danh sách
Có hai cách tiếp cận
Cách 1: Thay đổi thành phần Info

Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn)
Thay đổi thành phần Info (dữ liệu)
Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng
Nhược:
Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử -> chỉ phù hợp với những xâu có kích thước Info nhỏ
Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị thành phần Info lớn
Làm cho thao tác sắp xếp chậm
Thay đổi thành phần pNext
Ưu:
Kích thước của trường này không thay đổi, do đó không phụ thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút.
Thao tác sắp xếp nhanh
Nhược: Cài đặt phức tạp
void SelectionSort(LIST &l)
{
    Node *p,*q,*min;
    p=l.pHead;
    while(p!=l.pTail)
   {
  min=p;
  q=p->pNext;
  --------------------------------------
  while(q!=NULL)
  { 
  if(q->Info<p->Info)
    min=q;
  q=q->pNext;
  }
  HV(min->Info,p->Info);
  p=p->pNext;
  }
    }

    Các thuật toán sắp xếp hiệu quả trên List
Các thuật toán sắp xếp xâu (List) bằng các thay đổi thành phần pNext (thành phần liên kết) có hiệu quả cao như:
Thuật toán sắp xếp Quick Sort
Thuật toán sắp xếp Merge Sort
Thuật toán sắp xếp Radix Sort

Thuật toán sắp xếp Quick Sort
Bước 1:
Chọn X là phần tử đầu xâu L làm phần tử cầm canh
Loại X ra khỏi L
Bước 2:
Tách xâu L ra làm 2 xâu L1(gồm các phần tử nhỏ hơn hoặc bằng x) và L2 (gồm các phần tử lớn hơn X)
Bước 3: Nếu (L1 !=NULL) thì QuickSort(L1)
Bước 4: Nếu (L2!=NULL) thì QuickSort(L2)
Bước 5: Nối L1, X, L2 lại theo thứ tự ta có xâu L đã được sắp xếp
Sắp xếp L1
Sắp xếp L2
Chọn x=6 cầm canh, và tách L2 thành L21 và L22
void QuickSort(List &l)
{ Node *p,*X;//X lưu địa chỉ của phần tử cầm canh
  List l1,l2;
  if(l.pHead==l.pTail) return;//đã có thứ tự
  CreateList(l1);
  CreateList(l2);
  X=l.pHead;
  l.pHead=X->pNext;
  while(l.pHead!=NULL)//tách L = L1 va L2
  { p=l.pHead;
    l.pHead=p->pNext;
    p->pNext=NULL;
    if(p->Info<=X->Info)
      AddHead(l1,p);
    else
      AddHead(l2,p);
  }
  QuickSort(l1);//Gọi đệ quy sắp xếp L1
  QuickSort(l2);//Gọi đệ quy sắp xếp L2
  if(l1.pHead!=NULL)//nối l1, l2 va X vao l
  {
    l.pHead=l1.pHead;
    l1.pTail->pNext=X;//nối X vào
  }
  else
    l.pHead=X;
  X->pNext=l2.pHead;
  if(l2.pHead!=NULL) //l2 có trên một phần tử
    l.pTail=l2.pTail;
  else  //l2 không có phần tử nào 
    l.pTail=X;
}


Thuật tốn sắp xếp Merge Sort
Bước 1: Phân phối luân phiên từng đường chạy của xâu L vào 2 xâu con L1 và L2.
Bước 2: Nếu L1 != NULL thì Merge Sort (L1).
Bước 3: Nếu L2 != NULL thì Merge Sort (L2).
Bước 4: Trộn L1 và L2 đã sắp xếp lại ta có xâu L                đã được sắp xếp.
Không tốn thêm không gian lưu trữ cho các dãy phụ


Cài đặt hàm main()
Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó thành phần dữ liệu của mỗi nút là 1 số nguyên dương.
Liệt kê tất thành phần dữ liệu của tất cả các nút trong xâu
Tìm 1 phần tử có khoá bằng x trong xâu.
Xoá 1 phần tử đầu xâu
Xoá 1 phần tử có khoá bằng x trong xâu
Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info)
Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu vẫn tăng dần theo trường dữ liệu
..vv
  void main()
  {   LIST  l1; Node *p; int x;
    CreateList(l1);
    do{
      printf(“nhap x=”); scanf(“%d”,&x);
      if(x>0)  
      {   p = CreateNode(x);
        AddHead(l1,x);
      } 
    }while(x>0);
    printf(“Danh sách mới thành lập là\n”);
    PrintList(l1);
    printf(“nhập x cần tìm x=”); scanf(“%d”,&x);
  
    p = Search(l1,x);
    if(p==NULL) printf(“không tìm thấy”);
    else printf(“tìm thấy”); 
    RemoveHead(l1,x);
    printf(“danh sách sau khi xóa\n”);
    PrintList(l1);
    printf(“nhập khoá cần xoá\n”);
    scanf(“%d”,&x);
    RemoveX(l1,x);

    printf(“danh sách sau khi xoá”);
    PrintfList(l1);
    SelectionSort(l1);
    printf(“Danh sách sau khi sắp xếp”);
    PrintfList(l1);
    RemoveList(l1);
}

sắp xếp trộn run sắp xếp ngoại

 Phương pháp trộn Run
Khái niệm cơ bản:
 Run là một dãy liên tiếp các phần tử được sắp thứ tự. Ví dụ 2  4  7  12  50 là một run gồm có 5 phần tử
 Chiều dài run chính là số phần tử trong Run. Chẳng hạn, run trong ví dụ trên có chiều dài là 5.
 7 8 5 3 9 12 4 23 78 90 45 54


Giải thuật: Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau: Input: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự. Gọi f1, f2 là 2 tập tin trộn. Các tập tin f0, f1, f2 có thể là các tập tin tuần tự (text file) hay có thể là các tập tin nhị phân.

 Bước 1:
 - Giả sử các phần tử trên f0 là:  24 12 67 33 58 42 11 34 29 31
 - Khởi tạo f1, f2 rỗng
 - Thực hiện phân bố m=1 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 24 67 58 11 29 f2: 12 33 42 34 31
 Trộn f1, f2 thành f0:
 f0: 12 24 33 67 42 58 11 34 29 31

 Bước 2:
 -Phân bố m=2 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 12 24 42 58 29 31
f0: 12 24 33 67 42 58 11 34 29 31
f2: 33 67 11 34
- Trộn f1, f2 thành f0: f1: 12 24 42 58 29 31 f0: 12 24 33 67 11 34 42 58 29 31 f2: 33 67 11 34

Bước 3: - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau: f1: 12 24 33 67 29 31 f2: 11 34 42 58 - Trộn f1, f2 thành f0: f0: 11 12 24 33 34 42 58 67 29 31

Bước 4: - Phân bố m=8 phần tử lần lượt từ f0 vào f1 và  f2: f1: 11 12 24 33 34 42 58 67 f2: 29 31 - Trộn f1, f2 thành f0: f0: 11 12 24 29 31 33 34 42 58 67

Bước 5: Lặp lại tương tự các bước trên, cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0 thì dừng.

void chia(FILE *a,FILE *b,FILE *c,int p) void main (void) { FILE *a,*b,*c; tao_file(); xuat_file(); p = 1; while (p < n) { chia(a,b,c,p); tron(b,c,a,p); p=2*p; } }

void chia(FILE *a,FILE *b,FILE *c,int p) while (!feof(a)) { /*Chia p phan tu cho b*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(b,"%3d",x); dem++; }

 dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }
 void tron(FILE *b,FILE *c,FILE *a,int p) int stop,x,y,l,r; a=fopen("d:\ctdl\sortfile\bang.int","wb"); b=fopen("d:\ctdl\sortfile\bang1.int","rb"); c=fopen("d:\ctdl\sortfile\bang2.int","rb"); while ((!feof(b)) && (!feof(c))) { l=0;/*so phan tu cua b da ghi len a*/ r=0;/*so phan tu cua c da ghi len a*/ fscanf(b,"%3d",&x); fscanf(c,"%3d",&y); stop=0;

while ((l!=p) && (r!=p) && (!stop)) { if (x<y) { fprintf(a,"%3d",x); l++; if ((l<p) && (!feof(b))) /*chua du p phan tu va chua het file b*/ fscanf(b,"%3d",&x); else { fprintf(a,"%3d",y); r++; if (feof(b)) stop=1; } }

else
{
fprintf(a,"%3d",y); r++; if ((r<p) && (!feof(c))) /*chua du p phan tu va chua het file c*/ fscanf(c,"%3d",&y); else {

fprintf(a,"%3d",x); l++; if (feof(c)) stop=1; } } } //Chep phan con lai cua p phan tu tren b len a
while ((!feof(b)) && (l<p)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); l++; }

//Chep phan con lai cua p phan tu tren c len a while ((!feof(c)) && (r<p)) { fscanf(c,"%3d",&y); fprintf(a,"%3d",y); r++; } } if (!feof(b)) { /*chep phan con lai cua b len a*/ while (!feof(b)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); } }

{
fscanf(c,"%3d",&x); fprintf(a,"%3d",x);
} } fclose(a);  fclose(b);  fclose(c); }

 /*Chia p phan tu cho c*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }

thuật toán sắp xếp radix sort

Radix Sort là một thuật toán tiếp cận theo một hướng hoàn toàn khác.
Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó Radix Sort còn có tên là Postman’s Sort.
Radix Sort không hề quan tâm đến việc so sánh giá trị của phần tử mà bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.
Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, ..., an, giải thuật Radix Sort thực hiện như sau:
Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, ..., an là một số nguyên có tối đa m chữ số.
Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, … tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, ….

Bước 1 :// k cho biết chữ số dùng để phân loại hiện hành
k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục; …
Bước 2 : //Tạo các lô chứa các loại phần tử khác nhau
Khởi tạo 10 lô B0, B1, …, B9 rỗng;
Bước 3 :
For i = 1 .. n do
Đặt ai vào lô Bt với t: chữ số thứ k của ai;
Bước 4 :
Nối B0, B1, …, B9 lại (theo đúng trình tự) thành a.
Bước 5 :
k = k+1;Nếu k < m thì trở lại bước 2. Ngược lại: Dừng

thuật toán merge sort - sắp xếp trộn

Giải thuật Merge sort sắp xếp dãy a1, a2, ..., an dựa trên nhận xét sau:
Mỗi dãy a1, a2, ..., an bất kỳ là một tập hợp các dãy con liên tiếp mà mỗi dãy con đều đã có thứ tự.
Ví dụ: dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 dãy con không giảm (12); (2, 8); (5); (1, 6); (4, 15).
Dãy đã có thứ tự coi như có 1 dãy con.
Hướng tiếp cận: tìm cách làm giảm số dãy con không giảm của dãy ban đầu.
Bước 1 : // Chuẩn bị
k = 1; // k là chiều dài của dãy con trong bước hiện hành
Bước 2 :
Tách dãy a0, a1, ., an-1 thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử:
b = a0, ., ak, a2k, ., a3k, .
c = ak+1, ., a2k+1, a3k+1, .
Bước 3 :
Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.
Bước 4 :
k = k*2;
Nếu k < n thì trở lại bước 2.
Ngược lại: Dừng
Dữ liệu hỗ trợ: 2 mảng b, c:
int  b[MAX], c[MAX], nb, nc;
Các hàm cần cài đặt:
void MergeSort(int a[], int N); : Sắp xếp mảng (a, N) tăng dần
void Distribute(int a[], int N, int &nb, int &nc, int k); Phân phối đều luân phiên các dãy con độ dài k từ mảng a vào hai mảng con b và c
void Merge(int a[], int nb, int nc, int k); : Trộn mảng b và mảng c vào mảng a
void MergeSubarr(int a[], int nb, int nc, int &pa, int &pb, int &pc, int k); : Trộn một cặp dãy con từ b và c vào a


int b[MAX], c[MAX], nb, nc;

void MergeSort(int a[], int N)
{
int k;
for (k = 1; k < N; k *= 2) 
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
void Distribute(int a[], int N, int &nb, int &nc, int k)
{
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
b[pb] = a[pa];
for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
void Merge(int a[],int nb, int nc,int k)
{ int p, pb, pc, ib, ic, kb, kc;
p=pb=pc=0; ib=ic=0;
while((nb>0)&&(nc>0))
{ kb=min(k,nb); kc=min(k,nc);
if(b[pb+ib]<=c[pc+ic])
{ a[p++]=b[pb+ib]; ib++;
if(ib==kb)
{ for(;ic<kc;ic++ a[p++]=c[pc+ic];
pb+=kb; pc+=kc; ib = ic=0;
nb-=kb; nc-=kc;
}
}  
else
{ a[p++]=c[pc+ic]; ic++;
if(ic==kc)
{
for(;ib<kb;ib++) a[p++]=b[pb+ib];
pb+=kb;  pc+=kc; ib = ic=0;
nb-=kb; nc-=kc;
}
}
}
}
int min(int a,int b)
{
if(a>b) return b;
else return a;
}

thuật toán quick sort - sắp xếp nhanh

Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần :

Phần 1: Gồm các phần tử  có giá trị bé hơn x
Phần 2: Gồm các phần tử  có giá trị bằng  x
Phần 3: Gồm các phần tử  có giá trị lớn hơn x
với x là giá trị của một phần tử  tùy ý trong dãy ban đầu.
Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn:
1. ak  ≤ x , với k = 1 .. j
2. ak  = x , với k =  j+1 .. i-1
3. ak   x , với k =  i..N

Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3 chỉ có 1 phần tử  : đã có thứ tự
 khi đó dãy con ban đầu đã được sắp.
Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3  có nhiều hơn 1 phần tử  thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp.
Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …
Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử
Kết thúc; //dãy đã được sắp xếp
Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright
Đoạn 1  x
Đoạn 2: aj+1.. ai-1  = x
Đoạn 3: ai.. aright   x
Bước 3: Sắp xếp đoạn 1: aleft.. aj
Bước 4: Sắp xếp đoạn 3: ai.. aright


Bước 1 : Chọn tùy ý một phần tử  a[k] trong dãy là giá trị mốc ( l ≤ k ≤ r):  
x = a[k];   i = l;  j = r;
Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử
a[i], a[j] nằm sai chỗ :
Bước 2a : Trong khi (a[i]<x) i++;
Bước 2b : Trong khi (a[j]>x) j--;
Bước 2c : Nếu  i< j Swap(a[i],a[j]);
Bước 3 : Nếu  i < j: Lặp lại Bước 2.   Ngược lại: Dừng

void QuickSort(int a[], int left, int right)
{ int i, j, x;
x = a[(left+right)/2]; 
i = left; j = right;
  do
{
    while(a[i] < x) i++;
    while(a[j] > x) j--;
      if(i <= j)
{ 
Swap(a[i],a[j]);
        i++ ; j--;
}
} while(i <= j);

if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}

thuật toán heap sort - sắp xếp vun đống, (cây)

thuật toán heap sort - sắp xếp vun đống, (cây)

Heap Sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng được
Để làm được điều này Heap sort thao tác dựa trên cây.
Ở cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đó phần tử ở nút gốc là phần tử lớn nhất.
Nếu loại bỏ gốc ra khỏi cây, thì việc cập  nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toàn.
Bước kế tiếp có thể sử dụng lại kết quả so sánh của bước hiện tại.
Vì thế độ phức tạp của thuật toán O(nlog2n)
Giai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heap
Giai đoạn 2:  Sắp xếp dãy số dựa trên heap:
Bước 1:Đưa phần tử  lớn  nhất về vị trí đúng ở cuối dãy:             r = n-1;  Swap (a1 , ar );
Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1;        Hiệu chỉnh phần còn lại của dãy từ  a1 , a2 ... ar thành một heap.
Bước 3:
       Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2   Ngược lại : Dừng
Heap: Là một dãy các phần tử  al, al+1 ,... , ar  thoả các quan hệ với mọi i  [l, r]:
ai  a2i+1
ai  a2i+2 // (ai , a2i+1), (ai , a2i+2 ) là các cặp phần tử liên đới
Cho dãy số  : 12   2   8   5  1   6   4  15
Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành Heap
Giai đoạn 2: Sắp xếp dãy số dựa trên Heap

void shift(int a[],int l,int r)
{
int x,i,j;
i=l;
j=2*i+1;
x=a[i];
while(j<=r)
{ if(j<r)
if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1]

j++; //luu chi so cua phan tu nho nhat trong hai phan tu 
if(a[j]<=x) return;
else
{ a[i]=a[j];
a[j]=x;
i=j;
j=2*i+1;
x=a[i];
}
}
}
void CreateHeap(int a[],int n)
{ int l;
l=n/2-1;
while(l>=0)
{
shift(a,l,n-1);
l=l-1;
}
}
void HeapSort(int a[],int n)
{ int r;
CreateHeap(a,n);
r=n-1;
while(r>0)
{
Swap(a[0],a[r]);//a[0] la nút gốc
r--;
if(r>0)
shift(a,0,r);
}
}

thuật toán shell sort - cải tiến của chèn trực tiếp

thuật toán shell sort - cải tiến của chèn trực tiếp

shell sort là Cải tiến của phương pháp chèn trực tiếp
Ý tưởng:
Phân hoạch dãy thành các dãy con
Sắp xếp các dãy con theo phương pháp chèn trực tiếp
Dùng phương pháp chèn trực tiếp sắp xếp lại cả dãy.
Phân chia dãy ban đầu thành những dãy con gồm các phần tử  ở cách nhau h vị trí
Dãy ban đầu : a1, a2, ..., an được xem như sự xen kẽ của các dãy con sau :
Dãy con thứ nhất : a1 ah+1 a2h+1 ...
Dãy con thứ  hai  : a2 ah+2 a2h+2 ...
....
Dãy con thứ  h     : ah a2h a3h ...
Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử  được đưa về vị trí đúng tương đối
Giảm khoảng cách h để tạo thành các dãy con mới
Dừng khi h=1
Giả sử quyết định sắp xếp k bước, các khoảng cách  chọn phải thỏa điều kiện :
hi  > hi+1  và hk = 1
 hi  = (hi-1  - 1)/3 và hk = 1, k = log3n-1
Ví dụ :127, 40, 13, 4, 1
 hi  = (hi-1 - 1)/2 và hk = 1, k = log2n-1
Ví dụ : 15, 7, 3, 1
h có dạng 3i+1: 364, 121, 40, 13, 4, 1
Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1
h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1.
Bước 1: Chọn k khoảng cách h[1], h[2], ..., h[k];
i = 1;
Bước 2: Phân chia dãy ban đầu thành các dãy con   cách nhau h[i] khoảng cách.
Sắp xếp từng dãy con bằng phương pháp   chèn trực tiếp;
Bước 3 : i = i+1;            Nếu  i > k : Dừng            Ngược lại : Lặp lại Bước 2.    
Cho dãy số a:
12   2 8 5 1 6 4 15

Giả sử chọn các khoảng cách là 5, 3, 1

void ShellSort(int a[],int n, int h[], int k)
{ int step,i,j, x,len;
for (step = 0 ; step <k; step++)
{ len = h[step];
for (i = len; i<n; i++)
{
x = a[i]; 
j = i-len; // a[j] đứng kề trước a[i] trong cùng dãy con 
while ((x<a[j])&&(j>=0)// sắp xếp dãy con chứa  x 
{ // bằng phương pháp chèn trực tiếp 
a[j+len]  = a[j];
j = j - len;
}
a[j+len] = x;
}
}
}

thuật toán binary insertion sort - chèn nhị phân

thuật toán binary insertion sort - chèn nhị phân

void BInsertionSort(int a[],int n )
{
int l,r,m,i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<n ; i++)
{
x = a[i]; l = 0;
r = i-1;
while(l<=r) // tìm vị trí chèn x
{
m = (l+r)/2;
// tìm vị trí thích hợp m
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy }
}

thuật toán insertion sort - chèn trực tiếp

thuật toán insertion sort - chèn trực tiếp

Giả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự.
Tìm cách chèn phần tử  ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a0 , a1,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i).

Bước 1:  i = 1; //giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3: Dời chỗ các phần tử  từ a[pos] đến a[i-1]   sang phải 1 vị trí để dành chổ cho a[i]
Bước 4: a[pos] = x; //có đoạn a[1]..a[i]  đã được sắp
Bước 5: i = i+1;
Nếu  i < n : Lặp lại Bước 2
Ngược lại  : Dừng

void InsertionSort(int d, int n 
{ int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(i=1 ; i<n ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x; // chèn x vào dãy
}
}

sắp xếp từ điển trong lập trình C++ - bài tập đồ án CTDL & GT

sắp xếp từ điển trong lạp trình C++ - bài tập đồ án CTDL & GT

sắp xếp từ điển trong lập trình c/c++,tạo 1 mảng 1 chiều chứa các từ tiếng anh lấy từ file http://blackberryvietnam.net/threads/du-lieu-tu-dien-cho-ung-dung-ddict.897/ . sau đó dùng các thuật toán sắp xếp để sắp xếp mảng trên theo thứ tự và so sánh thời gian thực hiện các thuật toán.
lưu ý:để thuận tiện việc thao tác, chỉ lấy các từ đơn dưới 15 kí tự, các từ tiếng anh được tách ra từ dữ liệu từ điển việt-anh. (không phải từ điển anh-việt).
trong code dưới đây, dữ liệu nguồn là file va.dd, danh sách các từ tiếng anh lọc ra được và sắp xếp được đưa vào file av.dd.
*đây là bài tập đồ án của thầy Toàn UIT, dưới đây chỉ là các code sắp xếp, phần main() thì các bạn chỉnh sửa lại cho phù hợp với yêu cầu của đồ án, phần main() là ý kiến sáng tạo để hoàn thành bài tập, tôi chỉ viết đơn giản như vậy để chạy thử xem code sắp xếp có chạy đúng hay không thôi.

#include<iostream>
#include<time.h>
using namespace std;

void bang(char *a,char *b);
void doi(char *a,char *b);

//các thuật toán sắp xếp
void interchange(char s[][15],int k);
void select(char s[][15],int n);
void bubble(char s[][15],int n);
void insert(char s[][15],int n);
void insertbinary(char s3[][15],int k);
void shacker(char s[][15],int n);
void shell(char s[][15],int n);
void quick(char s[][15],int l,int r);
void heap(char s[][15],int n);
void merge(char a[][15],int n);

void main()
{
//lấy các từ tiếng anh đưa vào chuỗi s3
FILE *t,*t1;
char s[300];
char *s1,*s2,s3[50000][15];
t = fopen("E:\\va.dd","r");
t1=fopen("E:\\av.dd","w+");
while(fgets(s,300,t)!=NULL)
{
s1=strstr(s,"##");
if(s1!=NULL)
{
s2=strstr(s1,"|-");
if(s2!=NULL && strlen(s2)<15) fputs(s2+2,t1);
}
}
rewind(t1);
int k=0;
while(fgets(s,15,t1)!=NULL)
{
strcpy(s3[k],s);
k++;
}
int n=k;  
//sắp xếp
cout<<"\ndang sap xep...";
double tg;
double a=clock();
shell(s3,k);//kiểu sắp xếp. thay bằng các kiểu sắp xếp khác nhau để so sanh thời gian
//đang dùng shell sort..
double b=clock();
cout<<"\nda xep xong!\nthoi gian sap xep la: "<<(b-a)/1000<<" giay.";

rewind(t1);
for(int i=0;i<k;i++) fputs(s3[i],t1);
fcloseall();
system("pause"); 
}
void chinh(char s[][15],int l,int r)
{
int j=2*l+1;
while(j<=r)
{
if(j<r && stricmp(s[j],s[j+1])<0) j++;
if(stricmp(s[l],s[j])>=0) return;
else
{
doi(s[l],s[j]);
l=j;
j=2*l+1;
}
}
}
void taoheap(char s[][15],int n)
{
int l=n/2-1;
while(l>=0)
{
chinh(s,l,n-1);
l--;
}
}
void heap(char s[][15],int n)
{
int r=n-1;
taoheap(s,n);
while(r>0)
{
doi(s[0],s[r]);
r--;
if(r>0) chinh(s,0,r);
}
}
void quick(char s[][15],int l,int r)
{
int i=l,j=r,m=(l+r)/2;
while(i<=j)
{
while(stricmp(s[i],s[m])<0) i++;
while(stricmp(s[j],s[m])>0) j--;
if(i<=j)
{
doi(s[i],s[j]);
i++;j--;
}
}
if(i<r) quick(s,i,r);
if(j>l) quick(s,l,j);
}
void shacker(char s[][15],int n)
{
int l=0,r=n-1,k=n-1,i;
while(l<r)
{
for(i=r;i>l;i--)
if(stricmp(s[i],s[i-1])<0){ doi(s[i],s[i-1]);k=i;}
l=k;
for(i=l;i<r;i++)
if(stricmp(s[i],s[i+1])>0){doi(s[i],s[i+1]);k=i;}
r=k;
}
}
void bubble(char s[][15],int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(stricmp(s[j],s[j-1])<0) doi(s[j],s[j-1]);
}
void insert(char s[][15],int n)
{
for(int i=1;i<n;i++)
{
char x[15];
bang(x,s[i]);
int j=i-1;
while(stricmp(s[j],x)>0 && j>=0)
{
bang(s[j+1],s[j]);
j--;
}
bang(s[j+1],x);
}
}
void interchange(char s[][15],int k)
{
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++)
if(stricmp(s[i],s[j])>0) doi(s[i],s[j]);
}
void select(char s[][15],int n)
{
int dem=0;
for(int i=0;i<n-1;i++)
{
int m=i;
for(int j=i+1;j<n;j++)
if(stricmp(s[m],s[j])>0) m=j;
doi(s[i],s[m]);
}
}
void shell(char s[][15],int n)
{
int h[10]={10129,1678,437,256,134,62,5,3,2,1},k=10;
int i,j,len,step;
char x[15];
for(step=0;step<k;step++)
{
len=h[step];
for(i=len;i<n;i++)
{
bang(x,s[i]);
j=i-len;
while(j>=0 && stricmp(s[j],x)>0)
{
bang(s[j+len],s[j]);
j=j-len;
}
bang(s[j+len],x);
}
}
}
void insertbinary(char s3[][15],int k)
{
//sắp xếp chèn nhị phân
int l,r,m,i,j,dem=0;
char x[15];
for(i=1;i<k;i++)
{
l=0;r=i-1;
for(j=0;j<strlen(s3[i]);j++) x[j]=s3[i][j];x[j]='\0';
while(l<=r)
{
m=(l+r)/2;
if(stricmp(x,s3[m])<0) r=m-1;
else l=m+1;
}
for(j=i;j>l;j--) bang(s3[j],s3[j-1]);
bang(s3[l],x);
}
}
void bang(char *a,char *b)//phép gán
{
int i;
for(i=0;i<strlen(b);i++) a[i]=b[i];
a[i]='\0';
}
void doi(char *a,char *b)//hoán đổi vị trí
{
int i;
char c[300];
for(i=0;i<strlen(a);i++) c[i]=a[i];c[i]='\0';
for(i=0;i<strlen(b);i++) a[i]=b[i];a[i]='\0';
for(i=0;i<strlen(c);i++) b[i]=c[i];b[i]='\0';

}
void phanphoi(char a[][15],int n,char b[][15],int &nb,char c[][15],int &nc,int k)
{
int pa,pb,pc,i;
pa=pb=pc=0;
while(pa<n)
{
i=0;
while(i<k && pa<n)
{
bang(b[pb++],a[pa++]);
i++;
}
i=0;
while(i<k && pa<n)
{
bang(c[pc++],a[pa++]);
i++;
}
}
nb=pb;nc=pc;
}
int min(int a,int b)
{
if(a<b) return a;
return b;
}
void tron(char a[][15],int n,char b[][15],int nb,char c[][15],int nc,int k)
{
int pa,pb,pc,kb,kc,ib,ic;
pa=pb=pc=ib=ic=0;
while(nb>0 && nc>0)
{
kb=min(k,nb);
kc=min(k,nc);
if(stricmp(b[pb+ib],c[pc+ic])<=0)
{
bang(a[pa++],b[pb+ib]);
ib++;
if(ib==kb)
{
while(ic<kc)
{
bang(a[pa++],c[pc+ic]);
ic++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
else
{
bang(a[pa++],c[pc+ic]);
ic++;
if(ic==kc)
{
while(ib<kb)
{
bang(a[pa++],b[pb+ib]);
ib++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
}
}
void merge(char a[][15],int n)
{
char (*b)[15]=new char[50000][15];
char (*c)[15]=new char[50000][15];
int nb,nc,k=1;
while(k<n)
{
phanphoi(a,n,b,nb,c,nc,k);
tron(a,n,b,nb,c,nc,k);
k*=2;
}
delete [](*b);
delete [](*c);

}


file sắp xếp từ điển

//tác giả code: Trần Khánh Toàn - ĐH CNTT