原来你是这样的数据结构之线性表

算法是一切程序设计的基础灵魂,更是一位程序员水平高低的集中体现.

这是<<java常用算法手册>>中页面话,也说明了算法的重要性,干程序员也有几年了,随着学习的工作的越来越多,越来越深入,
不知不觉中感觉到的自己的瓶颈,在学习很多知识的时候,发现自己很难继续深入学习下去.干程序员这个行业就好像在练功,而
我们所分各种程序员中,前端程序员,后端程序员,android程序员,iOS程序员...大家只是练的外功不同,而我们的内功却被我们
忽视掉了,数据结构与算法就是内功,只有内功高深了,什么招式,那都是手拿擒来!

我写的这些学习笔记都是出自<<java常用算法手册>>!

什么是线性表?

在现实生活中,我们可以找到很多的例子来说明什么是线性表,比如26个英文字母(A,B,C,...,Z)中,每个英文字符就是一个数据元素,也称为数据结点.那么具体的定义是什么呢?

线性表是由n个数据元素组成的有序序列.

  • 数据元素的个数为n,也称为表的程度,当n=0的时候称为空表;
  • 如果一个线性表非空,即n>0,则可以简单地记作(a1,a2,...,an);
  • 数据元素ai(1<=i<=n)表示各个元素,在不同的场合,其含义也不同;

其逻辑结构特征如下:

  • 有且仅有一个开始结点a1,没有直接前趋结点,有且仅有一个后趋结点a2;
  • 有且仅有一个终结结点an,没有直接后继结点,有且仅有一个直接前趋结点;
  • 其余的内部结点ai(2<=i<=n-1)都有且仅有一个直接前趋结点和一个后趋结点;
  • 对于同一线性表,各数据元素ai必须具有相同的数据类型,即同一线性表中各数据元素具有相同类型,每个数据元素的长度相同.

线性表的基本运算

  1. 初始化
    初始化表(InitList)即构造一个空的线性表L.
    2.计算表长
    计算表长(ListLength)即计算线性表L中的结点的个数.
    3.获取结点
    获取结点(GetNode)即取出线性表L中第i个结点的数据,这里1<=i<=ListLength(L)
    4.查找结点
    查找结点就是找到线性表中值为x的结点,并返回该结点在线性表L中结点的位置,如果没有找到则返回错误标示.
    如果有多个相同的结点,则返回第一个结点.
    5.插入结点
    插入结点就是在线性表第i个位置插入结点,使得其后的结点编号依次加1,插入新的结点后,线性表L的长度将变为n+1.
    6.删除结点
    删除结点就是删除线性表L中第i个结点,使得其后的所有节点编号依次减1,线性表L的长度将变为n-1.

线性表的储存结构

线性表的存储结构有两种,一种是顺序存储结构,一种是链式存储结构.
原来你是这样的数据结构之线性表

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容