黑马程序员技术交流社区

标题: 【上海校区】数组与链表算法 [打印本页]

---

作者: 梦缠绕的时候    时间: 2019-2-26 10:59
标题: 【上海校区】数组与链表算法
数组与链表都是相当重要的结构化数据类型(structured data type)，也都是典型线性表的应用。按照内存存储的方式，基本上可分为以下两种方式：
1.静态数据结构(static data structure)
数据类型就是一种典型的静态数据结构，它使用连续分配的内存空间(contiguous allocation)来存储有序表中的数据。静态数据结构是在编译时就给相关的变量分配好内存空间。缺点是删除或加入数据时，需要移动大量的数据

2.动态数据结构(dynamic data structure)
动态数据结构又称为"链表"(linked list)，它使用不连续的内存空间存储具有线性表特性的数据。优点是数据的插入或删除都相当方便，不需要移动大量数据

0x01 矩阵
从数学的角度来看，对于mxn矩阵(matrix)的形式，可以用计算机中A(m,n)的二维数据来描述


“深度学习”(Deep Learning,DL)源自于人工神经网络(artificial neural network)模型，并且结合了神经网络架构与大量的运算资源，目的在于让机器建立与模拟人脑进行学习的神经网络，以解读大数据中的图像，声音和文字等多种信息。神经网络将权重存储在矩阵中，矩阵可以是多维的，以便考虑各种参数的组合

一.矩阵相加
1.原理简介
矩阵的相加运算较为简单，前提是相加的两个矩阵对应的行数与列数都必须相等，而相加后矩阵的行数与列数也是相同的。例如A+B=C



2.程序说明
2.1功能要求
说明3个二维数组，实现两个矩阵相加的过程，并显示结果

2.2源程序

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

A = [[1,3,5],[7,9,11],[13,15,17]]
B = [[9,8,7],[6,5,4],[3,2,1]]

N = 3
C = [[None] * N for row in range(N)]

for i in range(3):
    for j in range(3):
        C[i][j] = A[i][j] + B[i][j]
print("矩阵A和矩阵B相加的结果：")
for i in range(3):
    for j in range(3):
        print("%d" %C[i][j],end="\t")
    print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2.3运行结果

矩阵A和矩阵B相加的结果：
10        11        12       
13        14        15       
16        17        18       
1
2
3
4
二.矩阵相乘
1.原理简介
两个矩阵A与B的相乘受到某些条件的限制。首先必须符合A为一个mn的矩阵，B为一个np的矩阵，对AB之后的结果为一个mp的矩阵C


c11 = a11*b11+a12*b21+...+a1n+bn1
.
.
c1p = a11*b1p+a12*b2p+...+a1n+bnp
.
.
cmp = am1*b1p+am2*b2p+...+amn+bnp
1
2
3
4
5
6
7
2.程序说明
2.1功能要求
实现两个可自行输入矩阵维数的矩阵相乘过程，并显示输出结果

2.2源程序

def MatrixMultiply(arrA, arrB,arrC,M,N,P):
    global C
    if M<=0 or N<=0 or P<=0:
        print('[错误:维数M,N,P必须大于0]')
        return
    for i in range(M):
        for j in range(P):
            Temp=0
            for k in range(N):
                Temp = Temp + int(arrA[i*N+k])*int(arrB[k*P+j])
            arrC[i*P+j] = Temp

print('请输入矩阵A的维数(M,N): ')
M=int(input('M= '))
N=int(input('N= '))
A=[None]*M*N #声明大小为MxN的列表A

print('[请输入矩阵A的各个元素]')
for i in range(M):
    for j in range(N):
        A[i*N+j]=input('a%d%d='%(i,j))

print('请输入矩阵B的维数(N,P): ')
N=int(input('N= '))
P=int(input('P= '))

B=[None]*N*P #声明大小为NxP的列表B

print('[请输入矩阵B的各个元素]')
for i in range(N):
    for j in range(P):
        B[i*P+j]=input('b%d%d='%(i,j))

C=[None]*M*P #声明大小为MxP的列表C
MatrixMultiply(A,B,C,M,N,P)
print('[AxB的结果是]')
for i in range(M):
    for j in range(P):
        print('%d' %C[i*P+j], end='\t')
    print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2.3运行结果

请输入矩阵A的维数(M,N):
M= 2
N= 3
[请输入矩阵A的各个元素]
a00=5
a01=4
a02=4
a10=5
a11=5
a12=5
请输入矩阵B的维数(N,P):
N= 3
P= 2
[请输入矩阵B的各个元素]
b00=2
b01=4
b10=5
b11=4
b20=4
b21=5
[AxB的结果是]
46        56       
55        65       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
三.转置矩阵
1.原理简介
“转置矩阵”(A)就是把原矩阵的行坐标元素与列坐标元素互相调换，假设A为A的转置矩阵，则有A[i,j]=A[j,i]




