linkedlist.cpp

三： 针对带表头结点的单链表

#ifndef LINKDLIST_CLASS
#define LINKDLIST_CLASS
#include<iostream>
#include<cstdlib>
using namespace std;
#ifndef NULL
const int NULL=0;
#endif     //NULL

#include"node.h"

class LinkedList
{
	private:
	//数据成员：
		Node *front,*rear;        //表头和表尾指针
	    Node *prevPtr,*currPtr;   //记录表当前遍历位置的指针，由插入和删除操作更新
		int size;                    //表中的元素个数
		int position;                //当前元素在表中的位置序号。有函数Reset使用

	//函数成员：		
		Node *GetNode(int item,Node *ptrNext=NULL);//生成新节点，数据域为item,指针域为ptrNext		
		void FreeNode(Node *p);//释放节点

	public:
		LinkedList(void);    //构造函数

		Node *Locate(int n); //在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。
		Node *max(void);     //
		int  number(int x);
		void create(int *a,int n);   //按照数组生成连表
		void tidyup(void);   //在非递减有序的单链表中删除值相同的多余结点。

		int  OutSize(void);   //返回元素个数
		void InsertRear(int item);       //在表尾添加节点
		void OutAll(void);
		void ClearList(void);
};
Node *LinkedList::GetNode(int item,Node *ptrNext)
{
	Node *p;
	p=new Node(item,ptrNext);
    if(p==NULL)
	{ 
		cout << "Memory allocation failure!\n";
        exit(1);
	}
	return p;
}
void LinkedList::FreeNode(Node *p)
{
	delete p;
}
LinkedList::LinkedList(void)
{
	front=rear=NULL;
	prevPtr=currPtr=NULL;
	size=0;
	position=-1;
}
Node *LinkedList::Locate(int n)
{
	position=1;
	currPtr=front;
	prevPtr=NULL;
    if(n<=0)
		return NULL;
	while(position<n)
	{
       currPtr=currPtr->NextNode();
	   position++;
	}
	return currPtr;    
}
Node *LinkedList::max(void)
{
	prevPtr=currPtr=front;
	while(currPtr!=NULL)
	{
		if((currPtr->Num)>(prevPtr->Num))
			prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	return prevPtr;
}
int LinkedList::number(int x)
{
	prevPtr=NULL;
	currPtr=front;
	int sum=0;
	while(currPtr!=NULL)
	{
        if(currPtr->Num==x)
			sum++;
		currPtr=currPtr->NextNode();
	}
	return sum;
}
void LinkedList::create(int *a,int n)
{
	int i;
	if(front!=NULL)
	ClearList();
	for(i=0;i<n;i++)
	  InsertRear(a[i]);
}
void LinkedList::tidyup(void)
{
	Node *tempPtr;
    for(prevPtr=front;prevPtr!=rear;prevPtr=prevPtr->NextNode())
	{
		if(prevPtr==NULL) break;
        for(tempPtr=prevPtr;tempPtr!=rear;tempPtr=tempPtr->NextNode())
		{
			if(tempPtr==NULL) break;
            currPtr=tempPtr->NextNode();
            if(currPtr==NULL)break;															
            while( prevPtr->Num==currPtr->Num)
			{
				if(currPtr==rear)             //免得删掉rear指向的结点以后就找不到连表尾
				{
                    tempPtr->DeleteAfter();
					rear=tempPtr;
					currPtr=NULL;
                    size--;
				}
				else
				{
                    tempPtr->DeleteAfter();
                    size--;
                    currPtr=tempPtr->NextNode();
				}
				if(currPtr==NULL)break;
			}
		}
	}
}
int LinkedList:: OutSize(void)
{ return size;}
void LinkedList::InsertRear(int item)
{
	Node *newNode;
	newNode=GetNode(item,NULL);
	if(front==NULL)
		front=rear=newNode;
	else
	{
		rear->InsertAfter(newNode);
	    rear=rear->NextNode();
	}
    size++;
}
void LinkedList::OutAll(void)
{
	prevPtr=NULL;
	if(front==NULL)
	{ cout<<"空连表，没有任何数据"<<endl;}
	else
	for(currPtr=front;currPtr!=NULL;currPtr=currPtr->NextNode())
    { cout<<currPtr->Num<<"  ";}
}
void LinkedList::ClearList(void)
{	
	prevPtr=front;
	currPtr=front->NextNode();
	while(currPtr!=NULL)
	{
		FreeNode(prevPtr);
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	FreeNode(prevPtr);
	front=rear=NULL;
	currPtr=prevPtr=NULL;
	size=0;
	position=-1;
}

#endif   //LINKEDLIST_CLASS