赞
踩
不想看文字的人们,在最后有完整代码
要想知道什么是链表,我们要知道什么是链式存储
要想知道什么是链式存储,我们要知道什么是线性存储,什么是线性表
通俗来说,将逻辑有序的内容实际(物理空间)也有序地存储在一起,就是线性存储,
那线性表,就是将一堆线性存储的数据,比如说我们编程经常使用的数组
type array_name[length];
线性表的存储修改等操作都是通过数学公式实现的,因此速度较快,但是必须在最开头确定长度(存储空间大小)
复杂度:
获取长度 | O(1) |
修改 | O(1) |
删除 | O(n) |
移动 | O(n) |
查找 | O(1) |
空间复杂度:T(n) ∈ O(n)
既然我们已经知道了线性存储是什么,那么我们马上再来关注以下什么是链式存储
链式存储是将将逻辑有序的内容实际(物理空间)无序地存储在一起,
换句话说,链表存储的数据元素,其物理存储位置是随机的数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构
比如说在一个抽屉里放了一些东西(数据),然后里面还有一张小纸条,告诉你,下面一个(些)数据放在哪里
- struct Drawer{
- int value;
- Drawer* next;
- };
当然,我们也可以在抽屉里不仅放一个数据,可以放一个收纳盒,标准的形式就是这样:
- struct information {
- int data;
- // another information
- };
-
- struct node;
- typedef node* n;
-
- struct node {
- information value;
- n next;
- };
-
我们也可以不仅只存储它的直接后继(next),再存储它的直接前驱(prev),那么就变成了一个双向链表
- struct node {
- information value;
- n next, prev;
- };
再设计它的存取函数
- struct node {
- information value;
- n prev, next;
- int getifm()
- {
- return this->value.data;
- }
- int setifm(int x)
- {
- this->value.data = x;
- }
- };
至此,我们已经设计好了一个链表节点里的所有内容
因此,链表的节点由两个部分组成
也就是数据域,和指针域,其中数据域存储数据,就是我们刚刚写的information value,而指针域存储前一个结点下一个节点等联系,也就是我们刚刚写的n prev, next。
我们已经对链表有了一定的了解,下面让我们写一个专门控制链表节点的结构体,我们把它称为
链表(link list)
,很明显,我们要在这里面存储它的head(头节点)end(尾节点,爱存不存),length(长度,爱存不存,但按照我的习惯,我一般都存):
- struct linkl
- {
- n head, end;
- int length;
- };
也就是说,如果我们要存储一些数据,比如说{1,3,4,7,2}
数组是这样子的:
x | x+4 | x+8 | x+16 | x+20 |
1 | 3 | 4 | 7 | 2 |
而链表可能是这样子的
a | next | b | next | c | next | d | next | e | next | f | next | g | next |
4 | d | 3 | a | NULL | NULL | 7 | g | 1 | b | NULL | e | 2 | c |
在这个样例中,f就是头节点,c就是尾节点。
当然,也可以是各种各样的组合方式,其中abcde都是随机的,当然,我们也可以再弄7列存储它的prev(直接前驱),但是这样也够了。
让后让我们写一个链表最重要的函数——init初始化
- int init(int l=0)
- {
- this->h = new node;
- this->e = new node;
- n p, r;
- p = this->h;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = this->e;
- this->e->prev = p;
- this->len = l;
- }

