用struct手写了个list
有push_back,push_front,insert,erase reserve，size,setpos,rbegin 功能。
坑：一开始想用template<class T>结果总是编译错误（漏写了<T>)
改成int后总是地址错误，（因为没有new地址）
然后网上学（抄）了一下class的一个程序，总是编译报错orz
最后自己拙劣地写出了一个数据结构，100行左右注//释掉的是class版本：
#include<iostream>
#include <string>
#include<list>
#include<fstream>
using namespace std;
list<int> l;
typedef long long ll, rr;
const int H = 1e9;
struct mlist {
int d;
mlist *prior;
mlist *next;
mlist(int d=, mlist* prior = NULL, mlist* next = NULL) :d(d), prior(prior), next(next) {}//指向自己。
mlist * setpos(int i) {
mlist *p = next;
int count = ;
if (i < ) {
cout << "illegal find" << endl; return NULL;
}
while (p != NULL&&count<i) {
p = p->next;
count++;
}
return p;
}
mlist* rbegin() {
mlist *p = next;
while (p != NULL)p = p->next;
return p;
}
void pb(int x) {//find this list's end,attach to it;
if (next == NULL) {
mlist *now=new mlist(x, next, NULL);
next = now;
return;
}
mlist *p = next;
while (p->next != NULL)p = p->next;
mlist *now;
now = new mlist(x, p, NULL);
p->next = now; }
void pf(int x) {//find this list's end,attach to it;
if (next == NULL) {
mlist *now = new mlist(x, next, NULL);
next = now;
return;
} mlist *now;
now = new mlist(x, next->prior, next);
next = now; }
bool insert(int i, int x) {//第i个后面插入x，i从1开始
if (i == ) pf(x);
else {
mlist *p = next, *q;
if ((p =setpos(i )) == NULL) {//前1个
cout << "illegal insertion" << endl;
return false;
}
q = new mlist(x, p->prior, p->next);
p->next = q;
return true;
}
}
bool erase(int i) {//第i个后面插入x，i从1开始 if (i == ) {
mlist*q = next; next = next->next;
delete q;
}
else {
mlist *p = next, *q;
if ((p = setpos(i - )) == NULL) {//第i个
cout << "illegal deletion" << endl;
return false;
}
q = p->next;
p->next = p->next->next;
delete (q);
return true;
}
}
int size() {
int cnt = ;
mlist* p = next;
while (p != NULL) {
p = p->next;
cnt++;
}
return cnt;
}
void reverse() {
int n = size();
int t = n;
for(int i=;i<=n;i++) {
int x = setpos(n)->d;
erase(n);
insert(i-, x); } }
};
mlist init() {
mlist x;
x.d = H;
x.next = x.prior = NULL;
return x;
}
void homework1() {
ifstream fin("1.txt");
int n; fin >> n;
for (int i = ; i <= n; i++) { int x; fin >> x; l.push_back(x); }
auto e = l.end();
for (auto t = l.begin(); t != e; t++) {
if (*t < )l.push_front(*t);
else l.push_back(*t);
t = l.erase(t);
}
for (auto t : l) { cout << t << ' '; }
}
mlist head = init();
void print(mlist head) {
mlist *p = &head;
while (p != NULL) cout << p->d << ' ', p = p->next;
cout << endl;
}
int main() { int n;
cin >> n;
for (int i = ; i <= n; i++)head.pb(i);
print(head);
head.reverse();
print(head);
//cout << head.size();
cin >> n;
}
/*p->prior->next = p->next;
p->next->prior = p->prioir;
free(p);*/ /*template<class T> class Link {//const
public:
T data;
Link<T> *next;
Link(const T info, const Link<T>*nextValue = NULL) {
data = info;
next = nextValue;
}
Link(const Link<T>*nextValue) {
next = nextValue;
}
};
template<class T> class InkList :public List<T> {
private:
Link<T> *head, *tail;
Link<T> *setPos(const int p);
public:
~InkList(int s);
//ADT
bool isEmpty();
void clear();
int length();
bool append(const T value);
bool insert(const int p, const T value);
bool delete1(const int p);
bool getValue(const int p, T& value);
bool getPos(int &p, const T value);
};
//第i个的指针
template<class T>
Link<T> *InkList<T>::setPos(int i) {
int count = 0;
if (i == -1)
return head;
link<T>*p = head->next;
while (p != NULL&&count < i) {
p = p->next;
count++;
};
return p;
}
//insert tail??new??
template<class T>
bool InkList<T>::insert(const int i, const T value) {
Link<T> *p*q; if ((p = setPos(i - 1)) == NULL) {
cout << "illegal insertion" << endl;
return false;
}
q = new Link<T>(value, p->next);
p->next = q;
if (p == tail)
tail = q;
return true;
}
//delete
template<class T>
bool InkList<T>::delete1(const int i) {//delete 内置函数
Link<T>*q, *p;
if ((p = setPos(i - 1)) == NULL || p == tail) {
cout << "illegal deletion" << endl;
return false;
}
q = p->next;
if (q == tail) {
tail = p;
p->next = NULL;
}
else p->next = q->next;
delete q;
return true;
}
/*p = head;//delete by x;
while (p->next != NULL&&p->next->info != x) p = p->next;
q = p->next;
p->next = q->next;
free(q);*/