然后说一下这个，数据结构——链表

链式存储结构

  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻有关术语
  • 结点：数据元素的存储映像。由数据域和指针域两部分组成
    – 数据域：存储元素数值数据
    – 指针域：存储直接后继结点的存储位置
  • 链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
    – 单链表
    – 结点只有一个指针域的链表，称为单链表或线性链表
    – 双链表
    – 有两个指针域的链表，称为双链表
    – 循环链表
    – 首尾相接的链表称为循环链表
  • 头指针
    – 指向链表中第一个结点的指针
  • 首元结点
    – 指链表中存储第一个数据元素a1的结点
  • 头结点
    – 在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
    – 设置头结点的好处
    – 便于首元结点的处理
    – 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
    – 便于空表和非空表的统一处理
    – 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

链表的特点

  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
  • 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

链表的优缺点

  • 优点
    – 数据元素的个数可以自由扩充
    – 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
  • 缺点
    – 存储密度小
    – 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

顺序表和链表的比较

存储结构比较项目

顺序表

链表

存储空间

预先分配，会导致空间闲置或溢出现象

动态分配，不会出现存储空间闲置或溢出现象

存储密度

不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1

需要借助指针来体现元素间的逻辑关系，存储密度小于1

存取元素

随机存取，按位置访问元素的时间复杂度为O(1)

顺序存取，按位置访问元素时间复杂度为O(n)

插入、删除

平均移动约表中一半元素，时间复杂度为O(n)

不需移动元素，确定插入、删除位置后，时间复杂度为O(1)

适用情况

① 表长变化不大，且能事先确定变化的范围
② 很少进行插入或删除操作，经常按元素位置序号访问数据元素

① 长度变化较大
② 频繁进行插入或删除操作

C++代码实现

#include<iostream>
#include<stdlib.h>
using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int Elemtype;

/* typedef struct LNode{
	Elemtype data;
	struct LNode *next;
}LNode;

typedef struct{
	lnode *l;
}LinkList; */

typedef struct LNode {
	Elemtype data;
	struct LNode* next;
}LNode, * LinkList;


// 构造一个空的单链表
Status InitList(LinkList& L)
{
	L = new LNode; // 头指针L指向头结点
	if (!L) exit(OVERFLOW);
	L->next = NULL;  // 指针域置空
	return OK;
}

// 前插法创建单链表
void CreateList_H(LinkList& L, int n)
{
	LinkList p;
	int i;
	L = new LNode;  
	L->next = NULL;  // 先建立一个带头结点的空链表
	// for(i = 0; i < n; ++i)
	for (i = 1; i < n + 1; ++i)
	{
		cout << "请输入第" << i << "个结点的数据" << endl;
		p = new LNode;  // 生成新结点*p
		cin >> p->data;  // 输入元素赋值给新结点*p的数据域
		p->next = L->next;
		L->next = p; // 将新结点*p插入到头结点之后
	}
}


// 尾插法创建单链表
Status CreateList_L(LinkList& L, int n)
{
	LinkList r, p;
	int i;
	L = new LNode;
	L->next = NULL;
	// 尾结点指向头结点
	r = L;
	for (i = 1; i < n + 1; ++i)
	{
		cout << "请输入第" << i << "个结点的数据" << endl;
		p = new LNode;  // 生成新结点
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}
	return OK;
}

// 取值
Status GetElem(LinkList L, int i, Elemtype& e)
{
	// 根据序号i获取元素的值，用e返回值
	int j;
	LinkList p;
	for (p = L->next, j = 1; j < i && p; j++)
		p = p->next;
	if (!p || j > i) return ERROR;
	e = p->data;
	return OK;
}

// 在链表中查找值为e的元素的位置，返回其地址
LinkList LocateElem_L(LinkList L, Elemtype e)
{
	LinkList p;
	p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}

