User-Profile-Image
hankin
  • 5
请到[后台->外观->菜单]中设置菜单。
  • 分类
    • 靶机渗透
    • 计算机小技巧
    • 未分类
    • 数据结构
    • 内网渗透
    • 代码审计
    • XSS
    • WEB安全漏洞学习
    • Web
    • python
    • PHP
    • NodeJS
    • MYSQL
    • Misc
    • JavaScript
    • Docker
    • CTF相关知识点
    • CTFWP
    • Crypto
    • Cobalt Strike
  • 页面
  • 友链
    • 三哥的博客
    • Root师傅的博客
    • EDS师傅的博客
    • 天正哥的博客
    • 天尘翼师傅的博客
    • 熵增师傅的github
    • 信仰的博客
    • Jadore的博客
Help?

Please contact us on our email for need any support

Support
    首页   ›   数据结构   ›   正文
数据结构

线性表的概念及顺序存储

2020-03-04 09:07:16
46  0 0

线性表的概念及运算

定义:线性表是由n个类型相同的数据元素a1,a2……an组成的有限序列

记作(a1,a2……ai,ai+1……an)

数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继

逻辑结构图

线性表的特点:

1.同一性:线性表由同类数据元素组成,每一个ai必须属于同一数据对象

2.有穷性:线性表由有限个数据元素组成,表长度就是表中数据元素的个数

3.有序性:线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>

线性表的顺序存储

定义:是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

采用顺序存储结构的线性表通常称为顺序表。

假设线性表中每个元素占k个单元,第一个元素的地址为loc(a1),则第i个元素的地址为:loc(ai)=loc(ai)+(i-1)*k

基本运算:1.查找操作 2.插入操作 3.删除操作

1.查找操作:按序号查找GetData(L,i): 要求查找线性表L中第i个数据元素,其结果是L.elem[i]。

(1).按内容查找Locate(L,x): 要求查找线性表L中给定值x相等的数据元素,其结果是:若在表L中找到与x相等的元素,则返回该元素在表中的序号;若找不到,则返回一个“空序号”,如-1.

int Locate(SeqList L,ElemType x){
int i;
while(i<=L.length)&&(L.elem[i]!=x)
i++;
if(i<=L.length) return(i);
else return(-1);
}

2.插入操作:是指在表的第i(1<=i<=n+1)个位置,插入一个新元素e,使长度为n的线性表(e1,……ei-1,ei……en)变成长度为n+1的线性表(e1,……ei-1,X,ei……en)

3.删除操作:是指将表的第i(1<=i<=n)个元素删去,是长度为n的线性表 (e1,……ei-1,ei,ei+1……en) ,变成长度为n-1的线性表 (e1,……ei-1,ei+1……en)

线性表的顺序存储优缺点

优点

1.用数据存储元素,操作方法简单,容易实现

2.无须为表示节点间的逻辑关系而增加额外的存储开销。

3.存储密度高。

4.顺序表可按元素位序随机存取节点。

缺点

1.插入或删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作都必须移动大量的节点,其效率较低;

2.由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配。因此当表长变化较大时,难以确定合适的存储规模。

评论 (0)

点击这里取消回复。

欢迎您 游客  

近期文章
  • SUCTF 2019 Guess_game
  • Python pickle反序列化
  • [安洵杯 2019]easy_serialize_php
  • Session反序列化
  • 原生类序列化
近期评论
    文章归档
    • 2021年1月
    • 2020年12月
    • 2020年11月
    • 2020年9月
    • 2020年7月
    • 2020年6月
    • 2020年5月
    • 2020年4月
    • 2020年3月
    • 2020年2月
    • 2020年1月
    分类目录
    • Cobalt Strike
    • Crypto
    • CTFWP
    • CTF相关知识点
    • Docker
    • JavaScript
    • Misc
    • MYSQL
    • NodeJS
    • PHP
    • python
    • Web
    • WEB安全漏洞学习
    • XSS
    • 代码审计
    • 内网渗透
    • 数据结构
    • 未分类
    • 计算机小技巧
    • 靶机渗透
    功能
    • 登录
    • 项目feed
    • 评论feed
    • WordPress.org
    分类目录
    Copyright © 2021 网站备案号: 蒙ICP备20000552号-1
    smarty_hankin 主题. Designed by hankin
    主页
    页面
    博主
    purplet 管理员
    努力并有所方向
    157 文章 0 评论 20271 浏览
    测试
    测试