线性表的动态分配存储结构分析

曹小妹

摘要：线性表是由数据类型相同的若干个数据元素组成的有限序列，其特点和算法容易理解，是学习其它数据结构的基础。该文主要介绍了线性表、线性表的应用、线性表的常用算法和线性表的优缺点。

关键词：线性表；动态分配；插入；删除

中图分类号：TP311文献标识码：A文章编号：1009-3044（2012）30-7216-04

随着计算机产业的迅速发展和计算机应用领域的不断扩大，计算机应用已不仅仅局限于早期的科学计算，而是更多地用于控制、管理和数据处理等方面。所以，随之而来的便是处理的数据量越来越大，数据类型越来越多，数据结构越来越复杂。因此，针对实际问题，例如编制一个高效率的处理程序，那么就需要解决如何合理地组织数据，建立合适的数据结构，设计好的算法，来提高程序执行的效率这样的问题。

1 引入线性表动态分配的源由

在数据结构中，数据的逻辑结构分为线性结构和非线性结构，非线性结构中又以线性表为典型代表，线性表的逻辑结构是通过元素之间的相邻关系体现的。因此利用数组实现线性表的顺序存储，结构简单，其算法也容易理解。但是，由于存储分配只能预先定义，如果插入的数据量超出预先分配的存储空间，那么临时扩大就会存在很大的困难；如果按最大的可能空间进行分配，则势必降低了存储空间的利用率。为解决此问题，可以利用C语言动态分配内存的机制，实现线性表的顺序存储。

2 动态分配顺序存储结构的基本操作

2.1 动态分配的顺序存储结构的描述

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。由于高级程序设计语言中的数据类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，则在C语言中可用动态分配的一维数组，如下描述。

在上述定义中，顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。Listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为LISTINCREMENT个数据元素的空间。

2.2 线性表的初始化

根据线性表结构的基本描述，为完成对一组数据的处理，用户根据需要定义线性表供程序使用，则为线性表的初始化。初始化线性表是为线性表分配一个预定义的存储空间，并将线性表的当前长度定义为零。分配一个预定的存储空间可以通过调用C语言的动态分配库函数malloc来实现。具体算法如下：

2.3 线性表某个元素的插入

从线性表的特点中我们得到一个结论，在一个表中有且仅有唯一的根结点和终端结点，除了根结点和终端结点，其余结点都有唯一的前驱和唯一的后继，只有满足这样的条件才称为线性表，故此线性表是一个连续的有限的存储空间。我们要在一个线性表的某个元素前、后插入一个元素，其数据元素在存储空间中的位置有所变化，为了不破坏线性表的特征，我们就要采取一定的措施进行位置的变化，这就是线性表元素的插入。例如，某一长度为n的线性表，为了在线性表的第i个和第i+1个元素之间插入一个值为x的数据元素，则需要从第i个至第n个数据元素依次往后移动一个位置。一般情况下，所需要移动的元素次数为n-i+1。在具体的移动过程中为移出一个元素，则从尾部向前部依次向后移动至第i-1的位置处。具体算法如下：

2.4 线性表中删除某个元素

线性表的删除操作是使长度为n的线性表变成长度为n-1的线性表，数据元素之间的逻辑关系发生了变化，为了在存储结构上反映这个变化，同样需要移动元素。在移动过程中，必须将从第i+1个元素至n个元素依次前移一位，一般情况下，删除第i个元素时需从第i+1至第n个元素依次向前移动一个位置。具体算法如下：

3 动态分配顺序存储结构的应用

在日常生活中，我们只要注意观察，留意我们的生活，我们就不难发现，其实很多时候我们都会用到线性表的顺序存储结构，例如在学校对学生信息的管理、病人在医院挂号、数学集合的合并，其中两个线性表的合并操作是线性表处理的典型例子。今天我们以其作为综合应用。具体算法如下：

4 动态分配顺序存储结构的主函数

线性表动态分配顺序存储结构的基本操作共四个，包括线性表的初始化、插入、删除、合并。要将这些算法融合为一体成为一个完整的程序，我们必须从程序的入口点开始执行，即主函数main（）。下面就在主函数中调入以上的四个子程序，使程序结构化、合理化、正确化、实用化。程序如下：

5 动态分配顺序存储结构的优缺点

在数据结构中，我们通过时间复杂度和空间复杂度来评价一个算法的好坏，既要考虑程序所占的空间又要考虑程序执行的次数，所占空间越小，执行次数越少，又能得出正确答案，这是每个程序员所希望的，所以当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。但是，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。故顺序存储结构的优点为：具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出；缺点为：顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储很是不方便，效率低；顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢。

参考文献：

[1] 秦玉平，马靖善.数据结构（C语言版）[M].北京：清华大学出版社，2005.

[2] 谭浩强.C程序设计[M].3版.北京：清华大学出版社，2005.

[3] 严蔚敏，吴伟民.数据结构C语言[M].北京：清华大学出版社，2008.