欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3. 线性表(1)

程序员文章站 2024-03-20 13:17:28
...

  本文是《小甲鱼数据结构》的学习笔记,对视频课程中的相关知识进行总结。

  欢迎大家在评论区多多留言互动~~~~

1. 线性表的定义

  线性表是由零个多个数据元素组成的有限 序列

  这里需要强调几个关键的地方

  (1) 首先他是一个序列,就是元素之间有顺序;
  (2) 若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他的元素都只有一个前驱和后继;
  (3) 线性表强调有限。

  线性表也可以采用数学语言进行定义:若将线性表记为(a1,,ai1,ai,ai+1,,an),如下图所示

3. 线性表(1)

则表中的 ai1 领先于 aiai 领先于 ai+1,称 ai1ai 的直接前驱元素,ai+1ai 的直接后继元素,所以线性表元素的个数 n 定义为线性表的长度,当 n=0 时,称为空表。

2. 抽象数据类型

2.1 数据类型

  数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称,如我们之前所说的整型,浮点型等等。

  在C语言中,按照取值不同,数据类型可以分为两类:
  (1) 原子类型:不可以再分解的基本类型,例如整型、浮点型、字符型等;
  (2) 结构类型:由若干个类型组合而成,是可以再分解的,例如整型数组是由若干整型数组组成的;

2.2 抽象数据类型

  抽象是指抽取出事物具有的普遍性质。他要求抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象时一种思考问题的方式,他隐藏了繁杂的细节。

  对已有的数据类型进行抽象,就有了抽象数据类型。抽象数据类型(Abstract Data Type, ADT)是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于他的一组逻辑特性,而与其在计算机内部如何表示和实现无关。比如1+1=2这样的一个操作,在不同的CPU的处理上可能是不一样的,但是由于其定义的数学特性相同,所以在计算机编程者来看,他们是相同的。

  “抽象”的意义在于数据类型的数学抽象特征。而且抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序是自己定义的数据类型。例如一个 3D 游戏中三个整型数据构成的点。

   抽象数据类型的标准格式如下:

  ADT 抽象数据类型名
  Data
    数据元素之间逻辑关系的定义
  Operation
    操作
  endADT

2.3 线性表的抽象数据类型

  线性表的抽象数据类型定义如下

  ADT 线性表(List)
  Data
    线性表的数据对象集合为 (a1,,ai1,ai,ai+1,,an),每个元素的类型均为 DataTyte(即均为同一种数据类型)。其中,除第一个元素 a1 以外,每一个元素有且只有一个直接前驱元素,除了最后一个元素 an 以外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
  Operation
    InitList(*L):初始化操作,建立一个空的线性表L;
    ListEmpty(L):判断线性表是否为空表,若线性表为空,返回true,否则返回false;
    ClrearList(*L):将线性表清空;
    GetElem(L,i,*e):将线性表L中的第 i 个位置元素返回给e;
    LocateElem(L,e):在线性表L中查找与给定值 e 相等的元素,如果查找成功,返回返回该元素在表中的序号表示成功;否则,返回0表示失败(在这里线性表的序号从1开始而非0);
    ListInssert(*L,i,e):将线性表L中的第 i 个位置插入新元素e;
    ListDelete(*L,i,*e):删除线性表L中的第 i 个位置元素,并用e返回其值;
    ListLength(L):返回线性表L的元素个数;
  endADT

  对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的,对于实际问题中涉及关于线性表的更复杂的操作,完全可以使用这些基本操作的组合来实现。

2.4 实际例子

  用线性表实现两个集合的并集操作,通过分析可知,我们需要使用以下几个基本的操作即可

  -ListLength(L)
  -GetElem(L,i,*e)
  -LocateElem(L,e)
  -ListInssert(*L,i,e)

实现的具体代码如下

void unionL(List *La,list Lb)
{
    int La_len, Lb_len, i;

    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);

    for (i=1; i<=Lb_len;i++)
    {
        GetElem(Lb, i, &e);
        if (!LocateElem(*La,e))
        {
            ListInssert(La,++La_len,e);
            }
        }
    }
}

3. 线性表的顺序储存结构

  线性表具有两种物理存储结构:顺序储存结构和链式储存结构。线性表的顺序储存结构指的是用一段地址连续的存储单元依次存储线性表的数据元素,比如说如下图所示

3. 线性表(1)

是的看起来和数组很像,但是数组的开始是从0开始,而线性表的开始是从1开始。

  物理上存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的内存空间给占了,然后把相同的数据类型的数据元素依次放在这块空地中。

  线性表顺序储存结构代码

