【数据结构】顺序表-元素去重

1. 数据元素

结点定义，复杂数据类型，可用作整体性的管理系统。如果单独研究某些数据，比如只看学号或成绩，那么直接使用int之类的简单数据类型亦可。对应修改：typedef int Elemtype;

typedef struct student{ 	//定义学生个体 char name[100];	//姓名 int num;		//学号 
} Student;typedef Student Elemtype;

使用Elemtype做数据类型，对应修改为其他数据时更加便捷，增强代码复用性。

2. 顺序表定义

整体性思维，顺序表整体包含数据部分和长度两个属性。数据部分采用指针的方式指向首个元素的地址，通过下标的方式进行访问与使用。

typedef struct { 	//定义顺序表的数据结构Elemtype *p;	//线性表首地址  int length;		//当前的长度  
} SeqList; 

3. 初始化顺序表

为顺序表申请存储空间，成功后将表长度属性置0。注意C语言调用函数malloc申请，free进行释放，需加头文件。C++使用new与delete进行释放。

#include <stdlib.h>
// C语言
L.p = (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE);  
free(L.p);// C++写法
L.p=new Elemtype[MAXSIZE];			
delete L.p;

//初始化线性表  
int InitList(SeqList &L) {  //为顺序表的元素分配内存空间，大小为100个int的大小L.p = (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE);  if(!L.p)exit(0);		//overflow  分配失败L.length = 0;		//初始表长度为0return 0;  
}

4. 顺序表插入元素

向第k个位置前插入元素，那么对于长度为L.length的顺序表，可以插入的位置为1-L.length，所以判断非法位置时以此判断。

插入元素注意每个元素需往后挪一个位置，最后把k号位空出来。注意：必须先挪后面的元素，否则元素覆盖将出现数据丢失。

最后由于插入元素，顺序表长度++；

//向表尾插入元素  
void InsertList(SeqList &L,Elemtype e) {  if(L.length >= MAXSIZE)  //判断当前的顺序表是不是已经满了return ;L.p[L.length]=e;  		//如果没有满，就在顺序表的后面添加元素eL.length++;  			//添加后顺序表长度+1return;  
}//向第k个位置插入元素  
void InsertList_k(SeqList &L,int k,Elemtype e) {  if(L.length >= MAXSIZE)  //判断当前的顺序表是不是已经满了return ;if(k<1||k>L.length+1)	//插入位置不合法 return ; for(int j=L.length;j>=k;j--)L.p[j]=L.p[j-1];L.p[k-1]=e;L.length++;  			//添加后顺序表长度+1return;  
}

5. 遍历顺序表

循环一次遍历即可。倘若访问第k个位置，那么由于顺序表的特性（逻辑相邻，存储也相邻，可通过计算直接进行访问），通过下标即可访问对应位置。

Elemtype e=L.p[k-1];

