1 線性表

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列、字符串…

線性表在邏輯上是線性結(jié)構(gòu)，也就是說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

2 順序表

那么今天我們首先來(lái)學(xué)習(xí)順序表，然后再學(xué)習(xí)鏈表，有一個(gè)循序漸進(jìn)的效果

2.1 概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：

1. 靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。
   
   這種順序表空間固定，那么存儲(chǔ)到一定數(shù)量時(shí)就不能存儲(chǔ)，不太方便

2. 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)
   
   動(dòng)態(tài)開(kāi)辟就很好解決了空間不夠的問(wèn)題。

2.2 接口實(shí)現(xiàn)

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。
靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了，空間開(kāi)多了浪費(fèi)，開(kāi)少了不夠用。
所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表，根據(jù)需要動(dòng)態(tài)的分配空間大小，所以下面我們實(shí)現(xiàn)動(dòng)態(tài)順序表。

//那么我們先來(lái)實(shí)現(xiàn)接口函數(shù)#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int SLDataType;
#define INIT_CAPACITY 4typedef struct SeqList//順序表的創(chuàng)建
{SLDataType* s;//作為動(dòng)態(tài)數(shù)組來(lái)初始化int size;//元素個(gè)數(shù)應(yīng)該為正數(shù)int capacity;//初始容量大小
}SL;
//寫接口函數(shù)時(shí)，要想我們對(duì)順序表有什么操作？void SLInit(SL* ps);//順序表的初始化
void SLDestroy(SL* ps);//順序表的銷毀
void SLPrint(SL* ps);//打印順序表
void SLCheckCapacity(SL* ps);//檢查容量是否充足
void SLPushBack(SL* ps, SLDataType x);//在尾部插入數(shù)據(jù)
void SLPopBack(SL* ps);//在尾部刪除數(shù)據(jù)
void SLPushFront(SL* ps, SLDataType x);//在首部插入數(shù)據(jù)
void SLPopFront(SL* ps);//在首部刪除數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x);//在中間插入某個(gè)數(shù)據(jù)
void SLErase(SL* ps, int pos);//刪除中間某個(gè)數(shù)據(jù)
int SLSearch(SL* ps, SLDataType x);//尋找某個(gè)元素并且返回下標(biāo)

寫完接口函數(shù)時(shí)，就要實(shí)現(xiàn)函數(shù)了
注意：在寫代碼時(shí)，最好寫完一個(gè)接口函數(shù)就要進(jìn)行調(diào)試，這樣找錯(cuò)誤就很方便。

//首先是對(duì)順序表的初始化
void SLInit(SL* ps)
{assert(ps);//進(jìn)行斷言，ps指向的對(duì)象不為空ps->s = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//malloc開(kāi)辟空間時(shí)，后面要考慮開(kāi)辟失敗的情況，要進(jìn)行檢查if (ps->s == NULL){perror("malloc fail");return;}ps->size = 0;//初始化沒(méi)有元素ps->capacity = INIT_CAPACITY;//進(jìn)行初始化
}

//打印順序表
void SLPrint(SL* ps)
{assert(ps);//如果是空的順序表就不能打印int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->s[i]);}printf("\n");//打印完換行
}

//進(jìn)行容量檢查
void SLCheckCapacity(SL* ps)
{assert(ps);//判斷為不為空順序表if (ps->size == ps->capacity)//在進(jìn)行尾部插入數(shù)據(jù)時(shí)要先判斷空間夠不夠，不夠要進(jìn)行擴(kuò)容{SLDataType* ptr =(SLDataType*)realloc(ps->s, sizeof(SLDataType) * ps->capacity * 2);//這里使用新的指針是因?yàn)槿绻_(kāi)辟失敗返回空指針，就不會(huì)影響到原來(lái)開(kāi)辟的內(nèi)存空間if (ptr == NULL){perror("realloc fail");return;}ps->s = ptr;//開(kāi)辟成功將新開(kāi)辟空間的指針賦給原來(lái)的指針ps->capacity *= 2;//因?yàn)榭臻g擴(kuò)大了兩倍，那么容量也要擴(kuò)大兩倍}
}

