線性表的基本操作有哪些？動力節(jié)點小編來告訴大家。

線性表

?線性表總的來說其實就是一個簡單的一維數(shù)組，那么從這里就可以看出線性表的特點—有限，因為數(shù)組在定義的時候就需要聲明數(shù)組的空間大小，或者說是可以保存到數(shù)據(jù)元素的個數(shù)。同時根據(jù)數(shù)組的特點，線性表中每個元素，除了頭和尾，都有一個直接前驅(qū)和直接后繼，例如對于元素a [ i ] a[i]a[i]，它的直接前驅(qū)就是a [ i − 1 ] a[i-1]a[i−1]，直接后繼就是a [ i + 1 ] a[i+1]a[i+1]。

接下來根據(jù)上述線性表的特點，先設(shè)計出線性表的抽象數(shù)據(jù)類型，也就是使用一個結(jié)構(gòu)體將線性表中所有的信息進行綜合。那么首先可以知道的是，有一個成員需要是最大元素數(shù)量，也就是數(shù)組的“最大容量”，這里定義為M A X _ _ S I Z E MAX_{\_\_}SIZEMAX__SIZE;除了最大容量之外，一個所必須的成員就是存放數(shù)據(jù)的一維數(shù)組，這里定義為d a t a datadata，使用指針類型，之后初始化的使用可以使用C CC語言中的m a l l o c mallocmalloc函數(shù)或C + + C++C++語言中的n e w newnew函數(shù)來進行空間申請;最后還需要一個記錄當(dāng)前一維數(shù)組中已經(jīng)存放的數(shù)據(jù)的個數(shù)，也可以理解為現(xiàn)有數(shù)據(jù)的數(shù)目。故使用結(jié)構(gòu)體來表示該線性表就是如下結(jié)構(gòu)。

#include<iostream>
#include<stdio.h>
using namespace std;
typedef int EleType;	// 將元素類型定義為 EleType 
// 定義線性表
typedef struct Seq_List
{
	int MAX_SIZE;	//  線性表中最大元素個數(shù)
	EleType* data;	// 存放線性表中元素
	int size;	// 線性表中元素個數(shù)
	//Seq_List()	// 構(gòu)造函數(shù)
	//{
	//	cout << "構(gòu)造函數(shù)ing" << endl;
	//	MAX_SIZE = 20;	// 設(shè)置最大元素個數(shù)
	//	data = (int*)malloc(MAX_SIZE * sizeof(EleType));	// 開辟空間
	//	size = 0;
	//}
}SeqList;

上述代碼中被注釋的構(gòu)造函數(shù)部分，主要是用于C + + C++C++中的n e w newnew關(guān)鍵字，使用n e w newnew關(guān)鍵字時，創(chuàng)建結(jié)構(gòu)體實例時會主動調(diào)用該無參構(gòu)造函數(shù)，但是使用C CC語言的m a l l o c mallocmalloc函數(shù)來創(chuàng)建結(jié)構(gòu)體實例時，并不會調(diào)用該函數(shù)，只是向內(nèi)存申請對應(yīng)大小的空間而已，其他的任何操作都沒有。

初始化

?由于我們接下來還是主要使用C CC語言作為我們的實現(xiàn)語言，所以暫時不考慮前面的默認初始化，同時即使使用了C + + C++C++語言作為我們的實現(xiàn)語言，在使用無參構(gòu)造時也只是開辟了空間，并沒有對數(shù)組賦初值(這里指需要賦初值的情況)。一般情況下程序中會在開始時對該線性表進行一次初始化賦值，也就是一次性往線性表中添加很多元素作為起始數(shù)據(jù)。

?那么接下來就以C CC語言的實現(xiàn)為例來進行代碼分析，首先函數(shù)參數(shù)中，需要一個結(jié)構(gòu)體實例地址，不能是結(jié)構(gòu)體實例，因為作為參數(shù)時會自動生成一個臨時變量，為了讓主函數(shù)中的實例同步修改，故需要使用指針(C + + C++C++中的引用也可以)。之后第二個參數(shù)就是初始化數(shù)據(jù)的個數(shù)，第三個參數(shù)就是保存初始化數(shù)據(jù)的數(shù)組。

?在具體實現(xiàn)時，首先對該實例進行初始化，即起那么的最大元素個數(shù)，當(dāng)前元素個數(shù)(0)，同時為一維數(shù)組開辟空間，使用m a l l o c mallocmalloc函數(shù)。之后就是對于特殊情況進行判斷，首先是初始化的數(shù)據(jù)個數(shù)是否超出了線性表本身能容納的最大元素個數(shù)，且需要確保前面的m a l l o c mallocmalloc函數(shù)成功申請到了空間。在確保這些之后，便可以進行初始化，過程十分簡單，for循環(huán)遍歷即可，最后更新當(dāng)前元素個數(shù)。

// 初始化線性表
int	init_list(SeqList *list, int n, int num[])
{
	// TODO: 初始化結(jié)構(gòu)體實例的所有元素并將初始數(shù)據(jù)裝入
	list->MAX_SIZE = 20;	// 設(shè)置最大元素個數(shù)
	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;	// 當(dāng)前元素個數(shù)
	// cout << list->size << endl;
	return 1;
}

