二維以上矩陣

矩陣存儲方式

行序優先存儲

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

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)}")

• 運行結果