<commit_before>---
layout: post
title: 链表(list)笔记
description: 链表
tags: ["C++","算法","数据结构"]
---

这篇文章记录了我学习列表找到的一些有用的资料以及edX上Data Structures and Algorithms第三周的笔记.

### 一些概念
1. list是采用动态存储的典型结构
(1)其中的元素称作节点(node)
(2)各节点通过指针或引用彼此连接,在逻辑上构成一个线性序列
(3)相邻node彼此称作前驱(predecessor)或后继(successor). (前驱或后继若存在,则必然唯一)
(4)没有前驱/后继的唯一节点称作首(first/front)/末(last/rear)节点

2. 从秩到位置
(1)向量支持循秩访问(call-by-rank)
(2)根据数据元素的rank,可在O(1)时间内直接确定其物理位置
(3)对list call-by-rank 成本过高(从first/last出发,沿predecessor/successor引用)
(4)改用循位置访问(call-by-position)
(5)利用节点之间的相互引用, 找到特定的节点

3. 循位置访问(call-by-position)
(1)列表节点(list node): ADT接口 
(列表节点首先需要独立地"封装"实现),设置基本操作接口

```
pred(); 			//当前节点前驱节点的位置
succ();				//同上,后继
data();				//当前节点所存数据对象
insertAsPred(e);	//插入前驱节点,存入被引用对象e,返回新节点位置
insertAsSucc(e);	//同上,后继


```

```
/*列表节点:LIstNode模板类*/

#define Posi(T) ListNode<T>* 			//列表节点位置(ISO C++.0x, template alias)
template<typename T>
struct ListNode{						//不过度封装,列表节点模板类,以双向链表形式实现
	T data;								//数值
	Posi(T) pred;						//前驱
	Posi(T) succ;						//后继
	ListNode(){}						//针对header和trailer的构造
	ListNode(T e, Posi(T) p=NULL, Posi(T) s=NULL)
	: data(e),pred(p),succ(s){}			//默认constructor
	Posi(T) insertAsPred(T const & e);	
	Posi(T)	insertAsSucc(T const & e);
}
```

```
#include "listNode.h"				//引入list节点类

template<typename T> class List {	//list模板类
  private: 
	int _size;
	Posi(T)	header; Posi(T) trailer;
	/*
	头/尾哨兵,对外不可见
	firstNode/lastNode, 首元素/末元素对外可见
	头尾一定存在,firstNode和lastNode不一定存在
	头,首,末,尾
	-1, 0,n-1,n	(rank)							

  protected:
	/*内部函数*/
	
  public:
	/*constructor,destructor,只读接口,可写接口,遍历接口*/
}
```

```
/*构造*/

template<typename T> void List<T>::init(){ 		//初始化,创建列表对象时统一调用
	header  = new ListNode<T>;
	trailer = new ListNode<T>;
	header->succ = trailer; header->pred = NULL;//互联
	trailer->pred = header; trailer->succ= NULL;//互连
	_size = 0; 									//记录规模
}
```

### 无序列表
1. 循秩访问 (e.g. L[r])
(1)重载下标操作符

```
template <typename T>					//assert 0<= rank <size
T List<T>::operator[](Rank r) const {	//O(r), 效率低下,可偶尔为之,不宜长用
	Posi(T) p = first();				//从首节点出发
	while(r-- > 0) p = p->succ;			//顺数第r个节点即是
	return p->data;						//目标节点
}//任一节点的秩,亦即其前驱的总数

问题: Rank是什么类型? 可能要回头看vector那一章
```

2. 查找
(1)在节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者

```
template <typename T>										//从外部调用时,0 <= n <= rank(p) < _size
Posi(T) List<T>::find(T const & e,int n,Posi(T) p) const{	//顺序查找, O(n)
	while(n-- > 0)	//从右向左,逐个将p的前驱与e比对
		if(e == ( p = p->pred )->data ) return p;
	return NULL;
}//header的存在使得处理更为简洁

find(e,n,p)	//查找前驱pred
find(e,p,n)	//查找后继succ
```

### 补充知识
1. ADT(abstract data type): 抽象数据类型
http://www.cnblogs.com/linux-sir/archive/2012/08/15/2640175.html<commit_msg>insert and copy of list<commit_after>---
layout: post
title: 链表(list)笔记
description: 链表
tags: ["C++","算法","数据结构"]
---

这篇文章记录了我学习列表找到的一些有用的资料以及edX上Data Structures and Algorithms第三周的笔记.

### 一些概念
1.list是采用动态存储的典型结构
(1)其中的元素称作节点(node)
(2)各节点通过指针或引用彼此连接,在逻辑上构成一个线性序列
(3)相邻node彼此称作前驱(predecessor)或后继(successor).(前驱或后继若存在,则必然唯一)
(4)没有前驱/后继的唯一节点称作首(first/front)/末(last/rear)节点

