目录
什么是链表?
什么是链式存储?
线性存储&线性表
链式存储
链表
初始化
分析真实下标
获取长度
改&查(get&set)
尾部增删节点
清空链表元素
迭代器
任意位置增删节点
I/O操作
数据填充
数据置空(数据初始化)
数据交换
链表复制
拷贝列表部分
链表合并
链表高级操作(统计/查找)
链表排序
怎么实现链表(完整代码)?
Time to 点赞
不想看文字的人们,在最后有完整代码
什么是链表?
要想知道什么是链表,我们要知道什么是链式存储
什么是链式存储?
要想知道什么是链式存储,我们要知道什么是线性存储,什么是线性表
线性存储&线性表
通俗来说,将逻辑有序的内容实际(物理空间)也有序地存储在一起,就是线性存储,
那线性表,就是将一堆线性存储的数据,比如说我们编程经常使用的数组
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;
}
改&查(get&set)
这很简单,只要找到那个节点,然后对它进行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;
}
I/O操作
为了方便我们进行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);
}
}
};
Time to 点赞
看完后,别忘了
点赞!
收藏!文章来源:https://www.toymoban.com/news/detail-754045.html
Thanks……文章来源地址https://www.toymoban.com/news/detail-754045.html
到了这里,关于C++ 万字长文,链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!