Zen Course Guide

Bài 2. Danh sách liên kết

Mô hình

💡 MẸO

Bạn có thể tham khảo và thực hành theo mô hình Linked List tại đâyopen in new window

Lý thuyếtopen in new window

Source Code

linkedList.hopen in new window

CẤU TRÚC

struct NODE{
    int data;
    struct NODE* Next;
};
typedef struct NODE Node;
typedef struct{
    Node *Head;
    Node *Tail;
    int Size;
}List;

KHỞI TẠO RỖNG

void makeNullList(List *L){
    L->Head = NULL;
    L->Tail = NULL;
    L->Size = 0;
}

HIỂN THỊ DANH SÁCH

void displayList(List L){
    Node *temp = L.Head;
    while(temp != NULL){
        printf("%d ",temp->data);
        temp = temp->Next;
    }
    printf("\n");
    printf("Size = %d",L.Size);
    printf("\n");
}

TẠO MỘT NODE VỚI PHẦN TỬ

Node *createNode(int x){
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = x;
    newnode->Next = NULL;
    return newnode;
}

THÊM NODE VÀO ĐẦU HOẶC CUỐI DANH SÁCH

void insertList_Frist(Node *newNode,List *L){
    if(L->Head == NULL){
        L->Head = newNode;
        L->Tail = newNode;
    }
    else{
        newNode->Next = L->Head;
        L->Head = newNode;
    }
    L->Size++;
}

void insertList_End(Node *newNode,List *L){
    if(L->Head == NULL){
        L->Head = newNode;
        L->Tail = newNode;
    }
    else{
        L->Tail->Next = newNode;
        L->Tail=newNode;
        newNode->Next = NULL;
    }
    L->Size++;
}

THÊM NODE VÀO VỊ TRÍ P TRONG DANH SÁCH

void insertList_byPos(int p,Node *newNode,List *L){
    if(p < 1 || L->Head == NULL){
        insertList_Frist(newNode,L);
    }
    else if(p >= L->Size){
        insertList_End(newNode,L);
    }
    else{
        Node *temp = L->Head;
        int i = 0;
        while(temp != NULL){
            if(p - 1 == i){
                newNode->Next = temp->Next;
                temp->Next = newNode;
                L->Size++;
                return;
            }
            i++;
            temp = temp->Next;
        }
    }
}

THÊM N NODE VÀO DANH SÁCH

void inputList(int n,List *L){
    int x;
    Node *temp;
    for (int i = 0; i < n; i++){
        scanf("%d",&x);
        temp = createNode(x);
        insertList_byPos(i,temp,L);
    }
}

KIỂM TRA X TRONG DANH SÁCH

int memberList(int x,List L){
    Node *temp = L.Head;
    while (temp != NULL){
        if(temp->data == x){
            return 1;
        }
        temp = temp->Next;
    }
    return 0;
}

TÌM VỊ TRÍ NODE CHỨA X

