概述

顺序表是一种基本的数据结构，它使用一段连续的内存空间存储数据元素。在实际应用中，我们经常需要处理顺序表中的重复元素，这就涉及到去重操作。

顺序表结构定义
 

#include<stdio.h>
#define ELEM_TYPE int    //适用每个类型
#define SXQ_INIT_SIZE 10 //初始容量
#define SXQ_INC_SIZE 2   //扩容时的倍数

typedef struct Seqlist{
      int ELEM_TYPE* arr;//有效数组
      int size;//数组有效个数
      int capacity;//数组容量
}Seqlist;

去重核心思路，基于顺序表已排序的前提，通过双指针（ i 和 j ）遍历比较，用k作为去重后元素的下标，实现原地去重。

void RemoveDuplicates(SeqList *p) {
   if (p->size <= 1) return;
    
   int i=0；//当前待判断元素起始位置
   int j=1; //遍历后续元素，与i位置元素作比较
   int k=0; //存储不重复的元素
   while(j < p->size){
        if(p->arr[i]==p->arr[j]{
             j++; //元素重复，j后移
        }
        else{
             p->arr[k]=p->arr[i];
             k++;
             i=j;
             j++;
        }
   }
   p->arr[k]=p->arr[i];
   p->size=k+1; //更新顺序表长度
}

图解解析

当arr[i]和arr[j]的值相同时，j后移，直到比较后两个值不同。

 

此时把arr[i]的值存入arr[k]中

 

k后移，用j来更新i，j后移，此时arr[i]和arr[j]的值不同

 

把arr[i]的值存入arr[k]中，k后移，用j来更新i，j后移。后续过程依次类推

总结

本文介绍了C语言实现顺序表去重的方法。双指针法不需要额外空间，空间复杂度O(1)，时间复杂度为O(n)。在实际应用中，应根据具体需求选择合适的方法。