试题详情
简答题如何实现线性表的4种链式存储结构？
  • 数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。每个结点分为两部分：一部分用于存放数据元素的值，称为数据域；另一部分是指针，用于指向与该结点在逻辑上相连的其他结点，称为指针域。对于线性表，指针域用于指向该结点的前一个或后一个结点（即前驱结点或后继结点）。通过结点的指针域将n个结点按其逻辑结构连接在一起的数据存储结构，称为链式存储结构。
    单向链表：在线性链表中，用一个专门的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个逻辑结点，线性链表的最后一个结点的指针为空（用NULL或0表示），表示链表终止，这样的线性链表称为单向链表。下图是单向链表示意图。

    循环链表：将单向链表最后一个结点的指针指向头结点，这样整个链表就构成一个循环，这种链式存储结构称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL，而是指向头结点。只有头结点的循环链表称为空循环链表。下图是带头结点的非空循环链表和空循环链表示意图。

    双向链表：双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下图（a）所示。
    双向循环链表：如果将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的next指针与指向第一个结点，就构成了双向循环链表。下图（b）和（c）是双向链表和双向循环表的逻辑结构示意图。

  • 关注下方微信公众号，在线模考后查看

热门试题