数据结构——线性表之顺序表的基本操作讲解

目录

目录

一线性表

1.线性表定义        

2.常见的线性表：

 3.线性表存储结构       

二.顺序表

1.定义：

2.分类：

3.顺序表的初始化

4.顺序表的释放

5.顺序表的数据添加

6.数据的删除

 头部删除：

7.数据的查找——返回该数字的下标位置

 8.在指定位置插入数据

 9.在指定位置删除数据

10.数据的修改：

test.c测试文件代码：

SeqList.c文件代码：

SeqList.h代码：

---

---

一线性表

1.线性表定义        

        线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

2.常见的线性表：

顺序表、链表、栈、队列、字符串等

 3.线性表存储结构       

        线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 

 如图，上述两个就是线性表中两个重要的分类：顺序表和链表。而今天我要说的就是顺序表。

---

二.顺序表

1.定义：

        用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。而顺序表就是在数组上完成数据的增删查改等步骤。

2.分类：

顺序表分为静态顺序表和动态顺序表两类：

        A.静态的顺序表：大小固定，只适用于知道要存多少个数据，所以采用使用定长数组进行存储；

 
#define N 10
 
typedef int SLDataType;//类型重定义
 
struct SeqList {
	//int a[N];
	SLDataType a[N];
	int size;//存储数据的个数
};

 注：使用静态顺序并不方便，假如开1000个空间，只用到100个，那么剩下的990个空间被浪费；

        开1000个空间时，要存储1001个数据，会出现不够的情况，所以静态顺序表的使用总是达不到令人满意的结果。

---

        

        B.动态顺序表：使用动态开辟的数组进行存储，数组的大小随着数据的增加而增加，不会造成浪费，基本上都是有多少用多少；程序的灵活性更高；也不会出现分配不足的问题。

//动态顺序表的创建——malloc、calloc，realloc等动态开辟的空间
 
typedef int SLDataType;//类型重定义
 
typedef struct SeqList {
	SLDataType* a;//指针
 
	int size;//当前存储的个数
 
	int capacity;//整体容量的大小
 
    }SL;//将动态顺序表的结构体类型简写化为SL

        动态开辟需要用到三个成员：1是指针用于指向动态开辟的堆区空间；2.是当前数组中存储的数据个数；3.是当前数组的最大容量。动态开辟最大的特点是能随时扩容，当存储数据的个数达到数组的最大容量时，表示数组已经满了，这时就可以自动扩容，为下一个数据的存储增加空间！十分方便， 所以一般在数据结构中我们常使用动态顺序表。 

 

3.顺序表的初始化

        创建好顺序表的模型后，接下来我来讲一讲顺序表的初始化

        顺序表的初始化就是对刚刚创建好的结构体SL中的成员做数据分配：

在Test.c（这个.c文件主要用于进行测试）中：创建结构体变量s，通过取出变量s的地址作为实参去关联函数形参。

void TestSLInit() {
	SL s;
	SLInit(&s);//初始化
}
 
 
int main(){
 
    TestSLInit();
    return 0;
}

在SeqList.c（这个.c文件主要用于进行函数的实现）中 ：

//初始化函数
void SLInit(SL* psl) {
	assert(psl);//断言库函数（判断指针psl是否为空）
	psl-> size = 0;
	psl-> capacity = 0;
	psl->a = NULL;
}

        注： 在主函数中使用了传址调用，学习C语言的时候，大家都知道传值调用的过程中，形参只是实参的一份临时拷贝，形参的改变不能影响实参。实参是结构体的变量，代表着顺序表，想要对其进行数据的增删改查扽操作，需要传地址才能改变顺序表。

        注2：在初始化中，数据的个数与容量都设为0，而指针a先置为空指针，在之后的增加数据时会改变。

4.顺序表的释放

既然是动态开辟的数组，那么程序结束时就需要手动释放这块内存空间，否则会造成内存泄漏。

        free后，这块空间被交还给操作系统，但指针仍保留着这块空间的地址，因此指针a会变成野指针，很危险，需要手动置为空，此外size和capacity也得重新置为0 。

5.顺序表的数据添加

        创建好顺序表的开始与结束函数后，接下来就要对顺序表进行数据的添加了.

        需要注意的是数据的添加分为头部添加、尾部添加。一般常使用尾部添加方式。

        在数据的添加过程中，需要去检查数组（顺序表），看其容量是否能够允许数据被添加进来！因此我创建了一个独立函数去检查，而检查的条件就是当前存储的个数是否等于容量的上限。若是等于，则还需要看容量是否为0，若为0，则表明是第一次开辟空间；若不为0，则表明是容量满了需要扩容，针对这两种情况，我使用三目操作表达式去编写代码。