//進(jìn)行尾部插入數(shù)據(jù)
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//斷言可以找到問(wèn)題SLCheckCapacity(ps);//尾部插入要判斷最后一個(gè)元素有沒(méi)有空間，沒(méi)有則開(kāi)辟ps->s[ps->size] = x;//將數(shù)據(jù)賦給最后一個(gè)元素ps->size++;//同時(shí)將元素個(gè)數(shù)加一//SLInsert(ps, ps->size, x);//這個(gè)函數(shù)先不用管，后面會(huì)講
}

//進(jìn)行頭部插入數(shù)據(jù)
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判斷為不為空SLCheckCapacity(ps);//判斷容量夠不夠for (int i = ps->size - 1; i >= 0; i--){ps->s[i + 1] = ps->s[i];//將所有的數(shù)往后移一位}ps->size++;//元素要加一ps->s[0] = x;//進(jìn)行賦值//SLInsert(ps, 0, x);//后面會(huì)講
}

//進(jìn)行尾部刪除
void SLPopBack(SL* ps)
{assert(ps);//判斷不為空assert(ps->size > 0);//判斷順序表中有沒(méi)有元素ps->size--;//直接刪除一個(gè)元素
}

//進(jìn)行頭部刪除
void SLPopFront(SL* ps)
{assert(ps);//判讀為不為空assert(ps->size > 0);//當(dāng)這個(gè)數(shù)組是空的，size就為負(fù)數(shù)了//那么頭部刪除就可以進(jìn)行覆蓋，可以用memmove函數(shù)；也可以進(jìn)行一個(gè)一個(gè)覆蓋int begin = 0;for (begin = 1; begin <= ps->size - 1; begin++){ps->s[begin - 1] = ps->s[begin];//后一個(gè)將前一個(gè)進(jìn)行覆蓋}ps->size--;//讓元素減一
}

//進(jìn)行插入數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x)//這個(gè)插入包括了頭插和尾插，所以可以進(jìn)行復(fù)用
{assert(ps);//判斷為不為空assert(pos >= 0 && pos <= ps->size);//判斷指定下標(biāo)要合法，等于0就是要頭插，等于ps->size就是要尾插SLCheckCapacity(ps);//檢查容量是否充足int end = ps->size - 1;while (end >= pos){ps->s[end + 1] = ps->s[end];end--;//往后一個(gè)一個(gè)賦值}ps->s[pos] = x;//最后在pos位置賦值為xps->size++;//元素個(gè)數(shù)加一
}

//進(jìn)行刪除元素
void SLErase(SL* ps, int pos)
{assert(ps);//判斷為不為空assert(pos >= 0 && pos < ps->size);//判斷位置要合法int begin = pos + 1;while (begin < ps->size){ps->s[begin - 1] = ps->s[begin];++begin;//一個(gè)一個(gè)往前覆蓋}ps->size--;//元素要減一
}

//進(jìn)行元素的查找，找到了則返回下標(biāo)，沒(méi)找到則返回-1
int SLSearch(SL* ps, SLDataType x)//返回元素下標(biāo)，要有返回值
{assert(ps);//判斷為不為空for (int i = 0; i < ps->size; i++){if (ps->s[i] == x)return i;//進(jìn)行循環(huán)查找，找到了就返回下標(biāo)}return -1;//循環(huán)結(jié)束代表沒(méi)找到，返回-1表示沒(méi)找到
}

//最后進(jìn)行順序的銷毀
void SLDestroy(SL* ps)//銷毀順序表時(shí)，要釋放內(nèi)存，并且將指針設(shè)為空
{assert(ps);//判斷為不為空free(ps->s);//釋放指針?biāo)赶虻膬?nèi)存空間ps->s = NULL;//同時(shí)將指針置為空ps->size = ps->capacity = 0;//元素和容量置為0
}