其中l表示要初始化的长度,p为上一轮创建的节点,r是当前节点,在这一轮结束后,将p指向r,
下面我们要学的就是链表最重要的两行代码:
- p->next = r;
- r->prev = p;
通过这两行代码,我们可以轻松将p和r建立联系。
通过观察,不难发现初始化链表,或者说其中最重要的新建空节点的复杂度为O(n)。
在这里,我们可以自己规定,头尾节点不存储数据,而节点的下标为1~length,反向下标为-1~-length,于是我们可以在写一个函数,专门用来分析下标(在之后会用到)
- int real_index(int x)
- {
- if(x<0) return this->check_len()+x+1;
- else return x;
- }
为了及时获取链表的长度,我们再写一个函数用于分析链表的长度,实现很简单,只要不断便利,看看它的后继是不是end就行了
- int check_len()
- {
- n p = this->h;
- int t = 0;
- while(p->next != this->e)
- {
- t++;
- p = p->next;
- }
- this->len = t;
- return t;
- }
这很简单,只要找到那个节点,然后对它进行setifm或getifm就行了
- int set(int o, int i)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- return p->setifm(i);
- }
- int get(int o)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- return p->getifm();
- }

实现的方法就是找到尾节点的前面一个节点(因为尾节点是不存数据的),然后新建或删除指定数量的节点,并让最后一次操作的节点和尾节点建立联系,以下是代码
- int new_node(int l=1)
- {
- n p, r;
- p = this->e->prev;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = this->e;
- this->e->prev = p;
- this->len += l;
- }
- int del_node(int l=1)
- {
- n r;
- r = this->e;
- for(int i=1; i<=l; i++)
- {
- r = r->prev;
- delete r->next;
- }
- r->next = this->e;
- this->e->prev = r;
- this->len -= l;
- }

这只要使用我们刚刚编写的del_node,即可完成
- int clear_items()
- {
- this->del_node(this->check_len());
- this->len = 0;
- }
注意,为什么我们不使用简单的h->next=e, e->prev=h,是因为我们要在过程中释放节点空间,delete掉被删除的node
为了为以后做准备,让我们来写一个iter(迭代器),如果不知道迭代器的人,可以去看stl,
在下面这篇关于实现栈和队列的文章里,我们提到了迭代器,但这种迭代器极其简单,因为我们是通过数组来实现的,而数组是一种线性存储的结构,因此迭代器只要把它设成指向数据的指针就可以了,但是现在是链表,我们要如何实现迭代器呢?(很明显,指针自增自减已经不管用了)
C++ 手动实现栈&队列_嘉定世外的JinJiayang的博客-CSDN博客
“让我们来写一个结构体吧。”
struct iter;
下面让我们来实现它存储的信息
- struct iter {
- n nd;
- };
你没有看错,就是这么简单,下面让我们实现它的自增自减运算符,如果不知道如何重载运算符,可以baidu/google……一下
- struct iter {
- n nd;
- iter operator++()
- {
- if(this->nd->next == NULL) return *this;
- this->nd = this->nd->next;
- return *this;
- }
- iter operator++(int)
- {
- if(this->nd->next == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->next;
- return i;
- }
- iter operator--()
- {
- if(this->nd->prev == NULL) return *this;
- this->nd = this->nd->prev;
- return *this;
- }
- iter operator--(int)
- {
- if(this->nd->prev == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->prev;
- return i;
- }
- };

然后实现一下获取node的函数
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- };
输出函数(友元friend),这里输出了node的数据
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- friend ostream& operator<<(ostream& os, iter self)
- {
- os << self.get()->getifm();
- return os;
- }
- };
与整数类型加减函数,自增/自减n位
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- iter operator--()
- {
- if(this->nd->prev == NULL) return *this;
- this->nd = this->nd->prev;
- return *this;
- }
- iter operator--(int)
- {
- if(this->nd->prev == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->prev;
- return i;
- }
- iter operator+(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it++;
- return it;
- }
- iter operator-(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it--;
- return it;
- }
- };

等于/不等于判断
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- bool operator==(const iter other)
- {
- return (this->nd) == (other.nd);
- }
- bool operator!=(const iter other)
- {
- return (this->nd) != (other.nd);
- }
- };
返回该迭代器的头部(head->next)/尾部(end->prev)/真实头部(head)/真实尾部(end)
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- iter real_head()
- {
- iter p = *this;
- iter r = p--;
- while(p.nd != r.nd) p--, r--;
- return p;
- }
- iter real_end()
- {
- iter p = *this;
- iter r = p++;
- while(p.nd != r.nd) p++, r++;
- iter ready;
- ready.nd = p.get();
- return ready;
- }
- iter head()
- {
- return ++this->real_head();
- }
- iter end()
- {
- return --this->real_end();
- }
- };

