[线性表](2)链式线性表

从顺序线性结构的学习可以知道,线性表的顺序存储结构的特点是:

  • 逻辑关系上相邻的两个元素在物理位置上也相邻

    • 因此可以随机存取表中任一元素它的

然而,这个特点就铸成了这种存储结构的弱点:在作插入或删除操作时,需要移动大量的元素。

链式存储结构,它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随即存取的优点

线性链表

线性表的链式存储结构的特点是,用一组任意的 存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

因此,为了表示每个数据元素ai,与其直接后继数据元素a(i+1)之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其后继存储(即直接后继的存储位置)。

这两部分的信息组成元素ai的存储映像,称为结点(node)

  • 它包括两个域:

    • 其中存储数据元素信息的域称为数据域
    • 存储直接后继位置的域称为

    指针域

    • 指针域中存储的信息称为指针

n个结点(ai(1<=i<=n)的存储映像)链结成一个链表,即为线性表(a1,a2,...,an)的链式存储结构

又由于此链表的每个结点只包含一个指针域,故又称线性链表单链表

通过以下例子来了解

线性表:(ZHAQ,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)

的链表存储结构,整个链表的存储必须从头指针开始,头指针指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置,同时,由于最后一个数据元素没有直接后继,则线性表中最后一个结点的指针为“空”(NULL)

img上述线性表描述图

用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的,换句话说,指针为数据元素之间的逻辑关系映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求相邻,由此,这种存储结构为非顺序映像或链式映像

通常,我们把链表画出用箭头相链接的结点的序列,结点之间的箭头表示链域中的指针

如下图所示,这是因为在使用链表时,关心的只是它所表示的线性表中数据元素之间的逻辑顺序,而不是每个数据元素在存储器中的实际位置

img线性链表的逻辑状态

由上述可见,单链表可由头指针惟一确定,在C语音中可用“结构指针”来描述

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

其中data为数据域,next为指针域。

假设L是LinkList型的变量,则L为单链表的头指针,它指向表中第一个结点。若L为“空”(NULL)则所表示的线性表为“空”表,则长度n为零。有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点

头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个节点的指针(即第一个元素结点的存储位置)

若链表为空,则头结点的指针域不存放数据。如下图所示

img

在线性表的顺序存储结构中,由于逻辑上相邻的两个元素在物理位置上相邻,则每个元素的存储位置都可从线性表的起始位置计算得到。

而在单向链表中,任何两个元素的存储位置之间没有固定的联系。然而,每个元素的存储位置都包含在其直接前驱结点的存储信息之中。

假设p是指向线性表中第i个数据元素(结点a1)的指针,则p->next是指向第i+1个元素的指针,通俗点说,若p->data=ai,则p->next->data=ai+1

由此,在单链表中,取得第i个数据元素必须从头指针出发寻找,因此,单链表是非随机存取的存储结构,看看GetElem函数在单链表中的实现

Status GetElem_L(LinkList L, int i, ElemType& e)
//L为带头结点的单链表的头指针
//当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
{
    p = L->next;//初始化,p指向第一个结点,j为计数器
    j = 1;
    while (p != NULL && j < 1)//顺指针向后查找,直到p指向第i个元素或p为空
    {
        p = p->next;
        ++j;
    }

    if (p == NULL || j > i)//第i元素不存在
    {
        return ERROR;
    }
    e = p->data;//取第i个元素
    return OK;

}

C语言实现:

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
typedef struct LinkList
{
    int data;
    struct LinkList* next;
}LinkList;
 LinkList *L;

 int main()
{
    int i, e;
    scanf("%d", &i);
    L = (LinkList*)malloc(sizeof(LinkList));
    L->next = NULL;

    GetElem_L(L, i, &e);
    system("pause");
    return 0;
}
int GetElem_L(LinkList *L, int i, int* e)
//L为带头结点的单链表的头指针
//当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
{
    LinkList* p;
    int j;
    p=L->next;//初始化,p指向第一个结点,j为计数器
    j = 1;
    while (p != NULL && j < 1)//顺指针向后查找,直到p指向第i个元素或p为空
    {
        p = p->next;
        ++j;
    }

    if (p == NULL || j > i)//第i元素不存在
    {
        printf("i不存在\n");
        return 1;
    }
    e = p->next;//取第i个元素
    return 0;
}

上述算法的基本操作是比较j和i并后移指针p,while循环体中的语句频度与被查元素在表中位置有关,若1<=i<=n,则频度为i-1否则频度为n。

通俗来说,运气好,第一个就是,运气不好,最后一个才是,要找到i元素,必须遍历整个链表,一个一个去看,因此,时间复杂度为O(n)

插入和删除

在单链表中,又如何实现“插入”和“删除”两项功能

假设我们要在线性表的两个元素a和b之间插入一个数据元素x,已知p为其单链表存储结构中指向结点a的指针,如下图所示:

img

