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

目录：

• 线性表之《顺序表的表示及基本操作的实现》
• • 一、顺序表的表示
  • • 1、静态顺序存储结构
    • 2、动态顺序存储结构
  • 二、顺序表基本操作的实现
  • • 1、初始化
    • 2、查找
    • 3、插入
    • 4、删除
    • 5、顺序表的操作

一、顺序表的表示

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);


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;
}

运行结果：