线性表顺序存储结构

青旅半醒 2022-10-01 04:56 274阅读 0赞

**线性表顺序存储结构**

顺序存储结构：指的是用一段地址连续的存储单元一次存储线性表的数据元素。（理解成一维数组，既把第一个数据元素存到数组下表为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置）。

**一、结构**

#define MAXSIZE 20//存储空间初始化分配量
    typedef int ElemType;//此处可能是个结构体，练习使用int型足够了
    typedef struct
    {
    	ElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
    	int length;//链表长度
    }SqList;

描述线性表顺序存储结构需要三个属性：

1. 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置

2. 线性表的最大存储容量：数组长度MAXSIZE

3. 线性表的当前长度：length

**注意**：数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该小于等于数组的长度。

![Center][]

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

**二、线性表顺序存储插入操作**

![Center 1][]

**算法思路：**

1. 如果插入位置不合理，抛出异常；

2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

3. 从最后一个元素向前遍历到第i个位置，分表将他们都向后移动一个位置；

4. 将要插入元素填入位置i处；

5. 链表长度加1

**三、线性表顺序存储删除操作**

![Center 2][]

**算法思路：**

1. 如果删除位置不合理，抛出异常；

2. 取出删除元素；

3. 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；

4. 链表长度减1

**四、时间复杂度**

线性表的顺序存储结构，在存、读数据是，不管是哪个位置，时间复杂度都是O(1)；而插入或删除是时间复杂度都是O(n)。说明它比较适合元素个数不太变化，而更多是存取数据的应用。

**五、优缺点**

<table> 
 <tbody> 
  <tr> 
   <td> <p>优点</p> </td> 
   <td> <p>缺点</p> </td> 
  </tr> 
  <tr> 
   <td> <p>1.&nbsp;无须为表示表中元素之间的逻辑关系而增加额外的存储空间；</p> <p>2.&nbsp;可以快速的存取表中任一位置的元素</p> </td> 
   <td> <p>1.&nbsp;插入和删除操作需要移动大量元素；</p> <p>2.&nbsp;当线性表长度变化较大时，难以确定存储空间的容量</p> <p>3.&nbsp;造成存储空间的“碎片”</p> </td> 
  </tr> 
 </tbody> 
</table>

