《【精品数据结构】线性结构.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】线性结构.ppt（94页珍藏版）》请在三一文库上搜索。
1、,在此幻灯片插入公司的徽标 从“插入”菜单 选择图片 找到徽标文件 单击“确定” 重新设置徽标大小 单击徽标内任意位置。徽标外部出现的方框是“调整控点” 使用这些重新设置对象大小 如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维持原比例。,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,数据结构,2021/10/14,2,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个主要问题,2021/1
2、0/14,3,线性结构,A , B , C , ，X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,2021/10/14,4,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,2021/10/14,5,树形结构,全校学生档案管理的组织方式,2021/10/14,6,树形结构 结点间具有分层次的连接关系,2021/10/14,7,2.5 树,2.5.1 树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构
3、关系。,现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关系等。,2021/10/14,8,介绍几个概念： 结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：M棵互不相交的树的集合。,
4、2021/10/14,9,2.5.2 二叉树 （Binary Tree）,1 、二叉树的定义及其性质 (1) 二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。,2021/10/14,10,二叉数是n(n0)个结点的有限集合。它或为空数(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组成。,特别要注意：二叉数不是树的特殊情况。,a,a,b,b,两棵不同的二叉数,2021/10/14,11,A、 二叉树的第i层
5、上至多有2 i-1（i 1）个结点。,(2) 二叉树的基本性质,第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。,2021/10/14,12,A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多含有2h-1个结点。,(2) 二叉树的基本性质,此树的深度h=4，共有24-1=15个节点。,2021/10/14,13,A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多含有2h-1个结点。 C、 若在任意一棵二叉树中，有n0个叶子结点， 有n2个度为2的结点，则：n0=n2+1,(2) 二叉树
6、的基本性质,n0=8 n2=7,2021/10/14,14,（3）满二叉树,特点：每一层上都含有最大结点数。,2021/10/14,15,（4）完全二叉树,特点：除最后一层外，每一层都取最大结点数， 最后一层结点都集中在该层最左边的若干位置。,2021/10/14,16,（5）树与二叉树的区别,A树的结点个数至少为1，而二叉树的结点个数可以为0。 B树中结点的最大度数没有限制，二叉树结点最大度数为2。 C树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。,树,二叉树,2021/10/14,17,性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。 证明：根据二叉树的特点，结论是显
7、然的。,性质2：深度为h的二叉树中至多含有2h-1个结点。 证明：深度为m的二叉树最多有m层，根据性质1，只要将第1层到第m层的最大结点数相加，就可得到整个二叉树中结点的最大值。 21-1 + 2 2-1+ 2 m-1 = 2 m-1,性质3：度为0的结点总比度为2的结点多一个。 设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点， 则二叉树中结点总数为：n=n0+n1+ n2 设所有进入分支的总数为m,则总的结点个数为：n=m+1 总的射出分支与总的进入分支数相等：m= n1+2 n2 因此： n0+n1+ n2 = n1+2 n2 +1 所以： n0= n2+1,2021/1
8、0/14,18,（5）树与二叉树的区别,A 树的结点个数至少为1，而二叉树的结点个数可以为0。 B树中结点的最大度数没有限制，二叉树结点最大度数为2。 C树的结点子树无左、右之分，二叉树的结点子树有明确的左、 右之分。,二叉树,树,2021/10/14,19,2、二叉树的存储结构,(2) 链式存储结构,T16,若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。,(1) 顺序存储结构,(1) 顺序存储结构,2h-1=,24-1 = 15,用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。,一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费
9、。,2021/10/14,20,(2) 链式存储结构,图为一般二叉树的二叉链表结构,每个结点由数据域、左指针域和右指针域组成。,2021/10/14,21,链式存储结构的描述： Typedef struct BiTNode int data; Struct BiTNode *lchild, *rchild; BiTNode, * BiTree;,2021/10/14,22,3、将树和森林转换为二叉树 由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。 这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。 （1）树转换为二叉树 方法： 对每个孩子进行从左
10、到右的排序； 在兄弟之间加一条连线； 对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 以根结点为轴心，将整个树顺时针转45度。,2021/10/14,23,树转换为二叉树,2021/10/14,24,（2） 森林转换为二叉树,方法： 将各棵树分别转成二叉树； 把每棵树的根结点用线连起来； 以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。,2021/10/14,25,4、 二叉树的遍历 查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 （1）遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。 按先左后右的原则，一般使用三种遍历： 先序
11、遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。,2021/10/14,26,（2）遍历算法,先序遍历：D L R 中序遍历：L D R 后序遍历：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,2021/10/14,27,Void PreOderTraverse(BiTree T) if(T! =
12、NULL) printf (T-data); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); /*先序遍历*/,返回,返回,返回,返回,A,C,B,D,返回,2021/10/14,28,中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) if(T!=NULL) inOrderTraverse(T-lchild); printf(T-data); inOrderTraverse(T-rchild); ,后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T)
13、 if(T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(T-data); ,2021/10/14,29,（3）遍历二叉树的应用 1) 建立一棵二叉树 (在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构）,BiTree CreatBiTree() BiTree T; scanf(,A B D C,A B D C ,按先序遍历,2021/10/14,30,返回,返回,返回,返回,返回,2021/10/14,31,（2）统计二叉树中叶子结点的个数 方法：对二叉树进行遍历，判断被访问的结点是否叶
14、子结点，若是叶子结点，则将计数器加1。,实现算法： int countleaf(BiTree) int n1,n2; if (T= =NULL) return(0); else if (T-lchild= =NULL) ,2021/10/14,32,void change(NODE *T) NODE *m; if(T!=NULL) m=T-L T-L=T-R; T-R=m; change(T-L); change(T-R); ,typedef struct node int data； struct node *L，*R； NODE；,A,C,B,D,A,C,B,D,21.试以二叉链表作为存储
15、结构，将二叉树中所有结点的左右子树进行交换。,2021/10/14,33,阅读程序并回答问题： （1） 程序执行了什么功能？ （2） 针对右面的图，写出程序的运行结果。 typedef struct BiTNode int data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; int preprn(BiTtree T) if(T-lchild!=NULL) ,a,b,d,e,c,g,f,h,i,a b c g,2021/10/14,34,作业：,设Pa、Pb分别为两个按升序排列的单链表的头指针，设计一个算法把这两个单链表合并为一个按升序排
16、列的单链表C。,2021/10/14,35,合并的算法是：从两表的第一个节点开始顺链逐个将对应数据元素进行比较，复制小者并插入C表尾。,Pa,Pb,C,当两表中之一已到表尾，则复制另一个链表的剩余部分，插到C表尾。,2021/10/14,36,为了减少程序中的判断，C表增设一个表头节点，合并表运算结束后再把它删除。 函数值返回指向C表的表头。 设Pa、Pb分别指向两表当前搜索节点，p指向C表的当前表尾节点。,2021/10/14,37,定义单链表中结点类型：,Typedef struct node int data； struct node *link；JD；,#define NULL 0,2
17、021/10/14,38,合并算法程序如下：,JD * comlink(JD *pa,JD *pb) JD *p,*q,*pc; pc=(JD*)malloc(sizeof(JD);,pc,p=pc;,While(pa!=NULL ,if (pb-data data),q-data = pb-data;,p,q,Pa,Pb,2021/10/14,39,合并算法如下：,JD * comlink(JD *pa,JD *pb) JD *p,*q,*pc; pc=(JD*)malloc(sizeof(JD);,pc,p=pc;,While(pa!=NULL ,if (pb-data data),q-d
18、ata = pb-data;,p,q,Pa,Pb,2021/10/14,40,合并算法如下：,JD * comlink(JD *pa,JD *pb) JD *p,*q,*pc; pc=(JD*)malloc(sizeof(JD);,pc,p=pc;,While(pa!=NULL ,if (pb-data data),q-data = pb-data;,p,q,pb=pb-link;,Pa,Pb,2021/10/14,41,合并算法如下：,JD * comlink(JD *pa,JD *pb) JD *p,*q,*pc; pc=(JD*)malloc(sizeof(JD);,pc,p=pc;,W
19、hile(pa!=NULL ,if (pb-data data),q-data = pb-data;,p,q,pb=pb-link;,Pa,Pb,2021/10/14,42,pc,Else q-data = pa-data;,pa=pa-link;,p,q,Pa,Pb,2021/10/14,43,pc,Else q-data = pa-data;,pa=pa-link;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,2021/10/14,44,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (
20、pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,2021/10/14,45,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,46,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,47,pc,Else q-dat
21、a = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,48,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,49,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link
22、;,p,q,Pa,Pb,p=q; ,2021/10/14,50,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,51,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,52,pc,Else q-data = pa-data;,pa=pa-link;,
23、p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,53,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,54,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10
24、/14,55,pc,Else q-data = pa-data;,pa=pa-link;,p-link=q;,if (pa-data= =pb-data),pb = pb-link;,p,q,Pa,Pb,p=q; ,2021/10/14,56,While (pa!=nNULL)/*如果pa链表还未到表尾，复制剩余部分*/ q=(JD *)malloc(sizeof(JD); q-data = pa-data; pa=pa-link; p-link=q; p=q; ,2021/10/14,57,While (pb!=nNULL)/*如果pb链表还未到表尾，复制剩余部分*/ q=(JD *)mal
25、loc(sizeof(JD); q-data = pb-data; pb=pb-link; p-link=q; p=q; ,2021/10/14,58,pc,p-link=NULL;,p,q,2021/10/14,59,pc,p-link=NULL;,p=pc;,p,q,2021/10/14,60,pc,p-link=NULL;,p=pc;,pc=p-link;,p,q,2021/10/14,61,pc,p-link=NULL;,p=pc;,pc=p-link;,free(p);,p,q,2021/10/14,62,pc,p-link=NULL;,p=pc;,return(pc); ,pc=p
26、-link;,free(p);,q,2021/10/14,63,合并算法程序如下：,JD * comlink(JD *pa,JD *pb) JD *p，*q，*pc； pc=(JD*)malloc(sizeof(JD)；,p=pc；,While(pa!=NULL q-data = pa-data; pa=pa-link; p-link=q; p=q; ,2021/10/14,65,While (pb!=nNULL)/*如果pb链表还未到表尾，复制剩余部分*/ q=(JD *)malloc(sizeof(JD); q-data = pb-data; pb=pb-link; p-link=q; p
27、=q; ,2021/10/14,66,p-link=NULL;,p=pc;,return(pc); ,pc=p-link;,free(p);,2021/10/14,67,下面介绍链表的创建。,2021/10/14,68,Linklist creat() linklist head,p1,p2; n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； sc
28、anf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct
29、lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next
30、=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n=1) head
31、-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-dat
32、a!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)
33、； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=
34、(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(L
35、EN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；
36、p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p
37、1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=
38、n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf
39、(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct
40、 lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”, n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”, while(p1-data!0) n=n+1； if(n= =1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”,&p1-data)；p2-next=NULL； return(head)；,Head,n=3,重新播放单击此处,2021/10/14,94,上机作业3： 在顺序存储线性表和链式存储线性表中，在指定元素后插入指定元素。,