// 检查空间，如果满了，进行增容
static void CheckCapacity(SL* psl) {
	//1.检查
	if (psl->size == psl->capacity) {
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc filed\n");
			return -1;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}
}
 

        扩容的时候可以使用malloc、calloc、realloc等3种库函数去开辟，我使用的是realloc既可以开辟空间，又可以做扩容操作。

        一个重大结论：动态开辟是系统根据堆区内存空间的空闲位置去开辟的，就是说堆区中哪块空间空闲，就会在那个位置存放，基于此扩容 操作会有三种情况：

         原地扩容的好处就是扩展内存就直接原有内存之后直接追加空间，原来空间的数据不发生变化。

---

        异地扩容：也就是第一次开辟空间的后面无法再继续扩容，那么系统会自动寻找另一块能够放下扩容后的新地址，那么原有的空间会被系统回收 。

---

扩容失败表示堆区空间已满，无法继续为其增加空间。 

---

尾部插入代码：

SLPushBack函数的作用就是，在数组的尾部插入一个个数据，每添加一个数据，就使存储个数+1。

调试结果：

---

 头部插入代码：

 头部添加的关键在于：需要将所有数据往后挪一个单位，为数组首元素留下一个空位，并且使指针指向首元素位置添加数据。

调试结果：

---

6.数据的删除

分为头部删除、尾部删除。一般常使用尾部删除方式。

尾部删除：

 调试结果：

 

 尾部的删除相当简单，令size-1即可。

---

 头部删除：

结果对比： 

 

---

7.数据的查找——返回该数字的下标位置

