开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 第3章线性表 -> 正文阅读

[数据结构与算法]第3章线性表

该部分为学习笔记，具体内容详见：《数据结构（Python语言描述）》一书

第一节线性表的基本概念

线性表简称表，是由 n 个数据元素构成的有限序列，其中 n 称为线性表的表长。线性表具有以下特点：

有穷性：线性表中的元素个数是有限的。
同构性：一般来说，线性表中的所有元素具有相同的性质，即具有相同的类型。如果元素的性质不同，通常不具有实际应用意义。
不同类型元素构成的线性表，例如一个整数线性表和一个图书清单，虽然应用场合不同，但其元素之间的逻辑关系和基本操作是相同的。

第二节线性表的抽象数据类型

抽象数据类型从数据结构的逻辑结构及可对其进行基本操作两个方面进行定义。从定义的操作来看，线性表具有以下特性。

线性表是动态的结构，可以进行元素的插入或删除，长度可以变化。
线性表的插入、删除、读/写等主要操作基于位序进行。

第三节线性表的顺序存储及实现

一、线性表顺序存储的基本方法

线性表的顺序存储方案是将表中的所有元素按照逻辑顺序一次存储在一块连续的存储空间中。线性表的顺序存储结构简称顺序表，可分为两类：元素内置的顺序表和元素外置的顺序表。

元素内置的顺序表
元素外置的顺序表

二、Python 列表的内部实现

Python 列表是一种基于元素外置存储的顺序表。一个列表对象包含引用计数（ob_refcnt）、类型（ob_type）、列表所能容纳的元素个数（allocated）、变长对象的当前长度（ob_size）以及列表元素容器的首指针（ob_item）等信息。列表元素容器是一块连续的内存块，依次存储只想列表中各个数据元素的指针，因此列表元素容器是元素外置的顺序结构。因为每个列表元素也是一个包含类型等信息的完整结构，所以一个 Python 列表中各个元素的类型可以不同。

import sys
lst = []
empty_size = b = sys.getsizeof(lst)
count = 0
print("列表长度 %4d, 总占用字节数 %4d" % (0, b))
for k in range(500):
	lst.append(None)
	a = len(lst)
	old_b = b
	b = sys.getsizeof(lst)
	if b != old_b:
		print("列表长度 %4d, 总占用字节数 %4d，"
			  " 表元素容器大小 % 4d, 增加字节数： % 4d")
			  % (a, b, (b - empty_size) / 8, (b - old_b) / 8))

三、基于 Python 列表的实现

from AbstracList import AbstractList
class PythonList(AbstractList):
	def __init__(self):
		self._entry = []
	
	def __len__(self):
		return len(self._entry)

	def empty(self):
		return not self._entry

	def clear(self):
		self._entry = []

	def insert(self, i, item):
		self._entry.insert(i, item)

	def remove(self, i):
		self._entry.pop(i)

	def retrieve(self, i):
		return self._entry[i]

	def replace(self, i, item):
		self._entry[i] = item

	def contains(self, item):
		return item in self._entry

	def traverse(self):
		print(self._entry)

四、基于底层 C数组的实现

初始化空表的方法

def __init__(self, cap = 0):
	super().__init__()
	self._cur_len = 0
	selef._capacity = cap
	self._entry = self._make_array(self._capacity)

生成一个容量固定的底层C数组

def _make_array(self, cap):
	return (cap * ctypes.py_object)()

判别线性表是否为空

def empty(self):
	return self._cur_len == 0

求线性表的长度

def empty(self):
	return self._cur_len

清空线性表

def clear(self):
	self._capacity = 0
	self._cur_len = 0

将元素 item 添加到线性表的尾部

def append(self, item):
	if self._cur_len == self._capacity:
		if self.capacity == 0:
			cap = 4
		else:
			cap = 2 * self. _capacity
		self._resize(cap)
	self._entry[self._cur_len] = item
	self._cur_len += 1

数组的扩容

