Compartir tecnología

Estructura de datos: tabla de secuencia

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Definición de tabla de secuencia

lista linealSín tienen las mismas característicasdeelemento de datosdesecuencia finita。

La tabla lineal es una estructura de datos ampliamente utilizada en la práctica. Las tablas lineales comunes son:Lista de secuencia, lista enlazada, pila, cola, cadena...

mesa lineal enlógicamenteSíestructura lineal , es decir, una línea recta continua.Pero cuandoNo necesariamente continuo en estructura física., cuando una tabla lineal se almacena físicamente, generalmente esMatrices y estructuras encadenadas.almacenado en el formulario.

  • tabla de secuenciaes una seccionLas direcciones físicas son consecutivas.unidad de almacenamientoAlmacenar elementos de datos secuencialmentedeestructura lineal, generalmente usadoformaciónalmacenamiento.

La tabla de secuencia también encapsula los elementos de datos.Agregar, eliminar, verificar y modificardeinterfaz.

Diseñar una tabla de secuencia usando una estructura.

  1. //重定义类型，便于修改（int可修改为其他类型）
  2. typedef int SLDataType;
  3.  
  4. typedef struct SeqList
  5. {
  6. 	SLDataType* arr;
  7. 	int size;//有效数据元素个数
  8. 	int capacity;//空间大小
  9. }SL;定义的同时重命名顺序表

Varias interfaces para tablas de secuencia.

  1. ​
  2.  
  3. //顺序表初始化
  4. void SLInit(SL* ps);
  5. //顺序表销毁
  6. void SLDestroy(SL* ps);
  7. //顺序表打印
  8. void SLPrint(SL* ps);
  9.  
  10. //增 删 查 改操作
  11. //检查空间是否足够
  12. void CheckCapacity(SL* ps);
  13. //尾插
  14. void SLPushBack(SL* ps, SLDataType x);
  15. //头插
  16. void SLPushFront(SL* ps, SLDataType x);
  17. //尾删
  18. void SLPopBack(SL* ps);
  19. //头删
  20. void SLPopFront(SL* ps);
  21.  
  22. //指定位置插⼊数据
  23. void SLInsert(SL * ps, int pos, SLDataType x);
  24. //指定位置删除数据
  25. void SLErase(SL* ps, int pos);
  26. //找指定的数据
  27. int SLFind(SL* ps, SLDataType x);
  28.  
  29. ​
  30.  
  31. ​

Inicialización de la tabla de secuencia void SLInit(SL* ps)

Pon la secuencia en la tabla.arr, tamaño, inicialización de capacidad

  1. void SLInit(SL* ps)
  2. {
  3. 	ps->arr = NULL;
  4. 	ps->capacity = ps->size = 0;
  5. }

Destrucción de la tabla de secuencia void SLDestroy(SL* ps)

  1. void SLDestroy(SL* ps)
  2. {
  3. 	if (ps->arr)
  4. 	{
  5. 		free(ps->arr);
  6. 	}
  7. 	ps->arr = NULL;
  8. 	ps->capacity = ps->size = 0;
  9. }

vacío SLPrint(SL* ps) Impresión de tabla de secuencias

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

void CheckCapacity(SL* ps) comprueba si hay suficiente espacio

  1. void CheckCapacity(SL* ps)
  2. {
  3. 	//当有效数据个数size 与 有效空间大小capacity 相等时，说明空间不够了，要增容
  4. 	
  5. 	if (ps->capacity == ps->size)
  6. 	{
  7. 	    //增容，一般成倍增加，2~3倍较为合理
  8. 	    //用realloc函数，当ptr为空指针时，将分配一块新空间（调用realloc一样）
  9. 	    //此时又有一种特殊情况，一开始capacity为0时，怎样处理？
  10. 	    //三目操作符，为0时，将其赋值为4，不为0时，capacity*2
  11. 		int NewCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
  12. 		SLDataType* tep = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
  13. 		//判断增容成不成功
  14. 		if (tep == NULL)
  15. 		{
  16. 			perror("realloc");
  17. 			exit(1);
  18. 		}
  19. 		ps->arr = tep;
  20. 		//及时更新空间大小
  21. 		ps->capacity = NewCapacity;
  22. 	}
  23. }

