顺序表的实现

顺序表的实现

 这里是动态开辟的空间的顺序表的实现。本篇博客主要讲解可是结构体的定义以及各个函数的实现。

1.结构体的定义代码语言：javascript代码运行次数：0运行复制

typedef struct SeqList
{
	SLDataType* array;
	size_t sz;
	size_t capacity;
} SeqList;

 由于这里使用的是动态开闭空间的顺序表。所以在结构体的定义上可能会有一些不同。他一开始是定义了一个指针。用于指向那一片连续的空间，这样当后面采用异地扩容的时候也可以对这指令指针进行重新赋值。 sz用于记录顺序表中真正存储了多少个元素。 capacity用于记录顺序表申请了多少空间。

---

2.内部的检查函数代码语言：javascript代码运行次数：0运行复制

#include"SeqList.h"

//内部的检查函数
void CheckCapacity(SeqList* ps)
{
    if (ps->capacity == ps->sz)
    {
        SLDataType* ptr = (SLDataType*)realloc(ps->array, 2 * (ps->capacity) * sizeof(SLDataType));
        if (ptr == ULL)
        {
            perror("realloc");
        }
        ps->array = ptr;
        ps->capacity = 2 * (ps->capacity);
        printf("增容成功\n");
    }
}

 这是一个内部的检查数，用来检查。动态申请的空间是否够多。这里传入一个生指向结构体的指针。capacity与sz进行比较。如果相等则用realloc进行空间的扩充。 这里要注意的是在使用lock嗯进行内容的扩充的时候，要先再申请一个指针，将申请的空间有这个指针来指向，然后再对这个指针进行判断，是为空指针。这样才能让指向顺序表的指针进行赋值，否则可能会产生内存泄露）

---

 .顺序表打印代码语言：javascript代码运行次数：0运行复制

//顺序表打印
void SeqListprint(SeqList* ps)
{
	int i = 0;
	for (i = 0; i < (ps->sz); i++)
	{
		printf("%5d", ps->array[i]);
	}
	printf("\n");
}

 这里用了循环去遍历那一片连续的空间。

---

4.初始化顺序表代码语言：javascript代码运行次数：0运行复制

void SeqListInit(SeqList* ps)
{
	SLDataType* ptr = (SLDataType*)malloc(Defult_size * sizeof(SLDataType));
	if (ptr == ULL)
	{
		perror("malloc");
	}
	ps->array = ptr;
	ps->capacity = Defult_size;
	ps->sz = 0;
	printf("初始化顺序表成功\n");
}

这里用宏定义了一个初始的大小Defult_size ，然后用malloc申请空间，直接依旧是为了防止mg申请空间失败，先对这个指针返回的指针进检查。然后再用返回的指针对结构体里的指针进行赋值。 然后将capacity赋值为默认的大小 然后再将sz赋值为零

---

5. 销毁顺序表代码语言：javascript代码运行次数：0运行复制

void SeqListDestory(SeqList* ps)
{
	free(ps->array);
	ps->capacity = 0;
	ps->sz = 0;
}

将动态申请的空间用free函数释放掉， 然后将置为capacity和sz都置为零。 当然这里也可以增加一步将结构体内的指针也置为空指针。

---

6. 顺序表头部插入代码语言：javascript代码运行次数：0运行复制

//顺序表头部插入
void SeqListpushFornt(SeqList* ps, SLDataType data)
{
	CheckCapacity(ps);
	int i = 0;
	for (i = (ps->sz); i > 0; i--)
	{
		ps->array[i] = ps->array[i - 1];
	}
	ps->array[0] = data;
	ps->sz++;
}

用一个结构体指针和结构体内部数据类型作为形参。先使用内部的检查函数对传入的指针进行检查。看申请的空间是否能够再插入一个数据，如果不够，只要进行扩容。然后再利用一个循环将所有数据向后移位。然后将要插入的数据进行赋值，最后再加sz进行加加。

---

7.顺序表头部删除代码语言：javascript代码运行次数：0运行复制

void SeqListpopFront(SeqList* ps)
{
	int i = 0;
	for (i = 0; i < (ps->sz); i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->sz--;
}

用一个结构体指针作为形参，用一个循环将前面的空间赋值为后一个顺序表内的数据进行覆盖。从而达到第一个属性表的数据进行删除的效果。

---

8.顺序表尾部插入代码语言：javascript代码运行次数：0运行复制

void SeqListpushBack(SeqList* ps, SLDataType data)
{
	CheckCapacity(ps);
	ps->array[ps->sz] = data;
	ps->sz++;

}

用一个结构体指针和结构体内部数据类型作为形参。调用内部的函数，对传入的结构体指针进行检查空间是否足够。然后就直接利用sz访问到数据的末尾，将要插入的数据到顺序表的末尾。

---

9.顺序表尾部删除代码语言：javascript代码运行次数：0运行复制

void SeqListpopBack(SeqList* ps)
{
	ps->sz--;
}

直接将sz减减，就将末尾数据进行忽略、这样在遍历的时候就不会遍历到。

---

10.顺序表查(返回的是从零开始的位置)代码语言：javascript代码运行次数：0运行复制

int  SeqListpopFornt(SeqList* ps, SLDataType data)
{
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (data == ps->array[i])
		{
			return i;
		}
	}
}

用一个结构体指针和结构体内部数据喜欢进行便利。用用一个循环进行遍历。将传入的数据和顺序表内的数据进行比较开较看是否相等。如果相等，则返回该数据在这一表面的下标。

---

 11.顺序表在pos位置插入x代码语言：javascript代码运行次数：0运行复制

void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);

	assert(0 < pos && pos < ps->sz);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->sz; i > pos - 1; i--)
	{
		ps->array[i] = ps->array[i - 1];
	}
	ps->array[pos - 1] = data;
	ps->sz++;
}

用一个结构体指针和一个整数类型以及一个顺序表内部类型作为形参。 用assertt函数对传入的结构体指针进行检查。 然后再用assertt函数对传入的整形也就是pos位置进行检查，看是否在一个合理的区间内。 然后再用内部的检查函数对转入的指针也就是空间进行检查，看是否空间是满了，有没有足够的空间来进行插入操作。 然后就直接从顺序表的末尾开始利用循环将每个数据往后移一位直到pos位置。然后；利于pos去访问顺序表。

---

12.顺序表删除pos位置的值代码语言：javascript代码运行次数：0运行复制

void SeqListsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);

	assert(0 < pos && pos < ps->sz);

	int i = 0;

	for (i = pos - 1; i < ps->sz; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->sz--;
}

用断言函数断言PS是否为空函数。并且pos是否为一个在一个合理的区间内，然后再用循环，从pos开始，把后一个的值赋给前一个。进行覆盖，从而达到删掉oss位置的值效果。

---

---

这样子就实现了顺序表各个的函数之间的详细内容如果要去使用顺序表的话需要先将各个函数实现。然后在测试的时候，熟悉这个参数的传值，这样就可以了。 

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：202-11-09，如有侵权请联系 cloudcommunity@tencent 删除前往查看数据指针ps遍历函数