기술나눔

데이터 구조 - 시퀀스 테이블

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

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

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

무효 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 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편