2.程序说明
2.1功能要求
实现一个4*4二维数组的转置

2.2源程序

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

arrA = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

N = 4

arrB = [[None]*N for row in range(N)]

print("原设置的矩阵内容：")
for i in range(4):
    for j in range(4):
        print("%d" %arrA[i][j],end="\t")
    print()

for i in range(4):
    for j in range(4):
        arrB[i][j] = arrA[j][i]

print("转置矩阵内容：")
for i in range(4):
    for j in range(4):
        print("%d" % arrB[i][j], end="\t")
    print()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2.3运行结果

原设置的矩阵内容：
1        2        3        4       
5        6        7        8       
9        10        11        12       
13        14        15        16       
转置矩阵内容：
1        5        9        13       
2        6        10        14       
3        7        11        15       
4        8        12        16       
1
2
3
4
5
6
7
8
9
10
0x02 建立单向链表
在python中，如果以动态分配产生链表节点的节点，可以先行定义一个类，接着在该类中定义一个指针字段，作用是指向下一个链表节点，另外该类中至少要有一个数据字段。例如，我们声明一个学生成绩链表节点的结构声明，并且包含姓名(name)，成绩(score)两个数据字段与一个指针字段(next)。在python语言中可以声明如下：

class student:
  def __init__(self):
    self.name=""
    self.score=0
    self.next=None
1
2
3
4
5
完成节点类的声明后，就可以动态建立链表中的每个节点。假设现在要新增一个节点至链表的末尾，且ptr指向链表的第一个节点，在程序上必须设计4个步骤：

动态分配内存空间给新节点使用
将原链表尾部的指针(next)指向新元素所在的内存位置
将ptr指针指向新的节点的内存位置，表示这是新的链表尾部
由于新节点当前为链表的最后一个元素，因此将它的指针(next)指向None
例如：将s1的next变量指向s2，而且s2的next变量指向None

s1.next=s2
s2.next=None
1
2
python程序片段是建立学生节点的单向链表的算法：

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

head = student()
head.next = None
ptr = head
select = 0

while select!=2:
    print("(1)添加 (2)离开=>")
    try:
        select = int(input("请输入一个选项："))
    except ValueError:
        print("输入错误")
        print("请重新输入\n")
    if select==1:
        new_data = student()
        new_data.name = input("姓名：")
        new_data.no=input("学号：")
        new_data.Math=eval(input("数学成绩："))
        ptr.next = new_data
        new_data.next = None
        ptr = ptr.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
一.单向链表的连接
对于两个或两个以上的连接(concatenation，也称为级联)，其实现方法很容易：只要将链表的首尾相连即可


1.功能要求
将两组学生成绩的链表连接起来，并输出新的学生成绩链表

2.源程序
import sys
import random

def concatlist(ptr1,ptr2):
    ptr=ptr1
    while ptr.next!=None:
        ptr=ptr.next
    ptr.next=ptr2
    return ptr1

class employee:
    def __init__(self):
        self.num=0
        self.salary=0
        self.name=''
        self.next=None

findword=0
data=[[None]*2 for row in range(12)]

namedata1=['Allen','Scott','Marry','Jon','Mark','Ricky','Lisa','Jasica', 'Hanson','Amy','Bob','Jack']

namedata2=['May','John','Michael','Andy','Tom','Jane','Yoko','Axel','Alex','Judy','Kelly','Lucy']

for i in range(12):
    data[i][0]=i+1
    data[i][1]=random.randint(51,100)

head1=employee()   #建立第一组链表的头部
if not head1:
    print('Error!! 内存分配失败!!')
    sys.exit(0)
       
head1.num=data[0][0]
head1.name=namedata1[0]
head1.salary=data[0][1]
head1.next=None
ptr=head1
for i in range(1,12):  #建立第一组链表
    newnode=employee()
    newnode.num=data[i][0]
    newnode.name=namedata1[i]
    newnode.salary=data[i][1]
    newnode.next=None
    ptr.next=newnode
    ptr=ptr.next
           
for i in range(12):
    data[i][0]=i+13
    data[i][1]=random.randint(51,100)

head2=employee()   #建立第二组链表的头部
if not head2:
    print('Error!! 内存分配失败!!')
    sys.exit(0)  
       
head2.num=data[0][0]
head2.name=namedata2[0]
head2.salary=data[0][1]
head2.next=None
ptr=head2
for i in range(1,12):  #建立第二组链表
    newnode=employee()
    newnode.num=data[i][0]
    newnode.name=namedata2[i]
    newnode.salary=data[i][1]
    newnode.next=None
    ptr.next=newnode
    ptr=ptr.next
       
