1. 首页
  2. 文章中心
  3. 数据结构

数据结构--3.线性表3.线性表

72 阅读 0 评论
我是靠谱客的博主 甜美山水，最近开发中收集的这篇文章主要介绍数据结构--3.线性表3.线性表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

3.线性表

本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。
考核要求：
识记：线性结构的概念、线性表的概念
掌握：线性表的链式存储结构、顺序表与链表的比较
应用：线性表的顺序存储结构，插入、删除和定位运算在单链表上的实现

3.1线性表的定义

零个或多个数据元素的有限序列

它是一个序列，就是说元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继其他每个元素都有且仅有一个前驱和后继

同时，线性表强调有限，元素个数是有限的

用数学语言定义如下

在这里插入图片描述

3.2线性表的抽象数据类型

定义如下

ADT 线性表(List)
Data
    线性表的数据对象集合为(a1,a2,...an),每个元素的类型均为DataType。
    其中，除第一元素a1外，每一个元素有且仅有一个直接前驱元素，
    除了最后一个元素an外，每一个元素有且仅有一个直接后继元素，
    数据元素之间的关系是一对一的关系。

Operation
    InitList(*L);  初始化操作，建立一个空的线性表L；
    ListEmpty(L);  若线性表为空，返回true，否则返回false。
    ClearList(*L);  将线性表清空。
    GetElem(L,i,*e); 将线性表L中的第i个位置元素值返回给e
	LocateElem(L,e); 在线性表L中查询与给定值e相等的元素，
	如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
	ListInsert(*L,i,e); 在线性表L中的第i个位置插入新元素e。
	ListDelete(*L,i,*e); 删除线性表L中第i个位置元素，并且e返回其值。
	ListLength(L);   返回线性表L的元素个数
endADT

对于不同应用，线性表基本操作不同，对于更复杂的操作，可以用这些基本操作的组合实现。

例如，实现两个线性表A和B的并集操作，即A=A U B。可以循环集合B的元素，判断是否存在A中，若不存在，插入即可

假设La表示集合A，Lb表示集合B，实现代码如下

//将所有的在线性表Lb中但不在La中的数据元素插入La中
void union(List *La,List Lb)
{
    int La_len,Lb_len,i;
    ElemType e;			//声明与La和Lb相同的数据元素e
    La_len=ListLength(La);//求线性表的长度
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,e) //取Lb中第i个数据元素赋给e
        if(!LocateElem(La,e,equal))  //La中不存在和e相同数据元素
            ListInsert(La,++La_len,e);
    }
}

3.3线性表的顺序存储结构

顺序存储定义

指的是用一段地址连续的存储单元依次存储线性表的数据元素

顺序存储方式

因为每个数据元素类型相同，所以可以用一维数组来实现顺序存储结构

结构代码

#define MAXSIZE 20  //存储空间初始分配量
typedef int ElemType //ElemType类型根据实际情况而定，这里假设为int
typedef struct
{
    ElemType data[MAXSIZE]; //数组存储数据元素，最大值为MAXSIZE;
    int length;   //线性表当前长度
}sqList;

描述顺序存储结构需要三个属性

  • 存储空间的起始位置，数组data，它的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量，数组长度maxsize
  • 线性表的当前长度 length

数据长度与线性表长度的区别

数组长度是存放线性表的存储空间的长度

线性表长度是线性表中数据元素的个数

在任意时刻，线性表长度应该小于或等于数组长度

地址计算方法

因为C语言的数组从0开始下标，所以线性表的第i个元素要存储在数组下标为i-1的位置，对应关系如图

在这里插入图片描述

由于线性表可以插入，删除等操作，因此分配的数组空间要大于等于当前线性表长度

存储器中的每个存储单元都有自己的编号，这个编号称为地址

因为不同数据类型占用空间不同，假设占用c个存储单元，那么线性表中第i+1个数据元素和第i个数据元素的存储位置满足下列关系(LOC表示存储位置的函数)

