当前位置:   article > 正文

C++ 万字长文,链表详解_c++链表

c++链表

目录

什么是链表?

什么是链式存储?

线性存储&线性表

链式存储

链表

初始化

分析真实下标

获取长度

改&查(get&set)

尾部增删节点

清空链表元素

迭代器

任意位置增删节点

I/O操作

数据填充

数据置空(数据初始化)

数据交换

链表复制

拷贝列表部分

链表合并

链表高级操作(统计/查找)

链表排序

怎么实现链表(完整代码)?

Time to 点赞


不想看文字的人们,在最后有完整代码

什么是链表?

要想知道什么是链表,我们要知道什么是链式存储

什么是链式存储?

要想知道什么是链式存储,我们要知道什么是线性存储,什么是线性表

线性存储&线性表

通俗来说,将逻辑有序的内容实际(物理空间)也有序地存储在一起,就是线性存储,

那线性表,就是将一堆线性存储的数据,比如说我们编程经常使用的数组

type array_name[length];

线性表的存储修改等操作都是通过数学公式实现的,因此速度较快,但是必须在最开头确定长度(存储空间大小)

复杂度:

获取长度O(1)
修改O(1)
删除O(n)
移动O(n)
查找O(1)

 空间复杂度:T(n) ∈ O(n)

链式存储

既然我们已经知道了线性存储是什么,那么我们马上再来关注以下什么是链式存储

链式存储是将将逻辑有序的内容实际(物理空间)无序地存储在一起,
换句话说,链表存储的数据元素,其物理存储位置是随机的

数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构

比如说在一个抽屉里放了一些东西(数据),然后里面还有一张小纸条,告诉你,下面一个(些)数据放在哪里

  1. struct Drawer{
  2. int value;
  3. Drawer* next;
  4. };

当然,我们也可以在抽屉里不仅放一个数据,可以放一个收纳盒,标准的形式就是这样:

  1. struct information {
  2. int data;
  3. // another information
  4. };
  5. struct node;
  6. typedef node* n;
  7. struct node {
  8. information value;
  9. n next;
  10. };

我们也可以不仅只存储它的直接后继(next),再存储它的直接前驱(prev),那么就变成了一个双向链表

  1. struct node {
  2. information value;
  3. n next, prev;
  4. };

再设计它的存取函数

  1. struct node {
  2. information value;
  3. n prev, next;
  4. int getifm()
  5. {
  6. return this->value.data;
  7. }
  8. int setifm(int x)
  9. {
  10. this->value.data = x;
  11. }
  12. };

至此,我们已经设计好了一个链表节点里的所有内容

因此,链表的节点由两个部分组成

也就是数据域,和指针域,其中数据域存储数据,就是我们刚刚写的information value,而指针域存储前一个结点下一个节点等联系,也就是我们刚刚写的n prev, next。

链表

我们已经对链表有了一定的了解,下面让我们写一个专门控制链表节点的结构体,我们把它称为

链表(link list)

,很明显,我们要在这里面存储它的head(头节点)end(尾节点,爱存不存),length(长度,爱存不存,但按照我的习惯,我一般都存):

  1. struct linkl
  2. {
  3. n head, end;
  4. int length;
  5. };

也就是说,如果我们要存储一些数据,比如说{1,3,4,7,2}

数组是这样子的:

xx+4x+8x+16x+20
13472

而链表可能是这样子的

anextbnextcnextdnextenextfnextgnext
4d3aNULLNULL7g1bNULLe2c

在这个样例中,f就是头节点,c就是尾节点。

当然,也可以是各种各样的组合方式,其中abcde都是随机的,当然,我们也可以再弄7列存储它的prev(直接前驱),但是这样也够了。

初始化

让后让我们写一个链表最重要的函数——init初始化

  1. int init(int l=0)
  2. {
  3. this->h = new node;
  4. this->e = new node;
  5. n p, r;
  6. p = this->h;
  7. for(int i=1; i<=l; i++)
  8. {
  9. r = new node;
  10. p->next = r;
  11. r->prev = p;
  12. p = r;
  13. }
  14. p->next = this->e;
  15. this->e->prev = p;
  16. this->len = l;
  17. }

其中l表示要初始化的长度,p为上一轮创建的节点,r是当前节点,在这一轮结束后,将p指向r,

下面我们要学的就是链表最重要的两行代码:

  1. p->next = r;
  2. r->prev = p;

通过这两行代码,我们可以轻松将p和r建立联系。