i=0
ptr=concatlist(head1,head2) #将链表相连
print('两个链表相连的结果为：')
while ptr!=None: #打印链表的数据
    print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary),end='')
    i=i+1
    if i>=3:
        print()
        i=0
    ptr=ptr.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
3.运行结果
两个链表相连的结果为：
[ 1  Allen  58] => [ 2  Scott  65] => [ 3  Marry  65] =>
[ 4    Jon  75] => [ 5   Mark  60] => [ 6  Ricky  82] =>
[ 7   Lisa  56] => [ 8 Jasica  98] => [ 9 Hanson  54] =>
[10    Amy  65] => [11    Bob  60] => [12   Jack  51] =>
[13    May  98] => [14   John  80] => [15 Michael  95] =>
[16   Andy  93] => [17    Tom  72] => [18   Jane  85] =>
[19   Yoko  68] => [20   Axel  53] => [21   Alex  73] =>
[22   Judy  63] => [23  Kelly  94] => [24   Lucy  64] =>
1
2
3
4
5
6
7
8
9
二.单向链表的节点删除
在单向链表类型的数据结构中，若要在链表中删除一个节点，如同一列火车中拿掉原来的车厢，根据所删除节点的位置会有以下三种不同的情况：
(1)删除链表的第一个节点
只要把链表头指针指向第二个节点即可

python算法如下：

top=head
head=head.next

(2)删除链表的最后一个节点
只要指向最后一个节点ptr的指针直接指向None即可

python算法如下：

ptr.next=tail
ptr.next=None

(3)删除链表内的中间节点
只要将删除节点的前一个节点的指针指向将要被删除节点的下一个节点即可


python算法如下：

Y=ptr.next
ptr.next=Y.next

1.功能要求
在员工数据的链表中删除节点，并且允许所删除的节点有在链表头部，链表尾部和链表中间三种不同位置的情况。最后离开时，列出此链表的最后所有节点的数据字段的内容。结构成员类型如下：

class employee:
  def __init__(self):
    self.num=0
    self.salary=0
    self.name=""
    self.next=None

2.源程序
import sys
class employee:
    def __init__(self):
        self.num=0
        self.salary=0
        self.name=''
        self.next=None

def del_ptr(head,ptr):  #删除节点子程序
    top=head
    if ptr.num==head.num:  #[情形1]:要删除的节点在链表头部
        head=head.num
        print('已删除第 %d 号员工 姓名：%s 薪资:%d' %(ptr.num,ptr.name,ptr.salary))
    else:
        while top.next!=ptr:  #找到删除节点的前一个位置
            top=top.next
        if ptr.next==None:   #删除在链表末尾的节点
            top.next=None
            print('已删除第 %d 号员工 姓名：%s 薪资:%d' %(ptr.num,ptr.name,ptr.salary))
        else:
            top.next=ptr.next #删除在串行中的任一节点
            print('已删除第 %d 号员工 姓名：%s 薪资:%d' %(ptr.num,ptr.name,ptr.salary))
    return head  #返回链表

def main():
    findword=0
    namedata=['Allen','Scott','Marry','John','Mark','Ricky','Lisa','Jasica','Hanson','Amy','Bob','Jack']
    data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299], [1012,42660],[1014,25676],[1018,44145],[1043,52182], [1031,32769],[1037,21100],[1041,32196],[1046,25776]]
    print('员工编号 薪水 员工编号 薪水 员工编号 薪水 员工编号 薪水')
    print('-------------------------------------------------------')
    for i in range(3):
        for j in range(4):
            print('%2d  [%3d]  ' %(data[j*3+i][0],data[j*3+i][1]),end='')
        print()
    head=employee() #建立链表头部
    if not head:
        print('Error!! 内存分配失败!!')
        sys.exit(0)
    head.num=data[0][0]
    head.name=namedata[0]
    head.salary=data[0][1]
    head.next=None
       
    ptr=head
    for i in range(1,12):  #建立链表
        newnode=employee()
        newnode.num=data[i][0]
        newnode.name=namedata[i]
        newnode.salary=data[i][1]
        newnode.num=data[i][0]
        newnode.next=None
        ptr.next=newnode
        ptr=ptr.next
                       
    while(True):
        findword=int(input('请输入要删除的员工编号,要结束删除过程,请输入-1：'))
        if(findword==-1): #循环中断条件
            break
        else:
            ptr=head
            find=0
            while ptr!=None:
                if ptr.num==findword:
                    ptr=del_ptr(head,ptr)
                    find=find+1
                    head=ptr
                ptr=ptr.next
            if find==0:
                print('######没有找到######')
                       
    ptr=head
    print('\t员工编号    姓名\t薪水')   #打印剩余链表中的数据
    print('\t==============================')
    while(ptr!=None):
        print('\t[%2d]\t[ %-10s]\t[%3d]' %(ptr.num,ptr.name,ptr.salary))
        ptr=ptr.next
