数据结构第3讲顺序表

水深无声 2022-06-08 02:47 156阅读 0赞

**数据结构 第3讲 顺序表**

顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。

顺序表可以分配一段连续的存储空间Maxsize，用elem记录基地址，用length记录实际的元素个数，即顺序表的长度，

![Center][]

**结构体的定义：**

![Center 1][]

结构体定义后，如果要定义个顺序表L，就可以写：

SqList L;

1. 顺序表初始化

初始化是指给顺序表分配一个预定义大小的空间，用基地址elem记录这段空间的首地址，里面什么都没用，元素个数为0。前面我们已经预定义好了一个最大空间数Maxsize，那么就用new分配这么大的空间，分配成功会返回空间的首地址。假设顺序表里面需要存储整型数，那么就可以这样初始化：

boolInitList(SqList &L) //构造一个空的顺序表L

\{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

L.elem=new int\[Maxsize\]; //为顺序表分配Maxsize个空间

if(!L.elem) return false; //存储分配失败

L.length=0; //空表长度为0

return true;

2. 顺序表创建

顺序表创建是向顺序表中输入数据，输入数据的类型要与类型定义中的类型一致。假设顺序表里面需要存储整型数，那么就可以这样创建：

boolCreateList(SqList &L) //创建一个顺序表L

\{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

int a,i=0；

while(a!=-1)

cin>>a;

if(L.length==Maxsize)

cout<<”顺序表已满！”

return false;

L.elem\[i++\]=a;

L.length++;

return true;

3. 顺序表取值

顺序表中的任何一个元素都可以立即找到，称为随机存取方式，例如我们我取第i个元素，只要i值是合理的（1≤i≤L.length），那么立即就可以找到该元素L.elem\[i-1\]：

bool GetElem(SqList L,int i,int &e)

if (i<1||i>L.length) return false;

//判断i值是否合理，若不合理，返回false

e=L.elem\[i-1\]; //第i-1的单元存储着第i个数据

return true;

![Center 2][]

4. 顺序表查找

在顺序表中查找一个元素e，需要从第一个元素开始顺序查找，依次比较每一个元素值，如果相等，则返回元素位置(第几个元素)，如果查找整个顺序表都没找到，则返回-1：

int LocateELem(SqList L,int e)

for (i=0;i< L.length;i++)

if (L.elem\[i\]==e) return i+1; //第几个元素，例如第5个元素，下标其实为4

return -1;

时间复杂性分析：

**最好情况：**如果元素正好在第一个位置，一次比较成功；时间复杂度为*O*(1);

**最坏情况：**如果元素正好在最后一个位置，需要比较*n*次成功，时间复杂度为*O*(*n*);

**平均情况：**假设每个元素查找概率均等，在第一个位置需要比较1次，第二个位置需要比较2次，…，最后一个位置，需要比较*n*次，把*n*种情况加起来平均，平均时间复杂度也为*O*(*n*)：

![Center 3][]

5. 顺序表插入

在顺序表中第*i*个位置之前插入一个元素*e*，需要从最后一个元素开始后移，…，直到把第*i*个元素也后移一位，然后把*e*放入第*i*个位置。

![Center 4][]

（1）判断插入位置*i*是否合法（1≤*i*≤L.length+1），可以在第*n*\+1个元素之前插入。

（2）判断顺序表的存储空间是否已满。

（3）将第*n*至第*i* 位的元素依次向后移动一个位置，空出第*i*个位置。

（4）将要插入的新元素*e*放入第*i*个位置。

（5）表长加1，插入成功返回true。

bool ListInsert\_Sq(SqList &L,int i ,int e)

if(i<1 || i>L.length+1) return false; //i值不合法

if(L.length==Maxsize) return false; //存储空间已满

for(j=L.length-1;j>=i-1;j--)

L.elem\[j+1\]=L.elem\[j\]; //从最后一个元素开始后移，直到第i个元素后移

L.elem\[i-1\]=e; //将新元素e放入第i个位置

L.length++; //表长增1

return true;

时间复杂性分析：

假设每个位置插入的概率均等，可以在第一个位置之前插入，第二个位置之前插入，…，最后一个位置之前，第*n*\+1个位置之前，一共有*n*\+1种情况，每种情况移动元素的个数是*n*\-*i*\+1，把所有情况加起来平均，平均时间复杂度为*O*(*n*)：

![Center 5][]

6. 顺序表删除

在顺序表中删除第*i*个元素，需要把该元素暂存到变量*e*，然后从*i*\+1个元素开始前移，…，直到把第*n*个元素也前移一位，然后把*e*放入第*i*个位置。

![Center 6][]

（1）判断插入位置*i*是否合法（1≤*i*≤L.length）。

（2）将欲删除的元素保留在*e*中。

（3）将第*i*\+1至第*n* 位的元素依次向前移动一个位置。

（4）表长减1，删除成功返回true。

bool ListDelete\_Sq(SqList &L,int i, int &e)

if((i<1)||(i>L.length)) return false; //i值不合法

e=L.elem\[i-1\]; //将欲删除的元素保留在*e*中

for (j=i;j<=L.length-1;j++)

L.elem\[j-1\]=L.elem\[j\]; //被删除元素之后的元素前移

L.length--; //表长减1

return true;

时间复杂性分析：

假设删除每个元素的概率均等，一共有*n*种情况，每种情况移动元素的个数是*n*\-*i*，把所有情况加起来平均，平均时间复杂度为*O*(*n*)：

![Center 7][]

完整代码

\#include <iostream>

using namespace std;

\#define Maxsize 100 //最大空间

typedef struct\{

int \*elem;

int length; // 顺序表的长度

\}SqList;

bool InitList(SqList &L) //构造一个空的顺序表L

\{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

L.elem=new int\[Maxsize\]; //为顺序表分配Maxsize个空间

if(!L.elem) return false; //存储分配失败

L.length=0; //空表长度为0

return true;

bool CreateList(SqList &L) //创建一个顺序表L

\{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

int a,i=0;

cin>>a;

while(a!=-1)

if(L.length==Maxsize)

cout<<"顺序表已满！";

return false;

L.elem\[i++\]=a;

L.length++;

cin>>a;

return true;

bool GetElem(SqList L,int i,int &e)

if (i<1||i>L.length) returnfalse;

//判断i值是否合理，若不合理，返回false

e=L.elem\[i-1\]; //第i-1的单元存储着第i个数据

return true;

int LocateELem(SqList L,int x)

for (int i=0;i<L.length;i++)

if (L.elem\[i\]==x) return i+1;//第几个元素，例如第5个元素，下标其实为4

return -1;

bool ListInsert\_Sq(SqList &L,int i ,int e)

if(i<1 || i>L.length+1)return false; //i值不合法

if(L.length==Maxsize) returnfalse; //存储空间已满

for(intj=L.length-1;j>=i-1;j--)

L.elem\[j+1\]=L.elem\[j\]; //从最后一个元素开始后移，直到第i个元素后移

L.elem\[i-1\]=e; //将新元素e放入第i个位置

L.length++; //表长增1

return true;

bool ListDelete\_Sq(SqList &L,int i,int &e)

if((i<1)||(i>L.length))return false; //i值不合法

e=L.elem\[i-1\]; //将欲删除的元素保留在e中

for (int j=i; j<=L.length-1; j++)

L.elem\[j-1\] =L.elem\[j\]; //被删除元素之后的元素前移

L.length--; //表长减1

return true;

void print(SqList L)

cout << "输出顺序表" <<endl;

for(int j=0;j<=L.length-1;j++)

cout<<L.elem\[j\]<<" ";

cout<<endl;

void DestroyList(SqList &L)

if (L.elem) delete \[\]L.elem; //释放存储空间

int main()

SqList myL;

int i,e,x;

cout << "1. 初始化\\n";

cout << "2. 创建\\n";

cout << "3. 取值\\n";

cout << "4. 查找\\n";

cout << "5. 插入\\n";

cout << "6. 删除\\n";

cout << "7. 输出\\n";

cout << "8. 销毁\\n";

cout << "0. 退出\\n";

int choose = -1;

while (choose != 0)

cout << "请选择:";

cin >> choose;

switch (choose)

case 1://初始化顺序表

cout << "顺序表初始化..." <<endl;

if(InitList(myL))

cout <<"顺序表初始化成功！" << endl;

else

cout <<"顺序表初始化失败！" << endl;

break;

case 2://创建顺序表

cout << "顺序表创建..." <<endl;

cout << "输入整型数，输入-1结束" <<endl;

if(CreateList(myL))

cout <<"顺序表创建成功！" << endl;

else

cout <<"顺序表创建失败！" << endl;

break;

case 3://取值

cout << "输入整型数i，取第i个元素输出" <<endl;

cin>>i;

if(GetElem(myL,i,e))

cout <<"第i个元素是： " <<e<< endl;

else

cout <<"顺序表取值失败！" << endl;;

cout << "第i个元素是： "<<e<< endl;

break;

case 4://查找

cout << "请输入要查找的数x:";

cin>>x;

if(LocateELem(myL,x)==-1)

cout <<"查找失败！" << endl;

else

cout <<"查找成功！" << endl;

break;

case 5://插入

cout << "请输入要插入的位置和要插入的数据元素e:";

cin>>i>>e;

if(ListInsert\_Sq(myL,i,e))

cout <<"插入成功！" << endl;

else

cout <<"插入失败！" << endl;

break;

case 6://删除

cout << "请输入要删除的位置i:";

cin>>i;

if(ListDelete\_Sq(myL,i,e))

cout <<" 删除成功！" << endl;

else

cout <<"删除失败！" << endl;

break;

case 7://输出

print(myL);

break;

case 8://销毁

cout << "顺序表销毁..."<<endl;

DestroyList(myL);

break;

return 0;

[Center]: /images/20220608/b89b94108dd546bb9fa6280477381e55.png
[Center 1]: /images/20220608/880bd623cdc94be99434017bb31daf57.png
[Center 2]: /images/20220608/e8ec0a9a381644899ca8720bf2ce7eb8.png
[Center 3]: /images/20220608/f55e2c5113da438cbbce0261a0a94244.png
[Center 4]: /images/20220608/4cfc2408850c4f9595c1dba28d7395f8.png
[Center 5]: /images/20220608/4abc1386048f4274bcf1967a9c88ef9b.png
[Center 6]: /images/20220608/cc194b43ec904a2abbfb4c4cc91be3ce.png
[Center 7]: /images/20220608/3fb70f9e3d4f4da2adbbe7da5d60fecc.png