选择任意一种链式结构实现线性表,并完成线性表的基本功能
时间: 2023-05-21 17:07:28 浏览: 57
可以使用单链表实现线性表,基本功能包括插入、删除、查找、遍历等操作。以下是单链表的基本实现代码:
```
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = ListNode(None)
self.size = 0
def is_empty(self):
return self.size == 0
def get_size(self):
return self.size
def add_first(self, val):
new_node = ListNode(val)
new_node.next = self.head.next
self.head.next = new_node
self.size += 1
def add_last(self, val):
new_node = ListNode(val)
cur = self.head
while cur.next:
cur = cur.next
cur.next = new_node
self.size += 1
def add(self, index, val):
if index < 0 or index > self.size:
raise IndexError('Index out of range')
new_node = ListNode(val)
cur = self.head
for i in range(index):
cur = cur.next
new_node.next = cur.next
cur.next = new_node
self.size += 1
def remove_first(self):
if self.is_empty():
raise Exception('Linked list is empty')
self.head.next = self.head.next.next
self.size -= 1
def remove_last(self):
if self.is_empty():
raise Exception('Linked list is empty')
cur = self.head
while cur.next.next:
cur = cur.next
cur.next = None
self.size -= 1
def remove(self, index):
if self.is_empty():
raise Exception('Linked list is empty')
if index < 0 or index >= self.size:
raise IndexError('Index out of range')
cur = self.head
for i in range(index):
cur = cur.next
cur.next = cur.next.next
self.size -= 1
def get(self, index):
if self.is_empty():
raise Exception('Linked list is empty')
if index < 0 or index >= self.size:
raise IndexError('Index out of range')
cur = self.head.next
for i in range(index):
cur = cur.next
return cur.val
def set(self, index, val):
if self.is_empty():
raise Exception('Linked list is empty')
if index < 0 or index >= self.size:
raise IndexError('Index out of range')
cur = self.head.next
for i in range(index):
cur = cur.next
cur.val = val
def __str__(self):
cur = self.head.next
res = ''
while cur:
res += str(cur.val) + '->'
cur = cur.next
return res[:-2]
```
可以使用上述代码来操作单链表线性表,例如:
```
ll = LinkedList()
ll.add_first(3)
ll.add_last(5)
ll.add(1, 4)
print(ll.get_size()) # 3
print(ll.get(1)) # 4
ll.set(1, 6)
print(ll) # 3->6->5
ll.remove_first()
ll.remove_last()
ll.remove(0)
print(ll) # ''
```