《数据结构相关文档和PPT讲述》由会员分享，可在线阅读，更多相关《数据结构相关文档和PPT讲述（55页珍藏版）》请在金锄头文库上搜索。
1、数据结构 任课教师：邱 保 志 Email：iebzqiu 单位：郑州大学信息工程学院 为什么要学习数据结构？ n介于数学、计算机软件、硬件三者之间的核心 课程 n一般程序设计（尤指非数值计算的程序设计） 的基础 n设计和实现编译程序、操作系统、数据库系统 及其它系统程序和大型应用程序的重要基础。 如何利用计算机解决实际应用问题？ n需经过以下三步骤： n从具体问题中抽象出一个适当的数学模型 。 n设计一个解此数学模型的算法 n编程调试，得到最终答案 n Niklaus Wirth： Algorithm + Data Structures = Programs n 算法: 处理问题的策略 n
2、数据结构: 问题的数学模型 n 程序:为计算机处理问题编制一组指令集 登录号书名作者出版单位出版时间 N.3.73.762 数据结构 严蔚敏 吴伟民清华大学出版社 2003.12 图书馆的书目检索系统自动化问题 数学模型 一对一的线性结构 人机对弈问题 数学模型 一对多的树结构 “井”字棋对弈“树” 先手： C1 C9 C4 C2 C12 C10 C11 C5 C3 C6 C7 C8 计算机专业课程开设先后关系图 数学模型 多对多的图形结构 计算机专业课程开设问题 怎样学数据结构？ n牢记基本概念和经典算法 n联系实际，富于联想 n总结算法之间的共性和特性。 n忌：求偏、求难、重算法轻概念。
3、n三阶段：模仿-总结-创新 本书的内容简介 n第一章:综述数据结构等基本概念，介绍算法和算 法分析(3/2周) n第二章-第七章:讨论线性表(3周)、栈和队列(2周) 、串(2周) 、数组和广义表(2周) 、树和二叉树(2周) 、图(2周)等基本类型的数据结构、物理结构及其相 关操作的实现。 n第九章:静态查找表和动态查找表。(2周) n第十章:介绍五种内排序方法(2周) n复习（1/2周） 1.2 基本概念和术语 n数据：信息的载体，是描述客观事物的数、字符 及所有能输入到计算机中被计算机程序识别和处理 的符号的集合。 n数值性数据 n非数值性数据 n数据元素：数据的基本单位 n一个数据元素
4、可由若干个数据项组成。 n数据项是数据不可分割的最小单位。 n数据对象：数据的子集。具有相同性质的数据元 素集合。 n例如：整数对象 N = 0, 1, 2, 数据结构（逻辑结构） n数据结构：相互间存在一种或多种特定关系的 数据元素集合。 n结构：数据元素相互之间的关系 n特定关系： 特定关系数据结构举例 没有关系集合正整数 一对一关系线性表图书管理 一对多关系树 棋局对弈树 多对多关系 图（网） 课程开设先后关系图 数据结构的形式定义 nDS=(D,S) nD：数据元素的有限集合。 设a1,a2,ai,aj,an nS：定义在D上的关系的有限集合。 n若aiRaj,则ai,ajS n若ai
5、Raj,且ajRai,则(ai,aj)S n例：复数可定义为一种数据结构： COMPLEX=(C,R) C：含有两个实数的集合C1,C2； R：P是定义在C上的一种关系 n课上习题：T=(K,R)，画出它所对应的逻辑结构 nK=1,2,3,4,5,6 ；=r r=, aiaj aiaj 线性结构线性结构 树形结构树形结构 456 23 1 AB ED C F 图形结构图形结构 125 6 4 3 集合结构集合结构 四类基本逻辑结构关系图 n数据结构在计算机中的表示： n数据元素的表示 n数据元素之间关系的表示 n顺序映象：借助元素在存储器的相对 位置表示数据元素之间的逻辑关系。对应于 顺序存储
6、结构(sequential sets). n非顺序映象：利用指示元素存储地址 的指针表示数据元素间的逻辑关系。对应于 n链式存储结构(linked lists) n索引树(indexed trees) n散列表(hash tables) 数据的物理结构(存储结构) 数据逻辑结构和物理结构之间的关系 n关系： n任意一个算法的设计取决于选定的逻辑结构 n算法的实现依赖于采用的物理结构。 实际应用 算法 数据结构 线性结构 非线性结构 存储结构 顺序存储结构 非顺序存储结构 定位(查找) 加法、乘法 比较、移动 （逻辑） (物理) 数据结构主要研究什么？ n解决问题时可能遇到的典型的逻辑结构 n逻
7、辑结构的存储映象（物理结构） n数据结构的相关操作及其实现（算法） 数据类型 n 数据类型：一组性质相同的值的集合以及定义于该 值集上的一组操作的总称。 例：C语言中整型变量 值：定义在某区间上的整数 操作：加、减、乘、除、取模 按值的不同特性分： 原子类型：值不可再分 C的五种基本数据类型:char,int,float,double,void 结构类型：值由若干个成分按某种结构组成 抽象数据类型 n一个数据模型及定义在该模型上的一组操作。 n按照值域的不同特性:原子类型（值不可分解）、 固定聚合类型（值有确定数目的成分）、可变聚合 类型（成分的数目不确定）。 n例：抽象数据类型：矩阵=矩阵+
8、(求转置、加、乘、逆等） 形式定义：DS=(D, S, P)。 D：数据对象 S：D上的关系集， P：对D的基本操作集。 构造性操作：插入、删除、修改 非构造性操作：查找、排序 抽象数据类型的定义格式(仅适用于本书) nADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 n基本操作的定义格式为 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 n参数表有两种参数： n赋值参数：只为操作提供输入值； n引用参数：以j=1,2,n;ai,jElemSet 数据关系:R=Row,Col Row=|1im,1
9、jn- 1 Col=|1im- 1,1jn 基本操作： CreateMatrix( void example_1( ) Status a10; a0.9=0; 例2 #define OK 1 typedef int Status; Status example_2(int x,int y) if(xy) xy; return OK; 类语言的语法规则示例（续） 例3 typedef struct student char id5; char name11; int age; int math; int eng; int ds; int os; student; void example_3(
10、) student s; s=(,0,0,0,0,0); 附加内容：算法的描述方法 n步骤法 n程序流程图 nN-S图 n伪码 步骤法 n顺序查找数据序列中某个特定值 Step1：输入数据序列datan和欲查找值key Step2：从序列中的最后一个元素开始查找 Step3：若该元素值不等于key，查找前一项 Step4 ：若该元素值等于key，表示查找成功，返回key在 序列中的位置，去第六步 Step5：如果数据全部查找过但未能找到key，表示查找失 败，返回。 Step6：结束 程序流程图五种基本控制结构 程序流程图举例 开始 输入待查找序列 datan 查找成功，返回i 输入要查找的值
11、key 查找失败返回 datai=key 从最后一个元素开始查找 待查序列全查过 N N n顺序查找数据序列中某特定值 结束 i- N-S图 nN-S图也叫盒图，一种符合结构化程序设计 原则的图形描述工具。 n五种基本控制结构由五种图形构件表示： N-S图举例 顺序查找数据序列中某特定值 F 输入待查找序列datan 输入要查找的值key 从最后一个元素开始查找 datai=key 查找成功 返回key 所在位置 全查过 查找失败 返回 T FT 下一次循环 Do while (data!=key) 伪码 n以夹杂程序语法和自然语言的形式来描述解决 问题的方法，有类C、类PASCAL语言等。本
12、书用 的是类C语言。 n顺序查找数据序列中某特定值，由类C给出其算法 Status Search_Seq(SqList L,KeyType key) L.elem0=key; for(i=L.length;!EQ(L.elemi,key);i-); return i; Search_Seq.h代码 /说明部分 #include /包含预编译头文件 #define TRUE 1 /宏定义 #define FALSE 0 typedef int KeyType; /类型别名的定义 typedef struct KeyType *elem; int length; SqList; bool EQ(i
13、nt i, int j) /判断两个整数是否相等 if(i=j) return TRUE; else return FALSE; 顺序查找数据序列中某特定值的程序代码 stdio.h math.h string.h malloc.h /函数实现 void Construction(SqList printf(“input the length of data:n); scanf(%d, L.elem=(KeyType*)malloc(L.length+1)*sizeof(KeyType) ; printf(“input the key:n”); /输入待查找的关键字 for(i=1;i=L.l
14、ength;i+) scanf(%d, int Search(SqList L,KeyType key) /查找函数 int i; L.elem0=key; for(i=L.length;!EQ(L.elemi,key);-i); return i; 顺序查找数据序列中某特定值的程序代码 Search_Seq.cpp代码 #include “search_seq.h void main() KeyType key; SqList L; printf(“input key:n”); scanf(“%d”, /读入要查找的值 Construction(L); /创建待查找数据序列 int posi
15、tion=Search(L,key); /查找 printf(the key is located in %d,position); 顺序查找数据序列中某特定值的程序代码 1.4算法和算法分析 n算法的定义：对特定问题求解步骤的一种描述，是指令 的有限序列，一条指令表示一个或多个操作。 n操作分为： n数值计算：加、减、乘、除等算术运算 n非数值计算：检索、排序、插入、删除。 n算法的特性： n有穷性：算法应在执行有穷步后结束 n确定性：每步定义都是确切、无歧义的 n可行性：算法中描述的操作都可通过已经实现的 基本运算执行有限次实现 n输入： 有0个或多个输入 n输出： 有一个或多个输出(处理结果) n算法与程序的区别 算法设计的要求 n正确性： 程序不含语法错误； 程序对于几组输入数据能够得出满足要求的结果； 对精心选择带有刁难性的几组数据能得出满足要求的结果； 程序对于一切合法的输入数据都能产生满足要求的结果。 n可读性：易于阅读和交流，其次是机器运行。 n健壮性： n当输入数据
