数据结构导论系列①------线性表的基本预算：插入运算、删除运算、定位运算（含实现代码）

1、插入运算

顺序表的插入预算是在顺序表的第i个元素之前，插入一个新元素。使长度为n的线性表变为长度为n+1的线性表。

实现代码如下：

#include <iostream>
using namespace std;
typedef int DataType;
const int Maxsize = 8;
typedef struct
{
	DataType data[Maxsize];                       //存放数据的数组
	int length;                                   //顺序表的实际长度
}SeqList;                                         //顺序表类型名为SeqList
SeqList L;										  //定义L为一个顺序表

void InsertSeqlist(SeqList L, DataType x, int i)  //插入预算：将元素X插入到顺序表L的第i个数据
{
	if (L.length == Maxsize) cout << ("表已满");  //判断表内是否还有剩余空间（本人用vs中的C++进行的编辑，在输出上面与C略有差别，c语言中的输出语句是exit("表已满"）,此代码仅供梳理逻辑使用。
	if (i<1 || i>L.length + 1) cout << ("位置错");//判断插入的位置是否在表内，即是否合法，此代码中的L.lenth+1代表的意思是插入的数据不能空一格插入

	for (int j = L.length; j >= i; j--)           //for循环中i,j为下标：初始化j的值，为表长
		L.data[j] = L.data[j - 1];                //将L表中的数据后移
	L.data[i - 1] = x;                            //插入元素X
	L.length++;                                   //每成功插入一个元素，表L的长度加1
}

int main()
{
	SeqList L = { { 1,2,3,4,5,6,7 },8 };          //初始化顺序表
    InsertSeqlist(L,3,3};                         //将3插入到顺序表中第3个元素
}

2、删除运算

删除运算是指将线性表的第i个数据元素删除，使长度为n的线性表变为长度为n-1的线性表。

实现代码如下：

#include <iostream>
using namespace std;
typedef int DataType;
const int Maxsize = 8;
void DeleteSeqLIst(SeqList L, int i)              //删除运算：删除线性表中的第i个数据结点
{
	if (i<1 || i>L.length)                        //检查位置是否合法：如果删除的内容i<1或i>线性表的长度，即i超出了线性表的范围。
		cout << "非法位置" << endl;               //输出非法位置
	for (int j = i; j < L.length; j++)            //第i个元素的下标为i-1
		L.data[j - 1] = L.data[j];                //依次左移
	L.length--;
}

int main()
{
	SeqList L = { { 1,2,4,5,6,7,8 },8 };      //初始化顺序表
	DeleteSeqLIst(L,3 );                     //删除顺序表L中的第3个元素  
} 

3、定位运算

定位运算的功能是查找出线性表L中值等于x的结点序号的最小值，当找不到值为x的结点时，返回结果0。

实现代码如下：

#include <iostream>
using namespace std;
typedef int DataType;
const int Maxsize = 8;
int LocateSeqlist(SeqList L, DataType x)          //定位运算
{
	int i = 0;                                    //因为是从左往右，所以初始值的i为0
	while ((i < L.length) && (L.data[i] != x))    //当i小于顺序表长度且i的值不等于要定位的x的值：在顺序表中查找x的结点
		i++;                                      //i+1
	if (i < L.length)                             //如果i小于顺序表的长度
		return i + 1;                             //返回x元素的位置
	else
		return 0;                                 //否则未找到x元素的位置则返回0
}

int main()
{
	SeqList L = { { 1,2,4,5,6,7,8 },8 };         //初始化顺序表           
    int x = LocateSeqlist(L, 4);                 //查找值为4的结点序号并赋值给变量x
	cout << x << endl;                           //输出结点序号
}