顺序表的实现（迈入数据结构的大门）（2）

目录

顺序表的头插(SLPushFront)

此时：我们有两个思路（数组移位）

顺序表的头删(学会思维的变换)(SLPopFront)

顺序表的尾插(SLPushBack)

有尾插就有尾删

既然头与尾部的插入与删除都有，那必然少不了指定位置的插入删除

查找目标值

指定位置插入(SLInsert)

指定位置删除(SLErase)

打印(顺序表的结尾之声)

书接上文

顺序表的头插(SLPushFront)

头插：

对于头插，我们需要先将数组头部的位置空余出来存放我们需要插入的数x；

所以我们需要将数组中的数向后移一位；

此时：我们有两个思路（数组移位）

1、从下标为0开始向后置换，此时会出现数值覆盖的问题，我们需要另创建一个变量（tmp）存放后一个值以防覆盖之后寻找不到；当tmp的下一个数组为NULL时；怎么办了？

这就要if语句判断或者使用while语句，那有什么方法能将此简化呢：这就来到第二个方法；

2、我们从数组末尾进行移位，这就防止了数值覆盖的问题，还不需要使用到其余语句的创建；

//头插
void SLPushFront(SL* ps, SLDataType x){
//记住SLDataType，这里为我们为了方便（typedef int SLDataType）
	assert(ps);//断言一下，防止指针为空
	SLCheckCapacity(&ps);//开辟空间
	int i = ps->size;
	for (; i > 0; i--);//从后往前移位
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;//此时a[0]就空出来存放x；
	ps->size++;//不要忘记size需要++
}

顺序表的头删(学会思维的变换)(SLPopFront)

对于头删，我们需要删除下标为0的值，然后将值向前移一位，与头插类似，只不过，此时是从前往后移动;

//头删
void SLPopFront(SL* ps) {
	assert(ps);
	assert(ps->size);//存放的值不能为NULL;
	for (int i = 0; i < ps->size-1; i++) {
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

顺序表的尾插(SLPushBack)

当我们学会了头插，顺序表的尾插相对我们来说，简直轻而易举

尾插：我们就要先判断是否还有空余位置，就要利用SLCheckCapacity(SL* ps)；是否需要扩容

此时ps->size的位置如图所示，我们就可以直接将x的值赋给当前位置，然后ps->size++;

//尾插
void SLPushBack(SL* ps, SLDataType x) {
	assert(ps);
	void SLCheckCapacity(SL * ps);
	ps->a[ps->size++] = x;
	//相当于ps->a[ps->size] = x;
	//ps->size++；
}

有尾插就有尾删

思考一下，尾删，我们将ps->size-1的位置删除：将其置为NULL,ps->size--,就完成了尾删;

那我们换一个思路，我们只将这个位置删除，是否可以，直接ps->size--呢：因为当我们打印的时候只需打印[0,size)之间的数，size这个位置需要打印吗？当然不用啦；如果我们需要尾插的时候呢，我们可以直接将此位置覆盖掉；

//尾删
void SLPopBack(SL* ps) {
	assert(ps);
	assert(ps->size);//进行尾删，必须存在尾删的值
	ps->size--;
}

既然头与尾部的插入与删除都有，那必然少不了指定位置的插入删除

查找目标值

对于查找数组中的值时，一般使用遍历查询；

//查找
int SLFind(SL* ps, SLDataType x) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {//对数组进行遍历
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;//循环结束，没有找到，返回-1；
}

指定位置插入(SLInsert)

指定位置插入与头插相似，需要将指定位置后的值向后移移位，在进行插入；

//注意：这里的pos对应数组下标

//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0 && ps->size > pos);//pos必须在含有值之间插入
	//插入数据：空间够不够
	SLCheckCapacity(ps);
	//让pos及之后的数据整体往后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];//a[pos+1] = a[pos]与头插具有相似之处，导致值的覆盖
	}
	ps->a[pos] = x;//这里的pos对应，数组下标，如果不对应，则按情况+-；
	ps->size++;
}

指定位置删除(SLErase)

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//与头删类似
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

打印(顺序表的结尾之声)

这里我们要注意结构体访问成员的方式 ( . )  ( -> )

C语言结构体—自定义类型—struct-CSDN博客

void SLPrint(SL s)//对于打印数组，这里不再需要传地址，而是传值
{
	for (int i = 0; i < s.size; i++)
	{//对于结构体的使用  （.）与（->）的不同
		printf("%d ", s.a[i]);
	}
	printf("\n");
}

以上我们完成了顺序表的实现，下一节我们将实现(通讯录)顺序表

---

看到这里就点个赞走吧！！！