//遍历顺序表  
void PrintList(SeqList &L) {  int i;  for(i=0;i<L.length;i++) { //循环遍历打印printf("[ %s - %d ] \n",L.p[i].name,L.p[i].num);  }  printf("\n");  return;  
}

6. 删除元素

1）删除第k个元素，需要把元素往向前移动，以保证逻辑相邻，存储上依旧相邻。

2）删除顺序表中的重复元素：4种策略
①桶排序，具有去重效果，取数时只取一次；
②先排序，再对相邻元素进行去重；
③申请额外的空间，依次访问原始顺序表中的元素，与新表中元素不重复即存到末端。
④分别取每一个元素，将后续表中所有重复元素进行删除处理。

方法1，2去重后有序。方法3，4去重后数据相对位置不变。
假设顺序表数据元素个数为n，数据取值范围为m。

方法1时间复杂度O(n)，空间复杂度O(m)。----受限于数据元素的取值范围，因为需要准备那么多个‘桶’。
方法2时间复杂度O(nlogn)，空间复杂度O(1)。----排序采用O(nlogn)的算法，去重时可以考虑双指针，i指向当前处理的数据，j单独记录非重复元素个数，i向后移动直到元素不重复，将i位置元素移动到j的位置，并j++。时间复杂度为O(1)。
方法3时间复杂度O(n^2)，空间复杂度O(n)。----双层循环比较原始顺序表与新顺序表中的每一个元素是否相同。
方法4时间复杂度O(n^3)，空间复杂度O(1)。----双层循环寻找重复元素位置，额外一层循环用于删除元素后的移动操作。

 //删除第k个元素 
void Delete_k(SeqList &L,int k) {  if(k<1||k>L.length)	//删除位置不合法 return ; for(int j=k-1;j<L.length-1;j++)L.p[j]=L.p[j+1];L.length--;  			//删除后顺序表长度-1return;  
}//删除重复值 
void Deletep(SeqList &L) {int i,j;int temp; for(i=0;i<L.length-1;++i) {		//循环整个顺序表for(j=i+1;j<L.length;j++)	//每次判断当前元素和它之后的所有元素是否重复if(L.p[i].num==L.p[j].num) {//如果有与i相同的元素j，则j后面的所有的元素往前一位，覆盖掉jfor(int k=j;k<L.length;k++)L.p[k]=L.p[k+1];L.length--; j--;}}   
}  

7. 查找元素

查找方式：序号查找，按元素值进行查找。
按元素查找，需要遍历顺序表，依次比较，时间复杂度为O(n)。

//查找第k个元素 
void find_k(SeqList L,int k, Elemtype &e) {  if(k<1||k>L.length)	//查找位置不合法 return ; e=L.p[k-1]; return;  
}//查找元素e的位置 
int find_e(SeqList L,Elemtype e) {  for(int i=0;i<L.length;i++)		//循环整个顺序表if(L.p[i].num==e.num) return i+1;  
}

• 完整代码：

#include <stdio.h>  
#include <stdlib.h>  
#define MAXSIZE 100
//线性顺序表  
typedef struct student{ 	//定义学生个体 char name[100];	//姓名 int num;		//学号 
} Student;typedef Student Elemtype;typedef struct { 	//定义顺序表的数据结构Elemtype *p;	//线性表首地址  int length;		//当前的长度  
} SeqList;  //初始化线性表  
int InitList(SeqList &L) {  //为顺序表的元素分配内存空间，大小为100个int的大小L.p = (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE);  if(!L.p)exit(0);		//overflow  分配失败L.length = 0;		//初始表长度为0return 0;  
}//向表尾插入元素  
void InsertList(SeqList &L,Elemtype e) {  if(L.length >= MAXSIZE)  //判断当前的顺序表是不是已经满了return ;L.p[L.length]=e;  		//如果没有满，就在顺序表的后面添加元素eL.length++;  			//添加后顺序表长度+1return;  
}//向第k个位置插入元素  
void InsertList_k(SeqList &L,int k,Elemtype e) {  if(L.length >= MAXSIZE)  //判断当前的顺序表是不是已经满了return ;if(k<1||k>L.length+1)	//插入位置不合法 return ; for(int j=L.length;j>=k;j--)L.p[j]=L.p[j-1];L.p[k-1]=e;L.length++;  			//添加后顺序表长度+1return;  
}//遍历顺序表  
void PrintList(SeqList &L) {  int i;  for(i=0;i<L.length;i++) { //循环遍历打印printf("[ %s - %d ] \n",L.p[i].name,L.p[i].num);  }  printf("\n");  return;  
}//删除第k个元素 
void Delete_k(SeqList &L,int k) {  if(k<1||k>L.length)	//删除位置不合法 return ; for(int j=k-1;j<L.length-1;j++)L.p[j]=L.p[j+1];L.length--;  			//删除后顺序表长度-1return;  
}//删除重复值 
void Deletep(SeqList &L) {int i,j;int temp; for(i=0;i<L.length-1;++i) {		//循环整个顺序表for(j=i+1;j<L.length;j++)	//每次判断当前元素和它之后的所有元素是否重复if(L.p[i].num==L.p[j].num) {//如果有与i相同的元素j，则j后面的所有的元素往前一位，覆盖掉jfor(int k=j;k<L.length;k++)L.p[k]=L.p[k+1];L.length--; j--;}}   
}  //查找第k个元素 
void find_k(SeqList L,int k, Elemtype &e) {  if(k<1||k>L.length)	//查找位置不合法 return ; e=L.p[k-1]; return;  
}//查找元素e的位置 
int find_e(SeqList L,Elemtype e) {  for(int i=0;i<L.length;i++)		//循环整个顺序表if(L.p[i].num==e.num) return i+1;  
}int main() {SeqList list;		//定义变量InitList(list);		//初始化线性表list，对list进行修改，这里是值传递int n;  			//定义要存放的数的个数scanf("%d",&n);		//输入n的值int i;Student temp;  for(i=0;i<n;i++) { //循环给顺序表输入数值scanf("%d",&temp.num);scanf("%s",temp.name);
//		InsertList_k(list,1,temp);		// 输入数据后逆序存储，相当于前插法InsertList_k(list,list.length+1,temp);	//输入数据顺序存储,相当于后插法}Deletep(list) ;//删除冗余数值printf("顺序表长度：%d\n",list.length);//打印删除后的顺序表的长度PrintList(list);//打印顺序表return 0;  
}