练习-JZTXT

class SqList:
    def __init__(self):                         #构造函数
        self.initcapacity=5;                    #初始容量设置为5
        self.capacity=self.initcapacity         #容量设置为初始容量
        self.data=[None]*self.capacity          #设置顺序表的空间
        self.size=0                             #长度设置为0

    def resize(self, newcapacity):              #改变顺序表的容量为newcapacity
        assert newcapacity>=0                   #检测参数正确性的断言
        olddata=self.data
        self.data=[None]*newcapacity
        self.capacity=newcapacity
        for i in range(self.size):
            self.data[i]=olddata[i]

    def CreateList(self, a):                    #由数组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                        #添加后元素个数增加1

    def Add(self, e):                           #在线性表的末尾添加一个元素e
        if self.size==self.capacity:            #顺序表空间满时倍增容量
            self.resize(2*self.size)
        self.data[self.size]=e                  #添加元素e
        self.size+=1                            #长度增1

    def getsize(self):                          #返回长度
        return self.size

    def __getitem__(self,i):                    #求序号为i的元素
        assert 0<=i<self.size                   #检测参数i正确性的断言
        return self.data[i]

    def __setitem__(self, i, x):                #设置序号为i的元素
        assert 0<=i<self.size                   #检测参数i正确性的断言
        self.data[i]=x

    def GetNo(self, e):                         #查找第一个为e的元素的序号
        i=0;
        while i<self.size and self.data[i]!=e:
            i+=1                                #查找元素e
        if (i>=self.size):                      #未找到时返回-1
            return -1;
        else:
            return i;                           #找到后返回其序号

    def Insert(self, i, e):                     #在线性表中序号i位置插入元素e
        assert 0<=i<=self.size                  #检测参数i正确性的断言
        if self.size==self.capacity:            #满时倍增容量
            self.resize(2*self.size)
        for j in range(self.size,i,-1):         #将data[i]及后面元素后移一个位置
            self.data[j]=self.data[j-1]
        self.data[i]=e                          #插入元素e
        self.size+=1                            #长度增1

    def Delete(self, i):                        #在线性表中删除序号i的元素
        assert 0<=i<=self.size-1                #检测参数i正确性的断言
        for j in range(i,self.size-1):
            self.data[j]=self.data[j+1]         #将data[i]之后的元素前移一个位置
        self.size-=1                            #长度减1
        if self.capacity>self.initcapacity and self.size<=self.capacity/4:
            self.resize(self.capacity//2)       #满足要求容量减半

    def Deletek(self, i, k):          #删除从序号i开始的k个元素
         assert i>=0 and k>=1 and i+k>=1 and i+k<=L.getsize()
         for j in range(i+k,L.getsize()):
           #将要删除的元素均前移k个位置
             L[j-k]=L[j]
         L.size-=k          #长度减k


    def Deletex1(self, x):                  #删除其中所有值为x的元素
        k=0
        for i in range(L.getsize()):
            if L[i]!=x:         #将不为x的元素插入到data中
                L[k]=L[i]
                k+=1
        L.size=k                            #重置长度为k



    def Deletex2(self, x):               #删除其中所有值为x的元素
      k=0;
        for i in range(L.getsize()):
            if L[i]!=x:         #将不为x的元素前移k个位置
                L[i-k]=L[i]
            else:               #累计删除的元素个数k
                k+=1
        L.size-=k               #重置长度减少k


    def Deletex3(self, x):              #删除其中所有值为x的元素
         i=-1
         j=0
         while j<L.getsize():       #j遍历所有元素
             if L[j]!=x:            #找到不为x的元素a[j]
                 i+=1                   #扩大不为x的区间
                 if i!=j:
                     L[i],L[j]=L[j],L[i]        #将序号为i和j的两个元素交换
             j+=1               #继续扫描
         L.size=i+1             #重置长度为i+1


    def Reverse(self):              #所有元素逆置
         i=0
         j=L.getsize()-1
         while i<j :
             L[i],L[j]=L[j],L[i]   #两个元素交换
             i+=1
             j-=1


    def Merge2(self,A,B):              #求解算法
         C=SqList()                              #新建顺序表C
         i=j=0                                   #i用于遍历A,j用于遍历B
         while i<A.getsize() and j<B.getsize(): #两个表均没有遍历完毕
            if A[i]<B[j]:
                 C.Add(A[i])                     #将较小的A中元素添加到C中
                 i+=1
            else:
                C.Add(B[j])                     #将较小的B中元素添加到C中
                j+=1
         while i<A.getsize():                   #若A没有遍历完毕
                C.Add(A[i])
                i+=1
         while j<B.getsize():                   #若B没有遍历完毕
            C.Add(B[j])
            j+=1
         return C                                #返回C


    def Middle(self,A,B):                                #求解算法
        i=j=k=0
        while i<A.getsize() and j<B.getsize():      #两个有序顺序表均没有扫描完
            k+=1                                    #元素比较次数增1
            if A[i]<B[j]:                           #A中当前元素为较小的元素
                if k==A.getsize():                  #恰好比较了n次
                    return A[i]                     #返回A中的当前元素
                i+=1
            else:                                   #B中当前元素为较小的元素
                if k==B.getsize():                  #恰好比较了n次
                    return B[j]                     #返回B中的当前元素
            j+=1



    def display(self):                          #输出顺序表
        for i in range(0,self.size):
            print(self.data[i],end=' ')
        print()

if __name__ == '__main__':
    L=SqList()
    for i in range(1,6):
        L.Add(i)
    print("L[初始容量=%d,长度=%d]: " %(L.capacity,L.getsize()),end=''),L.display()

    print("序号为2的元素=%d" %(L[2]))
    print("设置序号为2的元素为8")
    #L[2]=8
    L.__setitem__(2,8)
    print("当前L: ",end=''),L.display()
    print("当前size=%d" %(L.getsize()))

    #for i in range(0,L.getsize()):
    print("删除%d序号的元素" %(0))
    L.Delete(0)
    print("当前L: ",end=''),L.display()
    print("当前size=%d" %(L.getsize()))

    print("在序号为3的位置插入元素为6")
    L.Insert(3, 6)
    print("当前L: ",end=''),L.display()
    print("当前size=%d" %(L.getsize()))

    print("在序号为5的位置插入元素为4")
    L.Insert(5, 4)
    #print("当前L: ",end=''),L.display()
    #print("当前size=%d" %(L.getsize()))
    print("L[当前容量=%d,长度=%d]: " %(L.capacity,L.getsize()),end=''),L.display()

    print("序号为3的元素=%d" %(L.__getitem__(3)))

    print("2号位置元素的序号=%d" %(L.GetNo(L[2])))

    print("元素4的序号=%d" %(L.GetNo(4)))

    print("所有元素逆置后L:")
    L.Reverse()
    L.display()


    print("删除从序号4开始的2个元素")
    L.Deletek(4, 2)
    print("L[当前容量=%d,长度=%d]: " %(L.capacity,L.getsize()),end=''),L.display()

    print("删除其中值为4的所有元素后L:")
   # L.Deletex1(4)
   # L.Deletex2(4)
    L.Deletex3(4)
    L.display()


    A=SqList()
    for i in range(1,6):
        A.Add(i)
    print("A: ",end=''),A.display()

    B=SqList()
    for i in range(1,6):
        B.Add(i+2)
    print("B: ",end=''),B.display()

    #C=SqList()
    print("合并A和B得到二路归并：")
    L.Merge2(A,B)
    print("L: ",end=''),L.display()
    L=L.Merge2(A,B)
    print("C: ",end=''),L.display()
    print("L[当前容量=%d,长度=%d]: " %(L.capacity,L.getsize()),end=''),L.display()



    print("求中位数")
    print("结果: %d " %(L.Middle(A,B)))