singlylinkedlist.h

回顾基础

        while (p!=NULL)  
        {
            rear->next = new Node<T>(p->data);   //创建结点链入rear结点之后
            p = p->next;
            rear = rear->next;                   //rear指向新的链尾结点
        }
    }
}

template <class T>
bool SinglyLinkedList<T>::equals(SinglyLinkedList<T> &list)   //比较两条单链表是否相等
{
    Node<T> *p=this->head, *q=list.head;
    while (p!=NULL && q!=NULL && p->data==q->data)
    {
        p = p->next;
        q = q->next;
    }
    return (p==NULL && q==NULL);
}


//以下是第4章例题，递归算法
/*
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(T value[], int n)    //构造由指定数组提供元素的单链表
{
    head = create(value,n,0);
}

template <class T>
Node<T>* SinglyLinkedList<T>::create(T value[], int n, int i)    //由指定数组构造单链表，递归算法
{
    Node<T> *p=NULL;
    if (i<n)
    {
        p = new Node<T>(value[i]);
        p->next = create(value, n, i+1);         //递归调用         
    }
    return p;
}

template <class T>
int SinglyLinkedList<T>::length()                //返回单链表长度
{
    return lengthFrom(head);
}

template <class T>
int SinglyLinkedList<T>::lengthFrom(Node<T>*p)   //返回从p结点开始的单链表长度，递归算法，私有函数
{
    if (p==NULL)
        return 0;
    return 1+lengthFrom(p->next);                //递归调用
}

template <class T>
void SinglyLinkedList<T>::print()                //输出单链表
{
    cout<<"(";
    printFrom(head);
    cout<<")\n";
}

template <class T>
void SinglyLinkedList<T>::printFrom(Node<T>*p)   //输出从p结点开始的单链表，递归算法，私有函数
{
    if (p!=NULL)
    {
        cout<<p->data;
        if (p->next!=NULL)
            cout<<", ";
        printFrom(p->next);                      //递归调用
    }
}
*/
//以下是第4章习题，递归算法
/*
template <class T>
SinglyLinkedList<T>::SinglyLinkedList(SinglyLinkedList<T> &list)   //以单链表list构造新的单链表，复制单链表
{
    this->head = copy(list.head);
}

template <class T>
Node<T>* SinglyLinkedList<T>::copy(Node<T> *p)   //复制单链表，递归算法，私有函数
{
    Node<T> *q=NULL;
    if (p!=NULL)
    {
        q = new Node<T>(p->data);
        q->next = copy(p->next); 
    }
    return q;
}
   
template <class T>
bool SinglyLinkedList<T>::equals(SinglyLinkedList<T> &list)   //比较两条单链表是否相等
{
    return equals(this->head, list.head);
}

template <class T>
bool SinglyLinkedList<T>::equals(Node<T> *p, Node<T> *q)   //比较两条单链表是否相等，递归算法，私有函数
{
    if (p==NULL && q==NULL)
        return true;
    if (p!=NULL && q!=NULL)
        return p->data==q->data && equals(p->next, q->next);
    return false;
}
*/





//以下第8章 8.2.1 顺序查找，散列表中用

template <class T>
Node<T>* SinglyLinkedList<T>::search(T value, Node<T>* start)    //从单链表start结点开始顺序查找指定元素
{                                                 //若查找成功返回结点，否则返回NULL
    if (isEmpty())
        return NULL;

    Node<T>* p=start;
    while (p!=NULL && p->data!=value)
        p = p->next;
    return p;
}

template <class T>
Node<T>* SinglyLinkedList<T>::search(T value)    //顺序查找指定元素
{
    return search(value, head); 
}

template <class T>
bool SinglyLinkedList<T>::contain(T value)       //以查找结果判断单链表是否包含指定元素
{
    return search(value)!=NULL;
}

template <class T>
bool SinglyLinkedList<T>::remove(T value)        //移去指定元素首次出现结点
{
    if (isEmpty())
        return false;
    
    Node<T> *p=head;
    if (head->data==value)
    {
        head = head->next;                       //头删除
        delete(p);
        return true;
    }
    
    Node<T>* front=head;
    p=front->next;
    while (p!=NULL && p->data!=value)            //中间/尾删除
    {
        front = p;
        p=p->next;
    }
    if (p!=NULL)
    {
        front->next = p->next;
        delete(p);
        return true;
    }
    return false;
}

/*
//以下是第2章习题
    public boolean replace(Object obj, E value)//将元素值为obj的结点值替换为value，O(n)
    {                                            //若替换成功返回true，否则返回false
        if (obj==null || value==null)
            return false;

        Node<E> p=this.head;
        while (p!=null)
        {
            if (obj.equals(p.data))
            {
                p.data = value;
                return true;
            }
            p = p.next;
        }
        return false;
    }
 
    public boolean replaceAll(Object obj, E value) //将所有元素值为obj的结点值替换为value，O(n)
    {                                            //若替换成功返回true，否则返回false
        boolean done=false;
        if (obj!=null && value!=null)
        {
            Node<E> p=this.head;
            while (p!=null)
            {
                if (obj.equals(p.data))
                {
                    p.data = value;
                    done = true;
                }
                p = p.next;
            }
        }
        return done;
    }
    
    public boolean removeAll(Object obj)         //将所有元素值为obj的结点删除
    {
        if (this.head==null || obj==null)
            return false;
        
        boolean done=false;
        while (this.head!=null && obj.equals(this.head.data))
        {
            this.head = this.head.next;          //头删除
            done = true;
        }
        Node<E> front=this.head, p=front.next;
        while(p!=null)
        {
            if (obj.equals(p.data))
            {
                front.next = p.next;             //删除p结点
                p = front.next;
                done = true;
            }
            else
            {
                front = p;
                p = p.next;
            }
        }
        return done;
    }


/* 第2章    //可行，但效率低，时间复杂度是O(n*n)。
    public String toString()
    {
        String str="{";
        if (this.length()!=0)
        {
            for(int i=0; i<this.length()-1; i++)
                str += this.get(i).toString()+", ";
            str += this.get(this.length()-1).toString();
        }
        return str+"}";
    }
*/