第一章 数据结构 概念数据结构电子教案1n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n算法定义算法定义n n模板模板n n算法简单性能分析与度量算法简单性能分析与度量第一章 数据结构概念2“ “学生学生” ”表格表格3“ “课程课程” ”表格表格4学生 (学号,姓名,性别,籍贯)课程 (课程号,课程名,学分)选课 (学号,课程号,成绩)“ “选课单选课单” ”包含如下信息包含如下信息学号学号 课程编号课程编号 成绩成绩 时间时间学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系5UNIX文件系统的系统结构图/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp6数据（data）n数据是信息的载体，是描述客观事物的数 、字符、以及所有能输入到计算机中，被 计算机程序识别和处理的符号的集合。n数据的分类：u 数值性数据u 非数值性数据7姓名 所在院系 性别 出生日期年 月职务 业绩数据元素 (data element)n数据的基本单位。在计算机程序中常作为 一个整体进行考虑和处理。n有时一个数据元素可以由若干数据项 (Data Item)组成。数据项是具有独立含义 的最小标识单位。n数据元素又称为元素、结点、记录。8什么是数据结构定义: 由某一数据元素的集合以及该集合中所有 数据元素之间的关系组成。记为：Data_Structure = D, R其中，D 是某一数据元素的集合，R 是该集 合中所有数据元素之间的关系的有限集合。9例：N 个网点之间的连通关系树形关系树形关系网状关系网状关系15615243624310数据结构是数据的组织形式n包括三个方面：u数据元素间的逻辑关系，即数据的逻辑 结构；u数据元素及其关系在计算机存储内的表 示，即数据的存储表示；u数据的运算，即对数据元素施加的操作 。11数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据， 与数据的存储无关；n数据的逻辑结构可以看作是从具体问题抽 象出来的数据模型；n数据的逻辑结构与数据元素本身的形式、 内容无关；n数据的逻辑结构与数据元素的相对存储位 置无关。12数据的逻辑结构分类n线性结构u 线性表n非线性结构u 树u 图（或网络）13线性结构树形结构 树 二叉树 二叉搜索树bindevetclibuser1413121123456789103158710119987456623131114堆结构“最大最大”堆堆 “最小最小”堆堆12354871110291641012115123698715图结构 网络结构12543611 33181466516192112563416数据的存储结构n数据的存储结构是逻辑结构用计算机语言 的实现；n数据的存储结构依赖于计算机语言。u 顺序存储表示u 链接存储表示u 索引存储表示u 散列存储表示主要用于内存的 存储表示 主要用于外存 (文 件) 的存储表示17抽象数据类型及面向对象概念n数据类型 定义：一组性质相同的值的集合, 以及 定义于这个值集合上的一组操作的总称.nC语言中的数据类型char char intint float double void float double void字符型 整型 浮点型 双精度型 无值 18n构造数据类型由基本数据类型或构造数 据类型组成。n构造数据类型由不同成分类型构成。n基本数据类型可以看作是计算机中已实 现的数据结构。n数据类型就是数据结构，不过它是从编 程者的角度来使用的。n数据类型是模板，必须定义属于某种数 据类型的变量，才能参加运算。 19抽象数据类型 (ADTs: Abstract Data Types)n抽象数据类型是由用户定义，用以表示 应用问题的数据模型。n特点是：信息隐蔽和数据封装，使用与 实现相分离。n抽象数据类型可用（D, S, P）三元组表 示，其中，D 是数据元素的集合（简称 数据对象），S 是 D上的关系集合，P 是 对 D 的基本操作集合。 20抽 象 数 据 类 型查找 登录 删除 修改 符 号 表21抽象数据类型的描述n其中数据对象、数据之间的关系用伪码 描述；基本操作定义格式为ADT 抽象数据类型名 数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT 抽象数据类型名基本操作名（参数表） 前置条件：先决条件描述 后置条件：操作结果描述22n基本操作有两种参数：赋值参数只为操作 提供输入值；引用参数以False, True Boolean, +、-、 /K是表项关键码类型 template / /E是表项类型 class dataList private:E *element;int listSize;void swap (int m1, int m2);int minKey (int low, int high);37public:dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element;void sort ( );friend ostreamfriend istream;#endif 38类中所有操作作为模板函数的实现 template void dataList : swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值E temp = element m1;element m1 = element m2;element m2 = temp;39template int dataList:minKey (int low, int high) /查找数组Elementlow到Elementhigh中具 /有最小关键码值的表项，函数返回其位置int min = low; for (int i = low+1, i ostreamcout inList.elementi;return inStream; 42template void dataList : sort ( ) /按非递减顺序对listSize个关键码element0到 /elementArraySize-1排序for (int i = 0; i #include “dataList.h”const int SZ = 10;int main ( ) struct sick /患者int key;char *name15;int age;char *address30;bool operator TestList (SZ);cin TestList;cout = i; j-) /n-i次比较 if (aj-1 aj) int tmp = aj-1; aj-1 = aj;aj = tmp; /一趟比较 65渐进时间复杂度渐进时间复杂度O(f (n)*g (n) = O(n2) BubblrSort外层循环 n-1 趟 内层循环 n-i 次比较66n有时, 算法的时间复杂度不仅依赖于问题规 模 n，还与输入实例的初始排列有关。n在数组 An 中查找给定值 k 的算法：int i = n-1; while (i = 0 return i;n算法的语句 i- 的频度不仅与 n 有关，还 与 A 中各元素的取值以及 k 的取值有关 。67n例：设有两个算法在同一机器上运行，其执 行时间分别为 100n2 和 2n，问：要使前者快 于后者，n 至少要取多大？解答：问题是找出满足 100n2 2n = 8192n = 14时，100n2 = 19600 2n = 16384n = 15时，100n2 = 22500 arraySize 或者对于某一 个 k ( 0 k n )，使得k!*2k maxInt 时， 应按出错处理。69可有如下几种不同的出错处理方式：用 cerr #define n 100 #define maxInt 0x7fffffffbool calc (int T , int n) int i, value = 1;if ( n != 0 ) for (i = 1; i maxInt / n / 2) return false; /直接判断 i!*2i MaxInt 是危险的value *= n * 2; 71Tn = value; /n!*2n Tn return true; void main ( ) int An, i;for (i = 0; i n; i+)if (!calc (A, i) cout “failed at “ i endl;break; 72