2.1-数据的逻辑结构ppt课件

1、 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面： 散列存储散列存储索引存储索引存储串及数组串及数组Data_Structure = (D,S)2第2章 线性表n 了解线性表的特点及类型定义；n 掌握线性表的顺序表示及实现，掌握线性表的链式表示及实现单链表、双向链表和循环链表）；n 算法设计层次3）：熟练掌握两种线性表表示的创建

2、、插入、删除和查找等基本操作；链表合并与分解，有序表插入；（灵活应用，习题集2.33之前）n 了解一元多项式的表示和相加。第2章 线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个的数据元素存在唯一的一个被称作“最后一个的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继n2.1 线性表的逻辑结构n定义：一个线性表是n个数据元素的有限序列niaaaa,21如例 英文字母表A,B,C,.Z)是一个线性表例学号姓名年龄001张三18002李四19数据元素元素文件n特征：n元素个数n表长度，n=0空表n1in时nai的直接前驱

3、是ai-1，a1无直接前驱nai的直接后继是ai+1，an无直接后继n元素同构，且不能出现缺项 类C描述建空表，求长度，定位，插入等基本操作利用基本操作实现复杂操作 如线性表合并P20 例21 线性表合并 union 算法2.1 ListLength，GetElem，LocateElem，ListInsert时间复杂度 for X LocateElem 即OListLength(Lb)xListLength(La)）P21 例22 有序表合并到第三个表 MergeList 算法2.2时间复杂度 O（ ListLength(Lb)+ListLength(La) ）抽象数据类型线性表的定义P196

4、void Union(List &La, List Lb) / 算法2.1 / 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i; ElemType e; La_len = ListLength(La); / 求线性表的长度 Lb_len = ListLength(Lb); for (i=1; i=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal) / La中不存在和e相同的数据元素 ListInsert(La, +La_len, e); / 插

5、入 / union7void MergeList(List La, List Lb, List &Lc) / 算法2.2 / 已知线性表La和Lb中的元素按值非递减排列。 / 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。 InitList(Lc); i=j=1; k=0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) / La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) ListIn

6、sert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i = La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j = Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / MergeListn2.2 线性表的顺序存储结构n顺序表：n定义：用一组地址连续的存储单元存放一个线性表叫n元素地址计算方法：nLOC(ai)=LOC(a1)+(i-1)*LnLOC(ai+1)=LOC(ai)+Ln其中：nL一个

7、元素占用的存储单元个数nLOC(ai)线性表第i个元素的地址nP22 图2.2n特点：n实现逻辑上相邻物理地址相邻n实现随机存取n实现：可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1类C描述 定义结构体类型SqList#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量SqListP23 例 算法2.3 初始化操作Status InitList_Sq(SqLi

8、st &L) / 构造一个空的线性表L。 L.elem = (ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) return OK; / 存储分配失败 L.length = 0; / 空表长度为0 L.listsize = LIST_INIT_SIZE; /初始存储容量 return OK; / InitList_Sq 空闲n插入n定义：线性表的插入是指在第i1i n+1个元素之前插入一个新的数据元素x，使长度为n的线性表niiaaaaa,1,21 变成长度为n+1的线性表niiaaxaaa,1,21 需将第i至

9、第n共n-i+1)个元素后移P24 算法2.411/ 算法2.4Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*size

10、of (ElemType); if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = &(L.elemi-1); / q为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; / ListInsert_Sq内存a1a2aiai+1an01i-1V数组下标

11、n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为n删除n定义：线性表的删除是指将第i1i n个元素删除，使长度为n的线性表niiaaaaa,1,21 变成长度为n-1的线性表niiaaaaa,11,21 需将第i+1至第n共n-i)个元素前移P24 算法2.515Status ListD

12、elete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; pdata表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode *

13、)malloc(sizeof(LNode);系统回收p结点：free(p)n线性链表n定义：结点中只含一个指针域的链表叫，也叫单链表ha1a2头结点an .h空表头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空单链表的基本运算取元素：GetElem_LP29 算法 2.8时间复杂度 T(n) = O(n)Status GetElem_L(LinkList &L,int i, ElemType &e) / 算法2.8 / L为带头结点的单链表的头指针。 / 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p = L-next; j = 1; / 初始化，p指

14、向第一个结点，j为计数器 while (p & jnext; +j; if ( !p | ji ) return ERROR; / 第i个元素不存在 e = p-data; / 取第i个元素 return OK; / GetElem_L24Status ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e p = L; j = 0; while (p & j next; +j; / 寻找第i-1个结点 if (!p | j i-1) return ERROR; / i小于1或者大于表长

15、s = (LinkList)malloc(sizeof(LNode); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_Lpabxs 插入：在线性表两个数据元素a和b间插入x，已知p指向as-next=p-next;p-next=s;P30 算法 2.9时间复杂度 T(n) = O(n)Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 p = L; j = 0;

16、while (p-next & j 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_LP30 算法2.10pabc时间复杂度 T(n) = O(n)删除：单链表中删除b，设p指向ap-next=p-next-next;void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序输入n个元素的值，建立带表头结点的单链线性表

17、L L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新结点 scanf(&p-data); /输入元素值 p-next = L-next; L-next = p; / 插入到表头 / CreateList_Lh头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0 nOnT 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h

18、为头指针nCreateList_L P30 算法 2.11算法评价27合并有序链表MergeList_L P31 算法 2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 已知单链线性表La和Lb的元素按值非递减排列。 / 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 pa = La-next; pb = Lb-next; Lc = pc = La; / 用La的头结点作为Lc的头结点 while (pa & pb) if (pa-data data) pc-next = pa; pc = pa

19、; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段 free(Lb); / 释放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.

20、17图2.11 数组静态链表1 备用链表 0n循环链表(circular linked list)n循环链表是表中最后一个结点的指针指向头结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同n单链表p或p-next=NULLn循环链表p或p-next=Hhh空表尾指针 合并简化 P35 图2.13temp = B-next;B-next = A-next;A-next = temp-next;A = B;n双向链表double linked list）n单链表具有单向性的缺点n结点定义typedef struct DulNode

21、ElemType data; struct DulNode *prior,*next;DulNode, *DulLinkList;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;bcaP删除P37 算法2.19 ListDelete_DuL算法评价：T(n)=O(n)p-prior-next=p-next;p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 删除带头结点的双链循环线性表L的第i

22、个元素，i的合法值为1i表长 if (!(p = GetElemP_DuL(L, i) / 在L中确定第i个元素的位置指针p return ERROR; / p=NULL, 即第i个元素不存在 e = p-data; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; / ListDelete_DuL32DuLinkList GetElemP_DuL(DuLinkList L, int i) / L为带头结点的双向链表的头指针。 / 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR DuLinkLis

23、t p; p = L-next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p!=L & jnext; +j; if (p=L | jprior = p-prior; 2. p-prior-next = s; 3. s-next = p; 4. p-prior = s;xSbaP插入34P36 算法2.18Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) / 在带头结点的双链循环线性表L的第i个元素之前插入元素e， / i的合法值为1i表长+1。 if (!(p = GetElemP_DuL(L,

24、 i) / 在L中确定第i个元素的位置指针p return ERROR; / p=NULL, 即第i个元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode) return ERROR; s-data = e; s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; return OK; / ListInsert_DuL 算法评价：T(n)=O(n)小结：带头结点的线性链表 取消参数i 位序算法改写 算法2.20 2.21n2.4 线性表的应用举例n 一元多项式的表示及相加n一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2