迭代器的完整代码
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- friend ostream& operator<<(ostream& os, iter self)
- {
- os << self.get()->getifm();
- return os;
- }
- iter operator++()
- {
- if(this->nd->next == NULL) return *this;
- this->nd = this->nd->next;
- return *this;
- }
- iter operator++(int)
- {
- if(this->nd->next == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->next;
- return i;
- }
- iter operator--()
- {
- if(this->nd->prev == NULL) return *this;
- this->nd = this->nd->prev;
- return *this;
- }
- iter operator--(int)
- {
- if(this->nd->prev == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->prev;
- return i;
- }
- iter operator+(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it++;
- return it;
- }
- iter operator-(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it--;
- return it;
- }
- bool operator==(const iter other)
- {
- return (this->nd) == (other.nd);
- }
- bool operator!=(const iter other)
- {
- return (this->nd) != (other.nd);
- }
- iter real_head()
- {
- iter p = *this;
- iter r = p--;
- while(p.nd != r.nd) p--, r--;
- return p;
- }
- iter real_end()
- {
- iter p = *this;
- iter r = p++;
- while(p.nd != r.nd) p++, r++;
- iter ready;
- ready.nd = p.get();
- return ready;
- }
- iter head()
- {
- return ++this->real_head();
- }
- iter end()
- {
- return --this->real_end();
- }
- };

下面让我们在结构体linkl里写几个返回迭代器的函数
- iter get_iter(int o)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- iter r;
- r.nd = p;
- return r;
- }
- iter iter_real_head()
- {
- return this->get_iter(0);
- }
- iter iter_head()
- {
- return this->get_iter(1);
- }
- iter iter_end()
- {
- return this->get_iter(-1);
- }
- iter iter_real_end()
- {
- return ++this->get_iter(-1);
- }

从现在起,我们想获得链表的第n个元素,就可以写成
n node_name = link_list.get_iter(n).get();
有了迭代器以后,我们之后的工作就方便多了。
这很简单,使用我们刚刚学习的迭代器即可解决,和init函数和del_node/new_node差不多,遍历+新建/删除
- int self_del_node(int i, int l=1)
- {
- i = this->real_index(i);
- iter it = this->get_iter(i);
- --it;
- iter now = it+l;
- ++now;
- n begin = it.get(), end = now.get();
- begin->next = end;
- end->prev = begin;
- this->len -= l;
- }
- int self_new_node(int i, int l=1)
- {
- i = this->real_index(i);
- n f = this->get_iter(i).get();
- n r, p=f;
- n nextf = f->next;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = nextf;
- nextf->prev = p;
- this->len += l;
- }

为了方便我们进行debug,我们可以写一些专门用来输入输出的函数,即IO函数,代码很简单
- void print(string sep=" ", string end="\n")
- {
- n p = this->h;
- int i;
- for(i=1; p->next != this->e; i++)
- {
- p = p->next;
- cout << p->getifm() << sep;
- }
- cout << end;
- this->len = i-1;
- }
- void reversed_print(string sep=" ", string end="\n")
- {
- n p = this->e;
- int i;
- for(i=1; p->prev != this->h; i++)
- {
- p = p->prev;
- cout << p->getifm() << sep;
- }
- cout << end;
- this->len = i-1;
- }
- string to_string(string sep=" ", string end="\n")
- {
- string result;
- n p = this->h;
- int i;
- for(i=1; p->next != this->e; i++)
- {
- p = p->next;
- result += to_string(p->getifm()) + sep;
- }
- result += end;
- this->len = i-1;
- return result;
- }
- void known_read(int t)
- {
- iter start = this->iter_end();
- this->new_node(t);
- for(int i=1; i<=t; i++)
- {
- start++;
- int v;
- cin >> v;
- start.get()->setifm(v);
- }
- start.get()->next = this->e;
- }
- int read()
- {
- this->init(0);
- int t;
- cin >> t;
- this->known_read(t);
- return 0;
- }
- int write()
- {
- this->print();
- return 0;
- }

