线性表——链表

2.3、链表

线性表的链式存储结构

链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

• 每个数据都有一个指针
• 数据分散在内存中，无需存储在连续空间中
• 访问时，只能从第一个数据开始，一一向下访问
• 添加数据时，只需要改变添加位置前后的指针就可以了，删除也是

1、定义

线性表的链式存储结构称为链表（linked list）

线性表中每个结点有唯一的前驱结点和后继结点。

数据域：存储结点中元素本身的信息

指针域：元素之间的逻辑关系，用指针表示

单链表：每个物理结点增加一个指向后继结点的指针域

双链表：每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

头指针（head pointer）：每个链表都带有一个头结点，头结点的指针指向这个链表，头结点的指针就是头指针

首指针（first pointer）：首结点的指针

尾指针（tail pointer）：尾结点的指针

单链表增加一个头结点的优点：

• 第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理
• 无论链表是否为空，都有一个头结点，因此空表和非空表的处理也统一了

存储密度是指 结点数据本身所占的空间 和 整个结点结构中所占的空间之比。

存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1.

2、单链表

结点类型定义：

typedef struct LNode
{
	ElemType data;	//存放元素值
    struct LNode *next;		//指向后继结点
}LinkNode;		//单链表结点类型

单链表访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。

①、插入结点和删除结点操作

1）插入结点

插入操作：将值为x的新结点 *s 插入到 *p结点之后

特点：只需修改相关结点的指针域，不需要移动结点

2）删除结点

删除操作：删除*p结点之后的一个结点

特点：只需修改相关结点的指针域，不需要移动结点

②、建立单链表

（1）头插法建表

• 从一个空表开始，创建一个头结点
• 依次读取字符数组a中的元素，生成新结点
• 将新结点插入到当前链表的表头上，直到结束为止
• 注意：链表的顺序与逻辑顺序 相反

//头插法算法如下
void CreateListF(LinkNode *&L, ElemType a[], int n)
{
    LinkNode *s;
    int i;
    L = (LinkNode *)malloc(sizeof(LinkNode));
    L->next = NULL;	//创建头结点，其next域置为NULL
    
    for(i = 0; i < n; i++)	//循环建立数据结点
    {
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = a[i];		//建立数据结点*s
        s->next = L->next;	//将*s插在原开始结点之前，头结点之后
        L->next = s;
    }
}

（2）尾插法建表

• 从一个空表开始，创建一个头结点
• 依次读取字符数组a中的元素，生成新结点
• 将新结点插入到当前链表的表尾上，直到结束
• 链表的结点顺序与逻辑次序相同

void CreateListR(LinkNode *&L, ElemType a[], int n)
{
	LinkNode *s, *r;
    int i;
    L = (LinkNode *)malloc(sizeof(LinkNode));	//创建头结点
    r = L;	//r始终指向尾结点，开始时指向头结点
    for(i = 0; i < n; i++)	//循环建立数据结点
    {
		s = (LinkNode *)malloc(sizeof(LinkNode));
         s->data = a[i]; 	//创建数据结点 *s
         r->next = s;	//将*s 插入 *r之后
         r = s;		//s就是新的r，r的指针右移了
    }
    r->next = NULL;		//尾结点next域置为NULL
}

③、线性表基本运算在单链表上的实现

（1）初始化线性表 InitList(L)

该运算建立一个空的单链表，即创建一个头结点。

void InitList(LinkNode *&L)
{
	L = (LinkNode *)malloc(sizeof(LinkNode));	//创建头结点
    L->next = NULL;
}

（2）销毁线性表 DestroyList(L)

释放单链表L占用的空间。即逐一释放全部结点的空间。

void DestroyList(LinkNode *&L)
{
    LinkNode *pre = L, *p = L->next;	//pre指向*p的前驱结点
    while(p != NULL)	//扫描单链表L
    {
        free(pre);	//释放*pre结点
        pre = p;	//pre、p同步后移一个结点
        p = pre->next;
    }
    free(pre);	//循环结束时，p为NULL，pre指向尾结点，释放它
}

（3）判断线性表是否为空表 ListEmpty(L)

若单链表L 没有数据结点，则返回真，否则返回假。

bool ListEmpty(LinkNode *L)
{
	return(L->next == NULL);
}

（4）求线性表的长度 ListLength(L)

返回单链表L中数据结点的个数

int ListLenth(LinkNode *L)
{
    int n = 0;
    LinkNode *p = L;	//p指向头结点，n置为0（头结点的序号为0）
    while(p->next != NULL)
    {
        n++;
        p = p->next;
    }
    return(n);	//循环结束，p指向尾结点，其序号n为结点个数
}

（5）输出线性表 DispList(L)

逐一扫描单链表L 的每个数据结点，并显示各结点的 data域值。

void DispList(LinkNode *L)
{
    LinkNode *p = L->next; 	//p指向开始结点
    while(p != NULL)	//p不为NULL，输出 *p 结点的 data域
    {
		printf("%d", p->data);
        p = p->next;	//p移向下一个结点
    }
    pirintf("\n");
}

