Code Bye

关于用链表实现一组数据的去重后排序

码拜
要求如下：输入一组数据，以-1结尾。将该组数据中相同的删去，再进行排序后输出，要求用链表实现。
本人的代码如下，总是出错，无法运行。
调试了一下感觉是空指针的问题，但这部分内容始终没太搞明白应该怎么弄…… 
#include<iostream>
using namespace std;
struct Node
{
	int content;
	Node *next;
};
Node *input()
{
	Node *h=NULL;//从表头插入数据
	int x;
	cin>>x;
	while(x!=-1)
	{
		Node *p=new Node;
		p->content=x;
		p->next=h;
		h=p;
		cin>>x;
	}
	return h;
}
void sort(Node *h)//排序
{
	for(Node *p=h;p!=NULL;p=p->next)
	{
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content>p->content)
			{
				int temp=q->content;
				q->content=p->content;
				p->content=temp;
			}
		}
	}
}
void output(Node *h)
{
	for(Node *p=h;p!=NULL;p=p->next)
		cout<<p->content<<",";
	cout<<endl;
}
void remove(Node *h)
{
	while(h!=NULL)
	{
		Node *p=h;
		h=h->next;
		delete p;
	}
}
int main()
{
	Node *h=NULL;
	h=input();
	for(Node *p=h;p!=NULL;p=p->next)//查重
	{
		Node *r=p;
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content!=p->content)
				r=q;//循环查找q的前一个结点
			if((r!=NULL)&&(p->content=q->content))//找到相同的，删除结点
			{
				r->next=q->next;
				delete q;
			}
		}
	}
	sort(h);
	output(h);
	delete(h);
	return 0;
}
解决方案

2

if((r!=NULL)&&(p->content=q->content))应该是if((r!=NULL)&&(p->content==q->content)) 
#include<iostream>
using namespace std;
struct Node
{
	int content;
	Node *next;
};
Node *input()
{
	Node *h=NULL;//从表头插入数据
	int x;
	cin>>x;
	while(x!=-1)
	{
		Node *p=new Node;
		p->content=x;
		p->next=h;
		h=p;
		cin>>x;
	}
	return h;
}
void sort(Node *h)//排序
{
	for(Node *p=h;p!=NULL;p=p->next)
	{
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content>p->content)
			{
				int temp=q->content;
				q->content=p->content;
				p->content=temp;
			}
		}
	}
}
void output(Node *h)
{
	for(Node *p=h;p!=NULL;p=p->next)
		cout<<p->content<<",";
	cout<<endl;
}
void remove(Node *h)
{
	while(h!=NULL)
	{
		Node *p=h;
		h=h->next;
		delete p;
	}
}
int main()
{
	Node *h=NULL;
	h=input();
	for(Node *p=h;p!=NULL;p=p->next)//查重
	{
		Node *r=p;
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content!=p->content)
				r=q;//循环查找q的前一个结点
			if((r!=NULL)&&(p->content==q->content))//找到相同的，删除结点
			{
				r->next=q->next;
				delete q;
			}
		}
	}
	sort(h);
	output(h);
	delete(h);
	return 0;
}

26

引用:
Quote: 引用:

if((r!=NULL)&&(p->content=q->content))应该是if((r!=NULL)&&(p->content==q->content))
已修改，仍不能运行

这样改呢：

#include<iostream>
using namespace std;
struct Node
{
	int content;
	Node *next;
};
Node *input()
{
	Node *h=NULL;//从表头插入数据
	int x;
	cin>>x;
	while(x!=-1)
	{
		Node *p=new Node;
		p->content=x;
		p->next=h;
		h=p;
		cin>>x;
	}
	return h;
}
void sort(Node *h)//排序
{
	for(Node *p=h;p!=NULL;p=p->next)
	{
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content>p->content)
			{
				int temp=q->content;
				q->content=p->content;
				p->content=temp;
			}
		}
	}
}
void output(Node *h)
{
	for(Node *p=h;p!=NULL;p=p->next)
		cout<<p->content<<",";
	cout<<endl;
}
void remove(Node *h)
{
	while(h!=NULL)
	{   
		Node *p=h;
		h=h->next;
		delete p;
	}
}
int main()
{
	Node *h=NULL;
	h=input();
	for(Node *p=h;p!=NULL;p=p->next)//查重
	{   
		Node *r=p;
		for(Node *q=p->next;q!=NULL;q=q->next)
		{
			if(q->content!=p->content)
				r=q;//循环查找q的前一个结点
			if((r!=NULL)&&(p->content==q->content))//找到相同的，删除结点
			{               
				r->next=q->next;
				delete q;
				q = r;
			}
		}
	}
	sort(h);
	output(h);
	delete(h);
	return 0;
}

24

去重的算法是错误
应该这么处理：
1）当不重复时，
前一个节点r 后移 一个节点；
当前节点q 后移一个节点；
2）当重复时候，
前一个节点 r 不动，从链上 取下 节点 q
方法是 r->next=q->next;
删除节点 q
指针 q 设置为 r 的下个节点 （即删除掉的节点的下个节点）
删除一个节点，有两个动作
第一个1个为 ，从链上取下，保持链表是完整的
第二个为 释放 节点的内存
最后，为了保持 r 始终是 q 的前一个节点，
让 q 指针指向r 的下个节点
去重代码 中。
不变性为 q ==  r->next;
循环算法的一个重要原则，就是循环不变性
设计好循环不变性。则 每一轮循环，可以保证是正确进行的。
因此，循环不变性得到保障后，
可以证明，这个个循环的设计是正确的，没有错误的。

4

引用:
Quote: 引用:
Quote: 引用:
Quote: 引用:

if((r!=NULL)&&(p->content=q->content))应该是if((r!=NULL)&&(p->content==q->content))
已修改，仍不能运行

这样改呢：

啊可以了呢~可是为什么要加一步q = r呢？能解释一下吗？

否则你循环后是去取q->next取的是一个删除掉的值的next

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明关于用链表实现一组数据的去重后排序！