《数据的逻辑结构》PPT课件

,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,散列存储,索引存储,串及数组,Data_Structure=(D,S),2,第2章线性表,了解线性表的特点及类型定义；掌握线性表的顺序表示及实现，掌握线性表的链式表示及实现（单链表、双向链表和循环链表）；算法设计（层次3）：熟练掌握两种线性表表示的创建、插入、删除和查找等基本操作；链表合并与分解，有序表插入；（灵活应用，习题集2.33之前）了解一元多项式的表示和相加。,第2章线性表,线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继,2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列,例英文字母表（A,B,C,.Z)是一个线性表,特征：元素个数n表长度，n=0空表1next表示p指向结点的指针域,生成一个LNode型新结点：p=(LNode*)malloc(sizeof(LNode);系统回收p结点：free(p),线性链表定义：结点中只含一个指针域的链表叫，也叫单链表,头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空,单链表的基本运算取元素：GetElem_LP29算法2.8,时间复杂度T(n)=O(n),StatusGetElem_L(LinkList/GetElem_L,24,StatusListInsert_L(LinkList/LinstInsert_L,插入：在线性表两个数据元素a和b间插入x，已知p指向a,s-next=p-next;,p-next=s;,P30算法2.9,时间复杂度T(n)=O(n),StatusListDelete_L(LinkList/ListDelete_L,P30算法2.10,时间复杂度T(n)=O(n),删除：单链表中删除b，设p指向a,p-next=p-next-next;,voidCreateList_L(LinkList/插入到表头/CreateList_L,动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针,CreateList_LP30算法2.11,算法评价,27,合并有序链表MergeList_LP31算法2.12voidMergeList_L(LinkList/释放Lb的头结点/MergeList_L算法2.2的两种实现：算法2.7顺序，算法2.12链接,单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢,静态链表无指针类型语言BASIC大数组用游标（指示器cur）代替指针P32图2.10备用链表：未使用的分量（数组元素）P33例2-3(A-B)U(B-A)算法2.14-2.17图2.11数组静态链表1备用链表0,循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p或p-next=H,尾指针合并简化P35图2.13,temp=B-next;B-next=A-next;A-next=temp-next;A=B;,双向链表（doublelinkedlist）单链表具有单向性的缺点结点定义,typedefstructDulNodeElemTypedata;structDulNode*prior,*next;DulNode,*DulLinkList;,p-prior-next=p=p-next-proir;,删除,P37算法2.19ListDelete_DuL,算法评价：T(n)=O(n),p-prior-next=p-next;,p-next-prior=p-prior;,StatusListDelete_DuL(DuLinkList/ListDelete_DuL,32,DuLinkListGetElemP_DuL(DuLinkListL,inti)/L为带头结点的双向链表的头指针。/当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORDuLinkListp;p=L-next;intj=1;/初始化，p指向第一个结点，j为计数器while(p!=L/GetElem_L,ListInsert_DuL1.s-prior=p-prior;2.p-prior-next=s;3.s-next=p;4.p-prior=s;,插入,34,P36算法2.18StatusListInsert_DuL(DuLinkList/ListInsert_DuL,算法评价：T(n)=O(n),小结：带头结点的线性链表取消参数i位序算法改写算法2.202.21,2.4线性表的应用举例一元多项式的表示及相加一元多项式的表示：,可用线性表P表示,但对S(x)这样的多项式浪费空间,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,单链表的