数据结构：顺序表

🎇个人主页：Ice_Sugar_7
🎇所属专栏：初阶数据结构
🎇欢迎点赞收藏加关注哦！

🍉概念

顺序表是一种数据结构，它在逻辑结构和物理结构上是线性的，这里的物理结构指的就是它在内存中的存储。
顺序表的底层结构是数组，也就是说它是基于数组实现的。那么废话少说，来看看如何实现顺序表吧。

---

🍉顺序表的结构

先来看下顺序表长啥样：

typedef int SLDateType;
typedef struct Seqlist {
	SLDateType* arr;
	int size;
	int capacity;
}SL;

1
2
3
4
5
6
7

arr是一个数组，这里没有指定它的大小，此时就是一个动态顺序表，要用的时候就用malloc给它开辟一块空间。

Q：为啥用typedef 重新命名 int？
A：因为数组 arr 存放的不一定是整型，在一个项目中，如果没有typedef重命名，要改变数据类型的话，就得一个一个去改，这就很麻烦了。有了typedef，要改的话直接把那里的 int 改了就ok。

然后解释下size和capacity：size是当前顺序表存储的数据个数；而capacity是指数组的容量，即它能装多少，capacity的作用主要是在向顺序表插入元素时判断是否有空间可插入。
了解它长啥样之后，接下来要来对它进行相应的操作。

---

🍉操作顺序表

🍌初始化

建立一个数据表后，它里面的data，size和capacity都是随机值（因为未初始化），所以写个初始化函数。

void SLInit(SL* ps) {
	ps->arr = NULL;   //一开始arr里面没东西，所以把它置为空
	ps->size = ps->capacity = 0;
}
1
2
3
4

注意：此处的SL就是上面顺序表结构类型的简写（是我为了后面方便写代码才用typedef重命名的，你在下面看到的话要知道是啥）

🍌销毁

在使用完之后就要销毁咯，销毁函数和初始化长得差不多。

void SLDestroy(SL* ps) {
	if (ps->arr){
		free(ps);   //释放申请的那块空间
		ps = NULL;  //记得释放后把指针置为空，养成好习惯
	}
	ps->size = ps->capacity = 0;
}
1
2
3
4
5
6
7

🍌打印

如果我们要看顺序表里面有啥，那就要把它给打印出来。
打印其实也就是打印里面那个数组，一个简单的循环遍历就ok。

void SLPrint(SL* ps) {
	for (size_t i = 0; i < ps->size; i++) {
		printf("%d", ps->arr[i]);
	}
}
1
2
3
4
5

🍌插入

现在要往那个数组里面插入东西了。

🥝检查容量

插入之前，得先检查下空间够不够，如果不够就要用realloc扩容了。哦那怎么判断空间是否足够？那就要用到size和capacity呗，只要 size 刚好等于 capacity ，那就说明空间满了，要扩容
这里的插入方式是一次插入一个，因为每次插入前都判断一下，所以临界条件是size等于capacity，如果要插入多个数据的话，那就来个循环。（你往下看就知道了）
然后扩容要扩多少，这也是个问题，扩太少的话就频繁扩容，这个代码稳定性就会有所降低；扩太多的话你如果不用那就造成空间浪费了。前人经过统计得出：新容积为以前容积的1.5倍到2倍这个区间的时候，相对而言既可以节省空间，又可以减少扩容的机会。以下我选择扩容两倍。
所以接下来先写一个检查容量的函数