通过观察,不难发现初始化链表,或者说其中最重要的新建空节点的复杂度为O(n)。

分析真实下标

在这里,我们可以自己规定,头尾节点不存储数据,而节点的下标为1~length,反向下标为-1~-length,于是我们可以在写一个函数,专门用来分析下标(在之后会用到)

  1. int real_index(int x)
  2. {
  3. if(x<0) return this->check_len()+x+1;
  4. else return x;
  5. }

获取长度

为了及时获取链表的长度,我们再写一个函数用于分析链表的长度,实现很简单,只要不断便利,看看它的后继是不是end就行了

  1. int check_len()
  2. {
  3. n p = this->h;
  4. int t = 0;
  5. while(p->next != this->e)
  6. {
  7. t++;
  8. p = p->next;
  9. }
  10. this->len = t;
  11. return t;
  12. }

改&查(get&set)

这很简单,只要找到那个节点,然后对它进行setifm或getifm就行了

  1. int set(int o, int i)
  2. {
  3. o = this->real_index(o);
  4. n p = this->h;
  5. for(int i=1; i<=o; i++)
  6. {
  7. p = p->next;
  8. }
  9. return p->setifm(i);
  10. }
  11. int get(int o)
  12. {
  13. o = this->real_index(o);
  14. n p = this->h;
  15. for(int i=1; i<=o; i++)
  16. {
  17. p = p->next;
  18. }
  19. return p->getifm();
  20. }

尾部增删节点

实现的方法就是找到尾节点的前面一个节点(因为尾节点是不存数据的),然后新建或删除指定数量的节点,并让最后一次操作的节点和尾节点建立联系,以下是代码

  1. int new_node(int l=1)
  2. {
  3. n p, r;
  4. p = this->e->prev;
  5. for(int i=1; i<=l; i++)
  6. {
  7. r = new node;
  8. p->next = r;
  9. r->prev = p;
  10. p = r;
  11. }
  12. p->next = this->e;
  13. this->e->prev = p;
  14. this->len += l;
  15. }
  16. int del_node(int l=1)
  17. {
  18. n r;
  19. r = this->e;
  20. for(int i=1; i<=l; i++)
  21. {
  22. r = r->prev;
  23. delete r->next;
  24. }
  25. r->next = this->e;
  26. this->e->prev = r;
  27. this->len -= l;
  28. }

清空链表元素

这只要使用我们刚刚编写的del_node,即可完成

  1. int clear_items()
  2. {
  3. this->del_node(this->check_len());
  4. this->len = 0;
  5. }

注意,为什么我们不使用简单的h->next=e, e->prev=h,是因为我们要在过程中释放节点空间,delete掉被删除的node

迭代器

为了为以后做准备,让我们来写一个iter(迭代器),如果不知道迭代器的人,可以去看stl,

在下面这篇关于实现栈和队列的文章里,我们提到了迭代器,但这种迭代器极其简单,因为我们是通过数组来实现的,而数组是一种线性存储的结构,因此迭代器只要把它设成指向数据的指针就可以了,但是现在是链表,我们要如何实现迭代器呢?(很明显,指针自增自减已经不管用了)

C++ 手动实现栈&队列_嘉定世外的JinJiayang的博客-CSDN博客

“让我们来写一个结构体吧。”

struct iter;

下面让我们来实现它存储的信息

  1. struct iter {
  2. n nd;
  3. };

你没有看错,就是这么简单,下面让我们实现它的自增自减运算符,如果不知道如何重载运算符,可以baidu/google……一下

  1. struct iter {
  2. n nd;
  3. iter operator++()
  4. {
  5. if(this->nd->next == NULL) return *this;
  6. this->nd = this->nd->next;
  7. return *this;
  8. }
  9. iter operator++(int)
  10. {
  11. if(this->nd->next == NULL) return *this;
  12. iter i = *this;
  13. this->nd = this->nd->next;
  14. return i;
  15. }
  16. iter operator--()
  17. {
  18. if(this->nd->prev == NULL) return *this;
  19. this->nd = this->nd->prev;
  20. return *this;
  21. }
  22. iter operator--(int)
  23. {
  24. if(this->nd->prev == NULL) return *this;
  25. iter i = *this;
  26. this->nd = this->nd->prev;
  27. return i;
  28. }
  29. };

然后实现一下获取node的函数

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. };

