注册 登录
编程论坛 数据结构与算法

设单链表以非递减有序排列,设计算法删除值相同的多余的结点”求大神修改我的代码

玉垒浮云 发布于 2013-04-05 19:01, 1585 次点击
#include<iostream>
using namespace std;
template<class T>
struct Node//循环链表的结点结构体
{
    T data;
    Node<T>*next;
};
template<class T>
class list
{
    public:
        list();
        list(T a[],int n);//建立链表
        ~list();
        int Length(){return length;}
        Node<T>*Index(int i);//按位查找,返回i结点指
        void Delete();//删除操作
        void print();//遍历操作
    private:
        Node<T>*first;//建立头结点
        int length;//表的长度
};
template<class T>//创建一个空表
list<T>::list()
{
    first=new Node<T>;
    first->next=first;
    length=0;
}
template<class T>
list<T>::list(T a[],int n)
{
    Node<T>*s,*r;
    first=new Node<T>;//生成头结点,这一步必不可少,通用的
    r=first;//r也指向头指针,尾指针初始化
    for(int i=0;i!=n;++i)
    {
        //每个数组建立一个结点,赋值
        s=new Node<T>;
        s->data=a[i];
        r->next=s;//将每个节点链在一起
        r=s;
    }
    r->next=first;//尾部结点与头结点相连
    length=n;
}
template<class T>
list<T>::~list()//析构函数将循环链表的所有节点的存储空间释放
{
    Node<T>*q;
    while(!length)
    {
        q=first;
        first=first->next;
        delete q;
    }
    cout<<"链表已经删除"<<endl;
}

template<class T>
Node<T> *list<T>::Index(int i)//按位查找的方法
{
    Node<T> *p;
    p=first->next;
    if(i<0||i>length)
    {
        cout<<"位置"<<i<<"不对"<<endl;
        exit(1);
    }
    if(i==0)
        return first;
    for(int j=1;j<i;++j)
        p=p->next;
    return p;
}

template<class T>
void list<T>::Delete()
{
    Node<T>*q,*p,*s;
    q=new Node<T>;
    s=new Node<T>;
    p=first->next;
    q=p->next;
    s=p;
    for(int i=0;i!=length-1;++i)
        for(int j=1;j!=length;++j)
        {
        
            if(p->data==q->data)
            {
                s->next=q->next;
                delete q;
                length--;
            }
            s=q;
            q=q->next;
        }
}
template<class T>
void list<T>::print()//遍历操作
{
    Node<T>*p;
    p=first->next;
    while(p!=first)
    {
        cout<<p->data<<",";
        p=p->next;
    }
    cout<<endl;
}
void main()
{
    int a[]={11,44,44,44,55,66};
    list<int>mylist(a,6);
    mylist.print();
    cout<<"输出链表的长度"<<mylist.Length()<<endl;
    mylist.Delete();
    mylist.print();
    cout<<"链表的长度"<<mylist.Length()<<endl;
}




编译器没有提示错误,但是mylist.Delete()不能运行,不知道该怎么修改,求大神帮忙
11 回复
#2
玉垒浮云2013-04-05 19:02
貌似Delete错了,求大神修改
#3
玉垒浮云2013-04-05 21:53
大神呢,求助啊
#4
玉垒浮云2013-04-05 21:58
大神呢,求助啊
#5
不玩虚的2013-04-06 00:12
template<class T>
void list<T>::Delete()
{
    Node<T>*q,*p,*s,*t;
    t=new Node<T>;
    s=new Node<T>;
    p=first->next;
    q=first->next;
    //s=p;
    while(p!=first)
    {     s=p;
        if(p!=first)
         {p=p->next;
            if(p->data==s->data)
            {
                 q->next=s->next;
                 length--;   
            }
            else q=s;
         }
     else break;
    }

}//只可以删除,相邻有相同的,要删一个表中有相同的,你的那个算法不对。错了别介意
#6
不玩虚的2013-04-06 00:27
template<class T>
void list<T>::Delete()
{
    Node<T>*q,*p,*s,*t;
    t=new Node<T>;
    s=new Node<T>;
    p=first->next;
   
    //s=p;
    while(p!=first)
    {     s=p;
            q=p->next;
        while(q!=first)
        {    t=p;
            if(p->data==q->data)
            {    t->next=q->next;
                length--;
            }
            q=q->next;
        }
        p=p->next;
    }

}//再给你个,你看那个能达到你的要求,这个好像不是相邻的也能删,你参考下,错了别介意
#7
玉垒浮云2013-04-06 12:54
回复 5楼 不玩虚的
大神,把你的算法试了一下,是对的,但是只能删除相邻的啊,还是有欠缺的,我再试一下你楼下的那个
#8
玉垒浮云2013-04-06 12:58
回复 6楼 不玩虚的
这个也不对,如果我把之前给的数据换成{11,44.33,44,55,44},输出结果就是{11,44}了,就错了,如果是之前的额那个,所以算法还是有欠缺啊,不过真心谢谢啊
#9
不玩虚的2013-04-06 20:12
template<class T>
void list<T>::Delete()
{
    Node<T>*q,*p,*s,*t;
    t=new Node<T>;
    s=new Node<T>;
    p=first->next;
        
    while(p!=first)
    {        s=t=p;
            q=p->next;
        while(q!=first)
        {
            if(p->data==q->data)
            {   
                t->next=q->next;
                    length--;
            }
        else    t=q;
            q=q->next;
        }
        p=p->next;
    }

}//又帮你弄了下,你再试试,看行不,你试的时候数据多弄点,情况多考虑下,我昨晚赶时间给你弄的,不好意思啦,有问题再讨论下,你这个问题我正好也要学习下。
#10
玉垒浮云2013-04-06 22:22
回复 9楼 不玩虚的
这次可以了,我也懂了为何之前的那几次错了,谢谢啊
#11
玉垒浮云2013-04-06 22:24
这是正确的代码,给下次问同样问题的同学一个参考吧,感谢版主的帮助



