数组与链表算法

1. 静态数据结构（ static data structure ）
   数组。
   连续分配的内存空间（ contiguous allocation ）。
   读取修改快，删除加入慢。
   在建立静态数据结构的初期就必须声明最大可能要占用的固定内存空间，因此容易造成内存的浪费。
2. 动态数据结构（ dynamic data structure ）
   链表（ linked list ）。
   不连续的内存空间。
   插入删除方便，查找麻烦，设计麻烦。
   内存分配是在程序执行时才进行的，不需要事先声明，充分节省内存。

• 矩阵相乘
  矩阵 A(M, N) , 矩阵 B(N, P) -> 矩阵 C(M, P)
  展开成一维数组进行操作
  赋值：

    for i in range(M):
        for j in range(N):
            A[ i * N + j ] = num

  相乘：

    for i in range(M):
        for j in range(P):
            temp = 0
            for k in range(N):
                temp = temp + int( A[ i * N + k ] ) * int( B[ k * P + j ] )
            C[ i * P + j ] = temp

• 转置矩阵
  矩阵 A(M, M)

    for i in range(M):
        for j in range(i):
            if i!= j:
                A[i][j], A[j][ i] = A[j][ i], A[i][ j]

• 建立单向链表
  • 动态分配产生链表节点 —— 定义一个类
    • 定义一个指针字段：指向下一个节点
    • 定义至少一个数据字段

      class student:
          def __init__(self):
              self.name = ""
              self.score = 0
              self.next = None

    建立学生节点的单向链表：

      class Student:
          def __init__(self):
              self.name = ""
              self.score = 0
              self.next = None
    
      head = Student()
      ptr = head  # 存取指针的位置
      for i in range(5):
          new_data = Student()
          new_data.name = "张三"
          new_data.score = 90
          # ptr ：指针，不破坏 head
          ptr.next = new_data
          ptr = ptr.next
    
      print('-->', ptr)
      for i in range(6):
          print('==>', head.next)
          head = head.next

  • 单向链表的连接功能
    级联 concatenation

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

  • 单向链表的节点删除
    1. 删除第一个节点
       python top = head head = head.next
    2. 删除最后一个节点
       python ptr.next = tail ptr.next = None
    3. 删除中间节点
       python Y = ptr.next ptr.next = Y.next

      def del_ptr(head, ptr):
          top = head
          if ptr.num == top.num:  # [ 1 ]
              head = head.next
          else:
              while top.next != ptr:  # 找到删除节点的前一个位置
                  top = top.next
              if ptr.next == None:  # [ 2 ]
                  top.next = None
              else:
                  top.next = ptr.next  # [ 3 ]
          return head

      ptr = head
      find = 0  # 未找到标记
      while ptr != None:
          if ptr.num == findword:  # findword 要查找的 num
              ptr = del_ptr(head, ptr)
              head = ptr
              find += 1
          ptr = ptr.next

  • 单向链表的反转
    无从知道上一个节点的位置，需要 3 个指针变量。

      class Employee:
          def __init__(self):
              self.num = 0
              self.next = None
    
      def invert(head):
          next = head
          cur = None
          while next != None:
              pre = cur
              cur = next
              next = next.next
              cur.next = pre
          return cur

    ---

    数组结构类型通常包含哪几个属性：起始地址、维数、索引上下限、元素个数、数组类型。

    class Node:
      def __init__(self):
          self.data = ""
          self.next = None
    
      def insert(T, X, Y):
          node = Node()
          node.data = Y
          if T == None:
              T = I
              # I.next = None
          else:
              node.next = X.next
              X.next = node

数组与链表算法

原文：https://www.cnblogs.com/catyuang/p/11760485.html