数据结构导论(第二章线性表）

一、线性表的基本概念

线性表的逻辑结构 线性表是一种最简单、最常见的数据结构

线性表是由n（n≥0）个数据元素（结点）a1，a2，a3，……an组成的有限序列。 数据元素的个数n定义为表的长度。 当n=0时，称为空表

将非空的线性表（n＞0）记作：l=（a1，a2，a3，……，an） a1：起始结点，an：终端结点。 a1称为a2的直接前驱，a3称为a2的直接后继

线性表的特点：

• 线性表中只有1个起始结点，1个终端结点， 起始结点没有直接前驱，有1个直接后继。
• 终端结点有1个直接前驱，没有直接后继。
• 除这2个结点外，每个结点都有且只有1个直接前驱和1个直接后继

二、线性表的顺序存储

线性表顺序存储的方法：将表中的结点依次存放在计算机内存 中的一组连续存储单元中。

数据元素在线性表中的邻接关系决定其在存储空间中的存储位置；即逻辑结构中相邻的结点，其存储位置也相邻。

 用顺序存储实现的线性表称为顺序表。

顺序表上的基本运算 ： 插入（insert）、删除（delete）、定位（locate）

=======================插入=========================

线性表的插入运算：是指在表的位置i上，插入一个新结点x，使 长度为n的线性表（a1，a2，……，ai，……，an） 变为长度为n+1的线性表（a1，……，x，……，an）

插入时的主义事项：

• 当表空间已满，不可再做插入操作。
• 当插入位置是非法位置，不可做正常的插入操作。

顺序表插入操作过程

• 将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1 上，空出位置i。
• 在位置i上插入新结点x。 （当插入位置i=n+1时，无须移动结点，直接将x插入表的末尾）
• 该顺序表长度加1

假设线性表中含有n个数据元素，在进行插入操作时，有n+1个位置可插入; 在位置i插入时，要移动n-i+1个数据。

 

 需要移动：10-4+1=7 ；7个节点

======================删除=====================

线性表的删除运算：是指将表的位置i的结点删去，使长度为n的线性 表（a1，a2，……，ai，……，an）变成长度为n-1的线性表 （a1，a2，……，ai-1，ai+1，……，an）

注意事项：当要删除元素的位置i不在表长范围内时，为非法位置，不能做正 常的删除操作

顺序表删除操作过程

• 若i=n，则只要删除终端结点，无须移动结点；
• 若1≤i≤n-1，则必须将表中位置 i+1，i+2，……，n的结点，依次前移到 位置i，i+1，…，n-1上，以填补删除操作造成的空缺。 （仅当删除位置i=n时， 才无须移动结点，直接令表长度-1即可）
• 该表长度减1

假设线性表中含有n个数据元素，在进行删除操作时，有n个位置可删除， 在位置i删除时，要移动n-i个数据。

 

 

 

 结论：顺序存储结构表示的线性表，在做插入或删除操作时，平均 需要移动大约一半的数据元素。当线性表的数据元素量较大， 并且经常要对其做插入或删除操作时，这一点需要考虑

===================定位=====================

定位:从第一个元素a1起，依次和x比较， 直到找到一个与x相等的数据元素，则 返回它在顺序表中的存储下标或序号；当查遍整个表都没找到与x相等的元 素，返回0。

定位算法的分析:

定位运算的功能是查找出线性表l中值等于x的结点序号的最小值，当不存 在这种结点时，结果为0。

i从0开始，作为扫描顺序表时的下标： 

• 最好情况下，第1个元素就是x值，此时查找比较次数为1。 
• 最坏情况下，最后1个元素是x值，此时查找比较次数为n。 
• 故平均查找长度为（n+1）/2。

三、线性表的链式存储

结点结构：

 

 

 链表的具体存储表示为：

• 用一组任意的存储单元来存放。
• 链表中结点的逻辑次序和物理次序不一定相同，还必须存储指示其后继 结点的地址信息

=================单链表===================

 

• 单链表：所有结点通过指针链接而组成。 
• null：空指针。
• head：头指针。
• 尾指针：指向最后一个元素（尾结点）的指针。

单链表的一般图示法：由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用 箭头来表示链域中的指针

单链表各个结点在内存中的存储位置（物理位置）并不一定连续

 

 头结点：一般不存数据，利用head存放该结点地址。

单链表特点总结：

• 链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head3的链表可称为表head3。 
• 起始节点又称为首结点，无直接前驱，故在无头结点时，设头指针head指向首结点。
• 终端结点又称尾结点，无直接后继，故终端结点的指针域为空，即null。 
• 除头结点之外的结点为表结点，为运算操作方便，头结点中不存数据。