**六、代码示例**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OK 1
    #define ERROR 0
    
    #define MAXSIZE 20//存储空间初始化分配量
    typedef int ElemType;//此处可能是个结构体，练习使用int型足够了
    typedef struct
    {
    	ElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
    	int length;//链表长度
    }SqList;
    
    //初始化操作，建立一个空的线性表L
    void InitList(SqList *L);
    //若线性表为空返回TRUE，否则返回FALSE
    int ListEmpty(SqList L);
    //将线性表清空
    void ClearList(SqList *L);
    /*在线性表L中查找给定值e相等的元素，
      *如果查找成功返回该元素在表中序号
      *表示成功；否则，返回0表示失败。
    */
    int LocateElem(SqList *L,ElemType e);
    
    //返回线性表L的元素个数
    int ListLength(SqList *L);
    
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：用e返回L中第i个数据元素的值
    int GetElem(SqList *L,int i,ElemType *e);
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：删除L中第i个位置的数据元素，并用e返回其值，L的长度减1
    int ListDelete(SqList *L,int i,ElemType *e);
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
    int ListInsert(SqList *L,int i,ElemType e);
    
    /*将所有的在线性表Lb中但是不在La中的元素插入到La中*/
    void swapList(SqList *La,SqList *Lb);
    
    int ListPrint(SqList *L);
    
    
    //初始化操作，建立一个空的线性表L
    void InitList(SqList *L)
    {
    	memset(L,0,sizeof(SqList));
    }
    //若线性表为空返回TRUE，否则返回FALSE
    int ListEmpty(SqList L)
    {
    	if(0 == L.length)
    	{
    		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
    		return ERROR;
    	}
    	return OK;
    }
    //将线性表清空
    void ClearList(SqList *L)
    {
    	memset(L,0,sizeof(SqList));
    }
    /*在线性表L中查找给定值e相等的元素，
      *如果查找成功返回该元素在表中序号
      *表示成功；否则，返回0表示失败。
    */
    int LocateElem(SqList *L,ElemType e)
    {
    	int i = 0;
    	if(L->length == 0)//线性表为空
    	{
    		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
    		return ERROR;
    	}
    
    	for(i = 0;i < L->length;i++)
    	{
    		if(e == L->data[i])
    		{
    			return i;
    		}
    	}
    	printf("[%s %d]链表L中不存在元素e:%d\n",__FUNCTION__,__LINE__,e);
    	return ERROR;
    }
    
    //返回线性表L的元素个数
    int ListLength(SqList *L)
    {
    	return L->length;
    }
    
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：用e返回L中第i个数据元素的值
    int GetElem(SqList *L,int i,ElemType *e)
    {
    	if(L->length == 0 || i< 1 || i>L->length)
    	{
    		return ERROR;
    	}
    	*e = L->data[i-1];
    	return OK;
    }
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：删除L中第i个位置的数据元素，并用e返回其值，L的长度减1
    int ListDelete(SqList *L,int i,ElemType *e)
    {
    	int k;
    	if(L->length == 0)//线性表为空
    	{
    		return ERROR;
    	}
    	if(i< 0 || i> L->length)//删除位置不正确
    	{
    		return ERROR;
    	}
    	*e = L->data[i-1];
    	if(i< L->length)//如果删除不是最后位置
    	{
    		for(k = i;k< L->length;k++)//将删除位置后继元素前移
    		{
    			L->data[k-1]=L->data[k];
    		}
    	}
    	L->length--;
    	return OK;
    }
    //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
    //操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
    int ListInsert(SqList *L,int i,ElemType e)
    {
    	int k;
    	if(L->length == MAXSIZE)//顺序线性表已满
    	{
    		return ERROR;
    	}
    	if(i< 0 || i> L->length)//当i不在范围内时
    	{
    		return ERROR;
    	}
    	if(i< L->length)//若插入位置不在表尾
    	{
    		for(k = L->length;k>= i;k--)//将要插入的位置后数据元素向后移动一位
    		{
    			L->data[k+1] = L->data[k];
    		}
    	}
    	L->data[i] = e;//将新元素插入
    	L->length++;
    	return OK;
    }
    
    /*将所有的在线性表Lb中但是不在La中的元素插入到La中*/
    void swapList(SqList *La,SqList *Lb)
    {
    	int La_len,Lb_len,i;
    	ElemType e;//声明与La个Lb相同的数据元素e
    	La_len = ListLength(La);//求线性表的长度
    	Lb_len = ListLength(Lb);
    	for(i = 1;i <= Lb_len;i++)
    	{
    		GetElem(Lb,i,&e);//取Lb中第i个数据元素赋值给e
    		if(!LocateElem(La,e))//La中不存在和e相同的数据元素
    		{
    			ListInsert(La,++La_len,e);//插入
    		}
    	}
    }
    
    int ListPrint(SqList *L)
    {
    	int i = 0;
    	if(L->length == 0)//线性表为空
    	{
    		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
    		return ERROR;
    	}
    
    	for(i = 0;i < L->length;i++)
    	{
    		printf("[%s %d]位置:%d,元素:%d\n",__FUNCTION__,__LINE__,i,L->data[i]);
    	}
    	return OK;
    }
    
    
    int main()
    {
        SqList L;
    	int i = 0;
    	int ret = ERROR;
    	ElemType e = 0;
    	InitList(&L);
    	//插入数据
    	printf("[%s %d]------------插入数据------------------\n",__FUNCTION__,__LINE__);
    	for(i = 0;i < 15;i++)
    	{
    		ret = ListInsert(&L,i,i);
    		if(ERROR == ret)
    		{
    			printf("[%s %d]插入数据失败，位置:%d,元素:%d\n",__FUNCTION__,__LINE__,i,i);
    		}
    	}
    
    	//打印链表
    	ret = ListPrint(&L);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
    	}
    
    	//插入数据
    	printf("[%s %d]------------指定位置插入数据------------------\n",__FUNCTION__,__LINE__);
    	ret = ListInsert(&L,10,22);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]插入数据失败，位置:%d,元素:%d\n",__FUNCTION__,__LINE__,i,i);
    	}
    
    	//打印链表
    	ret = ListPrint(&L);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
    	}
    	//获取单个元素
    	printf("[%s %d]------------获取单个元素------------------\n",__FUNCTION__,__LINE__);
    	ret = GetElem(&L,5,&e);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]获取位置5的数据失败\n",__FUNCTION__,__LINE__);
    	}
    	else
    	{
    		printf("[%s %d]e:%d\n",__FUNCTION__,__LINE__,e);
    	}
    	//获取长度
    	printf("[%s %d]------------获取长度------------------\n",__FUNCTION__,__LINE__);
    	ret = ListLength(&L);
    	printf("[%s %d]链表长度:%d\n",__FUNCTION__,__LINE__,ret);
    
    	printf("[%s %d]------------检查元素------------------\n",__FUNCTION__,__LINE__);
    	ret = LocateElem(&L,5);
    	if(OK == ret)
    	{
    		printf("[%s %d]5是链表中元素，位置:%d\n",__FUNCTION__,__LINE__,ret);
    	}
    	else
    	{
    		printf("[%s %d]5不是链表中元素\n",__FUNCTION__,__LINE__);
    	}
    
    	//删除数据
    	printf("[%s %d]------------删除数据------------------\n",__FUNCTION__,__LINE__);
    	ret = ListDelete(&L,10,&e);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]删除失败\n",__FUNCTION__,__LINE__);
    	}
    	else
    	{
    		printf("[%s %d]删除成功e:%d\n",__FUNCTION__,__LINE__,e);
    	}
    
    	//打印链表
    	ret = ListPrint(&L);
    	if(ERROR == ret)
    	{
    		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
    	}
    	printf("[%s %d]------------清空链表------------------\n",__FUNCTION__,__LINE__);
    	if(ListEmpty(L))
    	{
    		printf("[%s %d]链表不为空\n",__FUNCTION__,__LINE__);
    	}
    	ClearList(&L);
    	if(ListEmpty(L))
    	{
    		printf("[%s %d]链表不为空\n",__FUNCTION__,__LINE__);
    	}
    
    //void swapList(SqList *La,SqList *Lb);
    	return OK;
    }

[Center]: /images/20220705/22da08394b29455ba9a6d57e1eb73974.png
[Center 1]: /images/20220705/0d609b3621dc470cbdc395a02428c6f0.png
[Center 2]: /images/20220705/3eccfeb497d14fd9bd16046566c4eb7a.png