【10】数据结构的矩阵与广义表篇章

二维以上矩阵

矩阵存储方式

行序优先存储

• 求任意元素地址计算公式：

Address(A[i][j]) = BaseAddress + ( i × n + j ) × ElementSize

• 其中：
  BaseAddress 是数组的基地址，即数组第一个元素 A[0][0] 的地址。
  i 是行索引，范围从 0 到 m−1。
  j 是列索引，范围从 0 到 n−1。
  ElementSize 是数组中每个元素的大小（以字节为单位）。

列序优先存储

• 求任意元素地址计算公式：

Address(A[i][j]) = BaseAddress+ ( j × m + i ) × ElementSize

• 其中：
  BaseAddress 是数组的基地址，即数组第一个元素 A[0][0] 的地址。
  i 是行索引，范围从 0 到 m−1。
  j 是列索引，范围从 0 到 n−1。
  ElementSize 是数组中每个元素的大小（以字节为单位）。

特殊矩阵

对称矩阵

• n阶方阵元素满足：a[i][j] == a[j][i]

• 按行序优先存储方式：仅存储对称矩阵的下三角元素，将元素存储到一维数据A[0]~A[n(n+1)/2]中，则A[k]与二维矩阵a[i][j]地址之间的对应关系公式为：

$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+j,& \text{if }i\ge j\\ \frac{j(j-1)}{2}+i,& \text{if }i<j\end{array}$$

稀疏矩阵

• 定义：矩阵的非零元素比零元素少，且分布没有规律。
• 稀疏矩阵的两种存储方式：
  • 三元组
  • 十字链表

三元组方式存储稀疏矩阵的实现

• 特点：为了节省存储空间，只存储非零元素数值，因此，还需存储元素在矩阵中对应的行号与列号，形成唯一确定稀疏矩阵中任一元素的三元组:

(row, col, data)
row 行号
col 列号
data 非零元素值

三元组初始化

class Triples:"""三元组初始化"""def __init__(self):self.row = 0    # 行号self.col = 0    # 列号self.data = None    # 非零元素值

稀疏矩阵的初始化

class Matrix:"""稀疏矩阵初始化"""def __init__(self, row, col):# 行数self.row = row# 列数self.col = col# 最大容量self.maxSize = row * col# 非零元素的个数self.nums = 0# 存储稀疏矩阵的三元组self.matrix = [Triples() for i in range(self.maxSize)]

稀疏矩阵的创建

• 通过指定行列与元素值的方式进行插入创建
• 行序优先原则
• 主要通过if语句对不同的比较结果流向不同的分支。

    def insert(self, row, col, data):"""将数据插入三元组表示的稀疏矩阵中，成功返回0，否则返回-1:param row: 行数:param col: 列数:param data: 数据元素:return: 是否插入成功"""# 判断当前稀疏矩阵是否已满if (self.nums >= self.maxSize):print('当前稀疏矩阵已满')return -1# 判断列表是否溢出if row > self.row or col > self.col or row < 1 or col < 1:print("你输入的行或列的位置有误")return -1# 标志新元素应该插入的位置p = 1# 插入前判断稀疏矩阵没有非零元素if (self.nums == 0):self.matrix[p].row = rowself.matrix[p].col = colself.matrix[p].data = dataself.nums += 1return 0# 循环，寻找合适的插入位置for t in range(1, self.nums+1):# 判断插入行是否比当前行大if row > self.matrix[t].row:p += 1# 行数相等，但是列数大于当前列数if (row == self.matrix[t].row) and (col > self.matrix[t].col):p += 1# 判断该位置是否已有数据，有则更新数据if (row == self.matrix[p].row) and (col == self.matrix[p].col) and self.matrix[p].data == 0:self.matrix[p].data = datareturn 0# 移动p之后的元素for i in range(self.nums, p-1, -1):self.matrix[i+1] = self.matrix[i]# 插入新元素self.matrix[p].row = rowself.matrix[p].col = colself.matrix[p].data = data# 元素个数加一self.nums += 1return 0

展示当前稀疏矩阵

    def display(self):"""稀疏矩阵展示:return:"""if self.nums == 0:print('当前稀疏矩阵为空')returnprint(f'稀疏矩阵的大小为:{self.row} × {self.col}')# 标志稀疏矩阵中元素的位置p = 1# 双重循环for i in range(1, self.row+1):for j in range(1, self.col+1):if i == self.matrix[p].row and j == self.matrix[p].col:print("%d"%self.matrix[p].data, end='\t')p += 1else:print(0, end='\t')print()

