顺序链表简单操作

2024-03-19 19:16:04

文章目录

顺序表

/*
*@author zhazhazhi
*qq:2055418639
*github:zhazhazhi7
*/

顺序表

什么是顺序表？

顺序表是用来储存数据的一种结构，它会获取计算机一段连续等长的存储空间来存储数据，数组便是最常见也最方便的使用方法

顺序表由于存储位置连续，有容易浪费存储空间的缺点，但是顺序表在查询存储位置的时候非常的方便，只要输入位置信息（头地址，存储的位置），就能很快地找到数据。

顺序表的基本操作

顺序表完全可以使用数组来直接构造，其定义代码如下：

#define MAXIN 20//初定义

typedef int ELemType;
typedef struct{
    ElemType *data[MAXIN];//数据存放的数组
    int len;
}SqList;

但是顺序表的缺点在于储存的浪费，所以还是建议使用动态分配的方法来建立顺序表（但是在最后要注意将分配地址释放，避免数据溢出），下面是利用动态分配的方法构造的顺序表：

#define MAXIN 20
#define ADD 20//分配地址不够用时方便添加
typedef int ElemType ;//初定义

typedef struct {
	ElemType *head;//头指针用来确定顺序表的位置
	int len;//顺序表储存数据的长度
	int size;//顺序表的长度
}SqList;//定义顺序表

接下来就是顺序表的基本操作了，最后会附上包括验证的完整的代码，定义部分与上文相同：

初始化顺序表：

int InitList(SqList &L){
	L.head = (int *)malloc(MAXIN*sizeof(int));//给头指针分配地址
	if(!L.head){//确认地址分配成功
		cout<<"地址分配失败"<<endl;
		return 0;
	}
	L.len=0;//初始化顺序表的数据长度，因为没有放数据所以该变量为0
	L.size = MAXIN;//初始化表长度，为MAXIN
	cout<<"初始化成功"<<endl; 
	return 0;
}//初始化顺序表

打印顺序表：

void Print(SqList L){
	cout<<"当前的顺序表为："<<endl;
	for(int i=0;i<L.len;i++){
		cout<<L.head[i]<<" ";
	}
	cout<<endl;
}//打印

插入数据：

int InsertList(SqList &L,int i,ElemType e){
    //确认插入的位置是否有误
	if(i<0||i>L.size){
		cout<<"插入位置错误"<<endl;
		return 0;
	}
    //如果插入时存储位置不够则需要再扩增存储空间
	if(L.len==L.size){
		L.head = (int *)malloc((MAXIN+ADD)*sizeof(int));
		L.size+=ADD;
		if(!L.head){
			cout<<"地址分配失败"<<endl;
			return 0;
		}
	}
    //将该位置后的数据各向后移动一位
	for(int j = L.len-1 ;j>=i-1;j--){
		L.head[j+1] = L.head[j];
	} 
    //给插入位置赋值
	L.head[i-1] = e;
	L.len++;//顺序表数据存储长度加一位
	cout<<"插入成功"<<endl;
	return 0;
}//插入

删除数据：

int DeleteList(SqList &L,int i){
	if(i<0||i>L.len){//判断删除位置是否有误
		cout<<"删除的位置有误"<<endl;	
		return 0;
	}
    //将改位置之后的所有数据向前移动一位
	for(int j = i-1;j<L.len;j++){
		L.head[j] = L.head[j+1];
	}
	cout<<"删除成功"<<endl;
	return 0;
}//删除

在删除与插入操作中，我们一定记得要确认删除或插入的位置是否符合要求，避免数据溢出。

在插入操作中，插入的位置之后所有的数据都要向后移动。

for(int j = L.len-1 ;j>=i-1;j--){
		L.head[j+1] = L.head[j];
	}

删除时也要进行移位操作，所有该位置之后的数据向前移动一位。

for(int j = i-1;j<L.len;j++){
		L.head[j] = L.head[j+1];
	}

完整代码：

#include<bits/stdc++.h>

using namespace std;

#define MAXIN 20
#define ADD 20
typedef int ElemType ;

typedef struct {
	ElemType *head;
	int len;
	int size;
}SqList;//定义顺序表 

int InitList(SqList &L){
	L.head = (int *)malloc(MAXIN*sizeof(int));
	if(!L.head){
		cout<<"地址分配失败"<<endl;
		return 0;
	}
	L.len=0;
	L.size = MAXIN;
	cout<<"初始化成功"<<endl; 
	return 0;
}//初始化顺序表 

int CreateList(SqList &L){
	int n,m;
	cout<<"请输入顺序表的长度"<<endl;
	cin>>n;
	if(n<0||n>MAXIN){
		cout<<"输入的顺序表长度有误"<<endl;
		return 0;
	}
	cout<<"请输入顺序表的数据"<<endl;
	for(int i=0;i<n;i++){
		cin>>L.head[i];
	}
	L.len += n;
	cout<<"顺序表创建成功"<<endl;
	for(int i=0;i<n;i++){
		cout<<L.head[i]<<" ";
	}
	cout<<endl;
}//创建新的顺序表 

int InsertList(SqList &L,int i,ElemType e){
	if(i<0||i>L.size){
		cout<<"插入位置错误"<<endl;
		return 0;
	}
	if(L.len==L.size){
		L.head = (int *)malloc((MAXIN+ADD)*sizeof(int));
		L.size+=ADD;
		if(!L.head){
			cout<<"地址分配失败"<<endl;
			return 0;
		}
	}
	for(int j = L.len-1 ;j>=i-1;j--){
		L.head[j+1] = L.head[j];
	} 
	L.head[i-1] = e;
	L.len++;
	cout<<"插入成功"<<endl;
	return 0;
}//插入 

int DeleteList(SqList &L,int i){
	if(i<0||i>L.len){
		cout<<"删除的位置有误"<<endl;	
		return 0;
	}
	for(int j = i-1;j<L.len;j++){
		L.head[j] = L.head[j+1];
	}
	cout<<"删除成功"<<endl;
	return 0;
}//删除 

void Print(SqList L){
	cout<<"当前的顺序表为："<<endl;
	for(int i=0;i<L.len;i++){
		cout<<L.head[i]<<" ";
	}
	cout<<endl;
}//打印 

int main(){
	SqList L;
	InitList(L);
	CreateList(L);
	Print(L);
	int n,i;
	cout<<"请输入你要插入的数，位置"<<endl;
	cin>>n>>i;
	InsertList(L,i,n);
	Print(L);
	cout<<"请输入删除的位置"<<endl; 
	cin>>i;
	DeleteList(L,i);
	Print(L); 
	return 0;
}

谢谢阅读！

码农公寓