#include <iostream>typedef int dataType;struct Node{    Node():data(0),pNextNode(NULL){} //结点构造函数    dataType data;    Node* pNextNode;};class List{private:    Node *head; //作为链表唯一的头指针    int size;   //链表长度public:    List(){head=new Node;size=0;}    bool isEmpty();                //判断是否空表    bool InsertList(int i,dataType elem);　　//i的指标从1开始，而不是从0开始    void PushList(dataType elem);        　 //在链表尾部添加元素    bool DeleteList(int i);        //删除指定位置的元素    void ClearList();            //清除整条链表    void DeleteRepetitiveData();//删除重复元素    void PrintList();            //按顺序输出链表    int GetSize();        Node* Fine(int i);            //找到第i个结点并返回该结点的指针    Node* FinePre(int i);        //找到第i个结点前的结点，返回指针};

#include "List.h"#include <iostream>#include <vector>using namespace std;//判断空表bool List::isEmpty(){    if(head==NULL)        return false;    else        return true;}//在第i位插入数据bool List::InsertList(int i,dataType elem){    if (i<1)        return false;    else if(head==NULL||i==1)//如果是空表    {        head->data=http://www.mamicode.com/elem;        size++;        return true;    }    else if (i>size)        //位标大于链表长度时，在尾部添加    {        PushList(elem);        return true;    }    else    {        Node *pre=Fine(i-1);        Node *follow=Fine(i);        Node *s=new Node;        //为新结点申请内存        pre->pNextNode=s;        //连接前结点        s->pNextNode=follow;    //连接后结点        s->data=http://www.mamicode.com/elem;        size++;        return true;    }}//在尾部添加元素void List::PushList(dataType elem){    if(head==NULL)    {        head=new Node;        head->data=http://www.mamicode.com/elem;        size++;    }    else    {        Node *cur=head;        while(cur->pNextNode)            cur=cur->pNextNode;        Node *s=new Node;        cur->pNextNode=s;        s->data=http://www.mamicode.com/elem;        size++;    }}//打印链表void List::PrintList(){    Node *cur=head;    while (cur!=NULL)    {        cout<<cur->data<<"  ";        cur=cur->pNextNode;    }    cout<<endl;}//sizeint List::GetSize(){    return size;}//找到第i个结点Node* List::Fine(int i){    if(i==1)        return head;    else    {        Node *cur=head;        for (int pos=1;pos<i;pos++)            cur=cur->pNextNode;        return cur;    }    }//找到i的前一个个结点Node* List::FinePre(int i){    if(i<2)    {        cout<<"参数必须大于等于2！"<<endl;        return NULL;    }    else if(i==2)        return head;    else        return Fine(i-1);}//删除第i个元素bool List::DeleteList(int i){    if (i<1||i>size)        //限制i的范围        return false;    else if(i==1)    {        Node *temp=head;        head=head->pNextNode;        delete temp;        size--;        return true;    }    else    {        Node *cur=this->Fine(i);        Node *pre=this->FinePre(i);        pre->pNextNode=cur->pNextNode; //重新连接结点        delete cur;        size--;        return true;    }}//清空整个链表void List::ClearList(){    Node *temp=head;    while (head!=NULL)    {        temp=head;        head=head->pNextNode;        delete temp;    }    size=0;}//删除重复元素void List::DeleteRepetitiveData(){    int flag=0;        //代码运行标志,0为未运行    if(size==1)        //只有一个元素时跳出        return;    Node *stand=head;//内循环结束后或者找到相同数据后才会指向下个结点    Node *cursor;    //游标    vector<int>storge;    for (int i=0;i<size;i++)    {            //用for循环是因为要得到被删除元素的位置                //采用握手式比较，算法的时间复杂度为O(n^2)        cursor=stand->pNextNode;        flag=0;        while(cursor!=NULL)        {            if(stand->data=http://www.mamicode.com/=cursor->data)            {                stand=stand->pNextNode;                flag=1;                //将重复的数据的下标降序保存起来                storge.insert(storge.begin(),i+1);                break;            }            else                cursor=cursor->pNextNode;        }            if(!flag)            stand=stand->pNextNode;    }    int itemp=storge.size();    while (itemp--)            {        this->DeleteList(storge.at(0));//提取下标，释放多余结点        storge.erase(storge.begin());    }    storge.clear();　　　　//释放vector内存}

#include "List.h"#include <iostream>using namespace std;void main(){    //List类测试代码    List list;    list.InsertList(1,1);    list.InsertList(5,3);    list.InsertList(2,2);    list.InsertList(4,4);        list.PrintList();        //打印这4个元素    cout<<"链表的长度为："<<list.GetSize()<<endl;    cout<<"现在删除第2个元素"<<endl;    list.DeleteList(2);            list.PrintList();            cout<<"现在清空链表"<<endl;    list.ClearList();        //清空链表    cout<<"输出空表："<<endl;    list.PrintList();                list.PushList(4);    list.PushList(1);    list.PushList(7);    list.PushList(1);    list.PushList(1);    list.PushList(2);    list.PushList(2);        //压入4 1 7 1 1 2 2    cout<<"输出链表新加入的元素："<<endl;        list.PrintList();    cout<<"删除相同元素后的链表为："<<endl;        list.DeleteRepetitiveData();    list.PrintList();}/*总结：1.链表类应该先写Fine()和FindPre()，再写插入和删除2.链表的结构应该给每一个结点加上一个下标。因为下标在  操作时再加上的话，元素跟下标是不统一的，  如果有元素被删除，下标将要重新分配。
　这就导致void List::DeleteRepetitiveData()不能用
　相对直接的方法在检测到重复数据时就删除数据，而要借助vector
  间接删除

*/