#define MAXSIZE 20
typedef int Elemtype;
typedef struct
{
    Elemtype data[MAXSIZE];
    int length;   //线性表当前长度
}SqList;

实际上这里的线性表的顺序存储结构实际上是对数组进行了封装,增加了个当前长度的变量而已。

  总结下,顺序存储结构封装需要三个属性:
  (1) 存储空间的起始位置,数组data,他的存储位置就是线性表存储空间的存储位置;
  (2) 线性表的最大存储容量:数组的长度 MAXSIZE;
  (3) 线性表的当前长度:length。

其中数组的长度与线性表的当前长度需要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会变化的。

3.1 线性表的地址计算方法

  假设 Elemtype 占用的是 c 个存储单元(字节),那么线性表中第 i+1 个数据元素与第 i 个数据元素的存储位置的关系是(LOC表示获得存储位置的函数):

LOC(ai+1)=LOC(ai)+c

所以对于第 i 个数据元素 ai 的存储位置可以由 a1 推算得出
LOC(ai)=LOC(a1)+(i1)c

通过这个公式,可以随时计算出线性表中任意位置的地址,不管他是第一个还是最后一个,都是相同的时间。那么它的存储时间性能当然就为 O(1),通常称为随机存储结构。

3.1.1 读取元素的操作

  实现GetElem的具体操作如下

#define OK 1
#define ERROR 0
#define TURE 1
#define FLASE 0

typedef int Status;
// Status 是函数的类型,其值是函数结果状态代码,如OK 等
// 初始条件:顺序线性表已经存在。1<=i<=ListLength(L)
// 操作结果:用 e 返回 L 中第 i 个数据元素的值

Status GetElem(SqList L,int i,Elemtype *e)
{
    if(L.length==0|| i<1||i>L.length)
    {
        return ERROR;
    }
    *e = L.data[i-1];

    return OK;
}

3.1.2 插入元素的操作

  考虑实现插入算法,其主要思路如下

  (1) 如果插入位置不合理,抛出异常;
  (2) 如果线性表长度大于等于数组长度,则抛出异常或者动态增加数组数量;
  (3) 从最后一个元素开始向前遍历到第 i 个位置,分别将他们都向后移动一个位置。
  (4)将要插入的元素填入位置i 处
  (5) 线性表长 +1

代码如下

/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L) */
/*操作结果:在L中第i 个位置之前插入新的数据元素 e,L长度 +1 */

Status ListInsert (SqList L,int i,Elemtype *e)
{
    int k;

    if (L->length == MAXSIZE)
    {
        return ERROR;
    }
    if (i<1 || i>L->length+1)
    {
        return ERROR;
    }
    if (i<=L->length)
    {
        /*将要插入位置后的数据元素向后移动1位 */
        for (k=L->length-1;k>=i-1;k--)
        {
            L-data[k+1] = L-data[k];
        }
    }
    L->data[i-1]=e;
    L->length++;

    renturn OK;
}

在编程的过程中一点需要注意,虽然线性表的下标从1开始,但是线性表的内部实际上是一个数组,是从0开始的,插入某个元素实际上是向数组中插入一个元素,所以 for (k=L->length-1;k>=i-1;k--)就是为了保证与数组的下表相对应。

3.1.3 删除元素的操作

  考虑实现删除算法,其主要思路如下

  (1) 如果删除位置不合理,抛出异常;
  (2) 去除删除元素;
  (3) 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置

代码如下

/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L) */
/*操作结果:在L中第i 个位置之前插入新的数据元素 e,L长度 +1 */

/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L) */
/*操作结果:在L中第i 个位置之前插入新的数据元素 e,L长度 +1 */

Status ListDelete (SqList L,int i,Elemtype *e)
{
    int k;

    if (L->length == 0)
    {
        return ERROR;
    }
    if (i<1 || i>L->length)
    {
        return ERROR;
    }

    *e = L->data[i-1]

    if (i<L->length)
    {
        for (k=i;k<L->length;k++)
        {
            L->data[k-1] = L->data[k];
        }
    }
    L->length--;

    renturn OK;
}

3.1.4 插入和删除的时间复杂度分析

  显而易见地,最好的复杂度是 O(1),而最坏的复杂度是 O(n),因此平均下来的复杂度是 O(n+12) ,所以这两种的操作的复杂度就是 O(n)。

