Cấu trúc dữ liệu: Danh sách liên kết (ver 2.0) - Full Code

- Hàm Reverse không sử dụng danh sách trung gian L2 (xem bài cũ Danh sách Liên kết - Full Code để thấy sự khác biệt giữa 2 cách viết hàm)
- Hàm Distinct để xóa bỏ những phần tử trùng trong danh sách

#include <stdio.h>
#include <malloc.h>
typedef int ElementType;
typedef struct Node{
    ElementType Element;
    Node* Next;
};
typedef Node* Position;
typedef Position List;

void MakeNullList(List &L){
    L =(Node*)malloc(sizeof(Node));
    L->Next = NULL;
}
int EmptyList(List L){
    return (L->Next==NULL);
}
Position i2p(int i, List L){
    Position P = L;
    for(int k=1;k<i;k++)
        P=P->Next;
    return P;
}
void InsertList(ElementType X, Position P, List &L){
    Node* T = (Node*)malloc(sizeof(Node));
    T->Element = X;
    T->Next = P->Next;
    P->Next = T;
}
void InsertList(ElementType X, int P, List &L){
    InsertList(X,i2p(P,L),L);
}

void PrintList(List L){
    Position P = L;
    while(P->Next!=NULL){
        printf("%d ",P->Next->Element);
        P=P->Next;
    }
    printf("\n");
}

void DeleteList(Position P, List &L){
    if (L->Next!=NULL){
        Position T=P->Next;
        P->Next = T->Next;
        free (T);
    }
}
void DeleteList(int p, List &L){
   // DeleteList(i2p(P,L),L);
   if (L->Next!=NULL){
        Position P = i2p(p,L);
        Position T=P->Next;
        P->Next = T->Next;
        free (T);
    }
}

ElementType Retrieve(int P, List L){
    //Retrieve(i2p(P,L),L);
    return i2p(P,L)->Next->Element;
}
int Count(List L){
    int i=0;
    for(Position P=L;P->Next!=NULL;P=P->Next)
        i++;
    return i;
}

int Locate(ElementType X, List L){
   Position P = L;
   int i = 1;
   while (P->Next!=NULL){
        if (P->Next->Element==X)
            return i;
        P=P->Next;
        i=i+1;
   }
   return i;
}
void ReverseList(List &L){
    int i=1;
    int j=Count(L);
    while (i<j){
        Position left = i2p(i,L);
        Position right = i2p(j,L);
        ElementType t = left->Next->Element;
        left->Next->Element = right->Next->Element;
        right->Next->Element = t;
        i++;
        j--;
    }
}
void SortList (List &L){
    for(Position P = L;P->Next!=NULL;P=P->Next){
        ElementType min = P->Next->Element;
        Position curMin = P;
        for(Position Q =P->Next;Q->Next!=NULL;Q=Q->Next){
            if (Q->Next->Element < min){
                min = Q->Next->Element;
                curMin = Q;
            }
        }
        curMin->Next->Element=P->Next->Element;
        P->Next->Element = min;
    }
}
//xoa phan tu trung trong danh sach
void Distinct(List &L){
    for(int i=1;i<=Count(L)-1;i++){
     ElementType X = i2p(i,L)->Next->Element;
     for(int j=i+1;j<=Count(L);){
      ElementType Y = i2p(j,L)->Next->Element;
      if (X==Y)
       DeleteList(j,L);
      else
       j++;
     }
    }
}
int main(){
    List L;
    MakeNullList(L);
    InsertList(3,1,L);
    InsertList(4,1,L);
    InsertList(2,2,L);
    InsertList(5,3,L);
    InsertList(6,2,L);
    InsertList(7,6,L);
    InsertList(8,5,L);
    InsertList(3,2,L);
    InsertList(8,3,L);
    InsertList(1,8,L);
    InsertList(7,1,L);

    PrintList(L);
    Distinct(L);
    printf("Danh sach sau khi xoa bo phan tu trung:\n");
    PrintList(L);
    printf("Danh sach sau khi xoa 2 phan tu tai vi tri 2 va 5:\n");
    DeleteList(2,L);
    DeleteList(5,L);
    PrintList(L);
    printf("Retrieve(3,L) = %d\n",Retrieve(3,L));
    printf("Locate(100,L) = %d\n",Locate(100,L));
    ReverseList(L);
    printf("Danh sach dao:\n");
    PrintList(L);
    SortList(L);
    printf("Danh sach sau khi sap xep:\n");
    PrintList(L);
    return 0;
}