一、什么是線性表？

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

二、什么是順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，
順序表一般可以分為：
1.靜態順序表：就是存盤空間固定，如果空間被資料放滿了，此時就不能再插入資料了

2.動態順序表：存盤空間不固定，可以增容

三、順序表的實作

1.順序表的介面

代碼如下：

//順序表中存盤的資料型別為進行重命名
//為什么要重命名？
//因為如果以后想將存盤資料的內容改為char或者double等其他型別的話，只需在這里該一次就可以，在之前的堆疊和佇列我們已經說過了，下次就不說了---^_^
//而不必代碼中的每一處都改，減少了不必要的麻煩，提高了代碼的可讀性
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;//指向順序表的指標
	int capacity;//順序表的容量
	int size;//實際在順序表中已經存盤資料的個數
}SL;

//順序表的初始化
void SeqListInit(SL* ps);//
//檢查容量是否已滿
void SeqListCheckCapacity(SL* ps);//
//列印順序表中的資料
void SeqListPrint(SL* ps);//
//尾插
void SeqListPushBack(SL* ps, SQDataType x);//
//尾刪
void SeqListPopBack(SL* ps);//
//頭插
void SeqListPushFront(SL* ps, SQDataType x);
//頭刪
void SeqListPopFront(SL* ps);
//順序表的摧毀
void SeqListDestory(SL* ps);//
//隨機插入
void SeqListInsert(SL* ps, size_t pos, SQDataType x);
//隨機洗掉
void SeqListErase(SL* ps, size_t pos);
//在順便表中找出一次出現x的下標，如果沒有就回傳-1
int SeqListFind(SL* ps, SQDataType x);
//修改下標為pos的值
void SeqListModify(SL* ps, size_t pos, SQDataType x);

2.每個介面的實作

靜態順序表只適用于確定知道需要存多少資料的場景，靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用，所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實作動態順序表，
代碼如下：

