制作崔广才wwwcmscusteducn.ppt

《制作崔广才wwwcmscusteducn.ppt》由会员分享，可在线阅读，更多相关《制作崔广才wwwcmscusteducn.ppt（84页珍藏版）》请在三一文库上搜索。

1、制作：崔广才 ,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,线性表(Linear List) ： 由n(n0)个数据元素(结点)a1,a2,an组成的有限序列. 数据元素的个数n定义为表的长度。当n=0时称为空表 常常将非空的线性表(n0)记作：(a1,a2,ai,an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 同一个线性表中的元素必须属于同一种数据类型.,2.1 线性表的类型定义,例1、26

2、个大写英文字母组成的字母表 （A,B, Z）,例2、某校从1978年到1983年各种型号的计算机拥有量的变 化情况。 （6，17，28，50，92，188）,例3、学生健康情况登记表如下：,2.1 线性表的类型定义,例4、一副扑克的点数 （2，3，4，J，Q，K，A）,线性表的逻辑特征： 1)在非空的线性表，有且仅有一个开始结点a1，它没 有直接前趋，而仅有一个直接后继a2 2)有且仅有一个终端结点an，它没有直接后继，而仅 有一个直接前趋an-1； 3)其余的内部结点ai(2in-1)都有且仅有一个直接 前趋a i-1和一个直接后继ai+1。 线性表的逻辑结构是一种典型的线性结构。,2.1

3、线性表的类型定义,2.1 线性表的类型定义,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 /称 n 为线性表的表长; /称 n=0 时的线性表为空表。,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,/设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。,基本操作：,InitList( &L ),操作结果：,构造一个空的线性表L,DestroyList( &L ),初始条件： 操作结果：,线性表 L 已存在,销毁线性表 L,基本操作：,基本操作

4、：,ListInsert( &L, i, e ),初始条件： 操作结果：,线性表L已存在， 且 1iLengthList(L)+1,在L的第i个元素上插入新的元素e, L的长度增1。,（插入数据元素）,基本操作：,ListDelete(&L, i, &e),初始条件： 操作结果：,线性表L已存在且非空， 1iLengthList(L),删除L的第i个元素，并用e返回其值，L的长度减1。,（删除数据元素）,基本操作：,ListTraverse(L, Visit( ),（遍历线性表）,初始条件： 操作结果：,线性表L已存在。Visit() 为某个访问函数。,依次对L的每个元素调用函数Visit(

5、)。一旦visit( )失败，则操作失败。, ADT List,基本操作：,利用上述定义的线性表,可以实现其它复杂的操作,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求生成一个新的集合AAB。,例 2-1,上述问题可演绎为： 要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,void union(List /在逻辑结构上的算法实现 算法2.1,例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列， 现要求将LA和LB归并为一个新的

6、线性表LC，且LC中的元素仍按 值非递减有序排列。 如 LA=（3, 5, 8, 11） LB=（2, 6, 8, 9, 11, 15, 20） 则LC=（2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20),1初始化 LC 为空表；,2分别从 LA和LB中取得当前元素 ai 和 bj；,3若 aibj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中；,4重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；,5将 LA 表或 LB 表中剩余元素复制插入到LC 表中。,算法思想：,void mergelist (List La，List Lb，List

7、 /end while,while(i=la-len) GetElem(la，i+， ai); ListInsert(lc，+k， ai); / 插入 La 表中剩余元素 while(j=lb-len) GetElem(lb，j+， bj); ListInsert(lc，+k， bj); /end mergelist 算法2.2,一、顺序表 把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里,用这种方法存储的线性表简称顺序表。,2.2 线性表的顺序表示和实现,a1 a2 ai-1 ai an,线性表的起始地址， 称作线性表的基地址,以“存储位置相邻”表示有序对 即：LOC(ai) =

8、LOC(ai-1) + L,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) =LOC(a1) + (i-1)L,一个数据元素所占存储量,2.2 线性表的顺序表示和实现,基地址,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 typedef struct ElemType *elem; / 存储空间基址 int length; / 当前数据元素的个数(即线性表的长度) int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位) Sqlist;

