[Python][资料结构]稀疏矩阵(二)

给定三元序对

sparse1 = [             [5, 6, 4],              [1, 2, 3],              [2, 1, 6],             [3, 1, 9],              [4, 5, 12]          ]

使用一般转置法，转置

def sparset(sparse):  #稀疏矩阵一般转置    k=0    sparset=[]    sparset.append([sparse[0][1],sparse[0][0],sparse[0][2]])        while k<=sparset[0][1]:        for i in sparse[1:]:            if i[1]==k:                sparset.append([i[1],i[0],i[2]])        k+=1    return sparset

使用快速矩阵转置法，转置

def fastt(sparse): #稀疏矩阵快速转置    rowsize=[0 for _ in range(int(sparse[0][1]))] #用来统计原本矩阵 column有几个0几个1、    rowstart=[0 for _ in range(int(sparse[0][1]))]    sparset=[]   #建立转置后的空阵列        for _ in range(sparse[0][2]):           sparset.append([0,0,0])    for i in sparse[1:]:                        #1.计算rowsize 统计矩阵column的出现次数        rowsize[i[1]]+=1        rowstart[0]=0 #固定填入0    for i in range(1,int(sparse[0][1])):        #2.计算rowstart        rowstart[i]+=rowsize[i-1]+rowstart[i-1]    for i in sparse[1:]:                        #3.回到原三元序对，逐行检查，转置后对照rowstart放入相对应的位置，并且rowstart加1        sparset[rowstart[i[1]]][0]=i[1]        sparset[rowstart[i[1]]][1]=i[0]        sparset[rowstart[i[1]]][2]=i[2]        rowstart[i[1]]+=1    sparset.insert(0,[sparse[0][1],sparse[0][0],sparse[0][2]]) #4.依照三元序对，第一列为total，将第一列放入    return sparset

看结果

martixt1=sparset(sparse1)print("给定三元序对，使用一般转置法转成三元序对:",martixt1) #依照row major排序matrixt=fastt(sparse1)print("给定稀疏矩阵的三元序对，使用快速矩阵转置法转置:",matrixt)