线性表

**线性表:**一个有限序列,每个表项是相继排列的,每两个相邻表项都有直接前驱和直接后继关系。

按存储方式分类

顺序表: 基于数组的存储表示,结点逻辑顺序和物理顺序一致。 单链表: 每个结点有data和link两个域。用link域(指针)表示结点间的逻辑关系,结点逻辑顺序和物理顺序不一定一样。

线性链表的其它变形

  • 循环链表:最后一个结点的link域指向开始结点。【单链表是指向NULL】
  • 双向链表:每个结点有前驱指针(左指针)和后继指针(右指针)两个link域。

重要相关概念

  • 附加头结点:在链表第一个结点前增加“附加头结点”,它的data域可以不存放数据,也可以存放特殊标致或者表长。这样使空表与非空表第一个结点插入数据可以不作为特殊情况处理。
最后更新: 4/30/2019, 12:18:56 AM