数据结构重学日记（九）单链表增删改查

上一节学完了单链表的基本操作，这里再像顺序表一样跑一下代码。毕竟只靠看是记不住多少东西的。

单链表结构

typedef int ElemType;

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

// 遍历输出单链表
void PrintLists(LinkList L) {
    LNode *  p = L->next;  //  LinkList p 也是可以的
    while (p) {
        printf("%d", p->data);
        p = p->next;
        printf("\r\n");
    }

}

创建

单链表创建有两种模式，尾插法和头插法，具体概念在上一节已经写了。

头插法

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;
}

在main 方法中初始化并调用：

LinkList L;
LinkList search;
L = CreatList(L); // 输入数据为 2 3 4 999
PrintLists(L);

/*运行结果
5

4

3

2
*/

尾插法 L = CreatList2(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);
    }
    r->next = NULL;
    return L;

}

/*
2

3

4

5
*/

插入InsertElem(L, 2, 90)

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

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

/*
5

90

4

3

2
*/

按序号查找 search = GetElem(L, 2)

LNode *GetElem(LinkList L, int i) {
    int j = 1; // 计数 从1开始
    LNode * 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;
    }
}

/*
按序号查找成功

4
*/

按值查找 LNode(L,2)

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

2
*/

删除 DeleElem(L, 2)

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