线性结构 - 单链表小结

链式存储

链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。

在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息，这两部分信息组成数据元素的存储结构，称为结点。

包括两个域：

数据域：存储数据元素信息的域
指针域：存储直接后继存储位置的域

单链表

单链表是一种链式存储的数据结构。用一组任意的存储单元存放线性表中的数据元素。

单链表中的数据是以结点来表示的。

每个结点的构成：

数据域	指针域
存储数据元素	存储指针

C语言结构设计：

/* ElemType是数据类型，具体类型根据实际情况而定，这里假设为int */
typedef int ElemType;

/* 结点类型设计 */
typedef struct Node {
    ElemType data;
    struct Node *next;
}Node, *LinkList;

指针是指向每一个结点的，也就是指向struct Node这个自定义的结构体类型.
所以指向的类型就是struct Node *

单链表的基本操作

1. 单链表的初始化

头指针：指向链表中的第一个结点的指针
头结点：链表的首元结点之前附设的一个结点
首元结点：链表中存储线性表第一个数据元素的结点

为什么要引入头结点呢？

便于首元结点的处理
便于空表和非空表的统一处理

// 创建一个头指针，实际上就是创建一个头结点
// 头指针指向头结点
// 头结点的next 置空

Status initList(LinkList *L) {
    
    *L = (LinkList)malloc(sizeof(Node));
    
    if (*L == NULL) {
        return ERROR;
    }
    
    (*L)->next = NULL;
    return OK;
}

空链表，头指针就是尾指针

2. 头插法构建

void headInsertList(LinkList *L) {
    // 初始化1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    Node *p;
    
    int i = 0;
    while (i < MAXSIZE) {
        // 生成新结点
        p = malloc(sizeof(Node));
        // 保存数据
        p->data = i;
        
        // 更新新结点的next位置，指向单链表L的next
        p->next = (*L)->next;
        
        // 更新单链表L的next，指向新结点
        (*L)->next = p;
        
        i++;
    }
}

3. 尾插法构建

在链表的尾结点插入新的结点。

链表尾结点的next ->新结点
新结点的next 置空

void tailInsertList(LinkList *L) {
    
    // 初始化1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    // 定义尾指针r
    LinkList r = *L;
    Node *p;
    
    int i = 0;
    while (i < MAXSIZE) {
        // 生成新结点
        p = malloc(sizeof(Node));
        // 保存数据
        p->data = i;
        
        // 更新尾指针的next, 指向新结点
        r->next = p;
        // 更新尾指针
        r = p;
        i++;
    }
    r->next = NULL;
}

4. 插入

找插入位置的前驱结点
将插入结点的next指向前驱结点的next
将前驱结点的next指向插入结点

Status insertList(LinkList *L, int i, ElemType e) {
    
    // 寻找第 i - 1 位置的结点
    int j = 1;
    Node *p = *L;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i) {
        // 第 i - 1 个元素不存在
        return ERROR;
    }
    
    // 生成新结点
    Node *s = malloc(sizeof(Node));
    
    // 存值
    s->data = e;
    
    // 将新结点的next 指向第i - 1个元素的next
    s->next = p->next;
    // 将第i - 1个元素的next 指向新结点
    p->next = s;
    
    return OK;
}

5. 删除

找删除位置的前驱结点
将前驱结点的next指向删除结点的next
free删除结点

Status deleteList(LinkList *L, int i, ElemType *e) {
    int j = 1;
    Node *p = *L, *q;
    while (p && j < i) {
        p = p ->next;
        j++;
    }
    
    if (!p || j > i) {
        return ERROR;
    }
    
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

6. 遍历

void traversList(LinkList L) {
    Node *p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

7. 按序号查询

Status GetElem(LinkList L, int i, ElemType *e) {
    int j = 1;
    Node *p = L->next;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i) {
        return ERROR;
    }
    
    *e = p->data;
    return OK;
}

8. 按值查询

Status LocateElem(LinkList L, ElemType e, int *i) {
    Node *p = L->next;
    int j = 1;
    while (p != NULL && p->data != e) {
        p = p->next;
        j++;
    }
    *i = j;
    return OK;
}

查看demo