美文网首页
线性表及顺序存储

线性表及顺序存储

作者: 会讲段子的挨踢狗 | 来源:发表于2018-08-11 11:17 被阅读0次

多项式的表示
一元多项式及其运算
f(x)=a_0 + a_1x + a_{n-1}x^{n-1} + a_nx^n
主要运算:多项式相加、相减、相乘等

如何表示多项式?

多项式的关键数据
  • 多项式项数n
  • 各项系数a_i 和指数 i
方法1:顺序存储结构直接表示

数组各分量对应多项式各项
比如
f(x)=4x^5 - 3x^2 +1
用两个数组表示

image.png

第一个数组表示的是次幂
第二个数组表示的是系数

不足之处在于当遇到x + 3x^{2000}
表示次幂的数组前面0-1999空置,很多空间被浪费

方法2:顺序存储结构表示非零项

每个非零项涉及两个信息:指数和系数

image.png

按照指数大小有序存储!

方法3:链表结构存储非零项

链表中的每个结点存储多项式中的一个非零项,包括系数和指数两个数据域以及一个指针域

链表存储表示为

image.png

多项式表示问题的启示

  • 同一个问题可以有不同的表示存储方法
  • 有同一类共性问题:有序线性序列的组织和管理

线性表:由同类型数据元素构成有序序列的线性结构

  • 表中元素个数称为线性表的长度
  • 线性表没有元素时,称为空表
  • 表起始位置称表头,表结束位置称表尾

线性表的抽象数据类型描述

类型名称:线性表(List)

数据对象集:线性表是n(>=0)个元素构成的有序序列(a_1,a_2 ...a_n)

操作集:线性表L属于List,整数i表示位置,元素X属于ElemenType

线性表基本操作主要有:

  • List MakeEmpty(): 初始化一个空线性表L
  • ElementType FindKth(int K,List L):根据位序K,返回相应元素
  • int Find(ElementType X,List L):在线性表L中查找X的第一次出现位置
  • void Insert(ElementType X,int i,List L):在位序i前插入一个新元素X
  • void Delete(int i,List L):删除指定位序i的元素
  • int Lenght(List L):返回线性表L的长度n
线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

image.png

主要操作的实现

1. 初始化(建立空的顺序表)

image.png

通过malloc申请结构

image.png

把结构的Last声明为-1,因为Last代表的是最后一个,对应下标需要-1

image.png

返回结构的指针

image.png

2. 查找

image.png

平均查找次数为(n+1)/2
平均时间性能为O(n)

3. 插入

插入到第i个位置,对应下标为i-1
其次,先把最后一个往后挪,依次腾出直到腾出第i个位置

image.png image.png

p->[num]表示p指向的结构体变量中的num成员。

4. 删除

和插入不一样的是
插入,是从前往后挪
删除,从前往后挪

image.png image.png

相关文章

  • C语言实现顺序表(顺序存储结构)

    顺序表(顺序存储结构)及初始化过程详解 顺序表,全名顺序存储结构,是线性表的一种。通过《线性表》一节的学习我们知道...

  • 线性链表

    线性链表 线性表的顺序存储结构:顺序表线性表的链式存储结构:线性链表 线性表的链式存储所占存储空间大于顺序存储。 ...

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

    之前写了线性表的顺序存储结构和有序线性表的顺序存储结构,今天接着写线性表的链式存储结构 数据结构之线性表的顺序存储...

  • 数据结构和算法之一——线性表_2_顺序结构存储

    线性表存储结构分类线性表有两种物理存储结构:1)顺序存储结构;2)链式存储结构 顺序存储结构2.1定义:线性表的顺...

  • 数据结构之有序线性表的链式存储结构

    之前写了线性表的顺序存储结构和有序线性表的顺序存储结构以及线性表的链式存储结构,今天接着写有序线性表的链式存储结 ...

  • 数据结构与算法(二)--- 单向循环链表

    线性表 线性表分为顺序存储结构和链式存储结构 存储方式 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;...

  • 数据结构——顺序表

    顺序表:采用顺序存储方式的线性表称为顺序表 顺序存储结构:指的是用一段地址连续的存储单元依次存储线性表的数据元素,...

  • 线性表--顺序存储结构

    一、线性表的顺序存储结构 线性表有两种物理存储结构:顺序存储结构和链式存储结构。 顺序存储结构 ①定义:用一段地址...

  • 我与数据结构的二次博弈(二)

    线性表的顺序存储结构及实现 1. 顺序存储结构的基本思想: 用一组连续的存储单元依次存储数据元素,数据元素...

  • 线性表及应用

    线性表 “线性表(List):零个或多个数据元素的有限序列。” 线性表的顺序存储结构 线性表的顺序存储结构,指的是...

网友评论

      本文标题:线性表及顺序存储

      本文链接:https://www.haomeiwen.com/subject/mnvbmftx.html