C語言順序表的概念及結(jié)構(gòu)是什么

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

1.順序表的概念及結(jié)構(gòu)

順序表是使用一段連續(xù)物理地址的單元來依次儲存數(shù)據(jù)的線性結(jié)構(gòu)，一般采用數(shù)組存儲。在數(shù)組上完成增刪查改。

順序表分為兩類：

靜態(tài)順序表：使用定長數(shù)組儲存元素

struct SeqList
{
    int data;//存儲的數(shù)據(jù)
    int size;//記錄數(shù)據(jù)個數(shù)
    int 1000;//給定當(dāng)前順序表的總?cè)萘繛?000
};

動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲

struct SeqList
{
    int data;//存儲的數(shù)據(jù)
    int size;//記錄數(shù)據(jù)個數(shù)
    int capacity;//順序表的總?cè)萘?
};

2.增刪查改的實(shí)現(xiàn)

當(dāng)我們需要儲存的數(shù)據(jù)數(shù)目不確定時我們使用動態(tài)順序表更佳，所以下面就用動態(tài)順序表來實(shí)現(xiàn)增刪查改。

2.1擴(kuò)容

首先我們動態(tài)順序表想要實(shí)現(xiàn)自動擴(kuò)容，當(dāng)當(dāng)前數(shù)據(jù)量size等于總?cè)萘縞apacity時我們就需要自動增容，具體就是使用malloc函數(shù)開辟一定數(shù)量的空間，假如我們設(shè)定每次擴(kuò)充二倍，代碼如下：

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

2.2插入數(shù)據(jù)

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

2.2.1尾插

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

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

2.2.2頭插

頭插相對來說要復(fù)雜一點(diǎn)，當(dāng)頭上沒有數(shù)據(jù)時，我們就可以看成尾插直接插入，當(dāng)頭上有數(shù)據(jù)時，我們?yōu)榱吮苊鈹?shù)據(jù)的覆蓋，需要將所有數(shù)據(jù)向后移動，再放入在頭部，在我們向后移動數(shù)據(jù)時我們也需要判斷是否滿容了。

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

2.2.3任意位置插入

我們?nèi)我馕恢貌迦霑r有三種情況，當(dāng)在第一個位置時就是頭插可以調(diào)用頭插的函數(shù)，在最后一個位置時就是尾插，就調(diào)用尾插的函數(shù)，當(dāng)我們在中間的時我們需要找到需要插入的位置，然后將數(shù)據(jù)從這個位置開始向后挪動，再插入進(jìn)去。

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

2.3刪除數(shù)據(jù)

刪除數(shù)據(jù)和上面的插入數(shù)據(jù)差不多，我們也需要湊夠三個方面來撕開，頭部刪除，尾部刪除，中間任意位置刪除，當(dāng)我們刪除數(shù)據(jù)時我們只需要將這個數(shù)據(jù)后的數(shù)據(jù)依次向前挪動，覆蓋住這個數(shù)據(jù)即可。這里我們不能用free函數(shù)去釋放那塊地址的空間來刪除，因?yàn)轫樞虮淼奈锢淼刂肥沁B續(xù)的。鏈表可以，下一章會介紹。

2.3.1尾刪

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

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

2.3.2頭刪

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

//刪除需要檢查，刪多了會越界
//頭刪
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任意位置刪除

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

//任意位置刪除
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查找

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

//查找
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修改數(shù)據(jù)

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

//改數(shù)據(jù)
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銷毀空間

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

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

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