目录

前言

一、顺序表的定义

二、顺序表的 C 语言描述

三、顺序表中基本操作的实现 

3.1结构初始化操作

3.1.1构造一个空的线性表 L

3.1.2构造一个含 n 个数据元素的线性表 L

时间复杂度:O(n)

3.2销毁结构操作

3.2.1销毁一个顺序表  

3.3加工型操作

3.3.1改变数据元素的值

3.3.2插入数据元素

3.3.3删除数据元素

3.3.4线性表置空 

3.4引用型操作

3.4.1线性表判空

3.4.2求线性表的长度

3.4.3求前驱

3.4.4求后继

3.4.5求线性表中某个元素

3.4.6定位函数

3.4.7遍历线性表

四、顺序表代码实现

五、结果

六、总结 

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一、顺序表的定义

由n(n≥0)个类型相同的数据元素构成的有限序列，称为线性表。线性表中数据元素的个数n称为线性表的长度。  n=0时，称为空表。

线性表的顺序存储表示是指用一组地址连续的存储单元依次存放线性表中的数据元素，即顺序表。

二、顺序表的 C 语言描述

代码如下（示例）：

//存储结构 #define  MAXSIZE 100     
//最大长度 typedef  struct 
{
    int *elem;
    int length;
} SqList;  // 顺序表

三、顺序表中基本操作的实现 

3.1结构初始化操作

3.1.1构造一个空的线性表 L

时间复杂度：O(1) 

void InitList(SqList &L)
{
	L.elem=new int[MAXSIZE];
	if (!L.elem) exit(0);//未分配成功 
	L.length=0;
	cout<<"初始化成功"< 
3.1.2构造一个含 n 个数据元素的线性表 L 
 
 
时间复杂度:O(n) 
 
空间复杂度:S(n)=O(1)
 
 
void CreateList(SqList &L,int n)
{
	int e;
	if(n>MAXSIZE)
	{
		cout<<"超出最大长度"<>e;
			L.elem[i]=e;
			L.length++;
		}
	} 
}
 
3.2销毁结构操作 
3.2.1销毁一个顺序表   
 
 
不空才释放空间，空的话就不需要释放了
 
 
注意用new来开辟空间，则用delete释放空间
 
 
而用malloc来开辟空间，则使用free来释放空间
 
 
void DestoryList(SqList& L)
{
	if (L.elem) delete L.elem;//不空才释放空间，空的话就不用了
}
 
3.3加工型操作 
3.3.1改变数据元素的值 
 
 
随机存取
 
 
时间复杂度：O(1)
 
 
空间复杂度：O(1)
 
 
void PutElem(SqList &L,int i,int &e )
{
	int t;
	cout<<"输入你想改成的值"<>t;
	if(i<1||i>L.length)	cout<<"i的位置不对"< 
3.3.2插入数据元素 
 
 
在顺序表L的第 i 个元素之前插入新的元素e
 
 
时间复杂度T(n)=O(n)
 
 
顺序表的空间复杂度S(n)=O(1)
 
 
没有占用辅助空间
 
 
// 在顺序表L的第 i 个元素之前插入新的元素e,
void ListInsert(SqList &L,int i,int e)
{ 
	if(i<1||i>L.length+1) cout<<"位置不合法n"<=i-1;j--)
				L.elem[j+1]=L.elem[j]; //插入位及之后元素下移
			L.elem[i-1]=e;
			L.length++; 
		}
	}
} 
 
3.3.3删除数据元素 
 
 
时间复杂度T(n)=O(n)
 顺序表的空间复杂度S(n)=O(1)
 
 
