数据结构课件第二章线性表.pptVIP

线性结构包括线性表、栈、队列、串、数组和广义表。其特点是：在数据元素的非空有限集合中;第 2 章 线性表;2.1 线性表的逻辑结构;例2-3 一个学校的学生健康情况登记表如下图所示。;2.1 线性表的逻辑结构; 一个线性表（linear_list）是 n（n≥0）个具有相同属性的数据元素的有限序列，其中各元素有着依次相邻的逻辑关系。;*;2.2 线性表的顺序存储结构; (1) 定义 用一组地址连续的存储单元依次存储线性表中的各个数据元素，称为线性表的顺序存储。;1; (2) 特点 只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。顺序存储结构的特点是：逻辑上相邻的数据元素在物理存储上（在存储器中）也相邻。; (3) 线性表的顺序存储结构 可以使用一维数组来表示线性表的顺???存储结构。线性表的顺序存储结构的Ｃ语言描述如下。; (1) 算法思想;(2) 算法编写; (1) 算法思想 在一般情况下，在第 i（1≤i≤n ）个元素之前插入一个元素时，需要将 第 i 至第n（共 n-i+1）个元素向后移动一个位置。;a1;#define OK 1 #define ERROR 0 Int InsList ( SeqList *L, int i, ElemType e ) /*在顺序线性表 L 中第 i 个位置插入新的元素 e。*/ /* i 的合法值为 1≤i ≤L-last+2*/; if ( L-last=MAXSIZE-1) { printf(“表已满无法插入”); return(ERROR); }; (3) 算法分析 算法InsList的基本操作是数据元素后移操作。执行元素后移的次数是 n – i + 1。可以看到：移动元素的次数不仅和线性表的长度 n 有关，而且还与插入元素的位置 i 有关。当 i = n + 1 时，无须移动元素；当 i = 1 时，则元素后移执行 n 次。也就是说，该算法在最好的情况下时间复杂度是 O(1)，在最坏的情况下时间复杂度是 O(n)。; (1) 算法思想 在一般情况下，删除第 i 个元素时，需要将 n 至第 i+1 个（共 n-i）元素向前移动一个位置。;a1;Int DelList( SeqList *L, int i, ElemType *e ) /* 在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值 i 的合法值为 1≤i ≤L－last+1*/; L-last--; /* 表长减 1*/ return OK; } /*DelList*/; (3) 算法分析 算法DelList的基本操作是数据元素前移操作。执行元素前移的次数是 n - i。可以看到：移动元素的次数不仅和线性表的长度 n 有关，而且还与删除元素的位置 i 有关。当 i = n 时，无须移动元素；当 i = 1 时，则元素前移执行 n - 1 次。也就是说，该算法在最好的情况下时间复杂度是 O(1)，在最坏的情况下时间复杂度是 O(n)。 进一步分析算法的平均性能：算法DelList的时间复杂度为 O(n)。; 线性表顺序存储结构的最大特点就是逻辑上相邻的两个元素在物理位置上也相邻。这一特点使顺序表具有十分鲜明的优点和缺点。; (2) 顺序存储结构的缺点;*;线性表的链式存储表示; 线性表链式存储结构的特点是用一组任意的存储单元存储该线性表中的各个数据元素（存储单元可以连续，也可以不连续）。; (1) 结点 一个数据元素 ai 的存储结构由两部分信息组成，称之为结点 (node)。结点包括两个域：数据域 (data)，存储数据元素信息；指针域 (next)，存储直接后继元素地址（没有后继元素时指针为 “空” (NULL)） 。指针域中存储的信息称为指针或链。; (2) 线性表的单链表存储结构;例：线性表如下： （ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG）;*; (3) 头结点和头指针;头指针; 建立线性表的链式存储结构的过程是一个动态生成单链表的过程，即从 “空表” 的初始状态起，依次建立各元素结点，并逐个插入到单链表中。 (1) 算法思