Cấu trúc dữ liệu: Cây tổng quát với kiểu dữ liệu dạng chuỗi ký tự

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
#define MaxLength 10
#define NIL -1

typedef string DataType;
typedef int Node;
typedef struct Tree{
    DataType Data[MaxLength];
    Node Parent[MaxLength];
    int MaxNode;
};

void MakeNullTree(Tree &T){
    T.MaxNode = 0;
}
int EmptyTree(Tree T){
    return T.MaxNode == 0;
}

DataType LabelNode(Node i,Tree T){
    return T.Data[i];
}

Node Parent(Node i,Tree T){
    return T.Parent[i];
}
void PrintTree(Tree T){
    for(int i=0;i<T.MaxNode;i++){
        cout<<"Node "<<i<<": ";
        cout<<"P("<<i<<",T) = "<<Parent(i,T)<<" - ";
        cout<<"L("<<i<<",T) = "<<LabelNode(i,T)<<endl;


    }
}
Node LeftMostChild(Node i, Tree T){
    for(Node j=i+1;j<T.MaxNode;j++){
        if (Parent(j,T)==i)
            return j;
    }
    return NIL;
}

Node RightSibling(Node i, Tree T){
    Node p = Parent(i,T);
    for (Node j=i+1;j<T.MaxNode;j++){
        if (p==Parent(j,T))
            return j;
    }
    return NIL;
}
void PrintChilds(Node i, Tree T){
    Node lmc = LeftMostChild(i,T);
    if (lmc == NIL)
        cout<<"Node "<<i<<" khong co con!!";
    else
    {
        cout<<"Danh sach con cua nut "<<i<<endl;
        cout<<lmc<<"  ";
        Node rs = RightSibling(lmc,T);
        while(rs!=NIL){
            cout<<rs<<"  ";
            rs = RightSibling(rs,T);
        }
    }
}
void PreOrder(Node n,Tree T){
    cout<<LabelNode(n,T)<<"  ";
    Node i = LeftMostChild(n,T);
    while(i!=NIL){
        PreOrder(i,T);
        i=RightSibling(i,T);
    }

}
void InOrder(Node n,Tree T){
    Node i = LeftMostChild(n,T);
    if (i!=NIL)
        InOrder(i,T);
    cout<<LabelNode(n,T)<<"  ";
    i = RightSibling(i,T);
    while(i!=NIL){
        InOrder(i,T);
        i = RightSibling(i,T);
    }
}

void PostOrder(Node n,Tree T){
    Node i = LeftMostChild(n,T);
    while(i!=NIL){
        PostOrder(i,T);
        i = RightSibling(i,T);
    }
    cout<<LabelNode(n,T)<<"  ";

}