稀疏矩阵的转置

• 将矩阵中的所有每个元素a[i][j] = a[j][i]，其中a[i][j]与a[j][i]都存在。
• 每查找矩阵的一列，都完整地扫描器三元组数组，并进行行列颠倒。
• 要查找矩阵的每一列即每次都要定格行号。

    def transpose(self):"""稀疏矩阵的转置:return: 返回转置后的稀疏矩阵"""# 创建转置后的目标稀疏矩阵matrix = Matrix(self.col, self.row)matrix.nums = self.nums# 判断矩阵是否为空if self.nums > 0:# 标志目标稀疏矩阵中元素的位置q = 1# 双重循环，行列颠倒for col in range(1, self.row+1):# p标志渊矩阵中元素的位置for p in range(1, self.nums+1):# 如果列相同，则行列颠倒if self.matrix[p].col == col:matrix.matrix[q].row = self.matrix[p].colmatrix.matrix[q].col = self.matrix[p].rowmatrix.matrix[q].data = self.matrix[p].dataq += 1return matrix

三元组稀疏矩阵的调试与总代码

# 17.稀疏矩阵的实现
class Triples:"""三元组初始化"""def __init__(self):self.row = 0    # 行号self.col = 0    # 列号self.data = None    # 非零元素值class Matrix:"""稀疏矩阵初始化"""def __init__(self, row, col):# 行数self.row = row# 列数self.col = col# 最大容量self.maxSize = row * col# 非零元素的个数self.nums = 0# 存储稀疏矩阵的三元组self.matrix = [Triples() for i in range(self.maxSize)]def insert(self, row, col, data):"""将数据插入三元组表示的稀疏矩阵中，成功返回0，否则返回-1:param row: 行数:param col: 列数:param data: 数据元素:return: 是否插入成功"""# 判断当前稀疏矩阵是否已满if (self.nums >= self.maxSize):print('当前稀疏矩阵已满')return -1# 判断列表是否溢出if row > self.row or col > self.col or row < 1 or col < 1:print("你输入的行或列的位置有误")return -1# 标志新元素应该插入的位置p = 1# 插入前判断稀疏矩阵没有非零元素if (self.nums == 0):self.matrix[p].row = rowself.matrix[p].col = colself.matrix[p].data = dataself.nums += 1return 0# 循环，寻找合适的插入位置for t in range(1, self.nums+1):# 判断插入行是否比当前行大if row > self.matrix[t].row:p += 1# 行数相等，但是列数大于当前列数if (row == self.matrix[t].row) and (col > self.matrix[t].col):p += 1# 判断该位置是否已有数据，有则更新数据if (row == self.matrix[p].row) and (col == self.matrix[p].col) and self.matrix[p].data == 0:self.matrix[p].data = datareturn 0# 移动p之后的元素for i in range(self.nums, p-1, -1):self.matrix[i+1] = self.matrix[i]# 插入新元素self.matrix[p].row = rowself.matrix[p].col = colself.matrix[p].data = data# 元素个数加一self.nums += 1return 0def display(self):"""稀疏矩阵展示:return:"""if self.nums == 0:print('当前稀疏矩阵为空')returnprint(f'稀疏矩阵的大小为:{self.row} × {self.col}')# 标志稀疏矩阵中元素的位置p = 1# 双重循环for i in range(1, self.row+1):for j in range(1, self.col+1):if i == self.matrix[p].row and j == self.matrix[p].col:print("%d"%self.matrix[p].data, end='\t')p += 1else:print(0, end='\t')print()def transpose(self):"""稀疏矩阵的转置:return: 返回转置后的稀疏矩阵"""# 创建转置后的目标稀疏矩阵matrix = Matrix(self.col, self.row)matrix.nums = self.nums# 判断矩阵是否为空if self.nums > 0:# 标志目标稀疏矩阵中元素的位置q = 1# 双重循环，行列颠倒for col in range(1, self.row+1):# p标志渊矩阵中元素的位置for p in range(1, self.nums+1):# 如果列相同，则行列颠倒if self.matrix[p].col == col:matrix.matrix[q].row = self.matrix[p].colmatrix.matrix[q].col = self.matrix[p].rowmatrix.matrix[q].data = self.matrix[p].dataq += 1return matrixif __name__ == '__main__':# # 17.稀疏矩阵# # 创建稀疏矩阵matrix1 = Matrix(6, 7)matrix1.display()# 向矩阵中插入数据matrix1.insert(1, 1, 88)matrix1.insert(1, 2, 11)matrix1.insert(1, 3, 21)matrix1.insert(1, 4, 66)matrix1.insert(1, 7, 77)matrix1.insert(2, 2, 40)matrix1.insert(2, 4, 2)matrix1.insert(2, 7, 52)matrix1.insert(3, 1, 92)matrix1.insert(3, 6, 85)matrix1.insert(4, 3, 12)matrix1.insert(5, 1, 67)matrix1.insert(5, 2, 26)matrix1.insert(5, 4, 64)matrix1.insert(6, 3, 55)matrix1.insert(6, 5, 10)matrix1.display()# 矩阵转置matrix2 = matrix1.transpose()matrix2.display()

