php数据结构之线性表 数据结构线性表常见问题

什么是线性表？线性表有哪两种存储结构？它们是如何存储数据元素的？各有什么优点？

线性表：有n（n0）的数据元素a1，a2，a3，.....，an组成的有限序列。

成都创新互联专注于吉县企业网站建设,成都响应式网站建设公司,购物商城网站建设。吉县网站建设公司,为吉县等地区提供建站服务。全流程按需设计网站，专业设计，全程项目跟踪，成都创新互联专业和态度为您提供的服务

两种存储结构：

顺序存储结构：存取较快，插入删除较麻烦。

链式存储结构：存取较慢，插入删除叫简单。

存储数据元素：

顺序存储结构：直接存取。优点空间连续，位置明确。

链式存储结构：由于链表特征，需要从表头扫面。优点空间分散，位置不明确。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表。

扩展资料：

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

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。

当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。

数据结构笔记（四）——线性表

前面说过，数据结构的类型大方向上来说分为 线性结构 和 非线性结构 ，下面要说的线性表就是线性结构的一种。

（复习一下，前面说过的线性结构有：线性表、栈、队列、字符串、数组和广义表）

上一行是课本上的原话，但是感觉这个在逻辑上有一些不清楚的地方，先忘掉上一行的东西吧，看完下面的再回来想想。

先来说一下线性表是什么。

线性表简单来说就是一个* 有限个元素的序列 ***。

本来有一堆山楂，你拿个竹签，一个一个穿起来，就构成了线性表。

请记好，这里还有串“低配版”的只有山楂没有糖的糖葫芦，我们后面就用它来类比线性表。

——OOOOOOOOOOO————————(→.→ 我叫糖葫芦。。。)

1.首先，这串糖葫芦的山楂的个数一定是可数的。

所以类比到线性表，线性表的元素一定是有限的。

2.然后，一般吃糖葫芦都是从开头第一个山楂开始吃，吃到最后一个山楂吃完。

类比到线性表，线性表有且只有一个开始节点、有且只有一个终端节点。

3.除了糖葫芦的第一个和最后一个山楂，其余的每个山楂都左边有一个山楂右边有一个山楂。

类比，线性表除了两端的元素节点，其他的每个元素都有且只有一个前驱节点和后继节点。

4.世界上没有两片完全相同的树叶，也没有两颗完全相同的山楂。对于这串糖葫芦，山楂的位置都是固定的，该是第几个就是第几个（假如你不吃或者不把山楂往前撸的话），只要通过 位序 就能找到对应的山楂的位置。

5.吃完了这串糖葫芦，就只剩一个空竹签了。类比地，把含有0个元素节点的线性表称为 空表 。

6.当然，吃了半天糖葫芦，必须要知道的是，这串糖葫芦的每一个“元素”都是“山楂”，而不是其他什么果子。

类比线性表，线性表要求每一个数据元素的类型都是相同的，不能混进去什么奇怪的东西。

概括来说，线性表的三大特点就是： 同一性 （6）、 有穷性 （1）、 有序性 （2、3、4）。

说完了线性表的性质，可能就会有一些疑问：上面的糖葫芦模型是万能模型吗？（这个模型是不是完整模型？糖葫芦模型能不能代表所有线性表的特点?）

比如：我不想从第一个山楂开始吃，我从第二个开始吃可不可以？那对应的线性表的逻辑会不会乱掉？

答案是：虽然逻辑不会乱，你怎么吃那都是一串山楂；糖葫芦模型只是为了形象地表达一下线性表的最主要的特点，并不能解释所有的线性表的特点。后面还有别的线性表的内容呢，不能老吃糖葫芦呀多腻呀。。。

实际上线性表是有分类的（这个书上没说），按照操作方式，线性表一般分为 一般线性表 和 受限线性表 两种。

有什么区别呢？

一般线性表 就是前面的糖葫芦模型，你爱从哪里开始吃就从哪里开始，爱吃第几个就吃第几个。（对应的线性表例如数组）

受限线性表 就不是糖葫芦了，而是桶装薯片（栈）和吸管（队列）。

这时候你只能先吃最上层的薯片，吃了上层才能拿下一层的，不能随便拿中间的第X层的那张薯片。

或者是吸管，你只能最先喝到最先进入吸管的那一部分，而不能直接就喝到吸管中段的那部分。

总而言之，这时候你的操作受限制了，不能再任性下去了，所以这样的线性表，称为受限线性表。

好，现在关于线性表的一些基础知识都过了一遍，现在让我们回到开头，我说“感觉逻辑怪怪的”这里。

课本上说的线性结构包含了：线性表、栈、队列、字符串、数组和广义表。似乎是把线性表和栈、队列、数组这些东西给平行表示了。

但是实际上，线性表与栈、队列和数组（或者也包括字符串）不是平行的。

线性表包括了栈、队列和数组、字符串 。

所以说，其实数据结构里的线性结构大多都是以线性表表示的。然后根据操作性质分别选用了“一般线性表”或者“受限线性表”，然后又根据不同的使用场景再一步细分为使用哪一种线性表（栈？队列？数组？串？）。

关于线性表的概念就到这里，后面的几期还会有薯片吸管糖葫芦等着我去吃。

新手上路，才疏学浅。如有错漏，多谢指教。

数据结构如何建立1个线性表？

建立顺序表代码如下：

由数组元素a[0..n-1]创建顺序表L。将a中的每个元素依次放入顺序表中，并将n赋值给顺序表的长度域。算法为：

void CreateList(SqList * L, ElemType a[], int n){

int i=0, k=0;

L = (SqList *)malloc(sizeof(SqList));    //分配存储线性表的空间

while(in){

  L-data[k] = a[i];

  k++; i++;

}

L-length = k;        //设置线性表的实际长度，设置为k（即a的长度n）

}

扩展资料

线性表的特点：

1、对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；

2、数据元素之间具有一种线性的或“一对一”的逻辑关系。

3、第一个数据元素没有前驱，这个数据元素被称为开始节点；

4、最后一个数据元素没有后继，这个数据元素被称为终端节点；

5、除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

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

基本操作如下：

1、线性表的置空操作clear()：将一个已经存在的线性表置为空表。

2、线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false。

3、求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值。