《数据结构》-线性表_第1页
《数据结构》-线性表_第2页
《数据结构》-线性表_第3页
《数据结构》-线性表_第4页
《数据结构》-线性表_第5页
已阅读5页,还剩152页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第2章 线性表,第二章 线性表,线性表:是一个最简单的线性结构 线性结构:是一个数据元素的有序(次序)集,(2)存在唯一的一个被称为“最后一个”的结点;,(3)除第一个之外,表中的每个结点均只有一个前驱结点;,(4)除最后一个之外,表中的每个结点均只有一 个后继结点。,线性结构的特点:在非空线性结构表中, (1)存在唯一的一个被称为“第一个”结点;,2.1 线性表的类型定义 线性表(linear_list) 线性表是n个数据元素的有限序列,是最常 用而且是最简单的一种数据结构。,线性表的逻辑结构定义:一个线性表是n个数据元素的有限序列,例 英文字母表(A,B,C,.Z)是一个线性表,例,数据元素,特征:元素同构元素之间存在着序偶关系。相邻数据结构灵活,长度可变,可进行访问,插入和删除等操作。实质在于它的序列性。1i=0). 2. 空表:线性表中元素n的个数为0,即 n=0. 3.数据元素的位序:在非空表中,数据元素 在表中的位置,即次序号。,抽象数据类型线性表的定义 ADT List 数据对象: 数据关系: 基本操作:结构初始化操作结构销毁操作引用型操作加工型操作 ADT List,InitList( &L ),操作结果:,构造一个空的线性表L,初始化操作,结构销毁操作,DestroyList( &L ),初始条件:操作结果:,线性表 L 已存在,销毁线性表 L,ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ),NextElem( L, cur_e, &next_e ),GetElem( L, i, &e ),LocateElem( L, e, compare( ) ),ListTraverse(L, visit( ),引用型操作:,ListEmpty( L ),初始条件:操作结果:,线性表 L 已存在。,若 L 为空表,则返回TRUE,否则FALSE。,(线性表判空),ListLength( L ),初始条件:操作结果:,线性表 L 已存在。,返回 L 中元素个数。,(求线性表的长度),PriorElem( L, cur_e, &pre_e ),初始条件:操作结果:,线性表 L 已存在。,若 cur_e 是 L 的元素,则用pre_e 返回它的前驱,否则操作失败,pre_e无定义。,(求数据元素的前驱),NextElem( L, cur_e, &next_e ),初始条件:操作结果:,线性表 L 已存在。,若 cur_e 是 L 的元素,则用next_e 返回它的后继,否则操作失败,next_e无定义。,(求数据元素的后继),GetElem( L, i, &e ),初始条件: 操作结果:,线性表 L 已存在,,用 e 返回L中第 i 个元素的值。,(求线性表中某个数据元素),且 1iLengthList(L),LocateElem( L, e, compare( ) ),初始条件:操作结果:,线性表 L 已存在,e 为给定值, compare( ) 是元素判定函数。,返回 L 中第 1 个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在,则返回值为 0。,(定位函数),ListTraverse(L, visit( ),初始条件:操作结果:,线性表 L 已存在。visit() 为某个访问函数。,依次对 L 中每个元素调用函数visit( )。一旦 visit( )失败,则操作失败。,(遍历线性表),加工型操作,ClearList( &L ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),ClearList( &L ),初始条件:操作结果:,线性表 L 已存在。,将 L 重置为空表。,(线性表置空),ListInsert( &L, i, e ),初始条件:操作结果:,线性表 L 已存在,,在 L 的第 i 个元素之前插入新的元素 e,L 的长度增1。,(插入数据元素),且 1iLengthList(L)+1,ListDelete(&L, i, &e),初始条件:操作结果:,线性表 L 已存在且非空,,删除 L 的第 i 个元素,并用 e 返回其值,L 的长度减1。,(删除数据元素),1iLengthList(L),利用上述定义的线性表类型 可以实现其它更复杂的操作,例 2-2,例 2-1,例 2-3,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即:线性表中的数据元素即为集合中的成员。 现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作:扩大线性表 LA,将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为:,1从线性表 LB 中依次察看每个数据元素;,2依值在线性表 LA 中进行查访;,3若不存在,则插入之。,GetElem(LB, I,&e)e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e)( n 表示线性表 LA 当前长度),操作步骤:,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素,则插入之,La_len = ListLength(La); / 求线性表的长度 Lb_len = ListLength(Lb);,for (i = 1; i = Lb_len; i+) ,/for, / union,void union(List &La, List Lb) ,时间复杂度分析:O(listLength(LA) listLength(LB),已知一个非纯集合 B,试构造一个纯集合 A,使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合,例 2-2,集合 B,集合 A,从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上,因此,算法的策略应该和例2-1基本相同,差别仅在于集合 A 的初始状态是“空集”,void union(List / union,GetElem(Lb, i, e); / 取Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素,则插入之,for (i = 1; i = Lb_len; i+) /for,InitList(La); / 构造(空的)线性表LA,时间复杂度分析: O(listLength2(LB),若线性表中的数据元素相互之间可以比较,并且数据元素在表中依值非递减或非递增有序排列,即 aiai-1 或 aiai-1(i = 2,3, n),则称该为有序表(Ordered List)。,试改变结构,以有序表表示集合。,例如:(2,3,3,5,6,6,6,8,12),对集合 B 而言, 值相同的数据元素必定相邻,对集合 A 而言, 数据元素依值从小至大的顺序插入,因此,数据结构改变了, 解决问题的策略也相应要改变。,void purge(List i+) /for / purge,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和 e 相同的数据元素,则插入之,时间复杂度分析: O(listLength(LB),则,归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB,求得有序表 LC 也具有同样特性。,设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且已由(a1, , ai-1)和(b1, ,bj-1)归并得 (c1, , ck-1),例 2-3,k = 1, 2, , m+n,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 &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_list,while (i = La_len) & (j = Lb_len) / La 和 Lb 均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空,InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);,i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; ,while (i = La_len) & (j = Lb_len) / La 和 Lb 均不空,while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = L.listsize) / 当前存储空间已满 newbase = (ElemType *)realloc(L.elm,(L.listsize+LISTINCREMENT)*sizeof(ElemType)If(!newbase)exit(OVERFLOW);L.elem = newbase;L.Listsize += LISTINCREMENT;,if (i L.length+1) return ERROR; / 插入位置不合法,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率为 , 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:,例如:ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,q = ,已知一个顺序表L,其中的元素递增有序排列,设计一个算法插入一个元素x后保持该顺序表仍递增有序排列。,void insert(SqList ,线性表操作 ListDelete(&L, i, &e)的实现:,首先分析:,删除元素时,线性表的逻辑结构发生什么变化?,算法:顺序表的删除,定义:线性表的删除是指将第i(1i n)个元素删除,使长度为n的线性表,变成长度为n-1的线性表,需将第i+1至第n共(n-i)个元素前移,Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK;,p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,O( ListLength(L) ),考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:,L.length-1,0,87,56,p = ,例如:ListDelete_Sq(L, 5, e),线性表操作 LocateElem_Sq(L, e, (*compare)的实现:,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 算法2.6 / 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。 / 若找到,则返回其在L中的位序,否则返回0。 int i; ElemType *p; i = 1; / i的初值为第1个元素的位序 p = L.elem; / p的初值为第1个元素的存储位置 while (i data表示p指向结点的数据域p-next表示p指向结点的指针域,单链表的插入与删除,插入 第一种情况:在链表最前端插入 newnode-next = first ; first = newnode;,(插入前) (插入后),第二种情况:在链表中间插入 newnode-next = current-next; current-next = newnode;,第三种情况:在链表末尾插入 newnode-next = current-next; current-next = newnode;,(插入前) (插入后),删除第一种情况: 删除表中第一个元素第二种情况: 删除表中或表尾元素,在单链表中删除含ai的结点,ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,删除前,删除后,头结点:在单链表的第一个结点之前附设的 一个结点。其数据域可以不存储任何信息,也可以存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。,头结点,头结点指针域为空表示线性表为空,头结点,.,(a) 不带头结点,L,.,(b) 带头结点,图2.7 单链表结构,L,an-1,a0,a0,a1,a1,an-1,单链表操作的实现(带头结点),GetElem(L, i, e) / 取第i个数据元素,ListInsert(&L, i, e) / 插入数据元素,ListDelete(&L, i, e) / 删除数据元素,CreateList(&L, n) / 生成含 n 个数据元素的链表,算法2.8 查找元素GetElem(L, i, e) :查找单链表中第i个元素,若有则把其值赋给e并返回ok;否则返回error。,p-data=ai ;,p-next-data=ai+1;,线性表的操作 GetElem(L, i, &e)在单链表中的实现:,j,1,2,3,因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i,单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表中第 j 个数据元素,因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i,令指针 p 始终指向线性表中第 j 个数据元素,Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针,以 e 返回第 i 个元素 / GetElem_L,p = L-next; j = 1; / p指向第一个结点,j为计数器,while (p / 顺指针向后查找,直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK;,时间复杂度O(n),算法2.9 单链表插入在单链表第i个位置之前插入数据元素x,s-next=p-next;,p-next=s;,2.生成一个数据域为x的节点,s为指向节点x的指针,3. 插入: s-next=p-next; p-next=s;,步骤:1.首先找到指向i-1个数据元素的指针p,算法描述:Status ListInsert_L(LinkList ,时间复杂度O(n),算法2.10 单链表删除删除单链表中的第i个数据元素,p-next=p-next-next;,步骤:首先找到指向第i-1个数据元素的指针p,2. 删除:p-next=p-next-next;,时间复杂度O(n),i-1,算法描述:ListDelete_L(LinkList ,算法2.11 动态建立单链表算法: 逆序输入n个元素的值,建立一个单链表带头节点的单链表,操作步骤:,一、建立一个“空表”;,二、输入数据元素an, 建立结点并插入;,三、输入数据元素an-1, 建立结点并插入;,an,an,an-1,四、依次类推,直至输入a1为止。,void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素,建立带头结点的单链表 / CreateList_L,L = (LinkList)malloc(sizeof(Lnode);L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList)malloc(sizeof(Lnode); scanf( / 插入,时间复杂度O(n),思考:如果是顺序建表,该如何完成?,算法2.12 有序表合并,将两个有序链表La,Lb合并为一个有序链表Lc,算法2.12 有序表合并,void MergeList_L(LinkList ,时间复杂度:O(La_len + Lb_len)空间复杂度:不需要额外的空间,单链表特点它是一种动态结构不需预先分配空间指针占用额外存储空间不能随机存取,查找速度慢,单链表与顺序表的比较:单链表的存储密度比顺序表低,它多占用了存储空间。,在单链表里进行插入、删除运算比在顺序表里容易得多。,(3) 对于顺序表,可随机访问任一个元素,而在单链表中,需要顺着链逐个进行查找,因此单链表适合于成批地、顺序地处理线性表中的元素时采用。,思考题1,有一个非递减单链表,设计一个算法删除值域重复的结点,并分析算法的时间复杂度。,void dels1(LinkList ,算法时间复杂度O(n),思考题2,有一个非有序的单链表(允许出现值域重复的结点),设计一个算法删除值域重复的结点,并分析算法的时间复杂度。,void dels2(LinkList ,算法时间复杂度O(n2),思考题3,如何建立一个有序的单链表?,作 业设一单向链表的头结点为head,链表的记录中包含整数类型的key域,试设计算法,将此链表的记录按照key递增的顺序进行就地排序。(要求上机完成并提交电子版作业),静态链表,定义一个较大的结构数组作为备用结点空间(即存储池)。当申请结点时,每个结点应含有两个域:data域和cur域。data域用来存放结点的数据信息,需注意的是,此时的cur域不再是指针而是游标指示器,游标指示器指示其后继结点在结构数组中的相对位置(即数组下标)。,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,数组,1,2,3,4,5,6,7,8,0,9,10,1,2,3,4,5,6,7,8,静态链表,cur,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,1,2,3,4,5,6,7,8,0,9,10,1,2,3,4,5,6,7,8,cur,SHI,0,0,9,插入SHI 元素,数组,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,1,2,3,4,5,6,7,8,0,9,10,1,2,3,4,5,6,8,8,cur,SHI,0,9,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,1,2,3,4,5,6,7,8,0,9,10,1,2,3,4,5,6,7,8,cur,SHI,0,9,删除 ZHENG 元素,数组,数组,静态单链表的存储结构#define MAXSIZE 1000 /链表的最大长度Typedef struct ElemType data; int cur;component,SLinkListMAXSIZE;,SLinkList S;S0.cur 指示第一个结点在数据中的位置;i= S0.cur 则Si.data 存储线性表的第一个数据元素; Si.cur 指示第二个结点在数组中的位置; 以整型游标i代替动态指针p, i= Si.cur 操作相当于 p=p-next;,如何分配和回收空间?解决这个问题的方法是将所有未被分配的结点空间以及因删除操作而回收的结点空间用游标链成一个备用静态链表。当进行插入操作时,先从备用链表上取一个分量来存放待插入的元素,然后将其插入到已用链表的相应位置。当进行删除操作时,则将被删除的结点空间链接到备用链表上以备后用。,space(0:11),space(0:11),初始化一个空的静态链表,space0.cur为头指针,指向空链表中第一个可用的结点,void initSpace_SL(SLinkList space) /将一维数组space中各分量链成一个备用链表,space0.cur为头指针,”0”表示空指针 for(i=0; i next=NULL 循环链表p-next=H,k0,k1,kn-1,.,h,图2.11 循环链表结构,h,k0,k1,kn-1,.,k0,k1,kn-1,.,h,h,带头节点的空表,带头节点的循环链表, k0,k1,k2,kn-1 ,图2.12 双链表,head,优点:既可以方便的找前驱,也可以找后继。,rear,2.3.3 双向链表,实现,typedef struct DuNode ElemType data; struct DuNode *prior; struct DuNode *next; DuNode, * DuLinkList;,void ListInsert_Dul(DuLinkList ,算法描述,算法评价:T(n)=O(n),插入,s-prior=p-prior;,s-next=p;,p-prior=s;,p-prior-next=s;,void ListDelete_Dul(DuLinkList ,删除,p-prior-next=p-next;,p-next-prior=p-prior;,算法描述,算法评价:T(n)=O(n),2.4 线性表的应用举例,Pn(x)=p0+p1x+p2x2+pnxn,可用线性表p来表示:p=(p0, p1, p2, , pn),一元多项式的表示及相加一元多项式的表示:,mnRn(x)= Pn(x)+ Qm(x),线性表相加:R=(p0+ q0, p1+ q1, pm+qm, pn),Pn(x)=p0+p1x+p2x2+pnxn,线性表表示:P=(p0, p1, p2, , pn),Qm(x)=q0+q1x+q2x2+qnxm,线性表表示: Q=(q0, q1, q2, , qm),线性表的应用:一元多项式的表示和相加,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构,也可以用单链表,解决方法:一般Pn(x)=p1xe1+p2xe2+pmxem其中0=e1e2next; q=pb-next; pre=pa; while(p!=NULL) ,else if(p-exp=q-exp) /2 a的指数等于b的指数 x=p-coef+q-coef; if(x!=0) p-coef=x; pre=p; / 两系数相加不等于0 else pre-next=p-next; free(p); / 等于0 p=pre-next; u=q; q=q-next; free(u); ,else /3 a的指数大于b的指数 u=q-next; q-next=p; pre-next=q; pre=q; q=u; if(q!=NULL) / /4 链接b重剩余的节点 pre-next=q; free(pb);,问题描述: 设有n个人围坐在一个圆桌周围,现从第s个人开始报数,数到第m的人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,如此反复直到所有的人全部出列为止。Josephus问题是:对于任意给定的n,s和m,求出按出列次序得到的n个人员的序列。 现以n=8,s=1,m=4为例,问题的求解过程如图所示。图中s1指向开始报数位置, 若初始的顺序为 n1,n2,n3,n4,n5,n6,n7,n8。则问题的解为n4,n8,n5,n2,n1,n3,n7,n6。,应用举例Josephus问题,n1,n2,n3,n4,n5,n6,n7,n8,S=1; m=4;,n4,n8,n5,n2,n1,n3,n7,n6,Josephus问题,基本步骤为:,1)首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表;,2)从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点,然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点,重复此过程,直到Josephus表中的所有元素都删除。,顺序表表示 该程序中函数josephus_seq的运行时间主要是求出应出列元素后,将它删除时,移动数组element中元素所花费的时间,每次最多移动n-i个,总计移动元素个数不超过O(n2)循环链表表示 该程序的运行时间主要有以下几部分组成: 第一部分是创建由n+1个结点组成的带头结点的Josephus循环单链表,所花费的时间为O(n)。 第二部分是找pclist循环单链表中的第s个

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论