资源预览内容
第1页 / 共52页
第2页 / 共52页
第3页 / 共52页
第4页 / 共52页
第5页 / 共52页
第6页 / 共52页
第7页 / 共52页
第8页 / 共52页
第9页 / 共52页
第10页 / 共52页
亲,该文档总共52页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
题型: 1. 单选 15分 每题1分 2. 判断 10分 每题1分 3. 填空 12分 每空1分 4. 程序分析题 (写出运行结果)18分 每题6分 5. 应用题 30分 每题10分 6. 编程题 15分 两小题任选其一 数据结构复习 2012/11/101 应用题: 1. 分析算法的时间复杂度(最好、最差、平均情况) 2. 串 KMP算法(看习题)给出目标串做模式匹配,计算 next函数值,利用算法写出匹配过程(每趟的结果) 3. 二叉树的构造 给两个遍历序列画出二叉树,并写出另 外一种遍历序列 4.哈夫曼算法的应用 给出字符的出现频率,构造哈夫曼 树,编写二进制编码,计算最有WPL值 5.排序 快速、冒泡、直插、希尔排序四种排序的基本思 路,排序过程,给出关键字会写每趟的结果 编程题 1.写出算法的基本思路(可以用图示法和文字叙述)3分 2. 定义相应的数据结构 2分 3. 代码 10分 2012/11/102 第一章 基本概念: 数据元素:是数据(集合)中的一个“个体” , 是数据的基本单位。也称为结点、顶点、记录 等。通常作为一个整体来处理。 数据项:是具有独立含义的数据最小单位 ,也称 为字段或域。 数据结构:是指数据以及数据元素相互之间的联 系。可以看作是相互间存在一种或多种关系的数 据元素集合。 数据结构组成的三要素:数据的逻辑结构、存储 结构、数据的运算。 2012/11/103 4/49 学号姓名性别班号 1张斌男9901 8刘丽女9902 34李英女9901 20陈华男9902 12王奇男9901 26董强男9902 5王萍女9901 数据元素 数据项 数据结构实学生表 2012/11/10 逻辑结构类型 (1) 集合 结点之间关系:无。 (2) 线性结构 结点之间关系:一对一。 特点:开始结点和终端结点都是惟一的,除了开始结点和终端结点以 外,其余结点有且仅有一个直接前驱和直接后继结点。如学生表、成 绩表、档案表、索引表等都属于线性结构。 (3) 树形结构 结点之间关系:一对多。 特点:每个结点最多只有一个直接前驱结点,但可以有多个直接后 继结点。高校的行政结构示意图、家族族谱图、书的目录、操作系 统的目录结构、系统内部的表达式计算等都是树形结构。 (4) 图形结构 结点之间关系:多对多。 特点:每个结点的直接前驱和直接后继结点的个数都是任意的。交 通网、通信网、万维网、赛事日程安排、课程安排和最短路径问题 等都属于图形结构。 2012/11/105 常见逻辑结构的类型 1.集合 2.线性结构:顺序表 3.树形结构 4.图形结构 ( 3 2. 指针类型 int *p; 3. 数组类型 int a10; 4. 结构体类型 struct student int sno; char sname10; char ssex2; int sage; 5. 自定义类型 typedef char ElemType; 2012/11/109 算法分析方法,即算法的渐近时间复杂度分析 方法一 统计从开始到终止算法所需的总程序步数, 并 将其视为问题规模n的函数T(n); 方法二 在算法中选取一种基本操作;计算基本操作 执行总步数,并将其记作T(n)。 T(n)称为算法的时间复杂度。 时间复杂度的大O表达法:当问题的规模n趋向无穷大 时, 时间复杂度T(n)的数量级f(n)称为算法的渐进时间 复杂度,记作T(n)=O(f(n)。 T(n)=2n+3=O(n) T(n)=3n2+1=O(n2) 也就是只求出T(n)的最高阶,忽略其低阶项和常系数. 2012/11/1010 平均复杂度(The Average Case): 所有可能输入数据 集的期望值。 最坏情况复杂度(The Worst Case): 估算最坏情况下 时间复杂度的一个上界。这也是通常所指的复杂度。 一个没有循环的算法的基本运算次数与问题规模n 无关,记作O(1),也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规 模n的增长呈线性增大关系,记作O(n),也称线性阶。 重点:例1.81.9及相关习题(P33最坏情况、最好情 况、平均时间复杂度的分析) 2012/11/1011 12/49 各种不同数量级对应的值存在着如下关系: O(1)O(log2n)O(n)O(n*log2n)O(n2) O(n3)O(2n)length+1)return 0; i-; for (j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=e; L-length+; /*顺序表长度增1*/ return 1; 2012/11/1016 2. 删除数据元素ListDelete(L,i,e) 思路: 判断参数i是否为合法值; 保留第i个元素的值; 将顺序表表尾至第i个元素前移一位; 顺序表长度减1。 int ListDelete(SqList * if (iL-length)return 0; i-; e=L-datai; for (j=i;jlength-1;j+) L-dataj=L-dataj+1; L-length-; return 1; 2012/11/1017 单链表线性表中每个元素至多只有一个前驱元素和一个后继元素, 所以链表中每个结点除包含有数据域外,只设置一个指针域, 以指向其后 继结点, 这样的链接表称为单链表。 双链表每个结点中除包含有数值域外,设置两个指针域,分别指向其前 驱结点和后继结点,这样的链接表称之为线性双向链接表, 简称双链表。 循环链表循环链表是表中最后一个结点的指针指向头结点,使链表 构成环状 2012/11/1018 LinkList类型定义(单链表) typedef struct Lnode ElemType data; struct Lnode *next; LinkList; DLinkList类型定义(双链表) typedef struct Lnode ElemType data; struct Dnode *prior; struct Dnode *next; DLinkList; 2012/11/1019 单链表基本运算的实现 重点掌握头插法、尾插法建立单链表 1. 头插法 操作接口:CreateListF(L, a, n) 2012/11/1020 void CreateListF(LinkList * int i; L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL; for (i=0;idata=ai; s-next=L-next; L-next=s; 2012/11/1021 2.尾插法 2012/11/1022 void CreateListR(LinkList *int i; L=(LinkList *)malloc(sizeof(LinkList); r=L; for (i=0;idata=ai; r-next=s r=s; r-next=NULL; 2012/11/1023 比较顺序表和链表两种存储结构(差异、适用情形) 存储分配方式比较 顺序表采用顺序存储结构,即用一段地址连续的存储 单元依次存储线性表的数据元素,数据元素之间的逻 辑关系通过存储位置来实现。 单链表采用链接存储结构,即用一组任意的存储单元 存放线性表的元素。用指针来反映数据元素之间的逻 辑关系。 2012/11/1024 时间性能比较 时间性能是指实现基于某种存储结构的基本操作 (即算法)的时间复杂度。 顺序表的时间为(1),是随机存取; 单链表的时间为(n),是顺序存取。 顺序表需移动表长一半的元素,时间为(n); 单链表不需要移动元素,在给出某个合适位置的 指针后,插入和删除操作所需的时间仅为(1)。 2012/11/1025 空间性能比较 空间性能是指某种存储结构所占用的存储空间的 大小。 定义结点的存储密度: 2012/11/1026 空间性能比较 结点的存储密度: 顺序表中每个结点的存储密度为1(只存储数据 元素),没有浪费空间; 单链表的每个结点的存储密度0)个互不相交的有限集合T1,T2, ,Tm ,其中每个集合又是一棵树,并称为这个根结点 的子树。 2012/11/1039 2. 树的表示 树形图表示法:是树结构的主要表示方法。 括号表示法 文氏图表示法 凹入表示法 3. 树的基本术语 (1)结点的度与叶子结点:树中某个结点的子 树的个数称为该结点的度。树中各结点的度的最 大值称为树的度,通常将度为m的树称为m次 数。 (2)分支结点与叶子结点:度不为零的结点称 为非终端结点,又叫分支结点。度为零的结点称 为终端结点或叶子结点。在分支结点中,每个结 点的分支数就是该结点的度。 2012/11/1040 (3)路径与路径长度:对于任意两个结点ki和kj,若 树中存在一个结点序列ki,ki1,ki2,kin,kj,使 得序列中除ki外的任一结点都是在其序列中的前一个结 点的直接后继,则称该结点序列为由ki到kj的一条路径 ,用路径所通过的结点序列( ki,ki1,ki2,kin ,kj)表示这条路径。路径的长度等于路径所通过的结 点数目减1(及路径上分支数目)。 (4)孩子结点、双亲结点和兄弟结点:在一棵树中每 个结点的直接后继被称作该结点的孩子结点(或子女 结点)。相应的,该结点被称作孩子结点的双亲结点 (或父母结点)。具有同一双亲的孩子结点互为兄弟 结点。 (5)结点的层次和树的高
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号