《计算机软件工程基础课件,,第三版41110》由会员分享，可在线阅读，更多相关《计算机软件工程基础课件,,第三版41110（80页珍藏版）》请在金锄头文库上搜索。
1、1常用数据结构及其运算常用数据结构及其运算第三章第三章23.1 3.1 概述概述 3.2 3.2 线性表线性表3.3 3.3 栈与队栈与队 3.4 3.4 树与二叉树树与二叉树3.53.5 图图3.6 3.6 查找与排序查找与排序目录目录33.1 概 述3.1.1 数据结构的概念3.1.2 数据的逻辑结构和物理结构3.1.3 算法与算法分析3.1.4 算法分析技术初步3.1.5 小结43.1.1 数据结构的概念1. 数值型与非数值型数据数值型：整型、实型、布尔型等非数值型：文献检索、金融管理、商业系统 等数据处理 2. 数据结构研究非数值运算的程序设计问题。 数据结构就是相互之间存在一种或多种
2、特定 关系的数据元素的集合。如线性关系、层次关系、网状关系等。5数据(data)是信息的载体，指所有能输入到计 算机中并被计算机程序处理的符号的总称。如 数、字符、符号等的集合。分为数值型和非数 值型数据两类。数据元素(data element)是数据的基本单位。 如数据集合N= 1，2，3，4，5 中整数1至5 均为数据元素。 数据元素不一定是单个的数字或字符，也可 能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。3. 基本概念和术语3.1.1 数据结构的概念6数据类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等 结构类型：变
3、量值可分，如数组、结构体等数据对象(data object)性质相同的数据元素的 集合。如大写字母字符的数据对象是集合： C= A，B，.，Z 。3.1.1 数据结构的概念7数据结构(data structure)是指同一数据对象中各 数据元素间存在的关系。数据结构与算法 程序算法数据结构算法指解决特定问题的有限运算序列3.1.1 数据结构的概念81.逻辑结构：研究数据元素及其关系的数学特性，即数据元素间的逻辑关系。二元组 S =（D，R）D数据元素的非空有限集合 RD上关系的非空有限集合。3.1.2 数据的逻辑结构和物理结构9四类基本结构 ：线性结构（一对一）通迅录、成绩单、花名册树形结构（
4、一对多）电子字典、家谱、目录图形结构（多对多）交通线路、通信网络举举 例例集合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)，其中
5、D 1,2,3,4,5; R = r r = , , , , 3.1.2 数据的逻辑结构和物理结构122.物理结构(存储结构)：是逻辑结构在计算 机中的映象，即具体实现。四种基本存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构3.逻辑结构与存储结构的关系 算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。 同一种逻辑结构可采用不同的存储结构。3.1.2 数据的逻辑结构和物理结构13一、什么是算法 算法是对特定问题求解步骤的一种描述，是指 令的有限序列，其中每条指令表示一个或多个 操作。 算法的五个特征：有穷性、确定性、可行性、输入、输出 算法描述：采用类C语言的形式
6、，有时也用自然 语言。注释部分用/或/*.*/表示。3.1.3 算法与算法分析14二、算法设计的要求：正确性、健壮性、效率与低存储三、算法评价标准：时间复杂度、空间复杂度一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在时间和空间两方面的消耗多少 作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算 着重介绍第二种第二种方法。（算法、问题规模、语言、机器代码质 量、机器执行指令的速度）3.1.3 算法与算法分析15一、时间复杂度1. 频度：指一条语句重复执行的次数。记作 ：F(n)2. 算法的时间度量：T(n)=
7、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 n2T(n): O(1) O(n) O(n2)例: (a) +x;s=0(b) for (i=1;i外层逐层分析3.1.4 算法与分析技术初步255) 过程调用语句：a.非递归过程：根据过程调用的层次，由内而外分析程序的运行时间。b.递归调用：可先对递归过程设一特定的运行时间函数T(n
8、)，根据过程递归调用的情况，得到T(n)的一个递推关系。6) go to 语句：可以最坏情况进行计算，即在遇到向 下转移的go to 语句时，可认为go to 语句所引起 的控制转移根本没有发生；当遇到向上转移的go to 语句时，则必须考虑它对程序运行时间的影响。3.1.4 算法与分析技术初步264. 时间复杂度计算举例例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
9、)(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)/2T(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),有
10、：F(n)1.0= (y+1)(y+1) doy = 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)2223.1.4 算法与分析技术初步32例7： x = 87 ; y = 10 ;while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ; 求语句的频度和整个 算法的复杂度。分析：句频度F(n)= 15119114T(n)=O(1)3.1.4 算
11、法与分析技术初步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 顺序存储线性表 452. 删除1）概念：删除第i个位置上的元素，使线性表 的长度由n变为n-1。2）删除过程：ai+1an依次前移一个位置(共移 动n-i个元素) 。(合法位置：1n) return(0); /参数不合法 for (j=i;j Bj) Ck+=Bj+;else Ck+=Bj+; /相等
12、者只保存一个 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 10071000 1001 1002 1003 1004 1005 1006 1007 1008 1009地址head内存3.2.3 线性链表55三、单链表1. 基本概念：每个结点只有一个指针域的链表。 结点定义：type
13、def 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；57ppps psheadpsheadqpsppsq1）指针赋值：s=p;q=p-next; 2）指针移动：p=p-next;) 3）后插：s-next=
14、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 线性链表59NODE *CreateList(int n) /建立有n个结点的单链
15、表 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 线性链表601）问题描述：在值为a的结点前插入一个值为 x的结点。若链表为空，则x成为其头结点；若 表中无a元素，则将x插入表尾。aHeadxqs s-next=q-next; q-next=s;三、单链表 4.插入运算3.2.3 线性链表612）算法描述InsertList(head,a,x) GETNODE(p); p-data = x; /取得一个新结点pif (head=NULL) then /空表head=p; p-next = NULL; return; if (head-data=a)then /a为头结点p-next = head; head
