线性表的顺序和链式存储结构

线性表的顺序存储结构

线性表的顺序存储结构是最常用的存储方式，它直接将线性表的逻辑结构映射到存储结构上，既便于理解，又容易实现。

线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，如图2.2所示。由于线性表中逻辑上相邻的两个元素在对应的顺序表中它们的存储位置也相邻，所以这种映射称为直接映射。线性表的顺序存储结构简称为顺序表(sequential list)。

例：（34, 23, 67, 43）

顺序存储结构的特点

• 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致
• 在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构

顺序表基本运算的实现

建立顺序表

这里介绍整体创建顺序表，即由数组元素a[0..n-1]创建顺序表L。其方法是将数组a中的每个元素依次放人到顺序表中,并将n赋给顺序表的长度域。算法如下:

void CreateList(SqList * 8.L, ElemType a[],int n) //由a中的n个元素建立顺序表
{   int i=0,k=0; //k表示L中的元素个数，初始值为0
    L=(SqList * )malloc(sizeof(SqList)); //分配存放线性表的空间
    while (i<n) //i扫描数组a的元素
    {   L->data[k]=a[i]; //将元素a[0存放到L中
        k++; i++;
    }
    L->length=k; //设置L的长度k
}

当调用上述算法创建好L所指的顺序表后，需要回传给对应的实参，也就是说,L是输出型参数，所以在形参L的前面需要加上引用符“&”。

初始化线性表InitList(&L)

该运算的功能是构造一一个空的线性表L，实际上只需分配线性表的存储空间并将length域设置为0即可。算法如下:

void InitList(SqList *&L)
{   L=(SqList * )malloc(sizeof(SqList)); //分配存放线性表的空间
    L->length=0; //置空线性表的长度为0
}

销毁线性表DestroyList(&L)

该运算的功能是释放线性表L古用的内存空间。算法如下:

void DestroyList(SqList * &L)
{
free(L); ////释放L所指的顺序表空间
}

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

该运算返回一个布尔值表示L是否为空表。若L为空表，则返回true,否则返回false,算法如下:

bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

求线性表的长度ListLength(L)

该运算返回原序表的长度，实际上只需返回lengh域的值即可。算法如下:

int ListLength(SqList *L)
{
    return(L->length);
}

输出线性表DispList(L)

该运算依次显示L中各元素的值。算法如下:

void DispList(SqList *L)
{   for(int i=0;i<L->length;i++) //扫描描顺序表输出各元素值
        print("%d ",L -> data[i]);
    printf("\n");
}

求线性表中的某个数据元素值GetElem(L,i,&e)

该运算用引用型参数。返回L中第i(1≤i≤n)个元素的值。算法如下:

GetElem(SqList *L,int i, ElemType &e)
{   if (i<1 ||i>L->length)
        return false; //参数i错误时返回false
    e=L->data[i-1];   //取元素值
    return true; 
}

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

该运算顺序查找第一个值城与。e相等的元素的逻辑序号(找到后返回 一个大于0的值)，若这样的元素不存在，则返回值为0。算法如下:

int LocateElem(SqList * L, ElemType e)
{   int i=0;
    while (i<L->length&&L->data[i]!=e)
        i++;           //查找元素e
    if(i>=L->length)   //未找到时返回0
        return 0;
    else
        return i+1;    //找到后返回其逻辑序号
}

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

该运算在顺序表L的第i(1≤i≤n+1)个位置上插人新元素e。如果i值不正确，返回false；否则将顺序表原来的第i个元素及以后的元素均后移一个位置，并从最后一个元素an开始移动起，腾出一个空位置插人新元素，最后顺序表的长度增1并返回true。算法如下:

bool ListInsert(SqList *&L,int i,ElemType e)
{   if(i<1||i>L->length+1)
        return false;   //参数i错误时返回false
    i--;                //将顺序表逻辑序号转化为物理序号
    for(j=L->length;j>i;j--)//将data[i]及后面的元素后移一个位置
        L->data[j]=L->data[j-1];
    L->data[i]=e;     //插人元素e
    L->length++;      //顺序表长度增1
    return true;      
}

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

该运算删除顺序表L的第i(1≤i≤n)个元素。如果i值不正确，返回false；否则将线性表第i个元素以后的元素均向前移动一个位置，并从元素ai+1开始移动起，这样覆盖了原来的第i个元素,达到了删除该元素的目的，最后顺序表的长度减1并返回true。算法如下:

bool ListDelete(SqList *&L,int i,ElemType &e)
{   int j;
    if(i<1||i>L->length) //参数i错误时返回false
        return false;
    e=L->data[i];
    i--;                //将顺序表逻辑序号转化为物理序号
    for (j=i;j<L->length-1;j++)
        L->data[j]=L->data[j+1];
    L-> length--;       //顺序表的长度减1
    return true;
}

线性表的链式存储结构

顺表必须占用整块事先分配大小的存储空间，这样会降低存储空间的利用率。为此有了可以实现存储空间动态管理的链式存储结构——链表。线性表的链式存储是指用一组任意的存储单元存放线性表的元素，这组存储单元可以是连续的也可以是不连续的。

链式存储结构中，逻辑上相邻的两个数据元素其存储的物理位置不一定相邻，通过指针来映射数据元素之间的逻辑关系，由此，这种存储结构为非顺序映像或链式映象。

线性表的链式存储有关概念

• 结点：每个数据元素a_i来说，除了存储其本身的信息之外，还需存储指示其直接后继或直接前驱的信息，用来表示a_i与其后继数据元素a_i+1或前驱元素a_i-1的逻辑关系。这两部分信息组成了一个数据元素a_i的存储映射，称为结点(Node)。
• 指针域：存储后继或前驱逻辑关系的部分
• 线性链表 ：具有链式存储结构的线性表
• 单链表 ：在线性链表结点中只包含一个指针域的链表
• 头结点：为了操作方便，通常在单链表前加一结点。头结点的数据域可以不存储任何信息，也可以存储表长等信息。
• 线性表的第1个元素结点称为“首(元)结点”，最后一个元素结点称为“尾(元)结点”。
• 指向链表第1个结点的指针L，称为“头指针”。在有头结点的单链表中，它指向头结点；在没有头结点的单链表中，则指向首结点。   

链表基本运算的实现

建立单链表

这里介绍整体创建单链表，即由数组元素a[0...n-1]创建单链表L。整体建立单链表的常用方法有以下两种。

头插法

该方法从一个空表开始依次读取数组a中的元素，生成一个新结点(由s指向它)，将读取的数组元素存放到该结点的数据域中，然后将其插人插入到当前链表的表头上(即头结点之后)，直到数组a的所有元素读完为止。采用头插法建表的算法如下:

void CreateListF(LinkNode *&L, ElemType a[],int n)
{   LinkNode * s;
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next= NULL;        //创建头结点,其next域置为NULL
    for(int i=0;i<n;i++)  //循环建立数据结点s
    {   s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=a[i];     //创建数据结点s
        s->next=L->next;
        L->next=s;
    }
}

尾插法

该方法从一个空表开始依次读取数组a中的元素,生成一个新结点s，将读取的数组元素存放到该结点的数据域中，然后将其插人到当前链表的表尾上，直到数组a的所有元素读完为止。为此需要增加一个尾指针r,使其始终指向当前链表的尾结点，每插人一个新结点后让r指向这个新结点,最后还需要将r所指结点(尾结点)的next域置为空。采用尾插法建表的算法如下:

void CreateListR(LinkNode *&L, ElemType a[],int n)
{   LinkNode *s,*r;
    L=(LinkNode *)malloc(sizeof(LinkNode);//创建头结点
    r=L;
    for (int i=0;i<n;i++)   //循环建立数据结点
    {   s=(LinkNode *)mallc(sizeof(LiNkNode));
        s->data=a[i];       //创建数据结点S
        r->next=s;          //将结点s插人到结点r之后
        r=s;
    }
    r->next=NULL;           //尾结点的next域置为NULL
}

初始化线性表InitList(&L )

该运算建立一个空的单链表， 即创建一个头结点并将其next域设置为空。算法如下:

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

销毁线性表DestroyList(&L )

该运算释放单链表L占用的内存空间，即逐一释放全部结点的空间。其过程是让pre、p指向两个相邻的结点(初始时pre指向头结点，p指向首结点)。当p不为空时循环：释放结点pre,然后pre、p同步后移一个结点。循环结束后，pre指向尾结点，再将其释放。算法如下:

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);
}

判断线性表是香为空表ListEmpty(L)

该运算在单链表L中若有数据结点时返回真，否则返回假。算法如下:

bool LisrEmpty(LinkNodte *L)
{
    return(L->next==NULL);
}

求线性表的长度ListLength(L)

该运算返回单链表L中数据结点的个数。由于单链表没有存放数据结点个数的信息需要通过遍历来统计。其过程是让P指向头结点，用来累计数据结点个数(初始值为0)当p不为空时循环：n增1，p指向下一个结点，循环结束后返回。算法如下:

int ListLength(LinkNode * L)
{   int n=0;
    LinkNode *p=L;
    while(p->next!=NULL)
    {   n++;
        p=p->next;
    }
    return(n);
}

输出线性表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移向下一个结点
    }
    printf("\n");
}

线性表中的某个数据元素值GetElem(L,i,&e)

该运算在单链表L中从头开始找到第i个结点,若存在第i个数据结点，则将其data坝值赋给变量e。其过程是让p指向头结点，j用来累计遍历过的数据结点个数(初始值为0)，当j<i且p不为空时循环:：j增1，p指向下一个结点。循环结束后有两种情况，若p万空，表示单链表L中没有第i个数据结点(参数i错误)，返回false；否则找到第i个数据车点，提取它的值并返回true。算法如下:

bool GetEle(LinkNode *L,int i,ElemType &e)
{   int j=0;
    LinkNvode *p=L;
    if(i<=0)  return Talse;  //i错误返回假、
    while(j<i&&p!=NULL)
    {   j++;
        p=p->next;
    }
    if(p==NULL)    //不存在第1个数据结点，返回false
        return false;
    else           //存在第1个数据结点，返回true
    {
        e=p->data;
        return true;
    }
}

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

该运算在单链表L中从头开始找第一个值域 与e相等的结点，若存在这样的结点，则返回逻辑序号,否则返回0。算法如下:

int LocateElem(LinkNode * L, ElemType e)
{   int i=1;
    LinkNode *p=L->next;      
    while(p!=NULL&&p->data!=e)
    {   p=p->next;
        i++;
    }
    if(p==NULL)
        return(0);
    else
        return(i);

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

该运算的实现过程是先在单链表L中找到第i-1个结点，由p指向它。若存在这样的结点，将值为e的结点(s指向它)插人到p所指结点的后面。算法如下:

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

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

该运算的实现过程是先在单链表L中找到第i-1个结点，由p指向它。若存在这样的结点，且也存在后继结点(由q指向它)，则删除q所指的结点，返回true；否则返回false，表示参数i错误。算法如下:

bool ListDelete(LinkNode *&L,int i,ElemType &e)
{   int j=0;
    LinkNode *p=L,*q;  //p指向头结点,j置为0(即头结点的序号为0)
    if(i<=0)  return false;  //i错误返回false
    while(j<i-1&&p!=NULL)    //查找第i-1个结点
    {   i++;
        p=p->next;
    }
    if(p==NULL)
        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;
    }
}