输出函数(友元friend),这里输出了node的数据

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. friend ostream& operator<<(ostream& os, iter self)
  8. {
  9. os << self.get()->getifm();
  10. return os;
  11. }
  12. };

与整数类型加减函数,自增/自减n位

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. iter operator--()
  8. {
  9. if(this->nd->prev == NULL) return *this;
  10. this->nd = this->nd->prev;
  11. return *this;
  12. }
  13. iter operator--(int)
  14. {
  15. if(this->nd->prev == NULL) return *this;
  16. iter i = *this;
  17. this->nd = this->nd->prev;
  18. return i;
  19. }
  20. iter operator+(int l)
  21. {
  22. iter it = *this;
  23. for(int i=1; i<=l; i++) it++;
  24. return it;
  25. }
  26. iter operator-(int l)
  27. {
  28. iter it = *this;
  29. for(int i=1; i<=l; i++) it--;
  30. return it;
  31. }
  32. };

等于/不等于判断

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. bool operator==(const iter other)
  8. {
  9. return (this->nd) == (other.nd);
  10. }
  11. bool operator!=(const iter other)
  12. {
  13. return (this->nd) != (other.nd);
  14. }
  15. };

返回该迭代器的头部(head->next)/尾部(end->prev)/真实头部(head)/真实尾部(end)

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. iter real_head()
  8. {
  9. iter p = *this;
  10. iter r = p--;
  11. while(p.nd != r.nd) p--, r--;
  12. return p;
  13. }
  14. iter real_end()
  15. {
  16. iter p = *this;
  17. iter r = p++;
  18. while(p.nd != r.nd) p++, r++;
  19. iter ready;
  20. ready.nd = p.get();
  21. return ready;
  22. }
  23. iter head()
  24. {
  25. return ++this->real_head();
  26. }
  27. iter end()
  28. {
  29. return --this->real_end();
  30. }
  31. };

迭代器的完整代码

  1. struct iter {
  2. n nd;
  3. n get()
  4. {
  5. return this->nd;
  6. }
  7. friend ostream& operator<<(ostream& os, iter self)
  8. {
  9. os << self.get()->getifm();
  10. return os;
  11. }
  12. iter operator++()
  13. {
  14. if(this->nd->next == NULL) return *this;
  15. this->nd = this->nd->next;
  16. return *this;
  17. }
  18. iter operator++(int)
  19. {
  20. if(this->nd->next == NULL) return *this;
  21. iter i = *this;
  22. this->nd = this->nd->next;
  23. return i;
  24. }
  25. iter operator--()
  26. {
  27. if(this->nd->prev == NULL) return *this;
  28. this->nd = this->nd->prev;
  29. return *this;
  30. }
  31. iter operator--(int)
  32. {
  33. if(this->nd->prev == NULL) return *this;
  34. iter i = *this;
  35. this->nd = this->nd->prev;
  36. return i;
  37. }
  38. iter operator+(int l)
  39. {
  40. iter it = *this;
  41. for(int i=1; i<=l; i++) it++;
  42. return it;
  43. }
  44. iter operator-(int l)
  45. {
  46. iter it = *this;
  47. for(int i=1; i<=l; i++) it--;
  48. return it;
  49. }
  50. bool operator==(const iter other)
  51. {
  52. return (this->nd) == (other.nd);
  53. }
  54. bool operator!=(const iter other)
  55. {
  56. return (this->nd) != (other.nd);
  57. }
  58. iter real_head()
  59. {
  60. iter p = *this;
  61. iter r = p--;
  62. while(p.nd != r.nd) p--, r--;
  63. return p;
  64. }
  65. iter real_end()
  66. {
  67. iter p = *this;
  68. iter r = p++;
  69. while(p.nd != r.nd) p++, r++;
  70. iter ready;
  71. ready.nd = p.get();
  72. return ready;
  73. }
  74. iter head()
  75. {
  76. return ++this->real_head();
  77. }
  78. iter end()
  79. {
  80. return --this->real_end();
  81. }
  82. };

下面让我们在结构体linkl里写几个返回迭代器的函数

  1. iter get_iter(int o)
  2. {
  3. o = this->real_index(o);
  4. n p = this->h;
  5. for(int i=1; i<=o; i++)
  6. {
  7. p = p->next;
  8. }
  9. iter r;
  10. r.nd = p;
  11. return r;
  12. }
  13. iter iter_real_head()
  14. {
  15. return this->get_iter(0);
  16. }
  17. iter iter_head()
  18. {
  19. return this->get_iter(1);
  20. }
  21. iter iter_end()
  22. {
  23. return this->get_iter(-1);
  24. }
  25. iter iter_real_end()
  26. {
  27. return ++this->get_iter(-1);
  28. }

