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

【数据结构】顺序表(线性表)的实现_1. 完成线性表的顺序存储及基本操作的实现(顺序表初始化、插入、删除功能); 2. 实

作者：AllinToyou | 2024-04-15 09:36:39

赞

踩

1. 完成线性表的顺序存储及基本操作的实现(顺序表初始化、插入、删除功能); 2. 实

目录

         一、什么是顺序表？

         二、顺序表的动态实现

               1、顺序表初始化

               2、顺序表打印

               3、顺序表检查空间

               4、顺序表尾插

               5、顺序表尾删

               6、顺序表头插

               7、顺序表头删

               8、顺序表指定位置插入

               9、顺序表指定位置删除

               10、顺序表查找

               11、顺序表销毁

         三、源代码

               1、SeqList.h

               2、SeqList.c

               3、test.c

 

 

一、什么是顺序表？

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

顺序表的结构如下：

 

顺序表一般分为两种：

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

  1. #define Max 10 
  2. typedef int SLDataType;
  3. typedef struct SeqList
  4. {
  5. 	SLDataType data[Max];  //定长数组
  6. 	size_t size;  //有效数据的个数
  7. }SeqList;

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

  1. typedef int SLDataType;
  2. typedef struct SeqList
  3. {
  4. 	SLDataType* a;      // 指向动态开辟数组的指针
  5. 	size_t size;        // 有效数据个数
  6. 	size_t capicity;    // 容量空间的大小
  7. }SeqList;

本文主要使用的是动态顺序表，因为静态顺序表是事先已经设置好数组空间的大小，万一需要的空间大小比事先设置的大，此时就会出现溢出的情况，使用不方便，所以在这里使用动态顺序表，用多少开辟多少的数组空间。

二、顺序表的动态实现

  1、顺序表初始化

  1. //初始化
  2. void SLInit(SL* ps)
  3. {
  4. 	assert(ps);
  5. 	ps->a = NULL;
  6. 	ps->size = 0;
  7. 	ps->capacity = 0;
  8. }

初始化的时候可以给顺序表开辟空间，当然也可以直接将指针a给设置为NULL，size和capacity同样设置为0。

  2、顺序表打印

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

  3、顺序表检查空间

在顺序表插入和删除的时候会涉及到顺序表空间大小的问题，在插入的时候首先要判断一下，空间是否已满，满的情况要继续开辟空间，才能够插入。

  1. void SLCheckCapacity(SL* ps)
  2. {
  3. 	assert(ps);
  4. 	//扩容
  5. 	if (ps->size == ps->capacity)
  6. 	{
  7. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  8. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
  9. 		if (tmp == NULL)
  10. 		{
  11. 			perror("realloc fail");
  12. 			exit(-1);
  13. 		}
  14. 		ps->a = tmp;
  15. 		ps->capacity = newCapacity;
  16. 	}
  17. }

在这里之所以将检查封装为一个检查空间的函数，就是为了后面在插入的时候方便使用。

这个顺序表在刚创建的时候，其容量是0，此时我们就给它开辟4个元素大小的空间，当容量满的时候，我们就直接将容量翻倍。当我们在realloc函数中传入的是一个空指针的时候，此时的realloc函数就相当于一个malloc函数，所以在这里直接使用realloc函数也是可以的。

  4、顺序表尾插

  1. //尾插 O(1)
  2. void SLPushBack(SL* ps, SLDataType x)
  3. {
  4. 	assert(ps);
  5. 	SLCheckCapacity(ps);
  6. 	ps->a[ps->size] = x;
  7. 	ps->size++;
  8. }

首先我们要检查一下数组空间的大小，如果容量不满可以直接插入，如果容量已满就需要先扩容，在进行插入。 SLCheckCapacity()这个函数就是要检查容量是否已满，满的情况就会立即扩容。

  

  5、顺序表尾删

  1. //尾删
  2. void SLPopBack(SL* ps)
  3. {
  4. 	assert(ps);
  5. 	///暴力检查
  6. 	assert(ps->size > 0);
  7. 	ps->size--;
  8. }

