浅谈线性表的顺序存储结构

忘是亡心i 2022-06-08 12:26 278阅读 0赞

#     #

# 浅谈线性表的顺序存储结构 #

第一次接触到博客这个东西，第一次写博客也不知道要写什么，就简单的说一下最近刚学的线性表吧！由于是第一次写博客，所以有什么不对之处还请多多包涵！ 线性表是最基本、最简单、也是最常用的一种数据结构。 线性表有两种存储结构，一种是顺序存储，还有一种就是链式存储。

今天，我们就来讨论线性表的顺序存储结构。说到线性表的顺序存储，首先我们的脑子里要浮现出一张图，就是相当于一条不能断开的链子，它有头有尾，而且中间是不能断开的，是一个挨一个的连着的，就相当于我们c语言经常用到的数组一样。所以，根据想象我们可以得到线性表的顺序存储结构的定义代码：

#define MAXSIZE 100
    typedef struct  
    {  
        ElemType *elem;//存储空间的基地址   
        int length;//当前长度   
    }SqList;

需要说一下的是那个ElemType是一个抽象数据类型，没有固定的类型，只有在实际的应用里面才能将它改成相应的数据类型。MAXSIZE是设置线性表的最大长度为100。length是设置线性表的当前长度，也就是线性表里面存放元素的个数。

现在可以看看这张图对照一下你脑海中的线性表：

![Center][]

现在我们有了这个图片，我们可以根据这个图片来试着对线性表进行初始化：

Status InitList_Sq(SqList &L)//构造一个空的顺序表   
    {  
        L.elem=new ElemType[MAXSIZE];//为顺序表分配一个大小为MAXSIZE的数组空间   
        if(!L.elem) exit(OVERFLOW);//存储失败   
        L.length=0;//空表长度为零   
        L.listsize=MAXSIZE;  
        return OK;  
    }

同样，这段代码不能直接运行，因为还有一些抽象数据类型不能直接使用，只有在实际的例子中才能把它转换成相应的数据类型。

在对线性表的顺序存储结构进行定义以及初始化之后，我们就可以对顺序表开始操作了。首先我们先来看看销毁线性表的操作：由于线性表的顺序存储结构与数组基本是差不多的，所以如果想要销毁整个线性表只需要将线性表的首地址给销毁掉就行了。下面是线性表的顺序存储结构销毁操作的代码：

DestoryList(&L)
    {
        if(L.elem)
        {
           delete[] L.elem;
            return OK;
        }
        else
            return ERROR;
    }

可是，清空线性表与销毁线性表就不一样了，销毁线性表是销毁掉整个线性表，把整个线性表都给释放掉。而清空线性表就不一样了，清空不需要将整个线性表给释放掉，只需要将线性表里的元素清空就行了，销毁线性表是整个线性表都没有了，而清空线性表是让线性表回到了刚开始初始化线性表的那一个状态，所以依照初始化的代码来看的话，清空线性表的话就只需要把当前长度置为0就行了，清空线性表的顺序存储结构的代码如下：

ClearList(&L)
     {
       L.length=0;
       return OK;
      }

这里统一说一下“&”这个符号的用法，在以前的C语言中，它叫做取地址符，顾名思义，也就是用来取地址的。可是在这里这个符号叫做引用，是用来改变参数的值，然后将参数传到外面去，而且一定要是定义时加这个符号才能是引用，否则就是取地址符。

最后再来讲讲线性表最复杂也是最重要的两个操作插入及删除，插入及删除的操作基本一样，由于是一个挨一个存放的数据，所以插入时就要将元素一个接一个地往后移，从而可以空出一个位置来存放插入的元素，同样，删除也是差不多的操作，删除一个元素后又将后面的元素一个接一个地往前移，补上前面删除的空位，具体的代码实现如下所示：

线性表的顺序存储结构插入操作代码：

InsertList(&L,int i,ElemType e)
    {
        int j;
        if(L.length==MAXSIZE-1)
        {
           return ERROR;
        }
        else
            if(i<1||i>L.length)
               return ERROR;
            else
            {
                for(j=L.length-1;j>=i;j--)
                {
                    L.elem[j+1]=L.elem[j];
                }
                L.elem[i]=e;
                L.length++;
            }
         return OK;
    }

销毁线性表的顺序存储结构的代码实现：

DeleteList( & L,int j)
    {
    	int i;
    	if(j<0||j>L.Length)
    	{
    	return ERROR;
    	}
    
    	for(i=j;i<L.Length-1;i++)
    		L.elem[i-1]=L.elem[i];
    	L.Length--;
    	return OK;
    }

> 以上就是我学完线性表的链式存储结构后的总结，如果还有不对的地方欢迎指正修改！

[Center]: /images/20220608/dcece0c31ef04e6dbf86b20f15ca86e1.png