// 被删除元素之后的元素左移
// ListDelete
//T(n)=O(n)
//顺序表的空间复杂度S(n)=O(1)
void ListDelete(SqList &L, int i,int &e) 
{
	if((i<1)||(i>L.length))	cout<<"删除位置不对"< 
3.3.4线性表置空  
 
 
还占用原空间，只是把表长置为0，原来的数据都清除
 
 
//清空线性表
void ClearList(SqList& L)
{
	L.length = 0;//线性表长度置为0，但是还占用空间
}
 
3.4引用型操作 
3.4.1线性表判空 
 
 
用L.length来判断是否为空，长度为0则为空，返回1，不为空则返回0
 
 
//判断线性表是否为空
int ListEmpty(SqList L)
{
	if (!L.length)	return 1;//L.length==0返回true
	else return 0;
}
 
3.4.2求线性表的长度 
 
 
返回L.length即可得到长度
 
 
//求线性表长度
int ListLength(SqList& L)
{
	return L.length;
}
 
3.4.3求前驱 
 
 
cur_e为序号，即第几个元素，则元素下标为cur_e-1，那么它的前驱元素下标为cur_e-2
 
 
// （求前驱）
void PriorElem(SqList L,int cur_e,int &pre_e)
{
	if(cur_e<1||cur_e>L.length)	cout<<"cur_e的位置不对"< 
3.4.4求后继 
 
 
cur_e为序号，即第几个元素，则元素下标为cur_e-1，那么它的后继元素下标为cur_e
 
 
//（求后继）
void NextElem(SqList L,int cur_e,int &next_e )
{
	if(cur_e<1||cur_e>L.length)	cout<<"cur_e的位置不对"< 
3.4.5求线性表中某个元素 
 
 
i表示序号，是第几个元素的意思，对应下标是i-1
 
 
//取值（根据位置i获取相应位置数据元素的内容）
//i表示的是序号，是第几个元素，对应下标是i-1 
void GetElem(SqList L,int i,int &e)
{
	if(i<1||i>L.length)	cout<<"i的位置不对"< 
3.4.6定位函数 
 
 
顺序表上的查找操作的实现
 在顺序表中查询第一个满足判定条件的数据元素，
 若存在，则返回它的位序，否则返回 0 
 最好情况： T(n)=O(1)    最坏情况： T(n)=O(n)
 平均情况：假设每个元素的查找概率相等.
 ASL=(1+2+……n)/n=(n+1)/2
 T(n)=O(n) 
 
 
//顺序表上的查找操作的实现
//在顺序表中查询第一个满足判定条件的数据元素，
//若存在，则返回它的位序，否则返回 0 
// 最好情况： T(n)=O(1)    最坏情况： T(n)=O(n)
//平均情况：假设每个元素的查找概率相等.
//ASL=(1+2+……n)/n=(n+1)/2
//T(n)=O(n) 
int LocateElem(SqList L,int e) 
{	
	for (int i=0;i 
3.4.7遍历线性表 
 
 
时间复杂度:O(n)
 
 
空间复杂度:S(n)=O(1)
 
 
void ListTraverse(SqList L)
{
	for(int i=0;i 
 
四、顺序表代码实现 
代码如下（示例）：
 
#include 
using namespace std;
#define  MAXSIZE 100     //最大长度
typedef  struct sqlist{
	int *elem;
	int length;
}SqList;  // 顺序表
//初始化顺序表
//时间复杂度：O(1) 
void InitList(SqList &L)
{
	L.elem=new int[MAXSIZE];
	if (!L.elem) exit(0);//未分配成功 
	L.length=0;
	cout<<"初始化成功"<MAXSIZE)
	{
		cout<<"超出最大长度"<>e;
			L.elem[i]=e;
			L.length++;
		}
	} 
}    
//销毁一个线性表  
void DestoryList(SqList& L)
{
	if (L.elem) delete L.elem;//不空才释放空间，空的话就不用了
}

//清空线性表
void ClearList(SqList& L)
{
	L.length = 0;//线性表长度置为0，但是还占用空间
}
//求线性表长度
int ListLength(SqList& L)
{
	return L.length;
}
//判断线性表是否为空
int ListEmpty(SqList L)
{
	if (!L.length)	return 1;//L.length==0返回true
	else return 0;
}
//( 改变数据元素的值 )
void PutElem(SqList &L,int i,int &e )
{
	int t;
	cout<<"输入你想改成的值"<>t;
	if(i<1||i>L.length)	cout<<"i的位置不对"<L.length)	cout<<"cur_e的位置不对"<L.length)	cout<<"cur_e的位置不对"<L.length)	cout<<"i的位置不对"<L.length+1) cout<<"位置不合法n"<=i-1;j--)
				L.elem[j+1]=L.elem[j]; //插入位及之后元素下移
			L.elem[i-1]=e;
			L.length++; 
		}
	}
} 
// 被删除元素之后的元素左移
// ListDelete
//T(n)=O(n)
//顺序表的空间复杂度S(n)=O(1)
void ListDelete(SqList &L, int i,int &e) 
{
	if((i<1)||(i>L.length))	cout<<"删除位置不对"<>choice;
		switch(choice)
		{
			case 1:
				InitList(L);
				break;
			case 2:
				int n;
				cout<<"输入你需要多少个节点"<>n;
				CreateList(L,n);
				break;
			case 3:
				DestoryList(L);
				break;
			case 4:
				int i1,e1;
				cout<<"输入要改变的元素序号"<>i1;
				PutElem(L,i1,e1);
				cout<<"原来数据的值为"<>i2>>e2;
				ListInsert(L,i2,e2);
				break;
			case 6:
				int i3,e3;
				cout<<"输入要删除的元素位置"<>i3;
				ListDelete(L,i3,e3);
				cout<<"原来删除的元素数据:"<>i4;
				PriorElem(L,i4,e4);
				cout<<"该元素的前驱节点的数据："<>i5;
				NextElem(L,i5,e5);
				cout<<"该元素的后继节点的数据："<>i6;
				GetElem(L,i6,e6); 
				cout<<"该元素的数据："<>e7;
				cout<<"定位到的位置为："< 
 
五、结果 
 
图一
 
 
图二
 
 
图三
 
 
 
图四
 
 
 
图五
 
 
 
图六
 
 
 
 图七
 
 
 
图八
 
 
 
 
 
图九
 
图十 
 
 
 图十一
 
 ​​​
 
 图十二
 
 
图十三
 
 
 
图十四
 
 
 
图十五
 
 ​​​
 
 图十六
 
 
 
六、总结  
        看完王卓老师的视频后，我把顺序表的基本操作都实现了一遍，使我对顺序表有了更好的理解。顺序表有好的一面，比如存储密度大，可以随机存取表中任一元素，但是也有不好的一面，比如在插入、删除某一元素时，需要移动大量元素 浪费存储空间 属于静态存储形式，数据元素的个数不能自由扩充。针对这个缺点，我将在下一篇把自己学到的链表介绍给大家。