단일 체인 시트 생 성 및 일부 작업

4804 단어 데이터 구조J#
개인 이 만 든 클래스 로 단일 체인 표 의 기본 적 인 조작 을 실현 하 는 것 은 데이터 구조 지식 에 대한 약간의 복습 이 라 고 할 수 있다.


#ifndef TEMPLIST_H
#define TEMPLIST_H

#include <math.h>
#include<stdio.h>

template <class T>
class Node
{
public:
	T mydata;
	Node<T>* next;

	Node()                   //    
	{
		next=NULL;   //data      
	}
	Node(T data,Node<T>* next1=NULL)      //    ,         
	{
		mydata=data;
		next=next1;
	}
};

template <class T>
class SingleLinkedList             //    
{
public:
	Node<T>* head;             //   

	SingleLinkedList();        //               
	SingleLinkedList(T value[],int n);//               
	~SingleLinkedList();    //  

	bool isEmpty();       //         
	void concat(SingleLinkedList<T> &list);       // list          
	void clear();            //     
	bool remove(int i);

	Node<T>* insert(int i,T x);
	Node<T>* getNode(int i);
	T get(int i);
	int length();            //      
	T update(int i,T a);    //     
};

template <class T>
SingleLinkedList<T>::SingleLinkedList()
{
	this->head=NULL;
}

template <class T>
SingleLinkedList<T>::SingleLinkedList(T value[],int n)
{
	head=NULL;
	if(n>0)
	{
		head=new Node<T>(value[0]);
		Node<T>* rear = head;
		int i=1;
		while(i<n)            //              
		{
			rear->next = new Node<T>(value[i++]);
			rear = rear->next;
		}
	}
}

template <class T>
SingleLinkedList<T>::~SingleLinkedList()
{
	clear();
}

template <class T>
int SingleLinkedList<T>::length()
{
	int i=0;
	Node<T>* p=head;
	while(p!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}

template <class T>
Node<T>* SingleLinkedList<T>::insert(int i,T x)
{
	Node<T>* q=NULL;
	if(head==NULL||i<=0)
	{
		q=new Node<T>(x,head);
		head=q;
	}
	else
	{
		int j=0;
		Node<T>* p=head;
		while(p->next!=NULL&&j<i-1)
		{
			j++;
			p=p->next;
		}
		q=new Node<T>(x,p->next);
		p->next=q;
	}
	return q;
}

template <class T>
bool SingleLinkedList<T>::remove(int i)      // i      
{
	if(head!=NULL&&i>=0)
	{
		if(i==0)
		{
			Node<T>* q=head;
			head=head->next;
			delete q;
			return true;
		}
		else
		{
			Node<T>* p=getNode(i-1);
			if(p!=NULL&&p->next!=NULL)
			{
				Node<T>* q=p->next;
				p->next=q->next;
				delete q;
				return true;
			}
		}

	}
	return false;
}

template <class T>
T SingleLinkedList<T>::update(int i,T a)
{
	Node<T>* p=getNode(i);
	p->mydata+=a;
	return p->mydata;
}

template <class T>
Node<T>* SingleLinkedList<T>::getNode(int i)
{
	if(i<0)
		return NULL;
	int j=0;
	Node<T>* p=head;                //      
	while(p!=NULL&&j<i)
	{
		j++;
		p=p->next;
	}
	return p;
}

template <class T>
T SingleLinkedList<T>::get(int i)
{
	Node<T>* p=getNode(i);

	if(p!=NULL)
		return p->mydata;         //    
	throw"        ";
}


template <class T>
void SingleLinkedList<T>::clear()
{
	Node<T>* p=head;
	while(p!=NULL)
	{
		Node<T>* q = p;
		p=p->next;                   //       
		delete q;
	}
	head=NULL;
}

template <class T>
bool SingleLinkedList<T>::isEmpty()
{
	return head==NULL;
}

template <class T>
void SingleLinkedList<T>::concat(SingleLinkedList<T> &list)
{
	if(this->head==NULL)
		this->head=list.head;
	else{
		Node<T>* p = head;
		while(p->next!=NULL)          //        
		{
			p=p->next;
		}
		p->next=list.head;             //       
	}
	list.head=NULL;             //       ,     
}

#endif


좋은 웹페이지 즐겨찾기