代码：

         在查找函数中，我使用了顺序查找的方式，将数组从下标0到最后依次遍历。大家可能会问，顺序遍历的时间复杂度为O(N)，用二分查找会不会更好？二分查找算法的时间复杂度虽然是O(log2(N))，比O(N）更好，但使用二分查找的前提是该数列为有序数组，而排序的复杂度就很高了，代价大，所以还是老实用顺序遍历好。

         之前顺序表中剩余的元素为30,1,2,3 ，查找的数字为30，则系统会在顺序表中寻找该数字，并返回该数字的下标位置，若是没找到则返回-1。

---

 8.在指定位置插入数据

 SLInsert函数的作用：通过在数组下标位置pos前插入元素x。在右图中第一个语句表示在数组的下标位置2前插入数据999；第二个语句表示在数组下标位置0前插入数据666。

该函数的实现原理：

调试结果：

---

 9.在指定位置删除数据

调试结果：

 函数实现原理：在数组中，使指针指向pos位置处，使用循环，从前往后将 后一个值赋给前一个值。从而将begin指向的数据值被后一个数据值所覆盖，完成删除。

---

10.数据的修改：

以上就是对顺序表增删查改的基本步骤了，接下来我会发出所有代码：

test.c测试文件代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
 
void TestSLInit() {
	SL s;
	SLInit(&s);//初始化
 
	//尾部插入
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
 
	//头部插入
	SLPushFront(&s, 30);
	SLPushFront(&s, 20);
	SLPushFront(&s, 10);
 
	//尾部删除
	SLPopBack(&s);//删除数组最后一个元素
	SLPopBack(&s);//删除数组最后一个元素
	SLPopBack(&s);//删除数组最后一个元素
 
 
	//头部删除
	SLPopFront(&s);//删除数组首元素
	SLPopFront(&s);
 
	//查找
	/*int ret = SearchSL(&s, 30);
	printf("%d\n", ret);*/
 
	//在指定位置插入数据
	SLInsert(&s, 2, 999);
	SLInsert(&s, 0, 666);
 
 
	
	SLprint(&s);
 
 
	SLDestory(&s);//释放动态空间你重置
}
 
void TestSLInit2() {
	SL s2;
	SLInit(&s2);//初始化
	//尾部插入
	SLPushBack(&s2, 1);
	SLPushBack(&s2, 2);
	SLPushBack(&s2, 3);
	SLPushFront(&s2, 999);
 
	//在指定位置删除数据
	 SLprint(&s2);
	SLErase(&s2, 0);
	SLprint(&s2);
 
	SLDestory(&s2);
 
	//可以自己输入想要删除的下标位置代码
	/*int x = 0;
	scanf("%d", &x);
	int pos = SearchSL(&s2, x);
	if (pos != -1) {
		SLErase(&s2, pos);
	}*/
	SLprint(&s2);
}
 
int main() {
 
    //TestSLInit();
	TestSLInit2();
 
	return 0;
}

SeqList.c文件代码：

#include"SeqList.h"
 
 
//初始化函数
void SLInit(SL* psl) {
	assert(psl);
	psl-> size = 0;
	psl-> capacity = 0;
	psl->a = NULL;
}
 
//销毁动态内存
void SLDestory(SL* psl) {
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = psl->capacity = 0;
}
 
 
// 检查空间，如果满了，进行增容
 void CheckCapacity(SL* psl) {
	 assert(psl);
	//1.检查
	if (psl->size == psl->capacity) {
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc filed\n");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}
}
 
 
//尾部插入
void SLPushBack(SL* psl, SLDataType x) {
	assert(psl);
 
	//1.检查
	CheckCapacity(psl);
 
	//2.在尾部插入数据
	psl->a[psl->size] = x;
	psl->size++;
}
 
void SLprint(SL* psl) {
	int i = 0;
	for (i = 0; i size; i++) {
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
 
 
//头插
void SLPushFront(SL* psl, SLDataType x) {
	assert(psl);
 
	//1.检查
	CheckCapacity(psl);
 
	//2.将所有数据往后挪，以便在头部插入数据
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];//所有位置往后挪
		end--;
	}
 
	//3.插入数据
	psl->a[0] = x;
	psl->size++;
}
 
 
//尾部删除
void SLPopBack(SL* psl) {
	assert(psl);
	//温柔的检查
	if (psl->size == 0) {
		return;
	}
	//暴力的检查
	//assert(psl->size > 0);//选择其中一种即可
 
	psl->size--;
}
 
//头部删除
void SLPopFront(SL* psl) {
	assert(psl);
	//温柔的检查
	if (psl->size == 0) {
		return;
	}
	//暴力的检查
	//assert(psl->size > 0);//选择其中一种即可
 
	//从前往后(第二个元素的值赋值给第一个元素，第三个元素的
	//值赋给第二个，以此类推，直到begin<(psl->Size-1)停止
	int begin = 0;
	while (beginsize-1) {//size是指向数组最后一个位置的
							   //下一个位置，所以-1（可以理解为数组下标）
		psl->a[begin] =psl->a[begin+1];
		begin++;
	}
	psl->size--;
}
 
 
//查找——返回的是该数的下标位置
int SearchSL(SL* psl, SLDataType x) {
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++) {
		if (psl->a[i] == x) {
			return i;
		}
	}
	return -1;
}
 
 
//指定某一个数组下标位置进行插入数据
void SLInsert(SL* psl, int pos, SLDataType x) {
	assert(psl);
	assert(pos <= psl->size);
	int end = psl->size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}
 
 
//指定某一个数组下标位置删除数据
void SLErase(SL* psl, size_t pos) {
	assert(psl);
	assert(pos < psl->size);
 
	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
}

SeqList.h代码：

#pragma once
 
#include
#include
#include
 
//静态顺序表的创建——数组（定长数组）大小写死了，只适用于直到要存多少个数据采用
//#define N 10
//typedef int SLDataType;//类型重定义，因为int类型写死了，可以重定义int类型
//struct SeqList {
//	//int a[N];
//	SLDataType a[N];
//	int size;//存储数据的个数
//};
 
 
 
//一般写顺序表都是写动态版本的，静态版本的不怎么用！！！
//动态顺序表的创建——malloc、calloc，realloc等动态开辟的空间
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* a;
	int size;//当前存储的个数
	int capacity;//整体容量的大小
}SL;//将动态顺序表的结构体类型简写化为SL
 
//初始化函数
void SLInit(SL* psl);
//释放空间
void SLDestory(SL* psl);
 
//尾部插入——一般用法
void SLPushBack(SL* psl, SLDataType x);
 
//打印
void SLprint(SL* psl);
 
//头部插入
void SLPushFront(SL* psl, SLDataType x);
 
//尾部删除
void SLPopBack(SL* psl);
 
//头部删除
void SLPopFront(SL* psl);
 
//查找
int SearchSL(SL* psl, SLDataType x);
 
//指定某一个数组下标位置进行插入数据
void SLInsert(SL* psl, int pos, SLDataType x);
 
指定某一个数组下标位置删除数据
void SLErase(SL* psl, size_t pos);