list.h

来自「带表头结点的单链表 可完成基本的单链表操作 可查找删除第N个或值为X的结点 可删」· C头文件 代码 · 共 489 行

// list.h  -- 带有表头节点的单链表

#ifndef LIST_H
#define LIST_H

#include <iostream.h>
#include <math.h>

template<class Type> class List;  // 类List的前向声明
template<class Type> class ListIterator; // 类ListIterator的前向声明

template<class Type> class ListNode {  // 链表节点类ListNode的声明
	friend class List<Type>;  // List类作为友元类声明
	friend class ListIterator<Type>;  // ListIterator类作为友元类声明
	friend ostream& operator<<(ostream &, const List<Type> &);
public:	
	ListNode(const Type& = 0, ListNode<Type> * = 0);  // 给数据的构造函数	
	Type getData() const { return data; }
private:
	Type data;   // data
	ListNode<Type> *nextPtr; // next node in the list	
};

template<class Type> class List {  // 单链表类的定义	
	friend ostream& operator<<(ostream &, const List<Type> &);
	friend class ListIterator<Type>;
public:
	// 构造函数，建立一个只有表头的空链表	
	List() { lastPtr = firstPtr = new ListNode<Type>; } 
	List(const List<Type> &);  // 复制构造函数 
	~List();  // 析构函数
	List<Type>& operator=(const List<Type> &);  // 重载=运算符
	void makeEmpty();  // 将链表置为空表
	int length() const;  // 计算链表长度
	ListNode<Type> *findValue(const Type &value) const;  // 在链表中搜索含数据value的节点
	ListNode<Type> *findLocation(int i) const;  // 在链表中搜索第i个元素的地址
	bool insert(const Type& value, int i);  // 将新元素value插入在链表中第i个位置	
	void insertAtFront(const Type &);  // 将新元素插入为链表的第0个元素
	void insertAtBack(const Type &);  // 将新元素插入为链表的最后一个元素
	Type removeLocation(int i);  // 将链表中的第i个元素删去
	bool removeValue(const Type &value);  // 将链表中值为value的的第1个元素删去
	bool removeFromFront(Type &);  // 删除列表的第0个元素
	bool removeFromBack(Type &);  // 删除列表的最后一个元素
	Type get(int) const;  // 取出链表中的第i个元素
    Type max() const;//寻找最大值结点
	int findX(const Type &X) const;//统计单链表中具有给定值x的所有元素
	List<Type> make(Type *,int n);//根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中
	                       //各元素的次序相同，要求该程序的时间复杂性为O(n)
    void tidyup();//在非递减有序的单链表中删除值相同的多余结点
private:
	ListNode<Type> *firstPtr;  // 链表的表头指针
	ListNode<Type> *lastPtr; // 链表的表尾指针
	ListNode<Type> *getNewNode(const Type& = 0, ListNode<Type> * = 0);  // 创建新节点
};

// 链表游标类ListIterator的声明
template<class Type> class ListIterator {
public:
	ListIterator(const List<Type>& a) : list(a), currentPtr(a.firstPtr) { } 
	bool notNull() const;
	bool nextNotNull() const;
	ListNode<Type> *firstPtr();
	ListNode<Type> *next();
private:
	const List<Type>& list;  // 引用一个已有的列表
	ListNode<Type> *currentPtr;  // 指向list中的节点
};

// 构造函数：初始化数据和指针成员
template<class Type> ListNode<Type>::ListNode(const Type& value, ListNode<Type> *ptr)
{
	data = value;
	nextPtr = ptr;
}

// 类List的复制构造函数
template<class Type> List<Type>::List(const List<Type> &object) 
{
	lastPtr = firstPtr = new ListNode<Type>;

	ListNode<Type> *tempPtr = object.firstPtr->nextPtr;

	while (tempPtr != 0) { 
		ListNode<Type> *newNode = getNewNode(tempPtr->getData());
		lastPtr->nextPtr = newNode;
		lastPtr = newNode;		
		tempPtr = tempPtr->nextPtr;  // 循链搜索
	}
}

// 重载=运算符
template<class Type> List<Type>& List<Type>::operator=(const List<Type> &object)
{
	if (this == &object) 
		return *this;
	
	makeEmpty();

	if (firstPtr != 0)
		delete firstPtr; 

	firstPtr = lastPtr = new ListNode<Type>;

	ListNode<Type> *tempPtr = object.firstPtr->nextPtr;

	while (tempPtr != 0) {
		ListNode<Type> *newNode = getNewNode(tempPtr->getData());
		lastPtr->nextPtr = newNode;
		lastPtr = newNode;		
		tempPtr = tempPtr->nextPtr;  // 循链搜索
	}

	return *this;
}

// List类的析构函数
template<class Type> List<Type>::~List()
{
	makeEmpty();
	if (firstPtr != 0) {
		delete firstPtr;
		firstPtr = lastPtr = 0;
	}
}

