【王道2023考研计算机数据结构复习指导课后代码题】——06.在递增有序的单链表中删除重复元素

• 一【题目类别】
• 二【题目来源】
• 三【题目描述】
• 四【解题思路】
• 五【时间频度】
• 六【代码实现】
• 七【程序测试】

• 单链表

• 本题目选自王道2023考研计算机数据结构复习指导40页中二、综合应用题之12题

• 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素,使表中不再有重复的元素,例如(7,10,10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。

• 这个题目与【王道2023考研计算机数据结构复习指导课后代码题】——02.在有序顺序表中删除重复元素几乎一样，但是由于一个是顺序表，一个是单链表，所以代码上稍有不同，都是利用数据有序的前提，值相同的元素是“连续”存储的，所以直接定义两个指针，将重复元素删除即可。要注意：顺序表与单链表删除数据元素的时间复杂度是不同的。而且顺序表是判断不同值时进行处理，而单链表是判断相同值时进行处理

• 时间复杂度： O ( n ) O(n) O(n)，其中 n n n为单链表长度
• 空间复杂度： O ( 1 ) O(1) O(1)

#define _CRT_SECURE_NO_WARNINGS


#include
#include


typedef struct LNode
{
	int data;
	struct LNode* next;
}Node, *Link;


void PrintLink_Del_Same(Link link)
{
	Node* p = link->next;
	while (p != NULL)
	{
		if (p->next != NULL)
		{
			printf("%d->", p->data);
		}
		else
		{
			printf("%d", p->data);
		}
		p = p->next;
	}
}


void Del_Same(Link L)
{
	Link p = L->next;
	Node* temp = (Node*)malloc(sizeof(Node));
	if (p == NULL)
	{
		return;
	}
	while (p->next != NULL)
	{
		temp = p->next;
		if (p->data == temp->data)
		{
			p->next = temp->next;
			free(temp);
		}
		else
		{
			p = p->next;
		}
	}
}


int main()
{
	Link link = (Link)malloc(sizeof(Node));
	link->next = NULL;
	Node* p = link;
	int len;
	printf("请输入单链表的长度：");
	scanf("%d", &len);
	printf("请输入单链表的元素：");
	for (int i = 0; i < len; i++)
	{
		int x;
		scanf("%d", &x);
		Node* temp = (Node*)malloc(sizeof(Node));
		temp->data = x;
		temp->next = NULL;
		p->next = temp;
		p = temp;
	}
	printf("初始单链表为：");
	PrintLink_Del_Same(link);
	printf("n");
	Del_Same(link);
	printf("删除重复元素后的单链表为：");
	PrintLink_Del_Same(link);
	printf("n");
	
	system("pause");
	
	return 0;
}