【数据结构——线性表之链表】

【数据结构——线性表之链表】
一、单链表
- （一）单链表的描述
- （一）单链表的操作实现
- - 1、初始化
  - 2、查找
  - 3、插入
  - 4、删除
  - 5、单链表的建立（前插法）
  - 6、单链表的建立（后插法）
二、循环链表
三、双向链表
- - 1、插入
  - 1、删除

一、单链表

（一）单链表的描述

typedef struct LNode {
    ElemType data;//结点数据域
    struct LNode* next;//结点指针域
}LNode ,*LinkList;
变量定义：
LNode* p, * q     LinkList L;
p, q, L都是指针变量，* p, * q, * L都是结点变量
指针变量p : 表示结点地址
结点变量* p：表示一个结点
p->data;//表示数据域
p->next;//表示指针域
typedef struct LNode {
    ElemType data;//结点数据域
    struct LNode* next;//结点指针域
}LNode ,*LinkList;
LinkList p, s, L;//指针变量的定义
L = new LNode;//为指针变量L分配内存空间
p = L;//p指向头结点
s = L->next;//s指向首元结点

（一）单链表的操作实现

1、初始化

算法思想：
（1）、生成新结点作为头结点，用头指针L指向头结点
（2）、头结点的指针域置为空

/*初始化*/
Status InitList(LinkList& L)
{
    L = new LNode;//生成新结点作为头结点，用头指针L指向头结点
    L->next = NULL;//头结点的指针域置为空
    return OK;
}

2、查找

在这里插入图片描述

算法思想：
（1）、初始化，p指向第一个结点，j为计数器
（2）、从链表头依次向后扫描，直到p为空或p指向第i个元素
（3）、更新p指向当前结点，计数器+1
（4）、i 值不合法（i<=0或者i>n)
（5）、取第i个结点的数据域

/*按序号查找*/
Status GetElem(LinkList L, int i, ElemType& e)
{
    LinkList p;
    int j;
    p = L->next;j = 1;//初始化，p指向第一个结点，j为计数器
    while (p && j < i)//从链表头依次向后扫描，直到p为空或p指向第i个元素
    {
        p = p->next;//更新p指向当前结点
        ++j;//计数器+1
    }
    if (!p || j > i) return ERROR;//i 值不合法（i<=0或者i>n)
    e = p->data;//取第i个结点的数据域
    return OK;
}

3、插入

在这里插入图片描述

算法思想：
(1)找到a i - 1的存储位置p
(2)生成一个新结点 * s
(3)将新结点 * s的数据域置为e
(4)新结点 * s的指针域指向a i
(5)结点p指针域指向结点s

/*插入*/
Status ListInsert(LinkList & L, int i, ElemType e)
{
    p = L;
    int j = 0;
    while (p && j < i - 1)//寻找第i - 1个结点
    {
        p = p->next;//指向当前结点
        ++j;
    }
    if (!p || j > i - 1) return ERROR;//i值不合法
    LinkList s;
    s = new LNode;//生成新结点s
    s->data = e;//新结点的数据域置为e
    s->next = p->next;//新结点 * s的指针域指向a i
    p->next = s;//结点*p指针域指向结点*s
    return OK;
}

4、删除

在这里插入图片描述

算法思想：
(1)查找结点a i-1所在位置，并由指针p指向该结点
(2)临时保存待删除结点ai的地址在q中，以备释放
(3)将结点*p指向结点ai的直接后继结点
(4)释放结点ai的空间

Status LinkDelete(LinkList & L, int i)
{
    p = L;
    j = 0;
    while (p->next && j < i - 1)//寻找第i-1个结点
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i - 1) return ERROR;
    q = p->next;//临时保存待删除结点ai的地址在q中，以备释放
    p->next = q->next;//将结点*p指向结点ai的直接后继结点
    delete q;//释放结点ai的空间
    return OK;
}

5、单链表的建立（前插法）

在这里插入图片描述

描述：前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

算法思想
（1）创建一个只有头结点的空链表。
（2）根据待创建链表包括的元素个数n，循环n次执行以下操作：
1、生成一个新结点p;
2、输入元素值赋值给新结点p的数据域；
3、将新结点*p插入到头结点之后。

/*单链表的建立（前插法）*/
void CreateList(LinkList& L, int n)
{
    L = new LNode;//建立一个带头结点的空链表
    L->next = NULL;
    for (i = n;i > 0;--i)//循环插入新结点
    {
        p = new LNode;//生成新结点*p
        scanf_s("%d", &p->data);//输入元素赋值给p->data
        p->next = L->next;//将新结点*p插入到头结点后
        L->next = p;
    }
}

6、单链表的建立（后插法）

在这里插入图片描述

描述：后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。

算法思想：
（1）创建一个只有头结点的空链表
（2）尾指针r初始化，指向头结点
（3）根据创建链表包括的元素个数n,循环n次执行以下操作：
1、生成一个新结点p;
2、输入元素值赋给新结点p的数据域
3、将新结点p插入到尾结点r之后；
4、尾指针r指向新的尾结点*p.

/*单链表的建立（后插法）*/
void CreateList(LinkList& L, int n)
{
    L = new LNode;//建立带头结点的空链表
    L->next = NULL;
    r = L;//尾指针指向头结点
    for (i = 0;i < n;i++)
    {
        p = new LNode;//生成新结点p
        scanf_s("%d", &p->data);//输入数据域
        p->next = NULL;
        r->next = p;//插入到尾表
        r = p;//r指向新的尾结点
    }
}

二、循环链表

特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
在这里插入图片描述
从循环链表中的任何一个结点的位置都可以找到其他所有的结点，而单链表做不到，循环链表中没有明显的尾端。

在这里插入图片描述
实现

p->next = B->next;
B->next = A->next;
A->next = p->next;
delete p;
A = B;

三、双向链表

有两个指针域的链表，称为双链表

/*双向链表的存储结构*/
typedef struct DuLNode {
    ElemType data;//数据域
    struct DuLNode *prior;//前指针域
    struct DuLNode* next;//后指针域
}DuLNode,*DuLinkLst;

在这里插入图片描述

1、插入

在这里插入图片描述

/*双向链表的插入*/
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
        retrun ERROR;//p为NULL时，第i个元素不存在
    s = new DuLNode;//生成一个新结点s
    s->data = e;//将数据e存入到结点s的数据域data中
    s->prior = p->prior;//将结点s的前指针指向前一个结点
    p->prior->next = s;//将前一个结点的后指针指向新结点s
    s->next = p;//新结点s的后指针指向p
    p->prior = s;//p的前指针指向新结点
    return OK;
}

1、删除

在这里插入图片描述

/*双向链表的删除*/
Status ListDelete_DuL(DuLinkList& L, int i, ElemType &e)
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
        retrun ERROR;//p为NULL时，第i个元素不存在
    e = p->data;//保存被删除结点的数据域
    p->prior->next = p->next;//修改被删除结点的前驱结点的后继指针
    p->next->prior = p->prior;//修改被删除结点的后继结点的前驱指针
    delete p;//释放被删除结点的空间
    return OK;
}