软件工程-基础课程-计算机科学导论_数据结构：数组、链表、栈、队列、树、图.docxVIP

PAGE1

PAGE1

数据结构基础概念

数据结构是计算机科学中一个核心的概念，它涉及到数据的组织、管理和存储格式。数据结构的选择直接影响到算法的效率，以及软件的性能和可维护性。在本节中，我们将深入探讨几种基本的数据结构，包括数组、链表、栈、队列、树和图，理解它们的特性和应用场景。

1数组

数组是一种线性数据结构，它将元素存储在连续的内存位置中。数组中的每个元素可以通过其索引（通常是整数）直接访问，这使得数组在查找操作上非常高效。

1.1代码示例

#Python示例代码

#创建一个整数数组

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

#访问数组中的元素

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

#修改数组中的元素

arr[0]=100

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

#遍历数组

foriinrange(len(arr)):

print(arr[i])

#或者使用更Pythonic的方式遍历

forelementinarr:

print(element)

2链表

链表是一种线性数据结构，但与数组不同，它不使用连续的内存位置。每个元素（称为节点）包含数据和指向下一个节点的指针。链表在插入和删除操作上比数组更高效，因为不需要移动大量元素。

2.1代码示例

#Python示例代码

classNode:

def__init__(self,data=None):

self.data=data

self.next=None

classLinkedList:

def__init__(self):

self.head=None

defappend(self,data):

ifnotself.head:

self.head=Node(data)

else:

current=self.head

whilecurrent.next:

current=current.next

current.next=Node(data)

defdisplay(self):

elements=[]

current_node=self.head

whilecurrent_node:

elements.append(current_node.data)

current_node=current_node.next

print(elements)

#创建链表并添加元素

linked_list=LinkedList()

linked_list.append(1)

linked_list.append(2)

linked_list.append(3)

linked_list.display()#输出:[1,2,3]

3栈

栈是一种特殊的线性数据结构，遵循后进先出（LIFO）原则。元素只能在栈的顶部进行添加（压栈）和删除（弹栈）操作。

3.1代码示例

#Python示例代码

classStack:

def__init__(self):

self.items=[]

defpush(self,item):

self.items.append(item)

defpop(self):

ifnotself.is_empty():

returnself.items.pop()

defis_empty(self):

returnlen(self.items)==0

defpeek(self):

ifnotself.is_empty():

returnself.items[-1]

defsize(self):

returnlen(self.items)

#创建栈并进行操作

stack=Stack()

stack.push(1)

stack.push(2)

stack.push(3)

print(stack.pop())#输出:3

print(stack.peek(