数据库第二章线性表教学ppt

数据结构,李鑫辽宁工程技术大学电信学院,2020/4/26,数据结构,2,第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序,目录,2020/4/26,数据结构,3,数据结构课程的起点：,什么是线性结构？,2020/4/26,数据结构,4,第2章线性表,2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例,2020/4/26,数据结构,5,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,an）,简言之，线性结构反映结点间的逻辑关系是的。,特点只有一个首结点和尾结点；特点除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一(1:1),2020/4/26,数据结构,6,（a1,a2,ai-1，ai,ai1，,an）,2.1线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,2020/4/26,数据结构,7,（A,B,C,D,Z）,例2分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,例1分析26个英文字母组成的英文表是什么结构。,2020/4/26,数据结构,8,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,2020/4/26,数据结构,9,课堂讨论：,线性表表各种操作算法的“通式”该如何书写？采用抽象数据类型来表示,2020/4/26,数据结构,10,线性表的抽象数据类型定义（见教材P19）,ADTList数据对象：D=ai|aiELemSet,i=1,2,n,n0数据关系：R1=|ai1,aiD,i=2,n基本操作：,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,ADTList,2020/4/26,数据结构,11,线性表的基本操作如何表示？（见教材P19）,InitList(/删除第i个元素用e返回其值，L长度减1,练习：有一个线性表L=（a,c,a,d,b）,求下列操作,ListLength(L)=,5,返回假（0）,GetELem(L,3,e)=,e=a,LocateELem(L,a)=,1,ListInsert(L,4,e)=,执行后线性表L变成（a,c,a,e,d,b）,ListDeLete(L,3)=,执行后线性表L变成（a,c,e,d,b）,2020/4/26,数据结构,13,抽象数据类型操作的典型例子,教材例2-1：求两个线性表的“并”，即：线性表LA和LB分别表示两个集合A和B，要求一个新的集合A为：LA=LAULB?,算法至少有两种：LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA中；若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。,2020/4/26,数据结构,14,归并的算法,1、从LB中取每一元素GetELem（LB，e）,2、依值在LA中查找LocateELem（LA，e,equaL()）,3、若不存在，则插入ListInsert（LA，n+1，e）,2020/4/26,数据结构,15,voidunion(Listif(!LocateELem(La，e，equaL)ListInsert(La，+La_Len，e),算法时间复杂度？,时间复杂度为：O(ListLength(La)*ListLength(Lb),例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：,voidMergeList(ListLa，ListLb，List,2020/4/26,数据结构,18,算法时间复杂度？,时间复杂度为：O(ListLength(La)*ListLength(Lb),voidMergeList(ListLa，ListLb，List,19,whiLe(i=La-Len)GetELem(La，i+，ai);ListInsert(Lc，+k，ai);whiLe(j=Lb-Len)GetELem(Lb，j+，bj);ListInsert(Lc，+k，bi);,插入La/Lb剩余元素,时间复杂度为O(ListLength(La)+ListLength(Lb),思考：时间复杂度为？,分析两者的时间复杂度,算法2.1的时间复杂度为O（ListLength（LA）*ListLength（LB）算法2.2的时间复杂度为O（ListLength（LA）+ListLength（LB）,课后练习,已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素,2020/4/26,数据结构,22,2.2线性表的顺序表示和实现,1顺序表的表示2顺序表的实现3顺序表的运算效率分析,2020/4/26,数据结构,23,1顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从V0Vn-1,2020/4/26,数据结构,24,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）,对上述公式的解释如图所示,线性表顺序存储特点：,2020/4/26,数据结构,25,地址内容元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,b+(max-1)L,LOC(ai)=LOC(a1)+L*（i-1）,线性表的顺序存储结构示意图,下标起点是1,2020/4/26,数据结构,26,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是多少？,答案：113,但此题要注意下标起点是从0开始：LOC(M3)=98+5(4-1)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,例1,2020/4/26,数据结构,27,charV30;voidbuiLd()/*字母线性表的生成，即建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;,核心语句：法1Vi=Vi-1+1;法2Vi=a+i;法3Vi=97+i;,例2,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,省略了incLude语句,2020/4/26,数据结构,28,voidmain(void)/*主函数，字母线性表的生成和输出*/n=26;/*n是表长，是数据元素的个数，而不是V的实际下标*/buiLd();dispLay();,voiddispLay()/*字母线性表的显示，即读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;,/元素后移一个位置,/插入x,/表长加1,核心语句：,2)插入,2020/4/26,数据结构,31,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,2020/4/26,数据结构,32,实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当符合条件：1in或i=1,n,删除线性表的第i个位置上的元素,for(j=i+1;j=n;j+)aj-1=aj;n-;,/元素前移一个位置,/表长减1,核心语句：,3)删除,2020/4/26,数据结构,33,删除顺序表中某个指定的元素的示意图如下：,顺序表插入和删除的完整程序请同学们自编。,2020/4/26,数据结构,34,3顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,讨论1：若在长度为n的线性表的第i位前插入一个元素，则向后移动元素的次数f(n)为:f(n)=,ni+1,时间效率分析:,2020/4/26,数据结构,35,推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移次数为n；若在a1后面插入，要后移n-1个元素，后移次数为n-1;若在an-1后面插入，要后移次数为1；若在尾结点an之后插入，则后移次数为0；,故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n),共有多少种插入形式?连头带尾有n+1种!,所有可能的元素移动次数合计：0+1+n=n(n+1)/2,2020/4/26,数据结构,36,同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2O(n),想一想：顺序表插入、删除算法的平均空间复杂度为多少？,插入效率：,删除效率：,教材P25算法2.5也是对执行效率的推导：,因为没有占用辅助空间！,含义：对于顺序表，插入、删除操作平均需要移动一半元素(n/2),O(1),即插入、删除算法的平均时间复杂度为O(n),37,讨论：,顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？采用动态分配的一维数组,38,动态数组简介,先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。,#defineLIST_INIT_SIZE100/存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量TypedefstructELemType*eLem;/表基址(用指针*eLem表示）intLength;/表长度（表中有多少个元素）intListsize;/当前分配的表尺寸（字节单位）SqList;,注：三个分量可简写为：L.eLemL.LengthL.Listsize,存储结构描述如下（见教材P22）：,39,sizeof(x)算符的意思是：计算变量x的长度(字节数),maLLoc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,StatusInitList_Sq(SqList/InitList_Sq,动态创建一个空顺序表的算法：,40,reaLLoc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。,动态顺序表的插入算法StatusListInsert_Sq(SqList/检验i值的合法性,if(L.LengthL.Listsize)/若表长超过表尺寸则要增加尺寸newbase=(ELemType*)reaLLoc(L.eLem,(L.Listsize+LISTINCREMENT)*sizeof(ELemType);,if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错L.eLem=newbase;/重置新基址L.Listsize=L.Listsize+LISTINCREMENT;/增加表尺寸,41,q=/插入e,+L.Length;/增加1个数据元素，则表长+1,returnOK;/ListInsert_Sq,动态数组的核心是reaLLoc(void*ptr,newsize)函数！,42,动态顺序表的删除算法StatusListDeLete_Sq(SqList/i值不合法，返回,p=/被删除元素的值赋给e,q=L.eLem+L.Length-1;/q是表尾的位置for(+p;p=q;p+)*(p-1)=*p;/待删元素后面的统统前移,-L.Length;/表长-1,returnOK;/ListDeLete_Sq,43,在顺序表L中查找第一个值与e满足compare（）的元素的位序,i=1；p=L.elem,WhiLe（inext=p-next;Step2：p-next=s；,p-next,s-next,思考：Step1和2能互换么？,X结点的生成方式：s=(node*)maLLoc(m);s-data=X;s-next=?,（3）单链表的插入,StatusListInsert_L(LinkListj=0;WhiLe(p/生成新节点,s-data=e;/插入L中s-next=p-next;p-next=s;returnOK;,核心算法,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q=p-next;/首先保存b的指针，靠它才能找到c；p-next=q-next;/将a、c两结点相连，淘汰b结点；free(q)；/彻底释放b结点空间,p-next,思考：省略free(q)语句行不行？,(p-next)-next,q,（4）单链表的删除,StatusListDeLete_L(LinkListj=0;whiLe(p-next+j,if(!p-next|ji-1)returnERROR;/删除位置不合理,q=p-next;p-next=q-next;e=q-data;free(q);returnOK;,/寻找第i个节点,并令p指向其前驱,删除并释放节点,查找、插入、删除比较,查找p=L-next;j=1;whiLe(p,插入p=L;j=0;WhiLe(p,删除p=L;j=0;whiLe(p-next,寻找第i-1个节点,算法的效率如何？,2.3.3链表的运算效率分析,（1）查找因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。,时间效率分析,（2）插入和删除因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。,但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是O(n)。,从表尾到表头逆向建立单链表的算法,VoidCreateList_L(LinkListi0;-i),L=(LinkList)maLLoc(sizeof(LNode);L-next=NULL;/建立带头节点的单链表,p=(LinkList)maLLoc(sizeof(LNode);/生成新节点scanf(/输入元素值,p-next=L-next;L-next=p;/插入到表头,用两种方式建立26个字母的单链表并显示,思考：如何正向建立链表,应用举例,算法要求：已知：线性表A和B，分别由单链表La和Lb存储，其中数据元素按值非递减有序排列（即已经有序）；要求：将A和B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表Lc存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后的C=（2,3,5,6,8,8,9,11，11）,例1：两个链表的归并（教材P31例）,重点是链表,链表示意图：,头结点,算法设计：,算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向La、Lb和Lc链表；比较：比较La和Lb表中结点数据的大小；插入：将La和Lb表中数据较小的结点插入新链表Lc。,请注意链表的特点，仅改变指针便可实现数据的移动,即“数据不动，指针动”,Pa、Pb用于搜索La和Lb，Pc指向新链表当前结点。归并过程示意如下：,Lc=La,Pb,Pa,Pa,Pb,算法实现：,VoidMergeList_L(LinkList/释放Lb的头结点/MergeList_L,pc-next=pa?pa:pb;/插入非空表的剩余段,whiLe(papb=pb-next,pa=La-next;pb=Lb-next;Lc=pc=La；/有头结点,见P31算法2.12,?是条件运算符（为真则取第1项，见P10条件赋值）,注：Lc用的是La的头指针,时间复杂度：与算法2.7相同,空间复杂度,思考：,1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，怎么修改？,2、重复的数据元素不需要插入，怎么修改？,编程训练建议：简单：先建立一个整型数的单链表，然后统计单链表中数据元素为0的个数。稍难：先建立一个字母单链表并输出到屏幕上，再试着插入一个字母（例如将I插入到L之后）。,循环链表(circuLarLinkedList)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p或p-next=H,双向链表（doubLeLinkedList）单链表具有单向性的缺点结点定义,typedefstructnodeELemtypeeLement;structnode*prior,*next;DuLNode,*DuLinkList;,p-prior-next=p=p-next-proir;,指针域的变化：后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p-next);前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p-prior);,删除,算法评价：T(n)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,p-prior-next=p-next,p-next-prior=p-prior;,StatusListDeLete_DuL(DuLinkListp-prior-next=p-next;p-next-prior=p-prior;free(p);returnOK;/ListDeLete_DuL,核心语句,ai-1的后继从ai(指针是p)变为x（指针是s):ai的前驱从ai-1(指针是p-prior)变为x(指针是s);,算法评价：T(n)=O(1),插入,注意：要修改双向指针！,指针域的变化：,s-next=p;p-prior-next=s;,s-prior=p-prior;p-prior=s;,StatusListInset_DuL(DuLinkListif（！（s=(DuLinkList)maLLoc(sizeof(DuLNond)）returnERROR;,s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;returnok;/ListInsert_DuL,核心语句,2.4一元多项式的表示及相加例1：一元多项式的计算(参见教材P3943),讨论：,一元多项式的数学通式？用抽象数据类型如何描述它的定义？用C语言如何描述它的定义？如何编程实现两个一元多项式相加？,但当多项式的次数很高且零系数项很多时，更适于用链表存储。,1.一元多项式的数学通式？,机内存储方式？一般用顺序存储,链式存储,或,通常设计两个数据域（系数项和指数项）和一个指针域,头结点,只存系数项（但零系数项也不能遗漏）,P2000(x)=1+3x1000+5x2000,2.如何编程实现两个一元多项式相加？,例：,运算规则：两多项式中指数相同的项对应系数相加，若和不为0,则构成多项式c(=a+b)中的一项；a和b中所有指数不相同的项均应拷贝到c中。,链表a：,链表b：,实现思路：,依次比较Pa和Pb所指结点中的指数项，依Pa-expon=、Pb-expon等情况，再决定是将两系数域的数值相加（并判其和是否为0），还是将较高指数项的结点插入到新表c中。,+,运算效率分析：,(1)系数相加0加法次数min(m,n)其中m和n分别表