为插入数据元素x,首先要生成一个数据域为x的结点,然后插入在单链表中,根据插入操作的逻辑定义,还需要修改结点a中的指针域,使其指向结点x,而结点x中的指针域应指向结点b,从而实现3个元素a、b和x之间逻辑关系的变化。

假设s为指向结点x的指针,则上述指针修改用代码描述即为:

  • s->next=p->next;
  • p->next=s;

反之。如果要删除线性表中元素的元素,则如下图所示:

img

需要再线性表中删除元素b的时候,仅需修改结点a中的指针域即可,假设p为指向结点a的指针,则修改指针的语句为:

p->next=p->next->next

可见,在已知链表中元素插入或删除的确切位置的情况下,在单链表中插入或删除一个结点时,进需要修改指针,而不需要移动元素。

ListInsert和ListDelete在单链表中实现如下:(抽象代码)

Status ListInsert_L(LinkList& L, int i, ElemType e)
//在带头结点的单链线性表L中第i个位置之前插入元素e
{
    p = L;
    j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        ++j;
    }//寻找第i-1个结点

    if (p == NULL || j > i - 1)//i小于1或大于表长+1
    {
        return ERROR;
    }
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

删除:

Status ListDelete_L(LinkList& L, int i, ElemType& e)
//在带头结点的单链表L中,删除第i个元素,并由e返回其值
{
    p = L;
    j = 0;

    while (p->next != NULL && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    if (p->next == NULL || j > i - 1)
    {
        return ERROR//删除位置不合理
    }
    q = p->next;
    p->next = q->next;//将e保存删除结点中的数据域
    e = q->data;
    free(q);//删除并释放结点
    return OK
}

以上:创建,生成,插入,删除功能利用C语言实现测试代码如下:

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
    int data;
    struct LNode* next;
    int i;
}LNode,*LinkList;
LinkList L, s, node, p;
void GetElem_L(LinkList, int, int*);//查找
void ListInsert_L(LinkList, int, int*);//插入
void ListDelete_L(LinkList, int, int*);//删除

 int main()
{
    
    int a = 10;
    L = (LinkList)malloc(sizeof(LNode));
    L->i = 0;
    L->next = NULL;

    while (a)
    {
        s = L;
        int j;
        scanf("%d", &j);
        node = (LinkList)malloc(sizeof(LNode));
        node->data = j;
        L->i++;
        printf("当前有:%d个结点\n", L->i);
        if (s->next == NULL)
        {
            s->next = node;
            node->next = NULL;
        }
        else
        {
            while (s->next != NULL)
            {
                s = s->next;
            }
            s->next = node;
            node->next = NULL;
        }
        a--;
    }

    int i, e;
    printf("请输入i值:");
    scanf("%d", &i);
    
    
    GetElem_L(L, i, &e);
    printf("%d\n", e);

    printf("请输入需要插入的位置:");
    scanf("%d", &i);
    printf("请输入需要插入的元素:");
    scanf("%d", &e);
    ListInsert_L(L, i, &e);
    
    printf("请输入需要删除的位置:");
    scanf("%d", &i);
    ListDelete_L(L, i, &e);
    printf("删除的元素值为:%d\n", e);


    system("pause");
    return 0;
}
void GetElem_L(LinkList L, int i, int* e)
{
    LinkList p;
    int j;
    p = L->next;//初始化,p指向第一个结点,j为计数器
    j = 1;

    while (p != NULL && j < i)//顺指针向后查找,直到p指向第i个元素或p为空
    {
        p = p->next;
        ++j;
    }

    if (p == NULL || j > i)//第i元素不存在
    {
        printf("i不存在\n");
        return 1;
    }
    *e = p->data;//取第i个元素
}


void ListInsert_L(LinkList L, int i, int* e)
//在带头结点的单链线性表L中第i个位置之前插入元素e
{
    int j;
    p = L;
    j = 0;
    while (p->next != NULL && j < i - 1)
    {
        p = p->next;
        ++j;
    }//寻找第i-1个结点

    if (p->next == NULL || j > i-1)//i小于1或大于表长+1
    {
        printf("插入位置不合法\n");
        return 0;
    }
    
    
    node = (LinkList)malloc(sizeof(LNode));
    node->data = *e;
    
    node->next = p->next;
    p->next = node;
    printf("插入成功\n");
    L->i++;
    
    
    printf("当前L链表元素为:\n");
    s = L->next;
    while (s != NULL)
    {
        printf("data:%d\n", s->data);
        s = s->next;
    }
    printf("共%d个结点\n", L->i);
}

