数据结构程序填空题.pdfVIP

一、题目描述：

数据结构：链表

操作：

1.初始化链表

2.在链表头部插入元素

3.在链表尾部插入元素

4.在指定位置插入元素

5.删除链表头部元素

6.删除链表尾部元素

7.删除指定位置元素

8.查找链表中指定元素的位置

9.获取链表长度

10.打印链表中的所有元素

二、解题思路：

1.初始化链表：创建一个头结点，并将头结点的指针域置为空。

2.在链表头部插入元素：创建一个新节点，将新节点的指针域指向头结点的下

一个节点，再将头结点的指针域指向新节点。

后一个节点的指针域指向新节点。

4.在指定位置插入元素：创建一个新节点，遍历链表找到指定位置的前一个节

点，将新节点的指针域指向前一个节点的下一个节点，再将前一个节点的指针域指

向新节点。

5.删除链表头部元素：将头结点的指针域指向头结点的下一个节点。

6.删除链表尾部元素：遍历链表找到倒数第二个节点，将倒数第二个节点的指

针域置为空。

7.删除指定位置元素：遍历链表找到指定位置的前一个节点，将前一个节点的

指针域指向指定位置的下一个节点。

8.查找链表中指定元素的位置：遍历链表，逐个比较节点的值与指定元素的值，

直到找到匹配的节点，返回其位置。

9.获取链表长度：遍历链表，计数器加一，直到遍历到链表尾部。

10.打印链表中的所有元素：遍历链表，逐个打印节点的值。

```python

classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next

classLinkedList:

def__init__(self):

definsert_at_head(self,val):

new_node=ListNode(val)

new_node.next=self.head.next

self.head.next=new_node

definsert_at_tail(self,val):

new_node=ListNode(val)

curr=self.head

whilecurr.next:

curr=curr.next

curr.next=new_node

definsert_at_position(self,val,position):

new_node=ListNode(val)

curr=self.head

for_inrange(position):

curr=curr.next

new_node.next=curr.next

curr.next=new_node

defdelete_at_head(self):

ifself.head.next:

self.head.next=self.head.next.next

curr=self.head

whilecurr.next.next:

curr=curr.next

curr.next=None

defdelete_at_position(self,position):

curr=self.head

for_inrange(position):

curr=curr.next

curr.next=curr.next.next

deffind_position(self,val):

curr=self.head.next

position=0

whilecurr:

ifcurr.val==val:

returnposition

curr=curr.next

position+=1

return-1

defget_length(se