// 将链表置为空表
template<class Type> void List<Type>::makeEmpty() 
{
	ListNode<Type> *tempPtr;
	while (firstPtr->nextPtr != 0) {  // 当链表不空时，删去链表中的所有节点
		tempPtr = firstPtr->nextPtr;
		firstPtr->nextPtr = tempPtr->nextPtr;
		delete tempPtr;  // 循链逐个删除，保留一个表头节点
	}

	lastPtr = firstPtr;
}

template<class Type> int List<Type>::length() const  // 计算带表头节点的单链表的长度
{
	int count = 0;
	ListNode<Type> *tempPtr = firstPtr->nextPtr;
	while (tempPtr != 0) {
		tempPtr = tempPtr->nextPtr;  // 循链，寻找链尾
		count ++;
	}

	return count;  
}

// 在链表中搜索含数据value的节点：搜索成功时，函数返回该节点的地址；否则返回0值
template<class Type> ListNode<Type>* List<Type>::findValue(const Type& value) const
{
	ListNode<Type> *tempPtr = firstPtr->nextPtr;
	while (tempPtr != 0 && tempPtr->data != value)
		tempPtr = tempPtr->nextPtr;

	return tempPtr;
}

// 在链表中搜索第i个元素的地址：若i < -1或i超出链表中节点个数时，则返回0
template<class Type> ListNode<Type>* List<Type>::findLocation(int i) const
{
	if (i < -1 || i > length())  
		return NULL;
	if (i == -1)
		return firstPtr;

	ListNode<Type> *tempPtr = firstPtr->nextPtr;
	int j = 0;
	while (tempPtr != 0 && j < i) {
		tempPtr = tempPtr->nextPtr;
		j++;
	}

	return tempPtr;
}

// 将新元素value插入到链表中第i个位置
template<class Type> bool List<Type>::insert(const Type& value, int i)
{
	ListNode<Type> *tempPtr = findLocation(i - 1);  // 定位第i-1个元素
	if (tempPtr == 0)  // 参数i的值不合理，插入失败
		return false;

	ListNode<Type> *newNode = getNewNode(value, tempPtr->nextPtr);  // 创建data为value的节点
	if ListNode<Type> *tempPtr = firstPtr->nextPtr;// 如果为最后一个元素
		lastPtr = newNode;
	tempPtr->nextPtr = newNode;

	return true;  // 插入成功
}

// 插入链表的第0个元素
template<class Type>
void List<Type>::insertAtFront(const Type &value)
{
	ListNode<Type> *newNode = getNewNode(value);

	newNode->nextPtr = firstPtr->nextPtr;
	firstPtr->nextPtr = newNode;
}

// 插入列表的最后一个元素
template<class Type>
void List<Type>::insertAtBack(const Type &value)
{
	ListNode<Type> *newNode = getNewNode(value);

	lastPtr->nextPtr = newNode;
	lastPtr = newNode;
}

// 创建data为value的节点
template<class Type> ListNode<Type>* List<Type>::getNewNode(const Type &value, ListNode<Type> *nextptr)
{
	ListNode<Type> *newNode = new ListNode<Type>(value, nextptr);

	return newNode;
}

// 将链表中的第i个元素删去，通过函数返回该元素。若i不合理，则返回0
template<class Type> Type List<Type>::removeLocation(int i)
{
	ListNode<Type> *tempPtr = findLocation(i - 1);
	ListNode<Type> *currntPtr;
	if (tempPtr == 0 || tempPtr->nextPtr == 0)  // i的值不合理或空表，返回0
		return 0;

	currntPtr = tempPtr->nextPtr; // 第i个节点（i >= 0)
	tempPtr->nextPtr = currntPtr->nextPtr;
	Type value = currntPtr->data;

	if (currntPtr == lastPtr)
		lastPtr = tempPtr;
	//cout<<"45555555"<<endl;
	delete currntPtr;
	//cout<<"666666666"<<endl;
	return value;
}

// 将链表中值为value的的第1个元素删去
template<class Type> bool List<Type>::removeValue(const Type &value)
{
	ListNode<Type> *tempPtr = findValue(value);

	if (tempPtr == 0) {   // 值为value的元素不存在
		cout << "Sorry, I cannot find the data " << value << endl;
		return false;
	}

	ListNode<Type> *currentPtr = firstPtr->nextPtr; 
	
	if (tempPtr == currentPtr) {  // tempPtr为第0个元素
		firstPtr->nextPtr = tempPtr->nextPtr;
		if (firstPtr->nextPtr == 0) {
			lastPtr = firstPtr;
			lastPtr->nextPtr = 0;
		}
	}	
	else {   // tempPtr不是第0个元素
		while (currentPtr->nextPtr != tempPtr)
			currentPtr = currentPtr->nextPtr;
		if (tempPtr == lastPtr){  // tempPtr是最后一个元素
			lastPtr = currentPtr;
			lastPtr->nextPtr = 0;			
		} 
		else {
			currentPtr->nextPtr = tempPtr->nextPtr;
		}       
	}

	delete tempPtr;	
    
	return true;    
}