3.2 线性表顺序存储结构的优缺点

   线性表顺序存储结构,在存、读数据的时候,不管是在哪个位置,时间复杂度都是 O(1);而在插入数据时,时间复杂度都是 O(n)。这说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作时存取数据的应用。

  综上线性表顺序存储结构的优点有:

  (1) 无需为表示表中元素之间的逻辑关系而增加额外的存储空间;
  (2) 可以快速地存储表中任意位置的元素;

  缺点有:

  (1) 插入和删除操作需要移动大量元素;
  (2) 当线性表长度变化比较大的时候,难以确定存储空间的容量;
  (3) 容易造成储存空间的“碎片”;

4. 线性表的链式存储结构

  正是由于顺序存储结构不易于插入和删除元素,链式存储结构才显得很重要。线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的元素,这组存储单元可以存在内存中未被占用的任意位置。比起顺序储存结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中,除了要存储数据元素信息之外,还要存储它的后继元素的存储地址(指针)。

  把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或者链。这两部分信息组成数据元素称为存储映像,称为节点(node)。n 个结点链接成一个链表,即为线性表 (a1,,ai1,ai,ai+1,,an) 的链式存储结构。因为此链表中的每个结点只包含一个指针域,所以叫做单链表,如下图所示

3. 线性表(1)

在上面的链表中,总得有个头有个尾,链表也是相同的。我们把链表中的第一个结点的存储位置叫做头指针,最后一个结点指针为空(NULL)。

4.1 头指针与头结点的区别

  头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。头指针具有标识作用,所以常用头指针冠以链表的名字(指针变量的名字)。但是无论链表是否为空,头指针均不为空,头指针是链表的必要元素。

  头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(但也可以用来存放链表的长度)。有了头结点,对在第一元素结点之前插入结点和删除第一结点起操作与其他结点的操作就统一了。头结点不一定是链表的必须元素。

4.2 单链表的存储结构

  单链表的存储结构存储结构如下图所示

3. 线性表(1)

在 c 语言中可以用结构指针来描述单链表

typedef struct Node
{
    ElemType data;             //数据域
    struct Node* Next;         //指针域
} Node;
typedef struct Node* LinkList;

假设 p 是指向线性表第 i 个元素的指针,则该结点 ai 的数据域我们可以用 p->data的值表示,结点 ai 的指针域可以用 p->next来表示, 他是指向下一个结点的指针。

  如果 p->data = ai,那么 p->next->data是什么呢?很简单,答案就是 ai+1 。

4.2.1 单链表读取元素操作

  在线性表的顺序存储结构中,我们要计算任意一个元素的存储位置是很容易的,找到第一个元素之后,按照次序一直找下去就可以找到对应的元素,所以在单链表上数据的操作 GetElem 的算法思路如下

  (1) 声明一个结点 p 指向链表第一个结点,初始化 j 从1 开始;
  (2) 当 j< i 时,就遍历链表,让 p 的指针向后移动,不断指向下一结点,j+1;
  (3) 若到链表末尾 p 为空,则说明第 i 个元素不在;
  (4) 否则查找成功,返回结点 p 的数据。

  实现GetElem的具体操作如下

/* 初始条件:顺序线性表已经存在。1<=i<=ListLength(L)*/
/* 操作结果:用e 返回L中第i个数据元素的值*/

Status GetElem(SqList L,int i,Elemtype *e)
{
    int j;
    LinkList p;

    p = L->next;
    j = 1;

    while ( p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>i)
    {
        return ERROR;
    }

    *e = p->data;

    return OK;
}

上面这段代码的思路在于,他首先初始化了一个计数器 j,之后将指针指向第一个元素;当指针存在且 j 还没有达到 i 的大小,则继续找,如果找到了就退出循环;如果找到最后都没有找到(p为空),或者 大于指定的位置(i>j),那么均会返回错误,否则返回找到的数值。

  直观来讲就是从头开始找,直到第 i 个元素位置。由于这个算法的时间取决于所找元素的位置,所以它的时间复杂度为 O(n)。由于单链表结构中没有定义表长,所以不知道要循环多少次,因此也就不方便使用 for 控制循环。其核心思想叫做“工作指针后移”,这其实也是很多算法的常用技术。

4.2.2 单链表的插入

  假设存储元素 e 的结点为 s ,要实现结点 p ,p->next 和 s 之间的逻辑关系的变化,可以参考下面的图进行思考

3. 线性表(1)