def _resize(self, cap):
	temp = self._make_array(cap)
	for k in range(self._cur_len):
		temp[k] = self._entry[k]
	del self._entry
	self._entry = temp
	self.capacity = cap

将元素 item 插入表的 i 号位置

def insert(self, i, item):
	if not 0 <= i <= self._cur_len:
		raise IndexError("插入位置不合法")
	if self._cur_len == self._capacity:
		if self._capacity == 0:
			cap = 4
		else:
			cap = 2 * self._capacity
		self._resize(cap)
	for j in range(self._cur_len, i, -1):
		self._entry[j] = self._entry[j - 1]
	self._entry[i] = item
	self._cur_len += 1

删除 i 号位置的元素

def remove(self, i, item):
	if self.empty():
		raise Exception("underflow")
	if not 0 <= i < self._cur_len:
		raise IndexError("删除位置不合法")
	item = self._entry[i]
	for j in range(i, self._cur_len - 1):
		self._entry[j] = self._entry[j + 1]
	self._cur_len -= 1
	return item

读取 i 号元素

def retrieve(self, i):
	if not 0 <= i < self._cur_len:
		raise IndexError("元素读取位置不合法")
	return self._entry[i]

将 item 值写入表的 i 号位置

def replace(self, i, item):
	if not 0 <= i < self._cur_len:
		raise IndexError("元素写入位置不合法")
	self._entry[i] = item

判断指定元素 item 在表中是否存在

def contains(self, item):
	for i in range(self._cur_len):
		if self._entry[i] == item:
			return True
	return False

将线性表转换成字符串

def __str__(self):
	elements = ''.join(str(self._entry[c]) for c in range(self._cur_len))
	return elements

第四节线性表的链式存储及实现

在链式结构中，元素在内存中的映像称为结点，结点包含元素值和指针域两大部分，其中，指针域用于记录其后继结点或前驱结点的地址。可见，链式结构通过显式的指针域来表明元素的前驱、后继关系。线性表的链式实现结构简称为链表，根据结点中指针域的数目及尾部结点指针的定义，链表可以分为单链表、双向链表、循环链表等。最常见的链表形式是单链表。

一、单链表

单链表的每个结点包含两个域，其中 entry 域存储元素， next 域存储后继结点的指针。为使操作更简单、方便，通常在单链表首结点前附加一个表头结点（简称头结点），即为带头结点的单链表。

定义结点类

class Node:
	def __init__(self, data, next = None):
		self.entry = data
		self.next = next

Python 语言实现一个带头结点的单链表

from AbstractList import AbstractList
from Node import Node
class LinkedList(AbstractList):
	def __init__(self):
	def empty(self):
	def __len__(self):
	def clear(self):
	def insert(self, i, item):
	def remove(self, i):
	def retrieve(self, i):
	def replace(self, i, item):
	def contains(self, item):
	def traverse(self):
	def get_head(self):

初始化空表的方法

def __init__(self):
	self._head = Node(None)

判别线性表是否为空

def empty(self):
	return self._head.next is None

求线性表的长度

def __len__(self):
	p = self._head.next
	count = 0
	while p:
		count += 1
		p = p.next
	return count

清空列表

def clear(self):
	p = self._head.next
	self._head.next = None
	while p:
		q = p
		p = p.next
		del q

读取 i 号元素

def retrieve(self, i):
	if i < 0:
		raise IndexError("元素读取位置不合法，i 小于 0")
	p = self._head.next
	count = 0
	while p and count < i:
		p = p.next
		count += 1
	if p:
		return p.entry
	else:
		raise IndexError("元素读取位置不合法，i 太大，不存在 i号元素")

将元素 item 插入表的 i 号位置

def insert(self, i, item):
	if i<0:
		raise IndexError("插入位置不合法，i值小于0")
	previous = self._head
	count = -1
	while previous and count < i-1:
		previous = previous.next
		count + 1
	if previous is None:
		raise IndexError("插入位置不合法，i太大")
	new_node = Node(item)
	new_node.next = previous.next
	previous.next = new_node

