【数据结构】顺序表-元素去重
- 数据元素
结点定义，复杂数据类型，可用作整体性的管理系统。如果单独研究某些数据，比如只看学号或成绩，那么直接使用int之类的简单数据类型亦可。对应修改：typedef int Elemtype;
typedef struct student{ //定义学生个体
char name[100]; //姓名
int num; //学号
} Student;
typedef Student Elemtype;
使用Elemtype做数据类型，对应修改为其他数据时更加便捷，增强代码复用性。
- 顺序表定义
整体性思维，顺序表整体包含数据部分和长度两个属性。数据部分采用指针的方式指向首个元素的地址，通过下标的方式进行访问与使用。
typedef struct { //定义顺序表的数据结构
Elemtype *p; //线性表首地址
int length; //当前的长度
} SeqList;
- 初始化顺序表
为顺序表申请存储空间，成功后将表长度属性置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; //初始表长度为0
return 0;
}
- 顺序表插入元素
向第k个位置前插入元素，那么对于长度为L.length的顺序表，可以插入的位置为1-L.length，所以判断非法位置时以此判断。
插入元素注意每个元素需往后挪一个位置，最后把k号位空出来。注意：必须先挪后面的元素，否则元素覆盖将出现数据丢失。
最后由于插入元素，顺序表长度++；
//向表尾插入元素
void InsertList(SeqList &L,Elemtype e) {
if(L.length >= MAXSIZE) //判断当前的顺序表是不是已经满了
return ;
L.p[L.length]=e; //如果没有满，就在顺序表的后面添加元素e
L.length++; //添加后顺序表长度+1
return;
}
//向第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++; //添加后顺序表长度+1
return;
}
- 遍历顺序表
循环一次遍历即可。倘若访问第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;
}
- 删除元素
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--; //删除后顺序表长度-1
return;
}
//删除重复值
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后面的所有的元素往前一位，覆盖掉j
for(int k=j;k<L.length;k++)
L.p[k]=L.p[k+1];
L.length--;
j--;
}
}
}
- 查找元素
查找方式：序号查找，按元素值进行查找。
按元素查找，需要遍历顺序表，依次比较，时间复杂度为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; //初始表长度为0
return 0;
}
//向表尾插入元素
void InsertList(SeqList &L,Elemtype e) {
if(L.length >= MAXSIZE) //判断当前的顺序表是不是已经满了
return ;
L.p[L.length]=e; //如果没有满，就在顺序表的后面添加元素e
L.length++; //添加后顺序表长度+1
return;
}
//向第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++; //添加后顺序表长度+1
return;
}
//遍历顺序表
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--; //删除后顺序表长度-1
return;
}
//删除重复值
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后面的所有的元素往前一位，覆盖掉j
for(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;
}