一、实验目的
1．熟悉查找的基本概念，包括静态查找表和动态查找表、内查找和外查找之间的差异以及平均查找长度等；
2．掌握线性表上的各种查找算法，包括顺序查找、折半查找和分块查找的基本思路、算法实现和查找效率等；
3．灵活运用线性表各种查找算法解决一些综合应用问题。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现线性表上的各种相关算法程序设计和查找过程。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
（1） 编写一个实验程序，对一个递增有序表进行折半查找，输出成功找到其中每个元素的查找序列，用相关数据进行测试。
参考思路：
def BinSearch(R,k): #拆半查找非递归算法
n=len(R)
L=[] #存放查找序列
low,high=0,n-1
while low<=high: #当前区间非空时
mid=(low+high)//2 #求查找区间的中间位置
L.append(R[mid])
if k==R[mid]:
return L
if k<R[mid]: #继续在R[low..mid-1]中查找
……
#主程序
a=[______ ]
print()
print(" 整数序列:",a)
for i in range(len(a)):
L=_________
print(" 查找%d的查找序列:" %(a[i]),end='')
print(L)
（2）假设一个带权图G采用邻接矩阵存储，设计一个算法，采用狄克斯特拉算法思路，求顶点s到顶点t的最短路径长度（假设顶点s和t都是G中的顶点）。
参考思路：
from MatGraph import MatGraph,INF,MAXV
def Dijkstra(g,s,t): #基本Dijkstra算法，求从s到t的最短路径长度
dist=[-1]*MAXV
S=[0]*MAXV
for i in range(n):
dist[i]=g.edges[s][i]
S[s]=1
u=-1
for i in range(n-1):
mindis=INF
for j in range(n):
if S[j]==0 and dist[j]<mindis:
u=j
mindis=dist[j]
if u==t:return dist[t]
S[u]=1
for j in range(n):
if S[j]==0:
if g.edges[u][j]<INF and dist[u]+g.edges[u][j]<dist[j]:
dist[j]=dist[u]+g.edges[u][j]
return INF
#主程序
g=MatGraph()
n,e=_ _,_ _
a=[……] #图7.35的边数组
g.CreateMatGraph(a,n,e)
print("图g")
g.DispMatGraph()
s=_ _
t=_ _
print("求解结果");
print("%s->%d的最短路径长度:%d" %(s,t,Dijkstra(g,s,t)))
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
def BinSearch(R,k): #拆半查找非递归算法
n=len(R)
L=[] #存放查找序列
low,high=0,n-1
while low<=high: #当前区间非空时
mid=(low+high)//2 #求查找区间的中间位置
L.append(R[mid])
if k==R[mid]:
return L
if k<R[mid]: #继续在R[low..mid-1]中查找
high=mid-1
else: #k>R[mid]
low=mid+1 #继续在R[mid+1..high]中查找
return -1 #当前查找区间空时返回-
#主程序
a=[2,4,7,8,9,10,14,18,26,32,40]
print()
print(" 整数序列:",a)
for i in range(len(a)):
L=BinSearch(a,a[i])
print(" 查找%d的查找序列:" %(a[i]),end='')
print(L)
2． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from 图 import MatGraph,INF,MAXV
def Dijkstra(g,s,t): #基本Dijkstra算法，求从s到t的最短路径长度
dist=[-1]*MAXV
S=[0]*MAXV
for i in range(n):
dist[i]=g.edges[s][i]
S[s]=1
u=-1
for i in range(n-1):
mindis=INF
for j in range(n):
if S[j]==0 and dist[j]<mindis:
u=j
mindis=dist[j]
if u==t:return dist[t]
S[u]=1
for j in range(n):
if S[j]==0:
if g.edges[u][j]<INF and dist[u]+g.edges[u][j]<dist[j]:
dist[j]=dist[u]+g.edges[u][j]
return INF
#主程序
g=MatGraph()
n,e=6,10
a=[[1,3,1,4,INF,INF],
[1,3,1,INF,4,INF],
[5,2,0,5,2,1],
[8,INF,8,8,INF,8],
[INF,6,6,INF,6,6],
[INF,INF,9,9,9,9]] #图7.35的边数组
g.CreateMatGraph(a,n,e)
print("图g")
g.DispMatGraph()
s=1
t=9
print("求解结果");
print("%s->%d的最短路径长度:%d" %(s,t,Dijkstra(g,s,t)))
