数据结构和算法（三）线性表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构和算法（三）线性表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2433字，纯文字阅读大概需要4分钟。

内容图文

前言

      本章讲解数据结构中第一个逻辑结构——线性表

方法

1.概念

通过前面的讨论，我们知道了数据结构的基本概念和研究方向，以及算法的基本概念。

接下来我们来学习第一个逻辑结构线性表，这也是数据结构中最为简单的一种逻辑结构。

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

2.线性表的基本特征

1）相同的数据类型

在线性表中，存储的是相同的数据类型，这意味着每个元素占用着相同的存储空间，方便后续的查找。

2）序列（顺序性）

线性表的数据是具有顺序性的。除最后一个元素之外，均有唯一的后继(后件)，除第一个元素之外，均有唯一的前驱(前件)。

3）有限

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

3.线性表的逻辑结构

数据结构中的元素存在一对一的相互关系；

这个已经在之前的博客中做了介绍。

4.线性表的存储结构

1）顺序存储结构

特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址

优点：

• 节省存储空间，因为分配给数据的存储单元都用来存储数据，节点间的逻辑关系没有用额外的存储空间。
• 索引查找效率高，只需要知道表头的地址就可以知道线性表中其中一个元素（下标）的地址

缺点：

• 插入和删除需要移动数据，效率低
• 必须提前分配固定数量的存储空间，如果存储元素少，将导致空间浪费

接下来我们来探究其查找算法的时间复杂度

在Java中，我们可以通过如下代码查找线性表（顺序存储结构ArrayList）指定的数据:

package com.wondersgroup.training;

import java.util.ArrayList;
import java.util.List;

public class Welcome {

	public static void main(String[] args) {
		List<String> list = new ArrayList<>();
		list.add("a");
		list.add("b");
		list.add("c");
		//这里假定查找指定字符串“b”
		for(int i=0;i<list.size();i++){
			if("b".equals(list.get(i))){//基本语句
				System.out.println("找到该元素");
			}
		}
	}

}

第一步：找出算法的基本语句，很显然就是"b".equals(list.get(i));

第二步：算出该语句的时间频度，最坏的时间频度很显然是n，因为我们最多查找n次；

第三步：算出该算法时间频度的数量级，很显然也是n；

结论：该算法时间复杂度--> T(n) = O(n)

2）链式存储结构

 特点：数据元素存储空间不连续。每个结点由数据域和指针域所构成，数据域用来存储该节点的数据，指针域用来指示下一个数据所在的地址。逻辑上相邻的节点物理上不必相邻。

优点：

• 插入、删除节点比较灵活，不需要移动节点，只需要改变节点的指针域即可。（前提先定位到该元素才行）
• 有元素才会分配节点空间，不会有闲置的节点

缺点：

• 存储空间消耗大，每个节点由数据域和指针域构成。
• 查找指定节点较慢，需要从头开始连续进行查找。

在Java中，使用链式存储结构的线性表的例子为LinkedList

内容总结

以上是互联网集市为您收集整理的数据结构和算法（三）线性表全部内容，希望文章能够帮你解决数据结构和算法（三）线性表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---