顺序表的基本操作（必学）

秦jh

发布于 2024-01-19 10:36:01

2180

发布于 2024-01-19 10:36:01

文章被收录于专栏：c语言，c++

线性表：

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛应用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串……。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表：

概念和结构：

顺序表是用一段物理地址连续的存储单元依次存放数据元素的线性结构，一般情况下用数组存储。顺序表有一个特点：必须从头开始存数据

1.静态顺序表：使用定长数组存储元素

2.动态顺序表：使用动态开辟的数组存储

动态顺序表常用操作实现：

头文件（数组顺序表的声明）：

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;    
	int size;      //数据的个数
	int capacity;    //容量大小
}SeqList;

使用SLDateType代替int是因为如果需要更改数据类型，直接将int修改即可，操作方便。

各种基本操作总的声明：

//初始化
void SeqListInit(SeqList* ps);
//销毁
void SeqListDestroy(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//头插
void SeqListPushFront(SeqList* ps, SLDateType x);
//头删
void SeqListPopFront(SeqList* ps);
//尾删
void SeqListPopBack(SeqList* ps);
//检查是否需要扩容
void SeqListCheckCapacity(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

顺序表的初始化：

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->size = 0;
	ps->a = NULL;
}

顺序表的销毁

void SeqListDestroy(SeqList* ps)
{
	assert(ps);

	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}

顺序表的打印

void SeqListPrint(SeqList* ps)		
{
	assert(ps);

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

检查是否需要扩容

void SeqListCheckCapacity(SeqList* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = tmp;
		ps->capacity = NewCapacity;
	}

}

尾插

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++; 
}

头插

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);

	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

头删

void SeqListPopFront(SeqList* ps)
{
	assert(ps->size > 0);

	int begin = 1;
	while (begin<ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

尾删

void SeqListPopBack(SeqList* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

顺序表的查找

int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

顺序表的插入

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;

}

顺序表的删除

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}