线性表之《顺序表的表示及基本操作的实现》

云惠网小编 2020年9月30日08:30:32
评论
3967字阅读13分13秒
广告也精彩

线性表之《顺序表的表示及基本操作的实现》

目录:

一、顺序表的表示

1、静态顺序存储结构

/*线性表静态顺序存储结构*/
#define MAXSIZE 100 //定义线性表的最大长度
typedef int ElemType; //定义抽象类型ElemType为int类型
typedef struct
{
	ElemType elem[MAXSIZE]; //声明一个ElemType类型的数组elem
	int length; //顺序表的当前长度
}SqList; //此结构为SqList类型

2、动态顺序存储结构

/*线性表动态顺序存储结构*/
#define MAXSIZE 100 //定义线性表的最大长度
typedef int ElemType; //定义抽象类型ElemType为int类型
typedef struct
{
	ElemType* elem;//存储空间的基地址
	int length;//当前长度
}SqList;

二、顺序表基本操作的实现

补充:操作算法中用到的预定义常量和类型

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型,其值是函数结果状态代码
typedef int Status;

线性表的定义:

#define MAXSIZE 100 //定义线性表的最大长度
typedef int ElemType; //定义抽象类型ElemType为int类型
typedef struct
{
	ElemType* elem;//存储空间的基地址
	int length;//当前长度
}SqList;

1、初始化

算法思想
(1)为顺序表动态分配一个预定义大小的数组空间,使elem指向这段空间的基地址
(2)使该顺序表的当前长度为0

/*顺序表的初始化*/
typedef int Status;
Status InitList(SqList& L)//修改线性表,按引用传递
{
	L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
	if (!L.elem)  //开辟存储空间失败
		exit(OVERFLOW); 
	L.length = 0; //线性表的长度为0
	return OK;
}

2、查找

算法思想:
(1)从第一个元素起,依次和e相比较
(2)若第i个元素的值等于e,则查找成功,返回该元素的位序 i + 1
(3)若查遍整个顺序表都没有找到,则查找失败,返回0

/*顺序表的查找*/
int LocateElem(SqList L, ElemType e)
{
	for (i = 0;i < L.length;i++) //i 为下标序号
		if (L.elem[i] == e)
			return i + 1; //查找成功,返回i+1
	return 0; //查找失败,返回0
}

3、插入

算法思想:
(1)检查插入的位置i是否合法(合法范围 1 <= i <= n + 1), 若不合法返回ERROR
(2)检查数组空间是否存满,若存满返回ERROR
(3)从第n个元素到第i个元素依次往后移动一位
(4)将要插入的元素存到第i个位置
(5)表长 + 1
(6)插入成功,返回OK

/*顺序表的插入*/
typedef int ElemType;
typedef int Status;
Status ListInsert(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1) return ERROR;//插入位置不合法
	if (L.length == MAXSIZE) return ERROR;//数组空间已满
	for (j = L.length - 1;j >= i - 1;j--)
		L.elem[j + 1] = L.elem[j];//插入位置及之后元素后移
	L.elem[i - 1] = e;//新插入的元素e存到i-1
	++L.length;//表长+1
	return OK;
}

4、删除

算法思想
(1)判断删除元素位置是否合法
(2)将删除元素存入到e中
(3)将第i - 1到第i个元素依次往前移动一位
(4)表长 - 1,删除成功返回OK

/*顺序表的删除*/
typedef int Status;
typedef int ElemType;
Status ListDelete(SqList& L, int i, ElemType& e)
{
	if (i < 1 || i > L.length + 1) return ERROR;//判断位置是否合法
	e = L.elem[i - 1];//删除元素存入e
	for (j = i, j <= L.length -1, j++)
		L.elem[j - 1] = L.length[j];
	--L.length;
	return OK;
}

5、顺序表的操作

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100
#define OK 1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define ERROE 0

typedef int ElemType;
typedef int Status;

/*定义顺序表*/
typedef struct
{
	ElemType* elem;//数组空间基指针
	int length;
}SqList;

