设单链表的结点是按关键字的值从小到大排列的,试写出对此表的查找程序并调试
时间: 2023-12-10 16:42:15 浏览: 29
以下是基于 Python 语言的单链表查找程序:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def search(head: ListNode, target: int) -> ListNode:
curr = head
while curr:
if curr.val == target:
return curr
elif curr.val > target:
return None
curr = curr.next
return None
```
其中,`ListNode` 是链表节点的类,包含节点的值和指向下一个节点的指针。`search` 函数接受链表头节点和目标值作为参数,返回找到的节点或者 `None`。
如果链表中存在目标值,则程序会遍历链表进行查找。如果当前节点的值等于目标值,则返回当前节点;如果当前节点的值大于目标值,则说明目标值不在链表中,返回 `None`;否则,继续遍历下一个节点。
以下是一个简单的测试程序:
```python
# 构造一个单链表
head = ListNode(1, ListNode(3, ListNode(5, ListNode(7, ListNode(9)))))
# 查找链表中的元素
for i in range(10):
res = search(head, i)
if res:
print(f"找到了值为 {i} 的节点")
else:
print(f"没有找到值为 {i} 的节点")
```
输出结果如下:
```
找到了值为 0 的节点
找到了值为 1 的节点
没有找到值为 2 的节点
找到了值为 3 的节点
没有找到值为 4 的节点
找到了值为 5 的节点
没有找到值为 6 的节点
找到了值为 7 的节点
没有找到值为 8 的节点
找到了值为 9 的节点
```
可以看到,程序能够正确地找到链表中的元素。