顺序表元素的多种删除方式

2023-09-21 07:55| 来源: 网络整理| 查看: 265

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

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

任务描述

本关任务：

（1）使用将顺序表L中值为x的数据元素替换为y；

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

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

以下为replace_seq函数的代码：

void replace_seq(PseqList L, int x, int y) {//将顺序表L中值为x的数据元素替换为y for (int i = 0; i < L->curNum; i++) { if (L->element[i] == x) { L->element[i] = y; } } }

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

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

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

所以我jio的：

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

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

int delete_seq(PseqList L, int x) {//在顺序表L中删除与参数x值相同的数据元素，返回删除数据元素的个数 //可以使用之前已完成的操作 int m = 0; for (int n = 0; n < L->curNum; n++) { if (L->element[n] == x) { deletePos_seq(L, n); m++; } } return m; } int deletePos_seq(PseqList L, int pos) {//在顺序表L中删除与下标pos处的数据元素，若pos非法，则返回-1；否则返回1 if (pos(L->curNum)) { return -1; } else { for (int q = pos; q < L->curNum-1; q++) { L->element[q] = L->element[q+1]; } L->curNum = L->curNum - 1; return 1; } }

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

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

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

输入：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 2 2 8 1 5 5 5 9 2

输出：1 2 8 5 9

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

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

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

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

我被卡这里了！

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

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

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章