数据结构之链表（整型）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>

using namespace std;

struct node {
    int data;
    node *next;
    node() {};
    node(int n, node *p = NULL) : data(n), next(p) {};
};

class List {
public:
    node *head;
    int cnt;
    List() : head(NULL), cnt(0) {
        head = new node;
        head->next = NULL;
    }
    void Insert(int x) {
        int i = cnt;
        node *cur = head;
        node *temp = new node(x);
        for (int s = 0; s < i; s++)
            cur = cur->next;
        temp->next = cur->next;
        cur->next = temp;
        cnt++;
    }
    void Insert(int x, int i) {
        if (i > cnt) {
            cout << "in Insert,index is too big\n";
            return;
        }
        node *cur = head;
        node *temp = new node(x);
        for (int s = 0; s < i; s++)
            cur = cur->next;
        temp->next = cur->next;
        cur->next = temp;
        cnt++;
    }
    int find(int x, int after = -1) {
        int i;
        if (after >= cnt - 1) {
            cout << "in find, index after >=cnt-1\n";
            return -1;
        }
        node *cur = head->next;
        for (i = 0; i <= after; i++) {
            cur = cur->next;
        }
        for (i = after + 1; cur; cur = cur->next, i++) {
            if (cur->data == x) {
                return i;
            }
        }
        return -1;
    }
    void Delete(int i) {
        if (i >= cnt || i < 0) {
            cout << "in Delete, index is too big or too small\n";
            return;
        }
        node *pre = head;
        for (int s = 0; s < i; s++)
            pre = pre->next;
        node *temp = pre->next;
        pre->next = temp->next;
        delete temp;
        cnt--;
    }
    int empty() const {
        if (head == NULL || head->next == NULL)
            return 1;
        return 0;
    }
        void reverse(int i, int j) {
        if (i < 0 || j < i || j > cnt - 1) {
            cout << "in reverse,i and j is not suitable\n";
            return;
        }
        if (j == i)return;
        node *pHead, *pre, *old, *temp;
        /* pHead point to i-1 place, pre is the reversed list's first node,old is the not reversed list's first node
         ,temp is old 's next node */
        pHead = head;
        for (int s = 0; s < i; s++)// first move to the i place
            pHead = pHead->next;
        pre = pHead->next;
        old = pre->next;
        for (int count = 0; count < j - i && old; count++) {
            temp = old->next;
            old->next = pre;
            pre = old;
            old = temp;
        }
        pHead->next->next = old;
        pHead->next = pre;
        return;
    }

    void assign(const List &other) {//复制
        if (empty() == 0)
            clear();
        if (head == NULL)head = new node;
        node *other_cur, *cur;
        cur = head;
        cnt = other.cnt;
        for (other_cur = other.head->next; other_cur; other_cur = other_cur->next) {
            cur->next = new node(other_cur->data);
            cur = cur->next;
        }
    }



    void tailor(int i, int j) {
        if (i < 0 || j < i || j > cnt - 1) {
            cout << "in tailor,i and j is not suitable\n";
            return;
        }
        for (int s = 0; s < i; s++) {
            Delete(0);
        }
        while (cnt > j - i + 1) {
            Delete(cnt - 1);
        }
    }



    void delDuplicate() {//去重
        if (cnt <= 1)return;
        node *cur = head->next;
        int index;
        for (int i = 0; cur; cur = cur->next, i++) {
            index = find(cur->data, i);
            if (index != -1) {
                Delete(index);
            }

        }
    }


    void clear() {
        while (empty() == 0) {
            Delete(0);
        }
    }


    void puts() const {
        cout << "List:\n";
        if (head == NULL || head->next == NULL) {
            cout << "NULL";
            return;
        }
        for (node *cur = head->next; cur; cur = cur->next) {
            cout << cur->data << " ";
        }
        cout << endl;
    }

};

    void test() {//测试后几个函数
    int n;
    cout << "please tell me the amount of num:\n";
    cin >> n;
    List L;
    cout << "then cin in the number\n";
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        L.Insert(x);
    }
    L.puts();
    L.reverse(1, 3);
    L.puts();
    List other;
    other.assign(L);
    cout << "other ";
    other.puts();
    cout << "now test the tailor, please cin in the i and j\n";
    int i, j;
    cin >> i >> j;
    L.tailor(i, j);
    L.puts();
    cout << "now will begin to Remove the Same\n";
    L.delDuplicate();
    L.puts();
    }