计算机软件工程基础课件,高等教育出版社,第三版.ppt

1 常用数据结构及其运算常用数据结构及其运算 第三章第三章 2 3.1 3.1 概述概述 3.2 3.2 线性表线性表 3.3 3.3 栈与队栈与队 3.4 3.4 树与二叉树树与二叉树 3.53.5 图图 3.6 3.6 查找与排序查找与排序 目录目录 3 3.1 概 述 3.1.1 数据结构的概念 3.1.2 数据的逻辑结构和物理结构 3.1.3 算法与算法分析 3.1.4 算法分析技术初步 3.1.5 小结 4 3.1.1 数据结构的概念 1. 数值型与非数值型数据 数值型：整型、实型、布尔型等 非数值型：文献检索、金融管理、商业系统 等数据处理 2. 数据结构 研究非数值运算的程序设计问题。 数据结构就是相互之间存在一种或多种特定 关系的数据元素的集合。 如线性关系、层次关系、网状关系等。 5 数据(data)是信息的载体，指所有能输入到计 算机中并被计算机程序处理的符号的总称。如 数、字符、符号等的集合。分为数值型和非数 值型数据两类。 数据元素(data element)是数据的基本单位。 如数据集合N= 1，2，3，4，5 中整数1至5 均为数据元素。 数据元素不一定是单个的数字或字符，也可 能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。 3. 基本概念和术语 3.1.1 数据结构的概念 6 数据类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分， 如整型、实型、字符型等 结构类型：变量值可分，如数组、结构体等 数据对象(data object)性质相同的数据元素的 集合。如大写字母字符的数据对象是集合： C= A，B，.，Z 。 3.1.1 数据结构的概念 7 数据结构(data structure)是指同一数据对象中各 数据元素间存在的关系。 数据结构与算法 程序算法数据结构 算法指解决特定问题的有限运算序列 3.1.1 数据结构的概念 8 1.逻辑结构：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。 二元组 S =（D，R） D数据元素的非空有限集合 RD上关系的非空有限集合。 3.1.2 数据的逻辑结构和物理结构 9 四类基本结构 ： 线性结构（一对一） 通迅录、成绩单、花名册 树形结构（一对多） 电子字典、家谱、目录 图形结构（多对多） 交通线路、通信网络 举举 例例 集合 3.1.2 数据的逻辑结构和物理结构 10 例1：linearity = (D, R)，其中 D 1,2,3,4,5,6,7,8,9,10 R = r r = , , , , , , , , 例2：Tree= (D, R)，其中 D 1,2,3,4,5,6,7,8,9,10 R = r r = , , , , , , , , 3.1.2 数据的逻辑结构和物理结构 11 例4：S = (D, R)，其中 D 1,2,3,4,5,6 R = r1, r2 r 1= , , , , r2=, 例3：Graph= (D, R)，其中 D 1,2,3,4,5; R = r r = , , , , 3.1.2 数据的逻辑结构和物理结构 12 2.物理结构(存储结构)：是逻辑结构在计算 机中的映象，即具体实现。 四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构 3.逻辑结构与存储结构的关系 算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。 同一种逻辑结构可采用不同的存储结构。 3.1.2 数据的逻辑结构和物理结构 13 一、什么是算法 算法是对特定问题求解步骤的一种描述，是指 令的有限序列，其中每条指令表示一个或多个 操作。 算法的五个特征：有穷性、确定性、可行性、 输入、输出 算法描述：采用类C语言的形式，有时也用自然 语言。注释部分用/或/*.*/表示。 3.1.3 算法与算法分析 14 二、算法设计的要求：正确性、健壮性、效率与低存储 三、算法评价标准：时间复杂度、空间复杂度 一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在时间和空间两方面的消耗多少 作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算 着重介绍第二种第二种方法。（算法、问题规模、语言、机器代码质 量、机器执行指令的速度） 3.1.3 算法与算法分析 15 一、时间复杂度 1. 频度：指一条语句重复执行的次数。记作 ：F(n) 2. 算法的时间度量：T(n)=O(F(n) 是问题规模 n 的某个函数F(n),称为算法 的渐进时间复杂度或时间复杂度。 例：T(n)=3n2 + 2n, 则 T(n)=O(n2) T(n)=3n + 2n,则 T(n)=O(3n) 3.1.4 算法与分析技术初步 16 “+x”的语句频度及三段程序的时间复杂度： (a) (b) (c) F(n): 1 n n2 T(n): O(1) O(n) O(n2) 例: (a) +x;s=0 (b) for (i=1;i外层逐层分析 3.1.4 算法与分析技术初步 25 5) 过程调用语句： a.非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。 b.递归调用：可先对递归过程设一特定的运行时间 函数T(n)，根据过程递归调用的情况，得到T(n) 的一个递推关系。 6) go to 语句：可以最坏情况进行计算，即在遇到向 下转移的go to 语句时，可认为go to 语句所引起 的控制转移根本没有发生；当遇到向上转移的go to 语句时，则必须考虑它对程序运行时间的影响。 3.1.4 算法与分析技术初步 26 4. 时间复杂度计算举例 例1： (1) for ( i=1; i=i+1; -j ) (3) if ( Aj-1Aj ) (4)temp = Aj-1; (5)Aj-1=Aj; (6)Aj=temp; 分析： (4)(6): O(1) (3)(6): O(1) (2)(6): O(1(n-i) = O(n-i) (1)(6): T(n)=O(n2) 3.1.4 算法与分析技术初步 27 例2：for ( i=2 ; i= i ; -j) S ; 求“S”语句的频度及整个 程序段的算法复杂度 分析：i=2：执行 n-1 次 i=3：执行 n-2 次 i=n-2；执行 3 次 则：F(n) = 3+4+5+n-1 = (n-3)(n+2)/2 T(n) = O(n2) 3.1.4 算法与分析技术初步 28 例3： i=1; While ( i sqrt(n) printf(“%d是一素数n”, n); else printf(“%d不是一素数n”, n); 求算法的复杂度 分析：设嵌套最深层语 句“ i+”的频度为F(n), 有：F(n)1.0= (y+1)(y+1) do y = y+1 ; 求语句的频度和整个 程序段的算法复杂度 分析：F(n)F(n) 10 ) do if w 20 then w=w-10 ; k- elsew=w+10; 求语句的频度 分析：对每一合法k值，句执行2次 则，句频度F(n)= (21-10)222 3.1.4 算法与分析技术初步 32 例7： x = 87 ; y = 10 ; while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ; 求语句的频度和整个 算法的复杂度。 分析：句频度F(n)= 15119114 T(n)=O(1) 3.1.4 算法与分析技术初步 33 例8： int fact ( int n)/ 计算n! (1)if ( nn+1) return(0); /位置非法 for (j=n;j=i;j-) Lj+1=Lj; /移动元素 Li=x; /插入元素 n+; /长度加1 return(1); /执行成功，返回 3.2.2 顺序存储线性表 45 2. 删除 1）概念：删除第i个位置上的元素，使线性表 的长度由n变为n-1。 2）删除过程：ai+1an依次前移一个位置(共移 动n-i个元素) 。(合法位置：1n) return(0); /参数不合法 for (j=i;j Bj) Ck+=Bj+; else Ck+=Bj+; /相等者只保存一个 i+; if ( i= =m)/B未完，将B余下的元素赋给C for (t=j; tdata;a1-next; ） 3.2.3 线性链表 54 二、线性链表的逻辑结构 2. 线性链表的特点 存储单元不要求连续，插入和删除方便； 要求较多的存储空间（存放指针域）。 a2 1008 data next data next a1 1002 data next a4nil a3 1007 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 地址 head 内存 3.2.3 线性链表 55 三、单链表 1. 基本概念：每个结点只有一个指针域的链表。 结点定义：typedef struct node char data; struct node *next; NODE; 3.2.3 线性链表 56 三、单链表 2. 线性链表的基本运算 （1）基本操作 3.2.3 线性链表 1）指针赋值：s=p;q=p-next; 2）指针移动：p=p-next;) 3）后插：s-next=p-next；p-next=s； 4）前插：q=head； while(q-next!=p) q=q-next; q-next=s；s-next=p； 57 p p p s p s headp s headq p s p p sq 1）指针赋值：s=p;q=p-next; 2）指针移动：p=p-next;) 3）后插：s-next=p-next；p-next=s； 4）前插：q=head； while(q-next!=p) q=q-next; q-next=s；s-next=p； 58 （2）结点的动态生成及回收 动态生成：GETNODE（P）; data（P）data=b;） C语言中的实现：(包含头文件“alloc.h”) int Get(NODE *P) P=(NODE *)malloc(sizeof(NODE); if (!P) return(0); else return(1); 回收：RET（P）; C语言中的实现：free（P）; 3.2.3 线性链表 59 NODE *CreateList(int n) /建立有n个结点的单链表 NODE *h=NULL,*pre=NULL,*s; /定义变量 for (i=0;idata); s-next=NULL; /生成结点并赋值 if (h=NULL) h=s; else pre-next=s; pre=s; /结点指针链接 return(h); /返回链表头指针 三、单链表 3.线性链表的建立（补充） 3.2.3 线性链表 60 1）问题描述：在值为a的结点前插入一个值为 x的结点。若链表为空，则x成为其头结点；若 表中无a元素，则将x插入表尾。 a Head x q s s-next=q-next; q-next=s; 三、单链表 4.插入运算 3.2.3 线性链表 61 2）算法描述 InsertList(head,a,x) GETNODE(p); p-data = x; /取得一个新结点p if (head=NULL) then /空表 head=p; p-next = NULL; return; if (head-data=a)then /a为头结点 p-next = head; head = p; return; q=head; while (q-next!=NULL /查找a之前的结点q p-next = q-next; q-next = p; /完成插入 LOOKFOR(head,a,q) 3.2.3 线性链表 62 1）问题描述：将值为a的结点删除。 head a p q p=q-next; q-next=p-next;free(p); 三、单链表 5.删除运算 3.2.3 线性链表 63 2）算法描述 DeleteList(head,a) if (head=NULL) return; /空表 if (head-data=a)then /a为头结点 p=head; head=head-next; free(p); return; LOOKFOR(head,a,q); if (q-next= =NULL) then return; p=q-next; q-next=p-next; free(p); /完成删除 return; 3.2.3 线性链表 64 三、单链表 5.算法运算时间分析 在单链表中插入或删除一个结点时，仅需改变 一个或两个指针，而无需移动元素。 3.2.3 线性链表 65 1）在链表的第一个结点之前附加一个头结点 head head （空表 ） 四、线性链表的其他形式 1.带头结点的线性链表 头结点： 数据域不 用，或用于存放其它信息，如表长。 指针域指向链表的第一个结点。 3.2.3 线性链表 66 2）头结点的用处：可简化算法的形式，例如 在插入运算中，当表空时尚有头结点存在，因 此头指针非空，当a为表中第一个元素时，因 有头结点存在，则在a结点之前插入一元素时 不必修改头指针。 3.2.3 线性链表 67 表中最后一个结点指向表的第一个结点， 整个链表形成一个环。（只要给定循环链表中 任一结点的地址，就可以查遍表中所有的结点，而 不必从头指针开始） 四、线性链表的其他形式 2.循环链表 headhead （空表 ） head head （空表 ） 3.2.3 线性链表 68 优点：提高查找效率 思考：如何判断循环链表的表尾？ （单链表：判断指针域为空） 四、线性链表的其他形式 2.循环链表 3.2.3 线性链表 69 逻辑结构: 四、线性链表的其他形式 3.双向链表 prior data next head head （空表 ） head head （空表 ） 3.2.3 线性链表 70 四、线性链表的其他形式 3.双向链表 特点：一个结点有两个指针域，容易找到前驱。 双向链表的插入：在P结点之后插入值为y的结点 P x y q GETNODE(q); q-data=y; q-next=p-next; p-next=q; q-next-prior = q; q-prior = p; 3.2.3 线性链表 71 四、线性链表的其他形式 3.双向链表 双向链表的删除：删除结点P。 p-prior-next=p-next; p-next-prior =p-prior; free(p); P x 3.2.3 线性链表 72 五、链表应用举例 1.一元多项式相加 结点结构：每一个非零项构成链表中的一个结点， 结点由两个数据域和一个指针域构成： coef exp next pi 3.2.3 线性链表 73 A(x)=3x14+2x8+1 B(x)=8x14-3x10+10x6 C(x)=A(x)+B(x) 设 pa, pb 指针 （1）若指数相等，则系数相加，c(x)中建项（系数为0，不建） （2）若pa-exppb-exp 复抄pa所指项，反之，复抄pb所指项。 -13 142810 ah -18 14-3 1010 6 bh cofexp ch-1 1411-3102 810 61 0 pa pb pc 74 struct node1 *addpoly(struct node1 *ah, struct node1 *bh) struct node1 *pa,*pb,*pc,*ch,*pp; int x,e; ch=(struct node1 *)malloc(LEN); ch-exp=-1; ch-next=ch; pc=ch; /*建立新表头结点*/ pa=ah-next; pb=bh-next; while(pa-exp!=-1)|(pb-exp!=-1) if( pa-exp=pb-exp) x=pa-cof+pb-cof; e=pa-exp; /*系数相加*/ pa=pa-next; pb=pb-next； /*修改指针*/ 3.2.3 线性链表 75 else if (pa-exppb-exp) x=pa-cof; e=pa-exp; /*复抄A(x)*/ pa=pa-next; else x=pb-cof; e=pb-exp; /*复抄B(x)*/ pb=pb-next; if (x!=0) /*形成新结点链