软件工程-基础课程-数据结构_算法复杂度分析：时间复杂度与空间复杂度.docxVIP

PAGE1

PAGE1

数据结构基础

1数据结构的定义与分类

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

1.1线性结构

线性结构中的数据元素之间存在一对一的关系，如数组、链表、栈和队列。

1.2非线性结构

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

2线性结构与非线性结构

2.1线性结构

线性结构是最基本的数据结构类型，其中每个元素都与一个前驱元素和一个后继元素相关联。例如，数组和链表是两种常见的线性结构。

2.1.1数组

数组是一种线性数据结构，它在内存中以连续的方式存储数据元素。数组的访问和修改操作通常具有O(1)的时间复杂度，因为可以通过索引直接访问元素。

#创建一个数组

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

#访问数组中的元素

print(arr[2])#输出3

#修改数组中的元素

arr[2]=10

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

2.1.2链表

链表是一种线性数据结构，其中的元素不是存储在连续的内存位置，而是通过指针链接在一起。链表的插入和删除操作通常比数组更高效，因为不需要移动大量元素。

classNode:

def__init__(self,data=None):

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

#创建一个链表

ll=LinkedList()

ll.append(1)

ll.append(2)

ll.append(3)

#打印链表

ll.print_list()#输出1,2,3

2.2非线性结构

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

2.2.1树

树是一种非线性数据结构，它由节点和边组成，其中每个节点可以有零个或多个子节点。树的常见类型包括二叉树、平衡二叉树、红黑树等。

classTreeNode:

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

self.val=val

self.left=left

self.right=right

#创建一个二叉树

root=TreeNode(1)

root.left=TreeNode(2)

root.right=TreeNode(3)

root.left.left=TreeNode(4)

root.left.right=TreeNode(5)

#遍历二叉树

definorder_traversal(root):

ifroot:

inorder_traversal(root.left)

print(root.val)

inorder_traversal(root.right)

inorder_traversal(root)#输出4,2,5,1,3

2.2.2图

图是一种非线性数据结构，它由节点（顶点）和边组成，其中边可以是无向的或有向的。图的常见类型包括无向图、有向图、加权图等。

classGraph:

def__init__(self):

self.adj_list={}

defadd_vertex(self,vertex):