当前位置:   article > 正文

已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素

已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素
  1. #include<assert.h>
  2. typedef int SXBint;
  3. typedef struct SL
  4. {
  5. SXBint* a;
  6. int size;
  7. int capacity;
  8. }SLnode;
  9. void SeqLsitInit(SLnode* ps)
  10. {
  11. ps->a = NULL;
  12. ps->capacity = ps->size = 0;
  13. }
  14. void kuorong(SLnode* ps)
  15. {
  16. if (ps->capacity == ps->size)
  17. {
  18. int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  19. SXBint* temp = (SXBint*)realloc(ps->a, sizeof(SLnode) * Newcapacity);
  20. if (temp == NULL)
  21. {
  22. perror("error:");
  23. exit(1);
  24. }
  25. ps->a = temp;
  26. ps->capacity = Newcapacity;
  27. }
  28. }
  29. void SeqPushback(SLnode* ps, SXBint x)
  30. {
  31. kuorong(ps);
  32. ps->a[ps->size++] = x;
  33. }
  34. void Seq_dayin(SLnode ps)
  35. {
  36. for (int i = 0; i < ps.size; i++)
  37. {
  38. printf("%d->", ps.a[i]);
  39. }
  40. printf("NULL\n");
  41. }
  42. void deletes(SLnode* ps, int item) {
  43. int j = 0;
  44. for (int i = 0; i <= ps->size;i++) {
  45. if (ps->a[i] != item)
  46. {
  47. ps->a[j] = ps->a[i];
  48. ++j;
  49. }
  50. }
  51. ps->size = j - 1;
  52. }
  53. int main()
  54. {
  55. SLnode S;
  56. SeqLsitInit(&S);
  57. int n, num, item;
  58. printf("请输入顺序表的长度\n");
  59. scanf("%d", &n);
  60. printf("请输入顺序表的元素\n");
  61. for (int i = 0; i < n; i++)
  62. {
  63. scanf("%d", &num);
  64. SeqPushback(&S, num);
  65. }
  66. printf("顺序表的元素如下\n");
  67. Seq_dayin(S);
  68. printf("请输入item的值\n");
  69. scanf("%d", &item);
  70. deletes(&S, item);
  71. printf("删除item后\n");
  72. Seq_dayin(S);
  73. return 0;
  74. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/987443
推荐阅读
  

闽ICP备14008679号