#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:
	//數(shù)據(jù)成員：
		Node *front,*rear;        //表頭和表尾指針
	    Node *prevPtr,*currPtr;   //記錄表當(dāng)前遍歷位置的指針，由插入和刪除操作更新
		int size;                    //表中的元素個數(shù)
		int position;                //當(dāng)前元素在表中的位置序號。有函數(shù)Reset使用

	//函數(shù)成員：		
		Node *GetNode(int item,Node *ptrNext=NULL);//生成新節(jié)點，數(shù)據(jù)域為item,指針域為ptrNext		
		void FreeNode(Node *p);//釋放節(jié)點

	public:
		LinkedList(void);    //構(gòu)造函數(shù)

		Node *Locate(int n); //在單鏈表中尋找第i個結(jié)點。若找到，則函數(shù)返回第i個結(jié)點的地址；若找不到，則函數(shù)返回NULL。
		Node *max(void);     //
		int  number(int x);
		void create(int *a,int n);   //按照數(shù)組生成連表
		void tidyup(void);   //在非遞減有序的單鏈表中刪除值相同的多余結(jié)點。

		int  OutSize(void);   //返回元素個數(shù)
		void InsertRear(int item);       //在表尾添加節(jié)點
		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指向的結(jié)點以后就找不到連表尾
				{
                    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<<"空連表，沒有任何數(shù)據(jù)"<<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