数据结构软件.ppt
《数据结构软件.ppt》由会员分享,可在线阅读,更多相关《数据结构软件.ppt(375页珍藏版)》请在启牛文库网上搜索。
1、1,数 据 结 构,(C语言版),作者:黎剑兵,2,第 一 章 绪 论,学习内容 常用术语 算法评价 时间复杂度与空间复杂度的分析 重点了解逻辑结构 物理结构和数据的运算三方面相关概念及相互关系难点 时间复杂度的分析方法掌握 用类C语言的表示方法会用类C编写程序,3,第 一 章 绪 论,计算机科技 是 一门研究用计算机进行信息表示和处理的科学。主要涉及两方面的问题:信息的表示和信息的处理 信息的表示和组织直接关系到处理信息的程序 的效率,随着计算机的应用领域的扩大。信息量的增加,信息范围的拓宽,使系统程序和应用程序的规模的日趋增大,结构也日趋增大。因此,为了编写出一个“好”的程序,必须分析 处
2、理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。,4,第 一 章 绪 论,计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么,什么是数据结构呢?,5,1.地位,第 一 章 绪 论,6,1.地位,第 一 章 绪 论,数据结构Data Structure,7,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,8,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,(1)要对所加工的对象进行逻辑组织(2)如何把加工对象存储到计算机中去?(3)数据运算,9,3.学科定义,什么是数据结构,数据结构 是一门研究非数值
3、 计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的学科。,10,基本概念和术语,数据元素(data element)数据基本单位,也称节或孩子,可由若干个数据项组成。数据项是数据最小单位数据(data)是对客观事物的 表示,指所有能输入到计算机并被计算机程序处理的符号的总称。数据对象(data object)性质相同的数据元素的集合数据结构 数据元素之间的相互关系,11,1)集合,基本概念和术语,数据间的四种典型结构:,2)线形,3)树形,4)图或网络:,12,基本概念和术语,四种典型结构:,1)集合,13,四种典型结构,基本概念和术语,2)线形:,14,四种典型结构:
4、,基本概念和术语,3)树形:,15,四种典型结构:,基本概念和术语,4)图或网络:,16,基本概念和术语,(5)逻辑结构:从具体问题抽象出的数学模型。体现逻辑关系。,(6)物理结构(存储结构):DE及关系在计算机中的表示。DE存储称为节点关系存储:a.顺序存储 b.链式存储,17,基本概念和术语,(7)DS广义定义:DE 的逻 辑 结 构 DE 的物 理 结 构DE 的 抽 象 运 算(8)基本操作加工型:插入 删除 更新 排序 引用型:查找,18,基本概念和术语,19,算法和算法分析,一、算法定义,算法是对特定问题求解步骤的一种描述,是指令的有限序列。特性:有穷性 确定性 可行性 输入 输出
5、,20,算法和算法分析,二、算法的描述与分析描述:类C语言要求正确性:a.语法 b.n个输入 c.一组典型的苛刻的输入 d.所有输入可读性健壮性效率与存贮量,21,算法和算法分析,分析标准 a、时间复杂度:算法中基本操作重复执行的次数(频度)。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,22,分析标准 a、时间复杂度:算法中基本操作重复执行的次数。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,算法和算法分析,b、空间复杂度:算法所需存贮空间S(n)=O(f(n),23,算法和算法分析,例:分析下列
6、语句段的时间复杂度m=0;1for(k=0;kn;k+)n+1for(j=0;jk;j+)n(n+1)/2m+=2;O(n2),24,习题与练习 一,1.简要回答下列问题:a.数据与数据元素有何区别?b.逻辑结构与存储结构是什么?它们是什么关系?c.什么是算法?它有什么特点?,25,习题与练习 一,2.试写一个算法,统计输入的100个整数中奇数和偶数的个数。3.设计下面问题算法,并分析最坏情况时间复杂性:在数组 A1.n中查找值为 K的元素,若找到输出其位置 i(0 i n+1),否则输出0。,26,习题与练习 一,4.设 n 为正整数,写出下列程序段的时间复杂度:(1)for(I=1;In;
7、I+)m=m+I;for(j=0;jn;j+)count+=m+j;,27,习题与练习 一,(2)for(I=0;In;I+)m=m+I;for(j=0;j10;)count+=m+j;j+;,28,习题与练习 一,(3)k=1;s=0;while(s=n-1)k=k+s*6;s+;printf(“%d,%d”,s,k);,29,第 二 章 线 性 表,学习内容 线性表定义 线性表的抽象数据结构 线性表的顺序存储和操作实现 线性表的链接存储和在链表上的操作实现 线性表在双向链表操作实现,30,第二章 线性表,线性结构特点:,在数据元素的非空有限集合中 1)“第一个”唯一 2)“最后一个”唯一
8、3)除第一个外,每一个有且仅有一个直接前驱 4)除最后一个外,每一个均有且仅有一个直接后继,31,一、线性表的定义,第二章 线性表,表头元素,表尾元素,2.1 线性表的类型定义,32,2.1 线性表的类型定义,一、线性表的定义,一个线性表可以用一个标识符来命名:A=(a1,a2,ai,ai+1,an)ai可以是基本数据类型也可以是struct 类型,33,2.1 线性表的类型定义,二、线性结构特点,在数据元素的非空有限集中元素个数n表长度,n=0空表存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前趋除最后一个外,集合
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 软件