// 删除链表的第0个元素
template<class Type> bool List<Type>::removeFromFront(Type &value)
{
	if (firstPtr->nextPtr == 0) {
		cout << "The List is empty\n";
		return false;
	}

	ListNode<Type> *tempPtr = firstPtr->nextPtr;
	firstPtr->nextPtr = tempPtr->nextPtr;
	value = tempPtr->data;

	if (firstPtr->nextPtr == 0)  // 链表只有一个元素
		lastPtr = firstPtr;
	delete tempPtr;

	return true;
}

// 删除链表的最后一个元素
template<class Type> bool List<Type>::removeFromBack(Type &value)
{
	if (firstPtr->nextPtr == 0) {
		cout << "The List is empty\n";
		return false;
	}

	ListNode<Type> *tempPtr = lastPtr;
	ListNode<Type> *currentPtr = firstPtr->nextPtr;

	if (currentPtr == lastPtr)   // 链表中只有一个元素
		lastPtr = firstPtr;
	else {
		while (currentPtr->nextPtr != lastPtr)
			currentPtr = currentPtr->nextPtr;

		lastPtr = currentPtr;		
	}

	lastPtr->nextPtr = 0;

	value = tempPtr->data;	
	delete tempPtr;

	return true;
}

// 取出链表中的第i（i >= 0）个元素
template<class Type> Type List<Type>::get(int i) const
{
	ListNode<Type> *tempPtr = findLocation(i);
	if (tempPtr == 0 || tempPtr == firstPtr) 
		return 0;
	
	return tempPtr->data;
	
}

// 重载运算符<<：输出List的内容
template<class Type> ostream& operator<<(ostream &output, const List<Type> &list)
{
	ListNode<Type> *tempPtr = list.firstPtr->nextPtr;
	
	
	while (tempPtr != 0) {
		output << tempPtr->data << " ";
		tempPtr = tempPtr->nextPtr;
	}

	return output;	
}

// 检查当前节点是否非空
template<class Type> bool ListIterator<Type>::notNull() const {
	if (currentPtr == 0)
		return false;
	else
		return true;
}

// 检查当前节点的下一个是否非空
template<class Type> bool ListIterator<Type>::nextNotNull() const {
	if (currentPtr != 0 && currentPtr->nextPtr != 0)
		return true;
	else
		return false;
}

// 返回指向链表List的表头节点的指针
template<class Type> ListNode<Type>* ListIterator<Type>::firstPtr() {
	if (list.firstPtr != 0 ) {
		currentPtr = list.firstPtr;
		return currentPtr;
	}
	else {
		currentPtr = 0;
		return 0;
	}
}

// 返回指向链表List的下一个节点的指针
template<class Type> ListNode<Type>* ListIterator<Type>::next() {
	if (currentPtr != 0 && currentPtr->nextPtr != 0) {
		currentPtr = currentPtr->nextPtr;
		return currentPtr;
	}
	else {
		currentPtr = 0;
		return 0;
	}
}

//通过一趟遍历在单链表中确定值最大的结点
template<class Type> Type List<Type>::max() const
{
    ListNode<Type> *tempPtr = firstPtr->nextPtr;
	ListNode<Type> a;
    a.data=tempPtr->data;
	while(tempPtr->nextPtr!=0)
    {
     tempPtr = tempPtr->nextPtr;
     if(a.data< tempPtr->data)
    a.data=tempPtr->data;
	}
	return a.data;
}

//统计单链表中具有给定值x的所有元素
template<class Type> int  List<Type>::findX(const Type &X) const
{
	ListNode<Type> *tempPtr = firstPtr->nextPtr;
	int n=0;
	while (tempPtr != 0)
	{
      if( tempPtr->data ==X)
		  n++;
      tempPtr = tempPtr->nextPtr;
	}
	return n;
}

//根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元
//素的次序相同，要求该程序的时间复杂性为O(n)
template<class Type> List<Type> List<Type>::make(Type *a,int n)
{
    List<Type> A;
	int i;
	for(i=0;i<n;i++)
		A.insertAtBack(a[i]);
	return A;

}

//在非递减有序的单链表中删除值相同的多余结点
template<class Type> void List<Type>::tidyup()
{
	
	//int i,b,n;
	
    //Type c;
    //ListNode<Type> *tempPtr = firstPtr;
    //ListNode<Type> *in;
	//n=length();
    //for(i=0;i<n;i++)
	//{
	  //tempPtr = tempPtr->nextPtr;
      //c=tempPtr->data;
	  //in=tenpPtr;
	  //for(b=i+1;b<n;b++)
	  //{
        //in=in->nextPtr;
		//if(c==in->data)
		//{
		//	if(removeValue(c))
		//	{
		  //   b--;
	     	// n--;
		     //i--;
			//}
		//}
	  //}

	//}
	int a,b,n,i;
	Type c;
    n=length();
    ListNode<Type> *tempPtr = firstPtr->nextPtr;
	for(i=0;i<n-1;i++)
	{
		c=tempPtr->data;
        a=findX(c);
		if(a>1)
		{
		   
			for(b=0;b<a-1;b++)
			{
				
              if(removeValue(c))
			  {
				 cout<<"删除一个"<<c<<endl;
                 n--;
			  }
			}
          tempPtr = firstPtr->nextPtr;
		}
       tempPtr = tempPtr->nextPtr;
	}

}

#endif // LIST_H