【数据结构】顺序表的学习

前言:在之前我们学习了C语言的各种各样的语法，因此我们今天开始学习数据结构这一个模块，因此我们就从第一个部分来开始学习"顺序表"。

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！

顺序表
- 动态顺序表
- - 顺序表的初始化
  - 顺序表的销毁
  - 顺序表的空间容量检查
  - 顺序表的打印
  - 顺序表的尾增
  - 顺序表的头增
  - 顺序表的头删
  - 顺序表的尾删
  - 顺序表的选择插入
  - 顺序表的删除数据
  - 顺序表数据的查找
- 练习

代码思路：选择插入，即将一个值，任意插入到顺序表中的范围内，当然了口头总是不太好说清，我们对着下图来进行一一分析，我们可以记录一个end坐标记录数据的尾部，然后将值一一覆盖，pos为我们想要出入数据的位置，例如下图，当end走到pos的位置的时候，即可停止覆盖，这有点类似与我们前面的头删，将值pos之后的值全部往后挪动了一位，然后将最后重复的值被想插入的值覆盖即可。
在这里插入图片描述

代码实现：

void SLInsert(SL* ps1, int pos, SLDataype x)//插入数据
//pos是下标，size是数据个数，看作下标的话，他是最后一个数的下一个位置
{
	assert(ps1);//判断传来的值是否是空指针
	assert(pos >= 0 && pos <= ps1->size);//插入的值必须是再范围内（可以包括尾增）
	SLCheckCapacity(ps1);//检查空间
	// 挪动数据
	int end = ps1->size - 1;//找到尾坐标
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];//将值一一覆盖，类似于头删
		--end;
	}
	ps1->a[pos] = x;//赋值
	ps1->size++;
}

我们依然来看看函数的效果是否实现，测试代码和效果图如下：

void TestSL5()
{
	SL s1;//创建动态顺序表
	SLInit(&s1);//初始化顺序表
	SLPushBack(&s1, 2);//尾增数据
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushFront(&s1, 20);//头增的数据
	SLPushFront(&s1, 10);
	SLPushFront(&s1, 0);
	SLPushFront(&s1, 9);
	SLPrint(&s1);//打印原本的数据
	printf("上面是原本的数据\n");
	printf("--------------------------------------\n");
	printf("下面是选择插入后的数据\n");
	SLInsert(&s1, 3, 99);
	SLInsert(&s1, 1, 2);
	SLPrint(&s1);//打印选择插入后的数据
	SLDestory(&s1);//销毁顺序表
}
int main()
{
	//TestSL1();
	//TestSL2();
	//TestSL3();
	//TestSL4();
	TestSL5();
	return 0;
}

在这里插入图片描述

顺序表的删除数据

代码思路：删除数据和选择插入的概念其实大差不差，首先也应当判断传过来的数是否是空指针，删除的数据在不在数据范围内，然后我们再通过图文来进行分析，如下图，先把删除的位置记录下来，当然了，和前面同理依次往前面覆盖，再打印的时候直接将size往前移一位即可把最后重复的值给去掉，达到顺序表的删除的功能。
在这里插入图片描述
函数代码：

void SLErase(SL* ps1, int pos)//删除数据
{
	assert(ps1);
	assert(pos >= 0 && pos < ps1->size);
	int begin = pos + 1;//记录删除数据后的位置
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];//依次覆盖
		++begin;
	}
	ps1->size--;
}

代码实现和函数实现效果图如下：

void TestSL6()
{
	SL s1;//创建动态顺序表
	SLInit(&s1);//初始化顺序表
	SLPushBack(&s1, 2);//尾增数据
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushFront(&s1, 20);//头增的数据
	SLPushFront(&s1, 10);
	SLPushFront(&s1, 0);
	SLPushFront(&s1, 9);
	SLPrint(&s1);//打印原本的数据
	printf("上面是原本的数据\n");
	printf("--------------------------------------\n");
	printf("下面是选择插入后的数据\n");
	SLErase(&s1, 3);//删除数据
	SLErase(&s1, 1);//删除数据
	SLPrint(&s1);//打印选择插入后的数据
	SLDestory(&s1);//销毁顺序表

}

int main()
{
	//TestSL1();
	//TestSL2();
	//TestSL3();
	//TestSL4();
	//TestSL5();
	TestSL6();
	return 0;
}

在这里插入图片描述

顺序表数据的查找

代码思路：顺序表数据的查找就过于简单了，我们只需要遍历数据，看看是否有对应的值，有则返回该数的下标，没有则返回**-1**。代码如下：

int SLFind(SL* ps1, SLDataype x)//顺序表数据的查找
{
	assert(ps1);//判断传来的数据是否是空指针
	for (int i = 0; i < ps1->size; i++)//遍历数组
	{
		if (ps1->a[i] == x)
			return i;//找到即返回坐标i
	}
	return -1;//没找到返回-1
}

函数测试与效果图：

void TestSL7()
{
	SL s1;//创建动态顺序表
	SLInit(&s1);//初始化顺序表
	SLPushBack(&s1, 2);//尾增数据
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushFront(&s1, 20);//头增的数据
	SLPushFront(&s1, 10);
	SLPushFront(&s1, 0);
	SLPushFront(&s1, 9);
	SLPrint(&s1);//打印原本的数据
	printf("上面是原本的数据\n");
	printf("--------------------------------------\n");
	printf("下面是选择插入后的数据\n");
	printf("该数的下标是:%d\n",SLFind(&s1, 2));
	SLDestory(&s1);//销毁顺序表
}
int main()
{
	//TestSL1();
	//TestSL2();
	//TestSL3();
	//TestSL4();
	//TestSL5();
	//TestSL6();
	TestSL7();
	return 0;
}

在这里插入图片描述
讲到这里，关于顺序表的基本内容实现全部讲完了，接下来我们来看一题目练习一下把！

练习

题目链接：
在这里插入图片描述

思路分析：看到这个题，大家都会想到一个很通俗易懂的方法，就是开辟一个辅助数组，将所有的数放进去，然后进去排序，当然我们今天是不讲这个方法的，因为这个方法的时间复杂度过于高。我们看到这个是一个非递减顺序，可以知道最大的数都放在了后面，因此我们可以将两个数中最后的元素拿出来依次比较，然后将较大的放在nums1中的最后面，依次类推，放到最后自然而然的可以将所有数进行排序，那怎么去实现它呢？看图说话，如下图，我们记录一个坐标i1和i2分别记录下两个数组中的最后一个元素，然后依次进行比较，如果i1中的数较大就放在下标j的位置，反之则把i2放进去，且如果nums1中走完了，nums2还没有，就只需要将nums2中的数据单独拿出来，放再j所在的位置即可。
在这里插入图片描述
代码实现如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int i1 = m - 1;//记录第一个数组的尾坐标
    int i2 = n - 1;//第二个数组尾坐标
    int j = m + n - 1;//记录总元素的坐标
    while(i1 >= 0 &&  i2 >= 0)
    {
        if(nums1[i1] > nums2[i2])
        {
            nums1[j--] = nums1[i1--]; 
        }
        else
        {
            nums1[j--] = nums2[i2--];
        }
    }
    while(i2 >= 0)
    {
        nums1[j--] = nums2[i2--];
    }
}