linklist.cpp

数据结构实验课中的所有实验程序

// Linklist.cpp : Defines the entry point for the console application.
//
#include "iostream.h"
#include "stdafx.h"
#include "Linklist.h"

template <class Type> ListNode<Type>::ListNode():link(NULL){}
template <class Type> ListNode<Type>::ListNode(const Type &item){
data=item; link = NULL;}
template <class Type> void ListNode<Type>::InsertAfter( ListNode<Type> *p){
                    p->link=link;link=p;
      }

template <class Type> ListNode<Type>*ListNode<Type>::GetNode(const Type&item,ListNode<Type> *next=NULL)
{ ListNode<Type>*newnode=new ListNode<Type>(item);
   newnode->link=next;
        return newnode;}

template <class Type> ListNode<Type>*ListNode<Type>::RemoveAfter(){

	  ListNode<Type> *tempptr =link;
  if(link==NULL) return NULL;
	  link = tempper->link;
	 return tempper;
}

template <class Type> List<Type>::~List()
{MakeEmpty();delete first;}

template <class Type> void List<Type>::MakeEmpty(){
ListNode<Type> *q;
while(first->link!=NULL){

  q=first->link;first->link =q->link;
  delete q;
}
last=first;
}

template <class Type> int List<Type>::Length()const{

ListNode<Type> *p=first->link; int count =0;
while(p!=NULL){p=p->link;count++;}
return count;
}

template <class Type> ListNode<Type>*List<Type>::Find(Type value){
  ListNode<Type> *p=first->link;
  while (p!=NULL&&p->data!=value) p=p->link;
  return p;

}

template <class Type> ListNode<Type>*List<Type>::Find(int i){

	if(i<-1) return NULL;
	if(i==-1) return first;
	ListNode<Type> *p=first->link;int j=0;
	while(p!=NULL&&j<i){p=p->link;j=j++;}
     return p;
}

template <class Type>int List <Type>::Insert(Type value,int i){

	 ListNode<Type> *p=Find(i-1);
	 if(p==NULL) return 0;
	 ListNode<Type>*newnode=GetNode(value,p->link);
	 if(p->link==NULL) last=newnode;
	 p->link=newnode;
	 return 1;

}

template <class Type> Type *List<Type>::Remove(int i){

  ListNode<Type>*p=Find(i-1),*q;
  if(p==NULL||p->link==NULL) return NULL;
  q=p->link;p->link=q->link;
  Type value =new Type (q->data);
  if(q==last) last=p;
  delete q;return &value;
}

  
  template <class Type> Type *List<Type>::Get(int i){
   ListNode<Type>*p=Find(i);
   if(p==NULL||p==first)return NULL;
   else return &p->data;}
  
   template <class Type> void List<Type>::Inverse() 
   {
     if (first==NULL) return;
	 ListNode<Type> *p=first->link, *pr=NULL;
	 while (p!=NULL){
	  first->link=pr;
	  pr=first;first=p;p=p->link;
	 }
   first->link=pr;
   } 
  template <class Type> Type *List<Type>::Max()
  {
    if(first->link==NULL) return NULL;
	ListNode<Type> *pmax=first->link,p=first->link->link;
	while(p!NULL){
	  if(p->data>pmax->data) pmax=p;
	  p=p->link;
	}
	  return pmax;
  }



  void main()

  { 
  
  }