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)

链式存储

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

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

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

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

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 点赞

看完后,别忘了

点赞!

收藏!

Thanks……文章来源地址https://www.toymoban.com/news/detail-754045.html

到了这里,关于C++ 万字长文,链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】——线性表(顺序表加链表),万字解读(加链表oj详解)

    前言 由于之前存在过对两者的区别考虑,所以把他们放在一起来说,更加容易区别和理解 对于有关线性表的概念这里就不展示了,这里主要是介绍线性表里面的这两个结构的知识点 一.顺序表 1.顺序表介绍 顺序表的存储结构和逻辑结构都是相邻的, 这里如果我们把a1的地址

    2024年03月22日
    浏览(86)
  • 【c++学习】数据结构中的链表

    链表与线性表相对,链表数据在内存中的存储空间是不连续的,链表每个节点包含数据域和指针域。 下述代码实现了链表及其接口 包括增、删、查、改以及其他一些简单的功能 运行结果: 于 2024-01-23 第一次整理编写 学习时整理,不当之处烦请指正 码字不易,留个赞再走吧

    2024年01月24日
    浏览(55)
  • 链表综合算法设计(c++数据结构)

      一、设计内容 已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不限于以下功能: (1)    增加一个职工信息

    2024年02月02日
    浏览(55)
  • 数据结构-双向链表(c++)超全超详细

    单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入,删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。 提示:以下是本篇文章正文内容,下面案

    2023年04月08日
    浏览(43)
  • 利用C++超详细解释数据结构中的链表

    链表(Linked List)是一种常见的数据结构,它可以动态地插入和删除元素,不需要像数组那样预先分配固定大小的内存。链表中的每个元素称为节点(Node),每个节点包含一个数据值和一个指向下一个节点的指针。本教学将涵盖以下知识点: 单向链表(Singly Linked List) 双向

    2024年02月04日
    浏览(30)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(54)
  • 小白也能学会的链表 | C++ | 算法与数据结构 (新手村)

    本质:找到两个有序数据段中的第一个相同数据 解题:利用set的不重复性,首先把headA都塞到set中,再遍历headB找有没有已经出现在set中的节点即可。 注意! set的数据是ListNode* 不是 int。如果是int可能出现节点不同但是var相同的情况,而ListNode* 就不会。 时间复杂度:O(2n)

    2024年02月14日
    浏览(52)
  • 从0开始学C++ 第二十七课 数据结构入门 - 数组与链表

    第二十七课:数据结构入门 - 数组与链表 学习目标: 理解数组的基本概念和操作。 掌握链表的基本结构与特点。 学会在C++中定义和操作数组和链表。 了解数组和链表的基本使用场景。 学习内容: 数组(Array) 概念:数组是一种线性数据结构,用一段连续的内存空间来存储

    2024年01月23日
    浏览(47)
  • C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题,当删除元素时(元素出队列时)会出现假饱和的情况,如上图m_data[0]和m_data[1]再进行出队列操作之后,这两个位置可以容纳新的元素,但m_rear没有回到原本的m_data[0]位置,因此需要引入一个新的队列结构,环形队列,m_rear这个位置可以

    2024年02月05日
    浏览(41)
  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包