Κοινή χρήση τεχνολογίας

Δομή δεδομένων - πίνακας ακολουθιών

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

Βάλτε τη σειρά στον πίνακα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. }

άκυρη εισαγωγή ουράς 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. }

άκυρη διαγραφή κεφαλίδας 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 κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα σταθμός τεκμηρίωσης προγραμματιστή για να μοιραστείτε ορισμένα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο