什么是Python中的顺序表

1、顺序表介绍

顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以插入、删除时需要移动大量元素。顺序表可以分配一段连续的存储空间Maxsize,用elem记录基地址,用length记录实际的元素个数,即顺序表的长度

上图1表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元素)与存储单元大小(c)的乘积计算而得,即:Loc(element i) = Loc(e0) + c*i

所以,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。

如果元素的大小不统一,则须采用图2的元素外置的形式,将实际数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元素链接的存储位置,而后顺着链接找到实际存储的数据元素。注意,图2中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。

图2这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构。

2、顺序表的结构

一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需记录的信息,即有关表的整体情况的信息,这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

3、顺序表的两种基本实现方式

1为一体式结构,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了。

2为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。

4、元素存储区替换

一体式结构由于顺序表信息区与数据区连续存储在一起,所以若想更换数据区,则只能整体搬迁,即整个顺序表对象(指存储顺序表的结构信息的区域)改变了。分离式结构若想更换数据区,只需将表信息区中的数据区链接地址更新即可,而该顺序表对象不变。

5、元素存储区扩充

采用分离式结构的顺序表,若将数据区更换为存储空间更大的区域,则可以在不改变表对象的前提下对其数据存储区进行了扩充,所有使用这个表的地方都不必修改。只要程序的运行环境(计算机系统)还有空闲存储,这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表,因为其容量可以在使用中动态变化。

扩充的两种策略

每次扩充增加固定数目的存储位置,如每次扩充增加10个元素位置,这种策略可称为线性增长。

特点:节省空间,但是扩充操作频繁,操作次数多。

每次扩充容量加倍,如每次扩充增加一倍存储空间。

特点:减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐的方式。

6、顺序表的增删改查操作的Python代码实现

# 创建顺序表class Sequence_Table():
 # 初始化
 def __init__(self):
  self.date = [None]*100
  self.length = 0
 # 判断是否已经满了
 def isFull(self):
 if self.length>100:
 print("该顺序表已满,无法添加元素")
 return 1
 else:
 return 0
 # 按下表索引查找
 def selectByIndex(self,index):
 if index>=0 and index<=self.length-1:
 return self.date[index]
 else:
 print("你输入的下标不对,请重新输入\n")
 return 0
 # 按元素查下标
 def selectByNum(self,num):
  isContain = 0
  for i in range(0,self.length):
  if self.date[i] == num:
    isContain = 1
    print("你要查找的元素下标是%d\n"%i)
    if isContain == 0:
    print("没有找你你要的数据")
 # 追加数据
 def addNum(self,num):
 if self.isFull() == 0:
   self.date[self.length] = num
   self.length += 1
 # 打印顺序表
 def printAllNum(self):
 for i in range(self.length):
 print("a[%s]=%s"%(i,self.date[i]),end=" ")
 print("\n")
 # 按下标插入数据
 def insertNumByIndex(self,num,index):
 if index<0 or index>self.length:
 return 0
  self.length += 1
  for i in range(self.length-1,index,-1):
   temp = self.date[i]
   self.date[i] = self.date[i-1]
   self.date[i-1] = temp
  self.date[index] = num
  return 1 # 按下标删除数据
 def delectNumByIndex(self,index):
 if self.length <= 0:
 print("该顺序表内没有数据,不用删除")
  for i in range(index,self.length-1):
   temp = self.date[i]
   self.date[i] = self.date[i + 1]
   self.date[i + 1] = temp
  self.date[self.length-1] = 0
  self.length -= 1def main(): # 创建顺序表对象
 seq_t = Sequence_Table()
 # 插入三个元素
 seq_t.addNum(1)
 seq_t.addNum(2)
 seq_t.addNum(3)
 # 打印验证
 seq_t.printAllNum()
 # 按照索引查找
 num = seq_t.selectByIndex(2)
 print("你要查找的数据是%d\n" % num)
 # 按照索引插入数据
 seq_t.insertNumByIndex(4, 1)
 seq_t.printAllNum()
 # 按照数字查下标
 seq_t.selectByNum(4)
 #删除数据
 seq_t.delectNumByIndex(1)
 seq_t.printAllNum()
if __name__ == "__main__":
 main()

运行结果为:

a[0]=1 a[1]=2 a[2]=3
你要查找的数据是3
a[0]=1 a[1]=4 a[2]=2 a[3]=3
你要查找的元素下标是1
a[0]=1 a[1]=2 a[2]=3

7、顺序表的增删改查操作的C语言代码实现

#include<stdio.h>
// 1、定义顺序表的储存结构
typedef struct
{
 //用数组存储线性表中的元素
 int data[100];
 // 顺序表中的元素个数
 int length;
}Sequence_table,*p_Sequence_table;
// 2、顺序表的初始化,
void initSequenceTable(p_Sequence_table T)
{
 // 判断传过来的表是否为空,为空直接退出
 if (T == NULL)
 {
  return;
 }
 // 设置默认长度为0
 T->length = 0;
}
// 3、求顺序表的长度
int lengthOfSequenceTable(p_Sequence_table T)
{
 if (T==NULL)
 {
  return 0;
 }
 return T->length;
}
// 4、判断顺序表是否已满
int isFull(p_Sequence_table T)
{
 if (T->length>=100)
 {
  printf("该顺序表已经装满,无法再添加元素");
  return 1;
 }
 return 0;
}
// 5、按序号查找
int selectSequenceTableByIndex(p_Sequence_table T,int index)
{
 if (index>=0&&index<=T->length-1)
 {
  return T->data[index];
 }
 printf("你输入的序号不对,请重新输入\n");
 return 0;
}
// 6、按内容查找是否存在
void selectSequenceTableByNum(p_Sequence_table T,int num)
{
 int isContain = 0;
 for (int i=0; i<T->length; i++)
 {
  if (T->data[i] == num)
  {
   isContain = 1;
   printf("你要找的元素的下标是:%d\n",i);
  }
 }
 if (isContain == 0)
 {
  printf("没有找到你要的数据\n");
 }
}
// 7、添加元素(在队尾添加)
void addNumber(p_Sequence_table T,int num)
{
 // 顺序表还没有满的时候
 if (isFull(T) == 0)
 {
  T->data[T->length] = num;
  T->length++;
 }
}
// 8、顺序表的遍历
void printAllNumOfSequenceTable(p_Sequence_table T)
{
 for (int i = 0; i<T->length; i++)
 {
  printf("T[%d]=%d ",i,T->data[i]);
 }
 printf("\n");
}
//9、插入操作
int insertNumByIndex(p_Sequence_table T, int num,int index)
{
 if (index<0||index>T->length)
 {
  return 0;
 }
 T->length++;
 for (int i = T->length-1; i>index; i--)
 {
  int temp = T->data[i];
  T->data[i] = T->data[i-1];
  T->data[i-1] = temp;
 }
 T->data[index] = num;
 return 1;
}
// 10、删除元素
void delectNum(p_Sequence_table T,int index)
{
 if (T->length <= 0)
 {
  printf("该顺序表中没有数据,不用删除");
 }
 for (int i = index;i<T->length-1; i++)
 {
  int temp = T->data[i];
  T->data[i] = T->data[i+1];
  T->data[i+1] = temp;
 }
 T->data[T->length-1] = 0;
 T->length--;
}
int main(int argc, const char * argv[]) {

 // 创建顺序表的结构体
 Sequence_table seq_t;
 // 初始化
 initSequenceTable(&seq_t);
 // 添加数据
 addNumber(&seq_t, 1);
 addNumber(&seq_t, 2);
 addNumber(&seq_t, 3);
 // 打印验证
 printAllNumOfSequenceTable(&seq_t);
 // 根据索引下标查内容
 int num = selectSequenceTableByIndex(&seq_t, 2);
 printf("你查的数据是:%d\n",num);
 // 插入
 insertNumByIndex(&seq_t, 4, 1);
 printAllNumOfSequenceTable(&seq_t);
 // 根据内容查下标
 selectSequenceTableByNum(&seq_t, 4);
 // 根据下标删除数据
 delectNum(&seq_t, 1);
 printAllNumOfSequenceTable(&seq_t);
 return 0;
}

运行结果为:

T[0]=1 T[1]=2 T[2]=3
你查的数据是:3
T[0]=1 T[1]=4 T[2]=2 T[3]=3
你要找的元素的下标是:1
T[0]=1 T[1]=2 T[2]=3

知识点扩展:

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

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

list的基本实现技术

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

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

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

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

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

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

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

以上就是什么是Python中的顺序表的详细内容,更多关于Python中顺序表详解的资料请关注我们其它相关文章!

(0)

相关推荐

  • Python中顺序表的实现简单代码分享

    顺序表python版的实现(部分功能未实现) 结果展示: 代码示例: #!/usr/bin/env python # -*- coding:utf-8 -*- class SeqList(object): def __init__(self, max=8): self.max = max #创建默认为8 self.num = 0 self.date = [None] * self.max #list()会默认创建八个元素大小的列表,num=0,并有链接关系 #用list实现list有些荒谬,全当

  • python实现顺序表的简单代码

    顺序表即线性表的顺序存储结构.它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的.比如,第1个元素是存储在线性表的起始位置LOC(1),那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上,其中sizeof(ElemType)表示每一个元素所占的空间. 下面是顺序表的python实现: #coding:utf-8 ''' author:xzfreewind ''' class SeqList(object): def

  • Python数据结构之顺序表的实现代码示例

    顺序表即线性表的顺序存储结构.它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的.比如,第1个元素是存储在线性表的起始位置LOC(1),那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上,其中sizeof(ElemType)表示每一个元素所占的空间. 追加直接往列表后面添加元素,插入是将插入位置后的元素全部往后面移动一个位置,然后再将这个元素放到指定的位置,将长度加1删除是将该位置后面的元素往前移动,覆盖该元素,然

  • 什么是Python中的顺序表

    1.顺序表介绍 顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以插入.删除时需要移动大量元素.顺序表可以分配一段连续的存储空间Maxsize,用elem记录基地址,用length记录实际的元素个数,即顺序表的长度 上图1表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元

  • 详解Python数据结构与算法中的顺序表

    目录 0. 学习目标 1. 线性表的顺序存储结构 1.1 顺序表基本概念 1.2 顺序表的优缺点 1.3 动态顺序表 2. 顺序表的实现 2.1 顺序表的初始化 2.2 获取顺序表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 顺序表应用 3.1 顺序表应用示例 3.2 利用顺序表基本操作实现复杂操作 0. 学习目标 线性表在计算机中的表示可以采用多种方法,采用不同存储方法的线性表也有着不同的名称和特

  • 一文搞懂Python中pandas透视表pivot_table功能详解

    目录 一.概述 1.1 什么是透视表? 1.2 为什么要使用pivot_table? 二.如何使用pivot_table 2.1 读取数据 2.2Index 2.3Values 2.4Aggfunc 2.5Columns 一文看懂pandas的透视表pivot_table 一.概述 1.1 什么是透视表? 透视表是一种可以对数据动态排布并且分类汇总的表格格式.或许大多数人都在Excel使用过数据透视表,也体会到它的强大功能,而在pandas中它被称作pivot_table. 1.2 为什么要使用

  • 一文搞懂Python中pandas透视表pivot_table功能

    目录 一.概述 1.1 什么是透视表? 1.2 为什么要使用pivot_table? 二.如何使用pivot_table 2.1 读取数据 2.2Index 2.3Values 2.4Aggfunc 2.5Columns 一文看懂pandas的透视表pivot_table 一.概述 1.1 什么是透视表? 透视表是一种可以对数据动态排布并且分类汇总的表格格式.或许大多数人都在Excel使用过数据透视表,也体会到它的强大功能,而在pandas中它被称作pivot_table. 1.2 为什么要使用

  • python中Flask Web 表单的使用方法介绍

    目录 简介 普通表单提交 Flask-WTF基础 使用Flask-WTF处理表单 Flask消息闪现 文件上传 文件上传的另一种写法 简介 表单的操作是Web程序开发中最核心的模块之一,绝大多数的动态交互功能都是通过表单的形式实现的.本文会教大家实现简单的表单操作. 普通表单提交 在创建模板login.html页面中直接写form表单. login.html <!DOCTYPE html> <html lang="en"> <head>    <

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

    本文实例讲述了Python中顺序表原理与实现方法.分享给大家供大家参考,具体如下: Python中的顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术,具有顺序表的所有性质. tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似. list的基本实现技术 Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的顺序(即保序),而且还具有以下行为特征: 基于下标(位置

  • C语言顺序表的实现代码

    本文实例为大家分享了C语言实现顺序表的具体代码,供大家参考,具体内容如下 seqlist.h #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> #define SEQLIST_INIT_SIZE 8 #define INC_SIZE 3 //空间增量的大小 typedef int ElemType; typedef stru

  • Python中的嵌套循环详情

    目录 1 什么是嵌套循环 2 Python 嵌套 for 循环 2.1 嵌套循环打印图案 2.2 在 for 循环中的while循环 2.3 实践:打印一个带有 5 行 3 列星形的矩形图案 3 打破嵌套循环 4 继续嵌套循环 5 使用列表理解的单行嵌套循环 6 Python中的嵌套while循环 6.1 While 循环内的 for 循环 7 何时在 Python 中使用嵌套循环? 1 什么是嵌套循环 所谓嵌套循环就是一个外循环的主体部分是一个内循环.内循环或外循环可以是任何类型,例如 whi

随机推荐