删除 i 号位置的元素

def remove(self, i):
	if i<0:
		raise IndexError("删除位置不合法，i值小于0")
	previous = self._head
	j = -1
	while previous and j<i - 1:
		previous = previous.next
		j += 1
	if previous is None:
		raise IndexError("删除位置不合法，不存在 i - 1 号元素")
	current = previous.next
	if current is None:
		raise IndexError("删除位置不合法，不存在 i 号元素")
	previous.next = current.next
	item = current.data
	del current
	return item

获取头结点

def get_head(self):
	return self._head

二、循环链表

循环链表的概念
如果将单链表的最后一个结点的指针域指向键表开始位置，就构成了循环链表
循环链表与普通单链表的主要差别
（1）判别活动指针 p 是否达到表尾的条件不同。在循环链表中，p 到达表尾时，p.next = head；而在单链表中，p 到达表尾时，p.next = None。
（2）在循环链表中可设头指针 head，也可仅设尾指针 tail 标识一个链表，而在单链表中必须设头指针标识链表。
循环链表的特点
（1）从任一结点出发都可访问到表中的所有结点。
（2）在用头指针标识的单循环链表中，首结点定位操作的时间性能是 $O (1)$ ，尾结点定位操作的时间性能是 $O (n)$ 。
（3）在用尾指针表示的单循环链表中，首结点和尾结点的定位都只需 $O (1)$ 的时间性能。

三、双向链表

双向链表的概念
如果每个结点不仅存储后继结点的指针，还存储前驱结点的指针，这样就形成了双向链表。其中，entry 和 next 的含义跟单链表结点一致，而 prior 指针指向当前结点的前驱结点。双向链表可以带头结点或不带头结点，可以是循环链表或不是循环链表。
双向链表结点类

class DuNode:
	def __init__(self, entry, prior = None, next = None):
		self.entry = entry
		self.prior = prior
		self.next = next

双向链表链表类

from DuNode import DuNode
class DuLinkedList:
	def __init__(self):
		self._head = DuNode(None)
		self._head.next = self._head
		self._head.prior = self._head

	def insert(self, i, item):
		if i < 0:
			raise IndexError("插入位置不合法，i值小于 0 ")
		previous = self._head
		count = -1
		while previous.nexrt != self._head and count < i - 1:
			previous = previous.next
			count += 1
		following = previous.next
		if count == i - 1:
			new_node = DuNode(item, previous, following)
			previous.next = new_node
			flollowing.prior = new_node
		else:
			raise IndexError("插入位置不合法，i 值太大")

双向链表的特点
与单链表相比，双向链表主要有以下特点：
（1）可以根据实际需求不设头指针或尾指针。
（2）在插入或删除结点时，需同时修改前驱和后继两个方向的指针。
（3）因此，在做插入或删除操作时不必定位插入或删除位置的前驱结点，而可以直接定位当前位置结点。

第五节顺序表与链式存储及实现

一、顺序表与链表的比较

类别	优点	缺点	适用场合
顺序表 ? ? ? ?	（1）程序设计简单；（2）元素的物理位置反映逻辑关系，可事先随机存取，根据位序的读/写时间效率为 O(1) ；（3）存储密度为 1	（1）必须事先确定初始表长；（2）插入、删除会带来元素的移动；（3）多次插入后初始空间耗尽，造成溢出或许要空间扩容	（1）表长能事先确定；（2）元素个体较小；（3）很少在非尾部位置插入和删除；（4）经常需要根据位序进行读/写
链表	（1）存储空间动态分配，不需要事先申请空间；（2）不需要担心溢出；（3）插入、删除只引起指针的变化	（1）不能做到随机存取，根据位序读/写效率为 O(n)；（2）链域也占空间，使存储密度降低，必定小于 1；（3）由于涉及指针操作，程序设计的复杂性增大	（1）元素个体较大；（2）不能事先确定表长；（3）很少需要根据位序进行读/写；（4）经常需要做插入、删除和元素重排等