//順序表的列印
void SeqListPrint(SL* ps)
{
	assert(ps && ps->a);//斷言ps是否合法(是否為NULL)并且斷言ps->a(指向順序表的指標)是否合法
	for (int i = 0; i < ps->size; i++)//從下標為0處開始列印資料，直到下標為size-1(最后一個資料)處為止
	{
		printf("%d ",ps->a[i]);
	}
	printf("\n");
}
//順序表的摧毀
void SeqListDestory(SL* ps)
{
    assert(ps && ps->a);
	free(ps->a);
	ps->a = NULL;//釋放后要將指標置NULL，防止被誤操作(對已經被釋放的空間操作)
	ps->capacity = ps->size = 0;//空間已經被釋放了，所以capacity和size也要置0
}
//順序表的初始化
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
//檢查容量是否已滿
void SeqListCheckCapacity(SL* ps)//下面的頭插，尾插等都需要調這個介面來檢查是否需要擴容
{
	assert(ps);
	if (ps->capacity == ps->size)//當capacity和size相等時需要擴容，此時有兩種情況
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;//當capacity為0時，表示此時是指標a指向的是NULL，直接給4個容量，
	    //當capacity不為0時，直接擴容原來的兩倍
		SQDataType* tmp = (SQDataType*)realloc(ps->a, NewCapacity*sizeof(SQDataType));//擴容
		//這里用一個型別為SQDataType*的指標接受realloc的回傳值，如果不這么做可能造成記憶體泄漏，因為如果擴容失敗，realloc將回傳NULL
		//類似于ps->a=NULL,這樣就會導致指標a也為NULL，原來a指向的空間就無法找到
		if (!tmp)//如果tmp為NULL，表示擴容失敗，給出提示資訊，例外終止程式->exit(-1)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;//成功的話就將tmp賦給a
			ps->capacity = NewCapacity;//容量也進行更新
		}
	}
}
//尾插
void SeqListPushBack(SL* ps,SQDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//先檢查容量是否滿了，滿了就進行擴容
	ps->a[ps->size++] = x;//因為前面已經檢查了capacity，所以直接插入資料
	//這里也等價于ps->a[ps->size] = x;
	//           ps->size++;
}
//尾刪
void SeqListPopBack(SL* ps)
{
	assert(ps && ps->a);
	assert(ps->size > 0);//斷言順序表中是否有資料，如果有才進行Pop，所有的Pop介面都需要這么做
	ps->size--;//不必擔心順序表里的資料，因為在下一次尾插或者頭插時，會將后面的資料覆寫
}
//頭插
void SeqListPushFront(SL* ps, SQDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;//end就表示最后一個元素的下標位置
	while (end >= 0)//因為是頭插，所以需要從前往后挪動資料,下面的頭刪，和隨機洗掉，隨機插入都需要挪動資料
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//資料挪動完成，第一個位置就相當于空，所以就可以用來存盤x
	ps->size++;
}
//頭刪
void SeqListPopFront(SL* ps)
{
	assert(ps && ps->a);
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)//這里依然是挪動資料，不過與前面不同的是，這里是從后往前挪動資料
	{
		ps->a[begin - 1] = ps->a[begin];//每次都將后一個資料挪到前一個位置
		begin++;
	}
	ps->size--;
}
//在順便表中找出一次出現x的下標，如果沒有就回傳-1
int SeqListFind(SL* ps, SQDataType x)
{
	assert(ps && ps->a);
	for (int i = 0; i < ps->size; i++)//從下標為0開始遍歷整個順序表
	{
		if (ps->a[i] == x)
		{
			return i;//如果找到了與x相等的數，就回傳這個數的下標，不過這里只能回傳第一個
			         //換句話說，如果順序表出現了多個與x相等的值，只回傳第一個與x相等的數的下標，因為我們是從下標為0開始找的
		}
	}
	return -1;//如果找不到，就回傳1，至于為什么回傳1，眾所周知，陣列的下標不可能為負數，也可以回傳其他負數，所以負數代表沒找到
}
//在pos的位置插入
void SeqListInsert(SL* ps, size_t pos, SQDataType x)//size_t pos表示想插入的下標位置
{
	assert(ps && ps->a);
	assert(pos >= 0 && pos <= ps->size);//這里與前面的有所不同，主要是需要判斷pos(下標位置)是否合法
	SeqListCheckCapacity(ps);
	size_t end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];//依舊是挪動資料，從前往后挪
		end--;
	}
	ps->a[pos] = x;//挪動完后，pos的位置相當于空，此時就用來存放x
	ps->size++;
}
//洗掉pos位置的值
void SeqListErase(SL* ps, size_t pos)
{
	assert(ps && ps->a);
	assert(pos >= 0 && pos < ps->size);//與前面的SeqListInsert是一樣的原因
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];//從后往前挪動資料
		begin++;
	}
	ps->size--;
}
//修改pos位置的值
void SeqListModify(SL* ps, size_t pos, SQDataType x)
{
	assert(ps && ps->a);
	assert(pos >= 0 && pos < ps->size);//修改資料也要判斷pos是否合法
	ps->a[pos] = x;//將位置為pos的資料修改為x
}

下面我們將用畫圖的方式來分析頭插、頭刪、尾插、尾刪等介面：

3.測驗程式

代碼如下：

void test()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 5);
	SeqListPrint(&s);

	SeqListInsert(&s, 2, 7);
	SeqListPrint(&s);

	SeqListErase(&s, 2);
	SeqListPrint(&s);

	SeqListDestory(&s);
}

int main()
{
	test();
	return 0;
}

總結

經過對順序表的實作，我們知道了各個介面的原理，同時發現順序表的頭插、頭刪、隨機插入，隨機洗掉相對于尾插和尾刪都十分麻煩，原因在于我們必須要挪動資料，而且需要十分小心的控制插入或洗掉的邊界，否則會導致插入的資料把原始資料覆寫等一系列問題，但對于鏈表，我們不需要這么麻煩，我們只需要改變指標的指向即可，對于鏈表的實作，我們下期再說，