【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

0.前言

什么是数据结构？

1.逻辑结构:

1.1线性结构:

1.2非线性结构:

(1)集合

(2)树形结构

(3)图形结构或者网状结构

2.存储结构

一.线性表

二.顺序表

顺序表与数组的关系:(非常容易混淆)

1.静态顺序表：使用定长数组存储元素

2.动态顺序表：使用动态开辟的数组存储

接口实现

1️⃣ 初始化:SLInit

2️⃣销毁：SLDestroy

3️⃣检查容量:SLCheckCapacity

4️⃣顺序表打印:SLPrint

5️⃣尾部插入:SLPushBack

6️⃣头部插入:SLPushFront

7️⃣尾部删除:SLPopBack

8️⃣头部删除:SLPopFront

9️⃣中间插入:SLInsert

🔟中间删除:SLErase

1️⃣1️⃣查找:SLFind

1️⃣2️⃣修改:SLModify

三.整体实现代码

SeqLish.h

SeqList.c

Test.c

0.前言

本篇文章包含了不少的代码测试情况,以及经过调试之后如何找出bug的情况,也悉数列举。本篇文章虽然没有菜单,是1.0版本,日后本菜鸟的代码能力提高之后会逐步完善。但是此文章经过了本人的详细思考,以及理解情况，也可以给大佬们和朋友们列举一些反例,也希望大家可以从中吸取经验,最后希望大佬们如果乐意的话可以考虑给我留下个免费的赞,您的支持是我创作的最大动力,感谢!

在讲解这一章开始时，我先说明一下什么是数据结构。

什么是数据结构？

数据结构 (Data Structure) 是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的

数据元素的集合。

数据结构是由三部分进行组成，分别是:逻辑结构、存储结构和数据的运算

1.逻辑结构:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

这里的一般线性表就是顺序表的意思。

1.1线性结构:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

1.2非线性结构:

(1)集合

集合中的数据元素除了同属一个集合外，其它是没有关系的。

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

(2)树形结构

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

(3)图形结构或者网状结构

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

2.存储结构

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

一.线性表

线性表（ linear list ）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串 ...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

二.顺序表

概念及结构

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

储。在数组上完成数据的增删查改。

顺序表与数组的关系:(非常容易混淆)

这块我简单提一下顺序表和数组的关系:

对于数组而言:

数组的元素是可以随机存放的,因为：数组通过下标访问是可以任意存储的

可以看到值已经放进去了

对于顺序表而言:

顺序表是要连续存放的是,这个连续存放,不是指的是值连续,而是空间连续(意思是你存放的时候，不能跳着存，必须从0下标开始，依次向后存放)

简单地讲:

顺序表不能随意存储,顺序表必须从0下标开始,依次向后存放,意思就是他是顺序存储的,不会出现空一个位置的情况。

顺序表一般可以分为：动态和静态顺序表,

动态顺序表:也是基于数组实现的，只不过它可以实现扩容，而数组是固定长度大小的

1.静态顺序表：使用定长数组存储元素

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

定义静态顺序表:

#define N 10
typedef int SLDatatype;//这个地方可以避免写死类型是int,以后想换就换
struct SeqList
{
	SLDatatype a[N];//为了避免写死数组大小,需要改的时候到处改,那就使用宏定义
	int size;
};

静态顺序表的缺点:

如果存满了还想存入数据,那就不能继续存储了,因为空间是固定的

#define N 10

N-->改成10000,如果这个地方要存储10001,那还是不够存储,如果存不满10000个空间,那会浪费空间

总体来说:给小了不够用，给多了浪费

因此：

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N定大了，空

间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间

大小，所以下面我们实现动态顺序表。

2.动态顺序表：使用动态开辟的数组存储

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

定义动态顺序表

//动态顺序表
typedef int SLDatatype;//这个位置换成double会导致问题,可能会导致全元素都是0
typedef struct SeqList
{
	SLDatatype* a;//指向动态开辟的数组
	int size;	 //存储的有效数据的个数
	int capacity;//容量空间的大小
}SL;//类型名重定义

接口实现

1️⃣ 初始化:SLInit

void SLInit(SL* psl);//动态顺序表初始化

错误的初始化:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举) 正确的初始化:

void SLInit(SL* psl)
{  
    //malloc扩容因为malloc类型是->void* malloc (size_t size);所以需要强制转换
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开4个比较合适
	//开辟失败会返回NULL,并打印错误信息
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->capacity = 4;//使用结构体指针指向访问对象的成员,当前容量
	psl->size = 0;//当前有效信息个数
}

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

2️⃣销毁：SLDestroy

SLDestroy(SL* psl);//顺序表销毁

void SLDestroy(SL* psl)//销毁不是整没了，而是还给操作系统了
{
	free(psl->a);//这里不free的话会产生野指针
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

3️⃣检查容量:SLCheckCapacity

说明一下:

realloc是新增到多少空间,比如说我本来是20个int的空间，(int*)realloc(arr,40),这是把空间整体扩到40个int,不是说增了多少，后面这个40的位置是整体的大小,而不是20+40=60。

这个realloc的知识点可以看这篇文章，比较详细地展开说明:http://t.csdn.cn/H3I26

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)//有效信息的个数等于当前容量
	{
		SLDatatype* tmp =(SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL)//申请空间过大可能会申请失败
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;//原地扩容用的是原来的地址，异地扩容用的是新的
		psl->capacity *= 2;//当前容量*2
	}
}

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

(SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);

这个地方扩2倍是比较合适的。

4️⃣顺序表打印:SLPrint

void SLPrint(SL*psl);//顺序表打印

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

打印顺序表的每个元素

5️⃣尾部插入:SLPushBack

void SLPushBack(SL* psl, SLDatatype x); //顺序表尾插

void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);	
	SLCheckCapacity(psl);//容量初始值为4,检查当前容量,不够则扩容
	psl->a[psl->size++] = x;

}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

调用测试尾部插入的代码:

void TestSeqList1()
{
	SL s;
	SLInit(&s);
	
	SLPushBack(&s, 1);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushFront(&s,5);
	
	SLPrint(&s);

	SLDestroy(&s);
}

执行:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

6️⃣头部插入:SLPushFront

void SLPushFront(SL* psl, SLDatatype x);//头部插入

这里要说明一下头插之后的原有数组的元素的移动情况:从后往前挪动

从后往前的意思:是从数组原本有的元素开始，从最后一个元素开始往后面的空间移动，这样整体看来，对于数组原有元素来说，相对位置上确实是后面元素先挪动到后面，前面元素紧跟着后面元素的步伐

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题
	SLCheckCapacity(psl);

	//挪动数据
	int end = psl->size-1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}

代码可以看这个图解:

顺序表无元素:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

这个图是头插第一个元素(顺序表无元素时候)end数组下标的位置,先把a[0]赋值，然后size此时为0++,有效元素个数+1

顺序表有元素:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

这图是先从数组最后一个元素(也就是6)开始挪动，先把元素6往后面的空间挪动，不够了再扩容，然后7把6覆盖，以此类推，接着，看x此时输入(1)的是什么元素，再把a[0]赋值，达到头插的效果

调用头部插入的测试代码:

void TestSeqList2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPrint(&s);

	SLDestroy(&s);
}

执行：

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

7️⃣尾部删除:SLPopBack

void SLPopBack(SL* psl);//尾删

一开始的思路就是把顺序表最后一个元素变为0或者-1

void SLPopBack(SL* psl)
{

psl->a[psl->size - 1] = 0;这句话不好，为什么？
psl->size--;

}

原因有两个：

1. 要是这个位置本来就是0，或者-1，那就没有意义了。

所以这时候，我们直接改成这样,干脆利落:
void SLPopBack(SL* psl)
{
    
    psl->size--;

}
这样就不会引起其它问题了吗?然后并不是。

这是关于测试尾部删除的越界问题,以及打印值问题的测试代码

void TestSeqList3()//测试尾部删除的越界问题,以及打印值问题
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);//插入
	SLPushBack(&s, 2);//插入
	SLPushBack(&s, 3);//插入
	SLPushBack(&s, 4);//插入
	SLPushFront(&s, 5);//头插入
	SLPushFront(&s, 6);//头插入
	SLPrint(&s);//整体呈现出来应该是 6 5 1 2 3 4

	SLPopBack(&s);//尾删除
	SLPopBack(&s);//尾删除
	SLPrint(&s);//整体呈现出来应该是 6 5 1 2 

	SLPopBack(&s);//尾删除
	SLPopBack(&s);//尾删除
	SLPrint(&s);//整体呈现出来应该是 6 5 

	SLPopBack(&s);//尾删除
	SLPopBack(&s);//尾删除
	SLPopBack(&s);//尾删除-->此时顺序表已经没有元素了还要删一个
	SLPrint(&s);//这时候size有效信息个数还"欠"一个

	SLPushBack(&s, 1);//所以这个是被吃掉了~!
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//整体呈现 2 3 4

	SLDestroy(&s);
}

执行:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

调试一下寻找原因:

先大概率猜测没有问题,所以可以直接跳过打断点的过程

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

猜测一下，这个问题应该是删除产生的, 直接把断点打到尾删这个位置，这时候可以看到size=6，因为插入了6 5 1 2 3 4，中间扩了一次容,所以容量psl->capacity *= 2 -->为8，扩容得刚好是8

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

再按F10一步一步跳过函数的内容,接着发现了size--到了-1。因为有6个数据已经删除了6次，第7次删除至少不要把size搞成-1

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

那我们应该如何处理那个函数,使得它在即将删除元素越界的时候程序可以正常运行呢?

温柔的检查:

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	//温柔检查
	if (psl->size == 0)
	{
		printf("顺序表为空,删除失败\n");
		return;//不报错任何问题,直接回答主函数。
	}
		
	psl->size--;

}

如果这个printf信息不写,那将不会返回这个信息,直接返回主函数【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

暴力检查(推荐):

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);

	//暴力检查
	assert(psl->size > 0);

	psl->size--;

}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

关于free报错的原因:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

一般情况是内存越界了:申请的空间不够大，但是通过数组等方式遍历到并访问不是动态开辟的空间。还有就是看看指针有没有错，以图上的（psl->a）为例子,释放的那个指针是不是指向动态内存开辟的空间,除此之外有没有指向错误。

要是头文件处,变为typedef double SLDatatype;

那要写成psl->a[psl->size - 1] = 0.0;吗？

以下是可能会引发的问题:

所以删除的意思不是把顺序表最后一个元素抹成0或1就行了。

8️⃣头部删除:SLPopFront

void SLPopFront(SL* psl, SLDatatype x);//顺序表头插

把顺序表第一个元素删除掉,接着从顺序表第二个元素开始往前移动(第2个挪动到第1个,第3个移动到第2个，以此类推)。

void SLPopFront(SL* psl)//从后往前
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	//暴力检查
	assert(psl->size > 0);
	//温柔检查
	if (psl->size == 0)
		return;
	/*int start = 0;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}*/
	/*int start = 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}*/
	psl->size--;

}

写法1:start从0下标开始,start<psl->size-1

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

写法2:start从1下标开始,start<psl->size 【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

开一组测试看看效果:

void TestSeqList4()//头部删除越界
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

    //以下再删除就会越界
	//SLPopFront(&s);
	//SLPopFront(&s);
	//SLPrint(&s);

	SLDestroy(&s);
}

执行:最下面一行打印是因为assert。

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

9️⃣中间插入:SLInsert

void SLInsert(SL* psl, int pos, SLDatatype x);

//中间插入:首先要看容量，调用检查容量的函数,接着挪动
void SLInsert(SL* psl,int pos,SLDatatype x)
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	//assert(0 <= pos && pos <= psl->size);//说明这个位置可以是顺序表的头和尾

	SLCheckCapacity(psl);

	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

假设没有assert断言pos的范围,开一组测试看看效果:记住越界是不一定报错的!

void TestSeqList5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	SLInsert(&s, 2, 30);
	SLPrint(&s);

	SLInsert(&s, 20, 30);//在不属于顺序表的地方,插入一个元素，越界但不一定报错！
	//SLPrint(&s);

	SLInsert(&s, -20, 30);//负数下标
	//SLPrint(&s);

}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

加了assert(0 <= pos && pos <= psl->size)之后:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

这里说一下，头插和尾插都可以调用SLInsert函数，提高代码的复用性

尾插：

void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);

	//psl->a[psl->size] = x;
	//psl->size++;

	//SLCheckCapacity(psl);

	//psl->a[psl->size++] = x;

	SLInsert(psl, psl->size, x);
}

头插：

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	//SLCheckCapacity(psl);

	 挪动数据
	//int end = psl->size - 1;
	//while (end >= 0)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}

	//psl->a[0] = x;
	//psl->size++;
	SLInsert(psl, 0, x);
}

🔟中间删除:SLErase

void SLErase(SL* psl,int pos);

void SLErase(SL* psl, int pos)//从中间删除元素,也可以是首或者尾
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	assert(0 <= pos && pos < psl->size);//说明这个位置可以是顺序表的头和尾
	//assert(psl->size>0);//这句代码也可以不加，因为

	int start = pos + 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		++start;
	}

	psl->size--;
}

图解:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

再次调用这组测试,这次是为了测试从中间删除：

void TestSeqList5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	SLInsert(&s, 2, 30);//中间插入
	SLPrint(&s);

	//SLInsert(&s, 20, 30);
	//SLPrint(&s);

	//SLInsert(&s, -20, 30);
	//SLPrint(&s);

	SLErase(&s, 3);//删除中间下标为3的元素,把元素3删除了
	SLPrint(&s);
	 
	SLPopFront(&s);
	SLPrint(&s);

	SLPopBack(&s);
	SLPrint(&s);

	SLDestroy(&s);
}

执行:这里第三行把3干掉了

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

调用SLErase(函数

尾删：

void SLPopBack(SL* psl)
{
	assert(psl);
	// 暴力检查
	//assert(psl->size > 0);

	 温柔的检查
	if (psl->size == 0)
		return;

	psl->a[psl->size - 1] = 0;
	//psl->size--;

	SLErase(psl, psl->size-1);
}

头删:

void SLPopFront(SL* psl)
{
	assert(psl);
	// 暴力检查
	//assert(psl->size > 0);

	///*int start = 0;
	//while (start < psl->size-1)
	//{
	//	psl->a[start] = psl->a[start + 1];
	//	start++;
	//}*/

	//int start = 1;
	//while (start < psl->size)
	//{
	//	psl->a[start-1] = psl->a[start];
	//	start++;
	//}

	//psl->size--;

	SLErase(psl, 0);
}

1️⃣1️⃣查找:SLFind

int SLFind(SL* psl, SLDatatype x);//找到返回下标,没有找到返回-1

返回的-1也可以用其它负数,但是一般都是用-1。

int SLFind(SL* psl, SLDatatype x)//查找
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;//返回要查找的元素的下标
		}
	}
	return -1;//走完一遍了还没找到就返回-1，因为下标不可能是负数

}

测试一组查找的代码:

void TestSeqList6()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
    SLPushBack(&s, 6);//返回这个的下标,不会返回下面那个6的下标
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	int pos = SLFind(&s, 6);
	if (pos != -1)
	{
		SLErase(&s, pos);
	}
	SLPrint(&s);

	SLDestroy(&s);
}

找到了就返回该元素的下标,然后从中间删除它,注意这里有两个6，只返回第一个6的下标,因为第一个6是先放进去的

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

执行:

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

1️⃣2️⃣修改:SLModify

void SLModify(SL* psl, int pos, SLDatatype x);

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);//应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

	assert(0 <= pos && pos < psl->size);

	psl->a[pos] = x;
}

调用修改的代码：

void TestSeqList7()//用于测试修改
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 6);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	int pos = SLFind(&s, 6);
	if (pos != -1)
	{
		SLModify(&s, pos, 10);//4下标的6已经改成10了
	}
	SLPrint(&s);

	SLDestroy(&s);
}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

这里再测试一下assert断言的好处:应对可能传过来的NULL指针，而且好处是直接告诉你哪个文件的哪一行出问题

void TestSeqList8()
{
	SL* s = NULL;
	SLPushBack(s, 1);
	SLPushBack(s, 2);
	SLPushBack(s, 3);
	SLPrint(s);

	SLDestroy(s);
}

【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

三.整体实现代码

SeqLish.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

#include<assert.h>
//静态的顺序表
//#define N 10000
//typedef int SLDatatype;
//struct SeqList
//{
//	SLDatatype a[N];
//	int size;
//};

//动态顺序表
typedef int SLDatatype;//这个位置换成double会导致问题,可能会导致全元素都是0
typedef struct SeqList
{
	SLDatatype* a;
	int size;	 //存储的有效数据的个数
	int capacity;//容量
}SL;//类型名重定义

void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL*psl);// 顺序表打印


void SLPushBack(SL* psl, SLDatatype x);//尾插
void SLPushFront(SL* psl, SLDatatype x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删

void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl,int pos);

//找到返回下标,没有找到返回-1
int SLFind(SL* psl, SLDatatype x);

