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

線性表

?線性表總的來說其實就是一個簡單的一維數組，那么從這里就可以看出線性表的特點—有限，因為數組在定義的時候就需要聲明數組的空間大小，或者說是可以保存到數據元素的個數。同時根據數組的特點，線性表中每個元素，除了頭和尾，都有一個直接前驅和直接后繼，例如對于元素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函數來進行空間申請;最后還需要一個記錄當前一維數組中已經存放的數據的個數，也可以理解為現(xiàn)有數據的數目。故使用結構體來表示該線性表就是如下結構。

#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關鍵字時，創(chuàng)建結構體實例時會主動調用該無參構造函數，但是使用C CC語言的m a l l o c mallocmalloc函數來創(chuàng)建結構體實例時，并不會調用該函數，只是向內存申請對應大小的空間而已，其他的任何操作都沒有。

初始化

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

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

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

// 初始化線性表
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;
}

插入

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

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

插入到頭部

插入到中間

插入到尾部

在上面的三種插入情況可以看出，插入的位置只能從1到線性表的長度s i z e + 1 size+1size+1的位置?？雌饋硎侨N情況，其實這三種情況都可以當作一種情況來進行考慮。

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

之后我們需要將元素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即可。之后將要插入的元素填入對應的位置即可，整個過程如下所示。

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

// 插入元素, 默認線性表中元素下標從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;
}

刪除

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

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

?首先定位到該位置，然后將該位置上的值修改上后面一個元素的值，該位置后面元素的值都以此類推，這樣一來就做到了刪除元素的操作。當然可能會有疑問，這樣的話最后一個元素豈不是和倒數第二個元素相同?確實如此，但是此時之前的最后一個元素已經不在我們的線性表的有效數據范圍內了，所以之前的最后一個元素被劃分到了空閑空間。前面的例子中刪除位置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);	// 根據索引刪除
}

查找

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

?但是其實這里存在一個比較棘手的問題，也就是如果改下標不合法，應該如何提示主程序該元素獲取失敗，簡單舉個例子，如果返回值為-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];	// 正常返回
}