顺序表和链表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的
数据结构,常见的线性表：顺序表,链表,栈,队列,字符串...，线性表是一种具有相同特性的数据的集合。
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念于结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表再逻辑结构上是线性的,再物理结构上也是线性的,因为它的底层是数组。

顺序表和数组的区别?

顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口。

2.2 分类

顺序表是对数组进行封装,所以我们就要使用结构体。

2.2.1 静态顺序表

静态顺序表缺陷:空间给少了不够用,给多了造成空间浪费

2.2.2 动态顺序表

2.3 动态顺序表的实现

2.3.1 动态顺序表的初始化

//顺序表的初始化
void SLInit(SL* ps)
{
	//初始化顺序表的指针置为空
	ps->arr = NULL;
	//有效元素的个数和空间大小都为0
	ps->capacity = ps->size = 0;
}

问题1:

这张图片的问题就在于初始化的时候是传值调用,此时我们的s都没有初始化,因此传值调用的时候会报错,未初始化的变量s,其次传值调用形参的改变不会影响实参,所以要想影响我们的s,就必须传s的地址,这样初始化方法才有用,循序表的头文件中的函数定义也需要修改。

总结:函数传参,传值调用的时候,形参是实参的一份临时拷贝,指向的是两块不同的地址,但保存的诗句是一样的,改变形参并不影响实参,所以我们以后在函数传参的时候,要想形参影响实参的话,就必须传地址。

2.3.2 动态顺序表的销毁

代码:

//顺序表的销毁
//因为顺序表是动态内存开辟的,所以我们代码结束的时候要销毁
void SLDestroy(SL* ps)
{
	//判断顺序表底层数数组是否为空
	if (ps->arr)//ps->arr != NULL
	{
		//不为空就将底层数组释放
		free(ps->arr);
		//将底层数组置为空,否则会变为野指针
		ps->arr = NULL;
	}
	//有效元素的个数和内存的大小都置为0
	ps->capacity = ps->size = 0;
}

动态顺序表是我们用free来申请扩容的空间,虽然我们不释放,代码结束操作系统也会释放,但是如果代码很多,这块空间不用了,但是代码又不结束,还是需要手动释放,否则长此以往,会浪费很多空间,直到空间耗尽。

2.3.2 动态顺序表的尾插

//扩容
void SLCheckCapacity(SL* ps)
{
	//如果有效元素个数和空间一样大,则说明需要申请空间
	if (ps->capacity == ps->size)
	{
		//这里就是需要增容多大的空间
		/*
		因为我们的ps->capacity初始化是0,所以不能直接传参ps->capacity*sizeof(SL)
		这样算出的结果还是0,所以我们要用三目表达式来判断一下ps->capacity是否为0
		如果为0newCapacity就是4,否则就是以2倍扩容
		*/
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//需要增容,所以要用realloc
		/*
		这里需要创建临时变量来接收realloc返回的值,因为realloc申请失败会返回NULL
		一旦我们用ps->arr指针来接收,并且realloc返回空指针,那么原来的地址野找不到了
	  realloc给空地址扩容也是可以的,旧相当于申请空间,所以就算ps->arr是空指针,也是
	  可以进行扩容的 - 注意realloc的传参
		*/
		SLDataType* newArr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		//判断realloc的返回值
		if (newArr == NULL)
		{
			//打印申请失败的原因
			perror("malloc fail!");
			//退出
			exit(1);
		}
		//将扩容后的地址赋值给顺序表
		ps->arr = newArr;
		//将空间大小赋值给顺序表的capacity成员
		ps->capacity = newCapacity;
	}
}


//尾部插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	//不能传空指针 - 表达式为真继续往下执行,表达式为假,报错
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//插入
	*(ps->arr + ps->size++) = x;
    //上面代码拆解得到下面代码
	/*
	*(ps->arr + ps->size) = x;
	ps->size++;
	*/
}

常见问题:

1.扩容问题

2.realloc的传参

realloc传参最后一个参事的单位是字节,所以我们确定好申请的空间个数还要乘数据类型的大小。

