《765-数据的逻辑结构.ppt》由会员分享，可在线阅读，更多相关《765-数据的逻辑结构.ppt（39页珍藏版）》请在三一文库上搜索。
1、,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,散列存储,索引存储,串及数组,Data_Structure = (D,S),2,第2章 线性表,了解线性表的特点及类型定义； 掌握线性表的顺序表示及实现，掌握线性表的链式表示及实现（单链表、双向链表和循环链表）； 算法设计（层次3）：熟练掌握两种线性表表示的创建、插入、删除和查找等基本操作；链表合并与分解，有序表插入；（灵活应用，习题集2.33之前） 了解一元多项式的表示和相加。,第2章 线性表,线性结构特点：在数据
2、元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列,例 英文字母表（A,B,C,Z)是一个线性表,特征： 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,类C描述 建空表，求长度，定位，插入等基本操作 利用基本操作实现复杂操作 如线性表合并 P20 例21 线性表合并 unio
3、n 算法2.1 ListLength，GetElem，LocateElem，ListInsert 时间复杂度 for X LocateElem 即O（ListLength(Lb)xListLength(La)） P21 例22 有序表合并到第三个表 MergeList 算法2.2 时间复杂度 O（ ListLength(Lb)+ListLength(La) ）,抽象数据类型线性表的定义P19,6,void Union(List / 插入 / union,7,void MergeList(List La, List Lb, List / MergeList,2.2 线性表的顺序存储结构 顺序表：
4、 定义：用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L一个元素占用的存储单元个数 LOC(ai)线性表第i个元素的地址 P22 图2.2 特点： 实现逻辑上相邻物理地址相邻 实现随机存取 实现：可用C语言的一维数组实现,类C描述 定义结构体类型SqList #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int l
5、istsize; /当前分配的存储容量 SqList P23 例 算法2.3 初始化操作 Status InitList_Sq(SqList / InitList_Sq,插入 定义：线性表的插入是指在第i（1i n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表,变成长度为n+1的线性表,需将第i至第n共（n-i+1)个元素后移,P24 算法2.4,11,/ 算法2.4 Status ListInsert_Sq(SqList / ListInsert_Sq,x,算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数
6、的平均次数为：,删除 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表,变成长度为n-1的线性表,需将第i+1至第n共（n-i)个元素前移,P24 算法2.5,15,Status ListDelete_Sq(SqList / ListDelete_Sq,算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间
7、需按最大空间分配，利用不充分 表容量难以扩充,2.3 线性表的链式存储结构 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,实现,typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;,
8、LNode *h,*p;,(*p)表示p所指向的结点 (*p).datap-data表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域,生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNode); 系统回收p结点：free(p),线性链表 定义：结点中只含一个指针域的链表叫，也叫单链表,头结点：在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空,单链表的基本运算 取元素：GetElem_L P29 算法 2.8,时间复杂度 T(n) = O(n),Status GetElem_L(LinkList / GetElem_L
9、,24,Status ListInsert_L(LinkList / LinstInsert_L,插入：在线性表两个数据元素a和b间插入x，已知p指向a,s-next=p-next;,p-next=s;,P30 算法 2.9,时间复杂度 T(n) = O(n),Status ListDelete_L(LinkList / ListDelete_L,P30 算法2.10,时间复杂度 T(n) = O(n),删除：单链表中删除b，设p指向a,p-next=p-next-next;,void CreateList_L(LinkList / 插入到表头 / CreateList_L,动态建立单链表算法
10、：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针,CreateList_L P30 算法 2.11,算法评价,27,合并有序链表MergeList_L P31 算法 2.12 void MergeList_L(LinkList / 释放Lb的头结点 / MergeList_L 算法2.2 的两种实现：算法2.7 顺序，算法2.12 链接,单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢,静态链表 无指针类型语言 BASIC 大数组 用游标（指示器cur）代替指针 P32 图2.10 备用链表：未使用的分量（
11、数组元素） P33 例2-3 (A-B)U(B-A) 算法2.14-2.17 图2.11 数组静态链表1 备用链表 0,循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p或p-next=H,尾指针 合并简化 P35 图2.13,temp = B-next; B-next = A-next; A-next = temp-next; A = B;,双向链表（double linked list）
12、单链表具有单向性的缺点 结点定义,typedef struct DulNode ElemType data; struct DulNode *prior,*next; DulNode, *DulLinkList;,p-prior-next= p= p-next-proir;,删除,P37 算法2.19 ListDelete_DuL,算法评价：T(n)=O(n),p-prior-next=p-next;,p-next-prior=p-prior;,Status ListDelete_DuL(DuLinkList / ListDelete_DuL,32,DuLinkList GetElemP_Du
13、L(DuLinkList L, int i) / L为带头结点的双向链表的头指针。 / 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR DuLinkList p; p = L-next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p!=L / GetElem_L,ListInsert_DuL 1. s-prior = p-prior; 2. p-prior-next = s; 3. s-next = p; 4. p-prior = s;,插入,34,P36 算法2.18 Status ListInsert_DuL(DuLinkList / Li
14、stInsert_DuL,算法评价：T(n)=O(n),小结：带头结点的线性链表 取消参数i 位序 算法改写 算法2.20 2.21,2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示：,可用线性表P表示,但对S(x)这样的多项式浪费空间,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,单链表的结点定义,typedef struct node int coef,exp; struct node *next; JD;,一元多项式相加,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则,算法描述,作业 2.3 2.5 2.8 2.13,