.写一算法在单链表上实现线性表的ListLength(L)运算。
时间: 2024-09-30 15:13:23 浏览: 42
线性表 实验报告.docx
为了在单链表上实现计算线性表的长度(即链表中元素的数量),你可以使用迭代或递归的方式。这里提供一种简单的迭代方法:
**算法步骤:**
1. 初始化一个计数器 `length` 为 0。
2. 使用一个指向链表头节点的指针 `p` 或者 `head`。
3. 当 `p` 不为 NULL 时,表示链表非空,将 `length` 加 1,然后将 `p` 向前移动到下一个节点 `p = p->next`。
4. 重复步骤 3 直到 `p` 变为 NULL,这意味着已经检查了链表的所有节点。
5. 返回计数器 `length` 的值作为链表的长度。
**伪代码实现:**
```python
function ListLength(head):
length = 0
current = head
while current is not None:
length += 1
current = current.next
return length
```
**注意**:这个算法的时间复杂度是 O(n),其中 n 是链表的长度,因为它需要遍历整个链表一次。
阅读全文