9、,2.2 线性表的顺序表示和实现,二、顺序表上实现的基本操作 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist 类型的顺序表，则表中第i个元素是L.elemi-1。,2.2 线性表的顺序表示和实现,1、初始化 Status InitList_sq(SqList /end of InitList_sq,算法时间复杂度：,O(1),L.elem,L.length=0 L.listsize= LIST-INIT-SIZE,LIST-INIT-SIZE-1,0 1 2 3 4 5 6 ,2.2 线性表的顺序表示和实现,2、插入算法 线性表的插入操作是指在表的第i-1个数据元素和第i个数据

10、元素之间插入一个新的数据元素x，使长度为n的线性表.,2.2 线性表的顺序表示和实现,(a1, , ai-1, ai, , an) 改变为(a1, , ai-1, e, ai, , an), ,Status ListInsert_Sq(SqList / ListInsert_Sq,算法时间复杂度为:,O( L.length ),void *realloc(ptr, newsize)功能: 把由ptr所指向的已分配的内存大小变为由newsize所确定的新的大小. newsize值可以小于或大于原先的值,若分配成功,函数返回新分配的内存的首址,并把原先块的内容拷贝到新块中,信息不会丢失;否则,函数

11、将返回空指针.,例如：ListInsert_Sq(L, 5, 66),L:,q = / q 指示插入位置,例如：ListInsert_Sq(L, 5, 66),21 18 30 75 42 56 87,0 1 2 3 4 5 L.length-1,L:,for (p = ,例如：ListInsert_Sq(L, 5, 66),21 18 30 75 42 56,0 1 2 3 4 5 L.length-1,L:,87,for (p = ,例如：ListInsert_Sq(L, 5, 66),for (p = ,考虑移动元素的平均情况:,假设在第 i 个元素上插入的概率为 ， 则在长度为n 的线

12、性表中插入一个元素所需移动元素次数的为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的次数为：,3、删除(算法2.5),2.2 线性表的顺序表示和实现,(a1, , ai-1, ai, ai+1, , an) 改变为(a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,Status ListDelete_sq(Sqlist /end ListDelete_sq,2.2 线性表的顺序表示和实现,算法时间复杂度为:,O( ListLength(L),元素左移,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(L,

13、 5, e),考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的为：,2.2 线性表的顺序表示和实现,4、定位 (算法2.6) Status LocateElem_sq(SqList L,ElemType e) i=1; p=L.elem; while(i=L.length /end LocateElem_sq,O( ListLength(L) ),算法的时间复杂度为：,例如：顺序表（定位）,e =,38,i,1,2,3,4,1,8,50,4,0,5、顺序

14、表的合并(算法2.7) void MergeList_Sq(SqlList La,SqlList Lb,SqlList /end MergeList_Sq,算法的时间复杂度为 O(La.length+Lb.length),顺序表的优点： 1）无须为表示数据元素之间的关系而增加额外存储空间。 2）可方便地随机存取表中任一元素。 顺序表的缺点： 插入和删除时需移动大量元素。,2.2 线性表的顺序表示和实现,2.3.1 线性链表 用一组任意的存储单元来依次存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的。 为了能正确表示数据元素间的逻辑关系，在存储每个元素自身信息的同时，还必须存储

15、指示其直接后继的信息（即存储位置），这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构。 按指针域，线性链表分为单链表、循环链表和双向链表。,2.3 线性表的链式表示和实现,一、单链表 每一个结点只有一个指针域。 整个单链表可有头指针唯一确定。,2.3 线性表的链式表示和实现,例、线性表(bat，cat，eat， fat，hat，jat，lat，mat) 的单链表。,空指针,1、单链表的存储结构定义 typedef struct LNode Elemtype data; struct LNode *next; Lnode, *LinkList;,2.3 线性表的

16、链式表示和实现,为了操作方便，增设一个头结点。,注意区分头结点、头指针、首结点,2.3 线性表的链式表示和实现,考虑：为什么设置头结点？,如果没有头结点，在进行插入、删除等操作时，对首结点的操作比其它结点复杂。 如果增加头结点，则对首结点的操作与其它结点一致。,2、基本操作在单链表上的实现 （1）取元素(算法2.8)/取第i个元素,2.3 线性表的链式表示和实现,Status GetElem_L(LinkList L,int i,ElemType /end GetElem_L,算法分析 基本操作：移动元素，移动次数与i有关 最坏的时间复杂度O(n)。,2.3 线性表的链式表示和实现,2、基本操

17、作在单链表上的实现 （2）插入(算法2.9) 插入操作是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。 插入过程：1）定位；2）插入。,2.3 线性表的链式表示和实现,S-next=p-next;,P-next=s;,具体算法如下： Status ListInsert_L(LinkList /end ListInsert_L,2.3 线性表的链式表示和实现,上述算法里动态申请新结点空间时未加错误处理，可作下列 处理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can

18、 be obtained); return ERROR; 以上算法的时间复杂度均为O(n)。,算法分析 算法的时间主要耗费在查找操作上， 故时间复杂度为O(n）。,2.3 线性表的链式表示和实现,（3）删除(算法2.10) 删除操作是将表的第i个结点删去。 删除过程：1）定位；2）删除。,2.3 线性表的链式表示和实现,q=p-next; p-next=q-next;,具体算法如下： Status ListDelete_L (LinkList /end ListDelete_L,2.3 线性表的链式表示和实现,2.3 线性表的链式表示和实现,算法分析 算法的时间主要耗费在查找操作上，故最坏时间

19、复杂度为O(n）,链表上实现插入和删除运算，无须移动结点，仅需修改指针。,2、基本操作在单链表上的实现 （4）建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种 头插法建表(算法2.11) 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,2.3 线性表的链式表示和实现,void CreateList_L(LinkList /end for end CreatList_L,2.3 线性表的链式表示和实现,尾插法建表

20、 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。,2.3 线性表的链式表示和实现,void Creater(LinkList /end Creater,链表的合并(算法2.12) void MergeList(LinkList end MergeList,pa=La-next; pb=Lb-next; Lc=pc=La;,Lc,La,pc-next=pa; pc=pa; pa=pa-next;,Lc,La,pc-next=pb;pc=pb

21、;pb=pb-next;,Lc,La,Lb,Pa=,Lc,La,Lb,二、循环链表 循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表： 在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,2.3 线性表的链式表示和实现,a1,an,.,head, 非空表,2.3 线性表的链式表示和实现,head,a1,an,.,rear,(3) 仅设指针的

22、循环链表,循环链表基本操作的实现 基本操作与单链表类似 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像单链表那样判断p或 pnext是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等.,2.3.3 双链表/单链表的缺点：找不到前驱 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域pre。这样形成的链表中有两个方向不同的指针，故称为双向链表。形式描述为： typedef struct DulNode ElemType data; struc DulNode *pre，*next; DulNode *DuLin

23、kList;,2.3 线性表的链式表示和实现,空表,非空表,a1 a2 . an ,(ppre)next p (pnext)pre,p,a1 a2 . an ,e,s,4. P-pre=s;,p,1. S-pre=p-pre;,2. P-pre-next=s;,3. S-next=p;,双向链表的前插操作 (算法2.18),考虑：1和4能不能交换？ 1和2能不能交换？ 3和4能不能交换？,非空表,p,删除双向链表的第i个元素(算法2.18),1.p-pre-next=p-next;,ai,ai+1,an,ai-1,非空表,p,1.p-pre-next=p-next;,ai,ai+1,an,ai

24、-1,非空表,p,ai,ai+1,an,ai-1,1. p-pre-next=p-next;,2. p-next-pre=p-pre;,非空表,1. p-pre-next=p-next;,2. p-next-pre=p-pre;,ai+1,an,3. free(p);,ai-1,注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。,在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn),2.4 一元多项式的表示及相加,但是对于形如 P(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？,可以下列线性表表示:

25、 （p1, e1）, (p2, e2), , (pm,em) ）,2.4 一元多项式的表示及相加,一般情况下，一元稀疏多项式可写成 其中：pi 为指数ei项的非零系数 0 e1 e2 em = n,P999(x) = 7x3 - 2x12 - 8x999,例如:,可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示,2.4 一元多项式的表示及相加,ADT Polynomial 数据对象： 数据关系：,抽象数据类型一元多项式的定义如下：,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整

26、数 ,R |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 ,2.4 一元多项式的表示及相加,基本操作：,CreatPolyn ( &P, m ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。,DestroyPolyn ( &P ) 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。,PrintPolyn ( &P ) 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。,2.4 一元多项式的表示及相加,PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa,

27、 &Pb ) ADT Polynomial,初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。,初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。,一元多项式的实现：,typedef struct / 项的表示 float coef; / 系数 int expn; / 指数 term, ElemType;,typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,void CreatPolyn ( polynom

28、ail &P, int m ) / 输入m项的系数和指数，建立表示一元多项式的有序链表P / CreatPolyn,注意: 1.输入次序不限; 2.指数相同的项只能输入一次,InitList (P); h=gethead(P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素,for ( i=1; i=m; +i ) / 依次输入 m 个非零项 ,scanf (e.coef, e.expn); if (!LocateElem ( P, e, q, (*cmp)() ) if (MakeNode (s,e) InsFirst

29、( q, s );,Status AddPolyn ( polynomial ,case 0: / 两者的指数值相等 sum= a.coef + b.coef ; if ( sum!= 0.0 ) SetCurElem(qa,sum); ha=qa; else DelFirst(ha,sum);FreeNode(qa); DelFirst (hb,qb);FreeNode(qb); qb=NextPos(Pb,hb); qa=NextPos(Pa,ha); break; case 1: /多项式Pb中当前结点的指数值小 DelFirst (hb,qb);InsFirst(ha,qb); qb=

30、NextPos(Pb,hb); ha=NextPos(Pa,ha); break; /end switch /end while if(!ListEmpty(Pb) Append(Pa,qb); FreeNode(hb); / AddPolyn,本章小结,1.了解线性表的逻辑结构特性(数据元素之间存在着 线性关系)，在计算机中表示这种关系的两类不同 的存储结构是顺序存储结构和链式存储结构。用 前者表示的线性表简称为顺序表，用后者表示的 线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表 的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种 存储结构的不同特点及其适用场合。,作业,书面作业: p13: 2.5题 p14: 2.6题,2.9题 p18: 2.22题, 2.32题 上机作业: 实现一元多项式的表示及相加,