软件工程-基础课程-数据结构_数据结构在实际问题中的应用.docxVIP

PAGE1

PAGE1

数据结构基础

1数组与链表的基本概念

1.1数组

数组是一种基本的数据结构，它在内存中以连续的方式存储相同类型的元素。数组的每个元素可以通过其索引（位置）直接访问，这使得数组在查找操作上非常高效。数组的索引通常从0开始，直到数组长度减1。

1.1.1示例代码

#创建一个数组

arr=[10,20,30,40,50]

#访问数组中的元素

print(arr[0])#输出:10

#修改数组中的元素

arr[0]=100

print(arr)#输出:[100,20,30,40,50]

#添加元素到数组

arr.append(60)

print(arr)#输出:[100,20,30,40,50,60]

#删除数组中的元素

arr.remove(20)

print(arr)#输出:[100,30,40,50,60]

1.2链表

链表是一种线性数据结构，其中的元素不是在内存中连续存储的，而是通过指针链接在一起。每个元素（节点）包含数据和指向下一个节点的指针。链表在插入和删除操作上比数组更高效，因为不需要移动大量元素。

1.2.1示例代码

classNode:

链表节点类

def__init__(self,data):

self.data=data

self.next=None

classLinkedList:

链表类

def__init__(self):

self.head=None

defappend(self,data):

在链表末尾添加元素

new_node=Node(data)

ifnotself.head:

self.head=new_node

return

last_node=self.head

whilelast_node.next:

last_node=last_node.next

last_node.next=new_node

defprepend(self,data):

在链表头部添加元素

new_node=Node(data)

new_node.next=self.head

self.head=new_node

defdelete_node(self,key):

删除链表中具有特定值的节点

cur_node=self.head

ifcur_nodeandcur_node.data==key:

self.head=cur_node.next

cur_node=None

return

prev_node=None

whilecur_nodeandcur_node.data!=key:

prev_node=cur_node

cur_node=cur_node.next

ifcur_nodeisNone:

return

prev_node.next=cur_node.next

cur_node=None

#创建链表

llist=LinkedList()

llist.append(A)

llist.append(B)

llist.append(C)

llist.prepend(D)

#删除链表中的元素

llist.delete_node(B)

#链表现在是:D-A-C

2栈和队列的应用场景

2.1栈

栈是一种后进先出（LIFO）的数据结构，意味着最后添加的元素将首先被移除。栈在编程中有很多应用，如函数调用、表达式求值和括号匹配。

2.1.1示例代码

classStack:

栈类

def__init__(self):

self.stack=[]

defpush(self,item):

将元素添加到栈顶

self.stack.append(it