（6）求线性表L中位置 i 的数据元素 GetElme(L, i, &e)

思路： 在单链表L中从头开始找到第 i 个结点，若存在第 i 个数据结点，则将其 data 域值赋给变量 e。

bool GetElem(LinkNode *L, int i, ElemType &e)
{
    int j = 0;
    LinkNode *p = L;	//p指向头结点，j置为0（即头结点的序号为0）
    while(j < i && p != NULL)
    {
        j++;
        p = p->next;	//找出第i个结点*p
    }
    if(p == NULL)
    {
        return false;	//不存在第i个数据结点，返回false
    }else{
        e = p->data;
        return true;	//存在第 i个数据结点，返回true
    }
}

（7）按元素值查找 LocateElem(L, e)

思路：在单链表L中从头开始找第1个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回0。

int LocateElem(LinkNode *L, ElemType e)
{
    int i = 1;
    LinkNode *p = L->next;	//p指向开始结点，i置为1
    while(p != NULL && p->data != e)
    {
        p = p->next;	//查找data值为e的结点，其序号为i
        i++;
    }
    if(p == NULL)
    {
        return(0);		//不存在元素值为e的结点，返回0
    }else{
        return(i);	//存在元素值为e的结点，返回其逻辑序号i
    }
}
//算法的时间复杂度为O(n)，不具有随机存取特性

（8）插入数据元素 ListInsert(&L, i, e)

思路：先在单链表L中找到第 i-1 个结点 *p,若存在这样的结点，将值为e的结点 *s 插入到其后。

bool ListInsert(LinkNode *&L, int i, ElemType e)
{
    int j = 0;
    LinkNode *P = L, *s;	//p指向头结点，j置为0
    while(j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;	//查找第 i-1个结点
    }
    if(p == NULL)	//未找到第 i-1 个结点，返回false
    {
        return false;
    }else{
        //找到第 i-1个结点 *p,插入新结点并返回true
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = e;	//创建新结点 *s, 其 data 域置为 e 
        s->next = p->next;	//将 *s 插入到 *p 之后
        p->next = s;
    }
}

（9）删除数据元素 ListDelete(&L, i, &e)

思路：先在单链表 L中找到第 i-1 个结点 *p,若存在这样的结点，且也存在后继结点，则删除该后继结点。

bool ListDelete(LinkNode *&L, int i, ElemType &e)
{
    int j = 0;
    LinkNode *p = L, *q;	//p指向头结点，j置为0
    while(j < i - 1 && p != NULL)	//查找第 i-1 个结点
    {
        j++;
        p = p->next;
    }
    if(p == NULL)	//未找到第 i-1 个结点，返回false
    {
        return false;
    }else{
        //找到第 i-1 个结点*p
        q = p->next;	//q指向第i 个结点
        if(q == NULL)	//若不存在第 i 个结点，返回false
        {
            return false;
        }
        e = q->data;
        p->next = q->next;	//从单链表中删除 *q结点
        free(q);	//释放*q结点
        return true;	//返回true表示成功删除第 i 个结点
    }
}

④、单链表的算法设计方法

Ⅰ、以查找为基础的算法设计

• 按照条件进行结点查找
• 进行插入或者删除操作

void delmaxnode(LinkNode *&L)
{
    LinkNode *p = L->next, *pre = L, *maxp = p, *maxpre = pre;
    //查找最大值结点的前驱结点*maxpre
    while(p != NULL)
    {
        if(maxp->data < p->data)	//若找到一个更大的结点
        {
            maxp = p;	//更改maxp
            maxpre = pre;	//更改maxpre
        }
        pre = p;		//p,pre同步后移一个结点
        p = p->next;
    }
    maxpre->next = maxp->next;	//删除*maxp结点
    free(maxp);	//释放*maxp结点
}

void sort(LinkNode *&L)
{
    LinkNode *p, *pre, *q;
    p = L->next->next;	//p指向L的第2个数据结点
    L->next->next = NULL;	//构造只含一个数据结点的有序表
    while(p != NULL)
    {
        q = p->next;	//q保持*p结点后继结点的指针
        pre = L;	//从有序表开头进行比较，pre指向插入*p的前驱结点
        while(pre->next != NULL && pre->next->data < p->data)
        {
            pre = pre->next;	//在有序表中找插入*p的前驱结点*pre
        }
        p->next = pre->next;
        pre-next = p;
        p = q;	//扫描原单链表余下的结点
    }
}

Ⅱ、以建表算法为基础的算法设计

• 单链表有尾插法和头插法两种建表算法

3、双链表

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域。

优点：

• 从任一结点出发可以快速找到其前驱结点和后继结点
• 从任一结点出发可以访问其他结点

类型定义：

typedef struct DNode	//双链表结点类型
{
    ElemType data;
    struct DNode *prior;	//指向前驱结点
    struct DNode *next;		//指向后继结点
}DLinkNode;
//数据 前驱结点 后继结点

①、双链表中结点的插入和删除

②、建立双链表

