数据结构中一些常用的算法

1.计算二项式系数（动态规划）

# coding:utf-8

# computing C(n,k)
def Binomial_coefficient(n,k):
    if k == 0 or k == n:
        result = 1
    else:
        result = Binomial_coefficient(n-1,k-1)+Binomial_coefficient(n-1,k)
    return result


print Binomial_coefficient(10,3)



2.Floyd算法

# coding:utf-8


# floyd
_ = float('inf')
a = [[0,_,3,_],[2,0,_,_],[_,7,0,1],[6,_,_,0]]


for k in range(4):
    for i in range(4):
        for j in range(4):
            if a[i][j] > a[i][k] + a[k][j]:
                a[i][j] = a[i][k] + a[k][j]
            else:
                pass



print a

3.背包问题

# coding:utf-8


# knapsack_problem
w = [2,1,3,2]
v = [12,10,20,15]
matrix = []
sub_lst = []
for i_i in range(5):
    for j_j in range(6):
        sub_lst.append(0)
    matrix.append(sub_lst)
    sub_lst = []


for i in range(1,5):
    for j in range(1,6):
        if j >= w[i-1]:
            matrix[i][j] = max(matrix[i-1][j],v[i-1]+matrix[i-1][j-w[i-1]])
        else:
            matrix[i][j] = matrix[i-1][j]
print matrix

4.用于计算最小公约数的Euclid算法

# coding:utf-8


# Euclid
def Euclid(m,n):
    while n != 0:
        r = m % n
        m = n
        n = r
    return m

print Euclid(60,24)



5.求一个一维数组中大小最接近的两个元素的差

# coding:utf-8


# minDistance
def minDistance(lst):
    dmin = float('inf')
    for i in range(len(lst)):
        for j in range(len(lst)):
            if i < j and abs(lst[i]-lst[j]) < dmin:
                dmin = abs(lst[i] - lst[j])
            else:
                pass
    return dmin


print minDistance([1,99,5,10,23,80])



6.计算一个十进制数转换为二进制数后的位数

# coding:utf-8


# calculate count of binary


# method1
def Binary(n):
    count = 1
    while n > 1:
        count += 1
        n = n / 2
    return count


print Binary(4)


# method2
def Binary2(n):
    if n == 1:
        return 1
    else:
        return Binary2(n/2)+1
print Binary2(4)

7. 选择排序

# coding:utf-8


# selection_sort
def swap(a,b):
    tmp = a
    a = b
    b = tmp
    return a,b


def Selection_Sort(lst):
    for i in range(len(lst)-1):
        min = i
        for j in range(1,len(lst)):
            if lst[j] < lst[min]:
                min = j
        lst[i],lst[min] = swap(lst[i],lst[min])
    return lst


print Selection_Sort([3,1,2])



8.冒泡排序

# coding:utf-8


# BubbleSort
def swap(a,b):
    tmp = a
    a = b
    b = tmp
    return a,b


def Bubble_sort(lst):
    for i in range(len(lst)-1):
        for j in range(len(lst)-1-i):
            if lst[j+1] < lst[j]:
                lst[j],lst[j+1] = swap(lst[j],lst[j+1])
    return lst


print Bubble_sort([3,1,2])

最后

以上就是冷艳导师为你收集整理的数据结构中一些常用的算法的全部内容，希望文章能够帮你解决数据结构中一些常用的算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。