bool IsPath(Node A, Node B, Tree T){
    Node pB = Parent(B,T);
    if (pB == A || A == B)
        return true;
    else if (pB == NIL)
        return false;
    else
        return IsPath(A,pB,T);
}
int Path(Node A, Node B, Tree T){
    if (!IsPath(A,B,T) || A == B)
        return 0;
    else
        return 1 + Path(A,Parent(B,T),T);
}
bool IsLeaf(Node n, Tree T){
    return LeftMostChild(n,T)==NIL;
}
bool IsAncestor(Node A, Node B, Tree T){
   return IsPath(A,B,T);
}
bool IsDescendant(Node A,Node B, Tree T){
    return IsAncestor(B,A,T);
}
int Height(Node n, Tree T){
    int max = 0;
    for(Node i=n+1;i<T.MaxNode;i++){
        if (IsLeaf(i,T) && IsDescendant(i,n,T))
        {
            int p = Path(n,i,T);
            if (p>max)
                max = p;
        }
    }
    return max;
}
int Depth(Node n, Tree T){
    return Path(0,n,T);
}
Node CommonAncestor(Node A, Node B, Tree T){
    if (A == Parent(B,T))
        return A;
    else if (B == Parent(A,T))
        return B;
    else if (Parent(A,T)==Parent(B,T))
        return Parent(A,T);
    int da = Depth(A,T);
    int db = Depth(B,T);

    if (da>db)
        return CommonAncestor(Parent(A,T),B,T);
    else if (da<db)
        return  CommonAncestor(A,Parent(B,T),T);
    else
        return  CommonAncestor(Parent(A,T),Parent(B,T),T);
}
int main(){
    Tree T;
    MakeNullTree(T);
    string data[10]={"can tho","ninh kieu","ca mau","lam dong","kien giang","hau giang","an giang","soc trang","bac lieu","tra vinh"};
    for(int i=0;i<10;i++)
        T.Data[i]=data[i];
    T.Parent={-1,0,0,1,1,4,4,4,2,2};
    T.MaxNode=10;
    PrintTree(T);
    if (EmptyTree(T))
        cout<<"Cay rong!";
    cout<<"LeftMostChild(8,T) = "<<LeftMostChild(8,T)<<endl;
    cout<<"RightSibling(5,T) = "<<RightSibling(5,T)<<endl;
    PrintChilds(3,T);
    printf("\nDuyet tien tu:\n");
    PreOrder(0,T);
    printf("\nDuyet trung tu:\n");
    InOrder(0,T);
    printf("\nDuyet hau tu:\n");
    PostOrder(0,T);
    cout<<"\nisPath(2,5,T) = "<<IsPath(2,5,T);
    cout<<"\nisPath(1,1,T) = "<<IsPath(1,1,T);
    cout<<"\nisAncestor(1,7,T) = "<<IsAncestor(1,7,T);
    cout<<"\nisAncestor(2,4,T) = "<<IsAncestor(2,4,T);
    cout<<"\nisAncestor(4,2,T) = "<<IsAncestor(4,2,T);
    cout<<"\nisAncestor(0,0,T) = "<<IsAncestor(0,0,T);
    cout<<"\nisDescendant(7,1,T) = "<<IsDescendant(7,1,T);
    cout<<"\nisDescendant(4,2,T) = "<<IsDescendant(4,2,T);
    cout<<"\nisDescendant(5,5,T) = "<<IsDescendant(5,5,T);
    cout<<"\nPath(1,7,T) = "<<Path(1,7,T);
    cout<<"\nHeight(0,T) = "<<Height(0,T);
    cout<<"\nDepth(0,T) = "<<Depth(0,T);
    cout<<"\nDepth(4,T) = "<<Depth(4,T);

    cout<<"\nCommonAncestor(2,8,T) = "<<CommonAncestor(2,8,T);
    cout<<"\nCommonAncestor(8,2,T) = "<<CommonAncestor(8,2,T);
    cout<<"\nCommonAncestor(9,2,T) = "<<CommonAncestor(9,2,T);
    cout<<"\nCommonAncestor(5,8,T) = "<<CommonAncestor(5,8,T);
    cout<<"\nCommonAncestor(8,5,T) = "<<CommonAncestor(8,5,T);
    cout<<"\nCommonAncestor(3,7,T) = "<<CommonAncestor(3,7,T);

    return 0;
}

Cấu trúc dữ liệu: Cây nhị phân

#include <stdio.h>
#include <malloc.h>
typedef int DataType;
typedef struct Node{
    DataType Data;
    Node* Left;
    Node* Right;
};

typedef Node* Tree;

void MakeNullTree(Tree &T){
    T=NULL;
}
int EmptyTree(Tree T){
    return T==NULL;
}

