线性表的基本操作介绍

线性表的基本操作有哪些？赢咖4小编来告诉大家。

线性表

​线性表总的来说其实就是一个简单的一维数组，那么从这里就可以看出线性表的特点—有限，因为数组在定义的时候就需要声明数组的空间大小，或者说是可以保存到数据元素的个数。同时根据数组的特点，线性表中每个元素，除了头和尾，都有一个直接前驱和直接后继，例如对于元素a [ i ] a[i]a[i]，它的直接前驱就是a [ i − 1 ] a[i-1]a[i−1]，直接后继就是a [ i + 1 ] a[i+1]a[i+1]。

接下来根据上述线性表的特点，先设计出线性表的抽象数据类型，也就是使用一个结构体将线性表中所有的信息进行综合。那么首先可以知道的是，有一个成员需要是最大元素数量，也就是数组的“最大容量”，这里定义为M A X _ _ S I Z E MAX_{\_\_}SIZEMAX__SIZE;除了最大容量之外，一个所必须的成员就是存放数据的一维数组，这里定义为d a t a datadata，使用指针类型，之后初始化的使用可以使用C CC语言中的m a l l o c mallocmalloc函数或C + + C++C++语言中的n e w newnew函数来进行空间申请;最后还需要一个记录当前一维数组中已经存放的数据的个数，也可以理解为现有数据的数目。故使用结构体来表示该线性表就是如下结构。

#include<iostream>
#include<stdio.h>
using namespace std;
typedef int EleType;	// 将元素类型定义为 EleType 
// 定义线性表
typedef struct Seq_List
{
	int MAX_SIZE;	//  线性表中最大元素个数
	EleType* data;	// 存放线性表中元素
	int size;	// 线性表中元素个数
	//Seq_List()	// 构造函数
	//{
	//	cout << "构造函数ing" << endl;
	//	MAX_SIZE = 20;	// 设置最大元素个数
	//	data = (int*)malloc(MAX_SIZE * sizeof(EleType));	// 开辟空间
	//	size = 0;
	//}
}SeqList;

上述代码中被注释的构造函数部分，主要是用于C + + C++C++中的n e w newnew关键字，使用n e w newnew关键字时，创建结构体实例时会主动调用该无参构造函数，但是使用C CC语言的m a l l o c mallocmalloc函数来创建结构体实例时，并不会调用该函数，只是向内存申请对应大小的空间而已，其他的任何操作都没有。

初始化

​由于我们接下来还是主要使用C CC语言作为我们的实现语言，所以暂时不考虑前面的默认初始化，同时即使使用了C + + C++C++语言作为我们的实现语言，在使用无参构造时也只是开辟了空间，并没有对数组赋初值(这里指需要赋初值的情况)。一般情况下程序中会在开始时对该线性表进行一次初始化赋值，也就是一次性往线性表中添加很多元素作为起始数据。

​那么接下来就以C CC语言的实现为例来进行代码分析，首先函数参数中，需要一个结构体实例地址，不能是结构体实例，因为作为参数时会自动生成一个临时变量，为了让主函数中的实例同步修改，故需要使用指针(C + + C++C++中的引用也可以)。之后第二个参数就是初始化数据的个数，第三个参数就是保存初始化数据的数组。

​在具体实现时，首先对该实例进行初始化，即起那么的最大元素个数，当前元素个数(0)，同时为一维数组开辟空间，使用m a l l o c mallocmalloc函数。之后就是对于特殊情况进行判断，首先是初始化的数据个数是否超出了线性表本身能容纳的最大元素个数，且需要确保前面的m a l l o c mallocmalloc函数成功申请到了空间。在确保这些之后，便可以进行初始化，过程十分简单，for循环遍历即可，最后更新当前元素个数。

// 初始化线性表
int	init_list(SeqList *list, int n, int num[])
{
	// TODO: 初始化结构体实例的所有元素并将初始数据装入
	list->MAX_SIZE = 20;	// 设置最大元素个数
	list->data = (EleType*)malloc(list->MAX_SIZE * sizeof(EleType));	// 开辟空间
	list->size = 0;
	if (n > list->MAX_SIZE)	// 超出最大长度则报错
		return -1;
	if (list->data == NULL)	// 判断空间是否成功申请
		return -1;
	for (int i = 0; i < n; i++)	// 赋值
		list->data[i] = num[i];		
	list->size = n;	// 当前元素个数
	// cout << list->size << endl;
	return 1;
}

插入

​在实现线性表的插入的时候，其实就是实现数组的元素插入。这里需要注意的是，数组的下标是从0开始的，但是一般我们将的插入到数组中的位置都是从1开始的，这一点需要注意。

​其实插入到线性表一共分为三种情况：

插入到头部

插入到中间

插入到尾部

