做网站最重要的是什么/深圳网络营销模式

python数据结构教程第一课

python的一些实用的数据结构，原理加上实例源码。

目录

一、顺序表的实现

二、链接表的实现

1.单链表

2.带尾指针的单链表

3.循环单链表

4.双链表

5.循环双链表

三、线性表的应用—Josephus问题

1.顺序表解法

2.循环单链表解法

在程序里经常需要将一组数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，一组数据中包含的元素个数可能发生变化，也可能会用元素在序列里的位置和顺序，表示实际应用中的某种有意义信息。线性表就是这样一组元素的抽象，其具体实现方式有两种，顺序表和链接表

一、线性表的抽象数据类型(ADT)

线性表的基本操作应当有创建空表、返回长度信息、插入、删除等操作，其基本的ADT如下：

ADT List：

List(self) #创建一个新表

is_empty(self) #判断self是否是一个空表 len(self) #返回表长度 prepend(self,elem) #在表头插入元素 append(self,elem) #在表尾加入元素 insert(self,elem,i) #在表的位置i处插入元素 del_first(self) #删除第一个元素 def_last(self) #删除最后一个元素 del(self,i) #删除第I个元素 search(self,elem) #查找元素在表中第一次出现的位置 forall(self,op) #对表元素的遍历操作，op操作

二、顺序表的实现

python内部的tuple与list采用的就是顺序表结构，其不同点在于tuple是固定结构，一旦创建就无法进行改动，而list则支持变动操作，具有上述ADT所描述的全部操作，这里不再具体重写类代码，其主要使用命令如下

list1 = list([1,2,3,4,5]) #创建新表 list1.append(6) #在尾部添加新元素 6 k = len(list1) #返回表长度 list1.insert(k,7) #在位置k插入7 list1.pop() #返回并删除尾部元素 print(list1) #输出表的全部元素 list2 = list1[2:] #表的切片操作

顺序表的优势：在于O(1)时间的定位元素访问，很多简单的操作效率也比较高，

比较麻烦的地方：在于表中间位置元素的插入删除操作，由于元素在顺序表的存储区里连续排列，插入／删除操作可能要移动很多元素，代价很高

三、链接表的实现

基于链接技术实现的线性表称为链接表或者链表，用链接关系显式表示元素之间的顺序关系，链接表结构的基本思想如下：

1.把表中的元素分别存储在一批独立的存储块(结点)里

2.保证从组成表结构中的任一个结点可找到与其相关的下一个结点

3.在前一结点里用链接的方式显式地记录与下一结点之间的关联

在python里链表的实现有诸多方式和变形，接下来将选取主要的结构进行源码讲解