删除元素值相同的有序/无序单链表

柔光的暖阳◎ 2023-02-20 02:48 15阅读 0赞

## 删除带头结点的元素值有序排列的单链表 ##

注：  
(1).设置指针p最初指向第1个结点，当P的指针域不为空，  
既P不是最后一个结点时进入循环体内进行判断。  
(2).在循环过程中判断P所指的结点的后继q是否与P的数据域相同，  
如果相同则删除q；不同则说明了链表中没有与p的数据域相同的结点,则P后移；

#include"stdio.h"
    #include"stdlib.h"
    typedef struct node
    { 
    	int data;
    	struct node *next;//指向和自己类型相同的空间
    }link;
    
    void shuchu(link *head)//##################输出函数，带头结点的输出
    { 
    	link *r;
    	r=head->next;//打印的是带头结点的序列
    	while(r!=NULL)
    	{ 
    		printf("%d\t",r->data);
    		r=r->next;
    	}
    }
    
    link *drop(link *head)//##########################核心函数，删除相同的元素
    { 
    	link *q,*p;//定义了两个指针，q在前，p在后
    	q=head->next;
    	while(q->next)//q->next为真,也就是q->next!=null
    	{ 
    		p=q->next;
    		if(p->data==q->data)
    		{ 
    			q->next=p->next;
    			free(p);
    		}
    		else
    			q=q->next;
    	}
    	return head;
    }
    
    link *shuru(link *head)//##########################输入函数，采用尾插发的方式输入
    { 
    	int x;
    	link *t,*last;
    	t=(link *)malloc(sizeof(link));
    	head=t;
    	last=t;
    	t->next =NULL;
    	printf("请输入一个数:\n");
    	scanf("%d",&x);
    	for(;x!=0;)
    	{ 
    		t=(link *)malloc(sizeof(link));
    		t->data=x;
    		t->next =NULL;
    		last->next =t;//连接两个空间
    		last=t;使last指向刚申请的空间
    		scanf("%d",&x);
    	}
    	return head;
    }
    
    main()
    { 
    	link *head,*r;//r用于接收函数传回来的head的值
    	head=NULL;
    	r=shuru(head);
    	printf("未排序之前的序列是:\n");
    	shuchu(r);
    	r=drop(r);
    	printf("\n");
    	printf("排序之后的序列是:\n");
    	shuchu(r);
    	printf("\n");
    }

运行之后:  
![有序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70]

## 删除带头结点的元素值无序排列的单链表 ##

#include"stdio.h"
    #include"stdlib.h"
    typedef struct node
    { 
    	int data;
    	struct node *next;
    }link;
    
    void shuchu(link *head)//##################输出函数，带头结点的输出
    { 
    	link *r;
    	r=head->next;//打印的是带头结点的序列
    	while(r!=NULL)
    	{ 
    		printf("%d\t",r->data);
    		r=r->next;
    	}
    }
    
    link *drop(link *head)//##########################核心函数，删除相同的元素
    { 
    	link *r,*q,*p;
    	q=head->next;
    	while(q&&q->next)//q&&q->next都为真
    	{ 
    		r=q;
    		p=q->next;
    		while(p!=NULL)
    		{ 
    			if(p->data!=q->data)
    			{ 
    				r=p;
    				p=p->next;
    			}
    			else
    			{ 
    				r->next=p->next;
    				free(p);
    				p=r->next;
    			}
    		}
    		q=q->next;
    	}
    	return head;
    }
    
    link *shuru(link *head)//##########################输入函数，采用尾插发的方式输入
    { 
    	int x;
    	link *t,*last;
    	t=(link *)malloc(sizeof(link));//带头节点
    	head=t;
    	last=t;
    	t->next =NULL;
    	printf("请输入一个数:\n");
    	scanf("%d",&x);
    	for(;x!=0;)
    	{ 
    		t=(link *)malloc(sizeof(link));
    		t->data=x;
    		t->next =NULL;
    		last->next =t;
    		last=t;
    		scanf("%d",&x);
    	}
    	return head;
    }
    
    main()
    { 
    	link *head,*r;//r用于接收函数传回来的head的值
    	head=NULL;
    	r=shuru(head);
    	printf("未排序之前的序列是:\n");
    	shuchu(r);
    	r=drop(r);
    	printf("\n");
    	printf("排序之后的序列是:\n");
    	shuchu(r);
    	printf("\n");
    }

运行之后:  
![无序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70 1]

2020.6.22 下午

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622162754796.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622163015451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5,size_16,color_FFFFFF,t_70