【数据结构与算法】线性表顺序存储结构

一.顺序表的存储结构定义

1.1定义

线性表的顺序表示又称为顺序存储结构或顺序映像，称为顺序表，其逻辑结构与存储结构一致：用一段地址连续的存储单元依次存储线性表的数据元素。

设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为：

所以，只要确定了存储顺序表的起始地址（即基地址```a1```），计算任意一个元素的存储地址的时间是相等的。

1.2 图示

如图可见顺序表的特点：地址连续，依次存放，随机存取和类型相同（即以物理位置相邻表示逻辑关系，任一元素均可随机存取），我们通常用一维数组表示顺序表，也就是把线性表中相邻元素存储在数组中相邻位置，从而导致数据元素的序号和存放它的数组下标之间具有一一对应的关系。

注意：
C语言中数组的下标是 从0开始 的，而顺序表中元素的序号是 从1开始 的，即线性表中第 i 个元素存储在数组中下标为 i-1 的位置。

1.3结构代码

#define LIST INIT SIZE 100    //线性表存储空间的初始分配量
typedef struct{ElemType elem[LIST_INIT_SIZE];//存放顺序表中的元素的一个数组，可以替换，事先定义int length;               //当前长度
}SqList;                      //SqList是存放ElemType类型元素的顺序表，指针指向第一个元素的地址

从上面代码我们可以看到，这里我们封装了一个结构，事实上就是对数组进行封装，增加了个当前长度的变量罢了。（通过sqlist这个结构对数组进行封装，多了一个length的变量）

总结一下：顺序存储结构封装需要三个属性。

1. 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。（类似队伍的第一个同学找到自己的位置）
2. 线性表的最大存储容量，数组长度maxsize（也就是我们总共买了多少张票）
3. data三个含义：首地址，地址常量，&data[0]
4. 线性表的当前长度：length（也就是总共来了多少人）

注意：数组的长度与线性表的当前长度需要区分一下：数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的。由于线性表中可以进行插入操作，所以数组长度要大于当前线性表的长度。

*C语言的内存动态分配

由上诉内容可知，[MaxSize]是固定的，存放地址也固定，下面我们介绍动态内存分配，可以重建或修改数组

• 获得这个根数组中基地址（第一个元素的地址），其他地址用下标来操作。

//先定义指针，用内存分配函数，动态分配内存定义空间
typedef struct{ElemType *elem;int length;
}SqList;//顺序表类型
L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);//分配MaxSize个ElemType类型的空间
//返回值类型是void*，所以要强转
//要保存这个地址到data中就要把malloc返回值强转为L.data的类型

二.顺序表基本运算

*参数传递

在学习顺序表基本运算之前，我们先了解一下相关的知识点——C++中的参数传递

1. 函数调用时传送给形参表的实参必须与形参三个一致：类型，个数，顺序

2. 参数传递有两种方式：传值方式（参数为整型，实型和字符型等）和传地址

3. 传地址有三种：参数为指针变量，参数为引用类型，参数为数组名

   注意：当指针变量做参数时，形参变化不影响实参（栈的创建和销毁）

   #include<iostream.h>
   void swap(float *m,float *n){float *t;t=m;m=n;n=t;
   }
   void main(){float a,b,*p1,*p2;cin>>a>>b;p1=&a;p2=&b;//即交换p1和p2的值不会影响a和b的值swap(p1,p2);
   }
   cout<<a<<endl<<b<<endl;
   

   • 数组名作参数

     • 数组可以看成const指针（特殊的指针），定义后不可修改

     • 传递的是数组的首地址

     • 对形参数组所做的任何改变都将反映到实参数组中

   //用数组做函数的参数，求10个整数的最大数
   #include<iostream.h>
   #define N 10//定义常量N为10
   int max(int b[]){//定义计算数组中最大数的函数int i,n;n=b[0];for(i=1;i<N;i++)if(n<b[i])n=b[i];return n;        
   }
   int max(int a[]);
   void main(){int a[10];int i,m;for(i=0;i<N;i++)cin>>a[i];m=max(a);cout<<"the max number is:"<<m;
   }
   

   • 引用类型做参数

     • 引用，它用来给一个对象提供一个替代的名字

     • 传递引用参数给函数与传递指针的效果是一样的，形参变化实参也发生变化。

     引用类型做形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量做参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。

     • 指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“*指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性交差；另一方面，在主函数的调用点处，必须用变量的地址作为实参。

     #include<iostream.h>
     void main(){int i=5;int &j=i;//j是一个引用类型，代表i的一个替代名i值改变时，j值也跟着改变，所以会输出i=7,j=7i=7;cout<<"i="<<i<<"j="<<j;
     }
     

     #include<iostream.h>
     void swap(float &m,float &n){float temp;temp=m;m=n;n=temp;
     }
     void main(){float a,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;
     }
     

4. 形参&L和L的区别：带&的是引用型参数，它是地址传递，其实参会随着形参的改变而改变；不带&的参数是一般参数，是值传递，其实参不会随着形参的改变而改变。所以，结构改变，并且需要传回这种改变的要用引用型参数，否则用一般参数。

