数据结构第二讲:线性结构

在线课程 MOOC浙江大学数据结构课程

2.1 线性表及其实现

多项式表示

问题: 如何表示一个多项式?

方法:

  • 顺序存储结构直接表示

  • 顺序存储结构表示非零项

  • 链表结构存储非零项

两个多项式相加过程:

  • 对于顺序存储直接表示,对应位相加即可
  • 对于只存储非零项的情况,需要依次比较大小,寻找同指数项系数相加

链式存储和顺序存储的区别

顺序存储要求物理相邻

  • 求表长,$O(1)$
  • 查找值, 遍历比对,时间复杂度$O(n)$
  • 在指定位置插入值,先移动后面的值再插入,时间复杂度$O(n)$
  • 删除指定位置的值,查找到后先删除再前移,时间复杂度$O(n)$

    链式存储通过建立链来确定逻辑关系,不要求逻辑相邻

  • 求表长,遍历i计数,时间复杂度$O(n)$

  • 查找,遍历比对,时间复杂度$O(n)$
  • 插入,先找到位置再插入,$O(n)$
  • 删除,先找到位置再删除,$O(n)$

广义表

对于线性表而言,每个元素都是基本的单元素。在广义表中,这些元素不仅可以是单元素还可以是另一个广义表。

2.2 堆栈

顺序存储实现堆栈

头部和尾部只是个概念,数组的两端完全可以做栈底。

单向链表实现堆栈

栈顶指针Top只能在链表头。因为如果在链表尾,一旦执行删除操作,单向链表没有办法找到该结点前一个位置。

中缀表达式转成后缀表达式

2.3 队列的实现

什么是队列