导读

  • 顺序表的基本概念及其特点
  • 顺序表的实现的一般功能:创建,插入,删除,查找
  • 实现代码

 

概念及特点:

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

 

优点:

存取速度高效,通过下标来直接存储

缺点:

1.插入和删除比较慢,

2.不可以增长长度

比如:插入或者删除一个元素时,整个表需要遍历移动元素来重新排一次顺序:

适用场景:频繁查询但很少用到插入与删除可以考虑顺序表

 

实现的功能:

创建一个顺序表首先要明确其顺序表的基本元素和结构体的定义

基本元素:存储空间Maxsize,记录基地址elem,实际的元素个数length

结构体:

#define Maxsize 100 //最大空间

typedef struct{

Elemtype *elem;

int length; // 顺序表的长度

}SqList;//sqlist等价于结构体

定义个顺序表L,写做:SqList L;

ElemType:

中文意思:元素的类型

是数据结构的书上为了说明问题而用的一个词。它是element type(“元素的类型”)的简化体。 因为数据结构是讨论抽象的数据存储和算法的,一种结构中元素的类型不一定是整型、字符型、浮点型或者用户自定义类型,为了不重复说明,使用过程中用“elemtype”代表所有可能的数据类型,简单明了的概括了整体。在算法中,除特别说明外,规定ElemType的默认是int型。

初始化:

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

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

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

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

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

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

return true;

}

创建:

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;

}

取值:

顺序表采用随机存储的方法任一元素都可以立即找到,时间复杂度为o(1),例如我们我取第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;

}

查找:

在顺序表中查找一个元素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):(n+1)/2

插入:

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

(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):n/2

删除:

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

时间复杂性分析:

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

(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):(n-1)/2

完整代码

#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;

}

 

 

 


初闻不知曲中意,再听已是曲中人