整体建立双链表也有两种方法：头插法和尾插法。

与单链表的建表算法相似主要是插入和删除的不同。

头插法建立双链表：由含有n个元素的数组a创建带头结点的双链表L。

void CreateListF(DLinkNode *&L, ElemType a[], int n)
{
    DLinkNode *s;
    int i;
    L = (DLinkNode *)malloc(sizeof(DLinkNode));	//创建头结点
    L->prior = L->next = NULL;	//前后指针域置为NULL
    for(i = 0; i < n; i++)	//循环建立数据结点
    {
        s =(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data= a[i];	//创建结点*s
        s->next = L->next;	//将*s 插入到头结点之后
        if(L->next != NULL)		//若L存在数据结点，修改前驱指针
        {
            L->next->prior = s;
        }
        L->next = s;
        s->prior = p;
    }
}

尾插法建立双链表：由含有n个元素的数组a创建带头结点的双链表L。

void CreateListR(DLinkNode *&L, ElemType a[], int n)
{
    DLinkNode *s, *r;
    int i;
    L = (DLinkNode *)malloc(sizeof(DLinkNode));	//创建头结点
    r = L;	//r始终指向尾结点，开始时指向头结点
    for(i = 0; i < n; i++)	//循环建立数据结点
    {
        s = (DLinkNode *)malloc(sizeof(DLinkNode));
        s->data = a[i];	//	创建数据结点*s
        r->next = s;
        s->prior = r;	//将*s 插入 *r之后
        r = s;	//r指向尾结点
    }
    r-next = NULL;	//尾结点next域置为NULL
}

③、线性表基本运算在双链表中的实现

和单链表相比，双链表主要是插入和删除运算不同

插入算法：

bool ListInsert(DLinkNode *&L, int i, ElemType e)
{
    int j = 0;
    DLinkNode *p = L, *s;	//p指向头结点，j置为0
    while(j < i - 1 && p != NULL)	//查找第 i-1个结点
    {
        j++;
        p = p->next;
    }
    if(p == NULL)	//未找到第 i-1 个结点，返回false
    {
        return false;
    }else{		//找到第 i-1 个结点，在其后插入新结点 *s
        s = (DLinkNode *)malloc(sizeof(DLinkNode));
        s->data = e;	//创建新结点 *s
        s->next = p->next;	//在*p结点之后插入 *s结点
        if(p->next != NULL)	//并存在后继结点，修改其前驱指针
        {
            p->next->prior = s;
        }
        s-prior = p;
        p->next = s;
        return true;
    }
}

删除算法:

bool ListDelete(DLinkNode *&L, int i, ElemType &e)
{
    int j = 0;
    DLinkNode *p = L, *q;	//p指向头结点，j设置为0
    while(j < i - 1 && p != NULL)	//查找第 i-1个结点
    {
        j++;
        p = p->next;
    }
    if(p == NULL)	//未找到第 i-1 个结点
    {
        return false;
    }else{		//找到第 i-1 个结点
        q = p->next;	//q指向第 i个结点
        if(q == NULL)	//当不存在第 i个结点时返回false
        {
            return false;
        }
        e = q->data;
        p->next = q->next;	//删除*q结点
        if(p->next != NULL)		//修改前驱指针
        {
            p->next->prior = p;
        }
        free(q);		//释放*q结点
        return true;
    }
}

例子

有一个带头结点的双链表L，设计一个算法将其所有元素逆置，即第一个元素变为最后一个元素，。。。最后一个变为第一个。

采用头插法

void Reverse(DLinkNode *&L)	//双链表结点逆置
{
    DLinkNOde *p = L->next, *q;	//p指向头结点后的第一个结点
    L->next = NULL;	//构造只有头结点的双链表
    while(p != NULL)	//扫描L的数据结点
    {
        q = p->next;	//用q保存其后继结点
        p->next = L->next;		//采用头插法将 *p 结点插入
        if(L->next != NULL)		//修改其前驱指针
        {
            L-next->piror = p;
        }
        L->next = p;	//将新结点作为首结点
        p->prior = L;
        p = q;		//让p 重新指向其后继指针
    }
}

4、循环链表

循环单链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。

循环双链表：形成两个环

结点的类型都相同

①循环单链表

与非循环单链表相比，循环单链表：

• 链表中没有空指针域
• p所指结点为尾结点的条件：p->next == L

②、循环双链表

与非循环双链表相比，循环双链表：

• 链表中没有空指针域
• p所指结点为尾结点的条件：p->next == L
• 一步操作即L->prior可以找到尾结点

int Equal(DLinkNode *L)
{
    int same = 1;
    DLinkNode *p = L->next;	//p指向第一个数据结点
    DLinkNode *q = L->prior;	//q指向最后数据结点
    while(same == 1)
    {
        if(p->data != q-data)
        {
            same = 0;
        }else{
            if(p == 1 || p == q->prior)
            {
                break;
            }else{
                q = q->prior;	//q迁移
                p = p->next;	//p后移
            }
        }
    }
    return same;
}