线性表(顺序表)的初始化,取值,查找,插入及删除(c++)

一、问题描述:

顺序表中的基本操作以及描述(基本操作包括对线性表进行初始化,取值,查找元素,插入元素以及删除元素)

二、功能:

(1)初始化线性表:

构造一个空的顺序表,并将表的长度设置为0,具体代码实现如下:

Status InitList(SqList &L)
{
	L.elem=new ElemType[MAXSIZE];
	if(L.elem==NULL) return ERROR;
	L.length=0;
	return OK;
}

(2)存值

本用例为方便,仅存储5个数据,可以更改循环次数从而增加线性表刚开始存储元素的个数。

利用循环将5个值存入顺序表中,每一次存入都要将表的长度加一,记得形参这里的L一定要使用引

用传递,否则存入后线性表仍然是一个空的线性表

void Creat_n(SqList &L)//参数一定要使用引用
{
	ElemType c;
	printf("请输入线性表的5个值:\n");
	for(int i=1;i<=5;i++){
		scanf("%d",&c);
		L.elem[i]=c;
		L.length++;
	}
} 

(3)元素的取值

通过输入要取值的元素的位置来进行取值,并将取到的结果赋给同种变量类型e,在这里e同时也要使用引用传递,因为将取到的值赋给变量e后e的值已经发生改变了。同时要对输入的i值(所取元素的位置)进行判断,如果i值合理才能继续进行,否则需要找一个安全出口退出(return ERROR),具体代码如下:

Status GetElem(SqList L,int i,ElemType &e) 
{
	if(i<1 || i>L.length) return ERROR;
	e=L.elem[i];
	return OK;
} 

(4)元素的查找

元素的查找要使用逐一对比,从第一个元素开始依次与传进的值e进行对比,如果相同,返回i+1,如果没有与传入元素相同的值,返回0,具体代码实现如下:

int LocateElem(SqList L,ElemType e)
{
	for(int i=1;i<=L.length;i++)
		if(L.elem[i]==e) return i;
	return 0;
}

(5)元素的插入

插入元素首先判断插入的位置是否合理,及(i<1 || i>L.length+1),如果不合理,返回ERROR值,其次要判断该线性表的长度是否已经到达最大值MAXSIZE,如果达到,同样返回值ERROR,当插入位置合适并且线性表的长度没有到达最大值,进行元素的插入,将要插入的位置的后面所有元素依次向后移动一个位置(从后面开始移动),并将该元素插入指定位置,插入后,要将线性表的长度加1,具体代码实现如下:

Status ListInsert(SqList &L,int i,ElemType e)
{
	if(i<1 || i>L.length+1) return ERROR;
	if(L.length==MAXSIZE) return ERROR;
	for(int j=L.length;j>=i;j--)
		L.elem[j+1]=L.elem[j];
	L.elem[i]=e;
	++L.length;
	return OK;
} 

(6)元素的删除

同元素的插入一样,需要判断删除元素的位置是否合理,即(i<1 || i>L.length),但是不需要判断线性表的长度是否已经达到最大值,进行元素的删除时,要将该元素后面的元素一一向前挪动一个位置,删除元素后,要将线性表的长度减1,具体代码实现如下:

Status ListDelete(SqList &L,int i){
	if(i<1 || i>L.length) return ERROR;
	for(int j=i+1;j<=L.length;j++)
		L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
} 

(7)线性表的展示

线性表的展示直接利用循环遍历线性表中的每一个元素即可,这里的L不需要使用参数传递,因为只是简单的遍历输出元素,没有改变线性表元素的值,具体代码如下:

void Display(SqList L)
{
	printf("当前线性表为:\n");
	for(int i=1;i<=L.length;i++)
		 printf("%d ",L.elem[i]);
	printf("\n");
}

三、整体代码(注释及运行截图)

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct
{
	ElemType *elem;
	int length; 
}SqList;
 
