C語言順序表的概念及結構是什么

這篇文章主要介紹“C語言順序表的概念及結構是什么”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C語言順序表的概念及結構是什么”文章能幫助大家解決問題。

1.順序表的概念及結構

順序表是使用一段連續物理地址的單元來依次儲存數據的線性結構，一般采用數組存儲。在數組上完成增刪查改。

順序表分為兩類：

靜態順序表：使用定長數組儲存元素

struct SeqList
{
    int data;//存儲的數據
    int size;//記錄數據個數
    int 1000;//給定當前順序表的總容量為1000
};

動態順序表：使用動態開辟的數組存儲

struct SeqList
{
    int data;//存儲的數據
    int size;//記錄數據個數
    int capacity;//順序表的總容量
};

2.增刪查改的實現

當我們需要儲存的數據數目不確定時我們使用動態順序表更佳，所以下面就用動態順序表來實現增刪查改。

2.1擴容

首先我們動態順序表想要實現自動擴容，當當前數據量size等于總容量capacity時我們就需要自動增容，具體就是使用malloc函數開辟一定數量的空間，假如我們設定每次擴充二倍，代碼如下：

//增容
void SLCheckcapacity(SL* pc)
{
	assert(pc != NULL);
	//檢查容量，滿了就擴容
	if (pc->sz == pc->capacity)
	{
		//一次擴容二倍，如果初始為0就先擴容到4
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		//注意類型轉換
		SLDatatype* tmp = (SLDatatype*)realloc(pc->data, sizeof(SLDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("SLCheckcapacity::realloc");
			exit(-1);
		}
		//講開辟的空間tmp給到數組
		pc->data = tmp;
		pc->capacity = newcapacity;
	}
}

2.2插入數據

插入數據時我們有三種情況，頭插尾插和中間任意位置插。

2.2.1尾插

先從最簡單的尾插開始，我們尾插時需要記錄下當前的size，這樣插入的時候就可以直接找到尾部，我們需要注意的是，我們插入之前需要判斷一下當前的容量滿了沒有，如果滿了就需要擴容，沒滿就可以直接插入。

//尾插
void SLPushBack(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	//需要判斷是否需要增容
	SLCheckcapacity(pc);
	pc->data[pc->sz] = x;
	pc->sz++;
}

2.2.2頭插

頭插相對來說要復雜一點，當頭上沒有數據時，我們就可以看成尾插直接插入，當頭上有數據時，我們為了避免數據的覆蓋，需要將所有數據向后移動，再放入在頭部，在我們向后移動數據時我們也需要判斷是否滿容了。

//頭插
void SLPushFront(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	SLCheckcapacity(pc);
	//挪動數據
	int end = pc->sz - 1;
	while (end >= 0)
	{
		pc->data[end + 1] = pc->data[end];
		--end;
	}
	//插入數據
	pc->data[0] = x;
	pc->sz++;
}

2.2.3任意位置插入

我們任意位置插入時有三種情況，當在第一個位置時就是頭插可以調用頭插的函數，在最后一個位置時就是尾插，就調用尾插的函數，當我們在中間的時我們需要找到需要插入的位置，然后將數據從這個位置開始向后挪動，再插入進去。

//任意位置插入
void SLInsert(SL* pc, int pos, SLDatatype x)
{
	assert(pc);
    //判斷pos是否在有效數據范圍內
	assert(pos >= 0 && pos <= pc->sz);
	SLCheckcapacity(pc);
    //挪動數據
	int end = pc->sz - 1;
	while (end >= pos)
	{
		pc->data[end+1] = pc->data[end];
		--end;
	}
	pc->data[pos] = x;
	pc->sz++;
}

2.3刪除數據

刪除數據和上面的插入數據差不多，我們也需要湊夠三個方面來撕開，頭部刪除，尾部刪除，中間任意位置刪除，當我們刪除數據時我們只需要將這個數據后的數據依次向前挪動，覆蓋住這個數據即可。這里我們不能用free函數去釋放那塊地址的空間來刪除，因為順序表的物理地址是連續的。鏈表可以，下一章會介紹。

2.3.1尾刪

尾部后面沒有數據那么就把最后一個數據制成0就好了

//尾刪
void SLPopBack(SL* pc)
{
	assert(pc != NULL);
	//不能刪多了
	assert(pc->sz > 0);
	pc->sz--;
}

2.3.2頭刪

將從第二個位置開始的數據往前挪動，這里需要注意，刪除需要檢查，以免越界。

//刪除需要檢查，刪多了會越界
//頭刪
void SLPopFront(SL* pc)
{
	assert(pc != NULL);
	//檢查
	assert(pc->sz > 0);
	//從第二個元素開始從后往前挪直接將其覆蓋
	int begin = 0;
	while (begin <= pc->sz)
	{
		pc->data[begin-1] = pc->data[begin];
		++begin;
	}
	pc->sz--;
}

2.3.3任意位置刪除

任意位置刪除我們只需要將我們需要刪除的位置后面的數往前挪動就行了

//任意位置刪除
void SLErase(SL* pc, int pos)
{
	assert(pc != NULL);
	assert(pos >= 0 && pos < pc->sz);
	int begin = pos;
	while (begin < pc->sz-1)
	{
		pc->data[begin] = pc->data[begin + 1];
		begin++;
	}
	pc->sz--;
}

2.4查找

我們給一個數據x來表示我們想要查找的數據，從前往后把順序表遍歷一遍，當給的X等于順序表中的X時就找到了，返回當前位置的下標。

//查找
int SLFind(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	for (int i = 0; i < pc->sz; ++i)
	{
		if (pc->data[i] == x)
		{
			return i;
		}
	}
	printf("找不到\n");
	return;
}

2.5修改數據

當我們想要修改某一個地方的數據時，直接將那個位置的數據輸入新的數據覆蓋掉就行了。

//改數據
void SlModify(SL* pc, int pos, SLDatatype x)
{
	assert(pc != NULL);
	if (pos >= 0 && pos <= pc->sz)
	{
		pc->data[pos] = x;
	}
	else
	{
		printf("超出范圍了\n");
	}
}

2.6銷毀空間

當我們順序表使用完成過后，我們需要注意的是，我們malloc的空間并沒有得到釋放，可能會造成內存泄漏等問題（可參考前面的博客 '動態內存開辟' ），釋放內存就需要用到free函數

//銷毀空間
void SLDestory(SL* pc)
{
	if (pc->data)
	{
		free(pc->data);
		pc->data = NULL;
		pc->capacity = pc->sz = 0;
	}
}

關于“C語言順序表的概念及結構是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。