技術共有

データ構造 - シーケンステーブル

2024-07-12

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

シーケンステーブルの定義

線形主義者はい同じ特徴を持っていますのデータ要素の有限数列。

線形テーブルは、実際に広く使用されているデータ構造です。一般的な線形テーブルは次のとおりです。シーケンスリスト、リンクリスト、スタック、キュー、文字列...

の線形テーブル論理的にはい線状構造 、つまり連続した直線です。でもいつ物理的構造が必ずしも連続的であるとは限らない、線形テーブルが物理的に保存される場合、通常は配列と連鎖構造フォームに保存されます。

  • シーケンステーブルセクションです物理アドレスは連続している記憶装置データ要素を順番に格納するの線状構造、一般的に使用される配列ストレージ。

シーケンス テーブルはデータ要素もカプセル化します。追加、削除、確認、修正のインターフェース。

構造体を使用してシーケンス テーブルを設計する

  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) シーケンステーブルの初期化

シーケンスを表に入れますarr、サイズ、容量の初期化

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

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

void SLPrint(SL* ps) シーケンステーブル印刷

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

完全なコード

シーケンスリスト.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);

シーケンスリスト.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 などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便