大话数据结构-3.11 单链表结构与顺序存储结构优缺点 - 高飞网

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

2015-12-30 00:55:14.0

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

存储分配方式时间性能空间性能

· 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素

· 单链表采用链式存储结构,用一组任意的存储单元存放线性表的无数


· 查找

顺序存储结构O(1)单链表O(n)

· 插入和删除

· 顺序存储结构需要平均移动表长一半的元素时间为O(n)

· 单链表在找到某位置的指针后,插入和删除时仅为O(1)

· 顺序存储结构需要分配存储空间。分大了浪费,分小了易发生上溢

· 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

总结

  • 若线性需要频繁查找,很少进行插入和删除操作,宜使用顺序结构;若线性表需要频繁插入和删除操作,宜使用链式结构。
  • 当线性表的元素个数变化很大或根本不知道多大时,宜使用链式结构。


静态链表

    对于像Basic、Fortran这样的没有指针的高级语言,如何使用链表结构呢?可以用数组代替。这种用数组描述的链表叫做静态链表。

    让数组的元素都是两个数据域组成,data和cur。数据域data,用来存放数据元素,而游标cur相当于单链表中的next指针,存放元素的后继在数组中的下标。

数据结构为:

/* 静态链表 */
typedef int ElemType;
#define MAXSIZE 20
typedef struct
{
    ElemType data;
    int cur;        /* 游标(Cursor),为0时表示无指向 */
}Component,StaticLinkedList[MAXSIZE];


    另外,对于数组的第一个和最后一个元素做特殊处理,不存数据。通过把未被使用的数组元素称为备用链表。而数组第一个元素,即下标为0的元素的cur存放备用链表的第一个结点下标;数组最后一个元素的cur则存放第一个有数值的元素下标,相当于头结点,当整个链表为空时,则为0.
初始化代码:

//建立一个空的线性表L,将一维数组L中各分量链成一备用链表
Status InitList(StaticLinkedList L)    
{
    for(int i=0;i<MAXSIZE-1;i++)
    {   
        L[i].cur = i+1;
    }   
    L[MAXSIZE-2].cur = 0;		//倒数第2个元素也应是无指向的
    L[MAXSIZE-1].cur= 0;        //目前为静态链表,最后一个元素即头结点的cur为0
    return OK;    
}


静态链表的插入操作


//在线性表L中的第i个位置插入新元素e
Status ListInsert(StaticLinkedList L,int i,ElemType e)
{

    int j,k,l;  /* j,k,l分别表示j获得空闲分量的下标,k前一个元素的下标,l计数器 */
    k = MAXSIZE -1;
    if(i<0 || i>ListLength(L))
    {
        return ERROR;
    }
    j = Malloc_SLL(L);  /* 获得空闲分量的下标 */
    if(j)
    {
        L[j].data =e;   /* 将数据赋值给分量的data */
        for(l=1;l<=i;l++)   /* 找到第i个元素之前的位置 */
        {
            k = L[k].cur;
        }
        if(k == MAXSIZE-1)
        {//如果是空表
            L[MAXSIZE-1].cur=j;
        }
        else
        {
            L[j].cur = L[k].cur;/* 把第i个元素之前的cur赋值给新元素的cur */
            L[k].cur = j;/* 把新元素的下标赋值给第i个元素的cur */
        }
        return OK;
    }
    return ERROR;
}
/* 若备用空间链表非空,则返回分配的结点下标,否则返回0 */
int Malloc_SLL(StaticLinkedList L)
{
    /* 当前数组第一个元素的cur存的值即为第一个备用空闲的下标 */
    int i = L[0].cur;
    if(L[0].cur)
        L[0].cur = L[i].cur;//由于要拿出一个分量来使用,就得把它下一个分量用来做备用
    return i;
}



静态链表的删除操作


//删除线性表L中第i个位置元素
Status ListDelete(StaticLinkedList L,int i)    
{
    int j,k;    
    k = MAXSIZE -1; 
    if(i<1 || i>ListLength(L))
    {   
        return ERROR;   
    }   
    for(j=1;j<i-1;j++)  /* 找到第i个元素之前的位置 */
    {   
        k = L[k].cur;   
    }   
    j = L[k].cur;
    L[k].cur =L[j].cur;/* 把要删除的元素的cur赋值给第i个元素之前的cur */
    Free_SLL(L,j);
    return OK; 
}
/* 将下标为k的空闲结点回收到备用链表 */
Status Free_SLL(StaticLinkedList L,int k)
{
    L[k].cur = L[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    L[0].cur = k;           /* 把要删除的分量下标赋值给第一个元素的cur,即下次优先使用这个>索引的位置 */
    return OK;
}
//返回线性表L的元素个数
int ListLength(StaticLinkedList L)    
{
    int j = 0,i=L[MAXSIZE-1].cur;//i是静态链表的地址
    while(i && j!=L[0].cur)
    {   
        i=L[i].cur;
        j++;    
    }   
    return j;    
}



静态链表的优缺点

优点缺点

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

· 没有解决连续存储分配带来的表长难以确定的问题

· 失去了顺序存储结构随机存取的特性

循环链表

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

    注意,如果由单链表访问第一个结点的时间复杂度为O(1),而访问最后一个结点是O(n),如果不用头指针,而使用终端结点的尾指针,那么访问尾部头部都非常简单了。

如上图,如果终端结点用rear表示,想访问开始结点,其实就是要rear->next->next.时间复杂度也为O(1)

同时,如果想将两个单链表合并也变得非常简单,如下图:

只需要:
即:

p ->rearA->next;
rearA->rearB->next->next
rearB->next = p
free(p);

双向链表

双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。

数据结构为:

typedef int ElemType;
typedef struct DoubleNode
{
    ElemType data;
    struct DoubleNode *prior;       /* 直接前驱 */
    struct DoubleNode *next;        /* 直接后继 */
}DoubleNode,*DoubleLinkedList;


总结回顾

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

单链表静态链表循环链表双向链表