• 顺序表专题

    目录

    1. 数据结构

    1.1什么是数据结构

    1.2 为什么需要数据结构

    2. 顺序表的概念及结构

    2.1 线性表

    3. 顺序表的分类

    3.1顺序表和数组的区别

    3.2 顺序表分类

    3.3 动态顺序表的实现

    1. 数据结构

    数据结构是什么?为什么要学习数据结构?数据结构在我们的生活中又有什么样的作用呢?

    1.1什么是数据结构

    数据结构是由“数据”和“结构”两词组合而来。

    什么是数据?常见的数值1、2、3、4.....、网页肉眼眼可以看到的信息(文字、图片、视频等等),这些都是数据。

    什么是结构？当我们想要使用大量使用同⼀类型的数据时,通过手动定义⼤量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在⼀起,结构也可以理解为组织数据的方式。

    概念:数据结构是计算机存储,组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成,即数据由那部分构成,以什么方式构成,以及数据元素之间呈现的结构。

    总结:

    1.能够存储数据(如顺序表、链表等结构)。

    2.存储的数据能够方便查找。

    1.2 为什么需要数据结构

    如图中所示,不借助排队的方式来管理客户,会导致客户等待时间长,景区营业混乱等情况。同理，程序中如果不对数据进行管理,可能会导致数据丢失、操作数据困难、野指针等情况。

    通过数据结构,能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操 作。

    我们之前学过最基础的数据结构:数组

    假如我现在需要100个整型数据,如果之前没有学过数组, 那我们肯定会想到创建100个整型变量,用来存储100个整型数据,创建这100个整型变量,假如以后要对这100个数据中的某个数据修改,增加,查询,删除的话都是比较麻烦的,而且管理起来也是比比较麻烦的,如果为了刚好看一些,就会创建一百行,要声明还要初始化,涉及的行数就会更多。

    但是现在有了数组这样的数据结构,就可以使用一个数组来维护100个同类型的数据,甚至是上千上万个同类型的数据,我可以通过下标对指定的数据进行增加,删除,修改,查询,会非常的方便。

    有了数组,为什么还要学习其他的数据结构？

    假定数组有10个空间,已经使用了5个,向数组中插入数据步骤：

    求数组的长度,求数组的有效数据个数,向下标为数据有效个数的位置插入数据(注意：这里是否要判断数组是否满了,满了还能继续插入吗).....

    假设数据量非常庞大,频繁的获取数组有效数据个数会影响程序执行效率。

    结论:最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。

    2. 顺序表的概念及结构

    2.1 线性表

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

    顺序表是线性表的一种。

    线性表物理结构不一定是连续的,逻辑结构一定是连续的。

    顺序表物理结构和逻辑结构都是连续的,因为底层是数组。

    案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合

    3. 顺序表的分类

    3.1顺序表和数组的区别

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

    3.2 顺序表分类

    静态顺序表:

    1. //静态顺序表的定义
    2. struct SeqList//sequence:顺序的 List:表
    3. {
    4. 	int arr[100];//定长的数组
    5. 	int size;//顺序表当前有效的数据个数
    6. };

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

    动态顺序表:

    1. //动态顺序表的定义
    2. struct SeqList//sequence:顺序的 List:表
    3. {
    4. 	int* arr;//大小不确定,所以创建一个指针
    5. 	int size;//顺序表当前有效的数据个数
    6. 	int capacity;//空间大小
    7. };

    3.3 动态顺序表的实现

    代码:

    1.main.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3.  
    4. //测试初始化
    5. void SeqListInitTest()
    6. {
    7. 	SL sl;
    8. 	SLInit(&sl);
    9. 	SLDestroy(&sl);
    10. }
    11. //尾插测试
    12. SLPushBackTest()
    13. {
    14. 	SL sl;
    15. 	SLInit(&sl);
    16. 	SLPushBack(&sl, 1);
    17. 	SLPrint(&sl);
    18. 	SLPushBack(&sl, 2);
    19. 	SLPrint(&sl);
    20. 	SLPushBack(&sl, 3);
    21. 	SLPrint(&sl);
    22. 	SLPushBack(&sl, 4);
    23. 	SLPrint(&sl);
    24. 	SLPushBack(&sl, 5);
    25. 	SLPrint(&sl);
    26. 	SLPushBack(&sl, 6);
    27. 	SLPrint(&sl);
    28. 	SLDestroy(&sl);
    29. }
    30. //尾删测试
    31. void SLPopBackTest()
    32. {
    33. 	SL sl;
    34. 	SLInit(&sl);
    35. 	SLPushBack(&sl, 1);
    36. 	SLPushBack(&sl, 2);
    37. 	SLPushBack(&sl, 3);
    38. 	SLPushBack(&sl, 4);
    39. 	SLPrint(&sl);
    40. 	SLPopBack(&sl);
    41. 	SLPrint(&sl);
    42. 	SLPopBack(&sl);
    43. 	SLPrint(&sl);
    44. 	SLDestroy(&sl);
    45. }
    46. //头插测试
    47. void SLPushFrontTest()
    48. {
    49. 	SL sl;
    50. 	SLInit(&sl);
    51. 	SLPushFront(&sl, 1);
    52. 	SLPushFront(&sl, 2);
    53. 	SLPushFront(&sl, 3);
    54. 	SLPushFront(&sl, 4);
    55. 	SLPushFront(&sl, 7);
    56. 	SLPrint(&sl);
    57. 	SLDestroy(&sl);
    58. }
    59. //头删测试
    60. void SLPopFrontTest()
    61. {
    62. 	SL sl;
    63. 	SLInit(&sl);
    64. 	SLPushFront(&sl, 1);
    65. 	SLPushFront(&sl, 2);
    66. 	SLPushFront(&sl, 3);
    67. 	SLPushFront(&sl, 4);
    68. 	SLPushFront(&sl, 7);
    69. 	SLPrint(&sl);
    70. 	SLPopFront(&sl);
    71. 	SLPrint(&sl);
    72. 	SLDestroy(&sl);
    73. }
    74. //指定位置插入测试
    75. void SLInsertTest()
    76. {
    77. 	SL sl;
    78. 	SLInit(&sl);
    79. 	SLPushFront(&sl, 1);
    80. 	SLPushFront(&sl, 2);
    81. 	SLPushFront(&sl, 3);
    82. 	SLPushFront(&sl, 4);
    83. 	SLPrint(&sl);
    84. 	SLInsert(&sl,3,21);
    85. 	SLPrint(&sl);
    86. 	SLDestroy(&sl);
    87. }
    88. void SLEraseTest()
    89. {
    90. 	SL sl;
    91. 	SLInit(&sl);
    92. 	SLPushFront(&sl, 1);
    93. 	SLPushFront(&sl, 2);
    94. 	SLPushFront(&sl, 3);
    95. 	SLPushFront(&sl, 4);
    96. 	SLPrint(&sl);
    97. 	SLErase(&sl,0, 21);
    98. 	SLPrint(&sl);
    99. 	SLDestroy(&sl);
    100. }
    101. void SLFindTest()
    102. {
    103. 	int index = 0;
    104. 	SL sl;
    105. 	SLInit(&sl);
    106. 	SLPushFront(&sl, 1);
    107. 	SLPushFront(&sl, 2);
    108. 	SLPushFront(&sl, 3);
    109. 	SLPushFront(&sl, 4);
    110. 	SLPrint(&sl);
    111. 	index = SLFind(&sl, 7);
    112. 	if (index >= 0)
    113. 		printf("找到了,下标是:%d\n", index);
    114. 	else
    115. 		printf("没找到!!!\n");
    116. 	SLDestroy(&sl);
    117. }
    118. int main()
    119. {
    120. 	//SeqListInitTest();//初始化测试
    121. 	//SLPushBackTest();//尾插测试
    122. 	//SLPopBackTest();//尾删测试
    123. 	//SLPushFrontTest();//头插测试
    124. 	//SLPopFrontTest();//测试头删
    125. 	//SLInsertTest();//指定位置插入测试
    126. 	//SLEraseTest();//指定位置删除测试
    127. 	SLFindTest();//查找测试
    128. 	return 0;
    129. }

    2.SeqList.h

    1. #pragma once
    2. //定义顺序表的结构
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. //方便以后修改类型,如果今后要修改成char,只修改这一行代码就可以
    8. typedef int SLDataType;
    9.  
    10.  
    11. /*
    12. #define N 100
    13. //静态顺序表
    14. struct SeqList
    15. {
    16. 	int arr[N];
    17. 	int size;
    18. };
    19. */
    20.  
    21. //动态顺序表
    22. struct SeqList
    23. {
    24. 	SLDataType* arr;
    25. 	int size;//顺序表当前有效的数据个数
    26. 	int capacity;//空间大小
    27. };
    28.  
    29. typedef struct SeqList SL;//对结构体类型重命名
    30. //顺序表的初始化
    31. void SLInit(SL* ps);
    32. //顺序表的销毁
    33. void SLDestroy(SL* ps);
    34. //扩容
    35. void SLCheckCapacity(SL* ps);
    36. //打印顺序表
    37. void SLPrint(SL* ps);
    38. //尾部插入数据
    39. void SLPushBack(SL* ps, SLDataType x);
    40. //头部插入数据
    41. void SLPushFront(SL* ps, SLDataType x);
    42. //尾部删除数据
    43. void SLPopBack(SL* ps);
    44. //头部删除数据
    45. void SLPopFront(SL* ps);
    46. //指定位置插入数据
    47. void SLInsert(SL* ps, int pos, SLDataType x);
    48. //指定位置删除数据
    49. void SLErase(SL* ps, int pos);
    50. //查找顺序表中的数据
    51. int SLFind(SL* ps, SLDataType x);

    3.SeqList.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3. //顺序表的初始化
    4. void SLInit(SL* ps)
    5. {
    6. 	ps->arr = NULL;
    7. 	ps->size = ps->capacity = 0;
    8. 	/*
    9. 	也可以初始化的时候给capacity给空间大小,但是ps->arr同时也要malloc空间
    10. 	*/
    11. }
    12. //顺序表的销毁
    13. void SLDestroy(SL* ps)
    14. {
    15. 	//动态申请的空间需要手动的释放掉
    16. 	//不是销毁整个顺序表
    17. 	if (ps->arr)//判断数组成员是否为空
    18. 	{
    19. 		free(ps->arr);//释放动态申请的空间
    20. 	}
    21. 	ps->arr = NULL;//置为空指针,否则会变成野指针
    22. 	ps->size = ps->capacity = 0;//置为0
    23. }
    24. //扩容
    25. void SLCheckCapacity(SL* ps)
    26. {
    27. 	/*if (ps == NULL)
    28. 		return;*/
    29. 	assert(ps);//assert(ps != NULL);
    30. 	//插入数据之前先看数据够不够
    31. 	//判断当前空间与有效个数是不是相同,相同则需要申请空间
    32. 	if (ps->size == ps->capacity)
    33. 	{
    34. 		//申请空间
    35. 		/*
    36. 		要申请多大的空间,一次增容多大?
    37. 		增容通常来说是成倍的增加,一般是2或者3倍,实际上是数学推理出来的
    38. 		用2倍更合理
    39. 		可以百度:为什么增容要以2倍增加
    40. 		增容我们要用realloc，malloc和calloc都是用来申请空间的
    42. 		*/
    43. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    44. 		SLDataType* tem = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
    45. 		if (tem == NULL)
    46. 		{
    47. 			perror("realloc err!");//打印申请失败的原因
    48. 			exit(1);//给一个非0的值
    49. 		}
    50. 		ps->arr = tem;
    51. 		ps->capacity = newCapacity;
    52. 	}
    53. }
    54. //尾插
    55. void SLPushBack(SL* ps, SLDataType x)
    56. {
    57. 	SLCheckCapacity(ps);
    58. 	ps->arr[ps->size++] = x;//插入完数据直接加加,也可以分开写
    59.  
    60. }
    61. //头插
    62. void SLPushFront(SL* ps, SLDataType x)
    63. {
    64. 	SLCheckCapacity(ps);
    65. 	for (int i = ps->size; i > 0; i--)
    66. 	{
    67. 		ps->arr[i] = ps->arr[i-1];//ps->arr[1] = ps->arr[0]
    68. 	}
    69. 	ps->arr[0] = x;
    70. 	ps->size++;
    71. }
    72. //打印 - 可以不用传指针,因为这里不需要修改,只是打印
    73. void SLPrint(SL* ps)
    74. {
    75. 	for (int i = 0; i < ps->size; i++)
    76. 	{
    77. 		printf("%d ", ps->arr[i]);
    78. 	}
    79. 	printf("\n");
    80. }
    81. //尾删
    82. void SLPopBack(SL* ps)
    83. {
    84. 	assert(ps);
    85. 	assert(ps->size);//判断有效个数,有效个数为0则不能执行删除
    86. 	ps->size--;//直接--不影响后续的增删改查
    87. }
    88. //头删
    89. void SLPopFront(SL* ps)
    90. {
    91. 	assert(ps);
    92. 	for (int i = 0; i  size - 1; i++)
    93. 	{
    94. 		ps->arr[i] = ps->arr[i + 1];
    95. 	}
    96. 	ps->size--;
    97. }
    98. //指定位置插入数据
    99. void SLInsert(SL* ps, int pos, SLDataType x)
    100. {
    101. 	assert(ps && pos >= 0 && pos <= ps->size);
    102. 	SLCheckCapacity(ps);
    103. 	for (int i = ps->size; i > pos; i--)
    104. 	{
    105. 		ps->arr[i] = ps->arr[i - 1];
    106. 	}
    107. 	ps->arr[pos] = x;
    108. 	++ps->size;
    109. }
    110. //指定位置删除数据
    111. void SLErase(SL* ps, int pos)
    112. {
    113. 	assert(ps && pos >= 0 && pos < ps->size);
    114. 	for (int i = pos; i < ps->size - 1; i++)
    115. 	{
    116. 		ps->arr[i] = ps->arr[i + 1];
    117. 	}
    118. 	--ps->size;
    119. }
    120. //查找顺序表中的数据
    121. int SLFind(SL* ps, SLDataType x)
    122. {
    123. 	assert(ps);
    124. 	for (int i = 0; i < ps->size; i++)
    125. 	{
    126. 		if (x == ps->arr[i])
    127. 		{
    128. 			return i;
    129. 		}
    130. 	}
    131. 	return -1;
    132. }

    常见问题:

    1.初始化函数的注意点

    2.插入数据的注意点 

    3.申请空间的注意点

    4.空指针参数的处理

     

  • 相关阅读:
    自学Vue开发Dapp去中心化钱包（二）
    大数据毕业设计选题推荐-智慧小区大数据平台-Hadoop-Spark-Hive
    【K8s】初识PV和PVC
    月薪10.8K，从销售客服转行软件测试斩获4份offer，所有的惊艳都来自长久的准备
    问题解决：python接入支付宝沙箱问题处理
    分布式数据库系统实验五
    第0讲 课程介绍
    2022年NPDP考完多久出成绩？怎么查询？
    IPV4和IPV6是什么？
    猫头虎分享已解决Bug || **Eslint插件安装问题Unable to resolve eslint-plugin-猫头虎
  • 原文地址：https://blog.csdn.net/m0_74271757/article/details/139769856