《数据结构教程》第2章 线性表 C语言版.ppt

1、数据结构,C语言版,内 容,2.1 线性表的定义 2.2 基于抽象数据类型线性表的操作 2.3 线性表的存储结构 2.4 基于顺序存储结构的线性表操作算法 2.5 基于链式存储的线性表操作算法 2.6 循环链表的操作算法 2.7 双向链表的操作算法 2.8 顺序存储线性表与链式存储线性表的比较 2.9 一元多项式的表示及相加,第2章线性表,2.1 线性表的定义,1、名词术语 线性表-n个数据元素的有限序列. 记为(a1,a2,ai-1,ai,ai+1,，an)。例如：26英文字母表(A,B,C,X,Y,Z)、一个班级的学生成绩报表等表长-线性表中元素的个数直接前驱元素-线性表中ai-1领先于a

2、i，则ai-1是ai的直接前驱元素直接后继元素-线性表中ai领先于ai+1，则ai+1是ai的直接后继元素,2、线性表的抽象数据类型定义 ADT List数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList( /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;,3、线性表的链式存储结构L=(a1,a2,an) 示意图： 注：(a)为非空表，(b)为空表。,类型定义： /-线性表的单链表存储结构- typedef

3、struct LNode ElemType data; struct LNode *next;LNode,*LinkList;,2.4 基于顺序存储结构的线性表操作算法 1、创建一个空的线性表 Status InitList_Sq(SqList /InitList_Sq,2、插入元素算法 Status ListInsert_Sq(SqList /ListInsert_Sq,3、删除元素算法 Status ListDelete_Sq(SqList /ListDelete_Sq,4、查找元素算法 int LocateElem_Sq(Sqlist L,ElemType e,Status(*compa

4、re)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序/若找到，则返回其在L中的位序，否则返回0。i=1; /i的初值为第1个元素的位序p=L.elem; /p的初值为第1个元素的存储位置while(i=L.length /LocateElem_Sq,5、两表合并算法 void MergeList_Sq(SqList La,SqList Lb,SqList /插入Lb的剩余元素 /MergeList_Sq,2.5 基于链式存储的线性表操作算法 * 带头结点的单链表（如右：a图为非空表，b图为空表）,1、创建一个带头结点的单链表 void

5、 CreateList_L(LinkList /插入到表头,2、链表中插入结点算法 Status ListInsert_L(LinkList /ListInsert_L,3、链表中删除结点算法 Status ListDelete_L(LinkList /ListDelete_L,4、两个有序链表合并成一个有序链表 void MergeList_L(LinkList /释放Lb的头结点/MergeList_L,2.6 循环链表的操作算法 * 什么是循环链表？ 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中

6、其他结点，如下图所示为单链的循环链表。,循环链表的操作与单链表的差别,循环链表的操作与单链表基本一致，差别仅在于算法中的循环条件不是P或 Pnetx 是否为空，而是它们是否等于头指针。,2.7 双向链表的操作算法 * 什么是双向链表？,为了克服单链表单向性的缺点，可利用双向链表，在它的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。在C语言中可描述如下：,/-线性表的双向链表存储结构-typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNode, *DuLinkList;,1

7、.在双向链表中插入节点,Status ListInsert_Dul(DuLinkList /ListInsert_DuL,2.在双向链表中删除节点,Status ListDelete_Dul(DuLinkList /ListDelete_DuL,2.8 顺序存储线性表与链式存储线性表的比较,2.9 一元多项式的表示及相加,两个多项式的相加操作算法,根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。在此，和多项式链表中的结点无需另生成，而应该从两个多项式的链表中

8、摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况： 1）指针qa所指结点的指数值指针qb所指结点的指数值，则应摘取指针qa所指结点插入到和多项式链表中去；2）指针qa所指结点的指数值指针qb所指结点的指数值，则应摘取指针qb所指结点插入到和多项式链表中去；3）指针qa所指结点的指数值指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。,两个多项式的相加操作算法描述,int cmp(term a,term b);/依a的指数值)b的指数值，分别返回-1、0和+1 void AddPolyn(polynomial /释放Pb的头结点/AddPolyn,实例演示,小结,本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。,第二章 线性表习题,一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?,二、算法设计