int locateList(int x,List L){
    Node *temp = L.Head;
    int i = 0;
    while (temp != NULL){
        if(temp->data = x){
            free(temp);
            return i;
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
    free(temp);
    return -1;
}

XOÁ NODE CÓ VỊ TRÍ P TRONG DANH SÁCH

void deleteList_byPos(int p,List *L){
    Node *temp = L->Head;
    Node *prev = NULL;
    int i = 0;
    while (temp != NULL) {
        if(p == i){
            if (prev==NULL) {
                L->Head=temp->Next;
            }
            else{
                prev->Next=temp->Next;
            }
            L->Size--;
            return;
        }
        else{
            i++;
        }
        prev = temp;
        temp = temp->Next;
    }
}

XOÁ NODE TRONG DANH SÁCH

void deleteList_byNode(Node* newNode,List *L){
    int i = 0;
    Node *temp = L->Head;
    while (temp != NULL){
        if(newNode == temp){
            deleteList_byPos(i,L);
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
}

XOÁ NODE CÓ PHẦN TỬ X TRONG DANH SÁCH

void deleteList_byValue(int x,List *L){
    Node *temp = L->Head;
    int i = 0;
    while (temp != NULL){
        if(temp->data == x){
            deleteList_byPos(i,L);
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
}

TỐI ƯU DANH SÁCH (`1 2 1` -> `1 2`)

void optimizeList(List *L){
    Node *temp1 = L->Head;
    Node *temp2 = NULL;
    while (temp1->Next != NULL){
        temp2 = temp1->Next;
        while (temp2 != NULL){
            if(temp1->data == temp2->data){
                deleteList_byNode(temp2,L);
            }
            temp2 = temp2->Next;
        }
        temp1 = temp1->Next;
    }
}

TÌM NODE CÓ PHẦN TỬ LỚN NHẤT HOẶC NHỎ NHẤT

int Find_Max(List L){
    Node *temp=L.Head;
    int max=temp->data;
    while (temp!=NULL) {
        if(max<temp->data){
            max=temp->data;
        }
        temp=temp->Next;
    }
    free(temp);
    return max;
}

int Find_Min(List L){
    Node *temp=L.Head;
    int min=temp->data;
    while (temp!=NULL) {
        if(min>temp->data){
            min=temp->data;
        }
        temp=temp->Next;
    }
    free(temp);
    return min;
}

CHUYỂN SANG DANH SÁCH KHÁC

void changeList(List L1,List *L){
    Node *temp = L1.Head;
    int i = L->Size;
    while (temp != NULL){
        insertList_byPos(i,createNode(temp->data),L);
        i++;
        temp = temp->Next;
    }
}

GỘP 2 DANH SÁCH THÀNH 1 DANH SÁCH

void mergeList(List L1,List L2,List *L){
    changeList(L1,L);
    changeList(L2,L);
}

LỌC SỐ CHẴN HOẶC LẺ QUA DANH SÁCH KHÁC

void filter_evenNumber(List L1, List *L){
    Node *temp = L1.Head;
    int i = L->Size;
    while (temp != NULL){
        if(temp->data % 2 == 0){
            insertList_byPos(i,createNode(temp->data),L);
        }
        i++;
        temp = temp->Next;
    }
}

void filter_oddNumber(List L1, List *L){
    Node *temp = L1.Head;
    int i = L->Size;
    while (temp != NULL){
        if(temp->data % 2 != 0){
            insertList_byPos(i,createNode(temp->data),L);
        }
        i++;
        temp = temp->Next;
    }
}

TÍNH TỔNG TRUNG BÌNH PHẦN TỬ TRONG DANH SÁCH

double averageList(List L){
    Node *temp = L.Head;
    double result = 0;
    while (temp != NULL){
        result += temp->data;
        temp = temp->Next;
    }
    return result/L.Size;
}

sentenceList.hopen in new window

CẤU TRÚC

struct NODE{
    char Word;
    struct NODE *Next;
};
typedef struct NODE Node;
typedef struct{
    Node *Head;
    Node *Tail;
    int Size;
}Sentence;

TẠO RỖNG CÂU

void makeNullSentence(Sentence *S){
    S->Head = NULL;
    S->Tail = NULL;
    S->Size = 0;
}

HIỂN THỊ CÂU

void displaySentence(Sentence S){
    Node *temp = S.Head;
    while(temp != NULL){
        printf("%c",temp->Word);
        temp = temp->Next;
    }
    printf("Size = %d",S.Size);
    printf("\n");
}

TẠO MỘT NODE X LÀ TỪ

Node *createNode(char c){
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->Word = c;
    newNode->Next = NULL;
    return newNode;
}

CHÈN MỘT TỪ VÀO ĐẦU HOẶC CUỐI CÂU

void insertSentence_Frist(Node *newNode,Sentence *S){
    if(S->Head == NULL){
        S->Head = newNode;
        S->Tail = newNode;
    }
    else{
        newNode->Next = S->Head;
        S->Head = newNode;
    }
    S->Size++;
}
void insertSentence_End(Node *newNode,Sentence *S){
    if(S->Head == NULL){
        S->Head = newNode;
        S->Tail = newNode;
    }
    else{
        S->Tail->Next = newNode;
        S->Tail=newNode;
        newNode->Next = NULL;
    }
    S->Size++;
}

CHÈN TỪ VỊ TRÍ P TRONG CÂU

void insertSentence_byPos(int p,Node *newNode,Sentence *S){
    if(p < 1 || S->Head == NULL){
        insertSentence_Frist(newNode,S);
    }
    else if(p >= S->Size){
        insertSentence_End(newNode,S);
    }
    else{
        Node *temp = S->Head;
        int i = 0;
        while(temp != NULL){
            if(p - 1 == i){
                newNode->Next = temp->Next;
                temp->Next = newNode;
                S->Size++;
                return;
            }
            i++;
            temp = temp->Next;
        }
    }
}

NHẬP CÂU

void inputSentence(Sentence *S){
    char c[100];
    fgets(c,100,stdin);
    int len = strlen(c);
    Node *temp;
    for(int i = 0 ; i < strlen(c) ; i++){
        temp = createNode(c[i]);
        insertSentence_byPos(i,temp,S);
    }
}

KIỂM TRA TỪ X CÓ TRONG CÂU

int memberSentence(char x,Sentence S){
    Node *temp = S.Head;
    while (temp != NULL){
        if(temp->Word == x){
            return 1;
        }
        temp = temp->Next;
    }
    return 0;
}

TÌM VỊ TRÍ TỪ X TRONG CÂU

int locateSentence(char x,Sentence S){
    Node *temp = S.Head;
    int i = 0;
    while (temp != NULL){
        if(temp->Word == x){
            return i;
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
    return -1;
}

XOÁ TỪ VỊ TRÍ P TRONG CÂU

void deleteSentence_byPos(int p,Sentence *S){
    Node *temp = S->Head;
    Node *prev = NULL;
    int i = 0;
    while (temp != NULL) {
        if(p == i){
            if (prev==NULL) {
                S->Head=temp->Next;
            }
            else{
                prev->Next=temp->Next;
            }
            S->Size--;
            return;
        }
        else{
            i++;
        }
        prev = temp;
        temp = temp->Next;
    }
}

XOÁ TỪ X TRONG CÂU

void deleteSentence_byValue(char x,Sentence *S){
    Node *temp = S->Head;
    int i = 0;
    while (temp != NULL){
        if(temp->Word == x){
            deleteSentence_byPos(i,S);
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
}

XOÁ MỘT NODE TRONG CÂU

void deleteSentence_byNode(Node *newNode,Sentence *S){
    int i = 0;
    Node *temp = S->Head;
    while (temp != NULL){
        if(newNode == temp){
            deleteSentence_byPos(i,S);
        }
        else{
            i++;
        }
        temp = temp->Next;
    }
}

XOÁ KHOẢNG TRẮNG DƯ THỪA

void deleteWhiteSpace(Sentence *S){
    Node *temp = S->Head;
    while(isspace(temp->Word)){
        deleteSentence_byNode(temp,S);
        temp = temp->Next;
    }
    while(temp != NULL){
        if(isspace(temp->Word) && temp->Next != NULL){
            if(isspace(temp->Next->Word)){
                deleteSentence_byNode(temp,S);
            }
        }
        temp = temp->Next;
    }
}

CHUẨN HOÁ CÂU

void normalizeSentence(Sentence *S){
    deleteWhiteSpace(S);
    Node *temp = S->Head;
    if(islower(temp->Word)){
        temp->Word -= 32;
    }
    temp = temp->Next;
    while (temp != NULL){
        while(!isspace(temp->Word)){
            if(isupper(temp->Word)){
                temp->Word += 32;
            }
            temp = temp->Next;
        }
        if(isspace(temp->Word) && temp->Next != NULL){
            temp = temp->Next;
            if(islower(temp->Word)){
                temp->Word -= 32;
            }
        }
        temp = temp->Next;
    }
}
Cập nhật lúc :
Tác giả: Zenfection, Zenfection