Nhảy tới nội dung

Các phép toán trên danh sách liên kết các số nguyên

Các phép toán cơ bản​

deleteList​

Yêu cầu

Xóa phần tử có Position P.

void deleteList(Position P, List *pL)
{
    Position Temp;
    if (P->Next != NULL)
    {
        Temp = P->Next;
        P->Next = Temp->Next;
        free(Temp);
    }
}

emptyList​

Yêu cầu

Kiểm tra danh sách rỗng.

int emptyList(List L)
{
    return L->Next == NULL;
}

endList​

Yêu cầu

Trả về vị trí sau vị trí cuối cùng của danh sách L.

Position endList(List L)
{
    Position P = L;
    while (1)
    {
        if (P->Next == NULL)
            return P;
        P = P->Next;
    }
}

first​

Yêu cầu

Trả về vị trí đầu tiên của danh sách L.

Position first(List L)
{
    return L;
}

insertList​

Yêu cầu

Chèn thêm phần tử vào vị trí P.

void insertList(ElementType x, Position P, List *pL)
{
    Position T;
    T = (Position)malloc(sizeof(struct Node));
    T->Element = x;
    T->Next = P->Next;
    P->Next = T;
}

locate​

Yêu cầu

Trả về vị trí đầu tiên của x trong danh sách L.

Position locate(ElementType x, List L)
{
    Position P = L;
    while (P->Next != NULL)
    {
        if (P->Next->Element == x)
            return P;
        P = P->Next;
    }
    return P;
}

makenullList​

Yêu cầu

Khởi tạo danh sách rỗng.

void makenullList(List *pL)
{
    *pL = (List)malloc(sizeof(struct Node));
    (*pL)->Next = NULL;
}

myLocate​

Yêu cầu

Trả về vị trí thứ i của phần tử x trong danh sách L.

Position myLocate(ElementType x, int i, List L)
{
    Position P = L;
    int count = 0;
    while (P->Next != NULL)
    {
        if (P->Next->Element == x)
            count++;
        if (count == i)
            return P->Next;
        P = P->Next;
    }
    return P->Next;
}

next​

Yêu cầu

Trả về vị trí tiếp theo của P.

Position next(Position P, List L)
{
    return P->Next;
}

previous​

Yêu cầu

Trả về vị trí trước P.

Position previous(Position P, List L)
{
    Position Q = L;
    while (Q->Next->Next != NULL)
    {
        if (Q->Next->Next == P)
            Q = Q->Next;
    }
    return Q->Next;
}

retrieve​

Yêu cầu

Trả về giá trị của phần tử có vị trí P.

ElementType retrieve(Position P, List L)
{
    if (P->Next != NULL)
        return P->Next->Element;
}

Các phép toán khác​

addFirst​

Yêu cầu

Thêm phần tử vào đầu danh sách.

void addFirst(ElementType x, List *pL)
{
    Position P;
    P = (Position)malloc(sizeof(struct Node));
    P->Element = x;
    P->Next = (*pL)->Next;
    (*pL)->Next = P;
}

append​

Yêu cầu

Thêm phần tử vào cuối danh sách

void append(ElementType x, List *pL)
{
    Position P = endList(*pL);
    Position T = (Position)malloc(sizeof(struct Node));
    T->Element = x;
    T->Next = NULL;
    P->Next = T;
}

copyEvenNumbers​

Yêu cầu

Sao chép số chẵn trong danh sách.

void copyEvenNumbers(List L, List *pL)
{
    makenullList(pL);
    Position P = L;
    while (P->Next != NULL)
    {
        if (P->Next->Element % 2 == 0)
            append(P->Next->Element, pL);
        P = P->Next;
    }
}

deleteX​

Yêu cầu

Xóa phần tử x.

void deleteX(ElementType x, List *pL)
{
    Position P = first(*pL);
    while (P != endList(*pL))
    {
        if (retrieve(P, *pL) == x)
            deleteList(P, pL);
        else
            P = next(P, *pL);
    }
}