Status InitList_Sq(SqList& L);/*初始化顺序表*/
void InputList_Sq(SqList& L);/*顺序表的输入*/
void Output_Sq(SqList& L);/*顺序表的输出*/
int LocateElem_Sq(SqList L, ElemType e);/*顺序表的查找*/
Status InsertList_Sq(SqList& L, int i, ElemType e);/*顺序表的插入*/
Status DeleteList_Sq(SqList& L, int i, ElemType e);/*顺序表的删除*/

/*main函数*/
int main(void)
{
	SqList L;//顺序表L
	int i, value;
	InitList_Sq(L);//初始化顺序表
	InputList_Sq(L);//顺序表的输入
	Output_Sq(L);//顺序表的输出

	printf("n请输入要查找的元素:");
	int e;
	scanf_s("%d", &e);//输入要查找的元素
	int locate = LocateElem_Sq(L, e);
	printf("要查找元素所在的位置为:第 %d 位",locate);

	printf("n请输入要插入的位置i:");
	scanf_s("%d", &i);
	printf("请输入要插入的元素:");
	scanf_s("%d", &e);
	value =  InsertList_Sq(L, i, e);//插入元素
	if (value)
		Output_Sq(L);//输出
	else
		printf("插入失败!");

	printf("n请输入要删除元素的位置i:");
	scanf_s("%d", &i);
	value = DeleteList_Sq(L, i, e);//删除元素
	if (value)
		Output_Sq(L);//输出
	else
		printf("删除失败!");
	return 0;
}

/*初始化顺序表*/
Status InitList_Sq(SqList& L)
{
	L.elem = new ElemType[MAXSIZE];//开辟空间
	if (!L.elem) exit(OVERFLOW);//分配空间失败
	L.length = 0;//定义表长为0
	printf("顺序表初始化成功!n");//初始化提示
	return OK;
}

/*顺序表的输入*/
void InputList_Sq(SqList& L)
{
	int n;
	printf("请输入顺序表的长度:");
	scanf_s("%d", &n);
	L.length = n;
	if (n > MAXSIZE)//检查输入的长度是否合法
		printf("数组长度不合法!");
	else
	{
		printf("请输入%d个元素:n", n);
		for (int i = 0;i < L.length;i++)
		{
			printf("第%d个元素为:", i);
			scanf_s("%d", &L.elem[i]);
		}
	}
}

/*顺序表的输出*/
void Output_Sq(SqList& L)
{
	printf("当前顺序表的元素依次是:");
	for (int i = 0;i < L.length;i++)
		printf("%d ", L.elem[i]);
}

/*顺序表的查找*/
int LocateElem_Sq(SqList L, ElemType e)
{
	for (int i = 0;i < L.length;i++)
		if (L.elem[i] == e) return i + 1;//查找成功返回i+1
	return 0;
}

/*顺序表的插入*/
Status InsertList_Sq(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1) return ERROE;//i值不合法
	if (L.length == MAXSIZE) return ERROE;//存储空间已满
	for (int j = L.length - 1;j >= i - 1;j--)
		L.elem[j + 1] = L.elem[j];//插入位置后面的元素依次往后移动
	L.elem[i - 1] = e;//新插入的元素存在i - 1 中
	++L.length;//表长+1
	return OK;
}

/*顺序表的删除*/
Status DeleteList_Sq(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length) return ERROE;// i值不合法
	e = L.elem[i - 1];//将删除的元素存入到e中
	for (int j = i;j <= L.length - 1;j++)
		L.elem[j - 1] = L.elem[j];//将i位置后面的元素往前移动一位
	--L.length;//表长-1
	return OK;
}

运行结果:

腾讯云618
未分类
云惠网小编
SpringCloud -- Config、Bus解析

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
[深度解剖C语言] --关键字 static

[深度解剖C语言] –关键字 static

static ---最名不副实的关键字目录1.static修饰全局变量2.static修饰函数3.static修饰局部变量static的作用:1.static修饰全局变量我们创建两...
Java数据结构-认识顺序表

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论