inserción de cola vacía SLPushBack(SL* ps, SLDataType x)

  1. void SLPushBack(SL* ps, SLDataType x)
  2. {
  3. 	//ps不能为空指针
  4. 	assert(ps);
  5. 	//空间是否足够
  6. 	CheckCapacity(ps);
  7.  
  8. 	//尾插
  9. 	//ps->arr[ps->size] = x;
  10. 	//ps->size++;
  11. 	ps->arr[ps->size++] = x;
  12. }

encabezado vacío SLPushFront(SL* ps, SLDataType x)

  1. void SLPushFront(SL* ps, SLDataType x)
  2. {
  3. 	assert(ps);
  4. 	CheckCapacity(ps);
  5.  
  6. 	//把全部数据整体往后移动一位，把第一位置空出来，再插入数据
  7. 	for (int i = ps->size; i > 0; i--)
  8. 	{
  9. 		ps->arr[i] = ps->arr[i - 1];//循环的最后情况：ps->arr[1] = ps->arr[0]
  10. 	}
  11.  
  12. 	//头插
  13. 	ps->arr[0] = x;
  14. 	ps->size++;
  15. }

anular SLPopBack(SL* ps) eliminar cola

  1. void SLPopBack(SL* ps)
  2. {
  3. 	assert(ps);
  4. 	//删除的前提是有数据，得判断有效数据个数size是否为0
  5. 	assert(ps->size);
  6.  
  7. 	//尾删   
  8. 	//一种方法：ps->arr[--ps->size] = -1;
  9. 	//或者直接让size-1
  10. 	--ps->size;
  11. }

anular la eliminación del encabezado SLPopFront(SL* ps)

  1. void SLPopFront(SL* ps)
  2. {
  3. 	assert(ps);
  4. 	assert(ps->size);
  5.  
  6. 	//头删 把除第一位的数据整体往前移动一位，覆盖掉第一位的数据即可
  7. 	for (int i = 1; i < ps->size; i++)
  8. 	{
  9. 		ps->arr[i - 1] = ps->arr[i];//循环的最后情况：ps->arr[ps->size - 2] = ps->arr[ps->size - 1]
  10. 	}
  11. 	//及时更新size
  12. 	ps->size--;
  13. }

void SLInsert(SL* ps, int pos, SLDataType x) Inserta datos en la posición especificada

En lugar de sobrescribir los datos originales, el resultado de insertar datos hace que algunos datos retrocedan.

  1. void SLInsert(SL* ps, int pos, SLDataType x)
  2. {
  3. 	assert(ps);
  4. 	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size
  5. 	assert(pos >= 0 && pos <= ps->size);
  6. 	CheckCapacity(ps);
  7.  
  8. 	//指定位置插入， 先把pos位置的数据整体 往后 移一位（arr[pos] 至 arr[size - 1]），再插入
  9. 	for (int i = ps->size - 1; i >= pos; i--)
  10. 	{
  11. 		ps->arr[i + 1] = ps->arr[i];//循环的最后情况：ps->arr[pos + 1] = ps->arr[pos]
  12. 	}
  13. 	ps->arr[pos] = x;
  14. 	ps->size++;
  15. }

void SLErase(SL* ps, int pos) elimina datos en la ubicación especificada

  1. void SLErase(SL* ps, int pos)
  2. {
  3. 	assert(ps);
  4. 	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size - 1，为size就会越界
  5. 	assert(pos >= 0 && pos < ps->size);
  6. 	CheckCapacity(ps);
  7.  
  8. 	//指定位置删除数据，让pos后面的数据往前移动（arr[pos+1] 至 arr[size -1]）,覆盖要删除的数据
  9. 	for (int i = pos; i < ps->size - 1; i++)
  10. 	{
  11. 		ps->arr[i] = ps->arr[i + 1];//循环的最后情况：ps->arr[size - 2] = ps->arr[size - 1]
  12. 	}
  13. 	ps->size--;
  14. }