从现在起,我们想获得链表的第n个元素,就可以写成

n node_name = link_list.get_iter(n).get();

有了迭代器以后,我们之后的工作就方便多了。

任意位置增删节点

这很简单,使用我们刚刚学习的迭代器即可解决,和init函数和del_node/new_node差不多,遍历+新建/删除

  1. int self_del_node(int i, int l=1)
  2. {
  3. i = this->real_index(i);
  4. iter it = this->get_iter(i);
  5. --it;
  6. iter now = it+l;
  7. ++now;
  8. n begin = it.get(), end = now.get();
  9. begin->next = end;
  10. end->prev = begin;
  11. this->len -= l;
  12. }
  13. int self_new_node(int i, int l=1)
  14. {
  15. i = this->real_index(i);
  16. n f = this->get_iter(i).get();
  17. n r, p=f;
  18. n nextf = f->next;
  19. for(int i=1; i<=l; i++)
  20. {
  21. r = new node;
  22. p->next = r;
  23. r->prev = p;
  24. p = r;
  25. }
  26. p->next = nextf;
  27. nextf->prev = p;
  28. this->len += l;
  29. }

I/O操作

为了方便我们进行debug,我们可以写一些专门用来输入输出的函数,即IO函数,代码很简单

  1. void print(string sep=" ", string end="\n")
  2. {
  3. n p = this->h;
  4. int i;
  5. for(i=1; p->next != this->e; i++)
  6. {
  7. p = p->next;
  8. cout << p->getifm() << sep;
  9. }
  10. cout << end;
  11. this->len = i-1;
  12. }
  13. void reversed_print(string sep=" ", string end="\n")
  14. {
  15. n p = this->e;
  16. int i;
  17. for(i=1; p->prev != this->h; i++)
  18. {
  19. p = p->prev;
  20. cout << p->getifm() << sep;
  21. }
  22. cout << end;
  23. this->len = i-1;
  24. }
  25. string to_string(string sep=" ", string end="\n")
  26. {
  27. string result;
  28. n p = this->h;
  29. int i;
  30. for(i=1; p->next != this->e; i++)
  31. {
  32. p = p->next;
  33. result += to_string(p->getifm()) + sep;
  34. }
  35. result += end;
  36. this->len = i-1;
  37. return result;
  38. }
  39. void known_read(int t)
  40. {
  41. iter start = this->iter_end();
  42. this->new_node(t);
  43. for(int i=1; i<=t; i++)
  44. {
  45. start++;
  46. int v;
  47. cin >> v;
  48. start.get()->setifm(v);
  49. }
  50. start.get()->next = this->e;
  51. }
  52. int read()
  53. {
  54. this->init(0);
  55. int t;
  56. cin >> t;
  57. this->known_read(t);
  58. return 0;
  59. }
  60. int write()
  61. {
  62. this->print();
  63. return 0;
  64. }

数据填充

这个函数的目的是让链表的所有元素都填充为指定数据,实现方法就是遍历一个个节点,然后修改数据就行了

  1. int fill(int i, int from=1, int end=-1)
  2. {
  3. from = this->real_index(from);
  4. end = this->real_index(end);
  5. iter first = this->get_iter(from-1);
  6. for(int j=from; j<=end; j++)
  7. {
  8. ++first;
  9. first.get()->setifm(i);
  10. }
  11. }

数据置空(数据初始化)

这个和我们之前学习的clear_items不一样这个是把数据初始化为-1,也就是fill为-1,代码只有三行

  1. int clear()
  2. {
  3. this->fill(-1);
  4. }

就是用了我们刚刚写的fill函数,没什么很难的地方,很容易理解。

数据交换

swap函数的实现就是找到两个节点,然后如何交换就像交换两个变量一样

  1. int a, b;
  2. int swap(int* a, int* b)
  3. {
  4. int tmp;
  5. tmp = a;
  6. a = b;
  7. b = tmp;
  8. }

那么代码如下

  1. int swap(int i1, int i2)
  2. {
  3. n n1 = this->get_iter(i1).get();
  4. n n2 = this->get_iter(i2).get();
  5. int tmp;
  6. tmp = n1->getifm();
  7. n1->setifm(n2->getifm());
  8. n2->setifm(tmp);
  9. }

