Python数据结构实验串和数组的实现

一、实验目的

1．熟悉串和数组类型的实现方法，了解简单文字处理的设计方法；

2．熟悉Python语言的字符和把字符串处理的原理和方法；

3．了解矩阵的存储结构，运用Python语言进行矩阵简单运算处理。

二、实验环境

1．Windows操作系统的计算机

2．Python3.7环境平台和PyCharm编辑器

三、实验说明

1．实现串和数组类型的存储结构和基本运算操作。

2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。

3．自主编写程序，必要时参考相关资料。

4．实验学时：2学时

四、实验内容和步骤

1．实验内容（两题必做，一题选做）

（1）串实验题（必做）

① 编写程序，实现BF算法和KMP算法，并做正确性测试。

② 求解模式串t=”ababaaa”的next函数值。

参考框架：


from SqString import SqStringMaxSize=100def BF(s,t):                                                 #BF算法……def GetNext(t,next):                            #由模式串t求出next值……def KMP(s,t):                                              #KMP算法……#主程序        if __name__ == '__main__':……

（2）数组的应用（必做）

多维数组在数学和工程等领域有着非常广泛的应用，特别是在图像处理领域，被处理的数字图像即是一个二维数组。以下是一个非常简单的图像处理程序，请完成以下内容：①为每行代码进行注释；②说明这段程序实现的功能；③运行程序，对结果进行验证。

from PIL import Imageimport numpy as npimport matplotlib.pyplot as pltimage_array1 = np.array(Image.open("python.jpg").convert('L'))image_array2 = 255 - image_array1plt.subplot(121)plt.gray()plt.imshow(image_array1)plt.subplot(122)plt.gray()plt.imshow(image_array2)plt.show()

（3）数组实验题（选做）

求马鞍点问题。如果矩阵a中存在一个元素a[i][j]满足这样的条件：a[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。设计一个程序，计算出m×n的矩阵a的所有马鞍点。

算法思路：

对于二维数组a[m][n]，先求出每行的最小值元素，放入min数组中。再求出每列的最大值元素放入max数组中。若min[i]=max[j]，则该元素a[i][j]便是马鞍点，找出所有这样的元素并输出。

参考框架：

def MinMax(a):m=len(a)                             #行数n=len(a[0])                          #列数min=[0]*mmax=[0]*nfor i in range(m):             #计算每行最小元素，放入min[i]中……for j in range(n):             #计算每列最大元素，放入max[j]中……res=[]                                  #存放马鞍点for i in range(m):             #判定是否为马鞍点for j in range(n):if min[i]==max[j]: #找到一个马鞍点_      return resdef disp(a):             #输出二维数组……#主程序a=                       _      print("\n a:"); disp(a)print(" 所有马鞍点: ")ans=MinMax(a)for i in range(len(ans)):_

2．实验步骤

（1）分析实验内容，写出程序大致框架或完整的程序代码。

（2）进入Python集成环境。

（3）编辑程序并进行保存。

（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。

（5）检查程序输出结果。

五、实验代码与结果（程序运行代码及其结果）

1．（1）给出算法的基本设计思想。

（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

from SqString import SqString    # 导入 SqString 类#BF算法def BF(s,t):i = 0j = 0while i < len(s) and j < len(t):if s[i] == t[j]:i = i + 1j = j + 1else:i = i - j + 1j = 0if j == len(t):return i - jelse:return -1#由模式串t求出next值def GetNext(t,next):j = 0k = -1next[0] = -1while j < len(t) - 1:if k == -1 or t[j] == t[k]:j = j + 1k = k + 1next[j] = kelse:k = next[k]#KMP算法def KMP(s,t):next = [-1]*len(t)GetNext(t,next)i = 0j = 0while i < len(s) and j < len(t):if j == -1 or s[i] == t[j]:i = i + 1j = j + 1else:j = next[j]if j == len(t):return i - jelse:return -1if __name__ == '__main__':# 对于以下字符串进行测试s = SqString()s.StrAssign('BBCABCDABABCDABCDABDE')t = SqString()t .StrAssign('ABCDABD')# BF 算法测试print("== BF 算法 ==")pos = BF(s.get(),t.get())if pos == -1:print("模式串未在主串中找到！")else:print("模式串在主串中的位置为：%d" % (pos+1,))# KMP 算法测试print("\n== KMP 算法 ==")pos = KMP(s.get(),t.get())if pos == -1:print("模式串未在主串中找到！")else:print("模式串在主串中的位置为：%d" % (pos+1,))# 求解 next 值print("\n== 求解 next 值 ==")next = [-1]*len(t.get())GetNext(t.get(),next)print("模式串 ABCDABD的next数组值为：", next)

2．安照题目要求完成。

from PIL import Image#使用PIL库中的Image模块与numpy库import numpy as npimport matplotlib.pyplot as pltimage_array1 = np.array(Image.open("python.jpg").convert('L'))#导入图片并将其转为灰度图image_array2 = 255 - image_array1#每个像素点的颜色值在0-255之间。将image_array1反向取值，生成一个反向的灰度图。plt.subplot(121)plt.gray()# 设置为灰度图plt.imshow(image_array1)# 设置为灰度图plt.subplot(122)plt.gray()# 设置为灰度图plt.imshow(image_array2) # 画出反向图plt.show()

3．（1）给出算法的基本设计思想。

（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

def MinMax(a):m = len(a)  # 行数n = len(a[0])  # 列数row_mins = [min(row) for row in a]  # 计算每行最小元素，放入row_mins列表中col_maxes = [max(col) for col in zip(*a)]  # 计算每列最大元素，放入col_maxes列表中res = []  # 存放马鞍点for i in range(m):   # 判定是否为马鞍点for j in range(n):if a[i][j]==row_mins[i] and a[i][j] == col_maxes[j]:  # 找到一个马鞍点res.append((i,j))return resdef disp(a):  # 输出二维数组for row in a:print(' '.join([str(elem) for elem in row]))# 主程序a = [[4,5,6],[3,2,1],[7,8,9]]print("\n a:"); disp(a)print(" 所有马鞍点: ")ans = MinMax(a)for p in ans:print(f" ({p[0]}, {p[1]})")