Condivisione della tecnologia

Struttura dei dati - tabella di sequenza

2024-07-12

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

Definizione di tavola sequenziale

linearlistn hanno le stesse caratteristicheDielemento datiDisequenza finita

La tabella lineare è una struttura dati ampiamente utilizzata nella pratica Le tabelle lineari comuni sono:Elenco di sequenze, elenco collegato, stack, coda, stringa...

tavola lineare inlogicamentestruttura lineare , cioè una linea retta continua.Ma quandoNon necessariamente continuo nella struttura fisica, quando una tabella lineare viene archiviata fisicamente, di solito lo èArray e strutture concatenatememorizzato nel modulo.

  • Tabella delle sequenzeÈ una sezioneGli indirizzi fisici sono consecutiviunità di stoccaggioMemorizzare gli elementi di dati in sequenzaDistruttura lineare, generalmente usatovettoremagazzinaggio.

La tabella di sequenza incapsula anche gli elementi di datiAggiungi, elimina, controlla e modificaDiinterfaccia.

Progettare una tabella di sequenza utilizzando una struttura

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

Varie interfacce per tabelle di sequenza

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

void SLInit(SL* ps) inizializzazione della tabella di sequenza

Metti la sequenza nella tabellaarr, dimensione, inizializzazione della capacità

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

void SLDestroy(SL* ps) distruzione della tabella di sequenza

  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) Stampa della tabella di sequenza

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

void CheckCapacity(SL* ps) controlla se c'è abbastanza spazio

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

void SLPushBack(SL* ps, SLDataType x) inserimento coda

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

void SLPushFront(SL* ps, SLDataType x) intestazione

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

void SLPopBack(SL* ps) eliminazione coda

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

void SLPopFront(SL* ps) eliminazione dell'intestazione

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

void SLINsert(SL* ps, int pos, SLDataType x) Inserisci i dati nella posizione specificata

Invece di sovrascrivere i dati originali, il risultato dell'inserimento dei dati provoca lo spostamento indietro di alcuni dati.

  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. //指定位置插入, 先把pos位置的数据整体 往后 移一位(arr[pos] 至 arr[size - 1]),再插入
  8. for (int i = ps->size - 1; i >= pos; i--)
  9. {
  10. ps->arr[i + 1] = ps->arr[i];//循环的最后情况:ps->arr[pos + 1] = ps->arr[pos]
  11. }
  12. ps->arr[pos] = x;
  13. ps->size++;
  14. }

void SLErase(SL* ps, int pos) elimina i dati nella posizione specificata

  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. //指定位置删除数据,让pos后面的数据往前移动(arr[pos+1] 至 arr[size -1]),覆盖要删除的数据
  8. for (int i = pos; i < ps->size - 1; i++)
  9. {
  10. ps->arr[i] = ps->arr[i + 1];//循环的最后情况:ps->arr[size - 2] = ps->arr[size - 1]
  11. }
  12. ps->size--;
  13. }

int SLFind(SL* ps, SLDataType x) Trova i dati specificati di tipo intero

Restituisce pedice

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

Codice completo

ElencoSeq.h

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

Elenco Seq.c

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

拜拜,下期再见😏

摸鱼ing😴✨🎞