二、各种链表实现的比较

类别	特点和适用场合
不加头结点的单链表	0 号位置的插入、删除等操作需要额外操作，适合递归处理
加了头结点的单链表	可以使 0 号位置的操作与其他位置的操作一致，对空表与非空表的操作一致，使算法得到简化，被广泛使用
循环链表	可以方便地从尾结点走到头结点，方便循环往复地操作
双向链表	存储密度更低，在需要两个方向的操作时适用

三、自顶向下的数据结构实现

数学概念层：确定研究对象的数学模型。例如一个序列。
抽象数据类型层：确定数据之间的关系以及需要哪些概念性操作，但是不需要确定数据实际如何存储或操作如何执行。例如，明确当前的操作对象是一个线性表。
数据结构层：指定足够的细节，分析各操作的行为。
实现层：确定如何在计算机内存中表示数据结构；确定算法实现的细节，例如用底层 C 数组实现顺序表。
应用层：实现特定应用程序所需的所有细节。
注：在用 Python 实现数据结构时，任务是从抽象概念开始，逐步对其进行细化，最终类的方法对应于 ADT 的操作，类的数据成员对应于该数据结构的存储结构，这样就得到了该数据结构的 Python 实现。

四、算法设计的基本步骤

确定算法的详细功能，包括确定函数的入口参数、出口参数和返回值。
分析一般情况下算法的实现步骤，通常可借助图示。
写出一般情况下算法的主体执行部分。
检查入口参数的合法性。
检查特殊情况。
分析算法的性能及可能的改进方法，分析算法的适用场合。

第六节线性表的应用

一、求两个线性表的相同元素

无序线性表下的实现
假设线性表为无序表，例如 A=（7, 2, 1, 9），B=(3, 6, 7, 2, 5)，A 和 B 中的相同元素存放在无序表 C 中，则 C = (7， 2)

def intersect(la, lb):
	m = len(la)
	n = len(lb)
	lc = DynamicArrayList()
	for i in range(m):
		x = la.retrieve(i)
		if lb.contains(x):
			lc.append(x)
	return lc

有序线性表的实现
如果线性表为有序表，在上例中即 A = (1, 2, 7, 9)，B =（2, 3, 5, 6, 7），A 和 B中的相同元素存放在有序表 C 中，则 C=(2, 7)。

def intersect(la, lb):
	m = len(la)
	n = len(lb)
	lc = DynamicArrayList()
	i = 0
	j = 0
	k = 0
	while i < m and j < n:
		item_a = la.retrieve(i)
		item_b = lb. retrieve(j)
		if item_a < item_b:
			i += 1
		elif item_a > item_b:
			j += 1
		else:
			lc.insert(k, item_a)
			k += 1
			i += 1
			j += 1
	return lc

二、约瑟夫环问题

设有 n 个人围坐一圈，从 1 开始顺序编号。现在从第 1 个人开始报数，报到第 m(m>0)的人退出。然后继续 1~ m 的报数，直至所有人退出，最后一个退出的人是优胜者。依次输出出列人员的编号。该问题即著名的约瑟夫环问题。

基于 Python 内置 list 的实现

# 基于 Python 内置 list 的实现
def josephus(n, m):
    people = list(range(1, n + 1))
    i = 0
    for num in range(n, 0, -1):
        i = (i + m - 1) % num
        print(people.pop(i), end = "")
        if num > 1:
            print(",", end="")

if __name__ == "__main__":
    n = int(input("请输入一共有多少人"))
    m = int(input("请输入报哪个数"))
    josephus(n, m)

基于单向循环链表的实现

建立结点值依次为 1 至 n 的不带头结点的单向循环链表

    def create_cll(self, n):
        self._head = p = n_node = Node(1)
        for i in range(2, n + 1):
            n_node = Node(i)
            p.next = n_node
            p = p.next
        n_node.next = self._head

