数据的逻辑结构PPT学习教案

1、会计学1 数据的逻辑结构数据的逻辑结构 2 第1页/共39页 第2页/共39页 ni aaaa , ,21 如 例 英文字母表（A,B,C,.Z)是一个线性表 例 学号姓名年龄 001张三18 002李四19 数据元素 元素文件 n特征： 元素个数n表长度，n=0空表 1idata表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域 生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNode); 系统回收p结点：free(p) n线性链表 定义：结点中只含一个指针域的链表叫，也叫单链表 第20页/共39页 ha1a2 头结点 an . h

2、空表 头结点：在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空 第21页/共39页 时间复杂度 T(n) = O(n) Status GetElem_L(LinkList j = 1; / 初始化，p指向第一个结点，j为计数器 while (p +j; if ( !p | ji ) return ERROR; / 第i个元素不存在 e = p-data; / 取第i个元素 return OK; / GetElem_L 第22页/共39页 24 pab xs 插入：在线性表两个数据元素a和b间插入x， 已知p指向a s-next=p-next; p-next=s; P30 算法

3、 2.9 时间复杂度 T(n) = O(n) 第23页/共39页 Status ListDelete_L(LinkList j = 0; while (p-next +j; if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK; / ListDelete_L pabc 时间复杂度 T(n) = O(n) 删除：单链表中删除b，设p指向a p-next=p-next-next; 第24页/共39页 h 头结点 an 0

4、h 头结点 an-10an a2 .h 头结点 an-10an ha1a2 头结点 an .0 h 头结点 0 nOnT 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针 nCreateList_L P30 算法 2.11 算法评价 第25页/共39页 27 合并有序链表MergeList_L P31 算法 2.12 void MergeList_L(LinkList pb = Lb-next; Lc = pc = La; / 用La的头结点作为Lc的头结点 while (pa pc = pa; pa = pa-next; else pc-next = pb;

5、pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段 free(Lb); / 释放Lb的头结点 / MergeList_L 算法2.2 的两种实现：算法2.7 顺序，算法2.12 链接 第26页/共39页 静态链表 无指针类型语言 BASIC 大数组 用游标（指示器cur）代替指针 P32 图2.10 备用链表：未使用的分量（数组元素） P33 例2-3 (A-B)U(B-A) 算法2.14-2.17 图2.11 数组静态链表1 备用链表 0 第27页/共39页 h h 空表 尾指针 合并简化 P35 图2.13 temp = B-nex

6、t; B-next = A-next; A-next = temp- next; A = B;第28页/共39页 typedef struct DulNode ElemType data; struct DulNode *prior,*next; DulNode, *DulLinkList; priorelement next L 空双向循环链表： 非空双向循环链表： LAB bca p p-prior-next= p= p-next-proir; 第29页/共39页 bca P 删除 P37 算法2.19 ListDelete_DuL 算法评价：T(n)=O(n) p-prior-next=

7、p-next; p-next-prior=p-prior; 第30页/共39页 32 第31页/共39页 ListInsert_DuL 1. s-prior = p-prior; 2. p-prior-next = s; 3. s-next = p; 4. p-prior = s; x S ba P 插入 第32页/共39页 34 算法评价：T(n)=O(n) 小结：带头结点的线性链表 取消参数i 位序 算法改写 算法2.20 2.21 第33页/共39页 n nn xPxPxPPxP 2 210 )( ),( 210n PPPPP 可用线性表P表示 200001000 231)(xxxS但对

8、S(x)这样的多项式浪费空间 一般 em mn xPxPxPxP ee 21 21 )( 其中 为非零系数）（ i Pemee210 用数据域含两个数据项的线性表表示 emPePeP m， ，21 21 其存储结构可以用顺序存储结构，也可以用单链表 第34页/共39页 typedef struct node int coef,exp; struct node *next; JD; coefexp next 177 87 178 522117)()()( 9228)( 5937)( xxxxBxAxC xxxxB xxxxA -1 A 7 0 3 1 9 8 5 17 -1 B 8 1 22 7

9、 -9 8 -1 C 7 0 11 1 22 7 5 17 n一元多项式相加 第35页/共39页 设p,q分别指向A,B中某一结点，p,q初值是第一结点 比较 p-exp与q-exp p-exp exp: p结点是和多项式中的一项 p后移,q不动 p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动 p-exp = q-exp: 系数相加 0：从A表中删去p, 释放p,q，p,q后移 0：修改p系数域, 释放q，p,q后移 直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可 n运算规则 第36页/共39页 q -1 pa 7 0 3 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q -1 pa 7 0 3 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 ppre q -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pr e q -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q=NULL -1 pa 7 0 11 1 9 8 5 17 -1