# 数据结构之链表（整型）

（右图为reverse的图片解释）

#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:
int cnt;
}
void Insert(int x) {
int i = cnt;
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 *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;
}
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;
}
for (int s = 0; s < i; s++)
pre = pre->next;
node *temp = pre->next;
pre->next = temp->next;
delete temp;
cnt--;
}
int empty() const {
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;
/* 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 */
for (int s = 0; s < i; s++)// first move to the i place
old = pre->next;
for (int count = 0; count < j - i && old; count++) {
temp = old->next;
old->next = pre;
pre = old;
old = temp;
}
return;
}

void assign(const List &other) {//复制
if (empty() == 0)
clear();
node *other_cur, *cur;
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;
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";
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();
}


int main() {
// test();
return 0;
}