谈顺序存储与链式存储的异同

谈顺序存储与链式存储的异同

摘要：

顺序存储与链式存储的应用范围较为广泛。顺序存储就是用一组地址连续的存储单元依次存储该线性表中的各个元素，由于表中各个元素具有相同的属性，所以占用的存储空间相同，而链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。

关键词：顺序存储链式存储顺序存储与链式存储异同

一、什么是顺序存储

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.

顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

二、简述链式存储

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).

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

链式存储结构不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要用地址连续的存储单元来实现。因此在操作上，它也使得插入和删除操作不需要移动大量的结点。线性表的链式存储结构主要介绍了单链表、循环链表、双向链表和静态链表四种类型，讨论了各种链表的基本运算和实现算法。

三、栈的存储结构：顺序存储和链式存储

利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，顺序栈中的数据元素用一个预设的足够长度的一维数组来实现：ElemTypedata[MAXSIZE]，栈底位置通常设置在数组的0单元。而栈顶是随着插入和删除而变化的，用一个int top 来作为栈顶的指针，指明当前栈顶的位置。

数组data 和指针top 是栈的两个组成部分，需封装在一个结构体中组

成一个整体。顺序栈的类型描述如下：

#defineMAXSIZE 200

struct seqstack

{

Elemtype data[MAXSIZE];

int top;

};

定义一个指向顺序栈的指针：structseqstack *s;

用链式存储结构来实现的栈称为链栈。通常链栈用单链表来表示，因此其站点结构与单链表的结构相同，在此用stack_node表示，即

struct stack_node

{

Elemtype data;

struct stack_node*next;

};

struct stack_node*top;

建栈：

struct seqstack *init_seqstack()

{

struct seqstack *s;

s=(structseqstack *)malloc(sizeof(structseqstack));

s->top=0;

return s;

}

入栈

int push_seqstack(structseqstack *s,Elemtypex)

{

if(full_seqstack(s))

{

printf("Stackis full, fail to insert to the stack!");

return 0;

}

else

{

s->data[s->top]=x;

s->top++;

return 1;

}

}

尽管在建栈时，定义data 数组的长度尽可能大，但总有可能在data 数组满了后还在执行入栈操作，这种情形称为栈的上溢出。为了防止上溢，在入栈时需要检查栈是否满，若未满，则进行入栈操作，否则进行溢栈处理或溢栈报告。定义一个函数检查栈是否满：

int full_seqstack(structseqstack *s)

{

if(s->top==MAXSIZE)return 1;

elsereturn 0;

}

出栈

int pop_seqstack(structseqstack *s,Elemtype*x)

{

if(empty_seqstack(s))

{

printf("Emptystack, fail to get out from stack!");

return 0;

}

else

{

s->top--;

*x=s->data[s->top];

return 1;

}

}

int empty_seqstack(strictseqstack *s)

{

if(s->top==0)return 1;

elsereturn 0;

}

销毁栈

void destroy_seqstack(structseqstack *s)

{

free(s);

}

void clear_seqstack(structseqstack *s)

{

s->top=0;

}

销毁栈的算法很简单，只需释放栈指针即可；清楚栈只是将栈内元素清空，仍保留栈。栈通常使用顺序存储方式，但顺序栈很容易发生上溢。可以利用多个顺序栈实现多栈共享。最有效的解决途径时使用链栈，可不受内存单元数量的限制。

四、总结

顺序存储：

线性表的顺序表：指的是用一组地址连续的存储单元，依次存储线性表的数据元素。

线性表的顺序存储结构具备如下两个基本特征：

1、线性表中的所有元素所占的存储空间是连续的（即要求内存中可用存储单元的地址必须是连续的）。

2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

即：线性表逻辑上相邻、物理也相邻（逻辑与物理统一：相邻数据元素的存放地址也相邻），则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。

优点：

1、无须为表示结点间的逻辑关系而增加额外的存储空间。

2、可以方便的随机存取表中的任一结点。

3、存储密度大（＝1），存储空间利用率高。

缺点：

1、插入和删除运算不方便，需移动大量元素。

2、由于要求占用连续的存储空间，存储分配只能按最大存储空间预先进行，致使存储空间不能得到充分利用。

3、表的容量难以扩充。

链表存储：

线性表的链式存储：指用一组任意的存储单元存储线性表中的数据元素。线性表的链式存储结构具备的基本特征：

链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

优点：

1、插入、删除操作很方便，可通过修改结点的指针实现，无须移动元素。

2、方便扩充存储空间。

缺点：

1、不能随机存取元素。

2、存储密度小（

小结：

1、顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

2、若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。参考文献：

1）《算法导论》国防科大出版社张益新沈雁编著

2)《数据结构》清华大学出版社严蔚敏著

3)《线性表顺序和链式存储的对比分析》《保山学院学报》2010年05期