void SLModify(SL* psl, int pos, SLDatatype x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

//顺序表的要求就是连续存储




void SLInit(SL* psl)
{
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//malloc扩容,因为malloc类型是->void* malloc (size_t size);所以需要强制转换
	//打印错误信息?
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->capacity = 4;//使用结构体指针指向访问对象的成员,当前容量
	psl->size = 0;//当前有效信息个数
}


void SLDestroy(SL* psl)//销毁不是整没了，而是还给操作系统了
{
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
void SLPrint(SL* psl)
{
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//?
void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)//有效信息的个数等于当前容量
	{
		SLDatatype* tmp =(SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL)//申请空间过大可能会申请失败
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;//原地扩容用的是原来的地址，异地扩容用的是新的
		psl->capacity *= 2;//当前容量*2
	}
}
//尾插法
void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);	
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;//检查当前容量,不够则扩容


}
//头插法必须从后往前挪动数据，不能从往前往后挪动
void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);

	//挪动数据
	int end = psl->size-1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}



//尾删
void SLPopBack(SL* psl)
{
	assert(psl);

	//暴力检查
	//assert(psl->size > 0);
	//温柔检查
	if (psl->size == 0)
	{
		printf("顺序表为空,删除失败\n");
		return;//不报错任何问题,直接回答主函数。
	}
		

    //psl->a[psl->size - 1] = 0;这句话不好,就是说把最后一个位置变成0
	psl->size--;

}


void SLPopFront(SL* psl)//从后往前
{
	assert(psl);

	//暴力检查
	assert(psl->size > 0);
	//温柔检查
	if (psl->size == 0)
		return;
	int start = 0;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	/*int start = 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}*/
	psl->size--;

}

//中间插入:首先要看容量，调用检查容量的函数,接着挪动
void SLInsert(SL* psl,int pos,SLDatatype x)
{
	assert(psl);

	assert(0 <= pos && pos <= psl->size);

	SLCheckCapacity(psl);

	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, int pos)//从中间删除元素,也可以是首或者尾
{
	assert(psl);
	assert(0 <= pos && pos < psl->size);
	//assert(psl->size>0);

	int start = pos + 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		++start;
	}

	psl->size--;
}

int SLFind(SL* psl, SLDatatype x)//查找
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;//走完一遍了还没找到就返回-1，因为下标不可能是负数。

}


void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);

	assert(0 <= pos && pos < psl->size);

	psl->a[pos] = x;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void TestSeqList1()
{
	SL s;
	SLInit(&s);
	
	SLPushBack(&s, 1);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushFront(&s,5);
	
	SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList3()//测试尾部删除的越界问题,以及打印值问题
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPrint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList4()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

	//SLPopFront(&s);
	//SLPopFront(&s);
	//SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	SLInsert(&s, 2, 30);
	SLPrint(&s);

	//SLInsert(&s, 20, 30);
	//SLPrint(&s);

	//SLInsert(&s, -20, 30);
	//SLPrint(&s);

	SLErase(&s, 3);
	SLPrint(&s);
	 
	SLPopFront(&s);
	SLPrint(&s);

	SLPopBack(&s);
	SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList6()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 6);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	int pos = SLFind(&s, 6);
	if (pos != -1)
	{
		SLErase(&s, pos);
	}
	SLPrint(&s);

	SLDestroy(&s);
}


void TestSeqList7()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 6);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPrint(&s);

	int pos = SLFind(&s, 6);
	if (pos != -1)
	{
		SLModify(&s, pos, 10);
	}
	SLPrint(&s);

	SLDestroy(&s);
}

void TestSeqList8()
{
	SL* s = NULL;
	SLPushBack(s, 1);
	SLPushBack(s, 2);
	SLPushBack(s, 3);
	SLPrint(s);

	SLDestroy(s);
}

void menu()
{
	printf("***************************************\n");
	printf("1、尾插数据  2、尾删数据\n");
	printf("3、头插数据  4、头删数据\n");
	printf("5、打印数据  -1、退出\n");
	printf("***************************************\n");
}

int main()
{
	//TestSeqList1();
	TestSeqList2();
	
	//TestSeqList3();
	//TestSeqList5();
	//TestSeqList8();


	return 0;
}

欢迎大佬指正，非常感谢您的支持!文章来源地址https://www.toymoban.com/news/detail-462654.html

到了这里，关于【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！