尾删其实只用size--就行，但是要注意一个问题就是在size = 0 的时候，顺序表本身就为空，那么就不能再减了，防止越界访问，因此在这里面加了两个断言就可以防止这种情况的发生。

  6、顺序表头插

  1. //头插 O(N)
  2. void SLPushFront(SL* ps, SLDataType x)
  3. {
  4. 	assert(ps);
  5. 	//检查容量够不够
  6. 	SLCheckCapacity(ps);
  7.  
  8. 	//挪动数据
  9. 	int end = ps->size - 1;
  10. 	while (end >= 0)
  11. 	{
  12. 		ps->a[end + 1] = ps->a[end];
  13. 		end--;
  14. 	}
  15. 	ps->a[0] = x;
  16. 	ps->size++;
  17. }

头插首先肯定也要检查容量的大小， 保证容量大小充足，然后再将存入的数据整体向后移动一位，将第一个位置给空出来，最后插入新的元素。

  7、顺序表头删

  1. //头删
  2. void SLPopFront(SL* ps)
  3. {
  4. 	assert(ps);
  5. 	assert(ps->size > 0);
  6. 	//挪动数据
  7. 	int begin = 1;
  8. 	while (begin < ps->size)
  9. 	{
  10. 		ps->a[begin - 1] = ps->a[begin];
  11. 		begin++;
  12. 	}
  13. 	//暴力检查
  14. 	ps->size--;
  15. }

头删和尾删的大体逻辑是相同的，我们首先需要检查一下size是否为0。接下来的操作我们只需要让后面的数据覆盖前面的数据，最终就完成了头删的效果。

  8、顺序表指定位置插入 

任意位置插入就像是头插和尾插的升级版，只不过多了一个参数pos，如果pos在开始位置，相当于头插，如果pos在最后面，就相当于尾插。

  1. //在pos的位置插入数据
  2. void SLInsert(SL* ps, int pos, SLDataType x)
  3. {
  4. 	assert(ps);
  5. 	assert(pos >= 0);
  6. 	assert(pos <= ps->size);
  7. 	//检查容量够不够
  8. 	SLCheckCapacity(ps);
  9. 	int end = ps->size - 1;
  10. 	while (end >= pos)
  11. 	{
  12. 		ps->a[end + 1] = ps->a[end];
  13. 		end--;
  14. 	}
  15. 	ps->a[pos] = x;
  16. 	ps->size++;
  17. }

假设插入位置的下标是pos,那么我们只需要将pos位置到最后的所有数据整体向后移动，然后把pos的位置空出来，再在pos的位置插入一个新的元素，最后size++。

注意：assert(pos >= 0);assert(pos <= ps->size);这两句代码就是限制插入的元素是在0到size之间，而不是在其他地方，保证元素与元素之间是连续存储的。

 

  9、顺序表指定位置删除 

  1. //在pos的位置删除数据
  2. void SLErase(SL* ps, int pos)
  3. {
  4. 	assert(ps);
  5. 	assert(pos >= 0);
  6. 	assert(pos < ps->size);
  7. 	//挪动数据覆盖
  8. 	int begin = pos + 1;
  9. 	while (begin < ps->size)
  10. 	{
  11. 		ps->a[begin - 1] = ps->a[begin];
  12. 		begin++;
  13. 	}
  14. 	ps->size--;
  15. }

首先需要断言一下size是否为0。然后将pos后面的数据整体向前移动，覆盖原来pos位置所在的数据，最终size–。

  10、顺序表查找

  1. int SLFind(SL* ps, SLDataType x, int begin)
  2. {
  3. 	assert(ps);
  4.  
  5. 	for (int i = begin; i < ps->size; ++i)
  6. 	{
  7. 		if (ps->a[i] == x)
  8. 		{
  9. 			return i;
  10. 		}
  11. 	}
  12. 	return -1;
  13. }

这个函数接口就很简单了，只需遍历一遍数组就行，找到就返回元素的下标，找不到返回-1。

  11、顺序表销毁

  1. //销毁
  2. void SLDestory(SL* ps)
  3. {
  4. 	assert(ps);
  5. 	//if (ps->a != NULL)
  6. 	if (ps->a)
  7. 	{
  8. 		free(ps->a);
  9. 		ps->a = NULL;
  10. 		ps->capacity = 0;
  11. 		ps->size = 0;
  12. 	}
  13. }

我们开始的时候动态开辟的空间是在堆区申请的，我们用完之后一定要将它释放，防止内存泄漏。

