基本数据结构与运算-1线性表.ppt

第三章基本数据结构及运算,3.1概述3.2线性表3.3栈3.4队列3.5数组3.6树与二叉树3.7图,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,能输入到计算机中并能被计算机程序处理的符号的集合。,整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,计算机管理图书问题在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9,数据元素在计算机中的表示,第三章基本数据结构及运算,3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。,对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序),数据：计算机处理的对象数据元素(DataElement)：数据的基本单位一个数据元素可由若干数据项(DataItem)组成。数据项：数据的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。,数据元素亦称结点或记录数据项亦称字段或域,数据结构可描述为Group=（D，R）,有限个数据元素的集合,有限个结点间关系的集合,数据元素间的关系：前后件关系,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面,数据结构可描述为Group=（D，R）,数组,A.线性结构（一对一）,特性：1.有且只有一个根结点2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它有且仅有一个前驱和一个后继。）例：（A,B,C,，X,Y,Z）,例：学生成绩表,1数据的逻辑结构,DS1=（D1，R1）集合表示法D1=k1，k2，k3，k4R1=（k1，k2），（k2，k3），（k3，k4）DS2=(D2,R2)D2=k1,k2,k3R2=(k1,k2),(k1,k3),例：,例：,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为Group=（D，R）,数组,B非线性结构:树形结构（一对多）,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构,识别“体”字的过程,按分支和层次组织的数据，称为：“树形结构”,树形结构结点间具有分层次的连接关系,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4),D=1,2,3R=(1,2),(2,3),(3,2),(1,3),B非线性结构:图形结构（多对多）,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(a)=Lo+（i-1)*m,A.顺序存储,每个元素所占用的存储单元个数,2、数据的存储结构,元素n,.,元素i,.,元素2,元素1,存储内容,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点：1.插入或删除操作时，需移动大量元素。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,B.链式存储,每个节点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。,1536,元素2,1400,元素1,1346,元素3,元素4,head,链式存储,1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,1.比顺序存储结构的存储密度小(每个节点都由数据域和指针愈组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。,链式存储结构特点：,链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可,插入,删除,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A顺序存储,B链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数组,例管理信息系统中的查询问题各种计算机管理信息系统中，通常相关的信息(记录)组成一个表文件,表文件是一类很重要的数据结构,文件中的记录可按顺序方式组织,顺序文件,导出的链表,为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”,3.2.1.线性表的逻辑结构3.2.2线性表的存储结构及运算3.2.3线性表的应用3.2.4作业,3.2线性表,3.2.1.线性表的逻辑结构,线性表逻辑结构n个数据元素的有限序列:(a1,a2,a3,an)n为线性表的长度(n0)，n=0的表称为空表特性：数据元素呈线性关系.所有数据元素ai在同一个线性表中须是相同的数据类型例：学生表,线性表的基本运算：(1)插入：在两个确定的元素之间插入一个新的元素；(2)删除：删除线性表中某个元素；(3)修改：按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新,3.2.2线性表的存储结构,1.顺序存储结构及插入删除运算2.链式存储结构及插入删除运算（1）单链表（2）循环链表（3）双向链表,0,1,i-1,V.elemi-1,线性表的顺序存储结构,可用C语言中的一维数组来描述.#defineLISTINITSIZE100/线性表存储空间的初始分配量typedefstructElemType*elem；/数组指针表示存储空间基址intlength；/当前长度,intlistsize/当前分配的存储容量（以sizeof（ElemType）为单位）Sqlist,C语言的库函数,测算ElemType节点需占用的字节数,元素数据类型,1.顺序存储结构及插入删除运算,StatusListInsert_sq（SqlistV，inti,ElemTypex）/在线性表V中第i个元素之前插入x，i的合法值为1iV.Length+1if（iV.length+1）returnERROR;/i值不合法if(V.lengthV.listsize)returnOVERFLOW;/无存储空间q=V.elemi-1;/下行注：插入位置后的元素依次右移for(p=V.elemV.length-1;p=q;p)(p+1)=p;q=x;/插入x+V.length;/表长加1returnOK;,.,a2,a1,0,1,i-1,i,Length-1,P,（P+1）,q,插入运算,x,删除运算,StatusListDelete_sq（SqlistV，inti,ElemTypex）if（iV.length）returnERROR;P=V.elemi-1;x=P;q=V.elem+V.length1;for(+p;plink;,作业2：对以下单链表分别执行下列各程序段,并画出结果示意图.,(2)R-data=P-data;,(3)R-data=P-link-data;,(4)P-link-link-link-data=P-data;,(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-link;,(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;,(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;,(8)T=L;T-link=P-link;free(P);,(9)S-link=L;,Linklistcreat()linklisthead,p1,p2;n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)malloc(LEN)；scanf(“%d”,while(p1-data!0)n=n+1；if(n=1)head-next=p1；elsep2-next=p1；p2=p1；p1=(structlnode*)malloc(LEN)；scanf(%d”,n=0；p1=p2=(structlnode*)mal