list.cpp

Astar windows版本 Astar windows版本

#include "list.h"
template <class Type> List<Type>::~List()
{
	length = 0;
	delete pHead;
	pHead = NULL;
}
template <class Type> List<Type>::List()
{
	length = 0;
	pHead = NULL;
}
template <class Type> void List<Type>::Insert(int k, const Type & intnum)
{
	if(k==0)
	{
		if(length == 0)
		{
			pHead = new Node<Type>;
			pHead->contents = intnum;
			length++;
		}
		else
		{
			Node<Type> *p= new Node<Type>;
			p->contents = intnum;
			p->next=pHead;
			pHead=p;
			length++;
		}
	}
	else if(k==length)
	{
		Node<Type> *temp = pHead;
		for (int i=0;i<k-1;i++)
		{
			temp = temp->next;
		}
		Node<Type> *newNode = new Node<Type>;
		newNode->contents = intnum;
		newNode->next = NULL;
		temp->next = newNode;
		length++;
	}
	else
	{
		Node<Type> *temp = pHead;
		for (int i=0;i<k-1;i++)
		{
			temp = temp->next;
		}
		Node<Type> *newNode = new Node<Type>;
		newNode->contents = intnum;
		newNode->next = temp->next;
		temp->next = newNode;
		length++;
	}
}

template <class Type> void List<Type>::ShowListNode()
{
	if(length == 0)
	{
		cout<<"空表";
	}
	else
	{                                           
		Node<Type> *temp = pHead;
		for(int i=0;i<length;i++)
		{
			cout<<"节点"<<i+1<<": "<<temp->contents<<endl;
			if(i!=length-1)
			{
				temp = temp->next;
			}
		}
	}
}

template <class Type> void List<Type>::Delete(int k, Type & intnum)
{
	Node<Type> *temp = pHead;
	if(k==1 && k==length)
	{
		delete pHead;
		pHead = NULL;
	}
	else if(k==1)
	{
		pHead = pHead->next;
		delete temp;
	}
	else if(k==length)
	{
		for(int i=0; i<length-2; i++)
		{
			temp = temp->next;
		}
		delete temp->next;
		temp->next = NULL;
	}
	else
	{
		for (int i=0; i<k-1; i++)
		{
			temp = temp->next;
		}
		intnum = temp->contents;
		for(int i=k; i<length;i++)
		{
			temp->contents = temp->next->contents;
			if(i != length-1)
			{
				temp = temp->next;
			}
			else
			{
				delete temp->next;
				temp->next = NULL;
				break;
			}

		}
	}
	length--;
}
template <class Type> bool List<Type>::Find(int k, Type & intnum) const
{
	if(k > length)
		return false;
	else
	{
		Node<Type> *temp = pHead ;
		for (int i=0; i<k-1; i++)
		{
			temp = temp->next;
		}
		intnum = temp->contents;
		return true;
	}
}
template <class Type> int List<Type>::Search(const Type & intnum) const
{
		Node<Type> *temp = pHead;
		for (int i=0; i<length; i++)
		{
			if(temp->contents == intnum)
			{
				return i+1;
			}
			if(i != length-1)
			temp = temp->next;
		}
		return 0;
}
template <class Type> void List<Type>::Modify(int k,const Type &intnum)
{
	Node<Type> *temp = pHead ;
	for (int i=0; i<k-1; i++)
	{
		temp = temp->next;
	}
	temp->contents = intnum;
}