顺序表删除重复

编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。

函数原型如下:
void del_dupnum(SeqList *L)

相关定义如下:
struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist
SeqList;
提供代码
#include <stdio.h> #include <stdlib.h> #include "list.h" // 请不要删除,否则检查不通过 void
del_dupnum(SeqList *L) { }
 

参考代码v2.0.0  通过先将重复的化为min的,再用赋值处理,符合要求
/* 顺序表 删除重复 编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。 */ #include
<stdio.h> #include <stdlib.h> //#include "list.h" // 请不要删除,否则检查不通过 #define
ElemType int #define MAXSIZE 20 struct _seqlist { ElemType elem[MAXSIZE]; int
last; }; typedef struct _seqlist SeqList; void del_dupnum(SeqList* L){ int min
= L->elem[0]; int tmp = L->elem[0]; for (int i = 1; i <= L->last; i++) { if
(L->elem[i] == tmp) L->elem[i] = min; else tmp = L->elem[i]; } int p=1, q=1;
while (q <= L->last) { if (L->elem[q] != min) { L->elem[p] = L->elem[q]; p++; }
q++; } L->last = p-1; } void print(const SeqList* L) { int i = 0; for (i = 0; i
<= L->last; i++) { printf("%d ", L->elem[i]); } } int main() { SeqList L = {
{1, 2, 3, 7, 7, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 11},15 };//测试用例
del_dupnum(&L); print(&L);//打印看是否删除成功 return 0; }

辅助理解代码
#include <stdint.h> #include <stdio.h> int main() { int L[] = {1, 2, 3, 7, 7,
8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 11}; int size = sizeof(L) / sizeof(int); //
先找到最小的L[0] int min = L[0]; printf("size = %d\n", size); printf("L = ["); for
(int i = 0; i < size; i++) { printf("%d", L[i]); printf(i == size - 1 ? "]\n" :
", "); } printf(" "); for (int i = 0; i < size; i++) { if (i < 10) printf(L[i]
>= 10 ? "%d " : "%d ", i); else printf(L[i] >= 10 ? "%d " : "%d ", i); if (i ==
size - 1) puts(""); } // 只有一个元素就不用执行 if (size == 1) { printf("L = [%d]\n",
L[0]); return 0; } // 之前一个有效数据 int p = L[0]; for (int i = 0; i < size; i++) {
if (L[i] == p) L[i] = min; else p = L[i]; } // 输出 printf("size = %d\n", size);
printf("L = ["); for (int i = 0; i < size; i++) { // 忽略被标记的 if (i != 0 && L[i]
== min) continue; printf("%d", L[i]); printf(i == size - 1 ? "]\n" : ", "); }
printf(" "); for (int i = 0; i < size; i++) { // 忽略被标记的 if (i != 0 && L[i] ==
min) continue; if (i < 10) printf(L[i] >= 10 ? "%d " : "%d ", i); else
printf(L[i] >= 10 ? "%d " : "%d ", i); if (i == size - 1) puts(""); } // 最后整理一遍
p = 1; int q = 1; while (q < size) { if (L[q] != min) L[p++] = L[q]; q++; }
size = p; printf("size = %d\n", size); printf("L = ["); for (int i = 0; i <
size; i++) { // 忽略被标记的 if (i != 0 && L[i] == min) continue; printf("%d", L[i]);
printf(i == size - 1 ? "]\n" : ", "); } printf(" "); for (int i = 0; i < size;
i++) { // 忽略被标记的 if (i != 0 && L[i] == min) continue; if (i < 10) printf(L[i]
>= 10 ? "%d " : "%d ", i); else printf(L[i] >= 10 ? "%d " : "%d ", i); if (i ==
size - 1) puts(""); } return 0; }
参考代码v1.0.0采用冒泡排序,复杂度过高,不符合要求
/* 顺序表 删除重复 编写算法,在一非递减的顺序表L中,删除所有值相等的多余元素。要求时间复杂度为O(n),空间复杂度为O(1)。 */ /*
代码思路:借用冒泡排序的思想 */ #include <stdio.h> #include <stdlib.h> //#include "list.h" //
请不要删除,否则检查不通过 #define ElemType int #define MAXSIZE 10 struct _seqlist {
ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList; void
del_dupnum(SeqList* L) { int i = 0; int j = 0; while (i<L->last) { for (j = i;
j < L->last; ) { //比较是否相等 if (L->elem[i] == L->elem[j + 1]) { int k = 0;
//删除后一个相同的 for (k = j+1; k < L->last; k++) { L->elem[k] = L->elem[k + 1]; }
L->last--; } else { j++; } } i++; } } void print(const SeqList* L) { int i = 0;
for (i = 0; i <= L->last; i++) { printf("%d ", L->elem[i]); } } int main() {
SeqList L = { {0,0,0,3,3,5},4 };//测试用例 del_dupnum(&L); print(&L);//打印看是否删除成功
return 0; }

技术
©2019-2020 Toolsou All rights reserved,
C语言——qsort函数CSS实现溢出显示省略号网络层协议——ICMP协议C语言小游戏-俄罗斯方块Qt入门教程【基础控件篇】QCalendarWidget日历控件用python来控制wifi连接vue中input框只能输入数字Python内置函数C语言数据结构-顺序表删除重复V2.0.0abaqus质量缩放系数取值_ABAQUS的质量缩放