前言

本章會用C語言來描述數(shù)據(jù)結(jié)構(gòu)中的順序表，實現(xiàn)簡單的增刪查改操作，其中頭文件包含在新建的頭文件SeqList.h內(nèi)，順序表的實現(xiàn)在新建的Seqlist.c內(nèi)，主函數(shù)Text.c將會實現(xiàn)菜單，方便我們進(jìn)行功能的選擇。

1. 順序表的概念

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

順序表分為靜態(tài)和動態(tài)兩個版本，一般我們都是使用動態(tài)的版本進(jìn)行操作
因為靜態(tài)的版本使用定長數(shù)組存儲元素，而動態(tài)的版本使用動態(tài)開辟的數(shù)組存儲

2. 動態(tài)順序表

2.1 順序表的初始化與銷毀

//初始化
void SLInit(SL* ps1)
{
	ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (ps1->a == NULL)
	{
		perror("malloc fail");//順序表為空就報錯，說明申請空間失敗
		return;
	}
	ps1->capacity = 4;//我們設(shè)定初始空間為4個SLDatatype(這里是int)大小
	ps1->size = 0;
}

注意要釋放掉內(nèi)存

void SLDestory(SL* ps1)
{
	free(ps1->a);//釋放
	ps1->a = NULL;//將順序表置為空
	ps1->size = 0;//有效數(shù)字置0
	ps1->capacity = 0;//容量置0
}

2.2 順序表的尾插

尾插，顧名思義，就是在順序表的尾部插入數(shù)據(jù),在實現(xiàn)尾插功能的同時，我們要寫一個檢查順序表容量的函數(shù)，插入的時候我們要檢查空間是否足夠，不夠則要進(jìn)行擴(kuò)容，足夠則插入。

void SLPushBack(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);//檢查容量
	ps1->a[ps1->size] = x;//尾插數(shù)據(jù)
	size++
	//ps1->a[ps1->size++] = x;
	
}

容量檢查

void SLCheckCapacity(SL* ps1)
{
	if (ps1->size == ps1->capacity)//有效數(shù)據(jù)大小如果和容量相等說明需要擴(kuò)容了
	{
		SLDatatype* tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2);
		//如果空間不夠了，就擴(kuò)容到原來的二倍
		if (tmp == NULL)
		{
			perror("realloc fail");//如果tmp為空說明擴(kuò)容空間失敗
			return;
		}
		ps1->a = tmp;//檢查確保tmp不為空再賦給a
		ps1->capacity *= 2;//容量變?yōu)樵瓉淼亩?/span>
	}

}

2.3 順序表的尾刪

實現(xiàn)尾刪功能我們需要注意的時，說是刪，但是我們可不能真刪了，并不是把數(shù)據(jù)置為\n或是\0，只需要把有效數(shù)據(jù)-1就行了。
注意：不可以對要刪除數(shù)的空間進(jìn)行釋放，因為動態(tài)開辟出的空間有一個特點:一起開辟，一起釋放，在這里不可以實現(xiàn)。

void SLPopBack(SL* ps1)
{   //尾刪數(shù)據(jù)
	assert(ps1);//暴力檢查一下
	//size不能一直-1
	if(ps1->size>0)
	{
	    p->size--;
	}
}

2.4 順序表的頭插

除了需要把順序表中【0，size-1】的元素依次向后移動一位，再插入數(shù)值
我們要從后往前向后移，因為從前往后的話數(shù)據(jù)會被覆蓋

void SLPushFront(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);//檢查容量
	for (int i = ps1->size - 1; i >= 0; i--)//頭插需要將順序表中【0，size-1】的元素依次向后移動一位
	{
		ps1->a[i + 1] = ps1->a[i];
	}
	ps1->a[0] = x;   //頭插數(shù)據(jù)
	ps1->size++;     //有效數(shù)據(jù)+1
}

2.5 順序表的頭刪