#include<iostream>
 using namespace std;
 template<class T>
 struct Node//循环链表的结点结构体
 {
     T data;
     Node<T>*next;
 };
 template<class T>
 class list
 {
     public:
         list();
         list(T a[],int n);//建立链表
         ~list();
         int Length(){return length;}
         Node<T>*Index(int i);//按位查找,返回i结点指
         void Delete();//删除操作
         void print();//遍历操作
     private:
         Node<T>*first;//建立头结点
         int length;//表的长度
 };
 template<class T>//创建一个空表
 list<T>::list()
 {
     first=new Node<T>;
     first->next=first;
     length=0;
 }
 template<class T>
 list<T>::list(T a[],int n)
 {
     Node<T>*s,*r;
     first=new Node<T>;//生成头结点,这一步必不可少,通用的
     r=first;//r也指向头指针,尾指针初始化
     for(int i=0;i!=n;++i)
     {
         //每个数组建立一个结点,赋值
         s=new Node<T>;
         s->data=a[i];
         r->next=s;//将每个节点链在一起
         r=s;
     }
     r->next=first;//尾部结点与头结点相连
     length=n;
 }
 template<class T>
 list<T>::~list()//析构函数将循环链表的所有节点的存储空间释放
 {
     Node<T>*q;
     while(!length)
     {
         q=first;
         first=first->next;
         delete q;
     }
     cout<<"链表已经删除"<<endl;
 }
 
template<class T>
 Node<T> *list<T>::Index(int i)//按位查找的方法
 {
     Node<T> *p;
     p=first->next;
     if(i<0||i>length)
     {
         cout<<"位置"<<i<<"不对"<<endl;
         exit(1);
     }
     if(i==0)
         return first;
     for(int j=1;j<i;++j)
         p=p->next;
     return p;
 }
 
template<class T>
 void list<T>::Delete()
 {
     Node<T>*q,*p,*s,*t;
     t=new Node<T>;
     s=new Node<T>;
     p=first->next;
         
     while(p!=first)
     {        s=t=p;
             q=p->next;
         while(q!=first)
         {
             if(p->data==q->data)
             {   
                t->next=q->next;
                     length--;
            }
         else    t=q;
             q=q->next;
         }
         p=p->next;
     }
 
}//
 template<class T>
 void list<T>::print()//遍历操作
 {
     Node<T>*p;
     p=first->next;
     while(p!=first)
     {
         cout<<p->data<<",";
         p=p->next;
     }
     cout<<endl;
 }
 void main()
 {
     int a[]={1,2,6,5,3,4,6,3,5,4,2,3,1,2,4};
     list<int>mylist(a,15);
     mylist.print();
     cout<<"输出链表的长度"<<mylist.Length()<<endl;
     mylist.Delete();
     mylist.print();
     cout<<"链表的长度"<<mylist.Length()<<endl;
 }
#12
azzbcc2013-04-07 07:44
非递减有序,怎么可能不相邻?
1