Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/2.线性表 -- 单链表.md

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

bool InitLinkList(LinkList &List) {
    List = (LNode *) malloc(sizeof(LNode));
    if (List == NULL) {
        return false;
    }
    List->next = NULL;
    return true;
}

LNode *GetNode(LinkList List, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p = List;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

LNode *SearchNode(LinkList List, ElemType e) {
    LNode *p = List;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

bool InsertNextNode(LNode *pNode, ElemType e) {
    if (pNode == NULL) {
        return false;
    }
    LNode *sNode = (LNode *) malloc(sizeof(LNode));
    sNode->data = e;
    sNode->next = pNode->next;
    pNode->next = sNode;
    return true;
}

bool InsertPriorNode(LNode *pNode, ElemType e) {
    if (pNode == NULL) {
        return false;
    }
    LNode *sNode = (LNode *) malloc(sizeof(LNode));
    if (sNode == NULL) {
        return false;
    }
    sNode->next = pNode->next;
    pNode->next = sNode;
    sNode->data = pNode->data;
    pNode->data = e;
    return true;
}

bool LikeListInsert(LinkList &List, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    LNode *pNode = GetNode(List, i - 1);
    return InsertNextNode(pNode, e);
}

bool LNodeDelete(LNode *pNode) {
    if (pNode == NULL) {
        return false;
    }
    //BUG
    if (pNode->next == NULL) {
        return false;
    }
    LNode *qNode = pNode->next;
    pNode->data = qNode->data;
    pNode->next = qNode->next;
    free(pNode);
    return true;
}

bool LinkListDelete(LinkList &List, int i, ElemType &e) {
    if (i < 1) {
        return false;
    }
    LNode *pNode = GetNode(List, i - 1);
    if (pNode == NULL) {
        return false;
    }
    LNode *qNode = pNode->next;
    pNode->next = qNode->next;
    e = qNode->data;
    free(qNode);
    return true;
}

bool LNodeSetElem(LinkList &List, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    LNode *pNode = GetNode(List, i);
    pNode->data = e;
    return true;
}

bool LinkListHeadInsert(LinkList &List, ElemType e) {
    LNode *sNode = (LNode *) malloc(sizeof(ElemType));
    if (sNode == NULL) {
        return false;
    }
    sNode->data = e;
    sNode->next = List->next;
    List->next = sNode;
    return true;
}

bool LinkListEndInsert(LinkList &List, LNode *endNode, ElemType e) {
    LNode *sNode = (LNode *) malloc(sizeof(ElemType));
    if (sNode == NULL) {
        return false;
    }
    return InsertNextNode(endNode, e);
}

void PrintLinkList(LinkList List) {
    if (List->next == NULL) {
        printf("NULL\n");
        return;
    }
    LNode *p = List->next;
    while (p != NULL) {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList List;
    InitLinkList(List);
    PrintLinkList(List);
    for (int i = 0; i < 5; ++i) {
        LikeListInsert(List, i + 1, i + 1);
    }
    PrintLinkList(List);
    ElemType result;
    LinkListDelete(List, 1, result);
    PrintLinkList(List);
    LNode *pNode = GetNode(List, 4);
    printf("%3d\n", pNode->data);
    LNodeSetElem(List, 4, 9);
    PrintLinkList(List);
    return 0;
}