插入

?在實現(xiàn)線性表的插入的時候，其實就是實現(xiàn)數(shù)組的元素插入。這里需要注意的是，數(shù)組的下標(biāo)是從0開始的，但是一般我們將的插入到數(shù)組中的位置都是從1開始的，這一點需要注意。

?其實插入到線性表一共分為三種情況：

插入到頭部

插入到中間

插入到尾部

在上面的三種插入情況可以看出，插入的位置只能從1到線性表的長度s i z e + 1 size+1size+1的位置。看起來是三種情況，其實這三種情況都可以當(dāng)作一種情況來進行考慮。

?在具體插入時，一般的插入方法都是，將插入位置之后的元素全部后移一位。這里簡單舉一個例子，初始的線性表內(nèi)容如下所示。

之后我們需要將元素6插入到位置2中，所以需要將位置2之后的元素全部后移一位，移動的時候從最后一個元素開始移動，使得后一個數(shù)據(jù)等于當(dāng)前數(shù)據(jù)，也就是d a t a [ i + 1 ] = d a t a [ i ] data[i+1] = data[i]data[i+1]=data[i]，一直到需要移動的位置2即可。之后將要插入的元素填入對應(yīng)的位置即可，整個過程如下所示。

如上圖所示，再插入之后就可以得到對應(yīng)的插入后的序列。在具體到代碼實現(xiàn)的過程中，主體部分按照上述思路進行編寫，但除了這些算法部分還需要進行特殊情況的判斷，例如該線性表是否能繼續(xù)增加元素，以及要插入的位置是否滿足上述三種情況。

// 插入元素, 默認線性表中元素下標(biāo)從1開始，在數(shù)組中元素下標(biāo)從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)	// 判斷下標(biāo)是否合法
		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;	// 插入對應(yīng)位置
	list->size++;
	return 1;
}

刪除

?在實現(xiàn)線性表的刪除的時候，其實也就是實現(xiàn)數(shù)據(jù)中某個位置的元素的刪除。但是實際情況下會分為兩種情況，第一種是根據(jù)索引刪除，也就是根據(jù)位置刪除;第二種是根據(jù)對應(yīng)的值進行刪除，也可以里立即為刪除對應(yīng)元素。其實第二種可以轉(zhuǎn)化為第一種，故這里先重點分析第一種刪除方法。

?在根據(jù)位置刪除某個元素時，其實采用的方法和前面插入所采用的方法幾乎一致，都是利用數(shù)組平移的操作。只不過對于刪除操作來說，使用的是前移，可以理解為將那個位置上的元素覆蓋掉，而前面插入的后移則可以理解為騰出一個位置來放新插入的元素。有了這樣的一個想法就可以實現(xiàn)元素的刪除。

?首先定位到該位置，然后將該位置上的值修改上后面一個元素的值，該位置后面元素的值都以此類推，這樣一來就做到了刪除元素的操作。當(dāng)然可能會有疑問，這樣的話最后一個元素豈不是和倒數(shù)第二個元素相同?確實如此，但是此時之前的最后一個元素已經(jīng)不在我們的線性表的有效數(shù)據(jù)范圍內(nèi)了，所以之前的最后一個元素被劃分到了空閑空間。前面的例子中刪除位置2上面的元素的值的操作如下圖所示。

? 如上圖所示，刪除前有效空間為后面5個，刪除后有效空間為后面6個。

// 根據(jù)索引刪除元素, 索引從 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;
}

上述即為根據(jù)索引刪除元素值的代碼，在根據(jù)元素值刪除元素時，其實只需要先遍歷該數(shù)組，獲取該元素的對應(yīng)位置即可。其中獲取位置的代碼如下所示。

// 查找，返回索引，從 1 開始
int find_index(SeqList *list, EleType element)
{
	// TODO: 根據(jù)值來查找下標(biāo)	
	for (int i = 0; i < list->size; i++)	// 遍歷查找
	{
		if (element == list->data[i])	// 遇到相同的則返回下標(biāo)
			return i + 1;
	}
	return -1;
}

?在有了上面的查找元素索引的函數(shù)后，接下來只需要先計算索引，再刪除即可。

// 根據(jù)元素的值刪除元素
int delete_by_element(SeqList *list, EleType element)
{
	int index = find_index(list, element);	// 找到下標(biāo)
	return delete_by_index(list, index);	// 根據(jù)索引刪除
}

查找

?最后實現(xiàn)以下查找，其實也就是根據(jù)索引返回對應(yīng)索引的值，這里由于使用的是線性表，也就是一維數(shù)組，所以直接使用數(shù)組下標(biāo)即可。

?但是其實這里存在一個比較棘手的問題，也就是如果改下標(biāo)不合法，應(yīng)該如何提示主程序該元素獲取失敗，簡單舉個例子，如果返回值為-1代表索引越界，那么如果當(dāng)該索引對應(yīng)的元素值即為-1的時候，返回值也是-1，但是此時卻代表正確查找。

// 根據(jù)下標(biāo)獲取元素的值,這里的下標(biāo)從 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];	// 正常返回
}