Java教程

数据结构和算法(2)

本文主要是介绍数据结构和算法(2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、数组

1. 数组的概念

数组(array)是有限个相同类型的变量所组成的有序集合,数组中的每一个变量称为元素。

数组的存储形式如图:

 数组的两个特点:

  1. 数组中的每一个元素也都有着自己的下标,下标从0开始,一直到数组长度-1;
  2. 在内存中顺序存储 ,因此可以很好地实现逻辑上的顺序表

 

2. 数组的基本操作

(数据结构的操作无非是增、删、改、查)

a. 读取元素

对于数组来说,读取是最简单的操作。由于数组在内存中顺序存储,所以只要给出一个数组下标,就可以快速读取到对应的数组元素。

在Python中,数组对应的是列表(list),使用方括号的形式创建。

# 初始化列表
my_list = [3, 1, 2, 5, 4, 9, 7, 2]

现在拥有了名叫my_list的数组,如要读取下标为3的元素,写作my_list[3];要读取下标为5的元素,写作my_list[5]。需要注意的是,输入的下标必须在数组的长度范围之内,否则会出现数组越界的问题。像这种根据下标读取元素的方式叫做随机读取

# 读取元素
print(my_list[2])

 

b. 更新元素

要把数组中某一个元素的值替换为一个新值,也是非常简单的操作。直接利用数组下标,就可以把新值赋给该元素。

# 更新元素
my_list[3] = 10
print(my_list[3])

 

c. 插入元素

插入数组元素有3种操作:

  • 尾部插入
  • 中间插入
  • 超范围插入

尾部插入是直接把插入的元素放在数组尾部的空闲位置,等同于更新元素的操作。

中间插入需要首先把插入位置及后面的元素向后移动,腾出地方,再把要插入的元素放到对应的数组位置上。

 

 上面所描述的插入过程,Python中都有函数能快速实现:

# 尾部插入元素
my_list.append(6)
# 中间插入元素
my_list.insert(5, 11)  # insert中第一个是索引位置,第二个是要插入列表的对象
print(my_list)

为了更好地理解数组的工作方式,让我们来自己实现一段插入操作的代码:

class MyArray:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.size = 0
        
    def insert_v2(self, index, element):
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际元素范围!")
        # 从右向左循环,逐个元素向右挪一位
        for i in range(self.size-1, -1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
    
    def output(self):
        for i in range(self.size):
            print(self.array[i])


array = MyArray(4)
array.insert_v2(0, 10)
array.insert_v2(0, 11)
array.insert_v2(0, 15)
array.output()

代码中的成员变量size是数组中实际元素的数量。如果插入元素在数组尾部,传入的下标参数index等于size;如果插入元素在数组中间或头部,则index小于size。

如果传入的下标参数index大于size或小于0,则认为是非法输入,会直接抛出异常。

 

超范围插入就相当于数组的扩容。原数组在创建时长度就已经确定了,这时可以创建一个新的数组,长度是旧数组的2倍,再把旧数组的元素复制过去,这就完成了数组的扩容。

如此一来,我们的插入元素的方法也需要改写了,改写的代码如下:

class MyArray:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.size = 0
        
    def insert_v2(self, index, element):
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际元素范围!")
        # 如果实际元素达到数组容量上线,数组扩容
        if self.size >= len(self.array):
            self.resize()
        # 从右向左循环,逐个元素向右挪一位
        for i in range(self.size-1, -1, -1):
            self.array[i+1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1
        
    def resize(self):
        array_new = [None] * len(self.array) * 2
        # 从旧数组复制到新数组
        for i in range(self.size):
            array_new[i] = self.array[i]
        self.array = array_new
    
    def output(self):
        for i in range(self.size):
            print(self.array[i])


array = MyArray(4)
array.insert_v2(0, 10)
array.insert_v2(0, 11)
array.insert_v2(0, 12)
array.insert_v2(0, 13)
array.insert_v2(0, 14)
array.insert_v2(0, 15)
array.insert_v2(1, 16)
array.output()

 

d. 删除元素

数组的删除操作和插入操作的过程相反,如果删除的元素位于数组中间,其后的元素都需要向前挪动1位。

同样的,尝试一下自己实现删除元素的操作:

def remove(self, index):
    # 判断访问下标是否超出范围
    if index < 0 or index > self.size:
        raise Exception("超出数组实际元素范围!")
    # 从左到右,逐个元素向左挪一位
    for i in range(index, self.size):
        self.array[i] = self.array[i+1]
    self.size -= 1

 

 3. 数组的特点

数组拥有非常高效的随机访问能力,只要给出下标,就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找,就是利用了数组的这个优势。

至于数组的劣势,体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入、删除元素都会导致大量元素被迫移动,影响效率。

总的来说,数组所适合的是读操作多、写操作少的场景。

这篇关于数据结构和算法(2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!