在这里插入图片描述

通过这个公式，可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为0(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

3.4顺序存储结构的插入与删除

获取元素操作

对于线性表的顺序存储结构来说，实现GetElem操作，即将线性表L中的第i个位置元素值返回。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。代码如下

#define ok 1
#define error 0
#define true 1
#define false 0
typedef int Status;//Status是函数的类型，其值是函数结果状态代码，如ok等
//初始条件 顺序线性表L已存在，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;
}

这里返回值类型Status是一个整性，返回ok代表1，error代表0.

插入操作

插入算法思路

  • 如果插入位置不合理，抛出异常；
  • 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
  • 从最后一个元素开始向前遍历到第1个位置，分别将它们都向后移动一个位置；
  • 将要插入元素填入位置i处；
  • 表长加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)//当i不在范围内
        return error;
    if(i<=L->length)//若插入数据位置不在表尾
    {
        for(k=L->length-1;k>=i-1;k--)//将要插入位置后数据元素巷后移动一位
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;//新元素插入
    L->length++;
    return ok;
}

删除操作

删除算法思路

  • 如果删除位置不合理，抛出异常；
  • 取出删除元素；
  • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
  • 表长减1。
/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)*/
/*操作结果：删除L的第1个数据元素，并用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->1ength;k++)/*将删除位置后继元素前移*/
			L->data[k-1]=L->data[k];
    }
	L->length--;
	return OK;
}

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

优点

- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素

缺点

- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”

3.5线性表的链式存储结构

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
头指针与头节点的异同

头指针

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

头结点

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

线性表链式存储结构代码描述

若线性表为空表，则头结点的指针域为“空”

在这里插入图片描述
在这里插入图片描述

单链表中，我们在C语言中可用结构指针来描述

//线性表的单链表存储结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

在这里插入图片描述

3.6单链表的读取

获取链表第i个数据的算法思路

  • 声明一个结点p指向链表第一个结点，初始化j从1开始；
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
  • 若到链表末尾p为空，则说明第i个元素不存在；
  • 否则查找成功，返回结点p的数据。
//初始条件 链表已经存在 1<=i<=ListLength(L)
//操作结果 用e返回L中第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;//声明一结点p
    p=L->next;//让p指向链表L的第一个结点
    j=1;//j为计数器
    while(p && j<1)//p不为空或计数器j还没等于i时，循环继续
    {
        p=p->next;//让p指向下一个结点
        ++j;
    }
    if(!p || j>i)
        return error;//第i个元素不存在
    *e=p->data;//取第i个元素的数据
    return ok;
}

由于单链表的结构没有定义表长，所以不能事先知道循环多少次，因此不方便使用for循环

3.7单链表的插入与删除

插入

在这里插入图片描述
在这里插入图片描述

单链表第i个元素插入结点的算法思路

  • 声明一结点p指向链表第一个结点，初始化j从1开始；
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
  • 若到链表末尾p为空，则说明第i个元素不存在；
  • 否则查找成功，在系统中生成一个空结点s;
  • 将数据元素e赋值给s->data;
  • 单链表的插入标准语句s->next=p->next; p->next=s;
  • 返回成功。
//初始条件 链表已经存在 1<=i<=ListLength(L)
//操作结果 在L中第i个位置之前插入新的元素e，L的长度+1
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p=*L;
    j=1;
    while(p && j<1)//寻找第i个结点
    {
        p=p->next;
        ++j;
    }
    if(!p || j>i)
        return error;//第i个元素不存在
    s=(LinkList)malloc(sizeof(Node));//生产新结点(c标准函数)
    s->data=e;
    s->next=p->next;//将p的后继结点赋值给s的后继
    p->next=s;		//将s赋值给p的后继
    return ok;
}

删除

在这里插入图片描述

