数据结构软件

《数据结构软件》由会员分享，可在线阅读，更多相关《数据结构软件（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,四种典型结构, 基本概念和术语

4、,2）线形：,14,四种典型结构：, 基本概念和术语,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)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶, 算法和算法分

6、析,b 、空间复杂度： 算法所需存贮空间S(n)=O(f(n),23, 算法和算法分析,例：分析下列语句段的时间复杂度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. 设计下面问题算法，并分析最坏情况时间复杂性:在数组 A1n中查找值为 K的元素，若找到输出其位置 i ( 0

7、 i n+1),否则输出0。,26,习题与练习 一,4. 设 n 为正整数，写出下列程序段的时间复杂度： （1）for(I=1;In;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,第 二 章 线 性 表,学习内容线性表定义线性表的抽象数据结构线性表的顺序存储和操作实现线性表的链接存储和在链表上的操作实

8、现线性表在双向链表操作实现,30,第二章 线性表,线性结构特点：,在数据元素的非空有限集合中1）“第一个 ”唯一 2）“最后一个”唯一3）除第一个外，每一个有且仅有一个直接前驱4）除最后一个外，每一个均有且仅有一个直接后继,31,一、线性表的定义,第二章 线性表,表头元素,表尾元素,2.1 线性表的类型定义,32,2.1 线性表的类型定义,一、线性表的定义,一个线性表可以用一个标识符来命名：A=(a1 , a2 , , ai , ai+1 , , an)ai可以是基本数据类型也可以是struct 类型,33,2.1 线性表的类型定义,二、线性结构特点,在数据元素的非空有限集中 元素个数n表长度

9、，n=0空表 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前趋 除最后一个外，集合中的每个数据元素均只有一个后继 元素同构，且不能出现缺项,34,2.1 线性表的类型定义,线性表几个具体例子,L1=（a,b,c,4,7,+,-,*,/） L2=（25,35,28,49,51,87,46,32,88） L3=（“BASIC”,“PASCAL”,“JAVA”,“OK”） L4=（a,b,c,d,e,f,g,h,i,j,k,x,y,z）,35,2.1 线性表的类型定义,基本运算,( 1 ) 初始化 initList(

10、sq)。其作用是建立一个空表sq(即建立线性表的构架，但不含任何数据元素)。 ( 2 ) 求表长 ListLen(sq)。其作用是返回线性表sq的长度。 (3)读表元素 GetElem(sq，i)。若1iListLen(sq)， 则其作用是返回线性表sq的第i个数据元素;否则，返回NULL。,36,2.1 线性表的类型定义,基本运算,(4)定位(按值查找)LocateElem(sq，x)。若sq中存在一个或多个值与x相等的元素，则其作用是返回这些元素的序号的最小值；否则，返回0。,37,基本运算,(5)插入ListInsert(sq，x，i)。其作用是在线性表sq的第i个位置上增加一个以x为值

11、的新元素，使sq由(a1，ai-1，ai，an)变为(a1，ai-1，x，ai，an)。参数i的合法取值范围是：1in+1,2.1 线性表的类型定义,38,2.1 线性表的类型定义,基本运算,(6)删除ListDelete(sq，i)。其作用是删除线性表sq的第i个元素ai,使sq由(a1，ai-1，ai，ai+l，an)变为(a1，ai-1，ai+1，an)。参数i的合法取值范围是：1in。,39,2.1 线性表的类型定义,基本运算,(7)求前趋 PriorElem(sq,e) 若线性表中存在元素e且不是第一个,其作用是返回e的前趋元素;否则，返回NULL。 (8)求后继 NextElem(

12、sq,e) 若线性表中存在元素e且不是最后一个,其作用是返回e的后继元素;否则，返回NULL,40,2.1 线性表的类型定义,基本运算,应用基本运算可以实现线性表的其他运算，如求任一给定数据元素的直接后继或直接前趋，将两个线性表合并成一个线性表或将一个线性表拆分成两个线性表等等。另一方面，在实际应用中，可以根据具体需要选择适当的基本运算,41,2.1 线性表的类型定义,解本题的算法思路是：依次检查线性表B中的每个元素，看它是否在线性表A中。若在表A中，则将其从A中删除。,基本运算,例2.1 利用线性表的基本运算，编写在线性表A中删除线性表B中出现的元素的算法。,42,2.1 线性表的类型定义,

13、void delete(sqlist /若在线性表A/中找到则将其删除 ,43,2.1 线性表的类型定义,解 先始化线性表C，然后依次检查线性表A中的每个元素，看它是否在线性表B中；若在线性表B中，则将其插入到线性表C中.,基本运算,例2.2 利用线性表的基本运算，编写将线性表A和B中公共元素生成线性表C的算法,44,2.1 线性表的类型定义,void celem(sqlist A，sqlist B，sqlist /若在线性表B中 /找到，将其插入C,45,2.2 线性表的顺序存储和实现,一、 线性表的顺序存储（顺序表） 定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。

14、即用一组地址连续的存储单元存放一个线性表 特点： 实现逻辑上相邻物理地址相邻 实现随机存取 实现： （一维）数组,46,2.2 线性表的顺序存储和实现,ElemType类型的数组listMaxSize存储线性表A= (a1 , a2 , , ai , ai+1 , , an) 元素地址计算方法 第i个元素的存储位置为：list+(i-1)*sizeof(ElemType),线性表的顺序存储结构示意图,47,2.2 线性表的顺序存储和实现,元素地址计算方法 ： lLOC(ai)=LOC(a1)+(i-1)*LlLOC(ai+1)=LOC(ai)+L其中：uL一个元素占用的存储单元个数uLOC(a

15、i)线性表第i个元素的地址,48,a2,2.2 线性表的顺序存储和实现,49,2.2 线性表的顺序存储和实现,线性表的顺序存储示例（图书资料）,typedef struct card int num;char name20;char author10;char publisher30;float price; DATATYPE;,50,可以定义为静态数组或变量 DATATYPE libraryM; 或动态申请和释放内存 DATATYPE *pData； pData=(DATATYPE*)malloc(sizeof(DATATYPE); free(pData )；,2.2 线性表的顺序存储和实现,