今天我们来看一下数据结构入门---顺序表

①  顺序表的创建

顺序表分为静态顺序表和动态顺序表,想要知道顺序表的怎么创建,就必须明白一个点: 顺序表是什么?

其实,顺序表就是数组, 只不过这个数组的元素类型不确定, 这个数组与其他数组唯一的区别是:有相应的增(增加数据)删(删除数据)改(修改数据)查(查找数据)功能

举个例子: 排挡和西餐厅

在排挡里要吃"西蓝花", 你有可能直接大喊一声: 老板,再加一盘西蓝花 !   这时老板会回一句: 来了来了! 

但是当你在西餐厅里: 服务员,麻烦给我加一份"绿野仙踪"

这时餐厅的服务员不仅会给一盘西蓝花给你,还会在上面放上一副刀叉,走过来时候说一句: 您请慢用

所以"绿野仙踪" 和 "西蓝花" 是一种东西,但是两者的服务方式则是完全不一样的(其实我觉得排挡比西餐厅好吃得多哈哈哈) 

说完这些,不知道你能不能理解顺序表和普通数组的区别与联系

接下来,我们就来看看静态顺序表的创建:

//静态顺序表的创建

#define N 100

struct SeqList
{
	int arr[N];
	int size;//表示数组中有效的元素个数
};

来看一下,我在这地方定义了一个整形数组,并定义它的元素个数为 N  规定 N 为 100 ,有人说,为什么要这样写,我直接写一个 int arr[100] 

它不香吗,原因是,我后面要涉及到各种与这个数组元素个数相关的操作,如果都写个100 那将来想要对数组进行扩容,那么所有写100 的地方是不是都要变大,如果涉及到10000 行代码,我难道要改10000 行吗,反之,我现在把`100 替换成 N ,涉及到数组元素的地方全部改成 N  将来想要改变数组的元素个数(假如说要变成1000),我是不是直接把 #define N 100 改成 #define N 1000  就行了? 

那有人又问了 那你为啥要搞一个 size , 有效的元素个数难道不是 N 吗 ,当然不是, 举个例子

你们公司领导,让你和你的团队开发一个软件,那你用户容量给多少个? 你是不是肯定给大一点呀,因为你怕不够

后来发现,你确实给大了,但是后面肯定会有新用户注册进来,这时候就可以先用剩余的空间填补,就不用频繁增容了对不

所以说你当前的总容量 N 肯定是要大于有效元素个数 size ,后续才好增加数据

如果明白了这一点,那我们再往下看: 你就知道这个数组一定是整形的吗? 它有可能是 float  double char ......     那我这个地方也不能写死:

#define N 100

typedef int SLDataType;

struct SeqList
{
	SLDataType arr[N];
	int size;//数组中有效的数据个数
};

在这里同样的,这样写之后,我把后面所涉及到元素类型的操作全部替换成 SLDataType  然后想操作浮点数类型的时候,我就直接 把 int 改为 float 不就行了吗? 存有其他元素类型的数组以此类推....

这个结构体的名字是不是太长了呀?  那我把它换成 SL 后面用的时候是不是方便一点?

#define N 100

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType arr[N];
	int size;//数组中有效的数据个数
}SL;

//或者: typedef struct SeqList SL;

到这里,静态顺序表的创建就完了.

而在实际开发中,一般用的是动态顺序表,其创建与静态顺序表大差不差:

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;
	int size;//表示有效元素个数
	int capacity;//表示总容量(以个数为单位)
}SL;

由于动态顺序表的大小是由程序员自己指定开辟的,所以其总容量不确定.

② 顺序表相关功能的实现

(1) 顺序表的初始化: 

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

有人问,这个地方为什么要用指针接收呀,原因是:如果我只是单纯用一个结构体来接收,在此函数内部会对该接收的结构体进行初始化,而不会对我想初始化的那个结构体进行操作,简单来说就是: 形参是实参的一份临时拷贝,对形参的改变不会影响实参,所以结构体在传参的时候通常传的是指针

⑵ 顺序表的尾插:

void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		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;
	}
	ps->arr[ps->size++] = x;
}

⑶ 头插:

void SLPushFront(SL* ps, SLDataType x)
{
	SLrec(ps);//判断扩容
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = x;
	ps->size++;
}

(4) 判断扩容:

void SLrec(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		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;
	}
}

(5)尾删:

void SLPopBack(SL* ps)
{
	ps->size--;
}

⑹ 头删:

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

⑺ 指定位置插入:

void SLInsert(SL* ps, int pos, SLDataType x)
{
	SLrec(ps);
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size++;
}

⑻ 删除指定位置数据:

void SLErase(SL* ps, int pos)
{
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

⑼ 查找数据:

int SLFind(SL* ps, SLDataType x)
{
	int i = 0;
	for ( i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	if (i == ps->size)
		return -1;
}

⑽ 打印:

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}

⑾ 销毁:

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