//线性表的初始化 
Status InitList(SqList &L)
{
	L.elem=new ElemType[MAXSIZE];
	if(L.elem==NULL) return ERROR;
	L.length=0;
	return OK;
}
 
//线性表的存值
void Creat_n(SqList &L)
{
	ElemType c;
	printf("请输入线性表的5个值:\n");
	for(int i=1;i<=5;i++){
		scanf("%d",&c);
		L.elem[i]=c;
		L.length++;
	}
} 

//线性表的取值
Status GetElem(SqList L,int i,ElemType &e) 
{
	if(i<1 || i>L.length) return ERROR;
	e=L.elem[i];
	return OK;
} 
 
//线性表的查找元素
int LocateElem(SqList L,ElemType e)
{
	for(int i=1;i<=L.length;i++)
		if(L.elem[i]==e) return i;
	return 0;
}
 
//线性表的插入元素
Status ListInsert(SqList &L,int i,ElemType e)
{
	if(i<1 || i>L.length+1) return ERROR;
	if(L.length==MAXSIZE) return ERROR;
	for(int j=L.length;j>=i;j--)
		L.elem[j+1]=L.elem[j];
	L.elem[i]=e;
	++L.length;
	return OK;
} 
 
//线性表的删除元素
Status ListDelete(SqList &L,int i){
	if(i<1 || i>L.length) return ERROR;
	for(int j=i+1;j<=L.length;j++)
		L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
} 	
 
//打印线性表
void Display(SqList L)
{
	printf("当前线性表为:\n");
	for(int i=1;i<=L.length;i++)
		 printf("%d ",L.elem[i]);
	printf("\n");
}
 
int main()
{
	SqList L;
	ElemType e;
	int v,k,opt,p;
	p=InitList(L);
	if(p==0) printf("初始化失败!");
	else{
		printf("初始化成功\n");
		printf("请存入5个元素到线性表中\n"); 
		Creat_n(L); 
		printf("1:取出线性表中的某个值\n");
		printf("2:查找线性表中的元素\n");
		printf("3:将线性表中插入一个元素\n");
		printf("4:将线性表中删除一个元素\n");
		printf("5:展示当前线性表\n");
		printf("6:退出\n"); 
		
		while(1){	
			printf("请输入您的选择:");
			cin>>opt;
			if(opt==1){
				//取出线性表中的某个值 
				printf("请输入要取出值的位置:"); 
				cin>>v;
				p=GetElem(L,v,e);
				if(p==0) printf("输入位置非法\n");
				else
					printf("该值为:%d\n",e); 
			}
			else if(opt==2){
				//进行元素的查找
				printf("请输入您要查找的元素:");
				cin>>v;
				k=LocateElem(L,v);
				if(k==0) printf("输入位置非法\n");
				else
					printf("您所查找的元素所在位置为:%d\n",k);
			}
			else if(opt==3){
				//线性表元素的插入
				printf("请输入您要插入的元素及插入的位置:");
				cin>>v>>k;
				p=ListInsert(L,k,v);
				if(p==0) printf("输入位置非法\n");
				else
					Display(L);
			}
			else if(opt==4){ 
				//线性表元素的删除 
				printf("请输入您要删除第几个元素:");
				cin>>v; 
				p=ListDelete(L,v);
				if(p==0) printf("输入位置非法\n");
				else
					Display(L);
			}
			else if(opt==5){
				Display(L);
			}
			else if(opt==6){
				printf("退出成功");
				break; 
			}
		}
	}
}

运行截图

三、线性表(顺序表)的优点及缺点分析:

优点:顺序表可以随机存取表中的任一元素

缺点:插入和删除元素过于麻烦,都需要移动大量的数据,操作过程相对复杂,并且会导致存储空间的浪费。文章来源地址https://www.uudwc.com/A/woqzj/

原文地址:https://blog.csdn.net/m0_74472474/article/details/132817651

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月29日 10:05
Hadoop的安装实验报告
下一篇 2023年09月29日 11:05