动态内存管理-CSDN博客文章浏览阅读672次，点赞7次，收藏27次。在学校计算机语言的时候是这样讨论的,学习操作系统的时候会变。C/C++程序内存分配的几个区域:1. 栈区(stack):在执⾏函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限, 栈区主要存放运行函数而分配的局部变量,函数参数,返回数据,返回地址等。《函数栈帧的创建和销毁》2. 堆区(heap):⼀般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。分配方式类似于链表。https://blog.csdn.net/m0_74271757/article/details/140023654?spm=1001.2014.3001.5502详细可以看动态内存管理的3.2 realloc的使用方法。

3.对空指针解引用的问题

从调试可以看出代码如果传NULL,该函数会出问题,因为不能对空指针进行解引用操作。所以我们要对空指针做处理或者直接加上断言。

调试结果:

我们的头插也是需要判断空间是否足够的,所以我们再尾插写的判断空间是否足够的代码可以封装成一个函数。

2.3.3 动态顺序表的打印

代码:

//打印顺序表
//可以传地址也可以不传地址,因为只是遍历顺序表,不需要修改实参。
void SLPrint(SL* ps)
{
	//遍历顺序表
	for (int i = 0; i < ps->size; i++)
	{
		//打印
		printf("%d ", *(ps->arr+i));
	}
	//最后来个换行,好看
	printf("\n");
}

为了方便我们查看顺序表我们可以写一个顺序表的打印方法,这样就不通过调试看结果了。

2.3.4 动态顺序表的头插

代码:

//头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	//不能传空指针
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//插入 - 整体往后移动
	for (int i = ps->size; i > 0; i--)
	{
		*(ps->arr + i) = *(ps->arr + i - 1);//*(ps->arr+1) = *(ps->arr+0)
		//ps->arr[i] = ps->arr[i - 1];
	}
	//在第一个位置插入要插入的值
	*ps->arr = x;
	//有效元素个数自增
	ps->size++;
}

输出结果:

2.3.5 动态顺序表的尾删

代码:

//尾部删除数据
void SLPopBack(SL* ps)
{
	//传空指针以及顺序表为空是不能执行删除操作的
	assert(ps && ps->size);
	ps->size--;
}

输出结果:

顺序表为空不能进行删除操作,因为代码中加了assert断言。

2.3.6 动态顺序表的头删

代码:

//头部删除数据
void SLPopFront(SL* ps)
{
	//传空指针以及顺序表为空是不能执行删除操作的
	assert(ps && ps->size);
	//数据整体往前移动
	for (int i = 0; i < ps->size-1; i++)
	{
		*(ps->arr + i) = *(ps->arr + i + 1);
	}
    //有效元素个数自减
	ps->size--;
}

输出结果:

2.3.7 顺序表指定位置插入

代码:

//指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	//不能传空指针以及pos的有效范围
	assert(ps && pos >= 0 && pos <= ps->size);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//pos以及pos之后的位置整体往后挪动
	for (int i = ps->size; i > pos; i--)
	{
		*(ps->arr + i) = *(ps->arr + i - 1);
	}
	//顺序表的pos位置赋值为要插入的值
	*(ps->arr + pos) = x;
	//元素的有效个数自增
	ps->size++;
}

输出结果:

2.3.8 顺序表指定位置删除

代码:

//指定位置删除数据
void SLErase(SL* ps, int pos)
{
	//不能传空指针以及删除的范围必须有效
	assert(ps && pos >= 0 && pos < ps->size);
	//pos以后的数据整体往前挪动一位
	for (int i = pos; i < ps->size-1; i++)
	{
		*(ps->arr + i) = *(ps->arr + i + 1);//*(ps->arr + pos) 
	}
	//有效元素个数自减
	ps->size--;
}

思路:

输出结果:

2.3.9 顺序表的查找

代码:

//查找顺序表中的数据
int SLFind(SL* ps, SLDataType x)
{
	//不能传空指针以及顺序表为空不能查找
	assert(ps && ps->size);
	//遍历顺序表
	for (int i = 0; i < ps->size; i++)
	{
		if (*(ps->arr + i) == x)
		{
			return i;
		}
	}
	return -1;
}

思路很简单,遍历顺序表,如果有要找的值就返回下标,否则返回-1,因为下标没有负数。

输出结果: