当前位置:   article > 正文

顺序表元素的多种删除方式——删除重复元素和删除掉所有相同元素_第1关:删除重复元素100任务要求评论15任务描述程序分析编程要求测试说明任务描述

第1关:删除重复元素100任务要求评论15任务描述程序分析编程要求测试说明任务描述

大家好,初来乍到请多关照~

最近老师给留的编程作业里有一道题让我相当困惑:题目是这个样子的:

任务描述

本关任务:

(1)使用将顺序表L中值为x的数据元素替换为y;

(2)此处假设线性表中的元素用于表示集合,不考虑线性表中元素的位置,移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

第一个替换元素的代码很简单,直接遍历顺序表里的元素,如果相同将其赋值为目标元素。

以下为replace_seq函数的代码:

  1. void replace_seq(PseqList L, int x, int y)
  2. {//将顺序表L中值为x的数据元素替换为y
  3. for (int i = 0; i < L->curNum; i++)
  4. {
  5. if (L->element[i] == x)
  6. {
  7. L->element[i] = y;
  8. }
  9. }
  10. }

PseqList L是一个顺序表,以下为顺序表的相关定义:

  1. typedef int DataType;
  2. struct seqList
  3. {//有3个数据成员
  4. int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM
  5. int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum
  6. DataType* element;//用于存放顺序线性表数据元素的连续空间的起始地址
  7. };
  8. typedef struct seqList* PseqList;
  9. typedef struct seqList* PNode;

当我看到第二问,刚开始,我以为他是这个意思:

所以我jio的:

如果要删除重复出现的元素话,那就用两个循环外循环从头 i=0 开始遍历,内循环从 i+1 开始遍历,一旦发现重复,则用删除元素的代码直接删除掉这个元素就好啦 (好轻松啊~♂)

以下为两个删除函数,按照下标位置删除和输入目标值删除重复元素

  1. int delete_seq(PseqList L, int x)
  2. {//在顺序表L中删除与参数x值相同的数据元素,返回删除数据元素的个数
  3. //可以使用之前已完成的操作
  4. int m = 0;
  5. for (int n = 0; n < L->curNum; n++)
  6. {
  7. if (L->element[n] == x)
  8. {
  9. deletePos_seq(L, n);
  10. m++;
  11. }
  12. }
  13. return m;
  14. }
  15. int deletePos_seq(PseqList L, int pos)
  16. {//在顺序表L中删除与下标pos处的数据元素,若pos非法,则返回-1;否则返回1
  17. if (pos<0 || pos>(L->curNum))
  18. {
  19. return -1;
  20. }
  21. else
  22. {
  23. for (int q = pos; q < L->curNum-1; q++)
  24. {
  25. L->element[q] = L->element[q+1];
  26. }
  27. L->curNum = L->curNum - 1;
  28. return 1;
  29. }
  30. }

所以那么我的第一个错误的想法实践应该为:

  1. void delDuplicate_seq(PseqList L)
  2. {//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
  3. //使用常规删除即可,已修改测试用例
  4. for (int i = 0; i < L->curNum; i++)
  5. for (int k = i + 1; k < L->curNum; k++)
  6. if (L->element[i] == L->element[k])
  7. deletePos_seq(L, int k);
  8. }

但是它的输出结果并不是我想的那样,当重复值为两个的时候它的运行结果总是正确的:

输入:1 2 3 3 2 1 4 4 5 5

输出:1 2 3 4 5 

但是当重复值为三个以上的时候,它的运行结果出乎意料:

输入:2 2 2 3 3 3

输出:2 2 3 3

原来它只可以删除一次!

但是为什么呢?我不禁陷入了沉思......

 

 因此我们要修改k的值,保证它在删除掉一个重复值之后退回到原来的元素位置,这样我们才可以保证它会遍历比较所有的元素。

  1. void delDuplicate_seq(PseqList L)
  2. {//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
  3. //使用常规删除即可,已修改测试用例
  4. for (int i = 0; i < L->curNum; i++)
  5. for (int k = i + 1; k < L->curNum; k++)
  6. if (L->element[i] == L->element[k])
  7. {
  8. deletePos_seq(L, int k);
  9. k--;
  10. }
  11. }

输入:1 2 2 8 1 5 5 5 9 2

输出:1 2 8 5 9

 这样我们就可以删除掉所有的重复值啦~

当时我兴高采烈的的点击提交时,我发现的的测试案例并没有通过,仔细一剖析案例,人傻了都....

原来是要删除掉所有的重复出现的元素!

悲伤,失望,懊悔瞬间涌上心头......(((φ(◎ロ◎;)φ)))

我被卡这里了!

但是我是不会服输哒!于是我便急匆匆的打开CSDN看看大佬们是怎么解决的,浏览过后我发现大多的删除案例都是删除重复的数字,可是要怎么删除第一次被重复的那个值呢?我思索了好久,题目规定是不可以用额外的数组空间的,(但是因为时间快要截止了,所以我当时就抱着试一试的想法去修改了一下)我打算要循环两个大循环,首先定义一个数组,在第一次循环时将被重复的值记录到一个数组中,同时利用temp值以便删除时的计数。不会进行删除操作。第二次循环会删掉重复的元素,运行到这里我们的结果仅仅是删除掉重复值,被重复值是仍然存在的,所以我们还要删除掉那个数组里保存的所有被重复元素,这样就会得到我们想要的结果。

  1. void delDuplicate_seq2(PseqList L)
  2. {//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
  3. //使用常规删除即可,已修改测试用例
  4. int num = L->curNum;
  5. int a[20] = { };
  6. int temp = 0;
  7. for (int i = 0; i < L->curNum; i++)
  8. {
  9. for (int k = i + 1; k < L->curNum; k++)
  10. {
  11. if (L->element[i] == L->element[k])
  12. {
  13. a[temp] = L->element[i];
  14. temp++;
  15. break;
  16. }
  17. }
  18. }
  19. for (int i = 0; i < L->curNum; i++)
  20. {
  21. for (int k = i + 1; k < L->curNum; k++)
  22. {
  23. if (L->element[i] == L->element[k])
  24. {
  25. deletePos_seq(L, k);
  26. k--;
  27. }
  28. }
  29. }
  30. for (int k = 0; k <num ; k++)
  31. {
  32. for (int m = 0; m < temp; m++)
  33. delete_seq(L, a[m]);
  34. }
  35. }

输入:1 1 1 1 1 

输出:

输入:5 5 5 6 7 1 2 7 6 10

输出:1 2 10

测试是过了,但是我感觉我的方法很笨,(本来人就不是很聪明

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