数据结构之顺序表

虽然说顺序表是通过数组实现的但是数组和顺序表还是有很大的区别的，顺序表里面有很多的方法，这些方法包装好成为了我们的数组，而数组只是顺序表的底层结构，只是实现顺序表的一部分，就好比如一个小饭馆和我们的米其林餐厅，可能同样是一份土豆丝，但是米其林餐厅要经过摆盘等一系列的修饰最后成为了我们的另一道名字不同的菜，但是他还是又是由土豆丝为基础材料的，这里的顺序表就是我们的米其林餐厅，而我们的小饭馆就是数组。

总之：顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。

2.3顺序表的分类

顺序表有：静态的顺序表和动态的顺序表

静态的顺序表就是你定义一个定长的数组，这个数组的能存储的最多数据已经定了，你也不呢个再改变它了。

定义顺序表的时候结构体的写法如下：

这里我们的顺序表不只是用来存储整形的所以我们的可以用typedef关键字来重命名一下，方便我们的数据类型的改变，这样我们就不用再改变数据类型的时候一个个去修改里面的内容。

为了方便我们定义结构体，我们也可以将结构体名字重命名。

动态顺序表：这时候数组的空间就需要我们自己去动态开辟，这就让我们可以改变我们的数组大小，当我们的数组的大小不够时我们还能继续去申请空间继续加数据。

这里的静态数组我们的数组长度定多少合适呢？太大了会浪费太小了不够，所以很明显我们的动态数组会更好，因为我们的数组长度可以变的,这就不会浪费很多空间，和空间受限，因为不够我们还能继续去申请。

所以我们的用动态数组来实现我们的顺序表。

3顺序表基本功能的实现

顺序表的基本功能有：增删查找等。

当然我们可以根据自己的需求可以去添加方法。

3.1实现顺序表时文件的创建

首先我们实现顺序表的时候需要创建一个头文件:把我们所有的的头文件和方法名的声明放在里面。这样我们只需要引用这个头文件就可以了。

还需要一个我们实现顺序表的功能的.c文件，我们把方法的实现放在这个里面。

和一个用来测试你的方法有误写出bug的teat.c文件。

3.2顺序表的实现

记住记住每写完一个方法就去通过调试看看写错了没，这样你才有耐心去改。

我们这里函数的传参一般传地址，因为你要修改里面的内容不能只传一个值

这就使传值和传址的区别。

初始化

首先我们的顺序表最开始时是没有存放数据的空间的，我们可以写一个初始化顺序表的函数来给数组创建空间，

初始化的时候我们可以用malloc来申请空间，因为我们没有对数据初始化的要求，如果有你可以用calloc，他会将数据初始化。

其次我们要保证我们成功申请到空间，这样我们的才可以去解引用。

//初始化
void SLInit(SL* ps)
{
	Elemtyped* p= (Elemtyped*)malloc(sizeof(Elemtyped) * 4);
	assert(p);//判断是否为空
	ps->data = p;
	ps->capacity = 4;//空间大小
	ps->size = 0;//里面的数据个数
}

此时我们的里面还没有存放数据。所以size位0；

大小capacity为你申请到的空间。

销毁

其次我们再来写个销毁，为了防止我们没释放动态开辟的空间导致内存泄漏，

因为我们动态开辟的只有数组，所以我们只需要销毁我们的数组就行，不是我们动态开辟的不能用free来释放空间，而且数组的空间是连续的释放的时候一次性就释放完成了。而且你还不能释放空指针，所以要进行断言。

代码：

//销毁
void SLDestroy(SL* p)
{
	assert(p);
	free(p->data);
}

尾插

然后我们来实现一个尾插来增加数据，我们的尾插就是在最后一个数据的后面来插入数据，我们的最后一个数据就是我们下标为size-1的地方我们可以通过下表来访问。我们增加数据时我们的size就要增加一。

但是在插入之前我们的判断一下数组是否满了，如果满了我们要去再去申请空间。

这里申请空间用realloc,这个是调整我们空间大小的函数。（这里的扩容我们也可以写个函数）。

