数据结构DATA STRUCTURE

《数据结构DATA STRUCTURE》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DATASTRUCTUREC++版1.1《数据结构》课程研究的内容1.2《数据结构》课程的发展历史及课程重要性1.3基本概念和术语1.4算法及算法实现第一章绪论1.1《数据结构》课程研究的内容数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作算法的学科。它主要研究：①数据的逻辑结构--数据关系之间的逻辑关系②数据的存储结构--数据的逻辑结构在计算机中的表示③操作算法----插入、删除、修改、查询、排序等其中，数据的逻辑结构：集合线性结构-----表、栈、队列非线性结构-----树、图数据的存储结构：顺序存

2、储结构-----数组链式存储结构-----指针。1.2《数据结构》课程的发展历史及课程的重要性·源于程序设计,1968年在美国开设。它随着大型程序的出现而出现。·我国1980‘s年代初开设。它是计算机专业的核心课程，计算机专业考研必考。学习《数据结构》的目的：①提高复杂程序设计及软件开发的能力②培养算法设计能力③为后继课程（如操作系统、编译原理等）打基础。课程改革:开通精品课程网站,欢迎使用!实验单独设课,强调上机实践能力数据结构课程:理论课(4学分)+实验课(2学分)+课程设计(1学分)课程考核1.3基本概念和术语1、数据2、数据元素

3、3、数据对象4、数据结构5、数据类型6、抽象数据类型1.数据:能输入到计算机中的符号集合.2.数据元素:数据的基本单位.3.数据对象:具有相同性质的数据元素的集合.4.数据结构:DATASTRUCTURE数据及其相互关系的集合.分为逻辑结构和存储结构.数据结构----------------类CLASS数据之间的关系-------属性基本操作-------------方法“学生”表格“课程”表格树形结构树二叉树二叉排序树图结构网结构数据类型定义：一个数值的集合,以及定义于这个数值集合上的一组操作的总称。C++语言中的数据类型基本数据类型

4、、指针类型、数组类型、结构体类型、类class抽象数据类型(ADTs:AbstractDataTypes)抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。ADT：抽象数据类型名data数据元素之间逻辑关系定义operation操作1操作2……操作n抽象数据类型的定义：抽象数据类型的不同视图C++的类体现了抽象数据类型的思想使用视图-----ADT的定义ADT{逻辑结构+操作集合

5、}设计视图------ADT的设计数据结构:{存储结构+算法设计}实现视图-------ADT的实现类CLASS{成员变量+成员函数}1.4算法和算法分析1.定义：算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。2.特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性不会产生二义性有穷性算法应在执行有穷步后结束可行性在现有环境下能够实现3.评价算法的标准正确性可读性健壮性(鲁棒性)时间复杂性空间复杂性4.算法的描述方法(1)自然语言(2)流程图(3)伪代码(4)

6、程序设计语言例:P.36-385.时间复杂性的概念数量级的思想例1：求两个方阵的乘积C＝A*BMATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti,j,k;for(i=0;i

7、(k=1;k<=j;k++)x++;常数阶对数阶线性阶线性对数阶平方阶立方阶………K次方阶指数阶常见的时间复杂度，按数量级递增排序：6.空间复杂性的概念程序指令的存储空间数据存储空间辅助存储空间数量级的思想