《数据结构 第二章.ppt》由会员分享，可在线阅读，更多相关《数据结构 第二章.ppt（58页珍藏版）》请在三一文库上搜索。
1、第2章 线性表,学习目的与要求：,1了解线性表的逻辑结构；,2掌握顺序存储结构和链式存储结构的描述方法；,3掌握线性表在顺序存储结构和链式存储结构上实现的基本操作：查找、插入和删除的算法；,4能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；,5理解静态链表的定义及使用方法，并区分与单链表的不同。,基本内容,一、线性表的定义 二、线性表的顺序表示与实现 三、线性表的链式表示与实现 四、一元多项式的表示及相加 五、本章小结,线性结构的特点：在数据元素的非空有限集中 （1）存在惟一的一个被称作“第一个”的数据元素； （2）存在惟一的一个被称作“最后一个”的数据元素； （
2、3）除第一个之外，集合中的每个数据元素均只有一个直接前驱； （4）除最后一个之外，集合中的每个数据元素均只有一个直接后继。,一、线性表的定义,1. 线性表的定义,线性表是最简单、最常用的一种数据结构。线性表是n(n0)个具有相同特性的数据元素的有限序列。,根据它们之间的关系可以排成一个线性序列，记作： (a1，a2，an) 这里的ai(1in)属于同一数据对象，n代表线性表的表长，即线性表中数据元素的个数。当n=0时，线性表为空表。 对于ai，当1in 时，它有一个直接前驱ai-1；当1in 时，它有一个直接后继ai+1。,2. 抽象数据类型线性表的定义,ADT List 数据对象：D=ai
3、| aiElemSet，i=1，2， ，n， n0 数据关系： R= | ai-1, ai D, i=1, 2, , n 基本操作： InitList( /存储空间基址 int length; /当前长度 int listsize; /当前分配存储容量 SqList;,线性表顺序存储类型定义,（1）初始化线性表,void InitList_Sq(SqList /初始存储容量 /InitList_Sq,（2）插入：在线性表的第i个元素前插入一个元素,分析：若要在线性表的第i个元素前插入一个元素，除非i=n+1，否则，须将第n至第i（共n-i+1）个元素依次往后移动一个位置，如下图所示,表的长度增
4、加1,顺序表的插入 void ListInsert_Sq(SqList /插入e +L.1ength； /表长增1 ListInsert_Sq,（3）删除：删除线性表中的第i个元素,分析：若要删除线性表中的第i个元素，除非i=n，否则，须将第i+1至第n（共n-i）个元素依次往前移动一个位置，如下图所示,表的长度减少1,顺序表的删除 void ListDelete_Sq(SqList -L.1ength； /表长减1 / ListDelete_Sq,插入/删除操作时间复杂度分析,基本操作：移动元素操作,顺序表进行插入及删除操作的时间复杂度为O(n)。,插入操作移动元素次数的期望值,删除操作移动
5、元素次数的期望值,等概率情况下( , ),（4）两个顺序表的合并,假设利用两个线性表LA和LB分别表示两个集合A和B(即：线性表中的数据元素即为集合中的成员)，现要求一个新的集合A=AUB。,void Union(SqList struct LNode *next; LNode, *LinkList;,查找：在以L为头结点的单链表中查找值为e的结点。,分析：由于单链表的结点的地址都在其前驱的指针域中，因此，要查找值为e的结点，就必须从头指针出发寻找，因此，单链表是非随机存取的存储结构，算法描述如下：,LinkList GetElem_L(LinkList L，ElemType e) /在带头结
6、点的单链表L中，查找值为e的元素 p=L-next； while( p p-next = s;,算法描述如下： void ListInsert_L(LinkList p-next=q-next; free(q);,算法描述如下： void ListDelete_L(LinkList while(p-next pre = p;,用尾插法建立链表的算法描述如下：,void CreateList_L(LinkList for(i = 0；i data)； /输入元素值 pre-next = p； pre = p； /插入 pre-next = NULL； /修改尾指针 ,算法的时间复杂度为O(n),
7、用头插法建立链表,分析，尾插法使得每次插入的元素都是最后一个结点，而头插法恰恰相反，每次插入的元素都是首元结点，而且这个链表带有头结点。,p -next = L-next; L-next = p;,. . .,用头插法建立链表的算法描述如下：,void CreateList_L(LinkList B-next=A-next; A-next=HB-next; free(HB); A=B; 时间复杂度是：O(1),4、双向链表,原因：单链表具有单向性，寻查结点的直接前趋执行时间较长,在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱，双向链表的结构定义如下： typedef str
8、uct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;,双向链表示例,设d为DuLinkList型变量，则显然有： d-next-prior=d-prior-next=d,在双向链表中，有些操作，如ListLength，GetElem等涉及一个方向的指针的操作与线性链表一致, 但插入、删除则有很大不同, 需要同时修改两个方向上的指针，如下图所示：,在双链循环线性表L中第i个位置之前插入元素,int ListInsert_DuL(DuLinkList &L，int
9、i，ElemType e) / 在带头结点的双链循环线性表L中第i个位置之前插入元素e if (!(p=GetElemP_DuL(L，i) / 在L中确定第i个元素的位置指针p return 0； /p=NUlL，即第i个元素不存在 if (!(s=(DuLinkList)malloc(sizeof(DuLNode) return 0； s-data=e； s-prior=p-prior； p-prior-next=s； s-next=p； p-prior=s； return 1； / ListInsert_DuL,删除双链循环线性表L中第i个位置的元素,int ListDelete_DuL(
10、DuLinkList / ListDelete_DuL,四、一元多项式的表示及相加,一个一元多项式，Pn(x)可按升幂写成： 它由n+1个系数唯一确定，在计算机里，它可用一个线性表P来表示： 则两个多项式相加的结果（设mn） 可用线性表R表示：,对于形如 的多项式 ，在存储系数的同时存储相应的指数。一般情况下的一元n次多项式可写成： 对应的线性表表示为：,一元多项式也可以有两种存储表示方法：顺序存储和链式存储 适用范围： 顺序存储：只对多项式进行“求值”等不改变多项式的系数和指数的运算 链式存储：对多项式“求和”等改变多项式的系数和指数的运算,一元多项式的链式存储结构的定义如下： typede
11、f struct PNode float coef； / 系数 int expn； / 指数 struct PNode *next； PNode, *PolyType；,例：利用线性链表的基本操作来实现一元多项式的加法运算,分析：假设一元多项式为 和 ，每个结点表示多项式中的一项，则多项式A和B的链式存储结构如图所示：,运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况： （1）qa-expexp：取qa指针所指结点插入到“和多项式”链表中去； （2）qa-exp=qb-exp：系数相加： x=qa-coef+qb-co
12、ef x0：修改qa所指结点的系数值，同时释放qb所指结点； x=0：从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点； （3）qa-expqb-exp：取qb指针所指结点插入到“和多项式”链表中去。,void Add_Poly(PolyType A，PolyType B，PolyType &C) / 对用链式存储结构存储的两个一元多项式A和B进行相加运算，结果放在C中 qa=A-next； qb=B-next；/ qa和qb分别指向A和B多项式链表中的第一个结点 C=pre=A； / pre指向qa的前驱；C指向多项式C的头结点 while (qa & qb ) if (qa-e
13、xpexp) pre=qa；qa=qa-next； / qa指针后移 else if (qa-exp= =qb-exp) x=qa-coef+qb-coef； if (x) qa-coef=x；pre=qa； else pre-next=qa-next；free(qa)； / 删除qa qa=pre-next；u=qb；qb=qb-next；free(u)； else u=qb-next； qb-next=qa； pre-next=qb； pre=qb； qb=u； / qb插入在qa之前 if (qb) pre-next=qb； / 连接B多项式的剩余部分 free(B)； / 释放B多项式的头结点 / Add_Poly,五、本章小结,线性表的定义及抽象数据类型的定义；,线性表的顺序表示与实现，线性表的顺序存储结构又称作随机存储的存储结构，用顺序存储结构表示的线性表又称作顺序表；,线性表的链式表示与实现，线性表的链式存储结构又称作非随机存储的存储结构，链表有单链表、循环链表和多重链表；,线性表的应用：一元多项式的表示及运算。,