单链表第i个元素删除结点的算法思路

  • 声明一结点p指向链表第一个结点，初始化j从1开始
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;
  • 若到链表末尾p为空，则说明第i个元素不存在；
  • 否则查找成功，将欲删除的结点p->next赋值给q;
  • 单链表的删除标准语句p->next=q->next;
  • 将q结点中的数据赋值给e,作为返回；
  • 释放q结点；
  • 返回成功。
//初始条件 链表已经存在 1<=i<=ListLength(L)
//操作结果 删除L的第i个数据元素，并用e返回其值，L的长度-1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    LinkList p,s;
    p=*L;
    j=1;
    while(p->next && j<1)//遍历寻找第i个结点
    {
        p=p->next;
        ++j;
    }
    if(!(p->next) || j>i)
        return error;//第i个元素不存在
    q=p->next;
    p->next=q->next; //将q的后继赋值给p的后继
    *e=q->data;		//将q结点中的数据给e
    free(q);		//让系统回收此结点，释放内存
    return ok;
}

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

3.8单链表的整表创建

算法思路

  1. 声明一结点p和计数器变量i;
  2. 初始化一空链表L;
  3. 让L的头结点的指针指向NULL,即建立一个带头结点的单链表；
  4. 循环：
    • 生成一新结点赋值给p;
    • 随机生成一数字赋值给p的数据域p->data;
    • 将p插入到头结点与前一新结点之间。
//随机产生n个元素的值，建立带表头结点的单链表L(头插法)
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;
    srand(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; //随机生成100以内的数字
        p->next=(*L)->next;
        (*L)->next=p; //插入到表头
    }
}

//随机产生n个元素的值，建立带表头结点的单链表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int i;
    srand(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; //随机生成100以内的数字
        r->next=p;//将表尾终端结点的指针指向新结点
        r=p;		//将当前的新结点定义为表尾终端结点
    }
    r->next=null;//表示当前链表结束
}

在这里插入图片描述

3.9 单链表的整表删除

算法思路

  1. 声明一结点p和q;
  2. 将第一个结点赋值给p;
  3. 循环：
    1. 将下一结点赋值给q;
    2. 释放p;
    3. 将q赋值给p。
//初始条件 链表已经存在	操作结果  将L重置为空表
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next //p指向第一个结点
    while(p)//没到表尾
    {
        
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=null;//头结点指针域为空
    return ok;
}

3.10单链表结构与顺序存储结构优缺点

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

  • 查找
    • 顺序存储结构O(1)
    • 单链表O(n)
  • 插入与删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
    • 单链表在移动某位置的指针后，插入和删除时间仅为O(1)
  • 空间性能
    • 顺序存储结构需要预分配存储空间，分大了，浪费；分小了易发生上溢
    • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

3.11静态链表

用数组描述的链表叫做静态链表

数组的元素由两个数据域组成，data和cur。数组的每个下标都对应一个data和一个cur。data存放数据，游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。（游标实现法）

为方便插入数据，通常把数组建立得大一点。

//线性表的静态链表存储结构
#define maxsize 1000 //假设链表最大长度为1000
typedef struct
{
    ElemType data;
    int cur; //游标(Cursor) 为0时表示无指向
}Comopent,StaticLinkList[maxsize];

在这里插入图片描述

此时图示相当于初始化数组状态

//将一维数组space中各分量链成一备用链表
//space[0],cur为头指针，“0”表示空指针
Status InitList(StaticLinkList space)
{
    int i;
    for(i=0;i<maxsize-1;i++)
        space[i].cur=i+1;
    space[maxsize-1].cur=0 //目前静态链表为空，最后一个元素的cur为0
    return ok;    
}

在这里插入图片描述

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。
在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{
    int i=space[0].cur;/*当前数组第一个元素的cur存的值，·/
    					/*就是要返回的第一个备用空闲的下标*/
    if(space[0].cur)
        space[0].cur=space[i].cur;/*由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用*/
		return i;
}

在这里插入图片描述