在上面的三种插入情况可以看出，插入的位置只能从1到线性表的长度s i z e + 1 size+1size+1的位置。看起来是三种情况，其实这三种情况都可以当作一种情况来进行考虑。

​在具体插入时，一般的插入方法都是，将插入位置之后的元素全部后移一位。这里简单举一个例子，初始的线性表内容如下所示。

之后我们需要将元素6插入到位置2中，所以需要将位置2之后的元素全部后移一位，移动的时候从最后一个元素开始移动，使得后一个数据等于当前数据，也就是d a t a [ i + 1 ] = d a t a [ i ] data[i+1] = data[i]data[i+1]=data[i]，一直到需要移动的位置2即可。之后将要插入的元素填入对应的位置即可，整个过程如下所示。

如上图所示，再插入之后就可以得到对应的插入后的序列。在具体到代码实现的过程中，主体部分按照上述思路进行编写，但除了这些算法部分还需要进行特殊情况的判断，例如该线性表是否能继续增加元素，以及要插入的位置是否满足上述三种情况。

// 插入元素, 默认线性表中元素下标从1开始，在数组中元素下标从0开始
int insert_element(SeqList *list, int index, EleType element)
{
	if (list->size + 1 >= list->MAX_SIZE)	// 判断是否超出线性表的容量
		return -1;
	// 1 2 3 4 5 
	if (index <= 0 || index > list->size + 1)	// 判断下标是否合法
		return -1;
	for (int i = list->size; i >= index - 1; i--)	// 全部后移一位
	{
		list->data[i + 1] = list->data[i];
	}
	//cout << list->data[index - 1] << endl;
	list->data[index - 1] = element;	// 插入对应位置
	list->size++;
	return 1;
}

删除

​在实现线性表的删除的时候，其实也就是实现数据中某个位置的元素的删除。但是实际情况下会分为两种情况，第一种是根据索引删除，也就是根据位置删除;第二种是根据对应的值进行删除，也可以里立即为删除对应元素。其实第二种可以转化为第一种，故这里先重点分析第一种删除方法。

​在根据位置删除某个元素时，其实采用的方法和前面插入所采用的方法几乎一致，都是利用数组平移的操作。只不过对于删除操作来说，使用的是前移，可以理解为将那个位置上的元素覆盖掉，而前面插入的后移则可以理解为腾出一个位置来放新插入的元素。有了这样的一个想法就可以实现元素的删除。

​首先定位到该位置，然后将该位置上的值修改上后面一个元素的值，该位置后面元素的值都以此类推，这样一来就做到了删除元素的操作。当然可能会有疑问，这样的话最后一个元素岂不是和倒数第二个元素相同?确实如此，但是此时之前的最后一个元素已经不在我们的线性表的有效数据范围内了，所以之前的最后一个元素被划分到了空闲空间。前面的例子中删除位置2上面的元素的值的操作如下图所示。

​ 如上图所示，删除前有效空间为后面5个，删除后有效空间为后面6个。

// 根据索引删除元素, 索引从 1 开始, 即 1 <= index <= list->size
int delete_by_index(SeqList *list, int index)
{
	if (index <= 0 || index > list->size)	// 判断不合法的情况
		return -1;
	for (int i = index - 1; i < list->size; i++)	// 全部前移一位
		list->data[i] = list->data[i + 1];	
	list->size--;	// 表长减一
	return 1;
}

上述即为根据索引删除元素值的代码，在根据元素值删除元素时，其实只需要先遍历该数组，获取该元素的对应位置即可。其中获取位置的代码如下所示。

// 查找，返回索引，从 1 开始
int find_index(SeqList *list, EleType element)
{
	// TODO: 根据值来查找下标	
	for (int i = 0; i < list->size; i++)	// 遍历查找
	{
		if (element == list->data[i])	// 遇到相同的则返回下标
			return i + 1;
	}
	return -1;
}

​在有了上面的查找元素索引的函数后，接下来只需要先计算索引，再删除即可。

// 根据元素的值删除元素
int delete_by_element(SeqList *list, EleType element)
{
	int index = find_index(list, element);	// 找到下标
	return delete_by_index(list, index);	// 根据索引删除
}

查找

​最后实现以下查找，其实也就是根据索引返回对应索引的值，这里由于使用的是线性表，也就是一维数组，所以直接使用数组下标即可。

​但是其实这里存在一个比较棘手的问题，也就是如果改下标不合法，应该如何提示主程序该元素获取失败，简单举个例子，如果返回值为-1代表索引越界，那么如果当该索引对应的元素值即为-1的时候，返回值也是-1，但是此时却代表正确查找。

// 根据下标获取元素的值,这里的下标从 1 开始
EleType get_element(SeqList *list, int index)
{
	if (index <= 0 || index > list->size)	// 不合法的情况
	{
		cout << "get_element index error!!!" << endl;
		return -1;
	}
	return list->data[index - 1];	// 正常返回
}