//尾插
void SLPush(SL* ps, Elemtyped x)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		SLCheckCapacity(ps);
	}
	ps->data[ps->size] = x;
	ps->size++;
}
//扩容
void SLCheckCapacity(SL* ps)
{
	int newcapacity = 2 * ps->capacity;
	Elemtyped* p = (Elemtyped*)realloc(ps->data,sizeof(Elemtyped) *newcapacity);
	if (p == NULL)//判断是否申请到空间
	{
		perror("realloc:");
		exit(1);
	}
	ps->data = p;
	ps->capacity = newcapacity;
}

打印数据

这个函数很简单，我们只需要见数组从头到尾数组遍历一遍。只能到size-1这里，

打印里面的元素
void SLPrint(SL* ps)
{
	assert(ps);//判断是不是空指针
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

在指定位置插入数据

首先我们得判断数组是否满了，满了就得去扩容，然后我们得找到指定位置，再去进行插入，插入之前我们得去将后面的元素移动，我们得从后往前移，腾出你要插入的位置，再去进行插入，不要忘记改变数组的有效长度size。

指定位置插入
void SLInsert(SL* ps, int pos, Elemtyped x)//插入
{
	assert(ps);
	int i = 0;
	assert(pos<=ps->size&&pos>=0);
	if (ps->capacity == ps->size)
	{
		SLCheckCapacity(ps);//扩容
	}
	for (i = ps->size; i > pos; i++)
	{
		ps->data[i] = ps->data[i - 1];//移动
	}
	ps->data[pos] = x;
	ps->size++;
}

删除指定位置

我们删除指定位置只需要将该位置后面的数据往前移动，覆盖掉这个数据就删除成功了，记得改变有效长度的大小。

//指定位置删除
//pos[0,size-1]
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	printf("删除成功");
	ps->size--;
	return; 
}

按照元素查找，返回下标

我们只需要遍历数组来查找该数组是否有该元素，记得断言一下（ps不为空指针），还有就是不是空数组，就是size为0。

按照元素查找,返回下标
int SLFind(SL* ps, Elemtyped x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}
	printf("未有该值\n");
	return -1;
}

到这里我们常用的功能已经写完了，与需要的话自己可以加上一些方法

4顺序表全部代码

test.c自己写就可以了；

头文件：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include"Contact.h"

typedef per Elemtyped;

typedef struct SqList
{
	Elemtyped* data;
	int size;
	int capacity;
}SL;
// 初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
void SLPush(SL* ps,Elemtyped x);//尾插
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, Elemtyped x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, Elemtyped x);

SeqList.c

#pragma once
#include"SeqList.h"
//初始化
void SLInit(SL* ps)
{
	Elemtyped* p= (Elemtyped*)malloc(sizeof(Elemtyped) * 4);
	assert(p);//判断是否为空
	ps->data = p;
	ps->capacity = 4;//空间大小
	ps->size = 0;//里面的数据个数
}
//销毁
void SLDestroy(SL* p)
{
	assert(p);
	free(p->data);
}
//尾插
void SLPush(SL* ps, Elemtyped x)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		SLCheckCapacity(ps);
	}
	ps->data[ps->size] = x;
	ps->size++;
}
//扩容
void SLCheckCapacity(SL* ps)
{
	int newcapacity = 2 * ps->capacity;
	Elemtyped* p = (Elemtyped*)realloc(ps->data,sizeof(Elemtyped) *newcapacity);
	if (p == NULL)//判断是否申请到空间
	{
		perror("realloc:");
		exit(1);
	}
	ps->data = p;
	ps->capacity = newcapacity;
}



//打印里面的元素
void SLPrint(SL* ps)
{
	assert(ps);//判断是不是空指针
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}
//指定位置之前插入/删除数据
//pos[0,size]

//指定位置插入
void SLInsert(SL* ps, int pos, Elemtyped x)//插入
{
	assert(ps);
	int i = 0;
	assert(pos<=ps->size&&pos>=0);
	if (ps->capacity == ps->size)
	{
		SLCheckCapacity(ps);//扩容
	}
	for (i = ps->size; i > pos; i++)
	{
		ps->data[i] = ps->data[i - 1];//移动
	}
	ps->data[pos] = x;
	ps->size++;
}



//指定位置删除
//pos[0,size-1]
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	printf("删除成功");
	ps->size--;
	return; 
}
//按照元素查找,返回下标
int SLFind(SL* ps, Elemtyped x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}
	printf("未有该值\n");
	return -1;
//}