这个函数的目的是让链表的所有元素都填充为指定数据,实现方法就是遍历一个个节点,然后修改数据就行了
- int fill(int i, int from=1, int end=-1)
- {
- from = this->real_index(from);
- end = this->real_index(end);
- iter first = this->get_iter(from-1);
- for(int j=from; j<=end; j++)
- {
- ++first;
- first.get()->setifm(i);
- }
- }
这个和我们之前学习的clear_items不一样这个是把数据初始化为-1,也就是fill为-1,代码只有三行
- int clear()
- {
- this->fill(-1);
- }
就是用了我们刚刚写的fill函数,没什么很难的地方,很容易理解。
swap函数的实现就是找到两个节点,然后如何交换就像交换两个变量一样
- int a, b;
- int swap(int* a, int* b)
- {
- int tmp;
- tmp = a;
- a = b;
- b = tmp;
- }
那么代码如下
- int swap(int i1, int i2)
- {
- n n1 = this->get_iter(i1).get();
- n n2 = this->get_iter(i2).get();
- int tmp;
- tmp = n1->getifm();
- n1->setifm(n2->getifm());
- n2->setifm(tmp);
- }
如果我将链表直接复制另一个链表中,如下面的代码的话,
- linkl l;
- linkl l2;
- l2 = l;
但是l2的数据如果改动,l1的数据也会改动,因此是一种浅拷贝,这显然达不到我们想要的结果,因为我们希望的是l2的数据和l的数据是没有关联的,那么我们就要自己实现一个copy函数,一个深拷贝函数
那么怎么实现呢?
其实很简单,我们只要把init函数拿过来,做一些小改动就可以了,比如说在new节点的时候赋this对象的值,下面给出了代码:
- linkl copy()
- {
- linkl result;
- n noden = this->h;
- result.h = new node;
- n nn, pnn=result.h;
- while(this->e != noden)
- {
- noden = noden->next;
- n nnn = new node;
- nnn->k = noden->k;
- nnn->ifm = noden->ifm;
- pnn->next = nnn;
- nnn->prev = pnn;
- pnn = nnn;
- }
- result.e = pnn;
- result.len = this->len;
- return result;
- }

