有幸被富豪賞識，順序表怎能不會

聯動文章 五萬字超詳細Linux知識點

順序表

線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…

線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

但是今天這篇博客只講順序表

順序表（本質上就是陣列）

概念及結構

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

順序表一般可以分為：

1. 靜態順序表：使用定長陣列存盤元素，

#pragma once

//方便改陣列的大小
#define N 100

typedef int SLDataType; //這樣會很方便修改

//靜態順序表
typedef struct SeqList
{
	SLDataType a[N];
	SLDataType size;//表示陣列中存盤了多少個資料
}SL;

void SeqListPushBack(SL* ps, SLDataType x);

靜態的特點是滿了就不讓插入， 缺點就是我們不知道給多大的空間合適，給大了浪費，給小了“犯罪”，所以就出現了動態順序表

2. 動態順序表：使用動態開辟的陣列存盤，

既然都動態了，那么也就沒有空間大小N的必要了，我們用指標即可

//方便改陣列的大小
//#define N 100

typedef int SLDataType; //這樣會很方便修改

//動態順序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//表示陣列中存盤了多少個資料
	int capacity;//陣列實際能存資料的空間容量是多大
}SL;

void SeqListPushBack(SL* ps, SLDataType x);

介面函式（這里教你閉坑，不然有時候你不知道怎么死的（值傳遞與址傳遞的區別））

順序表初始化 SeqListInit

值傳遞

這里有一個告誡就是vs13與vs19不同，vs13你sl不初始化也可以跑過去，而vs19sl不初始化是跑不過去的，我把vs19跑不過去的圖放在下面

址傳遞

既然實參的是不能傳給形參，那么我們就把地址傳過去、

//順序表初始化
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

尾插函式SeqListPushBack

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		//壓根就沒有空間		 
		//空間滿的情況，擴容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("開辟失敗\n");//沒有開辟成功
			exit(-1);//例外結束
		}
		//成功擴容后
		ps->a = tmp;//把新的地址給他
		ps->capacity = newcapacity;//容量給他

	}
	//空間足夠的情況
	ps->a[ps->size] = x;
	ps->size++;
}

但是有時候一直除錯去看我們介面寫的怎么樣，會很浪費時間，所以我們得寫個列印函式

順序表列印函式SeqListPrint

//順序表列印
void seqListPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

我們做到這一步基本可以看成順序表起步成功，現在我們需要對順序表銷毀，實際上我們是知道，最后的最后才是順序表的銷毀，但是我們這里可以實作了（你可以可理解成單片機的最小系統或者丐版微星一個意思）

順序表銷毀函式SeqListDestory

//順序表銷毀
void seqListDestory(SL* ps)//就是釋放記憶體，防止記憶體溢位
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

最小系統板好了我們就一個一個加模塊

尾刪函式SeqListPopBack

溫柔

//尾刪
void SeqListPopBack(SL* ps)
{
	//溫柔做法
	if (ps->size > 0)
	{
		ps->size--;
	}
}

粗暴（我一個大男人比較喜歡粗暴一點的做法，直接了當）

//尾刪
void SeqListPopBack(SL* ps)
{
	溫柔做法
	//if (ps->size > 0)
	//{
	//	ps->size--;
	//}
	//粗暴
	assert(ps->size > 0);//斷言不為真直接報錯，管你不輕
	ps->size--;
}

在寫頭插之前，我們思考一下，你要插入，肯定要考慮到是否需要擴容，那么就與之前尾插里面的擴容重了，所以可以抽取出來單獨寫一個函式

順序表檢查容量函式SeqListCheckCapacity

//順序表檢查容量
void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//壓根就沒有空間		 
		//空間滿的情況，擴容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("開辟失敗\n");//沒有開辟成功
			exit(-1);//例外結束
		}
		//成功擴容后
		ps->a = tmp;//把新的地址給他
		ps->capacity = newcapacity;//容量給他
	}
}

然后用那個檢查容量就可以很輕松的擴容了

頭插函式SeqListPushFront

//頭插
void SeqListPushFront(SL* ps, SLDataType x)
{
	//檢查增容
	SeqListCheckCapacity(ps);
	//挪動資料
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

頭刪SeqListPopFront

//頭刪
void SeqListPopFront(SL* ps)
{
	assert(ps->size>0);
	int begin = 1;
	while (begin<ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

順序表查找函式SeqListFind

//順序表查找函式
int SeqListFind(SL* ps, SLDataType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

順序表插入函式SeqListInsert

//順序表插入函式
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	//斷言不在范圍內直接結束
	assert(pos>=0 && pos<=ps->size);
	//檢查擴容
	SeqListCheckCapacity(ps);
	//挪動資料
	int end = ps->size - 1;
	while (pos<=end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//然后再把資料給當前位置
	ps->a[pos] = x;
	ps->size++;
}

所以頭插尾插就不需要寫了，直接呼叫插入函式即可

順序表洗掉函式SeqListErase

//順序表洗掉函式
void SeqListErase(SL* ps, int pos)
{
	//斷言不在范圍內直接結束
	assert(pos >= 0 && pos < ps->size);
	//洗掉不需要考慮擴容,直接挪動資料 
	int begin = pos;
	while (begin+1<ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

所以頭刪尾刪也就可以 復用掉

練習題

例1移除元素

我們先分析一下題，他對空間復雜度是有要求的，對時間復雜度沒有什么要求

int removeElement(int* nums, int numsSize, int val){
    int i = 0;
    int* cur = nums;
    for(i = 0;i<numsSize;i++)
    {
        if(val ^ nums[i])
        {
           *cur++ = nums[i];            
        }
    }
    return cur-nums;
}

例2洗掉有序陣列中的重復項

我們不能空看我們得畫圖解決，題目直接把空間定死，不會給你開額外的陣列了，也就只能多指標解決

腦內模擬一番，一個定位指標，兩個游標指標，應該可以解決

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0)//空陣列跳出
    return 0;
    int* cur = nums;//定位指標
    int* head = nums;//游標頭指標
    int* tail = nums+1;//游標尾指標
    while(tail<nums+numsSize)
    {
        if(*head == *tail)
        {
            tail++;
        }
        else
        {
            *cur = *head;
            cur++;
            head = tail;
            tail++;
        }
    }
    *cur = *head;//最后一個不管等不等都強制賦值
    cur++;
    return (cur-nums);
}

例3合并兩個有序陣列

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* p1 = nums1+m-1;
    int* p2 = nums2+n-1;
    int* cur = nums1+m+n-1;
    while(p1>=nums1 && p2>=nums2)
    {
        *cur-- = *p1>*p2 ? *p1-- : *p2--;//三目運算子
    }
    while(p2>=nums2)
    {
        *cur-- = *p2--;
    }
}

聯動文章 五萬字超詳細Linux知識點