difference​

Yêu cầu

Tìm tập hiệu.

List difference(List L1, List L2)
{
    List L;
    makenullList(&L);
    Position P = L1;
    while (P->Next != NULL)
    {
        if (!member(P->Next->Element, L) && !member(P->Next->Element, L2))
            append(P->Next->Element, &L);
        P = P->Next;
    }
    return L;
}

erase​

Yêu cầu

Xóa phần tử x đầu tiên.

void erase(ElementType x, List *pL)
{
    if (locate(x, *pL)->Next != NULL)
        deleteList(locate(x, *pL), pL);
}

getAvg​

Yêu cầu

Tính trung bình cộng của danh sách.

float getAvg(List L)
{
    float sum = 0;
    int length = 0;
    Position P = L;
    if (P->Next == NULL)
        return -10000;
    while (P->Next != NULL)
    {
        sum += P->Next->Element;
        length++;
        P = P->Next;
    }
    return sum / length;
}

intersection​

Yêu cầu

Tìm tập giao của hai tập.

List intersection(List L1, List L2)
{
    List L;
    makenullList(&L);
    Position P = L2;
    while (P->Next != NULL)
    {
        if (!member(P->Next->Element, L) && member(P->Next->Element, L1))
            append(P->Next->Element, &L);
        P = P->Next;
    }
    return L;
}

member​

Yêu cầu

Kiểm tra một giá trị có trong danh sách không.

int member(ElementType x, List L)
{
    Position P = L;
    while (P->Next != NULL)
    {
        if (P->Next->Element == x)
            return 1;
        P = P->Next;
    }
    return 0;
}

normalize​

Yêu cầu

Xóa các phần tử trùng giá trị.

void normalize(List *pL)
{
    Position P = *pL, Q;
    while (P->Next != NULL)
    {
        Q = P->Next;
        while (Q->Next != NULL)
        {
            if (Q->Next->Element == P->Next->Element)
                deleteList(Q, pL);
            Q = Q->Next;
        }
        P = P->Next;
    }
}

printList​

Yêu cầu

In danh sách.

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

printOddNumbers​

Yêu cầu

In các số lẻ trong danh sách.

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

readSet​

Yêu cầu

Nhập tập hợp.

List readSet()
{
    List L;
    makenullList(&L);
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        if (!member(x, L))
            addFirst(x, &L);
    }
    return L;
}

removeAll​

Yêu cầu

Xóa tất cả các phần tử có giá trị x.

void removeAll(ElementType x, List *pL)
{
    while (locate(x, *pL)->Next != NULL)
        deleteList(locate(x, *pL), pL);
}

readList​

Yêu cầu

Nhập danh sách.

void readList(List *pL)
{
    makenullList(pL);
    int n;
    Position P = *pL,
             N;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        N = (Position)malloc(sizeof(struct Node));
        scanf("%d", &N->Element);
        P->Next = N;
        P = P->Next;
    }
}

sort​

Yêu cầu

Sắp xếp danh sách.

void sort(List *pL)
{
    Position P = *pL,
             N;
    while (P->Next != NULL)
    {
        N = P->Next;
        while (N->Next != NULL)
        {
            :::info Yêu cầu
            if (P->Next->Element N->Next->Element)
            :::
            {
                ElementType Temp = P->Next->Element;
                P->Next->Element = N->Next->Element;
                N->Next->Element = Temp;
            }
            N = N->Next;
        }
        P = P->Next;
    }
}

unionSet​

Yêu cầu

Gộp 2 tập hợp.

List unionSet(List L1, List L2)
{
    List L;
    makenullList(&L);
    Position P = L1;
    while (P->Next != NULL)
    {
        if (!member(P->Next->Element, L))
            append(P->Next->Element, &L);
        P = P->Next;
    }
    P = L2;
    while (P->Next != NULL)
    {
        if (!member(P->Next->Element, L))
            append(P->Next->Element, &L);
        P = P->Next;
    }
    return L;
}