2.2 何时选用顺序表、何时选用链表作为线性表的存储结构.ppt

数据结构数据结构数据结构 C C语言版语言版内容? 线性表的定义? 基于抽象数据类型线性表的操作? 线性表的存储结构? 基于顺序存储结构的线性表操作算法? 基于链式存储的线性表操作算法? 循环链表的操作算法? 双向链表的操作算法? 顺序存储线性表与链式存储线性表的比较? 一元多项式的表示及相加第2章线性表 线性表的定义 1、名词术语·线性表--(a 1,a 2,……,a i-1,a i,a i+1,……,a n)。例如: 26英文字母表(A,B,C, ……,X,Y,Z) 、一个班级的学生成绩报表等·表长--线性表中元素的个数·直接前驱元素--线性表中 a i-1领先于 a i,则a i-1是a i的直接前驱元素·直接后继元素--线性表中 a i领先于 a i+1,则a i+1是a i的直接后继元素 2、线性表的抽象数据类型定义 ADT List{ 数据对象: D={ a i|a i∈ElemSet ,i=1,2, ……,n,n ≥0} 数据关系: R 1={< a i -1,a i>|a i -1,a i∈D,i=2, ……,n} 基本操作: InitList (&L) 操作结果:构造一个空的线性表 L。……}ADT List 基于抽象数据类型线性表的操作 1、建立一个空的线性表 2、求线性表中元素个数 3、判断线性表 L是否为空 4、取线性表 L中第 i个元素 5、在线性表中插入某元素 6、在线性表中删除某元素 7、求线性表中某元素的前驱元素 8、求线性表中某元素的后继元素 9、在线性表中查找某元素 10、两个线性表进行合并 线性表的存储结构 1、两种存储结构: 顺序存储--数组链式存储--链表 2、线性表的顺序存储结构示意图: 存储地址内存状态数据元素在线性表中的位序 b 1 b+l2 …… b+(i-1)l i …… b+(n-1)l n b+ nl空闲… b+( maxlen -1)l 类型定义: //--- 线性表的动态分配顺序存储结构--- #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct {ElemType *elem ; // 存储空间基址 int length; // 当前长度 int listsize ; // 当前分配的存储容量(以 sizeof (ElemType )为单位) }SqList ; 3、线性表的链式存储结构 L=(a1,a2, ……,an) 示意图: 注: (a)为非空表, ( b)为空表。类型定义: //--- 线性表的单链表存储结构--- typedef struct LNode { ElemType data; struct LNode * next; } LNode ,* LinkList ;