devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

顺序表（数据结构）

作者：你好赵伟 | 2024-04-17 10:56:38

赞

踩

顺序表

目录

前情提示

概念

内容

1.顺序表的定义

2.顺序表的初始化

3.顺序表的销毁

4.检查空间

5.顺序表的尾插

6.顺序表的打印

7.顺序表的尾删

8.顺序表的头插

9.顺序表的头删

10.顺序表的指定位置插入

 11.顺序表指定位置值的删除

12.顺序表的查找

13.顺序表修改pos位置的值

总代码（想直接看结果的可以看这里）

在 SeqList.h 下

在 SeqList.c 下

在 Test.c 下

前情提示

SeqList.h  用于  引用的头文件、顺序表的定义、接口的函数声明。

SeqList.c  用于  接口函数的定义。

Test.c       用于   顺序表功能的测试。

概念

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以 数组和 链式结构的形式存储。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
          

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

1. 静态顺序表：使用定长数组存储元素。( 空间开多了浪费，开少了不够用 )

2. 动态顺序表：使用动态开辟的数组存储。(按需申请)

静态顺序表只适用于确定知道需要存多少数据的场景。不适用于现实生活中的实际情况，所以接下来我们只讲解动态顺序表。

内容

1.顺序表的定义

在 SeqList.h 下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突。
  2.  
  3. //先将可能使用到的头文件写上
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7.  
  8. typedef int SLDataType;//顺序表的类型名称，给变量定义一个易于记忆且意义明确的新名字，
  9. //并且便于以后存储其它类型时方便改动.
  10. //（比如我晚点想存double类型的数据，我就直接将 int 改为 double ）
  11.  
  12. typedef struct SeqList
  13. {
  14. 	SLDataType* a;//指向动态开辟的数组。
  15. 	size_t size;//有效数据个数
  16. 	size_t capacity;//空间容量
  17. }SL;
  18. //struct 关键字和 SeqList 一起构成了这个结构类型。
  19. //typedef 为这个结构起了一个别名，叫 SL，即：typedef struct SeqList SL 。
  20. //现在就可以像 int 和 double 那样直接使用 SL 定义变量。

2.顺序表的初始化

在 SeqList.h 下

  1. #define INIT_CAPACITY 4//初始化的容量
  2.  
  3. //顺序表初始化
  4. //我们传地址而不是传值，因为形参是实参的拷贝，形参的改变不影响实参。
  5. void SLInit(SL* ps);

在 SeqList.c 下

  1. #include"SeqList.h"//别忘了
  2.  
  3. void SLInit(SL* ps)
  4. {
  5.     assert(ps);//断言
  6.  
  7.     //用malloc申请了一块空间
  8. 	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);
  9.     //表示：malloc申请开辟 sizeof(int)乘以4 即16个字节大小的空间后，强制类型转换成(int*)
  10.  
  11.     if (ps->a == NULL)//如果开辟失败
  12. 	{
  13. 		perror("malloc fail");//输出错误信息
  14. 		return;
  15. 	}
  16. 	ps->size = 0;
  17. 	ps->capacity = INIT_CAPACITY;//初始化的时候先开辟一点空间
  18. }

提醒：

对malloc函数和sizeof操作符熟悉的可以跳过这一部分。

malloc函数内参数要求是size_t类型的，返回类型是void*。

如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。

在使用malloc开辟空间时，使用完成一定要释放空间(free)，如果不释放会造内存泄漏。

malloc的头文件，在ANSI标准建议使用stdlib.h头文件,但许多C编译要求用malloc.h。

 在 Test.c 下

  1. #include"SeqList.h"//别忘了
  2.  
  3. //用于接口函数功能的测试
  4. void TestSeqList1()
  5. {
  6. 	SL s;
  7. 	SLInit(&s);
  8. }
  9.  
  10. int main()
  11. {
  12. 	TestSeqList1();//调用测试函数
  13. 	return 0;
  14. }

3.顺序表的销毁

在 SeqList.h 下

  1. // 顺序表销毁
  2. void SLDestroy(SL* ps);

在 SeqList.c 下

  1. // 顺序表销毁
  2. void SLDestroy(SL* ps)
  3. {
  4.     assert(ps);//断言,最好加上，防止有些人直接将指针初始化为 NULL，而不用SLInit()函数
  5. 	free(ps->a);//释放a
  6. 	ps->a = NULL;//归还空间
  7. 	ps->capacity = ps->size = 0;//有效数据个数和空间容量都赋值为0
  8.     //将0赋给size，再将size赋给capacity
  9. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList1()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6. 	SLDestroy(&s);
  7. }

4.检查空间

在 SeqList.h 下

  1. //检查空间，如果满了，进行增容
  2. void SLCheckCapacity(SL* ps);

在 SeqList.c 下

扩容一般一次增容 2 倍，你也可以扩3倍、4倍。

  1. //检查空间
  2. void SLCheckCapacity(SL* ps)
  3. {
  4. 	assert(ps);//断言
  5.  
  6. 	//判断是否扩容,若是，则扩
  7. 	if (ps->size == ps->capacity)//若最后一个数据的下一个位置的下标等于空间容量，则需扩容
  8. 	{
  9. 	   //realloc的注意事项可看下文。
  10. 	   //很多人容易把下面这一行代码写成
  11.        //SLDataType*tmp=(SLDataType*)realloc(ps->a,ps->capacity*2);->这只扩到8个字节
  12. 	   SLDataType*temp=(SLDataType*)realloc(ps->a,sizeof(SLDataType)*ps->capacity*2);
  13. 	   //扩的空间是原来的两倍->扩到32个字节
  14. 	   //realloc(a地址，izeof(int)*4*2)后强制类型转化,
  15.        //从void*转化成int*类型,赋值给int*类型的temp
  16.  
  17. 	   if (temp == NULL)//如果申请失败
  18. 	   {
  19. 		   perror("realloc fail");//报错
  20. 		   return;
  21. 	   }
  22. 	   ps->a = temp;//a接收realloc返回的指针，realloc不一定原地扩容，可能原地、异地
  23. 	   //如果美甲上面那行代码程序没有报错，只是巧合，刚好原地扩容了。
  24. 	   ps->capacity *= 2;//如果扩容成功,size不变,capacity是原来2倍
  25. 	}
  26. }

提醒：

对realloc函数熟悉的可以跳过这一部分。

realloc函数返回的是void*类型的指针，指向在堆区重新开辟的内存块的起始地址，ptr是先前开辟的内存块的指针，size_t size指的是New size in bytes,新的字节数，注意不是增加的字节数，而是新开辟的那块内存空间的字节数。如果申请失败，将返回NULL，此时，原来的指针仍然有效。如果调用成功，不管当前内存段后面的空闲空间是否满足要求，都会释放掉原来的指针，重新返回一个指针。

5.顺序表的尾插

在 SeqList.h 下

  1. // 顺序表尾插——在顺序表的最后插入一个数据
  2. void SLPushBack(SL* ps, SLDataType x);//x为插入的数据

在 SeqList.c 下

有图可知：sz是数据个数，同时也是最后一个数据的下一个位置的下标。

  1. //顺序表的尾插
  2. void SLPushBack(SL* ps, SLDataType x)
  3. {
  4.     assert(ps);//断言
  5.     SLCheckCapacity(ps);//扩容
  6.  
  7.     if (temp == NULL)//如果申请失败
  8. 	{
  9. 	    perror("realloc fail");//报错
  10. 		return;
  11. 	}
  12.  
  13. 	//sz是数据个数，同时也是最后一个数据的下一个位置的下标
  14. 	ps->a[ps->size++] = x;
  15. 	//意思是:ps->a[ps->size] = x;
  16. 	//		 ps->size++;
  17. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList1()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6. 	SLPushBack(&s, 1);
  7. 	SLPushBack(&s, 2);
  8. 	SLPushBack(&s, 3);
  9. 	SLPushBack(&s, 4);
  10. 	SLPushBack(&s, 5);
  11. 	SLPushBack(&s, 6);
  12. 	SLDestroy(&s);
  13. }

6.顺序表的打印

在 SeqList.h 下

  1. //顺序表打印
  2. void SLPrint(SL* ps);

在 SeqList.c 下

  1. // 顺序表打印
  2. void SLPrint(SL* ps)
  3. {
  4.     assert(ps);//断言
  5. 	for (size_t i = 0; i < ps->size; ++i)
  6. 	{
  7. 		printf("%d ", ps->a[i]);
  8. 	}
  9. 	printf("\n");
  10. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList1()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6. 	SLPushBack(&s, 1);
  7. 	SLPushBack(&s, 2);
  8. 	SLPushBack(&s, 3);
  9. 	SLPushBack(&s, 4);
  10. 	SLPushBack(&s, 5);
  11. 	SLPushBack(&s, 6);
  12. 	SLPrint(&s);
  13. 	SLDestroy(&s);
  14. }

7.顺序表的尾删

在 SeqList.h 下

  1. // 顺序表尾删——在顺序表的最后删除一个数据
  2. void SLPopBack(SL* ps);

在 SeqList.c 下

  1. // 顺序表尾删
  2. void SLPopBack(SL* ps)
  3. {
  4.     assert(ps);//断言
  5. 	//size为 0之后就不能再删除了！
  6. 	if (ps->size == 0)
  7. 	{
  8. 		return;
  9. 	}
  10. 	//或者
  11. 	//assert(ps->size>0);
  12.  
  13. 	//加不加 ps->a[ps->size - 1] = 0;都无所谓
  14. 	ps->size--;
  15. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList1()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6. 	SLPushBack(&s, 1);
  7. 	SLPushBack(&s, 2);
  8. 	SLPushBack(&s, 3);
  9. 	SLPushBack(&s, 4);
  10. 	SLPushBack(&s, 5);
  11. 	SLPushBack(&s, 6);
  12. 	SLPrint(&s);
  13.  
  14. 	SLPopBack(&s);
  15. 	SLPopBack(&s);
  16. 	SLPrint(&s);
  17.  
  18. 	SLDestroy(&s);
  19. }

提醒：

若size为0之后还继续减，则size会取max（int）值。

 →

注意：

很多人到这里有一个疑问，就是顺序表可以扩容，那我尾删后可以缩容（释放部分）吗？

不能，因为操作系统的内存管理不支持，操作系统支持内存整块的申请，整块的释放。

8.顺序表的头插

思路：挪动数据(在SeqList.c中体现)

............ 

 

在 SeqList.h 下

  1. // 顺序表头插——在顺序表的开头插入一个数据
  2. void SLPushFront(SL* ps, SLDataType x);//x为插入的数据

在 SeqList.c 下

  1. // 顺序表头插
  2. void SLPushFront(SL* ps, SLDataType x)
  3. {
  4. 	assert(ps);//断言
  5. 	SLCheckCapacity(ps);//扩容
  6.  
  7. 	int end = (int)ps->size - 1;//思路理解看上图
  8. 	while (end >= 0)
  9. 	{
  10. 		ps->a[end + 1] = ps->a[end];
  11. 		--end;
  12. 	}
  13. 	ps->a[0] = x;
  14. 	ps->size++;
  15. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList2()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6.  
  7. 	SLPushFront(&s, 1);
  8. 	SLPushFront(&s, 2);
  9. 	SLPushFront(&s, 3);
  10. 	SLPushFront(&s, 4);
  11. 	SLPushFront(&s, 5);
  12. 	SLPrint(&s);
  13. }
  14.  
  15.  
  16. int main()
  17. {
  18. 	//TestSeqList1();
  19. 	TestSeqList2();
  20. 	return 0;
  21. }

9.顺序表的头删

思路：挪动数据(在SeqList.c中体现)

 

 .........

在 SeqList.h 下

  1. // 顺序表头删——在顺序表的开头删除一个数据
  2. void SLPopFront(SL* ps);

在 SeqList.c 下

  1. // 顺序表头删
  2. void SLPopFront(SL* ps)
  3. {
  4. 	assert(ps);//断言
  5. 	assert(ps->size > 0);//防止size为 0的时候，跳过循环，继续减减。
  6. 	int begin = 1;//思路理解看上图
  7. 	while (begin < (int)ps->size)
  8. 	{
  9. 		ps->a[begin - 1] = ps->a[begin];
  10. 		++begin;
  11. 	}
  12. 	ps->size--;
  13. }

在 Test.c 下

  1. void TestSeqList2()
  2. {
  3. 	SL s;
  4. 	SLInit(&s);
  5.  
  6. 	SLPushFront(&s, 1);
  7. 	SLPushFront(&s, 2);
  8. 	SLPushFront(&s, 3);
  9. 	SLPushFront(&s, 4);
  10. 	SLPushFront(&s, 5);
  11. 	SLPrint(&s);
  12.  
  13. 	SLPopFront(&s);
  14. 	SLPrint(&s);
  15. 	SLPopFront(&s);
  16. 	SLPrint(&s);
  17. 	SLPopFront(&s);
  18. 	SLPrint(&s);
  19. }

注意：头插/头删N个数据时间复杂度为0(N^2)

           尾插/尾删N个数据时间复杂度为0(N)

10.顺序表的指定位置插入

思路：挪动数据(在SeqList.c中体现)

 

 

 

 

在 SeqList.h 下

  1. // 顺序表在pos位置插入x
  2. void SLInsert(SL* ps, size_t pos, SLDataType x);

 在 SeqList.c 下

  1. // 顺序表在pos位置插入x
  2. void SLInsert(SL* ps, size_t pos, SLDataType x)
  3. {
  4. 	assert(ps);//断言
  5. 	assert(pos >= 0 && pos <= ps->size);//保证pos在0与size之间
  6. 	//取等时相当于头插/尾插
  7. 	SLCheckCapacity(ps);//扩容
  8.  
  9. 	int end = ps->size - 1;
  10. 	while (end >= (int)pos)//这里特别注意强制类型转换
  11.     //不改动其它，只将int end改成 size_t end会走死循环
  12. 	{
  13. 		ps->a[end + 1] = ps->a[end];
  14. 		--end;
  15. 	}
  16. 	
  17. 	//或者下面这种写法
  18. 	//size_t end = ps->size;
  19. 	//while (end >pos)
  20. 	//{
  21. 	//	ps->a[end] = ps->a[end-1];
  22. 	//	--end;
  23. 	//}
  24.  
  25. 	ps->a[pos] = x;
  26. 	ps->size++;
  27. }

学会在指定位置插入值的函数后，发现头插和尾插也能用这个函数。即：

  1. void SLPushFront(SL* ps, SLDataType x)
  2. {
  3.     SLInsert(ps,0,x);
  4. }
  1. void SLPushBack(SL* ps, SLDataType x)
  2. {
  3.     SLInsert(ps,ps->size,x);
  4. }

在 Test.c 下

  1. //用于接口函数功能的测试
  2. void TestSeqList3()
  3. {
  4. 	SL s;
  5. 	SLInit(&s);
  6.  
  7. 	SLPushFront(&s, 0);
  8. 	SLPushFront(&s, 2);
  9.  
  10. 	SLInsert(&s,0,5);
  11. 	SLPrint(&s);
  12. }
  13.  
  14. int main()
  15. {
  16. 	//TestSeqList1();
  17. 	//TestSeqList2();
  18. 	TestSeqList3();
  19. 	return 0;
  20. }

 11.顺序表指定位置值的删除

思路：挪动数据(在SeqList.c中体现)

 

 

在 SeqList.h 下

  1. // 顺序表删除pos位置的值
  2. void SLErase(SL* ps, size_t pos);

 在 SeqList.c 下

  1. // 顺序表删除pos位置的值
  2. void SLErase(SL* ps, size_t pos)
  3. {
  4. 	assert(ps);
  5. 	assert(pos >= 0 && pos < ps->size);
  6. 	//注意:pos不能等于size,这里和指定位置插入不一样，
  7.     //并且间接防止了size为0的时候，跳过循环，继续减减。
  8. 	int begin = pos + 1;
  9. 	while (begin <(int)ps->size)
  10. 	{
  11. 		ps->a[begin - 1] = ps->a[begin];
  12. 		++begin;
  13. 	}
  14. 	ps->size--;
  15. }

在 Test.c 下

  1. void TestSeqList4()
  2. {
  3. 	SL s;
  4. 	SLInit(&s);
  5.  
  6. 	SLPushFront(&s, 1);
  7. 	SLPushFront(&s, 2);
  8. 	SLPushFront(&s, 3);
  9. 	SLPushFront(&s, 4);
  10. 	SLPushFront(&s, 5);
  11. 	SLPushFront(&s, 6);
  12. 	SLPushFront(&s, 7);
  13. 	SLPushFront(&s, 8);
  14. 	SLPushFront(&s, 9);
  15. 	SLPrint(&s);
  16.  
  17. 	SLInsert(&s, 4, 666);
  18. 	SLPrint(&s);
  19.  
  20. 	SLInsert(&s, 0, 666);
  21. 	SLPrint(&s);
  22.  
  23. 	SLErase(&s, 4);
  24. 	SLPrint(&s);
  25.  
  26. 	SLErase(&s, 4);
  27. 	SLPrint(&s);
  28. }
  29.  
  30. int main()
  31. {
  32. 	//TestSeqList1();
  33. 	//TestSeqList2();
  34. 	//TestSeqList3();
  35. 	TestSeqList4();
  36. 	return 0;
  37. }

 学会删除指定位置的值的函数后，发现头删和尾删也能用这个函数。即：

  1. void SLPopFront(SL* ps)
  2. {
  3.     SLErase(ps,0);
  4. }
  1. void SLPopBack(SL* ps)
  2. {
  3.     SLErase(ps,ps->size-1);
  4. }

12.顺序表的查找

在 SeqList.h 下

  1. // 顺序表查找
  2. int SLFind(SL* ps, SLDataType x);//x为查找的数据

 在 SeqList.c 下

  1. // 顺序表查找
  2. int SLFind(SL* ps, SLDataType x)
  3. {
  4. 	assert(ps);
  5. 	for (int i = 0; i < (int)ps->size; ++i)
  6. 	{
  7. 		if (ps->a[i] == x)//如果找到了
  8. 		{
  9. 			return i;//则返回要找的值的下标
  10. 		}
  11. 	}
  12. 	return -1;//否则返回-1
  13. }

在 Test.c 下

  1. void TestSeqList5()
  2. {
  3. 	SL s;
  4. 	SLInit(&s);
  5. 	int result = 0;
  6.  
  7. 	SLPushFront(&s, 1);
  8. 	SLPushFront(&s, 2);
  9. 	SLPushFront(&s, 3);
  10. 	SLPushFront(&s, 4);
  11. 	SLPushFront(&s, 5);
  12. 	SLPrint(&s);
  13.  
  14. 	result=SLFind(&s, 3);
  15. 	printf("%d\n", result);
  16.  
  17. }
  18.  
  19.  
  20. int main()
  21. {
  22. 	//TestSeqList1();
  23. 	//TestSeqList2();
  24. 	//TestSeqList3();
  25. 	//TestSeqList4();
  26. 	TestSeqList5();
  27. 	return 0;
  28. }

13.顺序表修改pos位置的值

在 SeqList.h 下

  1. //顺序表修改pos位置的值
  2. void SLModify(SL* ps, size_t pos, SLDataType x);//x为修改后的值

 在 SeqList.c 下

  1. //顺序表修改pos位置的值
  2. void SLModify(SL* ps, size_t pos, SLDataType x)
  3. {
  4. 	assert(ps);
  5. 	assert(pos >= 0 && pos < ps->size);//既防止了size等于0，又规范了pos的位置
  6. 	ps->a[pos] = x;
  7. }

在 Test.c 下

  1. void TestSeqList6()
  2. {
  3. 	SL s;
  4. 	SLInit(&s);
  5.  
  6. 	SLPushFront(&s, 1);
  7. 	SLPushFront(&s, 2);
  8. 	SLPushFront(&s, 3);
  9. 	SLPushFront(&s, 4);
  10. 	SLPushFront(&s, 5);
  11. 	SLPrint(&s);
  12.  
  13. 	SLModify(&s, 2, 1);
  14. 	SLPrint(&s);
  15. }
  16.  
  17.  
  18. int main()
  19. {
  20. 	//TestSeqList1();
  21. 	//TestSeqList2();
  22. 	//TestSeqList3();
  23. 	//TestSeqList4();
  24. 	//TestSeqList5();
  25. 	TestSeqList6();
  26. 	return 0;
  27. }

总代码（想直接看结果的可以看这里）

在 SeqList.h 下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突。
  2.  
  3. //使用到的头文件
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7.  
  8. typedef int SLDataType;//顺序表的类型名称，给变量定义一个易于记忆且意义明确的新名字，
  9. //并且便于以后存储其它类型时方便改动。
  10. //(比如我晚点想存double类型的数据，我就直接将int改为double)
  11.  
  12. #define INIT_CAPACITY 4//初始化的容量
  13.  
  14. typedef struct SeqList
  15. {
  16. 	SLDataType* a;//指向动态开辟的数组
  17. 	size_t size;//有效数据个数
  18. 	size_t capacity;//空间容量
  19. }SL;
  20. //struct 关键字和 SeqList 一起构成了这个结构类型。
  21. //typedef 为这个结构起了一个别名，叫 SL，即：typedef struct SeqList SL 。
  22. //现在就可以像 int 和 double 那样直接使用 SL 定义变量。
  23.  
  24. //基本增删查改接口
  25.  
  26. //顺序表初始化
  27. //我们传地址而不是传值，因为形参是实参的拷贝，形参的改变不影响实参。
  28. void SLInit(SL* ps);
  29.  
  30. // 顺序表销毁
  31. void SLDestroy(SL* ps);
  32.  
  33. //顺序表打印
  34. void SLPrint(SL* ps);
  35.  
  36. // 顺序表尾插——在顺序表的最后插入一个数据
  37. void SLPushBack(SL* ps, SLDataType x);//x为插入的数据
  38.  
  39. // 顺序表尾删——在顺序表的最后删除一个数据
  40. void SLPopBack(SL* ps);
  41.  
  42. // 顺序表头插——在顺序表的开头插入一个数据
  43. void SLPushFront(SL* ps, SLDataType x);//x为插入的数据
  44.  
  45. // 顺序表头删——在顺序表的开头删除一个数据
  46. void SLPopFront(SL* ps);
  47.  
  48. //检查空间，如果满了，进行增容
  49. void SLCheckCapacity(SL* ps);
  50.  
  51. // 顺序表在pos位置插入x
  52. void SLInsert(SL* ps, size_t pos, SLDataType x);//x为插入的数据
  53.  
  54. // 顺序表删除pos位置的值
  55. void SLErase(SL* ps, size_t pos);
  56.  
  57. // 顺序表查找
  58. int SLFind(SL* ps, SLDataType x);//x为查找的数据
  59.  
  60. //顺序表修改pos位置的值
  61. void SLModify(SL* ps, size_t pos, SLDataType x);//x为修改后的值

在 SeqList.c 下

  1. #include"SeqList.h"//别忘了
  2.  
  3. //顺序表初始化
  4. void SLInit(SL* ps)
  5. {
  6. 	assert(ps);//断言
  7.  
  8. 	//用malloc申请了一块空间
  9. 	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);
  10.     //表示：malloc申请开辟 sizeof(int)乘以4 
  11.     //即16个字节大小的空间后，强制类型转换成(int*)
  12.  
  13. 	if (ps->a == NULL)//如果开辟失败
  14. 	{
  15. 		perror("malloc fail");//输出错误信息
  16. 		return;
  17. 	}
  18. 	ps->size = 0;
  19. 	ps->capacity = INIT_CAPACITY;//初始化的时候先开辟一点空间
  20. }
  21.  
  22. // 顺序表销毁
  23. void SLDestroy(SL* ps)
  24. {
  25. 	assert(ps);//断言,最好加上，防止有些人直接将指针初始化为NULL，而不用SLInit()函数
  26. 	free(ps->a);//释放a
  27. 	ps->a = NULL;//归还空间
  28. 	ps->capacity = ps->size = 0;//有效数据个数和空间容量都赋值为0
  29. }
  30.  
  31. //检查空间
  32. void SLCheckCapacity(SL* ps)
  33. {
  34. 	assert(ps);
  35. 	//判断是否扩容,若是，则扩
  36. 	if (ps->size == ps->capacity)//若最后一个数据的下一个位置的下标等于空间容量，则需扩容
  37. 	{
  38. 		//realloc的注意事项可看下文。
  39. 		//很多人容易把下面这一行代码写成
  40.         //SLDataType*tmp=(SLDataType*)realloc(ps->a,ps->capacity*2);->这只扩到8个字节
  41. 		SLDataType*temp=(SLDataType*)realloc(ps->a,sizeof(SLDataType)*ps->capacity*2);
  42. 		//扩的空间是原来的两倍->扩到32个字节
  43. 		//realloc(a地址sizeof(int)*4*2)后，
  44.         //强制类型转化从void*转化成int*类型赋值给int*类型的temp
  45.  
  46. 		if (temp == NULL)//如果申请失败
  47. 		{
  48. 			perror("realloc fail");//报错
  49. 			return;
  50. 		}
  51. 		ps->a = temp;//a接收realloc返回的指针，realloc不一定原地扩容，可能原地、异地
  52. 		如果美甲上面那行代码程序没有报错，只是巧合，刚好原地扩容了。
  53. 		ps->capacity *= 2;//如果扩容成功,size不变,capacity是原来2倍
  54. 	}
  55. }
  56.  
  57. //顺序表的尾插
  58. void SLPushBack(SL* ps, SLDataType x)
  59. {
  60. 	assert(ps);//断言
  61. 	SLCheckCapacity(ps);//扩容
  62.  
  63. 	//sz是数据个数，同时也是最后一个数据的下一个位置的下标
  64. 	ps->a[ps->size++] = x;
  65. 	//意思是:ps->a[ps->size] = x;
  66. 	//		 ps->size++;
  67. }
  68.  
  69. // 顺序表打印
  70. void SLPrint(SL* ps)
  71. {
  72. 	assert(ps);//断言
  73. 	for (size_t i = 0; i < ps->size; ++i)
  74. 	{
  75. 		printf("%d ", ps->a[i]);
  76. 	}
  77. 	printf("\n");
  78. }
  79.  
  80. // 顺序表尾删
  81. void SLPopBack(SL* ps)
  82. {
  83. 	assert(ps);
  84. 	//size为0之后就不能再删除了！
  85. 	if (ps->size == 0)
  86. 	{
  87. 		return;
  88. 	}
  89. 	//或者
  90. 	//assert(ps->size>0);
  91.  
  92. 	//加不加ps->a[ps->size - 1] = 0;都无所谓
  93. 	ps->size--;
  94. }
  95.  
  96. // 顺序表头插
  97. void SLPushFront(SL* ps, SLDataType x)
  98. {
  99. 	assert(ps);//断言
  100. 	SLCheckCapacity(ps);//扩容
  101.  
  102. 	int end = ps->size - 1;
  103. 	while (end >= 0)
  104. 	{
  105. 		ps->a[end + 1] = ps->a[end];
  106. 		--end;
  107. 	}
  108. 	ps->a[0] = x;
  109. 	ps->size++;
  110. }
  111.  
  112.  
  113. // 顺序表头删
  114. void SLPopFront(SL* ps)
  115. {
  116. 	assert(ps);//断言
  117. 	assert(ps->size > 0);//防止size为0的时候，跳过循环，继续减减。
  118. 	int begin = 1;
  119. 	while (begin < (int)ps->size)
  120. 	{
  121. 		ps->a[begin - 1] = ps->a[begin];
  122. 		++begin;
  123. 	}
  124. 	ps->size--;
  125. }
  126.  
  127.  
  128. // 顺序表在pos位置插入x
  129. void SLInsert(SL* ps, size_t pos, SLDataType x)
  130. {
  131. 	assert(ps);//断言
  132. 	assert(pos >= 0 && pos <= ps->size);//保证pos在0与size之间
  133. 	//取等时相当于头插/尾插
  134. 	SLCheckCapacity(ps);//扩容
  135.  
  136. 	int end = ps->size - 1;
  137. 	while (end >= (int)pos)//这里特别注意强制类型转换，不然容易死循环
  138. 	{
  139. 		ps->a[end + 1] = ps->a[end];
  140. 		--end;
  141. 	}
  142. 	
  143. 	//或者下面这种写法
  144. 	//size_t end = ps->size;
  145. 	//while (end >pos)
  146. 	//{
  147. 	//	ps->a[end] = ps->a[end-1];
  148. 	//	--end;
  149. 	//}
  150.  
  151. 	ps->a[pos] = x;
  152. 	ps->size++;
  153. }
  154.  
  155.  
  156. // 顺序表删除pos位置的值
  157. void SLErase(SL* ps, size_t pos)
  158. {
  159. 	assert(ps);//断言
  160. 	assert(pos >= 0 && pos < ps->size);
  161. 	//注意:
  162.     //pos不能等于size,这里和指定位置插入不一样并且间接防止了size为0的时候,跳过循环,继续减减
  163. 	int begin = pos + 1;
  164. 	while (begin <(int)ps->size)
  165. 	{
  166. 		ps->a[begin - 1] = ps->a[begin];
  167. 		++begin;
  168. 	}
  169. 	ps->size--;
  170. }
  171.  
  172. // 顺序表查找
  173. int SLFind(SL* ps, SLDataType x)
  174. {
  175. 	assert(ps);
  176. 	for (int i = 0; i < (int)ps->size; ++i)
  177. 	{
  178. 		if (ps->a[i] == x)//如果找到了
  179. 		{
  180. 			return i;//则返回要找的值的下标
  181. 		}
  182. 	}
  183. 	return -1;//否则返回-1
  184. }
  185.  
  186. //顺序表修改pos位置的值
  187. void SLModify(SL* ps, size_t pos, SLDataType x)
  188. {
  189. 	assert(ps);
  190. 	assert(pos >= 0 && pos < ps->size);//既防止了size等于0，又规范了pos的位置
  191. 	ps->a[pos] = x;
  192. }

在 Test.c 下

  1. #include"SeqList.h"//别忘了
  2.  
  3. //用于接口函数功能的测试
  4. void TestSeqList1()
  5. {
  6. 	SL s;
  7. 	SLInit(&s);
  8. 	SLPushBack(&s, 1);
  9. 	SLPushBack(&s, 2);
  10. 	SLPushBack(&s, 3);
  11. 	SLPushBack(&s, 4);
  12. 	SLPushBack(&s, 5);
  13. 	SLPushBack(&s, 6);
  14. 	SLPrint(&s);
  15.  
  16. 	SLPopBack(&s);
  17. 	SLPopBack(&s);
  18. 	SLPrint(&s);
  19.  
  20.  
  21. 	SLDestroy(&s);
  22. }
  23.  
  24. void TestSeqList2()
  25. {
  26. 	SL s;
  27. 	SLInit(&s);
  28.  
  29. 	SLPushFront(&s, 1);
  30. 	SLPushFront(&s, 2);
  31. 	SLPushFront(&s, 3);
  32. 	SLPushFront(&s, 4);
  33. 	SLPushFront(&s, 5);
  34. 	SLPrint(&s);
  35.  
  36. 	SLPopFront(&s);
  37. 	SLPrint(&s);
  38. 	SLPopFront(&s);
  39. 	SLPrint(&s);
  40. 	SLPopFront(&s);
  41.  
  42. 	SLPrint(&s);
  43. }
  44.  
  45. void TestSeqList3()
  46. {
  47. 	SL s;
  48. 	SLInit(&s);
  49.  
  50. 	SLPushFront(&s, 0);
  51. 	SLPushFront(&s, 2);
  52.  
  53. 	SLInsert(&s,0,5);
  54. 	SLPrint(&s);
  55. }
  56.  
  57. void TestSeqList4()
  58. {
  59. 	SL s;
  60. 	SLInit(&s);
  61.  
  62. 	SLPushFront(&s, 1);
  63. 	SLPushFront(&s, 2);
  64. 	SLPushFront(&s, 3);
  65. 	SLPushFront(&s, 4);
  66. 	SLPushFront(&s, 5);
  67. 	SLPushFront(&s, 6);
  68. 	SLPushFront(&s, 7);
  69. 	SLPushFront(&s, 8);
  70. 	SLPushFront(&s, 9);
  71. 	SLPrint(&s);
  72.  
  73. 	SLInsert(&s, 4, 666);
  74. 	SLPrint(&s);
  75.  
  76. 	SLInsert(&s, 0, 666);
  77. 	SLPrint(&s);
  78.  
  79. 	SLErase(&s, 4);
  80. 	SLPrint(&s);
  81.  
  82. 	SLErase(&s, 4);
  83. 	SLPrint(&s);
  84. }
  85.  
  86. void TestSeqList5()
  87. {
  88. 	SL s;
  89. 	SLInit(&s);
  90. 	int result = 0;
  91.  
  92. 	SLPushFront(&s, 1);
  93. 	SLPushFront(&s, 2);
  94. 	SLPushFront(&s, 3);
  95. 	SLPushFront(&s, 4);
  96. 	SLPushFront(&s, 5);
  97. 	SLPrint(&s);
  98.  
  99. 	result=SLFind(&s, 3);
  100. 	printf("%d\n", result);
  101.  
  102. }
  103.  
  104. void TestSeqList6()
  105. {
  106. 	SL s;
  107. 	SLInit(&s);
  108.  
  109. 	SLPushFront(&s, 1);
  110. 	SLPushFront(&s, 2);
  111. 	SLPushFront(&s, 3);
  112. 	SLPushFront(&s, 4);
  113. 	SLPushFront(&s, 5);
  114. 	SLPrint(&s);
  115.  
  116. 	SLModify(&s, 2, 1);
  117. 	SLPrint(&s);
  118. }
  119.  
  120.  
  121. int main()
  122. {
  123. 	//TestSeqList1();
  124. 	//TestSeqList2();
  125. 	//TestSeqList3();
  126. 	//TestSeqList4();
  127. 	//TestSeqList5();
  128. 	TestSeqList6();
  129. 	return 0;
  130. }

欢迎指正❀

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/439832
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号