单向循环链表下的循环报数

    def josephus(self, n, m):
        self.create_cll(n)
        p = self._head
        q = p
        count = n
        while q.next != p:
            q = q.next
        while count != 0:
            num = m % count
            if num == 0:
                num = count
            while num > 1:
                q = q.next
                p = p.next
                num -= 1
            print(p.entry, end="")
            if count > 1:
                print(",", end="")
            q.next = p.next
            del p
            count -= 1
            if count == 0:
                break
            p = q.next

第七节线性表算法举例

线性表是使用最广泛的一种数据结构，线性表下的算法设计尤为重要。

一、顺序表下的算法

为底层动态数组实现的顺序表类添加一个方法，删除第 i 号位置开始的 k 个元素

def remove_k(self, i, k):
	if i < 0 or k <= 0 or i + k > self._cur_len:
		raise IndexError("参数不合法")
	for j in range(i + k, self._cur_len):
		self._entry[j - k] = self._entry[j]
	self._cur_len -= k

假设顺序表中存储了若干个整数，设计时间性能和空间性能尽可能高效的算法，将表中小于或等于 x 的元素都放在列表的前端，将大于 x 的元素都放在列表的后端

def adjust(self, x):
	first_large = 0
	for i in range(0, self._cur_len):
		if self._entry[i] <= x:
			self._entry[first_large], self._entry[i] = self._entry[i], self._entry[first_large]
			first_large = first_large + 1

二、带头结点单链表下的算法

为带头结点的单链表类添加一个方法，利用原表空间将单链表中的所有元素进行逆置。

def reverse(self):
	o = self._head.next
	self._head.next = None
	while p:
		q = p.next
		p.next = self._head.next
		self._head.next = p
		p = q

三、与线性表具体实现无关的算法

调用线性表类提供的方法对线性表进行逆置

def reverse(alist):
	i = 0
	j = len(alist) - 1
	while i > j:
		item_a = alist.retrieve(i)
		item_b = alist.retrieve(j)
		alist.replace(i, item_b)
		alist.replace(j, item_a)
		i += 1
		j -= 1

第八节上机实验

一、线性表的顺序表实现

二、线性表的单链表实现

三、线性表的双向非循环链表实现

四、消费支出项目管理

五、每日快递

快递员小峰每日负责 n 个居民小区的快递派送任务。按照公司规定，他应该根据固定路线每天上午和下午各进行一次派送。在派送过程中，他还应该接受小区内已经预定寄出的快递。若某小区的派件数和收件数均为 0，则他不需要前往该小区。每日派送结束后，公司会对每个快递员去过的小区数目、派件数和收件数进行统计。
输入：
（1）第 1 行为居民小区数 n。
（2）第 2 行包含 n 个数字，对应于当天上午 n 个小区的派件数。
（3）第 3 行包含 n 个数字，对应于当天上午 n 个小区的收件数。
（4）第 4 行包含 n 个数字，对应于当天下午 n 个小区的派件数。
（5）第 5 行包含 n 个数字，对应于当天下午 n 个小区的收件数。
输出：快递员一天去过的小区数目、总的派件数和收件数

六、扑克牌整理

原有 n 副扑克牌，但因时间久远均已张数不全。现把它们合在一起，看是否能凑成 m (m < n）副完整的扑克牌（不考虑大王和小王）
（1）输入：输入数据来自文本文件，文件的第 1 行是一个数字 n（1《 n 《 20），表示原有 n副牌。从第 2 行起，每 4 行用于描述一副牌的不同花色（固定为黑、红、梅、方的顺序）的现有张数（各行的第一个数）和牌号 i（1≤i≤13）（各行的其余数字，无序）。
（2）输出：输出的第 1 行是所能拼凑的扑克牌套数。接着按花色输出第 j（1≤j≤n）副扑克牌中剩下的扑克，且对每个花色按牌点大小顺序输出。
（3）采用带头结点的单链表。