C語言順序表的基本操作(初始化,插入,刪除,查詢,擴(kuò)容,打印,清空等)

更新時(shí)間：2023年02月05日 10:44:54 作者：安河橋畔

這篇文章主要介紹了C語言順序表的基本操作(初始化,插入,刪除,查詢,擴(kuò)容,打印,清空等)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。

順序表的基本操作

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

在數(shù)組上完成數(shù)據(jù)的增刪查改等基本操作。

初始化

初始化結(jié)構(gòu)體，開辟空間

void SeqListInit(SeqList* ps, size_t inite_capicity)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
	if (NULL == ps->arr)
	{
		exit(1);
	}
	ps->capicity = inite_capicity;
	ps->size = 0;
}

清空

因?yàn)閯?dòng)態(tài)內(nèi)存申請(qǐng)用完空間必須釋放，所以存在這個(gè)函數(shù)

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capicity = 0;
		ps->size = 0;
	}
}

打印

打印順序表內(nèi)容

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

擴(kuò)容

增加順序表的容量

static void SeqListRealloc(SeqList* ps)
{
	SLDataType* temp = ps->arr;
	temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
	if (temp != NULL)
	{
		// 若申請(qǐng)則將擴(kuò)容后的地址賦給ps->size
		// 這樣做的目的是防止空間申請(qǐng)失敗后原有空間的地址無法找回
		ps->arr = temp;
	}
	ps->capicity *= 2;
}

尾插法

尾插法只需要將元素放入最會(huì)一個(gè)位置，并對(duì)size加上1即可

void SeqListPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	//先判斷是否已滿，如果已滿則需要擴(kuò)容
	if (ps->size == ps->capicity)
	{
		SeqListRealloc( ps);//調(diào)用擴(kuò)容函數(shù)
	}
	ps->arr[ps->size] = data;//將數(shù)據(jù)放到順序表的結(jié)尾
	ps->size++;//有效元素增加一個(gè)
}

判空

插入操作前都要判斷順序表是否已滿

static int IsSeqListEmpty(SeqList* ps)
{
	assert(ps);
	if (0==ps->size)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

尾刪法

尾刪只需要將實(shí)際元素個(gè)數(shù)減一即可

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		ps->size--;
	}
}

頭插法

順序表所有元素向后移動(dòng)一個(gè)單位，在第一個(gè)位置插入數(shù)據(jù)

void SeqListPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若順序表空間已滿調(diào)用擴(kuò)容函數(shù)
	}
	//***將ps->size強(qiáng)轉(zhuǎn)成int類型，否則計(jì)算時(shí)會(huì)發(fā)生類型提升***
	for (int i = (int)ps->size - 1; i >= 0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//所有元素向后移動(dòng)一個(gè)單位
	}
	ps->arr[0] = data;//將元素插入順序表頭部
	ps->size ++;//元素個(gè)數(shù)加1
}

頭刪法

將第一個(gè)元素以后的所有元素向前移動(dòng)一個(gè)單位

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = 0; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素個(gè)數(shù)減1
	}
}

查詢

查詢表中是否有某一元素，若存在則返回其下標(biāo)

int SeqListFind(SeqList* ps, SLDataType data)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == data) 
		{
			return i;
		}
	}
	return -1;//未找到返回-1
}

任意位置插入

函數(shù)的第二個(gè)參數(shù)為要插入的位置，第三個(gè)參數(shù)為要插入的數(shù)據(jù)，與頭插原理相似

void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若順序表空間已滿調(diào)用擴(kuò)容函數(shù)
	}

	for (int i = (int)ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移動(dòng)一個(gè)單位
	}
	ps->arr[pos] = data;//將元素插入順序表頭部
	ps->size++;//元素個(gè)數(shù)加1
}

任意位置刪除

從某一要?jiǎng)h除的元素位置開始，后面所有元素向前移動(dòng)一個(gè)單位

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = (int)pos; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素個(gè)數(shù)減1
	}
}

完整代碼

下面給出線性表操作的完整代碼，代碼的注釋對(duì)每步的作用有詳細(xì)的介紹：

其中work.h頭文件主要完成包含頭文件和結(jié)構(gòu)體、各個(gè)函數(shù)的聲明
main.c源文件是程序的入口，并在這里實(shí)現(xiàn)測(cè)試用例，具體使用時(shí)，結(jié)構(gòu)體變量在main.c中定義
work.c源文件是各個(gè)操作的具體函數(shù)的實(shí)現(xiàn)

work.h

#pragma once
#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<assert.h>
#define MAXSIZE 50

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//起始地址 
	size_t capicity;//容量
	size_t size;//有效數(shù)據(jù)

}SeqList;