注意：在進(jìn)行傳參數(shù)時(shí)，如果要改變所指向的內(nèi)容，就要傳地址過(guò)去，不要傳值過(guò)去，切記！！！

2.3 數(shù)組相關(guān)面試題

順序表的內(nèi)容完成后，那么接下來(lái)就要寫寫題目來(lái)鞏固能力了

1. 原地移除數(shù)組中所有的元素val，要求時(shí)間復(fù)雜度為O(N),空間復(fù)雜度O(1)。
   https://leetcode.cn/problems/remove-element/

//首先我們可以將元素覆蓋的方式去寫。
int removeElement(int* nums, int numsSize, int val) {int src = 0;//作為遍歷數(shù)組的元素int dst = 0;//作為返回?cái)?shù)組的新長(zhǎng)度while (src < numsSize){if (nums[src] != val){nums[dst++] = nums[src];//如果不等于元素不相等，那么將dst加一，src也加一}src++;//如果相等，只有src加一，dst不加一，等下個(gè)元素進(jìn)行覆蓋}return dst;//最后返回?cái)?shù)組的新長(zhǎng)度
}//也可以這樣寫
int removeElement(int* nums, int numsSize, int val) {int src = 0;int dst = 0;while (src < numsSize){if (nums[src] != val){nums[dst++] = nums[src++];//上面的方式更加簡(jiǎn)潔，因?yàn)閟rc哪種情況都要加一}else{src++;}}return dst;
}
//![動(dòng)圖描述](https://img-blog.csdnimg.cn/8c7e4339443448fc9930d677b4f59539.gif#pic_center)

2. 刪除排序數(shù)組中的重復(fù)項(xiàng)。
   https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

//這道題目和上一個(gè)思路差不多，每個(gè)數(shù)字之只能出現(xiàn)一次，返回?cái)?shù)組的新長(zhǎng)度
//我們使用快慢指針
int removeDuplicates(int* nums, int numsSize){int src = 1;//讓src為1int dst = 0;while (src < numsSize){if (nums[dst] == nums[src]){src++;//兩個(gè)數(shù)相等就src加1}else{nums[++dst] = nums[src++];//不相等就進(jìn)行賦值}}return dst + 1;//最后返回dst+1
}//結(jié)合圖片進(jìn)行理解
//![動(dòng)態(tài)理解](https://img-blog.csdnimg.cn/0d82014700df493184df034d7e3de84d.gif#pic_center)

3. 合并兩個(gè)有序數(shù)組
   https://leetcode.cn/problems/merge-sorted-array/

//這里的非遞減是可能遞增也可能相等
//這里我們可以從頭一個(gè)一個(gè)比較，小的放前面，大的放后面，但這樣比較實(shí)在麻煩。換個(gè)角度，如果從后面開(kāi)始放就會(huì)方便很多。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m - 1;//作為最后一個(gè)元素比較int end2 = n - 1;int dst = m + n - 1;while (end1 >= 0 && end2 >= 0){if (nums2[end2] > nums1[end1]){nums1[dst--] = nums2[end2--];//如果大，那么num2放元素}else{nums1[dst--] = nums1[end1--];//如果小，那么num1放元素}}while (end2 >= 0)//這里判斷end2，如果還有元素，依次放上去//不判斷end1的原因是num1的元素就在num1中，不用進(jìn)行移植{nums1[dst--] = nums2[end2--];}
}
//結(jié)合動(dòng)態(tài)理解!(https://img-blog.csdnimg.cn/7a9667b48f7d40e48155cfb77ec0dd45.gif#pic_center)

以上題目希望可以加深和理解順序表

2.4 順序表的問(wèn)題與思考

問(wèn)題：

1. 中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(n)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)谠倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。

如何解決以上問(wèn)題呢？那就要使用鏈表了！！！

這次我們學(xué)習(xí)了順序表，下次學(xué)習(xí)鏈表，希望各位學(xué)習(xí)永無(wú)止境！！！o_O

晚風(fēng)庭院落梅初。淡云來(lái)往越疏疏。–李清照