python数据结构之线性表的顺序存储结构

用Python仿照C语言来实现线性表的顺序存储结构,供大家参考,具体内容如下

本文所采用的数据结构模板为 《数据结构教程》C语言版,李春葆、尹为民等著。

该篇所涉及到的是线性表的顺序存储结构。

代码:

# !/usr/bin/env python
# -*- coding: utf-8 -*-

__author__ = 'MrHero'

class Node(object):
  """
  线性表的存储结构
  和 C 语言中的链式存储结构类似
  """
  def __init__(self, data=None):
    self.data = data
    self.next = None

class LKList(object):
  """
  线性表的具体操作
  """

  def __init__(self):
    """
    相当于初始化线性表, 即创建头结点
    头节点为空节点,占据位置号为0
    创建好的表即为: 头节点[0]->节点[1]->节点[2]->节点[3]->节点[4]
    :return:
    """
    self.L = Node(None)
    self.L.next = None
    self.length = 0

  def is_empty(self):
    """
    判断线新表的长度
    :return:
    """
    return self.length == 0

  def get_length(self):
    """
    获取线新表的长度
    :return:
    """
    return self.length

  def insert(self, i, elem):
    """
    在指定位i处置插入元素elem
    :param i: 指定的位置
    :param elem: 插入的元素elem
    :return:
    """
    j = 0
    p = self.L
    while j < i-1 and p is not None: # 查找第 i-1 个节点
      j += 1
      p = p.next
    if p is None:  # 未找到逻辑位序为 i-1 的节点
      raise IndexError("Index is out of range!")
    else:  # 找到逻辑位序为 i-1 的节点
      tmp = Node(elem)
      tmp.next = p.next
      p.next = tmp
      self.length += 1

  def delete(self, i):
    """
    删除指定节点的元素
    :param i: 指定节点
    :return: 删除的指定节点元素值
    """
    if self.is_empty():
      raise IndexError("The list is empty!")
    elif 0 < i <= self.length:
      j = 1
      p = self.L
      while j < i and p:
        p = p.next
        j += 1
      delelte_node = p.next
      p.next = delelte_node.next
      self.length -= 1
      return delelte_node.data
    else:
      raise IndexError("Index is out of range!")

  def get_elem(self, i):
    """
    获取某个节点的值
    :param i:
    :return:返回某个节点的值
    """
    if self.is_empty():
      raise IndexError("The list is empty")
    elif 0 < i <= self.length:
      j = 0
      p = self.L
      while j < i and p:
        p = p.next
        j += 1
      print p.data
    else:
      raise IndexError("Index is out of range!")

  def locate_elem(self, elem):
    """
    查找某值的位置
    :param elem:
    :return: 返回第一个值等于elem的位置
    """
    j = 0
    p = self.L
    while p is not None and p.data != elem:
      p = p.next
      j += 1
    if p is Node:
      return -1
    else:
      return j

  def create_dict_list_H(self, list):
    """
    头插法建表
    :param list:
    :return:
    """
    p = self.L
    for i in range(len(list)):
      tmp = Node(list[i])
      tmp.next = p.next
      p.next = tmp
      self.length += 1

  def create_dict_list_E(self, list):
    """
    尾插法建表
    :param list:
    :return:
    """
    p = self.L
    r = p
    for i in range(len(list)):
      tmp = Node(list[i])
      r.next = tmp
      r = tmp
      self.length += 1
    r.next = None

  def show_lklist(self):
    if self.is_empty():
      raise IndexError("It's a empty list!")
    else:
      j = 1
      p = self.L
      while j <= self.length and p:
        p = p.next
        if p is not None:
          print p.data
        j += 1