2.从秩到位置
(1)向量支持循秩访问(call-by-rank)
(2)根据数据元素的rank,可在O(1)时间内直接确定其物理位置
(3)对list call-by-rank 成本过高(从first/last出发,沿predecessor/successor引用)
(4)改用循位置访问(call-by-position)
(5)利用节点之间的相互引用, 找到特定的节点

3.循位置访问(call-by-position)
(1)列表节点(list node): ADT接口 
(列表节点首先需要独立地"封装"实现),设置基本操作接口

```
pred(); 			//当前节点前驱节点的位置
succ();				//同上,后继
data();				//当前节点所存数据对象
insertAsPred(e);	//插入前驱节点,存入被引用对象e,返回新节点位置
insertAsSucc(e);	//同上,后继


```

```
/*列表节点:LIstNode模板类*/

#define Posi(T) ListNode<T>* 			//列表节点位置(ISO C++.0x, template alias)
template<typename T>
struct ListNode{						//不过度封装,列表节点模板类,以双向链表形式实现
	T data;								//数值
	Posi(T) pred;						//前驱
	Posi(T) succ;						//后继
	ListNode(){}						//针对header和trailer的构造
	ListNode(T e, Posi(T) p=NULL, Posi(T) s=NULL)
	: data(e),pred(p),succ(s){}			//默认constructor
	Posi(T) insertAsPred(T const & e);	
	Posi(T)	insertAsSucc(T const & e);
}
```

```
#include "listNode.h"				//引入list节点类

template<typename T> class List {	//list模板类
  private: 
	int _size;
	Posi(T)	header; Posi(T) trailer;
	/*
	头/尾哨兵,对外不可见
	firstNode/lastNode, 首元素/末元素对外可见
	头尾一定存在,firstNode和lastNode不一定存在
	头,首,末,尾
	-1, 0,n-1,n	(rank)							

  protected:
	/*内部函数*/
	
  public:
	/*constructor,destructor,只读接口,可写接口,遍历接口*/
}
```

```
/*构造*/

template<typename T> void List<T>::init(){ 		//初始化,创建列表对象时统一调用
	header  = new ListNode<T>;
	trailer = new ListNode<T>;
	header->succ = trailer; header->pred = NULL;//互联
	trailer->pred = header; trailer->succ= NULL;//互连
	_size = 0; 									//记录规模
}
```

### 无序列表
1.循秩访问 (e.g.L[r])
(1)重载下标操作符

```
template <typename T>					//assert 0<= rank <size
T List<T>::operator[](Rank r) const {	//O(r), 效率低下,可偶尔为之,不宜长用
	Posi(T) p = first();				//从首节点出发
	while(r-- > 0) p = p->succ;			//顺数第r个节点即是
	return p->data;						//目标节点
}//任一节点的秩,亦即其前驱的总数

问题: Rank是什么类型? 可能要回头看vector那一章
```

2.查找
(1)在节点p(可能是trailer)的n个(真)前驱中,找到等于e的最后者

```
template <typename T>										//从外部调用时,0 <= n <= rank(p) < _size
Posi(T) List<T>::find(T const & e,int n,Posi(T) p) const{	//顺序查找, O(n)
	while(n-- > 0)	//从右向左,逐个将p的前驱与e比对
		if(e == ( p = p->pred )->data ) return p;
	return NULL;
}//header的存在使得处理更为简洁

find(e,n,p)	//查找前驱pred
find(e,p,n)	//查找后继succ
```

3.插入与复制

```
/*insert*/

template <typename T> Posi(T) List<T>::insertBefore(Posi(T) p,T const & e){
	_size++;
	return p->insertAsPred(e);
}

template <typename T>							//前插入算法(后插入完全对称)
Posi(T) ListNode<T>::insertAsPred(T const & e){	//O(1)
	Posi(T) x = new ListNode(e,pred,this);		//创建(耗时100倍(?))
	pred->succ = x;								//建立连接
	pred = x;
	return x;									//返回新节点的位置
}

//即便当前node是first node,它的pred依然存在, 是header
```

```
/*construction based on copy*/

template <typename T>					   //基本接口
void List<T>::copyNodes(Posi(T) p,int n){  //O(n)
	init();								   //创建header/trailer 
	while (n--){						   //将起自p的n项依次作为末节点插入
		insertAsLast(p->data);			   //实际上就是insertBefore(trailer)
		p = succ;
	}
}


```

### 补充知识
1.ADT(abstract data type): 抽象数据类型
http://www.cnblogs.com/linux-sir/archive/2012/08/15/2640175.html
{'fraction_non_alphanumeric': 0.19477036540395576, 'fraction_numerical': 0.015253100905129064, 'mean_word_length': 3.78125, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 54, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3690942', 'n_tokens_mistral': 3739, 'n_tokens_neox': 3819, 'n_words': 483}