算法 - 连续列表和链式列表

为什么要列出？

列表在日常生活中经常出现，例如：
  • 候诊室里的个人.
  • 专业注册的学生.
  • 汽车正在等待红灯.
  • etc.
目标是表示这些现实生活中的例子，并在计算机科学中处理它们.

列表的特征是什么？

  • 它们按顺序处理。
  • 两端分界<头>和<队列>。
  • 可以添加或删除元素.
  • 动态结构（大小不一）.
表示

1 - 连续表示

我们已经看到，我们可以用数组 T[1..max] 来表示一个列表，但它的结构是静态的（它的大小在我们定义声明中时是固定的）.



列表类型：Article
         {
           T： element
            长度：0..lmax
         }

最重要的操作


      优点

      • 直接访问.
      • 删除并插入列表末尾.
      • 易于实现.

      缺点

      • 你必须知道如何更改长度.
      • 删除和插入涉及偏移量.

      2- 代表 链式 

      它由一系列链接（块）组成，每个链接由两个字段组成：
      • An element field.
      • 指向以下内容的地址字段。

      L：指向第一个链接的指针。
      空的链表由 L=null.

      ptr 类型：link pointer
      链接类型：article
                 {
                    山谷;element
                    链接： ptr
                  }
      chainlisted< type： link/span>
      var L：chainlisted

      最重要的操作

      • The course.
        • 过程路径（L：list）
          顶部
            pp ：= L.link // 头部 de L
            只要 pp ！= null
            faire
              treat（L.T[i]）
              pp ：= *pp.link
            finfaire
           Fin


        优点

        • Sequential path.
        • 删除了链接.
        • 插入链接.

        缺点

        • 间接访问一个元素，你必须通过i-1链接才能到达 ith maillon.
        • links.