单链表类.cpp

//**************************单链表类**************************

#include <iostream>
#define NIL NULL
using namespace std;
template<class T>
struct node {
    T data;
    node* next;
};
//所有下标均从1开始计数
template<class T>
class MyList {
protected:
    int n;
    node<T>* head;
    node<T>* tail;
public:
    MyList(){init();}  //构造函数, 结点数初始化为0
    void init() {  //初始化链表
        n = 0;
        head = new node<T>;
        head->next = NIL;
        tail = head;
    }
    void push(T val) {  //相当于push_back()
        node<T>* p = new node<T>;
        p->data = x;
        p->next = NIL;
        tail->next = p;
        tail = p;
        n++;
    }
    bool Insert(int pos,T val) {  //插在指定位置处
        if(pos>n)  return false;
        node<T>* p=new node<T>;
        p->data=val;
        node<T>* pr=prve(pos);
        p->next=pr->next;
        pr->next=p;
        n++;
        return true;
    }
    node<T>* prve(int pos) {  //寻找前驱结点
        pos--;
        node<T>* p=head;
        while(pos--) p=p->next;
        return p;
    }
    bool Delete(int pos) {  //删除结点
        if(pos>n)  return false;
        node<T>* pr=prve(pos);
        node<T>* p=head;
        while(pos--)  p=p->next;
        pr->next=p->next;
        delete p;
        n--;
        return true;
    }
    bool Modify(int pos,T val) {  //修改结点值
        if(pos>n)  return false;
        node<T>* p=head;
        while(pos--)  p=p->next;
        p->data=val;
        return true;
    }
    int Find(T val) {  //按值查找
        int cnt=0;
        node<T>* p=head->next;
        while(p!=NIL) {
            cnt++;
            if( p->data==val ) {
                return cnt;
            }
            p=p->next;
        }
        return -1;
    }
    T At(int pos) {  //查询pos位置上的值
        node<T>* p=head;
        while(pos--)  p=p->next;
        return p->data;
    }
    void Display() {  //展示链表内容
        node<T>* p = head->next;
        while(p!=NIL) {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    int how_many() {return n;} //查询结点数
    ~MyList() {  //析构函数
        node<T>* p=head;
        node<T>* q;
        while(p != NIL) {
            q=p->next;
            delete p;
            p=q;
        }
        n = 0;
    }
};


//*****************************复用代码******************************


//*****************************测试代码******************************

int main()
{
    //下面为测试
    MyList<string> v;
    for(int i=0;i<5;i++) {
        string s;
        cin >> s;
        v.push(s);
        v.Display();
    }
    for(int i=0;i<5;i++) {
        int pos;
        string s;
        cin>>pos>>s;
        if(v.Insert(pos,s))  cout<<"successfully insert"<<endl;
        else  cout<<"error"<<endl;
        v.Display();
    }
    cout<<endl;
    for(int i=0;i<5;i++) {
        int pos;
        cin>>pos;
        if(v.Delete(pos))  cout<<"delete successfully"<<endl;
        else  cout<<"error"<<endl;
        v.Display();
    }
    cout<<endl;
    for(int i=0;i<5;i++) {
        int pos;
        string s;
        cin>>pos>>s;
        if(v.Modify(pos,s))  cout<<"modify successfully"<<endl;
        else  cout<<"error"<<endl;
        v.Display();
    }
    cout<<endl;
    for(int i=0;i<5;i++) {
        string val;
        cin>>val;
        if(v.Find(val)==-1)  cout<<"not found"<<endl;
        else  cout<<"found! "<<v.Find(val)<<endl;
    }
    for(int i=0;i<5;i++) {
        int pos;
        cin>>pos;
        cout<<v.At(pos)<<endl;
    }
    cout<<endl;
    v.Display();
    return 0;
}
//***************************测试代码*******************************