数据结构DS_chap02.ppt

第2章 线性表 主要内容 重点与难点 线性结构的特点 2.1 线性表的逻辑结构 线性表的定义 线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列:（a1,a2,a3,……an） 数据元素可以是一个数、一个符号、也可以是一幅图、一页书等。 数据元素也可由若干个数据项组成,这时常把数据元素称为记录,含有大量记录的线性表又称文件。 在数据元素的非空有限集中线性表中的数据元素类型多种多样； 同一线性表中的元素必定具有相同特性，即属同一数据对象； 相邻数据元素之间存在着序偶关系：ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.2 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.3 线性表的链式表示和实现 2.2 线性表的链式表示和实现 顺序表和链表的比较 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.4 一元多项式的表示和相加 2.6 作业 Data Structure 线性链表的特点 该线性表中的数据元素可用任意的存储单元来存储。线性表中逻辑相邻两元素的存储空间可以是不连续的。 除存储本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象，称为结点。(D,R) C语言中的链表即采用非顺序存储方式 用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示。 线性链表的分类： 从实现角度看，链表可分为：动态链表、静态链表； 从链接方式的角度看，链表可分为：单向链表、单向循环链表、双向链表、双向循环链表。 线性单向链表的存储实现： #define LIST_INIT_SIZE 100 struct LNODE { ElemType data; struct LNODE *next; }; typedef struct LNODE LNode; typedef struct LNODE * LinkList;  注意： 区别指针变量、结点变量 区别头指针、头结点（不带头结点链表、带头结点链表） 内存分配： p=(LNode *)malloc(sizeof(LNode)); 内存释放： free(p)； 初始化操作InitList(L) Status Init_L(LinkList L){ if (L=(LinkList *)malloc(sizeof(LNode))) { L-next=NULL； return 1; } else return 0; //分配失败 } 取某序号元素操作GetElem(L,i,e) Status GetElem_L(LinkList L,int i,ElemType e){ p=L-next,j=1; while (pji) { p=p-next; ++j; } if (!p||ji) return ERROR; e=p-data; return OK; }//GetElem_L 插入操作ListInsert(L,i,e) 插入操作ListInser