这个也可以使用链表复制的思路,但是就没有锻炼思维的意义了,因此我们换一种思路,使用我们的迭代器,方法如下:
1.新建链表result,并申请空间;
2.声明两个迭代器,分别赋值为result的head和this的head;
3.持续赋值,然后迭代器自增,直到结束。
- linkl get_part(int from=1, int end=-1)
- {
- linkl listt = this->copy();
- from = listt.real_index(from);
- end = listt.real_index(end);
- int sub = end-from;
- linkl result;
- result.init(sub+1);
- iter a = listt.get_iter(from);
- iter b = result.get_iter(1);
- for(int i=1; i<=sub+1; ++i, ++a, ++b)
- b.get()->setifm(a.get()->getifm());
- result.len = sub+1;
- return result;
- }
链表合并是比较简单的,只要找到另一个链表的头节点和尾节点,运用我们最开始学到的知识,将另一个链表的头节点和尾节点与要衔接的节点连接,合并就完成了。当然如果你不想浅拷贝,只需要在函数的开头加上copy函数就行了。
- int merge(linkl other, int o=-1)
- {
- other = other.copy();
- n noden = this->get_iter(o).get();
- n nnoden = noden->next;
- iter noth = other.iter_head();
- noden->next = noth.get();
- noth.get()->prev = noden;
- noth = noth.end();
- noth.get()->next = nnoden, nnoden->prev = noth.get();
- this->len += other.len;
- }
这个的实现和普通数组是一样的,只是下标变成了迭代器而已
统计:
- int count(int v)
- {
- int r = 0;
- iter n = this->iter_real_head();
- iter e = this->iter_real_end();
- while(n.get()->next != e.get())
- {
- ++n;
- if(n.get()->getifm() == v) r++;
- }
- return r;
- }
如果是数组,那么代码是:
- int count(int v)
- {
- int result = 0;
- for(int i=1; i<=length; i++)
- {
- if(value[i] == v) result++;
- }
- return result;
- }
查找:
- int find(int v)
- {
- iter n = this->iter_real_head();
- iter e = this->iter_real_end();
- int i = 0;
- while(n.get()->next != e.get())
- {
- ++i, ++n;
- if(n.get()->getifm() == v) return i;
- }
- return -1;
- }
如果是数组,那么代码是:
- int find(int v)
- {
- for(int i=1; i<=length; i++)
- {
- if(value[i] == v) return i;
- }
- return -1;
- }
下面我们使用的是快速排序的办法,快速排序是一种线性对数 O(nlogn) 的算法,速度快,但是是一种不稳定的排序方法,C++的sort函数就是通过快速排序实现的,它使用一种分治的思想来实现。如果没有学过快速排序的话,你可以去百度上搜一下,下面是升序的代码:
- int sort(int low=1, int high=-1)
- {
- low = this->real_index(low);
- high = this->real_index(high);
- if(low<high)
- {
- int i = low, j = high;
- int x = this->get(low);
- while(i<j)
- {
- while(i<j && this->get(j) > x) j--;
- if(i<j) this->set(i++, this->get(j));
- while(i<j && this->get(i) < x) i++;
- if(i<j) this->set(j--, this->get(i));
- }
- this->set(i, x);
- this->sort(low, i-1);
- this->sort(i+1, high);
- }
- }

