二章线表.PPT

第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 线性表的应用：一元多项式的表示及相加,线性结构是：一个数据元素的有序集。 线性结构的基本特征： 在数据元素的非空有限集合中， 1、存在唯一的一个被称做“第一个”的数据元素 2、存在唯一的一个被称做“最后一个”的数据元素 3、除第一个之外，集合中的每个数据元素均只有一个前驱 4、除最后一个之外，集合中每个数据元素均只有一个后继 例1：26个英文字母组成的字母表（A，B，C，Z）,例2：学生健康情况登记表如下：,（(王小林、 790631、男、18、健康)， (陈 红、 790632、女、20、一般)，),线性表(Linear List) ：由n(n0)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,2.1 线性表的类型定义,线性表的逻辑特征： 在非空的线性表中，有且仅有一个开始结点a1，它没 有直接前趋，而仅有一个直接后继a2；有且仅有一个终端 结点an，它没有直接后继，而仅有一个直接前趋an-1；其 余的内部结点ai(2in-1)都有且仅有一个直接前趋 a i-1和一个直接后继ai+1。 结论：线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,线性表的抽象数据类型的定义： ADT List 数据对象:D=ai |aiElemSet,i=1,2,n,n0 数据关系:R1=| ai-1,ai D,i=2,n 基本操作: InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListInsert(&L,i,e) 初始条件：线性表L已存在,1iListLength(L)+1. 操作结果：在L中第i个位置之前插入新的数据元素e。 ListDelete(&L,i,e) 初始条件：线性表L已存在且非空,1iListLength(L)+1. 操作结果：删除L的第i元素，并用e返回其值，L长度减1。 ,例2-1 利用两个线性表LA和LB分别表示两个集合A和B（即线性表中的数据元素即为集合中的成员），现要求一个新的集合A=AB。,void union(List if(!LocateElem(La，e，equal) ListInsert(la，+La_len，e) ,扩展1: 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。,void JiHeJiao(List ,例2-2 已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下： void MergeList(List La，List Lb，List while(i=La_len)&&(j=Lb_len), GetElem(La，i，ai);getElem(Lb，j，bj); if(ai=bj) ListInsert(Lc，+k，ai);+i; else ListInsert(Lc，+k，bj);+j; while(i=La_len) GetElem(La，i+，ai); ListInsert(Lc， +k，ai); while(j=Lb_len) GetElem(Lb，j+，bj); ListInsert(Lc，+k，bj); ,2.2 线性表的顺序表示和实现 2.2.1 顺序存储的线性表(Sequential Lists) 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。线性表的起始地址称作线性表的基地址。 假设线性表的每个元素需占用L个存储单元，则线性表中第i+1个数据元素的存储位置LOC( ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：,LOC(ai+1)=LOC(ai)+ L 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)* L,例：有一线性表为： (a1,a2,ai,an) 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。,b,b+L,b+(i-1)L,b+(n-1)L,b+nL,a0,a1,ai-1,an-1,线性表的顺序存储的c语言描述： # define List_Init_Size 100 typedef LISTINCREMENT 10; typedef struct ElemType *elem; int length; int listsize; Sqlist;,2.2.2 顺序表上实现的基本操作 线性表的初始化操作InitList( /InitList_Sq,问题规模是表的长度，设它的值为n。 该算法的时间主要花费在循环的结点后移语句上，移动 结点的次数是n-i+1。依赖于表的长度与插入位置。 当i=n+1时，结点后移语句将不进行； 这是最好情况，其时间复杂度O（1）； 当i=1时，需移动表中所有结点，即n次。 这是最坏情况，其时间复杂度为O（n）。,插入算法ListInsert(&L,i,e)的实现。 分析算法的复杂度：,王一,赵二,李四,张三,a0,a1,a2,a3,a4,王五,例：有一线性表为： (王一，赵二，张三，李四，王五) 现要变为： (王一，赵二，李四，王五),王一,赵二,李四,a0,a1,a2,a3,a4,王五,例：有一线性表为： (王一，赵二，张三，李四，王五) 现要变为： (王一，赵二，李四，王五),王一,赵二,李四,a0,a1,a2,a3,a4,王五,例：有一线性表为： (王一，赵二，张三，李四，王五) 现要变为： (王一，赵二，李四，王五),删除算法ListInsert(&L,i,&e)的实现。 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 若i=n，无需移动结点； 若i=1，则前移语句将循环执行n-1次。 两种情况下算法的时间复杂度分别为O(1)和O(n)。 删除算法的平均性能分析：在长度为n的线性表中删除一个结点，令Edl(n)表示所需移动结点的平均次数，pi表示删除表中第i个结点的概率。删除表中第i个结点的移动次数为n-i，故 Edl(n)= (n-i) pi,在等概率的假设下， p1=p2=p3=pn=1/n 由此可得： Edl(n)= (n-i)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结 点，平均时间复杂度也是O(n)。 小结： 1、在顺序表上插入、删除一个结点，需要移动大量元素。 2、具有随机访问的特点。,2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系 来表示结点间的逻辑关系，这一特点使我们可以随机存取表 中的任一结点，但它也使得插入和删除操作会移动大量的 结点.为避免大量结点的移动，介绍线性表的另一种存储方 式，链式存储结构，简称为链表。,2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性表的 结点，这组存储单元即可以是连续的，也可以是不连续 的，甚至是零散分布在内存中的任意位置上的。因此，链 表中结点的逻辑次序和物理次序不一定相同。为了能正确 表示结点间的逻辑关系，在存储每个结点值的同时，还必 须存储指示其后继结点的地址（或位置）信息，这个信息 称为指针或链。这两部分组成了链表中的结点结构：,其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表。 开始结点无前趋，应设头指针head指向开始结点。 终端结点无后继，终端结点的指针域为空，即NULL（图示中也可用表示)。,例1、线性表: (bat，cat，eat，fat， hat，jat，lat，mat),单链表示意图,110,130,135,160,165,170,200,205,头指针head,head,bat,cat,eat,mat ,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例如：若头指针名是head，则把链表称为表head,用C语言描述的单链表如下：,typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;,假设p为指向结点的指针变量，则它通过标准函数生成的，即 p=(LNode*)malloc(sizeof(LNode); 函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点不再需要了，又可通过标准函数 free(p)释放所指的结点空间。,注意：三个概念： 头结点的概念 头指针 首元结点,单链表的基本操作： 一、查找运算 在单链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从单链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。 因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1=i=n时，i的值是合法的。,算法的平均时间复杂度：,a,b,步骤1 ：生成一个数据域为x的结点。,p,x,s,data,next,在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。,二、单链表的插入,用C语句描述为： s = (LNode *)malloc(sizeof(LNode); s-data = x;,a,b,步骤2 ：将数据元素x插在a和b元素之间。,p,data,next,a,b,p,x,s,data,next,用C语言描述为： s-next = p-next; p-next = s;,a,b,p,data,next,即： p-next = s; s-next = p-next;,s,注意语句的顺序，如改为以下顺序，什么情况会发生？,b结点的地址？,在带头结点单链表L中第i个位置之前插入元素e：,ai-1,ai,p,j = 0,a1,L,在带头结点单链表L中第i个位置之前插入元素e：,ai-1,ai,j = 1,a1,p,L,在带头结点单链表L中第i个位置之前插入元素e：,p,j = ,ai-1,ai,a1,L,在带头结点单链表L中第i个位置之前插入元素e：,j = i-1,ai-1,ai,a1,p,L,ai-1,ai,a1,p,e,s,L,关键语句： s=(LNode *)malloc(sizeof(LNode); s-data = e; s-next = p-next; p-next = s;,插入算法： Status ListInsert(LinkList ,删除元素b：,a,b,p,c,data,next,b,三、单链表的删除,a,b,p,c,data,next,b,删除元素b：,三、单链表的删除,a,b,p,c,data,next,b,用C语言语句描述为： p-next=p-next-next;,删除元素b：,三、单链表的删除,删除元素b并释放之：,a,b,p,c,data,next,b,步骤1：将b的地址记录下来 即：q=p-next;,q,a,b,p,c,data,next,b,删除元素b并释放之：,步骤2：让p-next指向b后第一个结点 即：p-next=q-next;,q,a,b,p,c,data,next,b,删除元素b并释放之：,q,步骤3：释放b结点 即：free(q),删除结点的算法： Status ListDelete(LinkList ,小结,3、链式存储的优点：插入删除效率高,4、链式存储的缺点：访问某个数据效率低,1、在单链表上插入、删除一个结点，必须知道其前驱结点。,2、单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。,2.3.2 循环链表 循环链表：是一种头尾相接的链表。其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表：在单链表中，将终端结点的指针域NULL改为指向第一个结点，就得到了单链形式的循环链表，并简称为单循环链表。 循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,a1,an,.,head, 非空表, 空表,在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)。在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext) next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针。,2.3.3 双向链表 双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct DulNode ElemType data; 数据域 struct DulNode *prior; 指向前驱元素的指针 struct DulNode *next; 指向后继元素的指针 DulNode ,*DuLinkList;,设指针p指向某一结点，则有： (pprior)next=p =(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnext)的直接前趋指针域中。,a1,an,.,head, 非空表, 空表,双向链表,a,b,x,p,q,在p所指结点前插入值为x的结点， 应怎样修改指针？,q= (DulNode *) malloc(sizeof(DulNode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q;,a,b,p,c,双向链表中删除结点p ，应怎样修改指针？,ppriornext=pnext; pnextprior=pprior; free(p);,注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。,2.4 一元多项式的表示及相加,因此一元多项式： Pm(x)=p1xe1+ p2xe2+ .+pmxem 可用线性表： (p1,e1), (p2,e2), (pm,em) 表示,一元多项式： Pm(x)=p1xe1+ p2xe2+ .+pmxem 可用系数线性表P表示:p=(p1, p2,pm) 但对 S (x) = 1 + 3 x 1000 + 2 x 2000 这样的多项式浪费空间系数线性表( 1,0,0,3,0,0,2) 可用非零系数指数线性表: (1,0), (3,1000), (2,2000),例：求两多项式的和多项式 A (x) = 7 +3 x + 9 x 8 + 5 x 17 B (x) = 8 x + 22 x 7 9 x 8 C (x) = A (x) + B (x) = 7 + 11x +22 x 7 + 5 x 17,A=( (7,0),(3,1),(9,8),(5,17) B=( (8,1),(22,7),(-9,8) C=(7,0),(11,1), (22,7) ,(5,17),结点：,一元多项式的链式存储结构,抽象数据类型Polynomial ADT Polynomial 数据对象: D=ai|aiTermSet,i=1,2,m,m0 TermSet中的每个元素包含一个表示系数的实数和 表示指数的整数 数据关系: R1=| ai-1,ai D,且ai-1中的指数 值 ai 中的指数 值，i=2,n 基本操作: CreatPolyn(&p,m) DestroyPolyn(&p) PrintPolyn(p) PolynLength(p) AddPoly(&Pa,&pb) SubtractPolyn(&Pa,&Pb) MultiplyPolyn(&Pa,&Pb) ADT Polynomial,例： S (x) = 1 + 3 x 1000 + 2 x 2000 的单链表存储示意图,pa,和多项式链表：,AddPolyn算法(类似于两个有序表的归并，仅有一些细微差别。）,设多项式A (x) ，B (x)分别用带表头结点的单链表pa ， pb表示，和多项式仍用带表头结点的单链表pa表示。,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则：,算法示意：,最后：,