扫码获取更多资源

●初始化操作

(1)生成一个新结点作为头结点。 (2)设置头结点的指针域为空。

算法描述

●销毁操作

从单链表的头结点开始依次释放表中每一个结点所占用的存储空间。

(1)问题规模：线性表的“当前长度”，即单链表的结点个数(设值为n)。

(2)基本操作：指针后移、释放结点存储空间。

(3)时间分析：算法执行时间主要花费在while循环的基本操作上，执行次数为n+1, 因此算法2-15的时间复杂度为O(n)。

●清空操作

(1)从单链表的第一个结点开始依次释放表中每个结点所占用的存储空间。

(2)令头结点指针域为空。

单链表的逻辑状态表示

算法描述

(1)问题规模：线性表的“当前长度”，即单链表的结点个数(设值为n)。

(2)基本操作：指针后移、释放结点存储空间。

(3)时间分析：算法执行时间主要花费在while循环的基本操作上，执行次数为n,因 此算法2-16的时间复杂度为O(n)。

●求表长操作

在顺序表中，线性表的长度是它的一个属性，很容易求得。但在单链表中，整个链表由 一个“头指针”表示，线性表长度即为链表中的结点个数， 只能通过指针顺链表向后扫描，依 次“访问”结点，计数得到。

(1)设置一个指针，初始时指向单链表的头结点。 (2)设置一个计数器，初始时为0。 (3)通过指针顺链表向后扫描：如果指针不空，则令计数器加1,且令指针指向其后继 结点，如此循环直至指针为“空”停止。

联系我们：