软件工程-基础课程-数据结构_动态规划：基础概念与应用案例.docxVIP

PAGE1

PAGE1

数据结构基础概念

1数据结构的定义与分类

数据结构是计算机科学中一个重要的概念，它指的是数据的组织、管理、存储和检索方式。数据结构可以分为两大类：线性结构和非线性结构。

1.1线性结构

线性结构是最基本的数据结构类型，其中数据元素之间存在一对一的关系。常见的线性结构包括数组、链表、栈和队列。

1.1.1示例：数组

数组是一种线性数据结构，其中的元素在内存中是连续存储的，可以通过索引直接访问。

#创建一个数组

arr=[1,2,3,4,5]

#访问数组中的元素

print(arr[0])#输出：1

#修改数组中的元素

arr[0]=10

print(arr)#输出：[10,2,3,4,5]

1.1.2示例：链表

链表是一种线性数据结构，其中的元素通过指针链接在一起，每个元素包含数据和指向下一个元素的指针。

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

defprint_list(self):

打印链表

cur_node=self.head

whilecur_node:

print(cur_node.data)

cur_node=cur_node.next

#创建链表并添加元素

llist=LinkedList()

llist.append(A)

llist.append(B)

llist.append(C)

#打印链表

llist.print_list()#输出：ABC

1.2非线性结构

非线性结构中的数据元素之间存在一对多的关系。常见的非线性结构包括树和图。

1.2.1示例：二叉树

二叉树是一种非线性数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

classTreeNode:

二叉树节点

def__init__(self,val=0,left=None,right=None):

self.val=val

self.left=left

self.right=right

classBinaryTree:

二叉树

def__init__(self):

self.root=None

definsert(self,val):

插入节点

ifnotself.root:

self.root=TreeNode(val)

else:

self._insert(val,self.root)

def_insert(self,val,node):

递归插入节点

ifvalnode.val:

ifnode.leftisNone:

node.left=TreeNode(val)

else:

self._insert(val,node.left)

else:

ifnode.rightisNone:

node.right=TreeNode(val)

else:

self._insert