• 运行结果
  

十字链表方式存储稀疏矩阵的实现

• 十字链表的结点结构图

• 十字链表头结点结构图

• 以下面矩阵为例，稀疏矩阵十字链表的表示图

$$\left(\begin{array}{cccc}1& 0& 0& 2\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)$$

十字链表数据标签初始化

class Tag:def __init__(self):"""十字链表数据标签初始化"""self.data = Noneself.link = None

十字链表结点初始化

class Node:def __init__(self):"""十字链表结点初始化"""self.row = 0self.col = 0self.right = Noneself.down = Noneself.tag = Tag()

十字链表初始化

    def __init__(self, row, col):"""十字链表初始化:param row: 行数:param col: 列数"""self.row = rowself.col = colself.maxSize = row if row > col else colself.head = Node()self.head.row = rowself.head.col = col

十字链表的创建

• 这部分代码个人理解的很吃力，有没有人可以有更好的方式理解

    def create(self, datas):"""创建十字链表，使用列表进行初始化:param datas: 二维列表数据:return:"""# 定义头结点的指针列表head = [Node() for i in range(self.maxSize)]# 初始化头结点的指针列表tail = self.headfor i in range(0, self.maxSize):# 构建循环链表head[i].right = head[i]head[i].down = head[i]tail.tag.link = head[i]tail = head[i]# 将指针重新指向矩阵头结点tail.tag.link = self.head# 循环，添加元素for i in range(0, self.row):for j in range(0, self.col):# 判断列表中的元素是否为0if (datas[i][j] != 0):# 初始化新结点newNode = Node()newNode.row = inewNode.col = jnewNode.tag.data = datas[i][j]# 插入行链表node = head[i]while node.right != head[i] and node.right.col < j:node = node.rightnewNode.right = node.rightnode.right = newNode# 插入列链表node = head[j]while node.down != head[j] and node.down.row < i:node = node.downnewNode.down = node.downnode.down = newNode

十字链表的展示

    def display(self):print(f"行={self.row}, 列 = {self.col}")# 将列链的结点指向列中第一个结点colNode = self.head.tag.link# 循环列链while colNode != self.head:# 行链的结点指向行中第一个结点rowNode = colNode.right# 循环行链while colNode != rowNode:print(f"({rowNode.row + 1},{rowNode.col+1},{rowNode.tag.data})")rowNode = rowNode.rightcolNode = colNode.tag.link

十字链表形式稀疏矩阵的调试与总代码

# 17-1稀疏矩阵的十字链链表实现
class Tag:def __init__(self):"""十字链表数据标签初始化"""self.data = Noneself.link = Noneclass Node:def __init__(self):"""十字链表结点初始化"""self.row = 0self.col = 0self.right = Noneself.down = Noneself.tag = Tag()class Mat(object):def __init__(self, row, col):"""十字链表初始化:param row: 行数:param col: 列数"""self.row = rowself.col = colself.maxSize = row if row > col else colself.head = Node()self.head.row = rowself.head.col = coldef create(self, datas):"""创建十字链表，使用列表进行初始化:param datas: 二维列表数据:return:"""# 定义头结点的指针列表head = [Node() for i in range(self.maxSize)]# 初始化头结点的指针列表tail = self.headfor i in range(0, self.maxSize):# 构建循环链表head[i].right = head[i]head[i].down = head[i]tail.tag.link = head[i]tail = head[i]# 将指针重新指向矩阵头结点tail.tag.link = self.head# 循环，添加元素for i in range(0, self.row):for j in range(0, self.col):# 判断列表中的元素是否为0if (datas[i][j] != 0):# 初始化新结点newNode = Node()newNode.row = inewNode.col = jnewNode.tag.data = datas[i][j]# 插入行链表node = head[i]while node.right != head[i] and node.right.col < j:node = node.rightnewNode.right = node.rightnode.right = newNode# 插入列链表node = head[j]while node.down != head[j] and node.down.row < i:node = node.downnewNode.down = node.downnode.down = newNodedef display(self):print(f"行={self.row}, 列 = {self.col}")# 将列链的结点指向列中第一个结点colNode = self.head.tag.link# 循环列链while colNode != self.head:# 行链的结点指向行中第一个结点rowNode = colNode.right# 循环行链while colNode != rowNode:print(f"({rowNode.row + 1},{rowNode.col+1},{rowNode.tag.data})")rowNode = rowNode.rightcolNode = colNode.tag.linkif __name__ == '__main__':print('PyCharm')# 17-1：稀疏矩阵的十字链表datas = [[1, 0, 8, 2], [0, 0, 1, 0], [0, 9, 0, 1]]mat = Mat(3, 4)mat.create(datas)mat.display()

• 运行结果

广义表的实现

• 特点
  • 一种非线性数据结构
  • 既可以存储线性表中的数据
  • 也可以存储广义表自身结构
  • 广义表的长度为表中元素个数，最外层圆括号包含的元素个数
  • 广义表的深度为表中所含圆括号的重数
  • 广义表可被其他广义表共享
  • 可进行递归，深度无穷，长度有限
• 广义表链式存储结点结构图

• tag：又称标志位，表结点标志位为1，原子结点标志位为0.
• atom/lists：称存储单元，用于存储元素或指向子表结点.
• link：称指针域，用于指向下一个表结点.

存储结点初始化

class Node:def __init__(self, tag, atom, lists, link):"""广义表结点的初始化:param tag: 标志域:param atom: 存储元素:param lists: 指向子表结点:param link: 下一个表结点"""self.tag = tagself.atom = atomself.lists = listsself.link = link

• 广义表链式存储示意图
  • 以A,B,C,D,E五个广义表为例

A = ()
B = §
C = ((x, y, z), p)
D = (A, B, C)
E = (q, E)

• 广义表的分类
• 单元素表：如B
• 空表：如A
• 非空多元素广义表：如C、D

广义表初始化

class GList:def __init__(self):"""广义表的初始化"""self.root = Node(1, None, None, None)

广义表的创建

• 核心思想
  • "("符号。遇到左圆括号，表明遇到一张表，申请一个结点空间，将tag设为1，再进行递归调用，将结点lists指针地址作为参数传入函数；
  • ")"符号。遇到右圆括号，表明前面字符处理完成，将传入的参数指针lists指针或link指针地址设置为空;
  • “,”。遇到逗号，表明当前结点处理完成，顺延处理后继结点，传入link指针地址作为参数进行递归调用;
  • 其他字符。表明为结点中存储数据，将tag设为0，件当前字符赋值给atom.

    def create(self, datas):"""创建广义表:param datas: 广义表数据:return:"""# 移除所有空格datas = datas.replace(" ", "")# 获取数据长度strlen = len(datas)# 保存双亲结点nodeStack = Stack(100)self.root = Node(1, None, None, None)tableNode = self.rootfor i in range(strlen):# 判断是否为子表的开始if datas[i] == '(':# 新子表结点tmpNode = Node(1, None, None, None)# 将双亲结点入栈，用于子表结束时获取nodeStack.push(tableNode)tableNode.lists = tmpNodetableNode = tableNode.lists# 判断是否为子表的结束elif datas[i] == ')':#子表结束，指针指向子表双亲结点if tableNode == nodeStack.peak():tableNode = Node(1, None, None, None)tableNode = nodeStack.pop()# 表节点elif datas[i] == ',':tableNode.link = Node(1, None, None, None)tableNode = tableNode.link# 原子结点else:tableNode.tag = 0tableNode.atom = datas[i]

输出广义表

• 核心思想
• 1.tag为0，表明表为单元素表，直接输出元素；
• 2.tag为1，输出左圆括号"("，判断lists;
  • 若lists为None，表明为空表，输出右圆括号")";
  • 若lists不为空，进行递归调用，将lists作为参数传入函数;
• 3.子表结点输出完成后，回归递归调用处，判断link;
  • 若link为None，表明本层遍历结束，返回函数调用；
  • 若link不为空，表明本层当前元素还有后继结点，输出一个","逗号，之后再进行递归调用，将link作为参数传入函数.
• 在进行遍历扫描之前，对表中所有的空格进行删除处理，避免干扰运行.

    def display(self, node):"""展示广义表:param node: 广义表的第一个结点:return:"""if node.tag == 0:print(node.atom, end="")else:print("(", end="")if node.lists != None:self.display(node.lists)print(")", end="")if node.link != None:print(",", end="")self.display(node.link)if node == self.root:print()

广义表的深度

• 求解思路
  • tag为0，返回深度0.
  • tag为1，再根据lists判断表深度
    • 表空，返回深度1.
    • 表不为空，遍历每个元素，递归遍历子表元素.

    def depth(self, node):"""递归返回，判断为原子结点时返回0:param node: 广义表的第一个结点:return:"""if node.tag == 0:return 0maxSize = 0depth = -1# 指向第一个子表tableNode = node.lists# 如果子表为空，则返回1if tableNode == None:return 1# 循环while tableNode != None:if tableNode.tag == 1:depth = self.depth(tableNode)# maxSize为同一层所求的子表中深度最大值if depth > maxSize:maxSize = depthtableNode = tableNode.linkreturn maxSize + 1

广义表的长度

    def length(self):length = 0# 指向广义表的第一个元素node = self.root.listswhile node != None:# 累加元素个数length += 1node = node.linkreturn length

广义表的调试与总代码

# 18.广义表
class Node:def __init__(self, tag, atom, lists, link):"""广义表结点的初始化:param tag: 标志域:param atom: 存储元素:param lists: 指向子表结点:param link: 下一个表结点"""self.tag = tagself.atom = atomself.lists = listsself.link = linkclass GList:def __init__(self):"""广义表的初始化"""self.root = Node(1, None, None, None)def create(self, datas):"""创建广义表:param datas: 广义表数据:return:"""# 移除所有空格datas = datas.replace(" ", "")# 获取数据长度strlen = len(datas)# 保存双亲结点nodeStack = Stack(100)self.root = Node(1, None, None, None)tableNode = self.rootfor i in range(strlen):# 判断是否为子表的开始if datas[i] == '(':# 新子表结点tmpNode = Node(1, None, None, None)# 将双亲结点入栈，用于子表结束时获取nodeStack.push(tableNode)tableNode.lists = tmpNodetableNode = tableNode.lists# 判断是否为子表的结束elif datas[i] == ')':#子表结束，指针指向子表双亲结点if tableNode == nodeStack.peak():tableNode = Node(1, None, None, None)tableNode = nodeStack.pop()# 表节点elif datas[i] == ',':tableNode.link = Node(1, None, None, None)tableNode = tableNode.link# 原子结点else:tableNode.tag = 0tableNode.atom = datas[i]def display(self, node):"""展示广义表:param node: 广义表的第一个结点:return:"""if node.tag == 0:print(node.atom, end="")else:print("(", end="")if node.lists != None:self.display(node.lists)print(")", end="")if node.link != None:print(",", end="")self.display(node.link)if node == self.root:print()def depth(self, node):"""递归返回，判断为原子结点时返回0:param node: 广义表的第一个结点:return:"""if node.tag == 0:return 0maxSize = 0depth = -1# 指向第一个子表tableNode = node.lists# 如果子表为空，则返回1if tableNode == None:return 1# 循环while tableNode != None:if tableNode.tag == 1:depth = self.depth(tableNode)# maxSize为同一层所求的子表中深度最大值if depth > maxSize:maxSize = depthtableNode = tableNode.linkreturn maxSize + 1def length(self):length = 0# 指向广义表的第一个元素node = self.root.listswhile node != None:# 累加元素个数length += 1node = node.linkreturn lengthif __name__ == '__main__':print('PyCharm')# 18.广义表的实现datas = "(a, b, (c, d), ((e, f), g))"gList = GList()gList.create(datas)gList.display(gList.root)print(f"广义表的长度:{gList.length()}")print(f"广义表的深度:{gList.depth(gList.root)}")

• 运行结果