一、实验目的
1．掌握用Python定义线性表的顺序存储类型；
2．掌握用Python调试顺序表的基本方法；
3．掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现；
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现线性表顺序存储结构的基本操作。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
（1） 有一个递增有序的整数顺序表L,设计一个算法将整数x插入适当位置，以保持该表的有序性，并给出算法的时间和空间复杂度。例如，L=(1,3,5,7),插入x=6后L=(1,3,5,6,7).
（2） 有一个整数顺序表L，设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个），删除后元素的相对次序不改变，并给出算法的时间和空间复杂度。例如L=（1,2，-1，-2, 3，-3），删除后L=（1,2,3）。
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1．
import time
class SqList:
def __init__(self,capacity=0):
self.capacity=capacity # 最大容量
self.data=[None]*self.capacity # 用于存储数据
self.size=0 # 元素个数计数(线性表有效长度)
def getsize(self): # 获取顺序表长度
return self.size
def CreateSqlist(self,a): # 创建顺序表
for i in range(0,len(a)):
if self.size==self.capacity:
self.resize(2*self.size);
self.data[self.size]=a[i]
self.size+=1
def display(self): # 打印顺序表
for i in range(0,self.size):
print(self.data[i],end=' ')
print()
def resize(self,newcapacity): # 修改线性表的最大容量
if newcapacity>=self.capacity:
self.data=self.data+[None]*(newcapacity-self.capacity)
else:
self.data=self.data[:newcapacity]
self.capacity=newcapacity
def Add(self,e):
if self.size==self.capacity:
self.resize(2*self.size)
self.data[self.size]=e
self.size+=1
def getitem(self,i): # 求顺序表中序号为i的元素
return self.data[i]
def setitem(self,i,x): #设置顺序表中序号为i的元素
self.data[i]=x
def GetNo(self,e): #求顺序表中第一个值为e的元素的逻辑序号
i=0;
while i<self.size and self.data[i]!=e:
i+=1
if (i>=self.size):
return -1;
else:
return i;
def Inserrt(self,i,e): #在顺序表中插入e作为第i个元素
assert 0<=i<=self.size
if self.size==self.capacity:
self.resize(2*self.size)
for j in range(self.size,i-1,-1):
self.data[j]=self.data[j-1]
self.data[i]=e
self.size+=1
def Delete(self,i):
for j in range(i,self.size-1):
self.data[j]=self.data[j+1]
self.size-=1
def insert_sorted_list(L, x):
low, high = 0, len(L) - 1
while low <= high:
mid = (low + high) // 2
if L[mid] == x:
L.insert(mid, x)
return
elif x < L[mid]:
high = mid - 1
else:
low = mid + 1
L.insert(low, x)
if __name__ =='__main__':
L = [1, 3, 5, 7]
start = time.time()
SqList.insert_sorted_list(L, 6)
end = time.time()
print("排序后的列表：", L)
print('运行时间：', end - start)
#因为插入函数 insert_sorted_list() 没有定义在 class SqList 中，而是定义在类外部。你需要将该函数定义在 class SqList 中，或者在调用时加上类名前缀，如 SqList.insert_sorted_list(L, 6)。
2．
class SqList:
def __init__(self,capacity=0):
self.capacity=capacity # 最大容量
self.data=[None]*self.capacity # 用于存储数据
self.size=0 # 元素个数计数(线性表有效长度)
def getsize(self): # 获取顺序表长度
return self.size
def CreateSqlist(self,a): # 创建顺序表
for i in range(0,len(a)):
if self.size==self.capacity:
self.resize(2*self.size);
self.data[self.size]=a[i]
self.size+=1
def display(self): # 打印顺序表
for i in range(0,self.size):
print(self.data[i],end=' ')
print()
def resize(self,newcapacity): # 修改线性表的最大容量
if newcapacity>=self.capacity:
self.data=self.data+[None]*(newcapacity-self.capacity)
else:
self.data=self.data[:newcapacity]
self.capacity=newcapacity
def Add(self,e):
if self.size==self.capacity:
self.resize(2*self.size)
self.data[self.size]=e
self.size+=1
def getitem(self,i): # 求顺序表中序号为i的元素
return self.data[i]
def setitem(self,i,x): #设置顺序表中序号为i的元素
self.data[i]=x
def GetNo(self,e): #求顺序表中第一个值为e的元素的逻辑序号
i=0;
while i<self.size and self.data[i]!=e:
i+=1
if (i>=self.size):
return -1;
else:
return i;
def Inserrt(self,i,e): #在顺序表中插入e作为第i个元素
assert 0<=i<=self.size
if self.size==self.capacity:
self.resize(2*self.size)
for j in range(self.size,i-1,-1):
self.data[j]=self.data[j-1]
self.data[i]=e
self.size+=1
def Delete(self,i):
for j in range(i,self.size-1):
self.data[j]=self.data[j+1]
self.size-=1
def insert_sorted_list(L, x):
low, high = 0, len(L) - 1
while low <= high:
mid = (low + high) // 2
if L[mid] == x:
L.insert(mid, x)
return
elif x < L[mid]:
high = mid - 1
else:
low = mid + 1
L.insert(low, x)
def remove_negative_numbers(L):
i, j = 0, 0
n = len(L)
while i < n:
if L[i] >= 0: # 数值非负，保留在列表中，并移动指针i
L[j] = L[i]
j += 1
i += 1
del L[j:] # 删除末尾的负整数元素
return L
if __name__ =='__main__':
L = [1,2,-1,-2, 3,-3]
SqList.remove_negative_numbers(L)
print("运行结果：", L)
