Question

一道数据结构的题（C描述）请帮忙。急，谢谢

设计算法删除未排序单链表中的重复元素。

Answer 1

给一个简单的C程序,代码如下:
#include<malloc.h>
#include<stdio.h>
#include<string.h>
struct dt{
char ch;
struct dt *next;
};

void main(){
int n=0;
char c;
struct dt *head,*p1,*p2,*p,*pre;
p1=p2=(struct dt *)malloc(sizeof(struct dt));
printf("请输入每个结点的信息并以0结束\n");

//初始化单链表
scanf("%c",&c);
while(c!='0'){
n++;
p2->ch=c;
if(n==1) head=p2;
else{
p1->next=p2;
p1=p2;}

p2=(struct dt *)malloc(sizeof(struct dt));
scanf("%c",&c);
}
p1->next=NULL;

//删除相同结点元素的过程
p=head;
while(p!=NULL){
p2=p->next;
c=p->ch;
pre=p;
while(p2!=NULL){
if(p2->ch!=c)
pre=p2;
else
pre->next=p2->next;
p2=p2->next;
}
p=p->next;
}

//输出删除相同结点后的单链表信息
p=head;
while(p!=NULL){
printf("%c ",p->ch);
p=p->next;
}
printf("\n");
}

希望对你有帮助!

Answer 2

找个浪费空间的办法
先把链表的东西转存到数组
用qsort排序
排完序后，找出重复的值，并记录
遍历这个链表，保留碰到的第一个重复值，其余的全部删除

这样的效率是O(nlog(n))，比较浪费空间

Answer 3

我试试!!!