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

線性表

?線性表總的來說其實(shí)就是一個(gè)簡單的一維數(shù)組，那么從這里就可以看出線性表的特點(diǎn)—有限，因?yàn)閿?shù)組在定義的時(shí)候就需要聲明數(shù)組的空間大小，或者說是可以保存到數(shù)據(jù)元素的個(gè)數(shù)。同時(shí)根據(jù)數(shù)組的特點(diǎn)，線性表中每個(gè)元素，除了頭和尾，都有一個(gè)直接前驅(qū)和直接后繼，例如對(duì)于元素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ù)上述線性表的特點(diǎn)，先設(shè)計(jì)出線性表的抽象數(shù)據(jù)類型，也就是使用一個(gè)結(jié)構(gòu)體將線性表中所有的信息進(jìn)行綜合。那么首先可以知道的是，有一個(gè)成員需要是最大元素?cái)?shù)量，也就是數(shù)組的“最大容量”，這里定義為M A X _ _ S I Z E MAX_{\_\_}SIZEMAX__SIZE;除了最大容量之外，一個(gè)所必須的成員就是存放數(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ù)來進(jìn)行空間申請(qǐng);最后還需要一個(gè)記錄當(dāng)前一維數(shù)組中已經(jīng)存放的數(shù)據(jù)的個(gè)數(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;	//  線性表中最大元素個(gè)數(shù)
	EleType* data;	// 存放線性表中元素
	int size;	// 線性表中元素個(gè)數(shù)
	//Seq_List()	// 構(gòu)造函數(shù)
	//{
	//	cout << "構(gòu)造函數(shù)ing" << endl;
	//	MAX_SIZE = 20;	// 設(shè)置最大元素個(gè)數(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)鍵字時(shí)，創(chuàng)建結(jié)構(gòu)體實(shí)例時(shí)會(huì)主動(dòng)調(diào)用該無參構(gòu)造函數(shù)，但是使用C CC語言的m a l l o c mallocmalloc函數(shù)來創(chuàng)建結(jié)構(gòu)體實(shí)例時(shí)，并不會(huì)調(diào)用該函數(shù)，只是向內(nèi)存申請(qǐng)對(duì)應(yīng)大小的空間而已，其他的任何操作都沒有。

初始化

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

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

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

// 初始化線性表
int	init_list(SeqList *list, int n, int num[])
{
	// TODO: 初始化結(jié)構(gòu)體實(shí)例的所有元素并將初始數(shù)據(jù)裝入
	list->MAX_SIZE = 20;	// 設(shè)置最大元素個(gè)數(shù)
	list->data = (EleType*)malloc(list->MAX_SIZE * sizeof(EleType));	// 開辟空間
	list->size = 0;
	if (n > list->MAX_SIZE)	// 超出最大長度則報(bào)錯(cuò)
		return -1;
	if (list->data == NULL)	// 判斷空間是否成功申請(qǐng)
		return -1;
	for (int i = 0; i < n; i++)	// 賦值
		list->data[i] = num[i];		
	list->size = n;	// 當(dāng)前元素個(gè)數(shù)
	// cout << list->size << endl;
	return 1;
}

插入

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

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

插入到頭部

插入到中間

插入到尾部

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

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

之后我們需要將元素6插入到位置2中，所以需要將位置2之后的元素全部后移一位，移動(dòng)的時(shí)候從最后一個(gè)元素開始移動(dòng)，使得后一個(gè)數(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]，一直到需要移動(dòng)的位置2即可。之后將要插入的元素填入對(duì)應(yīng)的位置即可，整個(gè)過程如下所示。

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

// 插入元素, 默認(rèn)線性表中元素下標(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;	// 插入對(duì)應(yīng)位置
	list->size++;
	return 1;
}

刪除

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

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

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

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

// 根據(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í)，其實(shí)只需要先遍歷該數(shù)組，獲取該元素的對(duì)應(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ì)算索引，再刪除即可。

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

查找

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

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

// 根據(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];	// 正常返回
}