//在L中第i个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k=max_size-1;//k首先是最后一个元素的下标
    if(i<1 || i>ListLength(L)+1)
        return error;
    j=Malloc_SSL(L);//获得空闲分量的下标
    if(j)
    {
        L[j].data=e;//将数据赋值给此分量的data
        for(l=1;l<=i-1;l++)//找到第i个元素之前的位置
            k=L[k].cur;
        L[j].cur=L[k].cur;//把第i个元素之前的cur赋值给新元素的cur
        L[k].cur=j;//把新元素的下标赋值给第i个元素之前元素的cur
        return ok;
    }
    return error;
}

在这里插入图片描述

静态链表的删除操作

在这里插入图片描述

//删除在L中第i个元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    if(i<1 || i<ListLength(L))
        return error;
    k=max_size-1;
    for(j=1;j<=i-1;j++)
        k=L[k].cur;
    j=L[k].cur;
    L[k].cur=L[j].cur;
    Free_SSL(L,j);
    return ok;
}

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for循环因为i=1而不操作，j=k[999].cur=1,L[k].cur=L[j].cur也就是L[999].cur=L[1].cur=2。这其实就是告诉计算机现在“甲”已经离开了，“乙”才是第一个元素。
Free_SSL(L,j);是什么意思呢？来看代码：

//将下标为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space,int k)
{
    space[k].cur=space[0].cur;//把第一个元素cur的值赋给要删除的分量cur
    space[0].cur=k;//把要删除的分量下标赋值给第一个元素的cur
}

在这里插入图片描述

//静态链表L已存在，返回L中数据元素个数
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[maxsize-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

另外一些操作和线性表的基本操作相同

静态链表优缺点

优点

  • 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点

  • 没有解决连续存储分配带来的表长难以确定的问题
  • 失去了顺序存储结构随机存取的特性

3.12循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list)。

在这里插入图片描述

在这里插入图片描述

p=rearA->next; //保存a表的头结点，即1
rearA->next=rearB->next->next;//将本指向B表的第一个结点（不是头结点）赋值给rearA->next即2
rearB->next=p;//将原A表的头结点赋值给rearB->next即3
free(p);//释放p

3.13双向链表

双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域所以双向链表的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱

//线性表的双向链表存储结构
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;//直接前驱指针
    struct DulNode *next;//直接后继指针
}DulNode,*DuLinkList;

在这里插入图片描述

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

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。

在这里插入图片描述

s->prior=p;//把p赋值给s的前驱，即1
s->next=p->next;//把p->next赋值给s的后继，即2
p->next->prior=s;//把s赋值给s的后继，即3
p->next=s;//把s赋值给p的后继，即4

在这里插入图片描述

p->prior->next=p->next;//把p->next赋值给p->prior的后继，即1
p->next->prior=p->prior//把p->prior赋值给p->next的前驱，即2
free(p);//释放结点

最后

以上就是甜美山水为你收集整理的数据结构--3.线性表3.线性表的全部内容，希望文章能够帮你解决数据结构--3.线性表3.线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(48)

相关文章

合并两个有序列表
合并两个有序列表
合并两个有序的线性表
合并两个有序的线性表
7-1 两个有序链表序列的合并 （20 分)
7-1 两个有序链表序列的合并 （20 分)
1-7 两个有序链表序列的交集 (20 分)
1-7 两个有序链表序列的交集 (20 分)
数据结构--3.线性表3.线性表
数据结构--3.线性表3.线性表
浙江大学mooc 两个有序链表序列的合并
浙江大学mooc 两个有序链表序列的合并
线性表的合并（顺序表实现）一、问题描述二、数据结构——线性表三、算法的设计和实现四、代码示例
线性表的合并（顺序表实现）一、问题描述二、数据结构——线性表三、算法的设计和实现四、代码示例
线性表--有序表
线性表--有序表

评论列表共有 0 条评论

立即
投稿
返回
顶部