《数据结构第二章线性表ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第二章线性表ppt课件.ppt（78页珍藏版）》请在三一办公上搜索。
1、一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、一个带头结点的单链表类型,五、其它形式的链表,六、有序表类型,2.3 线性表的链式表示和实现,一、单链表,用一组任意的存储单元存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。为了表示每个元素ai 与其直接后继元素ai+1 之间的逻辑关系，对元素ai 来说，除了存储元素本身的信息之外，还需存储一个指针信息，它指示直接后继元素的存储位置。这两部分信息组成数据元素ai 的存储映象，称为结点。,data,next,结点,数据域 指针域,以元素(数据元素的映象) + 指针(指示后继元素存储位置) =
2、 结点 (表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表（每个结点中只包含一个指针域） 称作单链表,线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的线性链表存储结构： 存储地址 数据域 指针域 1 LI 43 7 QIAN 13 13 SUN 1 19 WANG Null 25 WU 37 31 ZHAO 7 37 ZHENG 19 43 ZHOU 25,头指针H,31,线性链表的逻辑状态,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,H,用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针来指示的，逻辑上相
3、邻的两元素其物理位置不要求紧邻。通常把链表画成用箭头相连接的结点的序列，结点之间的箭头表示链域中的指针。由此可见，单链表可由头指针唯一确定。,以线性表中第一个数据元素 a1的存储地址作为线性表的地址，称作线性表的头指针。当线性表为空时，头指针为空。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，头结点的指针域指向第一个结点的存储位置；以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,Typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *
4、LinkList;,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,ai=p -data; ai+1 =p -next -data,三、单链表操作的实现,GetElem(L, i, &e) / 取第i个数据元素,ListInsert(&L, i, e) /插入数据元素,ListDelete(&L, i, e) /删除数据元素,ClearList(&L) /重置线性表为空表,CreateList(&L, n) /生成含n个数据元素的链表,线性表的操作 GetElem(L, i, &e)在单链表中的实现:,j,1,2,3,在单链表中，任何两个元素的存储位置之间没
5、有固定的联系，然而每个元素的存储位置都包含在其直接前趋结点的信息中。在单链表中，取得第i个数据元素必须从头指针出发寻找。,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表中第 j 个数据元素。,Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以 e 返回第 i 个元素 / GetElem_L,算法时间复杂度为:,O(ListLength(L), = L-next; j = 1
6、; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK;,线性表的操作 ListInsert(&L, i, e) 在单链表中的实现：,有序对 改变为 和,因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。,Sta
7、tus ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e / LinstInsert_L,算法的时间复杂度为:,O(ListLength(L), = L; j = 0;while (p / i 大于表长或者小于1,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; /插入return OK;,s,p,C语言中的两个标准函数：malloc和free
8、 假设p和q是linklist型的变量，则执行p=(linklist)malloc(sizeof(node)的作用是：由系统生成一个node型的结点，同时将该结点的起始位置赋给指针变量p;执行free(q)的作用是由系统回收一个node型的结点，回收后的结点可以备作再次生成结点时用。 因此，单链表是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可以由系统应需求即时生成。建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。,线性表的操作 ListDelete (&L, i, &e)在链表
9、中的实现:,有序对 和 改变为 ,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q = p-next; p-next = q-next; e = q-data; free(q);,p,q,Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L,算法的时间复杂度为:,O(ListLength(L), = L; j = 0;while (p-next / 删除位置不合理,q = p-next; p-next =
10、q-next; / 删除并释放结点e = q-data; free(q);return OK;,操作 ClearList(&L) 在链表中的实现:,void ClearList( / ClearList,free(p);,算法时间复杂度：,O(ListLength(L),头结点,L,p,如何从线性表得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。,例如：逆位序输入 n 个数据元素的值，建立 带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an，建立 结点并插入；,三、输入数据元素an-1，建立 结点并插入；,an
11、,an,an-1,四、依次类推，直至输入a1为止。,void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L,算法的时间复杂度为:,O(Listlength(L),L = (LinkList) malloc (sizeof (LNode);L-next = NULL; /先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( /插入,回顾 2.1 节中三个例子的算法，看一下当线性表分别以链表
12、存储结构表示时，它们的实现算法的时间复杂度为多少？,void union(List /for / union,控制结构：基本操作：,for 循环GetElem, LocateElem 和 ListInsert,当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) ),当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) ),例2-1,算法时间复杂度,void purge(List /for / purge,控制结构：基本操作：,for 循环GetElem 和 ListInsert,当以顺序映
13、像实现抽象数据类型线性表时为: O( ListLength(Lb) ),当以链式映像实现抽象数据类型线性表时为: O( ListLength2(Lb) ),例2-2,算法时间复杂度,void MergeList(List La, List Lb, List ,控制结构：基本操作：,三个并列的while循环GetElem, ListInsert,当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)+ListLength(Lb) ),当以链式映像实现抽象数据类型线性表时为: O( ListLength 2(La)+ListLength 2(Lb) ),例2-3,算法时间复杂
14、度,用上述定义的单链表实现线性表的操作时，存在的问题：,改进链表的设置：,1单链表的表长是一个隐含的值；,1增加“表长”、“表尾指针” 和 “当前位置的指针” 三个数据域；,2在单链表的最后一个元素之后插入元素时， 需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的 “位置”概念加强。,2将基本操作中的“位序 i ”改变为“指针 p ”。,四、改进的线性链表类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position;,typedef struct / 链表类型 Link head
15、, tail; / 分别指向头结点和最后 一个结点的指针 int len; / 指示链表长度 Link current; / 指向当前被访问的结点的 / 指针，初始位置指向头结点 LinkList;,头结点,a1 ai . an ,head,current,tail,Status MakeNode( Link / 分配由 p 指向的值为e的结点，并返回OK， / 若分配失败，则返回 ERROR,void FreeNode( Link / 释放 p 所指结点,链表的基本操作:,结构初始化和销毁结构,Status InitList( LinkList / 构造一个空的线性链表 L，其头指针、 /
16、尾指针和当前指针均指向头结点，表长 / 为零。,Status DestroyList( LinkList / 销毁线性链表 L，L不再存在。,O(1),O(n),引用型操作,Status ListEmpty ( LinkList L ); /判表空,int ListLength( LinkList L ); /求表长,Status Prior( LinkList L ); /改变当前指针指向其前驱,Status Next ( LinkList L ); /改变当前指针指向其后继,ElemType GetCurElem ( LinkList L ); /返回当前指针所指数据元素,O(1),O(1
17、),O(n),O(1),O(1),Status LocatePos( LinkList L, int i ); /改变当前指针指向第i个结点,Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType); /若存在与e 满足函数compare( )判定关系的 /元素，则移动当前指针指向第1个满足条件的 /元素的前驱，并返回OK; 否则返回ERROR,Status ListTraverse(LinkList L, Status(*visit)() ); /依次对L的每个元素调用函数visit(),
18、O(n),O(n),O(n),加工型操作,Status ClearList ( LinkList /重置 L 为空表,Status SetCurElem(LinkList /更新当前指针所指数据元素,Status Append ( LinkList /在表尾结点之后链接一串结点,Status InsAfter ( LinkList /将元素 e 插入在当前指针之后,Status DelAfter ( LinkList /删除当前指针之后的结点,O(1),O(n),O(s),O(1),O(1),Status InsAfter( LinkList /否则返回ERROR。 / InsAfter,if
19、 ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;,Status DelAfter( LinkList 否则返回ERROR。 /DelAfter,if ( !(L.current ,例一Status ListInsert_L(LinkList L, int i, ElemType e) /在带头结点
20、的单链线性表L的第i个元素之前插入元素e / ListInsert_L,利用上述定义的线性链表如何完成线性表的其它操作 ？,if (!LocatePos (L, i-1) return ERROR; /i值不合法，第i-1个结点不存在if (InsAfter (L, e) return OK; /完成插入else return ERROR;,Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ， int (*compare) (ElemType,ElemType) /归并有序表 La 和 Lb ,生成新的有序表 Lc, /并在
21、归并之后销毁La 和 Lb, /compare 为指定的元素大小判定函数 / MergeList_L,例二,if ( !InitList(Lc) return ERROR; /存储空间分配失败,while (!( a=MAXC & b=MAXC) / La或Lb非空, ,LocatePos (La, 0); LocatePos (Lb, 0 ) ; /当前指针指向头结点,if ( DelAfter( La, e) a = e; / 取得La表中第一个元素a else a = MAXC; / MAXC为常量最大值if ( DelAfter( Lb, e) b = e; / 取得Lb表中第一个元素
22、b else b = MAXC; / a和b为两表中当前比较元素,DestroyList(La); DestroyList(Lb); / 销毁链表 La 和 Lbreturn OK;,if (*compare)(a, b) =0) / ab InsAfter(Lc, a); if ( DelAfter( La, e1) ) a = e1; else a = MAXC; ,else / ab InsAfter(Lc, b); if ( DelAfter( Lb, e1) ) b = e1; else b = MAXC; ,1. 双向链表,五、其它形式的链表,链表中的结点有两个指针域，其一指向直接
23、后继，另一指向直接前趋。,b,c,a,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,用C语言可描述如下：,最后一个结点的指针域的指针又指回第一个结点的链表。,a1 a2 . an,2. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,3.双向循环链表,空表,非空表,a1 a2 . an,双向链表的操作特点：,“查询
24、”和单链表相同。,“插入”和“删除”时需要同时修改两个方向上的指针。,s-next = p-next; p-next = s;s-next-prior = s; s-prior = p;,p,s,插入,删除,p-next = p-next-next;p-next-prior = p;,p,六、有序表类型,ADT Ordered_List 数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 ,集合中任意两个元素之间均可以进行比较,数据关系:R = | xi-1, xi S, xi-1 xi, i=2,3,n ,回顾例2-2的两个算法,LocateElem( L, e
25、, &q, int(*compare)(ElemType,ElemType) ) 初始条件：有序表L已存在。 操作结果：若有序表L中存在元素e，则q指示L中 第一个值为e 的元素的位置，并返回函 数值TRUE；否则q 指示第一个大于e 的元素的前驱的位置，并返回函数值 FALSE。,基本操作：, ,Compare是一个有序判定函数,( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 ),例如:,若 e = 45, 则 q 指向,若 e = 88, 则 q 指向,表示值为 88 的元素应插入在该指针所指结点之后。,void union(List / La中不存在和
26、e 相同的数据元素，则插入之 / for / union,算法时间复杂度：O(n2),void purge(List i+) / purge,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和 e 相同的数据元素，则插入之,算法时间复杂度：O(n),小结: 链式存储结构的优缺点 插入和删除运算时，无须移动表中元素的位置，只需修改有关结点的指针内容； 不能随机访问表中元素，访问时间与元素在表中的位置有关； 不需要一块
27、连续的存储空间，只要能存放一个数据元素的空闲结点就可以被利用 表的规模易扩充。,在实际应用中采用哪一种存储结构更合适？ 对这个问题不能一概而论，这涉及到不同实现方法的选择问题。一般而言，对存储结构的选择应从以下几条区别： 应有利于基本运算的实现。因为运算的具体实现以存储结构的确定为前提，存储结构在一定程度上、一定范围内决定了运算的实现是否方便、高效； 应有利于数据的特性。除了数据的逻辑性外，其他的诸如数据规模也应在选择存储结构时加以考虑； 应有利于软件环境。数据的存放方式对存储结构有不同的要求，所以应依据情况适当选择存储结构。具体而言，即应主要从存储空间、运算时间、程序设计语言三方面考虑。即,
28、 存储空间 顺序表要求预先分配存储空间，一般在程序执行之前是难以估计存储空间大小，估计过大会造成浪费，估计过小又会产生空间溢出。而链式存储结构的存储空间是动态分配，只要内存空间有空间，就可动态申请内存空间，不会产生溢出。对于存储空间的考虑也可以存储密度的大小来衡量。其中存储密度的大小定义为一个结点数据本身所占用的存储量与结点结构所占用的存储量的比值。一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链式存储结构的存储密度则小于1。, 运算时间 顺序存储结构是一种随机存取的结构，便于元素的随机访问。即表中任一元素都可在O(1)时间复杂度情况下迅速而直接地存取。而链式存储
29、结构，必须从头指针开始顺着链扫描才能取得，一般情况下其时间复杂度为O(n)，所以对于那些只进行查找运算而很少做插入和删除等的运算，宜采用顺序存储结构。但在顺序表中进行元素的插入和删除运算时，需移动大量元素，平均要移动约半数的元素。尤其是当表中每个元素的信息量较复杂时所花费的时间就更为可观。而采用链式存储结构，由于进行元素的插入或删除，只需修改指针并结合一定的查找。所以，对于那些需要经常频繁地进行元素的插入和删除运算的线性表，其存储结构应采用链式存储结构。, 程序设计语言 这主要是指依据某种高级语言是否提供指针类型或者依据实际需要决定存储结构是选用静态链表还是动态链表。 总之，线性表的顺序实现和
30、链式实现各有优缺点，是无法笼统地认定哪种优，哪种劣。只能根据实际问题的具体实现需要，对各方面的优缺点加以综合平衡来确定适宜的存储结构。,2.4 一元多项式的表示及相加,在数学上，一元n次多项式 Pn ( x)= p0 + p1 x+ p2 x2 + + pn xn由n+1个系数唯一确定，可用线性表P来表示 P =（p0 ,p1 , p2 , pn ）每一项的指数 i 隐含在其系数Pi的序号里。,假设Qm(x)是一元m次多项式,同样可用线性表Q来表示 Q =（q0 ,q1 , q2 , qm ）,设mn，则两个多项式相加的结果 Rn ( x)= Pn ( x)+ Qm(x) 可用线性表R表示 R
31、=( p0+q0 , p1+q1, p2+q2 , , pm+qm, pm+1, , pn),在通常应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如 S(x) = 1 + 3x10000 2x20000的一元稀疏多项式时，就要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应该避免的。 如果只存储非零系数项，则显然必须同时存储相应的指数。,一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n,可用一个长度为m
32、且每个元素有两个数据项（系数项和指数项）的线性表表示：（p1, e1）, (p2, e2), , (pm,em) ）,P999(x) = 7x3 - 2x12 - 8x999,例如:,可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示,在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但对于S(x)类的多项式，这种表示将大大节省空间。,对于象 (p1， e1), （p2， e2), （pm， em)的线性表，有两种存储结构：顺序存储结构和链式存储结构。在实际的应用程序中取用哪一种，则要视多项式作何种运算而定。 若只求多项式的值
33、，运算中无须修改多项式的系数和指数值，采用顺序存储结构为宜。 若求两个多项式之和，采用链式存储结构为宜。,多项式选择顺序存储结构： #define maxlen maxsize; typedef struct / 定义结点类型 float coef; / 系数域 int exp; / 指数域 elemtp; typedef struct elemtp vecmaxlen; / 定义线性表为向量 int len; / 线性表长度 sequenlist; / 类型定义,p1,e1,p2,pm,e2,em,coef exp,多项式选择链式存储结构： typedef struct node / 定义结
34、点类型 float coef; / 系数域 int exp; / 指数域 struct node *next; / 指针域 polynode; ploynode *p,*q;,ADT Polynomial 数据对象： 数据关系：,抽象数据类型一元多项式的定义如下：,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 ,R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 ,CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P
35、 ),基本操作：,操作结果：输入 m 项的系数和指数， 建立一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：销毁一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：打印输出一元多项式 P。,PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) ADT Polynomial,初始条件：一元多项式 P 已存在。操作结果：返回一元多项式 P 中的项数。,初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。,一元多项式的实现：,
36、typedef struct / 项的表示 float coef; / 系数 int expn; / 指数 term, ElemType;,typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,Status CreatPolyn ( polynomail &P, int m ) / 输入m项的系数和指数，建立表示一元多项式的有序链表P / CreatPolyn,InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素,for
37、 ( i=1; i=m; +i ) / 依次输入 m 个非零项return OK;,scanf (e.coef, e.expn);if (!LocateElem ( P, e, (*cmp)() ) / 当前链表中不存 在该指数项 if ( !InsAfter ( P, e ) ) return ERROR;,注意: 1.输入次序不限;2.指数相同的项只能输入一次。,Status AddPolyn ( polynomial while (!(a=MAXE & b=MAXE) / AddPolyn,switch (*cmp(e1, e2) case -1: / 多项式PA中当前结点的指数值小 b
38、reak; case 0: / 两者的指数值相等 e1.coef= a.coef + b.coef ; if ( a.coef != 0.0 ) InsAfter(Pc, e1); break; case 1: / 多项式PB中当前结点的指数值小 break; ,例：设An ( x)和Bm ( x)都是形如 Pn ( x)= p1 xe1+ p2 xe2 + + pm xem 的一元多项式，现求两多项式之和 Cn ( x)= An ( x)+Bm ( x) (mn),显然，应采用链式存储结构。用两个线性链表分别表示两个一元多项式，链表中的每个结点表示多项式中的一项。,两个一元多项式的运算规则：
39、 指数相同的项，对应系数相加，若和不为零，则生成和多项式的一项；指数不相同的项，则复制到和多项式中。实现方法： 设两个指针p,q分别指向两个多项式中的某一个结点，则可以比较结点的指数项， 若pexpqexp, *q结点是多项式中的一项，*q结点应插在*p结点之前，且q指针在原来的链表上后移；,-1,7,0,3,1,9,8,5,17,-1,8,1,22,7,-9,8,pa,pb,多项式表的单链存储结构,-1,7,0,11,1,5,17,22,7,pc,相加得到的和多项式,p,q,pre,polyadd(pa,pb) polynode *pa,*pb,*pc; polynode *p,*q,*pr
40、e,*r; pc=pa;p=panext; q=pbnext; pre=pa; while (p!=nil),else r=qnext; qnext=p; prenext=q; pre=q; q=r; / q结点插入在p结点之前 if (q!=nil) prenext=q; free(pb); / polyadd,本 章 小 结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及适用场合。,