链表复制

如果我将链表直接复制另一个链表中,如下面的代码的话,

  1. linkl l;
  2. linkl l2;
  3. l2 = l;

但是l2的数据如果改动,l1的数据也会改动,因此是一种浅拷贝,这显然达不到我们想要的结果,因为我们希望的是l2的数据和l的数据是没有关联的,那么我们就要自己实现一个copy函数,一个深拷贝函数

那么怎么实现呢?

其实很简单,我们只要把init函数拿过来,做一些小改动就可以了,比如说在new节点的时候赋this对象的值,下面给出了代码:

  1. linkl copy()
  2. {
  3. linkl result;
  4. n noden = this->h;
  5. result.h = new node;
  6. n nn, pnn=result.h;
  7. while(this->e != noden)
  8. {
  9. noden = noden->next;
  10. n nnn = new node;
  11. nnn->k = noden->k;
  12. nnn->ifm = noden->ifm;
  13. pnn->next = nnn;
  14. nnn->prev = pnn;
  15. pnn = nnn;
  16. }
  17. result.e = pnn;
  18. result.len = this->len;
  19. return result;
  20. }

拷贝列表部分

这个也可以使用链表复制的思路,但是就没有锻炼思维的意义了,因此我们换一种思路,使用我们的迭代器,方法如下:

1.新建链表result,并申请空间;

2.声明两个迭代器,分别赋值为result的head和this的head;

3.持续赋值,然后迭代器自增,直到结束。

  1. linkl get_part(int from=1, int end=-1)
  2. {
  3. linkl listt = this->copy();
  4. from = listt.real_index(from);
  5. end = listt.real_index(end);
  6. int sub = end-from;
  7. linkl result;
  8. result.init(sub+1);
  9. iter a = listt.get_iter(from);
  10. iter b = result.get_iter(1);
  11. for(int i=1; i<=sub+1; ++i, ++a, ++b)
  12. b.get()->setifm(a.get()->getifm());
  13. result.len = sub+1;
  14. return result;
  15. }

链表合并

链表合并是比较简单的,只要找到另一个链表的头节点和尾节点,运用我们最开始学到的知识,将另一个链表的头节点和尾节点与要衔接的节点连接,合并就完成了。当然如果你不想浅拷贝,只需要在函数的开头加上copy函数就行了。

  1. int merge(linkl other, int o=-1)
  2. {
  3. other = other.copy();
  4. n noden = this->get_iter(o).get();
  5. n nnoden = noden->next;
  6. iter noth = other.iter_head();
  7. noden->next = noth.get();
  8. noth.get()->prev = noden;
  9. noth = noth.end();
  10. noth.get()->next = nnoden, nnoden->prev = noth.get();
  11. this->len += other.len;
  12. }

链表高级操作(统计/查找)

这个的实现和普通数组是一样的,只是下标变成了迭代器而已

统计:

  1. int count(int v)
  2. {
  3. int r = 0;
  4. iter n = this->iter_real_head();
  5. iter e = this->iter_real_end();
  6. while(n.get()->next != e.get())
  7. {
  8. ++n;
  9. if(n.get()->getifm() == v) r++;
  10. }
  11. return r;
  12. }

如果是数组,那么代码是:

  1. int count(int v)
  2. {
  3. int result = 0;
  4. for(int i=1; i<=length; i++)
  5. {
  6. if(value[i] == v) result++;
  7. }
  8. return result;
  9. }

查找:

  1. int find(int v)
  2. {
  3. iter n = this->iter_real_head();
  4. iter e = this->iter_real_end();
  5. int i = 0;
  6. while(n.get()->next != e.get())
  7. {
  8. ++i, ++n;
  9. if(n.get()->getifm() == v) return i;
  10. }
  11. return -1;
  12. }

如果是数组,那么代码是:

  1. int find(int v)
  2. {
  3. for(int i=1; i<=length; i++)
  4. {
  5. if(value[i] == v) return i;
  6. }
  7. return -1;
  8. }

链表排序

