C++顺序表的基本操作实现

目录

• 1.顺序表的定义
• 2.顺序表上基本操作的实现
• 完整代码如下：
• 总结

1.顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧邻这存储的是第i+1个元素，称 i 为元素ai在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序和物理顺序相同。

假定线性表中的元素类型为ElemType,则线性表的顺序存储为

#define ElemType int
#define MaxSize 50  //定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize] //顺序表的元素
    int length; //顺序表的当前长度
}SqList;   //顺序表的类型定义

此时，一维数组是静态分配，由于数组的大小和空间事先已经固定，一单空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

2.顺序表上基本操作的实现

（1）初始化操作
初始化顺序表。构造一个空的线性表。

void IniteList(SqList &L){
	memset(L.data,0,sizeof(L)); //将顺序表L中的数据初始化为0
	L.length = 0;
}

注意： “&”表示C++中的应用调用，后面就不一一赘述了！
（2）创建顺序表

bool CreateList(SqList &L,int n){
	if(n<0||n>MaxSize){  //创建顺序表的个数不合理
		return false;
	}
	L.length = n;
	cout << "请依次输出" << n <<"个数并用空格隔开：";
	for(int i=0;i<L.length;i++){
		cin >> L.data[i];
	}
	return true;
}

（3）插入操作
在顺序表L的第i（1 <= i <= L.length+1)个位置插入新元素e。若 i 的输入不合法，则返回false,表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e,顺序表的长度加1，插入成功，返回true.

bool InserteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1){
		return false;
		cout << "插入位置不合法！";
	}
	if(L.length == MaxSize){
		return false;
		cout << "当前顺序表空间已满！";
	}
	for(int j=L.length;j>=i;j--){  //先移动最后一个元素，在移动其他的
		L.data[j]=L.data[j-1];//将i以及i之后的所有元素都往后移
	}
	L.data[i-1]=e; //注意：先后移完之后在插入
	L.length++;
	return true;
}

注意： 区别顺序表的位序和数组下标。前者是从1开始，后者是从0开始。
（4）删除操作
删除顺序表L中的第 i （1 <= i <= L.length) 个位置的元素，用应用变量e返回。若 i 的输入不合法，则返回 false;否则，将被删除元素赋给引用变量e,并将第 i + 1 个元素及其后的所有元素依次往前移动一个位置，返回true。

bool DeleteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length){
		return false;
	}
	e=L.data[i-1]; //将所删除的元素赋值给 e
	for(int j=i;j<L.length;j++){  //j = i,在数组中下标表示就是所删除元素后面第一个元素
		L.data[j-1]=L.data[j]; //将i之后的元素都往前移
	}
	L.length--;
	return true;
}

（5）查找（按值查找）
在顺序表L中查找第一个元素值等于 e 的元素，并将其返回。

int Search1_List(SqList &L,ElemType e){
	int j=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i] == e){
			j=i+1;   //下标为 i 的元素值等于 e ,将其返回其位序 i+1
		}
	}
	return j;
}

（6）查找（按序查找）
在顺序表中返回指定位置的元素。

int Search2_List(SqList &L,int i){
	if(i<1||i>L.length){
		cout << "查找位置不合理！";
	}
	return L.data[i-1];
}

（7）打印操作
按前后顺序打印线性表L中的所有值。

void PrintList(SqList L){
	cout << "顺序表中所有元素为：";
	for(int j=0;j<L.length;j++){
		cout << L.data[j] << " ";
	}
	cout <<endl;
}

完整代码如下：

/* 创建顺序表 实现插入，删除，按值查找，按序查找，打印顺序表 */
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<string.h>
#define ElemType int
#define MaxSize 100
using namespace std;
typedef struct{
	ElemType data[MaxSize];
	int length; //数序标的长度
}SqList;
//初始化顺序表
void IniteList(SqList &L){
	memset(L.data,0,sizeof(L)); //将顺序表L中的数据初始化为0
	L.length = 0;
}
//创建顺序表函数
bool CreateList(SqList &L,int n){
	if(n<0||n>MaxSize){
		return false;
	}
	L.length = n;
	cout << "请依次输出" << n <<"个数并用空格隔开：";
	for(int i=0;i<L.length;i++){
		cin >> L.data[i];
	}
	return true;
}
//顺序表L中在第i个位插入元素
bool InserteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1){
		return false;
		cout << "插入位置不合法！";
	}
	if(L.length == MaxSize){
		return false;
		cout << "当前顺序表空间已满！";
	}
	for(int j=L.length;j>=i;j--){
		L.data[j]=L.data[j-1];//将i以及i之后的所有元素都往后移
	}
	L.data[i-1]=e; //注意：先后移完之后在插入
	L.length++;
	return true;
}
//删除顺序表L中第i个元素的位置上
bool DeleteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length){
		return false;
	}
	e=L.data[i-1]; //将所删除的元素赋值给 e
	for(int j=i;j<L.length;j++){
		L.data[j-1]=L.data[j]; //将i之后的元素都往前移
	}
	L.length--;
	return true;
}
//查找(按值查找）函数
int Search1_List(SqList &L,ElemType e){
	int j=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i] == e){
			j=i+1;
		}
	}
	return j;
}
//查找(按序查找）函数
int Search2_List(SqList &L,int i){
	if(i<1||i>L.length){
		cout << "查找位置不合理！";
	}
	return L.data[i-1];
}
//打印输出顺序表函数
void PrintList(SqList L){
	cout << "顺序表中所有元素为：";
	for(int j=0;j<L.length;j++){
		cout << L.data[j] << " ";
	}
	cout <<endl;
}
//创建
void Create(SqList &L){
	int n;bool flag;
	cout << "请输入所创建顺序表中元素的个数：";
	cin >> n;
	flag = CreateList(L,n);
	if(flag){
		cout << "创建成功！";
		PrintList(L);
	}
	else
	  cout << "创建失败！";
}
//插入
void Insert(SqList &L){
	int i;
	int e;
	bool flag;
	cout << "请输入插入位置和所插元素：";
	cin >> i >> e;
	flag = InserteList(L,i,e);
	if(flag){
		cout << "插入成功！\n" << "插入后" ;
		PrintList(L);
	}
	else
	  cout << "插入失败！";
}
//删除
void Delete(SqList &L){
	int i; int e; bool flag;
	cout << "请输入删除位置：";
	cin >> i;
	flag = DeleteList(L,i,e);
	if(flag){
		cout << "删除成功！" << "删除后";
		PrintList(L);
	}
	else
	  cout << "删除位置不合法！";
}
//按值查找
void Search_1(SqList &L){
	int e,a;
	cout << "请输入要查找的值：";
	cin >> e;
	a = Search1_List(L,e);
	cout << e << "在顺序表L中的位置为："<< a << endl;
}
//按序查找
void Search_2(SqList &L){
	int i;
	cout << "请输入要查找的位置：\n";
	cin >> i;
	int j = Search2_List(L,i);
	cout << "顺序表L第" << i << "个位置上的元素为" << j;
}
int main(){
	SqList L;
	IniteList(L);
	Create(L);
	Insert(L);
	Delete(L);
	Search_1(L);
	Search_2(L);
	return 0;
}

编译器DEVC++:
编译结果：

总结

到此这篇关于C++顺序表的基本操作实现的文章就介绍到这了,更多相关C++顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！