//下面這些都是函數(shù)聲明
void SeqListInit(SeqList* ps,size_t inite_capicity);//初始化
void SeqListDestory(SeqList* ps);//空間釋放
void SeqListPushBack(SeqList* ps, SLDataType data);//尾插
void SeqListPopBack(SeqList* ps);//尾刪
void SeqListPushFront(SeqList* ps,SLDataType data);//頭插法
void SeqListPopFront(SeqList* ps);//頭刪法
int SeqListFind(SeqList* ps, SLDataType data);//查找
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//任意位置插入
void SeqListErase(SeqList* ps, size_t pos);//任意位置刪除
void SeqListPrint(SeqList* ps);//順序表打印

main.c

#include"work.h"

//測(cè)試用例
void TestSeqList()
{
	SeqList s;
	SeqList* ps = &s;
	SeqListInit(ps, MAXSIZE);

	SeqListPushBack(ps, 1);//尾插法增加5個(gè)元素
	SeqListPushBack(ps, 2);
	SeqListPushBack(ps, 3);
	SeqListPushBack(ps, 4);
	SeqListPushBack(ps, 5);
	SeqListPrint(ps);//打印輸出

	SeqListPopBack(ps);//尾刪法刪除一個(gè)元素
	SeqListPrint(ps);//打印輸出 

	SeqListPushFront(ps, 0);	//頭插法增加一個(gè)元素
	SeqListPrint(ps);	//打印輸出 

	SeqListPopFront(ps);//頭刪法刪除一個(gè)元素
	SeqListPrint(ps);	//打印輸出 

	//調(diào)用查找函數(shù)并返回下標(biāo)，若不存在返回值為-1
	printf("%d\n", SeqListFind(ps, 2));
	printf("%d\n", SeqListFind(ps, 10));

	SeqListInsert(ps, 4, 5);//第4個(gè)位置插入
	SeqListPrint(ps);

	SeqListErase(ps, 5);//第5個(gè)位置刪除
	SeqListPrint(ps);

	SeqListDestory(ps);
}

int main()
{
	TestSeqList();//調(diào)用測(cè)試函數(shù)
	system("pause");
	return 0;
}

work.c

#include"work.h"

//初始化函數(shù)
void SeqListInit(SeqList* ps, size_t inite_capicity)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
	if (NULL == ps->arr)
	{
		exit(1);
	}
	ps->capicity = inite_capicity;
	ps->size = 0;
}

//堆空間釋放釋放函數(shù)
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capicity = 0;
		ps->size = 0;
	}

}

//順序表打印函數(shù)
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//擴(kuò)容函數(shù)
static void SeqListRealloc(SeqList* ps)
{
	SLDataType* temp = ps->arr;
	temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
	if (temp != NULL)
	{
		// 若申請(qǐng)則將擴(kuò)容后的地址賦給ps->size
		// 這樣做的目的是防止空間申請(qǐng)失敗后原有空間的地址無法找回
		ps->arr = temp;
	}
	ps->capicity *= 2;
}

//尾插法
void SeqListPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	//先判斷是否已滿，如果已滿則需要擴(kuò)容
	if (ps->size == ps->capicity)
	{
		SeqListRealloc( ps);//調(diào)用擴(kuò)容函數(shù)
	}
	ps->arr[ps->size] = data;//將數(shù)據(jù)放到順序表的結(jié)尾
	ps->size++;//有效元素增加一個(gè)

}

//判空函數(shù)
static int IsSeqListEmpty(SeqList* ps)
{
	assert(ps);
	if (0==ps->size)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//尾刪法
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		ps->size--;//尾刪只需要將實(shí)際元素個(gè)數(shù)減一即可
	}
}

//頭插法
void SeqListPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若順序表空間已滿調(diào)用擴(kuò)容函數(shù)
	}
	//***將ps->size強(qiáng)轉(zhuǎn)成int類型，否則計(jì)算時(shí)會(huì)發(fā)生類型提升***
	for (int i = (int)ps->size - 1; i >= 0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//所有元素向后移動(dòng)一個(gè)單位
	}
	ps->arr[0] = data;//將元素插入順序表頭部
	ps->size ++;//元素個(gè)數(shù)加1
}

//頭刪法
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = 0; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素個(gè)數(shù)減1
	}
}


//查詢
int SeqListFind(SeqList* ps, SLDataType data)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == data) 
		{
			return i;
		}
	}
	return -1;//未找到返回-1
}

//任意位置插入
void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若順序表空間已滿調(diào)用擴(kuò)容函數(shù)
	}

	for (int i = (int)ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移動(dòng)一個(gè)單位
	}
	ps->arr[pos] = data;//將元素插入順序表頭部
	ps->size++;//元素個(gè)數(shù)加1
}

//任意位置刪除
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = (int)pos; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素個(gè)數(shù)減1
	}
}