main()

3.运行结果
员工编号 薪水 员工编号 薪水 员工编号 薪水 员工编号 薪水
-------------------------------------------------------
1001  [32367]  1007  [31299]  1018  [44145]  1037  [21100]  
1002  [24388]  1012  [42660]  1043  [52182]  1041  [32196]  
1003  [27556]  1014  [25676]  1031  [32769]  1046  [25776]  
请输入要删除的员工编号,要结束删除过程,请输入-1：1046
已删除第 1046 号员工 姓名：Jack 薪资:25776
请输入要删除的员工编号,要结束删除过程,请输入-1：1012
已删除第 1012 号员工 姓名：Mark 薪资:42660
请输入要删除的员工编号,要结束删除过程,请输入-1：-1
        员工编号    姓名        薪水
        ==============================
        [1001]        [ Allen     ]        [32367]
        [1002]        [ Scott     ]        [24388]
        [1003]        [ Marry     ]        [27556]
        [1007]        [ John      ]        [31299]
        [1014]        [ Ricky     ]        [25676]
        [1018]        [ Lisa      ]        [44145]
        [1043]        [ Jasica    ]        [52182]
        [1031]        [ Hanson    ]        [32769]
        [1037]        [ Amy       ]        [21100]
        [1041]        [ Bob       ]        [32196]

三.单链表的反转
如果要将单向链表反转，则必须使用三个指针变量

python算法如下：

class employee:
  def __init__(self):
    self.num=0
    self.salary=0
    self.name=""
    self.next=None

def invert(x):          # x为链表的头指针
  p=x                   # 将p指向链表的开头
  q=None                # q是p的前一个节点
  while p!=None:
    r=q           # 将r接到q之后
    q=p           # 将q接到p之后
    p=p.next      # p移到下一个节点
    q.next=r      # q连接到之前的节点
   return q
1

在算法invert(X)中，我们使用了p,q,r三个指针变量，它的演变过程如下：
第一步：执行while循环前


第二步：执行whilex


第三步：第二次执行while循环


当执行到p=None时，整个单向链表就整个反转过来了

1.源程序
#include <stdio.h>
#include <stdlib.h>
class employee:
    def __init__(self):
        self.num=0
        self.salary=0
        self.name=''
        self.next=None

findword=0

namedata=['Allen','Scott','Marry','Jon', \
          'Mark','Ricky','Lisa','Jasica', \
          'Hanson','Amy','Bob','Jack']

data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299], \
      [1012,42660],[1014,25676],[1018,44145],[1043,52182], \
      [1031,32769],[1037,21100],[1041,32196],[1046,25776]]

head=employee() #建立链表头部
if not head:
    print('Error!! 内存分配失败!!')
    sys.exit(0)

head.num=data[0][0]
head.name=namedata[0]
head.salary=data[0][1]
head.next=None
ptr=head
for i in range(1,12): #建立链表
    newnode=employee()
    newnode.num=data[i][0]
    newnode.name=namedata[i]
    newnode.salary=data[i][1]
    newnode.next=None
    ptr.next=newnode
    ptr=ptr.next

ptr=head
i=0
print('反转前的员工链表节点数据：')
while ptr !=None:  #打印链表数据
    print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary), end='')
    i=i+1
    if i>=3: #三个元素为一行
        print()
        i=0
    ptr=ptr.next

ptr=head
before=None   
print('\n反转后的链表节点数据：')
while ptr!=None: #链表反转,利用三个指针
    last=before
    before=ptr
    ptr=ptr.next
    before.next=last

ptr=before
while ptr!=None:
    print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary), end='')
    i=i+1
    if i>=3:
        print()
        i=0
    ptr=ptr.next

2.运行结果
反转前的员工链表节点数据：
[1001  Allen 32367] => [1002  Scott 24388] => [1003  Marry 27556] =>
[1007    Jon 31299] => [1012   Mark 42660] => [1014  Ricky 25676] =>
[1018   Lisa 44145] => [1043 Jasica 52182] => [1031 Hanson 32769] =>
[1037    Amy 21100] => [1041    Bob 32196] => [1046   Jack 25776] =>

反转后的链表节点数据：
[1046   Jack 25776] => [1041    Bob 32196] => [1037    Amy 21100] =>
[1031 Hanson 32769] => [1043 Jasica 52182] => [1018   Lisa 44145] =>
[1014  Ricky 25676] => [1012   Mark 42660] => [1007    Jon 31299] =>
[1003  Marry 27556] => [1002  Scott 24388] => [1001  Allen 32367] =>
---------------------

---

作者: 不二晨    时间: 2019-2-26 15:35
奈斯，感谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2