Python中顺序表原理与实现方法详解

作者:xlengji 时间:2023-03-24 22:57:48 

本文实例讲述了Python中顺序表原理与实现方法。分享给大家供大家参考,具体如下:

Python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术,具有顺序表的所有性质。

tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似。

list的基本实现技术

Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的顺序(即保序),而且还具有以下行为特征:

  • 基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1);

    为满足该特征,应该采用顺序表技术,表中元素保存在一块连续的存储区中。

  • 允许任意加入元素,而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变。

    为满足该特征,就必须能更换元素存储区,并且为保证更换存储区时list对象的标识id不变,只能采用分离式实现技术。

在Python的官方实现中,list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) (或 list.insert(len(list), x),即尾部插入)比在指定位置插入元素效率高的原因。

《数据结构与算法 Python语言描述》 裘宗燕 著

在Python的官方实现中,list实现采用了如下的策略:在建立空表(或者很小的表)时,系统分配一块能容纳8个元素的存储区;在执行插入操作(insert或append)时,如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方式,是为了避免出现过多空闲的存储位置。

在Python的官方实现中,list实现采用了如下的策略:


 /* This over-allocates proportional to the list size, making room
  * for additional growth. The over-allocation is mild, but is
  * enough to give linear-time amortized behavior over a long
  * sequence of appends() in the presence of a poorly-performing
  * system realloc().
  * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
  */
 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
 /* check for integer overflow */
 if (new_allocated > PY_SIZE_MAX - newsize) {
   PyErr_NoMemory();
   return -1;
 } else {
   new_allocated += newsize;
 }

python顺序表增删查实现


class shunxubiao:
 def __init__(self,length):#length表示顺序表的长度,决定此顺序表最多存储多少元素
   self.length=length
   self.data=[] #data表示顺序表内容
   self.biao=-1 #元素下标
 def weikong(self):#判断 这个顺序表是否是空的
   if self.biao==-1:
     return True
   else:
     return False
 def mande(self):#判断此顺序表是否是满的
   if self.biao+1==self.length:
     return True
   else:
     return False
 def qingkong(self):
   if not self.weikong():
     self.data=[]
     self.biao=-1
 def geshu(self):
   return self.biao+1
 def chazhao(self,x):#知道下标查找元素
   return self.data[x]
 def chazhao1(self,x):#知道元素查找下标
   if self.weikong():
     print('表为空')
     return -1
   for i in range(self.biao+1):
     if self.data[i]==x:
      return i
      break
      print('查找的元素不存在')
 def biaoweijia(self,x): #给顺序表表尾加一个元素
   if self.mande():
     print('biaoyiman')
   else:
    self.data.append(x)
   self.biao+=1
 def charu(self,index,x):#想顺序表的index位置插入x元素
   if self.mande():
     print('biayiman')
   elif index<0 or index>self.biao-1:
     print('bunengcharu')
   else:
     for i in range(self.biao,index-1):
       self.data[i+1]=self.data[i]
       self.data[index-1]=x
     self.biao+=1
 def shanchu(self,x):#删除指定元素x
   if self.weikong():#判断是不是空表
     print('kongde,bunengshanchu')
   index=-1#用index来找x的位置
   for i in (self.data):
     index+=1
     if i == x:
       break
   for i in range(index,self.biao-1):#把x元素之后的元素都向前推进一格
     self.data[i]=self.data[i+1]
   self.biao-=1
c=shunxubiao(6)
c.data=[2,4,5,6]
c.biao=3
c.weikong()
print(c.chazhao(2))#知道尾标2查找元素
print(c.chazhao1(4))#知道元素查找尾标
c.biaoweijia(7)#给表尾加元素
print(c.data)
print(c.biao)
c.charu(3,9)
print(c.data)
print(c.biao)
c.shanchu(7)
print(c.data)
print(c.biao)

输出结果:

[2, 4, 5, 6, 7] 4 [2, 4, 5, 6, 7] 5 [2, 4, 5, 6, 7] 4

思考:为什么没有把9添加进去,也没有把7删除掉

希望本文所述对大家Python程序设计有所帮助。

来源:https://blog.csdn.net/xlengji/article/details/82142944

标签:Python,顺序表
0
投稿

猜你喜欢

  • 一个jquery日期选取插件源码

    2009-12-23 19:15:00
  • python groupby函数实现分组后选取最值

    2022-06-02 09:27:45
  • Pycharm配置远程调试的方法步骤

    2021-03-13 00:45:38
  • SQL Server修改标识列方法 如自增列的批量化修改

    2024-01-19 04:59:22
  • vue中为何方法要写在methods的里面

    2024-05-10 14:19:24
  • 关于PowerDesigner初体验的使用介绍

    2024-01-13 04:15:25
  • Python日志模块logging简介

    2022-07-14 23:55:22
  • MyBatis批量插入/修改/删除MySql数据

    2024-01-18 05:55:11
  • python中Lambda表达式详解

    2021-12-06 22:40:26
  • 使用python实现个性化词云的方法

    2021-08-27 03:46:59
  • SQL判断字段列是否存在的方法

    2024-01-22 16:30:26
  • Python使用Srapy框架爬虫模拟登陆并抓取知乎内容

    2022-02-02 11:08:01
  • Python 实现数据结构-堆栈和队列的操作方法

    2021-05-25 20:56:16
  • 用python实现名片管理系统

    2022-03-27 09:34:33
  • python基础教程之while循环

    2021-02-05 03:02:17
  • 解决mysql5中文乱码问题的方法

    2024-01-15 07:47:52
  • python使用ctypes库调用DLL动态链接库

    2023-12-08 14:14:05
  • 深入分析Python中Lambda函数的用法

    2023-07-01 16:03:21
  • Python的文本常量与字符串模板之string库

    2022-04-11 05:13:25
  • Python实现批量识别银行卡号码以及自动写入Excel表格步骤详解

    2023-12-12 21:39:18
  • asp之家 网络编程 m.aspxhome.com