5分鐘帶你了解什么是順序表，并用它寫一個簡單的增刪查改(畫圖講解,詳細代碼)

順序表的概念及結構

順序表在資料結構中一種很重要的邏輯結構 ,它是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，也就是說，順序表本質是一個陣列，它的存盤的資料從左向右必須是連續的，
順序表的結構：

下面這種結構不是順序表，因為資料不是連續的,5和6中間空了一塊空間，

順序表可以分為：

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

順序表的靜態的存盤：

#define N 100
typedef int SLDataType;
typedef struct SeqList
{
 SLDataType array[N]; // 定長陣列，陣列的大小是固定的，所以是靜態儲存
  size_t size; // 有效資料的個數 
}SeqList;

動態順序表的存盤：

，

順序表的缺點

1.在頭部或中間插入資料需要挪動資料

2.動態增容有增容時有性能的消耗
3增容時一般是以2倍或1.5倍增長的,勢必會有一定的空間的浪費,例如,當前最大容量為100,滿了以后,增容到200,我在插入5個資料,后面就有95個空間浪費掉了.

增刪查改(動態)

增刪查改的意義

在寫代碼之前,我們先來聊一下寫這個增刪查改的意義.增刪查改的結構隨處可見,無論是我們的微信的通訊錄里,還是在學校的教務系統里,都需要有一個增刪查改去去添加聯系人(學生)的資訊,查找聯系人(學生)的資訊,所以學習增刪查改的基本結構的對我們的意義很大,當我們學會了增刪查改的基本邏輯以后,我們才能去延伸去寫通訊錄,去寫教務系統.或者看懂代碼.

動態順序表

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

初始化資料

先定義一個結構體

typedef struct SeqList
{
	int* s;
	int capacity;//該陣列的最大容量
	int sz;//該陣列當前存盤資料的個數
}SeqList;

void SeqListInit(SeqList* pc)
{
	pc->s = NULL;
	pc->capacity = 0;
	pc->sz = 0;
}

尾部增加一個資料

如果想在4后面插入一個5,此時的sz為4,只要再pc->s[pc->sz]插入一個5即可,因為5的位置為陣列下標為4
的位置.

當然,我們在插入資料之前,得檢查是否需要增容.
所以我們在定義一個增容的函式

void CheckCapacity(SeqList* pc)
{
	assert(pc);
	if (pc->capacity == pc->sz)//若sz等于最大容量,則需要增容
	{
		pc->capacity = pc->capacity == 0 ? 5 : pc->capacity * 2;
		pc->s = (int *)realloc(pc->s, sizeof(int) * pc->capacity);
		if (pc->s == NULL)
		{
			return;
		}
		printf("增容成功\n");
	}

 }

void SeqListPushBack(SeqList* pc,int x)
{
	assert(pc);//防止pc為NULL
	CheckCapacity(pc);//檢查是否需要增容
	pc->s[pc->sz] = x;
	pc->sz++;
}

頭部插入一個資料

我們如何把一個資料插入在順序表的首位置呢?
這就需要我們把資料全部往后移,然后空出首位置的,在把值插入到首位置

代碼如下:

void SeqListPushFront(SeqList* pc, int x)
{
	assert(pc);//防止pc為NULL
	CheckCapacity(pc);//檢查是否需要增容
	int i = pc->sz;
	while (i--)
	{
		pc->s[i + 1] = pc->s[i];
	}
	pc->s[0] = x;
	pc->sz++;

}

尾部洗掉一個資料

尾刪其實很簡單,只需要把有效資料減少一個就行,也就是把sz就可以,

參考如下代碼;

void SeqListPopFront(SeqList* pc)
{
	assert(pc);
	pc->s[pc->sz - 1] = 0;
	pc->sz--;

}

頭部洗掉一個元素

void SeqListPopFront(SeqList* pc)
{
	assert(pc);
	if (pc->sz == 0)//當sz=0,也就是說沒有有效資料,后面不用洗掉資料
	{
		return;
	}
	for (int i = 0; i < pc->sz - 1; i++)
	{
		pc->s[i] = pc->s[i + 1];
	}
	pc->sz--;
}

查找函式

查找函式是查找想要的數在順序表中第一個位置,該代碼如下

int SeqListFind(SeqList* pc, int x)
{
	assert(pc);
	for (int i = 0; i < pc->sz; i++)//先閱歷一遍陣列
	{
		if (pc->s[i] == x)
		{
			return i ;//找到了該數,則回傳該數在線性表的下標
		}
	}
	return 0;//如果找不到,則回傳0
}

在指定的位置中插入一個數據

代碼如下

void SeqListInster(SeqList* pc, int pos, int x)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->sz);//檢查該位置是否為合理
	CheckCapacity(pc);//檢查容量是否滿了
	int i = pc->sz-1;
	while (i>=pos)
	{
		pc->s[i + 1] = pc->s[i];
		i--;
	}
	pc->s[pos] = x;
	pc->sz++;
}

洗掉指定位置的資料

void SeqListErase(SeqList* pc, int pos)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->sz);//檢查pos是否為有效位置
	if (pc->sz == 0)
	{
		return 0;
	}
	int i = pos;
	for (i = pos; i < pc->sz - 1; i++)
	{
		pc->s[i] = pc->s[i + 1];
	}
	pc->sz--;//有效資料減1
}

好了,文章就寫到這里了,如果有什么不懂的地方,可以私信我一下,我盡量幫助你去搞懂,若文章有什么錯誤,可以在評論區里幫我指正,如果文章對你有幫助的話,希望你能夠幫我點個贊鼓勵一下筆者,謝謝!