如上图所示,我们需要做的就是在数据 ai 所对应的结点和数据 ai+1 所对应的结点之间增加一个结点 s 。增加这个结点并不需要改变其他结点,只需要让 s->next 和 p->next 的指针做一点改变即可,如下所示

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

在上面的过程中,可以认为等号左边的是符号,右边的是符号对应的具体的数值。所以上面的过程实际上是指针倒着赋值的过程,首先将 p->next 的值赋值给 s->next,让 s 的下一个结点是地址 p->next;接下来将 s 的值赋值给 p->next,让 p 的下一个结点的地址是 s 。

  但是考虑下面给的过程则是不可以的

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

在这个过程中先将 s 的值赋值给 p->next,再将 p->next 的值赋值给 s->next,这样 s->next =s ,自己的下一个元素的地址还是自己,就会陷入死循环,所以是不可以的。

  单链表第 i 个数据插入结点的算法思路:

  (1) 声明一结点 p 指向链表头结点,初始化 j 从 1 开始;
  (2) 当 j< i 时,就遍历链表,让 p 的指针向后移动,不断指向下一结点,j 累加1;
  (3) 若到链表末尾 p 为空,则说明第 i 个元素不存在;
  (4) 否则查找成功,在系统中生成一个空结点 s;
  (5) 将数据元素 e 赋值给 s->data;
  (6) 向单链表插入刚才来的两个标准语句;
  (7) 返回成功。

Status ListInsert (LinkList *L,int i,Elemtype e)
{
    int j;
    LinkList p,s;

    p = *L;
    j = 1;

    while ( p && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j>i)
    {
        return ERROR;
    }

    s = (LinkList)malloc(sizeof(Node));
    s->data = e;

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

    return OK;
}

4.2.3 单链表的删除

  单链表的删除操作如下图所示

3. 线性表(1)

假设元素 a2 的结点为 q,要实现结点 q 删除单链表的操作,其实就是将他的前继结点的指针绕过,指向后继节点即可。那我们所做的就是下面两种实现方式之一就好

p->next = p->next->next;           //方法1
q = p->next;p->next = q->next;    //方法2

第一种实现方式十分直观,将下下个结点的指针赋值给 p->next,这让就绕开了结点 q。另一种实现的方法是一种比较婉转的方法,它首先将 p->next 赋值给 q,再将 q->next 赋值给 p->next 同样实现了绕过 q 点的功能。

  单链表第 i 个数据删除结点的算法思路:

  (1) 声明一结点 p 指向链表头结点,初始化 j 从 1 开始;
  (2) 当 j< i 时,就遍历链表,让 p 的指针向后移动,不断指向下一结点,j 累加1;
  (3) 若到链表末尾 p 为空,则说明第 i 个元素不存在;
  (4) 否则查找成功,将欲删除结点 p->next 赋值给 q;
  (5) 单链表的删除标准语句 p->next = q->next;
  (6) 将 q 结点中的数据赋值给 e,作为返回;
  (7) 释放 q 结点。

其中的(5)(6)可以合并为 1 步,即p->next = p->next->next;。分析上述代码可知,大部分执行的操作是相通的,只不过一个是插入,而另一个是删除。这里给出实现的代码如下

Status ListInsert (LinkList *L,int i,Elemtype *e)
{
    int j;
    LinkList p,s;

    p = *L;
    j = 1;

    while ( p->next && j<i)
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j>i)
    {
        return ERROR;
    }

    q = p->next;
    p->next = q->next; 

    *e = q->data;
    free(q);

    return OK;
}

5. 线性表的顺序存储结构域链式存储结构效率比较

  我们可以看到对于单链表,无论是插入还是删除,他的复杂度都是 O(n),那么单链表的优势在于什么呢?加入我们希望从第 i 个位置开始,插入连续 10 个元素,对于顺序存储结构意味着每一次插入都需要移动 n-i 个位置,所以每次都是 O(n)。但是对于单链表,我们只需要在第一次时,找到第 i 个位置的指针,此时为 O(n),接下来只是简单地通过赋值移动指针而已,时间复杂度都是 O(1)。

  显然,对于插入或者删除数据越频繁的操作,单链表的效率优势就越明显。