if __name__ == '__main__':
  lk = LKList()
  #
  # lk.create_dict_list_E([1, 2, 3, 4])
  # print "-----"
  # lk.get_elem(1)
  # lk.get_elem(2)
  # lk.get_elem(3)
  # lk.get_elem(4)
  # print "-------"
  # lk.show_lklist()
  # lk.insert(3, 5)
  # print "-------"
  # lk.show_lklist()
  # lo = lk.locate_elem(5)
  # print "location is %d" % lo
  # lk.delete(4)
  # print "-------"
  # lk.show_lklist()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python中的函数式编程:不可变的数据结构

    让我们首先考虑正方形和长方形.如果我们认为在接口方面,忽略了实现细节,方块是否是矩形的子类型? 子类型的定义取决于Liskov代换原理.为了成为一个子类型,它必须能够完成超级类型所做的一切. 如何定义矩形的接口? zope.interface import Interface class IRectangleInterface: get_length: """Squares can do that""" get_width: "&quo

  • Python常见数据结构之栈与队列用法示例

    本文实例讲述了Python常见数据结构之栈与队列用法.分享给大家供大家参考,具体如下: Python常见数据结构之-栈 首先,栈是一种数据结构.具有后进先出特性. #栈的实现 class Stack(): def __init__(self,size): self.stack=[] self.size=size self.top=-1 def push(self,content): if self.Full(): print "Stack is Full" else: self.sta

  • Python数据结构之图的应用示例

    本文实例讲述了Python数据结构之图的应用.分享给大家供大家参考,具体如下: 一.图的结构 二.代码 # -*- coding:utf-8 -*- #! python3 def searchGraph(graph,start,end): results =[] generatePath(graph,[start],end,results) results.sort(key =lambda x:len(x)) return results def generatePath(graph,path,

  • 详解python的四种内置数据结构

    对于每种编程语言一般都会规定一些容器来保存某些数据,就像java的集合和数组一样python也同样有这样的结构 而对于python他有四个这样的内置容器来存储数据,他们都是python语言的一部分可以直接使用而无需额外的导入 一.列表(list) 列表一种跟java和c中的数据很像的一种数据结构,他都是保存一系列相似,且有序元素的集合,不过不同的是列表中的元素可以不是同一种数据类型,且列表的长度是可变的 可以动态的增加可减少这一点则有点像java中的stringBuilder对象,列表中有一点值

  • Python数据结构之栈、队列及二叉树定义与用法浅析

    本文实例讲述了Python数据结构之栈.队列及二叉树定义与用法.分享给大家供大家参考,具体如下: 目前只实现了三种,栈.队列和二叉树,哪天得空继续补吧~ 1. 栈 #栈 class Stack: def __init__(self,size = 16): self.stack = [] self.size = size self.top = -1 def setSize(self, size): self.size = size def isEmpty(self): if self.top ==

  • python数据结构学习之实现线性表的顺序

    本文实例为大家分享了python实现线性表顺序的具体代码,供大家参考,具体内容如下 线性表 1.抽象数据类型表示(ADT) 类型名称:线性表 数据对象集:线性表是n(>=0)个元素构成的有序序列(a1,a2,-.,an) 操作集: 2.线性表的顺序实现 1.表示方法: 其中100可以自己规定,last代表线性表的长度 # 线性表定义 class Lnode(object): def __init__(self,last): self.data = [None for i in range(100

  • Python数据结构之哈夫曼树定义与使用方法示例

    本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel

  • python数据结构之线性表的顺序存储结构

    用Python仿照C语言来实现线性表的顺序存储结构,供大家参考,具体内容如下 本文所采用的数据结构模板为 <数据结构教程>C语言版,李春葆.尹为民等著. 该篇所涉及到的是线性表的顺序存储结构. 代码: # !/usr/bin/env python # -*- coding: utf-8 -*- __author__ = 'MrHero' class Node(object): """ 线性表的存储结构 和 C 语言中的链式存储结构类似 ""&q

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

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

  • java线性表的存储结构及其代码实现

    Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素

  • Java数据结构之线性表

    线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等.而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表.单链表以及双链表的各种基本操作. 1:线性表抽象的数据类型 线性表:是由n(n>=0)个数据相同的元素组成的有限序列.线性表的定义接口如下 public interface IList<T> { /** * 是否为空 * @return */ boolean isEmpty(); /** *

  • C语言数据结构之线性表的链式存储结构

    1.什么是线性表的链式存储结构 -链表 存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息 这个结点有:数据域和指针域 一个指针域:指向后继结点, 单链表 二个指针域: 指向前继结点,还有一个指向后继结点 双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结

  • Java 数据结构线性表之顺序存储详解原理

    目录 线性表的定义 线性表的基本运算 线性表的存储之顺序存储 定义线性表 添加元素 查找元素 删除元素 打印线性表 实现的完整代码 测试一下 线性表的定义 线性表的逻辑特征: ①有且仅有一个称为开始元素的a1,她没有前趋,仅有一个后继结点a2: ②有且仅有一个称为终端元素的an,他没有后继,只有一个直接前驱a(n-1): ③其余元素ai(2≤i≤n-1)称为内部元素,他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1). 线性表的图像表示 线性表的基本运算 线性表初始化 求表长 按索引值

  • Java实现线性表的顺序存储

    本文实例为大家分享了Java实现线性表的顺序存储,供大家参考,具体内容如下 顺序表:用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 package algorithm.datastructure.seqlist; /*顺序表 * * 用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 * */ public class SeqList { private int length;//

  • java数据结构基础:线性表

    目录 前言 需求分析 编码 add方法 getIndex方法 pop方法 insert方法 getAll 全部代码 总结 前言 其实线性表在生活中和栈的结构差不多.昨天总结了一篇单链表,也是线性表的一种. 今天用另一种写法来控制指针的移动实现数据的顺序存储结构. 需求分析 首先要明确,这种顺序存储结构的线性表底层用什么.根据之前查看过的源码来看,list一般都是以数组为底层.我们也不例外. 其次,我们还得去定义好线性表的长度,以及每个元素的指针. private Object[] arr; //

  • Java数据结构(线性表)详解

    线性表的链式存储与实现 实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销. 单链表 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针.这里具有

  • C语言线性表顺序存储结构实例详解

    C语言线性表顺序存储结构实例详解 1. 什么是顺序存储结构? 用一段地址连续的存储单元依次存储线性表的数据元素. 2.线性表的顺序存储结构 #include<stdio.h> #include<stdlib.h> #define Max 80 //存储空间初始分配量 #define Increment 10 //存储空间分配增量 typedef struct { int *elem; // 存储空间基地址,此处为int型,视情况而定 int length; // 元素表当前长度 i

随机推荐