Tree Create2(DataType V,Tree Left,Tree Right){
    Tree T = (Node*)malloc(sizeof(Node));
    T->Data = V;
    T->Left = Left;
    T->Right = Right;
    return T;
}
void PreOrder(Tree T){
    if (T!=NULL){
        printf("%d  ",T->Data);
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
}
void InOrder(Tree T){
    if (T!=NULL){
        InOrder(T->Left);
        printf("%d  ",T->Data);
        InOrder(T->Right);
    }
}

void PostOrder(Tree T){
    if(T!=NULL){
        PostOrder(T->Left);
        PostOrder(T->Right);
        printf("%d  ",T->Data);
    }
}
int  IsLeaf(Tree T){
    return (T->Left==NULL && T->Right==NULL);
}
//dem so nut tren cay
int NbNodes(Tree T){
    if (T==NULL)
        return 0;
    else
        return 1+NbNodes(T->Left)+NbNodes(T->Right);
}
//dem so nut la tren cay
int NbLeaves(Tree T){
    if (T==NULL)
        return 0;
    else if (IsLeaf(T))
        return 1;
    else
        return NbLeaves(T->Left)+NbLeaves(T->Right);
}
int max (int a,int b){
    return (a>b)?a:b;
}
int Height(Tree T){
    if (T==NULL || IsLeaf(T))
        return 0;
    else
        return 1+max(Height(T->Left),Height(T->Right));
}
int main(){
    Tree T1=Create2(1,NULL,NULL);
    Tree T2=Create2(2,NULL,NULL);
    Tree T5=Create2(5,NULL,NULL);
    Tree T3=Create2(3,NULL,NULL);
    Tree T8=Create2(8,NULL,T2);
    Tree T12=Create2(12,T1,NULL);
    Tree T7=Create2(7,T5,T8);
    Tree T6=Create2(6,T3,T12);
    Tree T = Create2(9,T7,T6);
    printf("Duyet tien tu:\n");
    PreOrder(T);
    printf("\nDuyet trung tu:\n");
    InOrder(T);
    printf("\nDuyet hau tu:\n");
    PostOrder(T);
    printf("\nIsLeaf(8) = %d",IsLeaf(T8));
    printf("\nIsLeaf(1) = %d",IsLeaf(T1));
    printf("\nNbNodes(T) = %d",NbNodes(T));
    printf("\nNbLeaves(T) = %d",NbLeaves(T));
    printf("\nHeight(T) = %d",Height(T));
    return 0;
}

Cấu trúc dữ liệu: Tập hợp

Tập hợp là một danh sách mà không có phần tử nào trùng nhau, không phân biệt thứ tự các phần tử. Vì thế, ta có thể cài đặc cấu trúc dữ liệu tập hợp bằng cách sử dụng lại cấu trúc danh sách liên kết.

Trong bài viết này, giả sử kiểu dữ liệu của Danh sách và Tập hợp là kiểu số nguyên

Xét lại cấu trúc danh sách liên kết:

Khai báo cấu trúc dữ liệu danh sách liên kết:

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

Khởi tạo danh sách rỗng & kiểm tra danh sách rỗng:

void MakeNullList(List &L){
    L =(Node*)malloc(sizeof(Node));
    L->Next = NULL;
}
int EmptyList(List L){
    return (L->Next==NULL);
}


Thêm, xóa phần tử trong danh sách:

void InsertList(ElementType X, int p, List &L){
    Node* T = (Node*)malloc(sizeof(Node));
    Position P = i2p(p,L);
    T->Element = X;
    T->Next = P->Next;
    P->Next = T;
}

void DeleteList(Position P, List &L){
    if (L->Next!=NULL){

        Position T=P->Next;
        P->Next = T->Next;
        free (T);
    }
}

In danh sách:

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

Để sử dụng lại cấu trúc danh sách liên kết, ta cần lưu các thủ tục và hàm ở trên ra 1 file và đặt tên là thuvien_list.cpp

Tiếp theo, tạo 1 tập tin tên là tap_hop.cpp để cài đặt cấu trúc dữ liệu TapHop. Chú ý tập tin tap_hop.cpp phải cùng thư mục với tập tin thuvien_list.cpp

Viết code cho cấu trúc dữ liệu tập hợp:

Include thư viện danh sách liên kết

#include "thuvien_list.cpp"

Khai báo cấu trúc dữ liệu tập hợp: cũng là cấu trúc dữ liệu danh sách

typedef List Set;

Khởi tạo tập hợp rỗng & kiểm tra tập hợp rỗng: thực chất tập hợp rỗng và danh sách rỗng là như nhau nên ta sử dụng lại hàm MakeNullList và EmptyList để cài

void MakeNullSet(Set &S){
    MakeNullList(S);
}

int EmptySet(Set S){
    return EmptyList(S);
}

Hàm Member kiểm tra xem X có phải là thành viên thuộc tập hợp hay không?

int Member(ElementType X, Set S){
    Position P = S;
    while (P->Next!=NULL){
        if (P->Next->Element == X)
            return 1;
        P=P->Next;
    }
    return 0;
}

Thêm phần tử X vào tập hợp S: tương tự như thêm 1 phần tử vào danh sách nhưng trước khi thêm phải kiểm tra xem X có thuộc S hay không? Nếu không thuộc (!Member) thì mới thêm. Phần tử mới sẽ được thêm vào đầu tập hợp

void InsertSet(ElementType X, Set &S){
    if (!Member(X,S))
        InsertList(X,1,S);
}

Xóa phần tử X vào tập hợp S: trước tiên phải xác định vị trí của phần tử X trong tập hợp S, gọi là P. Nếu P->Next!=NULL (tức là X có tồn tại trong tập S) thì ta thực hiện gọi hàm xóa phần tử tại vị trí P trong danh sách S

void DeleteSet(ElementType X, Set &S){
    Position P = S;
    while (P->Next!=NULL )
        if (P->Next->Element == X)
            break;
        else
            P=P->Next;
    if (P->Next!=NULL)
        DeleteList(P,S);
}

Phép giao 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép giao là: lần lượt với từng phần tử Xi thuộc tập hợp A, thực hiện kiểm tra xem Xi thuộc tập hợp B không? Nếu thuộc thì Xi là phần tử giao của tập A và B và đưa Xi vào tập kết quả C.
Set Intersect(Set A,Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        if (Member(A->Next->Element,B))
            InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    return C;
}

Phép hợp 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hợp là: thêm tất cả phần tử thuộc tập A vào tập C, thêm tất cả phần tử thuộc tập B vào tập C.

Set Union(Set A, Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    while(B->Next!=NULL){
        InsertSet(B->Next->Element,C);
        B=B->Next;
    }
    return C;
}

Phép hiệu 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hiệu là: với từng phần tử Xi thuộc A, kiểm tra xem Xi có thuộc B hay không? Nếu không thuộc thì thêm Xi vào tập kết quả C

Set Except(Set A, Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        if (!Member(A->Next->Element,B))
            InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    return C;

}

In tập hợp: tương tự như in danh sách

void PrintSet(Set S){
    PrintList(S);
}

Hàm main để kiểm tra các phép toán đã cài đặt:

int main(){
    Set A;
    MakeNullSet(A);
    InsertSet(2,A);
    InsertSet(7,A);
    InsertSet(3,A);
    DeleteSet(2,A);
    Set B;
    MakeNullSet(B);
    InsertSet(3,B);
    InsertSet(2,B);
    InsertSet(1,B);
    Set C = Intersect(A,B);
    Set D = Union(A,B);
    Set E = Except(A,B);
    Set F = Except(B,A);
    printf("\nTap A : ");
    PrintSet(A);
    printf("\nTap B : ");
    PrintSet(B);
    printf("\nTap C : ");
    PrintSet(C);
    printf("\nTap D : ");
    PrintSet(D);
    printf("\nTap E : ");
    PrintSet(E);
    printf("\nTap F : ");
    PrintSet(F);
    return 0;
}