浅谈线性表

halo~大家好，今天来跟大家分享数据结构线性表、栈与队列的区别。

一、线性表

1、什么是线性表

还记得我们小学时放学之前要做什么吗--排队。我记得我总是排在第二位置，前面是那个男孩，后面是另外一个男孩，每次都是他们，为什么要这么做？因为当我看不见他们的时候，老师可以迅速找出谁不在，迅速清点人数。这种排好队的组织方式，就是我们即将学习的数据结构：线性表。

2、线性表（List）的定义

零个或多个数据元素的有限序列。

注意：第一个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继。

线性表元素的个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

图 1-1

3、线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。如图1-2所示。

图1-2

在C语言中可以用一位数组实现顺序存储结构。

注意区分：“数组的长度”和“线性表的长度”

数组的长度：是存放线性表的存储空间的长度，存储分配后这个大小一般不会改变。

线性表的长度：是线性表中数据元素的个数。

在任意时刻，线性表的长度应小于等于数组的长度。

优点：

①无须为表示表中元素之间的逻辑关系而增加额外的存储空间；

②可以快速地存取表中任一位置的元素；

缺点：

①插入和删除操作需要移动大量的元素；

②当线性表长度变化大时，难以确定存储空间的容量；

③造成存储空间的碎片；

4、线性表的链式存储结构

那么链式存储结构与顺序结构有什么不一样呢？在顺序结构中，除了要存数据元素外的信息，还要存储它的后继元素的存储地址。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域存储的信息称为直接或链。这两部分信息组成数据元素ai的存储映像，称为结点。

图 1-3

我们把链表中第一个结点的存储位置称为头指针，最后一个结点指针为空（NULL）。

头指针与头结点的异同：

5、单链表结构与顺序存储结构的优缺点

好啦~今天的分享到此为此，下期详细介绍几种链表。