删除无序顺序表中的重复元素

王道数据结构上有道题，删除无序的顺序表中重复元素，提示是用散列表，自己试着实现了一下

算法设计思想

关键之处在于利用散列表的冲突来判断元素是否存在重复。于是解决散列表冲突的方式只能用拉链法，不能用开放地址法。散列表有数组和多个链表组成。数组里存储的是对应单个链表的首地址，链表中数据域用存储同义词。通过散列函数找到对应位置，继而判断是否存在相同元素。

算法代码

void DeleteSame(Seqlist *L)
{
	int p = L->len;
	LNode *S;
	int H[M] = { 0 },k=0;//H[]为散列表中数组，k为删除元素后顺序表长度
	for (int i = 0, j; i < L->len; i++)
	{
		j = L->data[i] % p;
		if (H[j] == 0)//判断对应位置链表是否为空
		{
			S = (LNode*)malloc(sizeof(LNode));//创建同义词节点
			S->data = L->data[i];
			S->next = NULL;
			H[j] = S;
			L->data[k++] = L->data[i];//将与元素放入新表中
		}
		else//对应位置链表不为空
		{
			S = H[j];
			while(S != NULL)//判断同义词链表中是否有相同元素
			{
				if (S->data == L->data[i])
					break;
				S = S->next;
			}
			if (S == NULL)//没有相同元素
			{
				S = (LNode*)malloc(sizeof(LNode)); // 创建同义词节点
				S->data = L->data[i];
				S->next = H[j];
				H[j] = S;
				L->data[k++] = L->data[i];//将与元素放入新表中
			}
		}
	}
	L->len = k;
}

测试程序

#include<stdio.h>
#include<stdlib.h>
#define M 10
typedef struct {
	int data[M];
	int len;
}Seqlist;
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*Linklist;
void InitSeqlist(Seqlist *L);
void PrintList(Seqlist *L);
void DeleteSame(Seqlist *L);
int main() {
	Seqlist List;
	Seqlist *L = &List;
	InitSeqlist(L);
	printf("初始顺序表\n");
	PrintList(L);
	DeleteSame(L);
	printf("删除删除顺序表中重复元素\n");
	PrintList(L);
}
void DeleteSame(Seqlist *L)
{
	int p = L->len;
	LNode *S;
	int H[M] = { 0 },k=0;//H[]为散列表中数组，k为删除元素后顺序表长度
	for (int i = 0, j; i < L->len; i++)
	{
		j = L->data[i] % p;
		if (H[j] == 0)//判断对应位置链表是否为空
		{
			S = (LNode*)malloc(sizeof(LNode));//创建同义词节点
			S->data = L->data[i];
			S->next = NULL;
			H[j] = S;
			L->data[k++] = L->data[i];//将与元素放入新表中
		}
		else//对应位置链表不为空
		{
			S = H[j];
			while(S != NULL)//判断同义词链表中是否有相同元素
			{
				if (S->data == L->data[i])
					break;
				S = S->next;
			}
			if (S == NULL)//没有相同元素
			{
				S = (LNode*)malloc(sizeof(LNode)); // 创建同义词节点
				S->data = L->data[i];
				S->next = H[j];
				H[j] = S;
				L->data[k++] = L->data[i];//将与元素放入新表中
			}
		}
	}
	L->len = k;
}
void InitSeqlist(Seqlist *L)//初始化链表
{
	int n = 10;
	int a[10] = { 25,25,25,15,8,3,8,18,13,3 };//测试用顺序表
	for (int i = 0; i < n; i++) 
	{
		L->data[i] = a[i];
	}
	L->len = 10;
}
void PrintList(Seqlist *L)//打印链表
{
	for (int i = 0; i < L->len; i++)
	{
		printf("%d ", L->data[i]);
	}
	printf("\n");
}

测试结果

VS2017环境下