頭刪很簡單，與頭插相反，頭插是將從最后一個數(shù)開始向后覆蓋，而頭刪是從第二個元素開始從前往后覆蓋前一個元素。

void SLPopFront(SL* ps1)
{
	assert(ps1->a > 0);//暴力檢查
	for (int i = 0; i < ps1->size - 1; i++)
	{
		ps1->a[i] = ps1->a[i + 1];
	}
}

2.6 固定位置的插入

思路和頭插沒區(qū)別，只要找到要插入的位置，將它后面位置的元素全部向后移一位，然后插入，就OK了，需要注意的是pos(插入的位置)也要進(jìn)行斷言

void SLInsert(SL* ps1, int pos, SLDatatype x)
{
	assert(ps1);//斷言檢查空指針
	assert(pos>=0 && pos <= ps1->size);//斷言檢查pos是否合規(guī)

	SLCheckCapacity(ps1);//檢查容量
	int end = ps1->size - 1;
	while (pos <= end)
	{
		ps1->a[end + 1] = ps1->a[end];
		--end;
	}
	ps1->a[pos] = x;
	ps1->size++;
	

}

2.7 固定位置的刪除

同理，從要刪除的位置開始，從前往后將后一位的值賦給前一位，太簡單了

void SLEarse(SL* ps1, int pos)
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);

	SLCheckCapacity(ps1);
	int start = pos+1;
	while (start < ps1->size)
	{
		ps1->a[start - 1] = ps1->a[start];
		++start;
	}
	ps1->size--;
}

2.8 查找和打印

過于簡單，直接上代碼

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SLPrint(SL* ps1)
{
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ",ps1->a[i]);
	}
	printf("\n");
}

2.9 修改元素

void SLModify(SL* ps1, int pos, SLDatatype x)
{
	assert(ps1);
	assert(0 <= pos && pos < ps1->size);

	ps1->a[pos] = x;

}

主函數(shù)部分(菜單)

void menu()
{
	printf("***************************************\n");
	printf("1、尾插數(shù)據(jù)  2、尾刪數(shù)據(jù)\n");
	printf("3、頭插數(shù)據(jù)  4、頭刪數(shù)據(jù)\n");
	printf("5、打印數(shù)據(jù)  -1、退出\n");
	printf("***************************************\n");
}
int main()
{
	int option = 0;
	SL s;
	SLInit(&s);
	while (option != -1)
	{
		menu();
		printf("請輸入你的操作:>");
		scanf("%d", &option);
		if (option == 1)
		{
			/*printf("請輸入要尾插的數(shù)據(jù)，以-1結(jié)束:");
			int x = 0;
			scanf("%d", &x);
			while (x != -1)
			{
				SLPushBack(&s, x);
				scanf("%d", &x);
			}*/

			int n = 0;
			printf("請輸入要尾插的數(shù)據(jù)個數(shù)，再依次輸入要插入的數(shù)據(jù):");
			scanf("%d", &n);

			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushBack(&s, x);
				n--;
			}
		}
		else if (option == 5)
		{
			SLPrint(&s);
		}
		else if (option == -1)
		{
			break;
		}
		else
		{
			printf("無此選項,請重新輸入\n");
		}
	}

	SLDestroy(&s);

	return 0;
}

結(jié)語

就這樣，順序表從定義到結(jié)束，增刪查改的功能也全部實現(xiàn)了，學(xué)到這里，我們就大致掌握了順序表，同時我們也要思考一些問題：
1.中間/頭部的插入，時間復(fù)雜度為O(N)
2.增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間，這個過程會有損耗
3.增容一般是以兩倍的方式增長，所以必定會造成浪費(fèi)，比如我們當(dāng)前容量為100，已經(jīng)滿了，我們擴(kuò)容到200，但是只新插入了5個數(shù)據(jù)，這就浪費(fèi)了95個數(shù)據(jù)空間
如何處理呢？

文章來源地址http://www.zghlxwxcb.cn/news/detail-436298.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門(C語言)順序表的增刪查改的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！