软件工程-基础课程-数据结构_算法设计与分析：递归与递推.docxVIP

PAGE1

PAGE1

数据结构基础

1数组与链表

1.1数组

数组是一种基本的数据结构，它在内存中以连续的方式存储相同类型的元素。数组的索引通常从0开始，通过索引可以直接访问数组中的元素，这使得数组的访问速度非常快。然而，数组的大小是固定的，一旦定义，就不能改变。

1.1.1示例：查找数组中的最大值

#定义一个数组

arr=[1,3,5,7,9,2,4,6,8,0]

#查找数组中的最大值

deffind_max(arr):

max_val=arr[0]

foriinarr:

ifimax_val:

max_val=i

returnmax_val

#执行函数

max_val=find_max(arr)

print(数组中的最大值是：,max_val)

1.2链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的大小可以动态改变，但访问链表中的元素需要从头节点开始，逐个节点遍历，因此访问速度较慢。

1.2.1示例：在链表中插入一个新节点

classNode:

def__init__(self,data=None):

self.data=data

self.next=None

classLinkedList:

def__init__(self):

self.head=None

definsert(self,data):

new_node=Node(data)

new_node.next=self.head

self.head=new_node

#创建链表

linked_list=LinkedList()

#插入数据

linked_list.insert(1)

linked_list.insert(2)

linked_list.insert(3)

#打印链表

current=linked_list.head

whilecurrent:

print(current.data)

current=current.next

2栈与队列

2.1栈

栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。栈常用于解决需要后进先出处理的问题，如函数调用、括号匹配等。

2.1.1示例：使用栈进行括号匹配

defis_matched(expr):

stack=[]

forcharinexpr:

ifcharin([{:

stack.append(char)

elifcharin)]}:

ifnotstack:

returnFalse

current_char=stack.pop()

ifcurrent_char==(:

ifchar!=):

returnFalse

ifcurrent_char=={:

ifchar!=}:

returnFalse

ifcurrent_char==[:

ifchar!=]:

returnFalse

ifstack:

returnFalse

returnTrue

expr=([{}])

ifis_matched(expr):

print(括号匹配)

else:

print(括号不匹配)

2.2队列

队列是一种先进先出（FIFO）的数据结构，只允许在队尾进行插入操作，在队头进行删除操作。队列常用于解决需要先进先出处理的问题，如任务调度、消息队列等。

2.2.1示例：使用队列进行任务调度

fromcollectionsimportdeque

classTaskQueue:

def__init__(self):

self.queue=deque()

defenqueue(self,task):