Skip to main content

Python 入门基础知识 - 数据结构与算法 - 表

Python 入门基础知识 - 数据结构与算法 - 表

数据结构与算法

数据结构用来描述一种或多种数据元素之间的特定关系。算法是程序设计中对数据操作的描述。数据结果和算法组成

了程序。对于简单的任务,只要使用编程语言提供的基本数据类型就足够了。而对于较复杂的任务,就需要使用基本

的数据类型构造更加复杂的数据结构。

表、栈和队列

表、栈和队列都是基本的线性数据结构。由于Python设计良好的数据结构,其列表可以当做表来使用。而且列表的

某些特性跟链表相似,在Python中表的实现非常简单。对于栈和队列,则可以自己在脚本中构建。

表示最基本的数据结构,在Python中可以使用列表来创建表。而在C语言中,一般使用数组来创建表。由于使用数组

创建表,对表中元素进行插入和删除操作的开销较大。当插入一个元素时,要先将该元素后的所有元素,从最后一个

元素开始,依次向后移动一个位置。完成元素移动后,再将元素插入数组中。同样,要删除表中的元素时,首先删除

元素,然后将位于该元素之后的元素从前向后,依次向前移动一个位置。

如果一个表含有元素较多,而要进行插入或删除的位置又比较靠近表的前端,则移动元素的操作将耗费大量的时间。

为了减少插入和删除元素的线性开销,可以使用链表代替表。在C语言中,链表中不仅保存数据,还保存了指向下一个

元素的指针,如下图

Image

当进行插入操作时,要先将位于插入元素前的元素指针赋值给插入元素。完成赋值后再将插入元素的地址赋值给位于

其前的元素,如下图

Image

当进行删除元素时,只需要删除元素的指针赋值给其前边的元素即可。如下图

Image

使用链表,可以降低插入、删除元素的线性开销。由于链表中不仅存储了数据,而且还保存了指向下一个元素的指针,

因而使用链表将占用更大的存储空间。而在Python中,列表本身就提供了插入和删除操作。因此,在Python中列表

也可以充当链表使用,而不用自己构建。

还有一种链表,称之为双向链表,如下图

Image

双向链表中不仅保存了指向下一个元素地址的指针,而且还保存了指向其上一个元素地址的指针。相对于单向链表,

双向链表需要更大的存储空间,但使用双向列表可以完成倒序扫描连边表。

版权声明

版权声明

durban.zhang 创作并维护的 Walkerfree 博客采用 创作共用保留署名-非商业-禁止演绎4.0国际许可证。本文首发于 Walkerfree 博客(http://www.walkerfree.com/),版权所有,侵权必究。本文永久链接:http://www.walkerfree.com/article/101