三、源代码

  1、SeqList.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5.  
  6. //动态的顺序表 - 按需扩空间
  7. #define N  10
  8. typedef int SLDataType;
  9.  
  10. typedef struct SeqList
  11. {
  12. 	SLDataType* a;
  13. 	int size;//记录存储多少个有效数据
  14. 	int capacity;//空间容量大小
  15. }SL;
  16.  
  17. void SLPrint(SL* ps);//打印
  18. void SLInit(SL* ps);//初始化
  19. void SLDestory(SL* ps);//销毁
  20. void SLCheckCapacity(SL* ps);//检查空间大小
  21.  
  22. //尾插
  23. void SLPushBack(SL* ps, SLDataType x);
  24. //尾删
  25. void SLPopBack(SL* ps);
  26.  
  27. //头插
  28. void SLPushFront(SL* ps, SLDataType x);
  29. //头删
  30. void SLPopFront(SL* ps);
  31.  
  32. //中间的插入
  33. //在pos位置插入数据
  34. void SLInsert(SL* ps, int pos, SLDataType x);
  35. //中间的删除
  36. //删除pos位置的数据
  37. void SLErase(SL* ps, int pos);
  38.  
  39. //查找
  40. int SLFind(SL* ps, SLDataType x);

  2、SeqList.c

  1. #include "SeqList.h"
  2.  
  3. //打印
  4. void SLPrint(SL* ps)
  5. {
  6. 	assert(ps);
  7. 	for (int i = 0; i < ps->size; i++)
  8. 	{
  9. 		printf("%d ", ps->a[i]);
  10. 	}
  11. 	printf("\n");
  12. }
  13.  
  14.  
  15. //初始化
  16. void SLInit(SL* ps)
  17. {
  18. 	assert(ps);
  19. 	ps->a = NULL;
  20. 	ps->size = 0;
  21. 	ps->capacity = 0;
  22. }
  23.  
  24. //销毁
  25. void SLDestory(SL* ps)
  26. {
  27. 	assert(ps);
  28. 	//if (ps->a != NULL)
  29. 	if (ps->a)
  30. 	{
  31. 		free(ps->a);
  32. 		ps->a = NULL;
  33. 		ps->capacity = 0;
  34. 		ps->size = 0;
  35. 	}
  36. }
  37.  
  38. void SLCheckCapacity(SL* ps)
  39. {
  40. 	assert(ps);
  41. 	//扩容
  42. 	if (ps->size == ps->capacity)
  43. 	{
  44. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  45. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
  46. 		if (tmp == NULL)
  47. 		{
  48. 			perror("realloc fail");
  49. 			exit(-1);
  50. 		}
  51. 		ps->a = tmp;
  52. 		ps->capacity = newCapacity;
  53. 	}
  54. }
  55. //尾插 O(1)
  56. void SLPushBack(SL* ps, SLDataType x)
  57. {
  58. 	assert(ps);
  59. 	SLCheckCapacity(ps);
  60. 	ps->a[ps->size] = x;
  61. 	ps->size++;
  62. }
  63. //尾删
  64. void SLPopBack(SL* ps)
  65. {
  66. 	assert(ps);
  67. 	//暴力检查
  68. 	assert(ps->size > 0);
  69. 	ps->size--;
  70. }
  71.  
  72. //头插 O(N)
  73. void SLPushFront(SL* ps, SLDataType x)
  74. {
  75. 	assert(ps);
  76. 	//检查容量够不够
  77. 	SLCheckCapacity(ps);
  78.  
  79. 	//挪动数据
  80. 	int end = ps->size - 1;
  81. 	while (end >= 0)
  82. 	{
  83. 		ps->a[end + 1] = ps->a[end];
  84. 		end--;
  85. 	}
  86. 	ps->a[0] = x;
  87. 	ps->size++;
  88. }
  89. //头删
  90. void SLPopFront(SL* ps)
  91. {
  92. 	assert(ps);
  93. 	assert(ps->size > 0);
  94. 	//挪动数据
  95. 	int begin = 1;
  96. 	while (begin < ps->size)
  97. 	{
  98.     	ps->a[begin - 1] = ps->a[begin];
  99. 		begin++;
  100. 	}
  101. 	//暴力检查
  102. 	ps->size--;
  103. }
  104.  
  105. //在pos的位置插入数据
  106. void SLInsert(SL* ps, int pos, SLDataType x)
  107. {
  108. 	assert(ps);
  109. 	assert(pos >= 0);
  110. 	assert(pos <= ps->size);
  111. 	//检查容量够不够
  112. 	SLCheckCapacity(ps);
  113. 	int end = ps->size - 1;
  114. 	while (end >= pos)
  115. 	{
  116. 		ps->a[end + 1] = ps->a[end];
  117. 		end--;
  118. 	}
  119. 	ps->a[pos] = x;
  120. 	ps->size++;
  121. }
  122. //在pos的位置删除数据
  123. void SLErase(SL* ps, int pos)
  124. {
  125. 	assert(ps);
  126. 	assert(pos >= 0);
  127. 	assert(pos < ps->size);
  128. 	//挪动数据覆盖
  129. 	int begin = pos + 1;
  130. 	while (begin < ps->size)
  131. 	{
  132. 		ps->a[begin - 1] = ps->a[begin];
  133. 		begin++;
  134. 	}
  135. 	ps->size--;
  136. }
  137.  
  138. //查找
  139. int SLFind(SL* ps, SLDataType x)
  140. {
  141. 	assert(ps);
  142. 	for (int i = 0; i < ps->size; ++i)
  143. 	{
  144. 		if (ps->a[i] == x)
  145. 		{
  146.             //找到
  147. 			return i;
  148. 		}
  149. 	}
  150.     //没找到
  151. 	return -1;
  152. }

  3、test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1	
  2. #include"SeqList.h"
  3. void menu()
  4. {
  5. 	printf("*******************************\n");
  6. 	printf("******  0.退出   1.打印  ******\n");
  7. 	printf("******  2.尾插   3.尾删  ******\n");
  8. 	printf("******  4.头插   5.头删  ******\n");
  9. 	printf("******  6.任意插 7.任意删******\n");
  10. 	printf("******  8.在pos位置插入  ******\n");
  11. 	printf("******  9.删除pos元素值  ******\n");
  12. 	printf("*******************************\n");
  13. }
  14.  
  15. int main()
  16. {
  17. 	int input = 1;
  18. 	SL s;
  19. 	SLInit(&s);	//创建一个顺序表
  20. 	while (input)
  21. 	{
  22. 		int pos = 0;
  23. 		SLDatatype x = 0;
  24. 		SLDatatype y = 0;
  25. 		menu();
  26. 		printf("请选择:>");
  27. 		scanf("%d", &input);
  28. 		switch (input)
  29. 		{
  30. 		case 0:
  31. 			printf("退出顺序表!\n");
  32. 			SLDestroy(&s);
  33. 			break;
  34. 		case 1:
  35. 			SLPrint(&s);
  36. 			break;
  37. 		case 2:
  38. 			printf("请输入一个值:>");
  39. 			scanf("%d", &x);
  40. 			SLPushBack(&s, x);
  41. 			break;
  42. 		case 3:
  43. 			SLPopBack(&s);
  44. 			break;
  45. 		case 4:
  46. 			printf("请输入一个值:>");
  47. 			scanf("%d", &x);
  48. 			SLPushFront(&s, x);
  49. 			break;
  50. 		case 5:
  51. 			SLPopFront(&s);
  52. 			break;
  53. 		case 6:
  54. 			printf("请输入下标和目标值:>");
  55. 			scanf("%d %d", &pos, &x);
  56. 			SLInsert(&s, pos, x);
  57. 			break;
  58. 		case 7:
  59. 			printf("请输入下标:>");
  60. 			scanf("%d", &pos);
  61. 			SLErase(&s, pos);
  62. 			break;
  63. 		case 8:
  64. 			printf("请输入要插入元素值和目标值:>");
  65. 			scanf("%d %d", &y, &x);
  66. 			SLInsert(&s, SeqListFind(&s, y), x);
  67. 			break;
  68. 		case 9:
  69. 			printf("请输入要删除元素值:>");
  70. 			scanf("%d", &y);
  71. 			SLErase(&s, SeqListFind(&s, y));
  72. 			break;
  73. 		default:
  74. 			printf("选择错误，请重新选择!\n");
  75. 			break;
  76. 		}
  77. 	}
  78. 	return 0;
  79. }

 本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。

  老铁们，记着点赞加关注哦!!!

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

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

  

闽ICP备14008679号