下面我们使用的是快速排序的办法,快速排序是一种线性对数 O(nlogn) 的算法,速度快,但是是一种不稳定的排序方法,C++的sort函数就是通过快速排序实现的,它使用一种分治的思想来实现。如果没有学过快速排序的话,你可以去百度上搜一下,下面是升序的代码:

  1. int sort(int low=1, int high=-1)
  2. {
  3. low = this->real_index(low);
  4. high = this->real_index(high);
  5. if(low<high)
  6. {
  7. int i = low, j = high;
  8. int x = this->get(low);
  9. while(i<j)
  10. {
  11. while(i<j && this->get(j) > x) j--;
  12. if(i<j) this->set(i++, this->get(j));
  13. while(i<j && this->get(i) < x) i++;
  14. if(i<j) this->set(j--, this->get(i));
  15. }
  16. this->set(i, x);
  17. this->sort(low, i-1);
  18. this->sort(i+1, high);
  19. }
  20. }

“至此,我们已经实现了一个链表的基本功能。”

怎么实现链表(完整代码)?

因为我吃饱了没事干,因此我写了一个数据简单加密,但是你可以不管。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct information;
  4. struct node;
  5. typedef node* n;
  6. struct iter;
  7. struct linkl;
  8. typedef linkl jll;
  9. struct information {
  10. int data;
  11. int k;
  12. int init()
  13. {
  14. srand(time(0));
  15. this->k = rand() % 10007 + 1;
  16. this->data = -1;
  17. return this->k;
  18. }
  19. int getifm(int key)
  20. {
  21. if(k == this->k)
  22. return this->data;
  23. else
  24. return 0x7fffffff;
  25. }
  26. int setifm(int key, int v)
  27. {
  28. if(k == this->k)
  29. {
  30. this->data = v;
  31. return v;
  32. }
  33. else
  34. return 0x7fffffff;
  35. }
  36. };
  37. struct node {
  38. information ifm;
  39. n next;
  40. n prev;
  41. int k;
  42. node()
  43. {
  44. this->k = this->ifm.init();
  45. this->next = NULL;
  46. this->prev = NULL;
  47. }
  48. int getifm()
  49. {
  50. return this->ifm.getifm(this->k);
  51. }
  52. int setifm(int i)
  53. {
  54. return this->ifm.setifm(this->k, i);
  55. }
  56. };
  57. struct iter {
  58. n nd;
  59. n get()
  60. {
  61. return this->nd;
  62. }
  63. friend ostream& operator<<(ostream& os, iter self)
  64. {
  65. os << self.get()->getifm();
  66. return os;
  67. }
  68. iter operator++()
  69. {
  70. if(this->nd->next == NULL) return *this;
  71. this->nd = this->nd->next;
  72. return *this;
  73. }
  74. iter operator++(int)
  75. {
  76. if(this->nd->next == NULL) return *this;
  77. iter i = *this;
  78. this->nd = this->nd->next;
  79. return i;
  80. }
  81. iter operator--()
  82. {
  83. if(this->nd->prev == NULL) return *this;
  84. this->nd = this->nd->prev;
  85. return *this;
  86. }
  87. iter operator--(int)
  88. {
  89. if(this->nd->prev == NULL) return *this;
  90. iter i = *this;
  91. this->nd = this->nd->prev;
  92. return i;
  93. }
  94. iter operator+(int l)
  95. {
  96. iter it = *this;
  97. for(int i=1; i<=l; i++) it++;
  98. return it;
  99. }
  100. iter operator-(int l)
  101. {
  102. iter it = *this;
  103. for(int i=1; i<=l; i++) it--;
  104. return it;
  105. }
  106. bool operator==(const iter other)
  107. {
  108. return (this->nd) == (other.nd);
  109. }
  110. bool operator!=(const iter other)
  111. {
  112. return (this->nd) != (other.nd);
  113. }
  114. iter real_head()
  115. {
  116. iter p = *this;
  117. iter r = p--;
  118. while(p.nd != r.nd) p--, r--;
  119. return p;
  120. }
  121. iter real_end()
  122. {
  123. iter p = *this;
  124. iter r = p++;
  125. while(p.nd != r.nd) p++, r++;
  126. iter ready;
  127. ready.nd = p.get();
  128. return ready;
  129. }
  130. iter head()
  131. {
  132. return ++this->real_head();
  133. }
  134. iter end()
  135. {
  136. return --this->real_end();
  137. }
  138. };
  139. struct linkl {
  140. n h;
  141. n e;
  142. int len;
  143. // 初始化,重定位,拷贝操作
  144. int init(int l=0)
  145. {
  146. this->h = new node;
  147. this->e = new node;
  148. n p, r;
  149. p = this->h;
  150. for(int i=1; i<=l; i++)
  151. {
  152. r = new node;
  153. p->next = r;
  154. r->prev = p;
  155. p = r;
  156. }
  157. p->next = this->e;
  158. this->e->prev = p;
  159. this->len = l;
  160. }
  161. int real_index(int x)
  162. {
  163. if(x<0) return this->check_len()+x+1;
  164. else return x;
  165. }
  166. int check_len()
  167. {
  168. n p = this->h;
  169. int t = 0;
  170. while(p->next != this->e)
  171. {
  172. t++;
  173. p = p->next;
  174. }
  175. this->len = t;
  176. return t;
  177. }
  178. linkl copy()
  179. {
  180. linkl result;
  181. n noden = this->h;
  182. result.h = new node;
  183. n nn, pnn=result.h;
  184. while(this->e != noden)
  185. {
  186. noden = noden->next;
  187. n nnn = new node;
  188. nnn->k = noden->k;
  189. nnn->ifm = noden->ifm;
  190. pnn->next = nnn;
  191. nnn->prev = pnn;
  192. pnn = nnn;
  193. }
  194. result.e = pnn;
  195. result.len = this->len;
  196. return result;
  197. }
  198. // 迭代器访问操作
  199. iter get_iter(int o)
  200. {
  201. o = this->real_index(o);
  202. n p = this->h;
  203. for(int i=1; i<=o; i++)
  204. {
  205. p = p->next;
  206. }
  207. iter r;
  208. r.nd = p;
  209. return r;
  210. }
  211. iter iter_real_head()
  212. {
  213. return this->get_iter(0);
  214. }
  215. iter iter_head()
  216. {
  217. return this->get_iter(1);
  218. }
  219. iter iter_end()
  220. {
  221. return this->get_iter(-1);
  222. }
  223. iter iter_real_end()
  224. {
  225. return ++this->get_iter(-1);
  226. }
  227. // IO操作
  228. void print(string sep=" ", string end="\n")
  229. {
  230. n p = this->h;
  231. int i;
  232. for(i=1; p->next != this->e; i++)
  233. {
  234. p = p->next;
  235. cout << p->getifm() << sep;
  236. }
  237. cout << end;
  238. this->len = i-1;
  239. }
  240. void reversed_print(string sep=" ", string end="\n")
  241. {
  242. n p = this->e;
  243. int i;
  244. for(i=1; p->prev != this->h; i++)
  245. {
  246. p = p->prev;
  247. cout << p->getifm() << sep;
  248. }
  249. cout << end;
  250. this->len = i-1;
  251. }
  252. string string_print(string sep=" ", string end="\n")
  253. {
  254. string result;
  255. n p = this->h;
  256. int i;
  257. for(i=1; p->next != this->e; i++)
  258. {
  259. p = p->next;
  260. result += to_string(p->getifm()) + sep;
  261. }
  262. result += end;
  263. this->len = i-1;
  264. return result;
  265. }
  266. void known_read(int t)
  267. {
  268. iter start = this->iter_end();
  269. this->new_node(t);
  270. for(int i=1; i<=t; i++)
  271. {
  272. start++;
  273. int v;
  274. cin >> v;
  275. start.get()->setifm(v);
  276. }
  277. start.get()->next = this->e;
  278. }
  279. int read()
  280. {
  281. this->init(0);
  282. int t;
  283. cin >> t;
  284. this->known_read(t);
  285. return 0;
  286. }
  287. int write()
  288. {
  289. this->print();
  290. return 0;
  291. }
  292. // 数量增删操作
  293. int new_node(int l=1)
  294. {
  295. n p, r;
  296. p = this->e->prev;
  297. for(int i=1; i<=l; i++)
  298. {
  299. r = new node;
  300. p->next = r;
  301. r->prev = p;
  302. p = r;
  303. }
  304. p->next = this->e;
  305. this->e->prev = p;
  306. this->len += l;
  307. }
  308. int del_node(int l=1)
  309. {
  310. n r;
  311. r = this->e;
  312. for(int i=1; i<=l; i++)
  313. {
  314. r = r->prev;
  315. delete r->next;
  316. }
  317. r->next = this->e;
  318. this->e->prev = r;
  319. this->len -= l;
  320. }
  321. int clear_items()
  322. {
  323. this->del_node(this->check_len());
  324. this->len = 0;
  325. }
  326. int self_del_node(int i, int l=1)
  327. {
  328. i = this->real_index(i);
  329. iter it = this->get_iter(i);
  330. --it;
  331. iter now = it+l;
  332. ++now;
  333. n begin = it.get(), end = now.get();
  334. begin->next = end;
  335. end->prev = begin;
  336. this->len -= l;
  337. }
  338. int self_new_node(int i, int l=1)
  339. {
  340. i = this->real_index(i);
  341. n f = this->get_iter(i).get();
  342. n r, p=f;
  343. n nextf = f->next;
  344. for(int i=1; i<=l; i++)
  345. {
  346. r = new node;
  347. p->next = r;
  348. r->prev = p;
  349. p = r;
  350. }
  351. p->next = nextf;
  352. nextf->prev = p;
  353. this->len += l;
  354. }
  355. // 数据更改操作
  356. int fill(int i, int from=1, int end=-1)
  357. {
  358. from = this->real_index(from);
  359. end = this->real_index(end);
  360. iter first = this->get_iter(from-1);
  361. for(int j=from; j<=end; j++)
  362. {
  363. ++first;
  364. first.get()->setifm(i);
  365. }
  366. }
  367. int swap(int i1, int i2)
  368. {
  369. n n1 = this->get_iter(i1).get();
  370. n n2 = this->get_iter(i2).get();
  371. int tmp;
  372. tmp = n1->getifm();
  373. n1->setifm(n2->getifm());
  374. n2->setifm(tmp);
  375. }
  376. int clear()
  377. {
  378. this->fill(-1);
  379. }
  380. int set(int o, int i)
  381. {
  382. o = this->real_index(o);
  383. n p = this->h;
  384. for(int i=1; i<=o; i++)
  385. {
  386. p = p->next;
  387. }
  388. return p->setifm(i);
  389. }
  390. int get(int o)
  391. {
  392. o = this->real_index(o);
  393. n p = this->h;
  394. for(int i=1; i<=o; i++)
  395. {
  396. p = p->next;
  397. }
  398. return p->getifm();
  399. }
  400. // 链表集体操作
  401. int merge(linkl other, int o=-1)
  402. {
  403. other = other.copy();
  404. n noden = this->get_iter(o).get();
  405. n nnoden = noden->next;
  406. iter noth = other.iter_head();
  407. noden->next = noth.get();
  408. noth.get()->prev = noden;
  409. noth = noth.end();
  410. noth.get()->next = nnoden, nnoden->prev = noth.get();
  411. this->len += other.len;
  412. }
  413. linkl get_part(int from=1, int end=-1)
  414. {
  415. linkl listt = this->copy();
  416. from = listt.real_index(from);
  417. end = listt.real_index(end);
  418. int sub = end-from;
  419. linkl result;
  420. result.init(sub+1);
  421. iter a = listt.get_iter(from);
  422. iter b = result.get_iter(1);
  423. for(int i=1; i<=sub+1; ++i, ++a, ++b)
  424. b.get()->setifm(a.get()->getifm());
  425. result.len = sub+1;
  426. return result;
  427. }
  428. // 链表高级操作
  429. int find(int v)
  430. {
  431. iter n = this->iter_real_head();
  432. iter e = this->iter_real_end();
  433. int i = 0;
  434. while(n.get()->next != e.get())
  435. {
  436. ++i, ++n;
  437. if(n.get()->getifm() == v) return i;
  438. }
  439. return -1;
  440. }
  441. int count(int v)
  442. {
  443. int r = 0;
  444. iter n = this->iter_real_head();
  445. iter e = this->iter_real_end();
  446. while(n.get()->next != e.get())
  447. {
  448. ++n;
  449. if(n.get()->getifm() == v) r++;
  450. }
  451. return r;
  452. }
  453. int sort(int low=1, int high=-1)
  454. {
  455. low = this->real_index(low);
  456. high = this->real_index(high);
  457. if(low<high)
  458. {
  459. int i = low, j = high;
  460. int x = this->get(low);
  461. while(i<j)
  462. {
  463. while(i<j && this->get(j) > x) j--;
  464. if(i<j) this->set(i++, this->get(j));
  465. while(i<j && this->get(i) < x) i++;
  466. if(i<j) this->set(j--, this->get(i));
  467. }
  468. this->set(i, x);
  469. this->sort(low, i-1);
  470. this->sort(i+1, high);
  471. }
  472. }
  473. };

Time to 点赞

看完后,别忘了

点赞!

收藏!

Thanks……

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/756276
推荐阅读
相关标签
  

闽ICP备14008679号