int SLFind(SL* ps, SLDataType x) Encuentra los datos especificados de tipo entero

Subíndice de retorno

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

código completo

Lista de secuencias.h

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5. #include"Contact.h"
  6.  
  7. //定义顺序表的结构
  8.  
  9. //动态顺序表
  10. //重定义类型，便于修改（int可修改为其他类型）
  11. typedef int SLDataType;
  12.  
  13. typedef struct SeqList
  14. {
  15. 	SLDataType* arr;
  16. 	int size;//有效数据元素个数
  17. 	int capacity;//空间大小
  18. }SL;
  19.  
  20. //顺序表初始化
  21. void SLInit(SL* ps);
  22. //顺序表销毁
  23. void SLDestroy(SL* ps);
  24. //顺序表打印
  25. void SLPrint(SL* ps);
  26.  
  27. //检查空间是否足够
  28. void CheckCapacity(SL* ps);
  29.  
  30. //增 删 查 改操作
  31. //尾部插入
  32. void SLPushBack(SL* ps, SLDataType x);
  33. //头部插入
  34. void SLPushFront(SL* ps, SLDataType x);
  35. //尾部删除
  36. void SLPopBack(SL* ps);
  37. //头部删除
  38. void SLPopFront(SL* ps);
  39.  
  40. //指定位置插⼊数据
  41. void SLInsert(SL * ps, int pos, SLDataType x);
  42. //指定位置删除数据
  43. void SLErase(SL* ps, int pos);
  44. //找指定的数据
  45. int SLFind(SL* ps, SLDataType x);

