【数据结构】线性表的顺序存储结构_顺序线性表

     

目录

【线性表的一些基础概念】

【线性表的顺序表示---顺序表】

1、顺序表：

2、顺序表的缺点和优点

优点：

缺点：

【顺序表的实现】

一、顺序表的结构体

二、顺序表初始化

三、打印顺序表

四、寻找指定元素，函数返回值为指定元素的位序

五、尾插法插入元素

六、头插法插入元素

七、在指定位序插入元素

八、寻找该表中最小值以及下标：

九、找到列表最小的值 并且删除它，移动最后一个元素去填充它

十、删除指定位序元素，并用e返回

十一、要求时间复杂度为O（1），空间复杂度为O（n），删除顺序表中所有值为x 的元素

---

---

【线性表的一些基础概念】

线性表：是具有相同数据类型的n(>=0）个数据元素的有限序列（序列：先来后到）

位序和下标：位序是1开始，下标是从0开始。

1、第一个元素没有前驱，最后一个元素没有后继

2、其他元素有且只有一个前驱和后继

3、线性表所处理的数据是有限的。

如何去判断一个结构是不是线性表？

1、是否是一对一

2、类型是否相同

3、是否是有限序列？

4、逻辑结构？

补充：关于数据结构中存储方式和存取方式：

存储方式：

四种：顺序存储、链式存储、索引存储、散列存储。

存取方式：

二种：随机存取，顺序存取。

对于线性表而言：有顺序表和链表两种

线性表是属于逻辑结构。

而顺序表是采用顺序存储对线性表的实现，是存储结构。

链表是采用链式存储对线性表的实现，是存储结构

这里我们接收线性表的顺序存储结构：

【线性表的顺序表示---顺序表】

1、顺序表：

按照逻辑顺序，依次存储到指定位置开始的一块连续存储空间，物理上就是相邻的。 是线性表的顺序存储结构。“数组实现” 地址是连续的。 逻辑相邻的两个元素物理上也相邻

2、顺序表的缺点和优点

线性表的顺序存储结构，也就是顺序表。在存、读取数据时候，不管在哪个位置，时间复杂度都是O（1），而在插入和删除、查找时，时间复杂度都是O（n）

优点：

一、顺序表在查找数据元素的时候时间复杂度为O（1），很方便查找和访问

二、相较于链表而言，存储密度更高。

缺点：

一、在删除和插入元素的时候，需要移动大量的元素，所以时间复杂度为O（n），但是链表时间复杂度为O（1）。

【顺序表的实现】

一、顺序表的结构体

1.静态存储结构

#define MaxSize 50 //规定大小
//顺序表的静态分配
typedef struct{
     ElemType data[MaxSize];
     int len;
}SqList;

2.动态存储结构

typedef  int elemtpye;  //对应元素类型需要在这里修改，在我这里面就是int类型
 
typedef struct {
    elemtpye *data;
    int len;
    int Maxsize;
}Sqlist;

二、顺序表初始化

1.静态存储：只需要将len变为0

void initSqlist(Sqlist &l){
    l.len=0;
}

2.动态存储

void init_list(list &l,int initsize) //初始化顺序表
{
    l.data = (elemtpye *)malloc(sizeof(elemtpye)*initsize);
    l.Maxsize = initsize;
    l.len  = 0;
}

三、打印顺序表

void print_list(list l)  //打印顺序表,不涉及修改不需要引用
{
    for(int i=0;i<l.len;i++)
    {
        cout<<l.data[i]<<" ";
    }
    cout<<endl;
}

四、寻找指定元素，函数返回值为指定元素的位序

int localElem(list &l,elemtpye a)
{
    for (int j=0;j<l.len;j++){
        if(l.data[j]==e)
            return j+1;
    }
    return  0;
}

五、尾插法插入元素

bool pushback_list(list &l,elemtpye a)
{
    if(l.len == l.Maxsize)
    {
        cout<<"list is full"<<endl;
        return false;
    }
    else
    {
        l.data[l.len] = a;
        l.len++;
        return  true;
 
    }
}

六、头插法插入元素

bool popback(list &l,elemtpye e)
{
    if(l.len == l.Maxsize)
    {
        cout<<"list is full"<<endl;
        return false;
    }
    else
    {
 
        for(int i =l.len;i>=0;i--)
        {
            l.data[i] = l.data[i-1];
        }
        l.data[0] = e;
        l.len++;
        return  true;
    }
}

七、在指定位序插入元素

bool insert_list(list &l,int i,elemtpye a)
{
 
     if(i<1 || i>l.len+1||l.len >= l.Maxsize)
    {
        return false;
    }
     else
    {
         for(int j = l.len;j>=i;j--)
         {
             l.data[j] = l.data[j-1]; //从后开始，将插入位置后面的所有元素都往后移动一位
          }
         l.data[i-1] = a;
         l.len++;
         return true;
     }
}

八、寻找该表中最小值以及下标：

void  find_min(list &l,int &index,elemtpye &target)
{
     index = 0;
     target = l.data[index];  //一开始假设最小值是第一个元素，往后遍历，找到更小的，就更新index和target
   // l.data[index] = target; //最小值
    for(int i=1;i<l.len;i++)
    {
         if(l.data[i]<target)
         {
             index = i;
             target = l.data[i];
         }
    }
}

九、找到列表最小的值 并且删除它，移动最后一个元素去填充它

bool  my_fun(list &l,elemtpye &min)  //找到最小值删除它，然后使用最后一个元素去填补它。
{
    if(l.len == 0)
    {
        return  false;
    }
    int index_min =0;
     min = l.data[index_min];
    for(int i = 1;i<l.len;i++)
    {
        if(l.data[i]<min)
        {
            min = l.data[i];
            index_min = i;
        }  //找到最小值
    }
    l.data[index_min] = l.data[l.len-1];
    l.len--;
     return  true;
}

十、删除指定位序元素，并用e返回

bool ListDelete(SqList &l, int i, ElemType &e)
{
    if(l.len<0 || i<1 || i>l.len) return false;
    e = l.data[i-1];
    for (int j=i;j<l.len;j++) {
        l.data[j-1]=l.data[j];
    }
    l.len--;
    return true;
 
}

十一、要求时间复杂度为O（1），空间复杂度为O（n），删除顺序表中所有值为x 的元素

void deleteValue(Sqlist &l,ElemType x)
{
    int i=0,k=0;
    while(i<l.len){
        if(L.data[i]==x)
            k++;
        else {
            L.data[i-k]=l.data[i];
            i++;
            l.length-=k;
        }
}