数据结构初阶：单链表

4. 尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            ptail = ptail->next;
        }
        ptail->next = newnode;
    }
}

5. 头插

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

6. 尾删

void SLTPopBack(SLTNode** pphead) {
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } else {
        SLTNode* prev = *pphead;
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

7. 头删

void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

8. 查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

9. 指定位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && *pphead);
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    if (pos == *pphead) {
        SLTPushFront(pphead, x);
    } else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = newnode;
        newnode->next = pos;
    }
}

10. 指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

11. 指定位置前删除

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && *pphead);
    SLTNode* prev = *pphead;
    if (pos == *pphead) {
        SLTPopFront(pphead);
    } else {
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

12. 指定位置后删除

void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = pos->next->next;
    free(del);
}

13. 链表的销毁

void SLTDestroy(SLTNode** pphead) {
    assert(pphead);
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    *pphead = NULL;
}

3. 程序源码

共分三个文件

SList.h 函数的声明

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
} SLTNode;

void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);

SList.c 函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SLTPrint(SLTNode* phead) {
    SLTNode* pcur = phead;
    while (pcur) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

SLTNode* SLTBuyNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            ptail = ptail->next;
        }
        ptail->next = newnode;
    }
}

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SLTPopBack(SLTNode** pphead) {
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } else {
        SLTNode* prev = *pphead;
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && *pphead);
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    if (pos == *pphead) {
        SLTPushFront(pphead, x);
    } else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = newnode;
        newnode->next = pos;
    }
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && *pphead);
    SLTNode* prev = *pphead;
    if (pos == *pphead) {
        SLTPopFront(pphead);
    } else {
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = pos->next->next;
    free(del);
}

void SLTDestroy(SLTNode** pphead) {
    assert(pphead);
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    *pphead = NULL;
}

test.c 用来测试

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SListTest01() {
    SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
    node1->data = 1;
    SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
    node2->data = 2;
    SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
    node3->data = 3;
    SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
    node4->data = 4;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;

    SLTNode* plist = node1;
    SLTPrint(plist);
}

void Test02() {
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);

    SLTPopBack(&plist);
    SLTPrint(plist);

    SLTNode* find = SLTFind(plist, 3);
    SLTInsertAfter(find, 9);
    SLTPrint(plist);
    SLTPopFront(&plist);
    SLTPrint(plist);
    SLTEraseAfter(find);
    SLTDestroy(&plist);
    SLTPrint(plist);
}

int main() {
    Test02();
    return 0;
}