void ListDelete_L(LinkList L, int i, int* e)
//在带头结点的单链表L中,删除第i个元素,并由e返回其值
{
    LinkList q;
    p = L;
    int j;
    j = 0;

    while (p->next != NULL && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    if (p->next == NULL || j > i - 1)
    {
        printf("删除位置不合理\n");
        return 0;//删除位置不合理
    }
    
    q = p->next;
    p->next = q->next;//将e保存删除结点中的数据域
    e = q->data;
    free(q);//删除并释放结点
    printf("删除成功");
    L->i--;


    printf("当前L链表元素为:\n");
    s = L->next;
    while (s != NULL)
    {
        printf("data:%d\n", s->data);
        s = s->next;
    }
    printf("共%d个结点\n", L->i);

    return 1;

}

VS2019环境下测试成功,测试结果:

img

可以看出,插入和删除的时间复杂度为O(n),这是因为在第i个结点之前插入一个新结点或者删除第i个结点,都必须先找到第i-1个结点,即需修改指针的结点

上述使用的为C语言代码实现,抽象代码中引用了malloc和free两个stdC函数,通常

在设有“指针”数据类型的高级语言中,均存在与其相应的过程或函数,假设p和q是LinkLinst型变量,则执行p=(LinkList)malloc(sizeof(LNode))的作用是由系统生成一个LNode型的结点,同时将该结点的起始位置赋给指针变量p;

反之,指向free(q)的作用是由系统回收一个LNode型的结点,回收后的空间可以备作再次生成结点时用。

因此,单链表和顺序结构不同,它是一种动态结构,整个可用存储空间可为多个链表共同想用,每个链表占用的空间不需预先分配划定,而是可以由系统应需求即使生成。

由此,建立线性表的链式存储结构的过程就是一个动态生成链表的过程,即从“空表”的初始状态起,依次建立各元素结点,并逐次插进链表。

下列讨论一个从表尾到表头的逆向建立单链表的算法,时间复杂度为O(n)

Status CreateList_L(LinkList& L, int n)
//逆位序输入n个元素的值,建立带表头结点的单链线性表L
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;//初始化头结点
    
    for (i = n; i > 0; --1)
    {
        p = (LinkList)malloc(sizeof(LNode));//生成新的结点
        scanf(&p->data);
        p->next = L->next;//插入到表头
        L->next = p;
    }
}

下面来看看如何将两个有序链表并为一个有序链表

假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构,现要归并La和Lb得到单链表Lc,按照之前归并数组的思想,需设立3个指针,pa、pb和pc。

其中pa和pb分别指向La表和Lb表中当前待比较插入的结点,而pc指向Lc表中当前最后一个结点,若pa->data<=pb->data,则将pa所指结点链接到pc所指结点之后。

否则将pb所指结点链接到pc所指结点之后,显然,指针的初始状态为:当LA和LB为非空表时,pa和pb分别指向La和Lb表中的第一个结点,否则为空

pc指向空表中的头结点。由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个为空时,说明有一个表的元素已归并完,则只要将另一个表的剩余段链接在pc所指结点以后即可,代码如下:

void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)
//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列
{
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La;//用La的头结点作为Lc的头结点

    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa ? pa : pb;//插入生与段
        free(Lb);//释放Lb的头结点
    }
}

C语言实现为:

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
    int data;
    struct LNode* next;

}LNode,*LinkList;

LinkList La, Lb, Lc, node, s;

void MergeList_L(LinkList , LinkList , LinkList );

int main()
{
    int i = 10;

    La = (LinkList)malloc(sizeof(LNode));
    La->next = NULL;
    printf("请输入La的值:\n");
    while (i)
    {
        s = La;
        node = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &node->data);
        if (s->next == NULL)
        {
            s->next = node;
            node->next = NULL;
        }
        else
        {
            while (s->next != NULL)
            {
                s = s->next;
            }
            s->next = node;
            node->next = NULL;
        }
        i--;
    }

    printf("请输入Lb中的值:\n");
    i = 10;
    Lb = (LinkList)malloc(sizeof(LNode));
    Lb->next = NULL;
    while (i)
    {
        s = Lb;
        node = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &node->data);
        if (s->next == NULL)
        {
            s->next = node;
            node->next = NULL;
        }
        else
        {
            while (s->next != NULL)
            {
                s = s->next;
            }
            s->next = node;
            node->next = NULL;
        }
        i--;
    }


    MergeList_L(La, Lb, Lc);
    Lc = La;
    s = La->next;
    while (s != NULL)
    {
        printf("%d ", s->data);
        s = s->next;
    }

    system("pause");
    return 0;

}

void MergeList_L(LinkList La, LinkList Lb, LinkList Lc)
//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列
{
    LinkList pa, pb, pc;
    pa = La->next;
    pb = Lb->next;
    pc = La;//用La的头结点作为Lc的头结点

    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa ? pa : pb;//插入剩余段//释放Lb的头结点
    }
    free(Lb);
}

VS2019环境下测试成功,测试结果如下:

img

思路如下图所示:

img

在归并两个链表为一个链表时,不需要另建新表的结点空间,只需要将原来一个链表中结点之间的关系解除,再依次保存后继结点的位置,不断的访问作比较,将满足条件的结点插到新的结点当中即可

本文链接:

https://nullcode.fun/7.html
1 + 3 =
快来做第一个评论的人吧~