Обмен технологиями

Структура данных — таблица последовательности

2024-07-12

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

Определение таблицы последовательности

линейный списокдаn имеют одинаковые характеристикиизэлемент данныхизконечная последовательность。

Линейная таблица — это структура данных, широко используемая на практике. Распространенными линейными таблицами являются:Список последовательностей, связанный список, стек, очередь, строка...

линейный стол влогическидалинейная структура , то есть непрерывная прямая линия.Но когдаНе обязательно непрерывная по физической структуре, когда линейная таблица физически хранится, она обычноМассивы и цепные структурыхранится в форме.

  • Таблица последовательностиЭто разделФизические адреса последовательныеединица храненияХраните элементы данных последовательноизлинейная структура, обычно используетсямножествохранилище.

Таблица последовательности также инкапсулирует элементы данных.Добавляйте, удаляйте, проверяйте и изменяйтеизинтерфейс.

Разработайте таблицу последовательности, используя структуру

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

Различные интерфейсы для таблиц последовательности

  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. ​

void SLInit(SL* ps) инициализация таблицы последовательностей

Запишите последовательность в таблицуобр., размер, инициализация емкости

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

void SLDstroy(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. }

void SLPrint(SL* пс) Печать таблицы последовательности

  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) проверяет, достаточно ли места

  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. }

void 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. }

void 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. }

void SLPopBack(SL* ps) удаление хвоста

  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. }

удаление заголовка void 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) Вставить данные в указанную позицию.

Вместо перезаписи исходных данных результат вставки данных приводит к перемещению некоторых данных назад.

  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) удаляет данные в указанном месте

  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) Найти указанные данные целочисленного типа.

Вернуть нижний индекс

  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. }

Полный код

SeqList.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);

SeqList.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😴✨🎞

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта