软件工程-基础课程-数据结构_线性数据结构：数组与链表.docxVIP

PAGE1

PAGE1

线性数据结构概览

1数组与链表的基本概念

1.1数组

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

1.1.1代码示例：数组的创建与访问

#创建一个整型数组

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

#访问数组中的元素

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

print(arr[3])#输出：40

#修改数组中的元素

arr[2]=35

print(arr)#输出：[10,20,35,40,50]

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

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()#输出：123

2线性数据结构的特性与应用

2.1数组的特性

固定大小：数组在创建时需要指定大小，一旦创建，大小不可改变。

随机访问：数组支持通过索引直接访问元素，时间复杂度为O(1)。

连续存储：数组中的元素在内存中连续存储，这有助于提高缓存性能。

2.2链表的特性

动态大小：链表的大小可以根据需要动态改变，插入和删除操作灵活。

顺序访问：链表中的元素需要通过指针顺序访问，查找特定元素的时间复杂度为O(n)。

非连续存储：链表中的元素在内存中不一定连续存储，这使得内存管理更加灵活。

2.3应用场景

数组：适用于需要快速查找元素的场景，如缓存、数据库索引等。

链表：适用于需要频繁插入和删除元素的场景，如实现队列、栈等数据结构。

2.4实例分析：数组与链表在不同场景下的应用

2.4.1数组实例：实现一个简单的缓存

classSimpleCache:

使用数组实现的简单缓存

def__init__(self,capacity):

self.capacity=capacity

self.cache=[None]*capacity

self.size=0

defget(self,index):

获取缓存中的元素

ifindex0orindex=self.capacity:

returnNone

returnself.cache[index]

defput(self,index,value):

在缓存中添加元素

ifindex0orindex=self.capacity:

return

ifself.cache[index]