// 插入
Status ListInsert(LinkList& L, int i, Elemtype& e)
{
	LinkList p, s;
	int j;
	for (p = L, j = 0;j < i - 1 && p; j++)
		p = p->next;
	if (!p || j > i) return ERROR;
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

// 删除
Status ListDelete(LinkList& L, int i, Elemtype& e)
{
	LinkList p, q;
	int j;
	for (p = L, j = 0;j < i - 1 && p; j++)
		p = p->next; 
	if (!p || j > i) return ERROR;
	q = p->next;
	p->next = q->next;
	e = q->data;
	delete q;
	return OK;
}

// 销毁
Status DestroyList(LinkList& L)
{
	LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	return OK;
}

// 清空
Status ClearList(LinkList& L)
{
	LinkList p, q;
	p = L->next; // p指向第一个结点
	while (p)  // 没到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;  // 头结点指针域为空
	return OK;
}

// 求表长
int ListLength_L(LinkList L){
	// 返回L中数据元素的个数
	int i;
	LinkList p;
	p = L->next;  // p指向第一个结点
	i = 0;
	while (p)  // 遍历单链表，统计结点数
	{
		i++;
		p = p->next;
	}
	return i;
}

// 判断表是否为空
int ListEmpty(LinkList L) {
	// 若L为空，返回1；否则，返回0
	if (L->next)
		return 0;
	else
		return 1;
}

int main()
{
	LinkList L;
	Elemtype e;
	int i, n;

	// 创建链表测试
	cout << "请输入表长：";
	cin >> n;
	// 尾插法创建
	CreateList_L(L, n);

	cout << "表长为：";
	cout << ListLength_L(L) << endl;

	// 查找测试
	cout << "请输入您需要查找元素的位置：";
	cin >> i;
	GetElem(L, i, e);
	cout << e;

	// 删除测试
	cout << "请输入您要删除的元素的位置：";
	cin >> i;
	ListDelete(L, i, e);
	cout << e;

	return 0;
}

Python代码实现

  • SingleNode
```python

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# @Date    : 2019-10-02 09:32:38

# @Author  : Your Name (you@example.org)

# @Link    : http://example.org

# @Version : $Id$

class SingleNode(object):

	def __init__(self, item):

		self.item = item

		self.next = None

class SingleLinkList(object):

	def __init__(self):

		self._head = None

	def isEmpty(self):

		return self._head == None

	def length(self):

		cur = self._head

		count = 0

		while cur:

			count += 1

			cur = cur.next

		return count

	def travel(self):

		cur = self._head

		while cur:

			print(cur.item, end=" ")

			cur = cur.next

		print()

		return None

	def addFirst(self, item):

		node = SingleNode(item)

		node.next = self._head

		self._head = node

	def append(self, item):

		node = SingleNode(item)

		if self.isEmpty():

			self._head = node

		else:

			cur = self._head

			while cur.next:

				cur = cur.next

			cur.next = node

	def insert(self, pos, item):

		if pos <= 0:

			self.addFirst(item)

		elif pos > (self.length() - 1):

			self.append(item)

		else:

			node = SingleNode(item)

			count = 0

			pre = self._head

			# 数据从0开始

			# 从1开始 应该为 pos - 2

			while count < (pos - 1):

				count += 1

				pre = pre.next

			node.next = pre.next

			pre.next = node

	def remove(self, item):

		cur = self._head

		pre = None

		while cur:

			if cur.item == item:

				if not pre:

					self._head = cur.next

				else:

					pre.next = cur.next

				break

			else:

				pre = cur

				cur = cur.next

	def search(self, item):

		cur = self._head

		while cur:

			if cur.item == item:

				return True

			cur = cur.next

		return False

if __name__ == '__main__':

	sll = SingleLinkList()

	sll.addFirst(10)

	sll.addFirst(20)

	sll.append(30)

	sll.travel()

	sll.remove(10)

	sll.travel()

	print(sll.search(30))

	print(sll.search(10))

	sll.insert(2, 40)

	sll.travel()

	print(sll.length())

	print(sll.isEmpty())

	sll.insert(2, 50)

	sll.travel()

```

	20 10 30 

	20 30 

	True

	False

	20 30 40 

	3

	False

	20 30 50 40 

	[Finished in 0.6s]

  • SingleCycLinkedList
```python

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# @Date    : 2019-10-02 11:13:14

# @Author  : Your Name (you@example.org)

# @Link    : http://example.org

# @Version : $Id$

class SingleNode(object):

	def __init__(self, item):

		self.item = item

		self._head = None

class SingleCysLinkedList(object):

	def __init__(self):

		self._head = None

	def is_empty(self):

		return self._head == None

	def length(self):

		if self.is_empty():

			return 0

		count = 1

		cur = self._head

		while cur.next != self._head:

			count += 1

			cur = cur.next

		return count

	def travel(self):

		if self.is_empty():

			return

		cur = self._head

		print(cur.item, end=" ")

		while cur.next != self._head:

			cur = cur.next

			print(cur.item, end=" ")

		print()

	def addFirst(self, item):

		node = SingleNode(item)

		if self.is_empty():

			self._head = node

			node.next = self._head

		else:

			node.next = self._head

			cur = self._head

			while cur.next != self._head:

				cur = cur.next

			cur.next = node

			self._head = node

	def append(self, item):

		node = SingleNode(item)

		if self.is_empty():

			self._head = node

			node.next = self._head

		else:

			node.next = self._head

			cur = self._head

			while cur.next != self._head:

				cur = cur.next

			cur.next = node

			node.next = self._head

	def insert(self, pos, item):

		if pos<= 0:

			self.addFirst(item)

		elif pos > (self.length() - 1):

			self.append(item)

		else:

			node = SingleNode(item)

			cur = self._head

			count = 0

			while count < (pos - 1):

				count += 1

				cur = cur.next

			node.next = cur.next

			cur.next = node

	def remove(self, item):

		if self.is_empty():

			return

		cur = self._head

		pre = None

		if cur.item == item:

			# 删除第一个元素

			if cur.next != self._head:

				while cur.next != self._head:

					cur = cur.next

				cur.next = self._head.next

				self._head = self._head.next

			else:

				# 只有一个元素

				self._head = None

		else:

			pre = self._head

			while cur.next != self._head:

				if cur.item == item:

					pre.next = cur.next

					return

				else:

					pre = cur

					cur = cur.next

			if cur.item == item:

				pre.next = cur.next

	def search(self, item):

		if self.is_empty():

			return False

		cur = self._head

		if cur.item == item:

			return True

		while cur.next != self._head:

			cur = cur.next

			if cur.item == item:

				return True

		return False	

if __name__ == '__main__':

	ll = SingleCysLinkedList()

	ll.addFirst(1)

	ll.addFirst(2)

	ll.append(3)

	ll.insert(2, 4)

	ll.insert(4, 5)

	ll.insert(0, 6)

	print("length: {0}".format(ll.length()))

	ll.travel()

	print(ll.search(3))

	print(ll.search(7))

	ll.remove(1)

	print("length:", ll.length())

	ll.travel()

```

	length: 6

	6 2 1 4 3 5 

	True

	False

	length: 5

	6 2 4 3 5 

	[Finished in 0.4s]

  • DLinkList “`python
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    # @Date : 2019-10-02 12:10:18
    # @Author : Your Name ([email protected])
    # @Link : http://example.org
    # @Version : $Id$
class Node(object):

	def __init__(self, item):

		self.item = item

		self.next = None

		self.prev = None

class DLinkList(object):

	def __init__(self):

		self._head = None

	def is_empty(self):

		return self._head == None

	def length(self):

		cur = self._head

		count = 0

		while cur:

			count += 1

			cur = cur.next

		return count

	def travel(self):

		cur = self._head

		while cur:

			print(cur.item, end=" ")

			cur = cur.next

		print()

	def add(self, item):

		node = Node(item)

		if self.is_empty():

			self._head = node

		else:

			node.next = self._head

			self._head.prev = node

			self._head = node

	def append(self, item):

		node = Node(item)

		if self.is_empty():

			self._head = node

		else:

			cur = self._head

			while cur.next:

				cur = cur.next

			cur.next = node

			node.prev = cur

	def search(self, item):

		cur = self._head

		while cur:

			if cur.item == item:

				return True

			cur = cur.next

		return False

	def insert(self, pos, item):

		if pos <= 0:

			self.add(item)

		elif pos > (self.length() - 1):

			self.append(item)

		else:

			node = Node(item)

			cur = self._head

			count = 0

			# 移动到指定位置的前一个位置

			while count < (pos - 1):

				count += 1

				cur = cur.next

			# 将node的prev指向cur

			node.prev = cur

			# 将node的next指向cur的下一个结点

			node.next = cur.next

			# 将cur的下一个结点的prev指向node

			cur.next.prev = node

			# 将cur的next指向node

			cur.next = node

	def remove(self, item):

		if self.is_empty():

			return

		else:

			cur = self._head

			if cur.item == item:

				if cur.next == None:

					self._head = None

			else:

				cur.next.prev = None

				self._head = cur.next

			return

		while cur:

			if cur.item == itme:

				cur.prev.next = cur.next

				cur.next.prev = cur.prev

				break

			cur = cur.next

if __name__ == '__main__':

	ll = DLinkList()

	ll.add(1)

	ll.add(2)

	ll.append(3)

	ll.insert(2, 4)

	ll.insert(4, 5)

	ll.insert(0, 6)

	print("length:", ll.length())

	ll.travel()

	print(ll.search(3))

	print(ll.search(4))

	ll.remove(1)

	print("length: {}".format(ll.length()))

	ll.travel()

```

	length: 6

	6 2 1 4 3 5 

	True

	True

	length: 5

	2 1 4 3 5 

	[Finished in 0.1s]

正文完
2022-06-01