Lista de secuencias.c

  1. #include "SeqList.h"
  2.  
  3. //顺序表初始化
  4. void SLInit(SL* ps)
  5. {
  6. 	ps->arr = NULL;
  7. 	ps->capacity = ps->size = 0;
  8. }
  9.  
  10. //顺序表销毁
  11. void SLDestroy(SL* ps)
  12. {
  13. 	if (ps->arr)
  14. 	{
  15. 		free(ps->arr);
  16. 	}
  17. 	ps->arr = NULL;
  18. 	ps->capacity = ps->size = 0;
  19. }
  20.  
  21. void SLPrint(SL* ps)
  22. {
  23. 	assert(ps);
  24.  
  25. 	for (int i = 0; i < ps->size; i++)
  26. 	{
  27. 		printf("%d ", ps->arr[i]);
  28. 	}
  29. 	printf("n");
  30. }
  31.  
  32. //“增”的操作检查空间是否足够，不够就向内存申请空间
  33. void CheckCapacity(SL* ps)
  34. {
  35. 	//当有效数据个数size 与 有效空间大小capacity 相等时，说明空间不够了，要增容
  36. 	
  37. 	if (ps->capacity == ps->size)
  38. 	{
  39. 	    //增容，一般成倍增加，2~3倍较为合理
  40. 	    //用realloc函数，当ptr为空指针时，将分配一块新空间（调用realloc一样）
  41. 	    //此时又有一种特殊情况，一开始capacity为0时，怎样处理？
  42. 	    //三目操作符，为0时，将其赋值为4，不为0时，capacity*2
  43. 		int NewCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
  44. 		SLDataType* tep = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
  45. 		//判断增容成不成功
  46. 		if (tep == NULL)
  47. 		{
  48. 			perror("realloc");
  49. 			exit(1);
  50. 		}
  51. 		ps->arr = tep;
  52. 		//及时更新空间大小
  53. 		ps->capacity = NewCapacity;
  54. 	}
  55. }
  56.  
  57. //尾部插入
  58. void SLPushBack(SL* ps, SLDataType x)
  59. {
  60. 	//ps不能为空指针
  61. 	assert(ps);
  62. 	//空间是否足够
  63. 	CheckCapacity(ps);
  64.  
  65. 	//尾插
  66. 	//ps->arr[ps->size] = x;
  67. 	//ps->size++;
  68. 	ps->arr[ps->size++] = x;
  69. }
  70.  
  71. //头部插入
  72. void SLPushFront(SL* ps, SLDataType x)
  73. {
  74. 	assert(ps);
  75. 	CheckCapacity(ps);
  76.  
  77. 	//把全部数据整体往后移动一位，把第一位置空出来，再插入数据
  78. 	for (int i = ps->size; i > 0; i--)
  79. 	{
  80. 		ps->arr[i] = ps->arr[i - 1];//循环的最后情况：ps->arr[1] = ps->arr[0]
  81. 	}
  82.  
  83. 	//头插
  84. 	ps->arr[0] = x;
  85. 	ps->size++;
  86. }
  87.  
  88. //尾部删除
  89. void SLPopBack(SL* ps)
  90. {
  91. 	assert(ps);
  92. 	//删除的前提是有数据，得判断有效数据个数size是否为0
  93. 	assert(ps->size);
  94.  
  95. 	//尾删   
  96. 	//一种方法：ps->arr[--ps->size] = -1;
  97. 	//或者直接让size-1
  98. 	--ps->size;
  99. }
  100.  
  101. //头部删除
  102. void SLPopFront(SL* ps)
  103. {
  104. 	assert(ps);
  105. 	assert(ps->size);
  106.  
  107. 	//头删 把除第一位的数据整体往前移动一位，覆盖掉第一位的数据即可
  108. 	for (int i = 1; i < ps->size; i++)
  109. 	{
  110. 		ps->arr[i - 1] = ps->arr[i];//循环的最后情况：ps->arr[ps->size - 2] = ps->arr[ps->size - 1]
  111. 	}
  112. 	//及时更新size
  113. 	ps->size--;
  114. }
  115.  
  116. //指定位置插⼊数据(不是覆盖原先数据，插入数据的结果造成部分数据后移) pos是下标
  117. void SLInsert(SL* ps, int pos, SLDataType x)
  118. {
  119. 	assert(ps);
  120. 	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size
  121. 	assert(pos >= 0 && pos <= ps->size);
  122. 	CheckCapacity(ps);
  123.  
  124. 	//指定位置插入， 先把pos位置的数据整体 往后 移一位（arr[pos] 至 arr[size - 1]），再插入
  125. 	for (int i = ps->size - 1; i >= pos; i--)
  126. 	{
  127. 		ps->arr[i + 1] = ps->arr[i];//循环的最后情况：ps->arr[pos + 1] = ps->arr[pos]
  128. 	}
  129. 	ps->arr[pos] = x;
  130. 	ps->size++;
  131. }
  132.  
  133. //指定位置删除数据
  134. void SLErase(SL* ps, int pos)
  135. {
  136. 	assert(ps);
  137. 	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size - 1，为size就会越界
  138. 	assert(pos >= 0 && pos < ps->size);
  139. 	CheckCapacity(ps);
  140.  
  141. 	//指定位置删除数据，让pos后面的数据往前移动（arr[pos+1] 至 arr[size -1]）,覆盖要删除的数据
  142. 	for (int i = pos; i < ps->size - 1; i++)
  143. 	{
  144. 		ps->arr[i] = ps->arr[i + 1];//循环的最后情况：ps->arr[size - 2] = ps->arr[size - 1]
  145. 	}
  146. 	ps->size--;
  147. }
  148.  
  149. //查找整型指定数据
  150. int SLFind(SL* ps, SLDataType x)
  151. {
  152. 	assert(ps);
  153. 	assert(ps->size);
  154.  
  155. 	for (int i = 0; i < ps->size; i++)
  156. 	{
  157. 		if (ps->arr[i] == x)
  158. 		{
  159. 			return i;
  160. 		}
  161. 	}
  162. 	return -1;
  163. }

拜拜，下期再见😏

摸鱼ing😴✨🎞

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi información de contacto

Correo