linklist.h

大二半年的数据结构上机实验。包括链表

#include<iostream.h>
#include<stdlib.h>
template <class T> class LinkedList;      	//it is for friend definition
template <class T>                        	//T
class ListNode{
    friend class LinkedList<T>;           	//define friend
private:
    ListNode<T> *link;                    	//point to next object
    T data;                               	
public:
     ListNode(ListNode<T> *ptrlink = NULL)  //constructor ,for header node
       { link = ptrlink; }
     ListNode(const T& item, ListNode<T> *ptrlink = NULL) // for object node
       { data = item; link = ptrlink; }
    ~ListNode(void){}             		
};
template<class T>
class LinkedList{
public:
    LinkedList(){first==NULL;}; 
    ~LinkedList(){};
    LinkedList<T>& Creat();
    int Search(const T& x) const; 
    LinkedList<T>& Delete(int mark, T& x); 
    LinkedList<T>& Insert(const T& x,int mark);
    void Outputlist() const;
private:
    ListNode<T> *first;  //header pointer
};
template <class T>
LinkedList<T>& LinkedList<T>::Creat() 
{ 
    ListNode<T> *p, *rear;
    T value;	
    first = NULL;
    rear = NULL;
    cin >> value;   
    while (value != 0) {
        p= new ListNode<T>(value, NULL);
        if (first == NULL)  first = p;  	//the first node 
        else  rear->link = p;       		//other nodes 
        rear = p;        			//r points to new rear
        cin >> value;   
    }
    if (rear!=NULL)  rear->link = NULL; //the last node of a nonempty list 
}
template<class T>
int LinkedList<T>::Search(const T& x) const
{   int pos=0;
    ListNode<T> *p = first;
    while (p && p->data != x) 
     {p = p->link;
      pos++;
        }
    if(p) return pos+1;
    return 0;
}
template<class T>
LinkedList<T>& LinkedList<T>::Delete(int mark, T& x)
{
    if (mark< 1 || !first) {cout<<"删除失败"; return *this;}//no this object
   
    ListNode<T> *p=first;
    if (mark == 1) 	
        first = first->link; 
    else
    { //use q to record its predecessor
        ListNode<T> *q = first;
        for (int index = 1; index < mark - 1 && q; index++)
            q = q->link;
        if (!q||!q->link) {cout<<"删除失败"; return *this;}//no this object
        p = q->link; 	//store deleting node
        q->link = p->link; //break up the link
       } 	
     x=p->data;
    delete p;
    return *this;
}

template<class T>
LinkedList<T>& LinkedList<T>::Insert(const T& x,int mark)
{  if (mark< 0) {cout << "插入失败";return *this;}
   ListNode<T> *p=new ListNode<T>(),*q=first,*r;
   p->data=x;
   int i;
   for(i=0;i<mark-2;i++)
   {q=q->link;}
    r=q->link;
    q->link=p;
    p->link=r;
    return *this;
}

template<class T>
void LinkedList<T>::Outputlist() const
{ListNode<T> *p=first;
 while(p)
 {cout<<p->data<<endl;
  p=p->link;}
 }