【数据结构/线性表】线性表的顺序表示和实现

小咪咪 2023-01-21 12:27 55阅读 0赞

1.称顺序存储结构的线性表为**顺序表**

2.线性表的顺序存储结构是一种**随机存取**的存储结构

3.通常用**数组**来描述数据结构中的顺序存储结构

4.**逻辑结构与存储结构**一致

5.访问每个元素所花时间**相等**

## 顺序表数据结构 ##

*数组形式*

//顺序表数据结构
    typedef struct
    {
        
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;                   //顺序表的结构类型为SqList

*指针形式*

//顺序表数据结构
    typedef struct
    {
        
    	ElemType *elem;        //存储空间的基地址
    	int length;            //顺序表当前长度
    }SqList;                   //顺序表的结构类型为SqList

## 顺序表初始化 ##

*数组形式*

//初始化顺序表函数，构造一个空的顺序表 
    Status InitList(SqList &L)
    {
        
    	memset(L.data, 0, sizeof(L));//初始化数据为0
    	L.length = 0;                //初始化长度为0
    	return 0;
    }

*指针形式*

Status InitList(SqList &L)
    {
        
    	L.elem=new int[MAXSIZE];
    	if(!L.elem) exit(OVERFLOW);
    	L,length=0;
    	return OK;
    }

## 销毁顺序表 ##

void DestoryList(SqList &L)
    {
        
    	if(L.elem) delete[] L.elem;
    }

## 顺序表的取值 ##

*指针形式*  
时间复杂度：**O(1)**

Status GetElem(SqList L,int i,int &e)
    {
        
    	if((i<1)||(i>L.length)) return ERROR;
    	e=L.elem[i-1];//将第i个元素赋值给e
    	return OK; 
    }

## 顺序表的查找 ##

*指针形式*  
时间复杂度：**O(n)**  
查找失败返回0

Status LocateElem(SqList L,int e)
    {
        
    	for(i=0;i<L.length;i++)
    	{
        
    		if(L.elem[i]==e) return i+1;
    	}
    	return 0;
    }

## 顺序表的插入 ##

插在第**i**个节点之前，需要移动**n-i+1**次元素

时间复杂度：**O(n)**

Status ListInsert(SqList &L,int i,int e)
    {
        	
    	if((i<1)||(i>L.length+1)) return ERROR;//i值不合法 
    	if(L.length==MAXSIZE) return ERROR;//存储空间已满 
    	for(j=length-1;j>=i-1;j--)
    	{
        
    		L.elem[j+1]=L.elem[j];
    	}
    	L.elem[i-1]=e;//将新元素放入第i个位置
    	++L.length; 
    	return OK;
    }

## 顺序表的删除 ##

删除第**i**个节点，需要移动**n-i**次元素

时间复杂度：**O(n)**  
空间复杂度：**O(1)**

Status ListDelete(SqList &L,int i)
    {
        
    	if((i<1)||(i>L.length)) return ERROR;//i值不合法 
    	for(j=i;j<=L.length-1;j++)
    	{
        
    		L.elem[j-1]=L.elem[j];
    	}
    	--L.length;
    	return OK;
    }

## 顺序表的倒置 ##

//倒置函数 将原顺序表直接倒置
    void Reverse(SqList &L)
    {
        
    	if (L.length)
    	for (int i = 0; i<L.length - 1 - i; i++)
    	{
        
    		int t = L.data[i];
    		L.data[i] = L.data[L.length - 1 - i];
    		L.data[L.length - 1 - i] = t;
    	}
    }

## 清空顺序表 ##

void ClearList(SqList &L)
    {
        
    	L.length = 0;
    }

## 优点和缺点 ##

### 优点： ###

随机存取表中任何一个元素，其存储位置可用一个简单直观的公式来表示

### 缺点： ###

1.做插入或者删除操作，需要移动大量元素

2.数组长度有相对固定的静态特性，当表中数据元素个数较多而且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。