6. 单链表的整表创建

  对于顺序储存结构的线性表的整表创建,我们可以使用数组的初始化直观理解。而单链表和顺序存储结构就不一样了,它不像顺序存储结构那么集中,他的数据可以是分散在内存的各个角落,他的增长是动态的的。对于每个链表来说,它占用的空间大小和位置是不需要预先分配划定的,可以根据系统的情况和实际的需求即时生成。

  创建单链表的过程是一个动态生成链表的过程,从“空表”的初始状态起,依次建立各个元素结点并逐个插入链表,所以单链表的整表创建的算法思路如下

  (1) 声明一结点 p 和计数变量 i;
  (2) 初始化一空链表 L;
  (3) 让 L 的头结点的指针指向NULL,即建立一个带头节点的单链表;
  (4) 循环实现后继结点的赋值和插入。

6.1 头插法建立单链表

  头插法从一个空表开始,生成新结点,读取数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。简单来说就是把新加进的元素放在表头后的第一个位置,实际上就是现实生活中的插队,并且每一次都直接插在第一位的位置。具体过程如下图所示

3. 线性表(1)

可见我们输入数据的顺序是正的,但是创建的链表的顺序是倒序的,造成这种现象的原因正是因为头插造成的。

  具体的实现代码如下

/* 头插法建立单链表实例 */

void CreatListHead(LinkList *L,int n)
{
    LinkList p;
    int i;

    scand(time(0));     //根据时间给出随机初始化种子

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for (i=0; i<n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

分析这一段代码,其中scand 是随机初始化的种子,后面给链表赋值的数值最准备。之后建立一个结点,让这个结点的指针为NULL,表明这是一个头结点。在循环中,创立一个临时结点p ,之后用随机数给这个结点赋值,其中rand()%100+1产生的是1~100的数。p->next = (*L)->next;是将 p 与之前的结点相连,而(*L)->next = p;是将 p 设置为头结点。

6.2 尾插法建立单链表

  头插法建立链表虽然简单,但是生成的链表的节点顺序域输入的顺序相反,这个时候就需要使用尾插法产生顺序相同的链表。

3. 线性表(1)

  具体的实现代码如下

/* 头插法建立单链表实例 */

void CreatListHead(LinkList *L,int n)
{
    LinkList p, r;
    int i;

    scand(time(0));     //根据时间给出随机初始化种子

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;             //指向尾部的结点

    for (i=0; i<n; i++)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;           //将尾部更新
    }

    r->next = NULL;
}

分析上面这段代码可以知道,尾插法与头插法十分相似,不同的地方在于这里有一个 r 用于指向尾部的结点;在 for 循环中,r->next = p; r = p; 这两句话的含义就是,因为 r 是指向尾部的嘛~所以第一句的意思是将 p 与链表相连,第二句话的意思是,这个时候 r 已经不在尾部了,这个时候 p 是尾部,所以为了保持 r 仍然是尾部,令 r = p

7. 单链表的整表删除

  当单链表不在需要的时候,可以对单链表进行整表删除。将链表删除可以留出空间给其他程序或软件使用。单链表的整表删除的算法思路如下

  (1) 声明结点 p 和 q;
  (2) 将第一个结点赋值给 p,下一个结点赋值给 q;
  (3) 循环执行释放 p 和将 q 赋值给 p 的操作。

  代码如下

Status ClearList(LinkList *L)
{
    LinkList p ,q;

    p = (*L)->next;

    while (p)
    {
        q = p -> next;
        free (p);
        p =q ;
    }
    (*L) = NULL;

    return OK;
}

在上面的代码中 q 是不能省略的,因为释放的过程中不仅仅释放了数据域,也释放了指针域,所以将 p 删除后,没有 q 接着就会使得后面的元素无法被删除。

8. 单链表结构与顺序存储结构的优缺点

  下面从存储分配方式、时间性能和空间性能三个方面进行对比。

  存储分配方式
  (1) 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;
  (2) 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

  时间性能
  (1) 查找:顺序存储结构O(1),单链表O(n);
  (2) 插入和删除:顺序存储结构无论多少个都是 O(n),单链表只有第一个是 O(n),剩下的都是 O(1)。

  空间性能
  (1) 顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出;
  (2) 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。

  综上对比,给出一些经验性结论
  (1) 若线性表需要频繁查找,很少进行插入和删除操作,宜用顺序存储结构;如网站中的个人信息等。
  (2) 若需要频繁插入和删除时,宜采用单链表结构,如游戏账户中的装备信息等。
  (3) 线性表中元素多的个数变化较大或者根本不知道有多大时,最好使用单链表,这样可以不用考虑存储空间的大小问题。
  (4) 如果事先知道线性表的大致长度就可以使用顺序存储结构。

综合两者各有千秋,要根据实际情况进行选择。