• 引用L->length等同于(*L)length

2.1建立

这里介绍整体创建顺序表，即由数组元素a[0…n-1]创建顺序表L。其方法是将数组a中的每个元素依次放入顺序表中，并将n赋给顺序表的长度域。算法如下：

void CreatList(SqList *&L,ElemType a[],int n){//由a中的n个元素建立顺序表int i=0,k=0;//k表示L中元素的个数，初始值为0L=(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间while(i<n){//i扫描数组a的元素L->data[k]=a[i];//将元素a[i]存放到L中k++;i++;}L->length=k;//设置L的长度K
}

调用上述算法创建好L所指的顺序表之后，需要回传给对应的实参，也就是说L是输出型参数，所以在形参L的前面需要加上引用符"&".

2.2初始化(InitList(&L))

该运算功能是构造一个空的线性表L，实际上只需分配线性表的存储空间并将length域设置为0即可。算法如下：

void InitList(SqList *&L){L=(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间L->length=0;;//置空线性表的长度为0
}

本算法的时间复杂度为O(1)。

2.3销毁(DestroyList(&L))

该运算功能是释放线性表L占用的内存空间。算法如下：

void DestroyList(SqList *&L){free(L);//释放L所指的顺序表空间
}

本节的顺序表是通过malloc函数分配存储空间的，当不再需要顺序表时务必调用DestroyList基本运算释放其存储空间；否则，尽管系统会自动释放顺序表的指针变量L，但不会自动释放L指向的存储空间，如此可能会造成内存泄漏，本算法的时间复杂度为O(1).

2.4判断线性表是否为空表(ListEmpty(L))

该运算返回一个布尔值表示L是否为空表。若L为空表，返回true，否则返回false。算法如下：

bool ListEmpty(SqList *L){return(L->length==0);
}

2.5求线性表的长度(ListLength(L))

该运算返回顺序表L的长度，实际上只需返回length域的值即可。算法如下：

bool ListEmpty(SqList *L){return(L->length==0)
}

2.6输出线性表(DispList(L))

该运算依次输入L中各元素的值。算法如下：

void DispList(SqList *L){for(int i=0;i<L->length;i++)printf("%d",L->data[i]);printf("\n");
}

本算法中的基本操作为for循环中的printf语句，故时间复杂度为O(n)

2.7查找元素的操作(GetElem与LocateElem)

2.7.1按序号(GetElem(L,i,&e))

实现GetElem的具体操作，即将线性表L中的第i个位置元素值返回。就程序而言，我们只需要把数组第i-1下标的值返回即可。

bool GetElem(SqList *L,ElemType e){int i=0;while(i<1||i>L->length)return false;//参数i错误时返回falsee=L->data[i-1];//取元素的值return true;//成功找到元素时返回true
}

本算法的时间复杂度为O(1)

2.7.2按元素(LocateElem(L,e))

按运算顺序查找第一个值为e的元素的逻辑符号，若这样的元素不存在，则返回为0.算法如下：

int LocateElem(SqList *L,ElemType e){int i=0;while(i<L->length && L->data[i]!=e)i++;//查找元素eif(i>=L->length)return 0;//未找到时返回0elsereturn i+1;//找到后返回其逻辑符号
}

该算法的时间复杂度为O(n)

2.8插入数据元素(ListInsert(&L,i,e))

刚才我们提到过排队的问题，如果这时候有一个人要回到队列当中，我们应该怎么做，我们会找到他要插入位置的那个同学，让他以及它后面的同学全部往后移动一个位置，再将新同学安排在这个位置里面。所以我们插入算法的思路如下：

1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；
3. 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；
4. 将要插入元素填入位置i处；
5. 线性表长度+1;
   算法如下：

Status ListInsert(SqList *L,int i,ElemType e){int k;if(L->length==MAXSIZE){//顺序线性表已经满了return ERROR;}if(i<1||i>L->length+1){//当i不在范围内时return ERROR;}if(i<=L->length){//若插入数据位置不在表尾//将要插入位置后数据元素向后移动一位for(k=L->length-1;k>=i;k--){L->data[k+1]=L->data[k];}}L->data[i-1]=e;//将新元素插入L->length++;return true;
}

时间复杂度为O(n)

2.9删除数据元素(ListDelet(&L,i,&e))

我们完全可以借鉴前面插入数据元素的算法，得到删除数据算法的思路：

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

2. 取出删除元素

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

4. 表长-1

   算法如下：

Status ListDelet(SqList *L,int i,ElemType *e){int k;if(L->length==0){return ERROR;}if(i<1||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 true;
}

三.顺序表优缺点

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)。而在插入或删除数据时，时间复杂度都是O(n)。这就说明，它比较适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用。那么我们可以得出它的优缺点：

优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任意位置的元素。

缺点：

• 插入和删除操作需要移动大量元素。
• 当线性表长度变化较大时，难以确定存储空间的容量。
• 容易造成存储空间的“碎片”（因为申请空间的时候是一整块一整块地申请的，那么两块地的中间就会有一小块碎片的地方被浪费）