数据结构重学日记（八）单链表的操作

头插法

建立新的结点分配内存空间，将新结点插入到当前链表的表头：

LinkList CreatList(LinkList L) {
    int x;
    LNode * s; //辅助指针
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL; //初始为空表
    scanf("%d", &x);
    while (x != 999) { //输入999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x; //对新结点的数据域赋值
        s->next = L->next; //新节点的后继指向第一个结点
        L->next = s; //头结点的后继指向新结点
        scanf("%d",&x); //读取下一个节点值
    }
    return L;
}

尾插法

建立新的结点分配内存空间，将新结点插入到当前链表的表尾：

LinkList CreatList2(LinkList L) {
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LNode *s, *r = L; // r为表尾指针，指向表尾
    scanf("%d", &x);
    while (x != 999) {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}

按序号查找

从单链表第一个结点出发，顺指针 next 域逐个往下搜索，知道找到第 i 个结点为止，否则返回最后一个结点指针域 null。

LNode *GetElem(LinkList L, int i) {
    int j = 1; // 计数 从1开始
    LinkList p = L->next; // 第一个节点指针赋予 p a1

    if (i == 0) return L; // 若 i = 0 ，返回头结点

    if (i < 1) return NULL; // i 无效，返回 null

    while (p && j < i) { // 从第一个结点开始查找，直到 i
        p = p->next; // 下一个结点指针
        j++;

    }
    if (j == i) {
        return p;
    } else {
        return NULL;
    }
}

按值查找

从第一个结点开始，依次往后比较结点语句与的值，若某个结点的值等于给定值 e ，则返回该结点的指针，若整个单链表中没有这样的结点，则返回 null。

LNode * LocateElem(LinkList L, ElemType e){
    LinkList  p = L->next;
    while (p != NULL && p->data != e){ // 从第一个结点开始查找 data 域为 e 的结点
        p = p->next;
    }
    return p;
}

链表插入

将值为 x 的新结点插入到单链表的第 i 个位置，先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i - 1 个结点，再在其后插入新结点。

LNode *InsertElem(LinkList L, int i, ElemType x) {

    LinkList p = GetElem(L, i - 1);
    LinkList s = (LNode *) malloc(sizeof(LNode));
    s->next = p->next;
    s->data = x;
    p->next = s;
}

删除

先检查位置的合法性，然后查找第 i - 1 个结点，即被删除结点的前驱结点，再将其删除。

LNode *DeleElem(LinkList L, int i) {
    LinkList p = GetElem(L, i - 1);
    LinkList q;
    q = p->next;
    p->next = q->next;
    free(q);
}