void SLCheckCapacity(SL* ps, int capacity) {
	if (ps->size == ps->capacity) {
		//newcapacity就是扩容后的容积
		int newcapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;  //上面那个初始化函数将capacity置为0，所以这里的意思就是：首次插入就先给capacity和newcapacity一个固定的大小
		SLDateType* tmp = (SLDateType*)realloc(ps, sizeof(SLDateType) * newcapacity);
		if (tmp == NULL) {
			perror("realloc fail!\n");
			return 1;
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13

Q：为啥要用tmp？
A：因为realloc扩容失败的话会返回空指针，你传进来的是数组的地址，直接接收空指针的话那数组直接寄了，再也找不到它了。所以这里先弄个tmp接收一下，确保扩容成功了才给arr。

🥝从最前面插入

既然要放一个元素进去，那数组中原有的元素就要给它让位了，所以其他元素往后退。

void SLPushFront(SL * ps, SLDateType a) {
	//空间不够就realloc扩容
	if (ps->size == ps->capacity)
	{
		SLDateType* ps1 = (SLDateType)realloc(ps->arr, sizeof(SLDateType) * 2 * ps->capacity);
		//把元素往后挪
		for (int i = ps->size; i > 0; i--) {
			ps1[i] = ps1[i - 1];
		}
		ps1[0] = a;
		ps->size++;   //size一定要记得++
	}
		//空间足够直接加
	else if (ps->size < ps->capacity) {
		for (int i = ps->size; i > 0; i--) {
			ps->arr[i] = ps->arr[i - 1];
		}
		ps->arr[0] = a;
		ps->size++;
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🥝从最后面插入

这个比从最前面插入的要简单，因为直接放下去就可以了。

void SLPushBack(SL* ps, SLDateType a){
	//空间不够  realloc扩容
	if (ps->size == ps->capacity) {
		SLDateType* ps1 = (SLDateType)realloc(ps->arr, sizeof(SLDateType) * 2 * ps->capacity);		
		ps1[ps->size++] = a;
	}
	else if (ps->size < ps->capacity) {
		ps->arr[ps->size++] = a;
	}
}

1
2
3
4
5
6
7
8
9
10
11

🥝指定位置插入

思路：插入位置处的元素及之后的元素要往后挪，给待插入元素让出位置

void SLInsert(SL* ps, int pos,SLDateType a) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = ps->size-1; i > pos-1 ; i--) {
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = a;
	
}

1
2
3
4
5
6
7
8
9
10

---

🍌删除

删除一个元素，同样有前置工作一一判断顺序表是否为空，如果是空的话那压根删不了。

bool SLIsEmpty(SL* ps) {
	assert(ps);
	return ps->size == 0;
}
1
2
3
4

🥝删除最前面元素

这个直接把后面的元素往前挪，第二个元素会把最前面的元素给覆盖掉，其实这样就实现删除的效果了。

void SLPopFront(SL* ps) {
	assert(ps);
	assert(!SLIsEmpty(ps));
	//其他元素得往前移
	for (int i = 0; i < ps->size-1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

1
2
3
4
5
6
7
8
9
10

🥝删除最后面元素

这个最简单，直接size- -就ok了，你可能会说：“啊？这样就可以了？”因为size- -之后原先数组中第size个元素就不在数组之中了，后续各种操作都和它无关了，你如果确实过意不去的话，就把它置为0。

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

1
2
3
4
5
6

🥝指定位置前删除

仿照上面的思路，比如要删除第pos个元素，那就让它后面的元素往前覆盖，然后size–。

void SLErace(SL* ps, int pos) {
	assert(pos >= 0 && pos < ps->size);
	if (!SLIsEmpty) {
		for (int i = pos; i < size - 1; i++) {
			ps->arr[i] = ps->arr[i + 1];
		}
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9

注意：删除前得判断pos的范围是否合理，显然pos取值范围为0到size-1

---

🍌查找元素

有时候我们需要查找某元素是否在顺序表之中。
思路：遍历数组，如果找到了就返回true，反之false。

bool SLFind(SL* ps, SLDateType a) {
	for (int i = 0; i < ps->size; i++) {
		if (ps->arr[i] == a)
			return true;
	}
	return false;
}

1
2
3
4
5
6
7
8

---

🍌修改元素

要修改元素就得先找到这个元素的下标，这里就可以把上面那个查找元素的函数改一下，找到了就返回下标，然后再根据下标进行修改。

void SLModify(SL* ps, SLDateType a,SLDateType b) {
	int flag = 0;
	for (int i = 0; i < ps->size; i++) {
		if (ps->arr[i] == a) {
			arr[i] = b;
			flag = 1;
		}
	}
	if (flag == 0) {
		printf("查找失败，无法修改\n");
	}
	else {
		printf("修改成功\n");
		SLPrint(ps);  //修改之后顺带打印出来看一下
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16