“至此,我们已经实现了一个链表的基本功能。”
因为我吃饱了没事干,因此我写了一个数据简单加密,但是你可以不管。
- #include<bits/stdc++.h>
- using namespace std;
-
-
- struct information;
- struct node;
- typedef node* n;
- struct iter;
- struct linkl;
- typedef linkl jll;
-
-
- struct information {
- int data;
- int k;
- int init()
- {
- srand(time(0));
- this->k = rand() % 10007 + 1;
- this->data = -1;
- return this->k;
- }
- int getifm(int key)
- {
- if(k == this->k)
- return this->data;
- else
- return 0x7fffffff;
- }
- int setifm(int key, int v)
- {
- if(k == this->k)
- {
- this->data = v;
- return v;
- }
- else
- return 0x7fffffff;
- }
- };
-
-
- struct node {
- information ifm;
- n next;
- n prev;
- int k;
- node()
- {
- this->k = this->ifm.init();
- this->next = NULL;
- this->prev = NULL;
- }
- int getifm()
- {
- return this->ifm.getifm(this->k);
- }
- int setifm(int i)
- {
- return this->ifm.setifm(this->k, i);
- }
- };
-
-
-
-
- struct iter {
- n nd;
- n get()
- {
- return this->nd;
- }
- friend ostream& operator<<(ostream& os, iter self)
- {
- os << self.get()->getifm();
- return os;
- }
- iter operator++()
- {
- if(this->nd->next == NULL) return *this;
- this->nd = this->nd->next;
- return *this;
- }
- iter operator++(int)
- {
- if(this->nd->next == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->next;
- return i;
- }
- iter operator--()
- {
- if(this->nd->prev == NULL) return *this;
- this->nd = this->nd->prev;
- return *this;
- }
- iter operator--(int)
- {
- if(this->nd->prev == NULL) return *this;
- iter i = *this;
- this->nd = this->nd->prev;
- return i;
- }
- iter operator+(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it++;
- return it;
- }
- iter operator-(int l)
- {
- iter it = *this;
- for(int i=1; i<=l; i++) it--;
- return it;
- }
- bool operator==(const iter other)
- {
- return (this->nd) == (other.nd);
- }
- bool operator!=(const iter other)
- {
- return (this->nd) != (other.nd);
- }
- iter real_head()
- {
- iter p = *this;
- iter r = p--;
- while(p.nd != r.nd) p--, r--;
- return p;
- }
- iter real_end()
- {
- iter p = *this;
- iter r = p++;
- while(p.nd != r.nd) p++, r++;
- iter ready;
- ready.nd = p.get();
- return ready;
- }
- iter head()
- {
- return ++this->real_head();
- }
- iter end()
- {
- return --this->real_end();
- }
- };
-
-
- struct linkl {
- n h;
- n e;
- int len;
-
- // 初始化,重定位,拷贝操作
- int init(int l=0)
- {
- this->h = new node;
- this->e = new node;
- n p, r;
- p = this->h;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = this->e;
- this->e->prev = p;
- this->len = l;
- }
- int real_index(int x)
- {
- if(x<0) return this->check_len()+x+1;
- else return x;
- }
- int check_len()
- {
- n p = this->h;
- int t = 0;
- while(p->next != this->e)
- {
- t++;
- p = p->next;
- }
- this->len = t;
- return t;
- }
- linkl copy()
- {
- linkl result;
- n noden = this->h;
- result.h = new node;
- n nn, pnn=result.h;
- while(this->e != noden)
- {
- noden = noden->next;
- n nnn = new node;
- nnn->k = noden->k;
- nnn->ifm = noden->ifm;
- pnn->next = nnn;
- nnn->prev = pnn;
- pnn = nnn;
- }
- result.e = pnn;
- result.len = this->len;
- return result;
- }
-
- // 迭代器访问操作
- iter get_iter(int o)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- iter r;
- r.nd = p;
- return r;
- }
- iter iter_real_head()
- {
- return this->get_iter(0);
- }
- iter iter_head()
- {
- return this->get_iter(1);
- }
- iter iter_end()
- {
- return this->get_iter(-1);
- }
- iter iter_real_end()
- {
- return ++this->get_iter(-1);
- }
-
- // IO操作
- void print(string sep=" ", string end="\n")
- {
- n p = this->h;
- int i;
- for(i=1; p->next != this->e; i++)
- {
- p = p->next;
- cout << p->getifm() << sep;
- }
- cout << end;
- this->len = i-1;
- }
- void reversed_print(string sep=" ", string end="\n")
- {
- n p = this->e;
- int i;
- for(i=1; p->prev != this->h; i++)
- {
- p = p->prev;
- cout << p->getifm() << sep;
- }
- cout << end;
- this->len = i-1;
- }
- string string_print(string sep=" ", string end="\n")
- {
- string result;
- n p = this->h;
- int i;
- for(i=1; p->next != this->e; i++)
- {
- p = p->next;
- result += to_string(p->getifm()) + sep;
- }
- result += end;
- this->len = i-1;
- return result;
- }
- void known_read(int t)
- {
- iter start = this->iter_end();
- this->new_node(t);
- for(int i=1; i<=t; i++)
- {
- start++;
- int v;
- cin >> v;
- start.get()->setifm(v);
- }
- start.get()->next = this->e;
- }
- int read()
- {
- this->init(0);
- int t;
- cin >> t;
- this->known_read(t);
- return 0;
- }
- int write()
- {
- this->print();
- return 0;
- }
-
- // 数量增删操作
- int new_node(int l=1)
- {
- n p, r;
- p = this->e->prev;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = this->e;
- this->e->prev = p;
- this->len += l;
- }
- int del_node(int l=1)
- {
- n r;
- r = this->e;
- for(int i=1; i<=l; i++)
- {
- r = r->prev;
- delete r->next;
- }
- r->next = this->e;
- this->e->prev = r;
- this->len -= l;
- }
- int clear_items()
- {
- this->del_node(this->check_len());
- this->len = 0;
- }
- int self_del_node(int i, int l=1)
- {
- i = this->real_index(i);
- iter it = this->get_iter(i);
- --it;
- iter now = it+l;
- ++now;
- n begin = it.get(), end = now.get();
- begin->next = end;
- end->prev = begin;
- this->len -= l;
- }
- int self_new_node(int i, int l=1)
- {
- i = this->real_index(i);
- n f = this->get_iter(i).get();
- n r, p=f;
- n nextf = f->next;
- for(int i=1; i<=l; i++)
- {
- r = new node;
- p->next = r;
- r->prev = p;
- p = r;
- }
- p->next = nextf;
- nextf->prev = p;
- this->len += l;
- }
-
- // 数据更改操作
- int fill(int i, int from=1, int end=-1)
- {
- from = this->real_index(from);
- end = this->real_index(end);
- iter first = this->get_iter(from-1);
- for(int j=from; j<=end; j++)
- {
- ++first;
- first.get()->setifm(i);
- }
- }
- int swap(int i1, int i2)
- {
- n n1 = this->get_iter(i1).get();
- n n2 = this->get_iter(i2).get();
- int tmp;
- tmp = n1->getifm();
- n1->setifm(n2->getifm());
- n2->setifm(tmp);
- }
- int clear()
- {
- this->fill(-1);
- }
- int set(int o, int i)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- return p->setifm(i);
- }
- int get(int o)
- {
- o = this->real_index(o);
- n p = this->h;
- for(int i=1; i<=o; i++)
- {
- p = p->next;
- }
- return p->getifm();
- }
-
- // 链表集体操作
- int merge(linkl other, int o=-1)
- {
- other = other.copy();
- n noden = this->get_iter(o).get();
- n nnoden = noden->next;
- iter noth = other.iter_head();
- noden->next = noth.get();
- noth.get()->prev = noden;
- noth = noth.end();
- noth.get()->next = nnoden, nnoden->prev = noth.get();
- this->len += other.len;
- }
- linkl get_part(int from=1, int end=-1)
- {
- linkl listt = this->copy();
- from = listt.real_index(from);
- end = listt.real_index(end);
- int sub = end-from;
- linkl result;
- result.init(sub+1);
- iter a = listt.get_iter(from);
- iter b = result.get_iter(1);
- for(int i=1; i<=sub+1; ++i, ++a, ++b)
- b.get()->setifm(a.get()->getifm());
- result.len = sub+1;
- return result;
- }
-
- // 链表高级操作
- int find(int v)
- {
- iter n = this->iter_real_head();
- iter e = this->iter_real_end();
- int i = 0;
- while(n.get()->next != e.get())
- {
- ++i, ++n;
- if(n.get()->getifm() == v) return i;
- }
- return -1;
- }
- int count(int v)
- {
- int r = 0;
- iter n = this->iter_real_head();
- iter e = this->iter_real_end();
- while(n.get()->next != e.get())
- {
- ++n;
- if(n.get()->getifm() == v) r++;
- }
- return r;
- }
- int sort(int low=1, int high=-1)
- {
- low = this->real_index(low);
- high = this->real_index(high);
- if(low<high)
- {
- int i = low, j = high;
- int x = this->get(low);
- while(i<j)
- {
- while(i<j && this->get(j) > x) j--;
- if(i<j) this->set(i++, this->get(j));
- while(i<j && this->get(i) < x) i++;
- if(i<j) this->set(j--, this->get(i));
- }
- this->set(i, x);
- this->sort(low, i-1);
- this->sort(i+1, high);
- }
- }
- };

看完后,别忘了
点赞!
收藏!
Thanks……
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。