《数据结构-绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构-绪论.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构绪论绪论抽象数据类型抽象数据类型小结和作业小结和作业地位和作用地位和作用学习内容学习内容算法分析算法分析数据（数据（Data）1、形式、形式2、含义、含义数字、字符、图形、图像、音频、视频数字、字符、图形、图像、音频、视频11111111111111110000000000000001数据类型：数据类型：int float double(IEEE 754)文件类型：文件类型：DOC TXT JPG PDF结构（结构（Structure）结构：关系（Relation）数据结构数据结构Data_Structure=(D,S)D:a1,a2,a3,anS:,D：1,7,8,9D：“A
2、BC”,“City”D：“张明”，“男”，19，“计算机”，“王明辉”，“男”，20，“法律”，数据结构数据结构物理结构物理结构逻辑结构逻辑结构集合集合线性表线性表树树图图顺序结构顺序结构链式结构链式结构Da1,a2,anS 集集合合Da1,a2,anS|ai-1,ai D,i=2,.,n 线性表线性表Da1,a2,anS|i j 对每个j，存在唯一的i有 树树Da1,a2,anS|ai D,aj D 图图例1有数据结构:D=1,2,3,4,5 S=,什么数据结构?逻辑结构逻辑结构例1D=1,2,3,4,5 S=,12345逻辑结构逻辑结构例2有数据结构:D=1,2,3,4,5,6,7 S=,
3、什么数据结构?逻辑结构逻辑结构例2D=1,2,3,4,5,6,7 S=,1234675逻辑结构逻辑结构例3有数据结构:D=1,2,3,4,5,6,7,8 S=row,colrow=,Col=,什么数据结构?逻辑结构逻辑结构例31234675D=1,2,3,4,5,6,7,8 row=,Col=,8逻辑结构逻辑结构物理结构物理结构数据在内存中如何表示？数据在内存中如何表示？数据之间的关系在内存中如何表示？数据之间的关系在内存中如何表示？存储器模型存储器模型1、电子元器件构成存储单元2、地址寄存器4、地址总线6、数据寄存器物理模型逻辑模型5、数据总线3、地址译码器0123n存储器模型存储器模型假设
4、有假设有5位同学的成绩表：位同学的成绩表：2006001 992006003 802006004 852006005 602006006 70顺序存储结构顺序存储结构元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容2006001 992006003 802006004 852006005 602006006 70链式存储结构链式存储结构存储内容存储内容L0元素元素n n.元素元素2 2.元素元素3 3元素元素1 12006001 992006003 802006004 852006005 60200
5、6006 70P地位与作用地位与作用Niklaus Wirth（N.沃思）教授提出：Programs=Algorithm+Data Structures 地位与作用地位与作用aX2+bX+c=0#include#include int main(int argc,char*argv)int a,b,c;float r1,r2,deta;scanf(%d%d%d,&a,&b,&c);deta=b*b-4*a*c;if(deta=a2&a1=a3&a1=a4)printf(max=,a1);地位与作用地位与作用#include int main(int argc,char*argv)int a10
6、,max,i;for(i=0;i10;i+)scanf(%d,&ai);max=a0;for(i=1;i10;i+)if(max ai)max=ai;printf(max=%dn,max);return 0;姓名姓名项目项目1项目项目2项目项目3丁礼仪跳高跳远100M马翔标枪铅球张大伟标枪100M200M李三立铅球200M跳高王敏跳远200M合理的安排各个项目的比赛时间，使得每合理的安排各个项目的比赛时间，使得每位选手都能参与比赛位选手都能参与比赛地位与作用地位与作用跳高跳远标枪铅球200M100M地位与作用地位与作用韦尔奇韦尔奇.鲍威尔（鲍威尔（Welch Powell）1、将图、将图G中的
7、结点按照度的递减次序排列中的结点按照度的递减次序排列2、用第一种颜色对第一个点着色，按照排列、用第一种颜色对第一个点着色，按照排列次序，对与前面着色点不邻接的每一点着上同次序，对与前面着色点不邻接的每一点着上同样的颜色样的颜色3、用第二种颜色对尚未着色的点重复第、用第二种颜色对尚未着色的点重复第2步步4、用第三种颜色继续前面的过程，直到所有、用第三种颜色继续前面的过程，直到所有的点都被着色的点都被着色地位与作用地位与作用跳高跳远200M100M第一时间：第一时间：200M第二时间：跳高和标枪第二时间：跳高和标枪第三时间：第三时间：100M和铅球和铅球第四时间：跳远第四时间：跳远地位与作用地位与
8、作用铅球标枪跳高跳远标枪铅球200M100M在计算机中如何在计算机中如何表示图？表示图？地位与作用地位与作用学习内容学习内容1、如何使用存储结构实现逻辑结构、如何使用存储结构实现逻辑结构2、如何实现逻辑结构的常用操作、如何实现逻辑结构的常用操作3、如何评价？、如何评价？学习内容学习内容n绪论：数据、数据元素、数据结构、数据类型、抽象数据类型的概念。n线性表：线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；用线性表表示一元多项式及实现稀疏多项式的相加等运算。n栈和队列：栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用。学习内容学习内容n树和二叉树：树的
9、基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；线索二叉树；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码。n图：图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径。学习内容学习内容n查找：静态查找表、动态查找表、哈希表实现；n排序：介绍插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。n算法分析和递归程序理论教学：理论教学：48学时学时实践教学：上机实践教学：上机8学时学时 2周集中课程设计周集中课程设计教材：教材：数据结构数据结构严蔚敏、严蔚敏、吴伟民吴伟民主编主编 清华大学出版
10、社清华大学出版社 学习内容学习内容数据结构、算法与应用数据结构、算法与应用Sartaj Sanhi著著 汪诗林等译汪诗林等译 机械工业出版社出版社机械工业出版社出版社 数据结构数据结构 Java语言描述语言描述Sichael Main著著 机械工业出版社出版社机械工业出版社出版社 李盛恩李盛恩 教授教授计算机计算机科学技术学院科学技术学院E-mail:Tel:86361301Office:XX220 学习内容学习内容抽象数据类型的定义抽象数据类型的定义线性表List=(D,R,P)P=InitList,DestroyList,ListInsert Da1,a2,anR|ai-1,ai D,i=
11、2,.,n 抽象数据类型的实现抽象数据类型的实现定义存储结构 typedef struct ElemType*elem;intlength;intlistsize;SqList;抽象数据类型的实现抽象数据类型的实现Status ListInit_Sq(SqList&L)L.elem=(ElemType*)malloc (LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return(OK);抽象数据类型的实现抽象数据类型的实现封装到一个头文件List_
12、Sq.h#include#define TRUE1#define FALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2抽象数据类型的使用抽象数据类型的使用作为一个数据类型应用：#include List_Sq.hint main(int argc,char*argv)SqList L;ListInit_Sq(L);for(int i=1;i11;i+)ListInsert_Sq(L,i,i);ListDelete_Sq(L,5,i);算法分析算法分析算法算法是为了解决某类问题而规定的一个有限长的操操作序列作序列。算法
13、分析：算法分析：对算法的性能进行分析，便于算法的比较和选用。算法分析：算法分析：时间复杂性分析和空间复杂性分析通常有两种两种衡量算法效率的方法:事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1、必须执行程序 2、其它因素掩盖算法本质算法分析算法分析渐进时间复杂性分析方法：渐进时间复杂性分析方法：1、确定算法的主要操作2、计算主要操作执行的次数3、一般的讲，执行次数是输入的函数4、根据函数的特点，得到函数所属的阶（order）算法分析算法分析算法分析算法分析求S=1+2+3+nint S=0,i,n;scanf(%d“,&n);for(i=1;i=n;i+)S=S+i;printf
14、(“%d“,S);输入的长度输入的长度:n主要操作：加法主要操作：加法执行加法的次数：执行加法的次数：n算法的时间复杂性：算法的时间复杂性：T(n)=O(n)算法的空间复杂性：算法的空间复杂性：S(n)=O(1)函数关系：函数关系：f(n)=n算法分析算法分析函数的分类：函数的分类：常数阶O(1)对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n2)指数阶O(2n)小小 结结物理结构物理结构逻辑结构逻辑结构集合集合线性表线性表树树图图顺序结构顺序结构链式结构链式结构数据结构数据结构作业及要求作业及要求阅读：1、教材的第一章 2、Michael Main.Data Stru
15、cture and Other Objects Using Java.机械工业出版社 Chapter One:The Phases of Software Development作业及要求作业及要求预习：1、p18-262、C语言的一维数组 内存的存放方法 访问数组元素的两种方法 数组名的内涵 动态存储分配 malloc和realloc作业及要求作业及要求思考：如何用类实现抽象数据类型？作业：1.3要求：1、独立完成作业2、字迹工整，美观3、按时交作业4、做错了的题下次要改正5、准备两个本子练习练习2、数据的()包括集合、线性、树和图结构四种类型。A.存储结构 B.逻辑结构 C.物理结构 D.基本运算1、数据结构有（）结构和（）结构两种，通常是指（）结构