【数据结构初阶】--顺序表(三)

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。 

前言：在上篇博客中我们已经完成了顺序表的头插，尾插，头删，尾删等接口。今天博主将带大家实现顺序表中剩下的几个接口，还是一样，先分开来实现，最后为大家展示总的代码。

目录

一.顺序表的指定位置查找

二.顺序表的指定位置插入

三.顺序表的指定位置删除 

四.顺序表的修改和销毁

 五.代码展现

SeqList.h：

SeqList.c：

test.c：

一.顺序表的指定位置查找

--指定位置的插入和删除我们都需要先找到指定位置，才能继续往下实现。所以我们先来实现下这一个接口吧。

SeqList.c：

//查找
int SLFind(SL* ps, SLdatatype x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;//返回一个无效坐标
}

重点提示:

 这里的查找实现很简单，遍历数组，找到了对应元素就返回它的对应下标，没找到就返回一个无效坐标-1。

test.c：

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	int pos=SLFind(&s,2);
	if (pos == -1)
		printf("找不到\n");
	else
		printf("找到了,下标为%d\n",pos);
}

int main()
{
	test1();
}

--测试出来没有问题，可以找到元素2，下标为1。 

二.顺序表的指定位置插入

--通过前面查找接口的实现，我们可以继续来实现我们的指定位置插入了

SeqList.c：

//在pos前插入
void SLInsert(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

重点提示：

先断言，ps！=NULL，pos的范围是[0,ps->size)；i从ps->size开始，到一直到i=pos结束，按从后往前的顺序依次向后移动一位，然后把插入的数据放在pos位置，最后ps->size++。

test.c：

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	int pos=SLFind(&s,2);
	SLInsert(&s, pos, 7);
	SLPrint(&s);// 1 7 2 3 4
}

int main()
{
	test1();
}

 --测试完没有问题，在指定位置插入了数据7，最后结果正确。

三.顺序表的指定位置删除 

 SeqList.c：

//删除pos位置的元素
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

重点提示：

断言的部分跟指定位置插入一样，i从pos开始，直到i=ps->size-1时结束，按从前往后的顺序依次向前移动，如图所示，覆盖掉pos位置的数据，最后直接ps->size--。

四.顺序表的修改和销毁

SeqList.c：

//修改
void SLModify(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	ps->arr[pos] = x;
}

 重点提示：

找到pos位置，把这个位置的值修改就行了，很简单没有什么特别难的地方

//销毁
void SLDestory(SL* ps)
{
	if(ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

重点提示： 

free掉ps->arr后，将所有的都恢复初始化状态

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	int pos=SLFind(&s,2);
	SLInsert(&s, pos, 7);
	SLPrint(&s);// 1 7 2 3 4
	SLErase(&s, pos);
	SLPrint(&s);//1 2 3 4
	SLModify(&s, pos, 6);
	SLPrint(&s);//1 6 3 4
	SLDestory(&s);

	//SLPushFront(&s, 5);
	//SLPrint(&s);// 5 1 2 3 4
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPrint(&s);// 5 1 2
	//SLPopFront(&s);
	//SLPrint(&s);//1 2
}

int main()
{
	test1();
}

 --测试完没有问题，成功把pos位置的修改成6，最后销毁

 五.代码展现

SeqList.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLdatatype;
typedef struct SeqList
{
	SLdatatype* arr;
	int size;
	int capacity;
}SL;

//顺序表初始化
void SLInit(SL* ps);

//打印顺序表
void SLPrint(SL* ps);

//尾插
void SLPushBack(SL* ps, SLdatatype x);
//头插
void SLPushFront(SL* ps, SLdatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//查找
int SLFind(SL* ps, SLdatatype x);
//在pos前插入
void SLInsert(SL* ps, int pos, SLdatatype x);
//删除pos位置的元素
void SLErase(SL* ps, int pos);
//修改
void SLModify(SL* ps, int pos, SLdatatype x);
//销毁
void SLDestory(SL* ps);

SeqList.c：

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//打印
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
//检查空间
void SLCheckCapacity(SL*ps)
{
	//扩容
	int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));
	if (tmp == NULL)
	{
		perror("realloc");
		exit(1);
	}
	ps->arr = tmp;
	ps->capacity = newcapacity;
}

//尾插
void SLPushBack(SL* ps, SLdatatype x)
{
	//检查空间是否足够
	SLCheckCapacity(ps);
	//空间足够
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLdatatype x)
{
	assert(ps);
	//检查空间是否足够
	SLCheckCapacity(ps);
	//空间足够
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLdatatype x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;//返回一个无效坐标
}
//在pos前插入
void SLInsert(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
//删除pos位置的元素
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//修改
void SLModify(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	ps->arr[pos] = x;
}
//销毁
void SLDestory(SL* ps)
{
	if(ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

test.c：

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	int pos=SLFind(&s,2);
	SLInsert(&s, pos, 7);
	SLPrint(&s);// 1 7 2 3 4
	SLErase(&s, pos);
	SLPrint(&s);//1 2 3 4
	SLModify(&s, pos, 6);
	SLPrint(&s);//1 6 3 4
	SLDestory(&s);

	//SLPushFront(&s, 5);
	//SLPrint(&s);// 5 1 2 3 4
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPrint(&s);// 5 1 2
	//SLPopFront(&s);
	//SLPrint(&s);//1 2
}

int main()
{
	test1();
}

往期回顾： 

【数据结构初阶】--算法复杂度的深度解析

【数据结构初阶】--顺序表(一)

【数据结构初阶】--顺序表(二)

结语：这篇博客中我们将顺序表的全部接口都实现完了，大家可以额外思考一下，怎么在pos后插入数据以及利用指定位置的插入，删除的复现来实现尾插，头插，尾删，头删。后面我会继续为大家分享其它数据结构的知识点，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。