关于数据结构:线性表的链式表示单链表

1、定义：

通过一组任意的存储单元来存储线性表中的数据元素。为了建设数据元素之间的线性关系，对每个链表节点，除了寄存元素本身的信息外，还须要寄存一个指向下一个节点

构造体：

typedef int ElemType;
typedef struct LNode {       //定义单链表节点类型
    ElemType data;           //每个节点寄存一个数据元素
    struct LNode *next;      //指针指向下一个节点
} LNode, *LinkList;          //强调这是一个单链表应用LinkList，强调节点应用LNode*

2、创立一个单链表

2.1 用头插法建设单链表

新节点插入到以后列表的表头：

代码实现：

/**
 * 用头插法建设单链表
 * @param L
 * @return
 */
LinkList List_HeadInsert(LinkList &L) {  //逆向建设单链表
    LNode *s;
    int x;
    L = (LinkList) malloc(sizeof(LNode));  //创立头节点
    L->next = NULL;                        //初始为空链表
    scanf("%d", &x);                 //输出节点的值
    while (x != 9999) {                     //输出9999示意完结
        s = (LNode *) malloc(sizeof(LNode)); //创立新节点
        s->data = x;
        s->next = L->next;
        L->next = s;                        //将新节点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

采纳头插法建设单链表时，读入数据的程序与生成的链表中的元素的程序式相同的

2.2 用尾插法建设单链表

新节点插入到以后列表的表尾，该办法须要一个尾指针指向链表的最初一个节点，图中未画出尾指针：

代码实现：

/**
 * 用尾插法建设单链表
 * @param L
 * @return
 */
LinkList List_TailInsert(LinkList &L) {      //正向建设单链表
    int x;                                  //设ElemType为整型
    L = (LinkList) malloc(sizeof(LNode));    //建设头节点
    LNode *s, *r = L;                          //r为表尾指针
    scanf("%d", &x);                  //输出节点的值
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                               //r指向新的表尾节点
        scanf("%d", &x);
    }
    r->next = NULL;                         //尾节点指针置空
    return L;
}

3、基本操作

3.1 在指定节点前插入元素

实现原理图：

代码实现:

/**
 * 前插操作，在p节点之前插入元素e
 * @param p
 * @param e
 * @return
 */
bool InsertPriorNode(LNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }
    s->next = p->next;
    p->next = s;          //新节点s连到p之后
    s->data = p->data;    //将p中元素复制到s中
    p->data = e;        //p中的元素改为e
    return true;
}

3.2 在指定节点后插

代码实现：

/**
 * 后插操作，在p节点之后插入元素e
 * @param p
 * @param e
 * @return
 */
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) {       //内存调配失败
        return false;
    }
    s->data = e;        //用节点s保留数据元素e
    s->next = p->next;  // 留神先后顺序
    p->next = s;
    return true;
}

3.3 按位序删

代码实现：

/**
 * 按位序删除，带头结点
 * @param L
 * @param i
 * @param e
 * @return
 */
bool ListDelete(LinkList &L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    LNode *p;       //指针p指向以后扫描到的节点
    int j = 0;      //以后p指向的是第几个节点
    p = L;            //L指向头节点，头节点是第0个节点，不存数据
    while (p != NULL && j < i - 1) {  //循环找到第 i-1 个节点
        p = p->next;
        j++;
    }
    if (p == NULL) {       //i值不非法
        return false;
    }
    if (p->next == NULL) {   //第i-1个节点之后已无其余节点
        return false;
    }
    LNode *q = p->next;     //令q指向被删除的节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中断开
    free(q);                //开释节点的存储空间
    return true;
}

3.4 按位查找

/**
 * 按位查找，返回第i个元素，带头节点
 * @param L
 * @param i
 * @return
 */
LNode *GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;       //指针p指向以后扫描到的节点
    int j = 0;      //以后p指向的是第几个节点
    p = L;          //L指向头节点，头节点是第0个节点，不存数据
    while (p != NULL && j < i) {    //循环找到第 i 个节点
        p = p->next;
        j++;
    }
    return![image.png](/img/bVcSqxv)