《数据结构c语言版 CH_1》由会员分享，可在线阅读，更多相关《数据结构c语言版 CH_1（22页珍藏版）》请在金锄头文库上搜索。
1、阜阳师范学院数学与计算科学学院 信息教研室 王先超*数据结构是计算机及相关专业中一门重要的专业基础课程。当用计 算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数 据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面 内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识 基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机 应用专业中具有举足轻重的作用。本课程的任务是： 在基础方面，要求学生掌握常用数据结构的基 本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。 学业基础：本课程的先修课程为
2、离散数学和高级语言程序设计。 学习本课程必须具备高级语言程序设计(比如Pascal语言或C语言) 的基础知识与基本技能。它的后续课程有操作系统和数据库原理 等。 进度安排：总学时68，其中课堂讲授60学时，实验教 学8学时。第一章 绪言 1.1 什么是数据结构程序=数据结构+算法 例1 书目自动检索系统登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2 人机对奕问题树.例3 教学计划编排问题一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的
3、关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数 据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程， 如果从顶点vi到vj之间存在有向边，则表示课程i必须先于课程j进行。数据结构定义: 是一门研究非数值计算的程序设 计问题中计算机的操作对象以及它们之间的关系 和操作等等的学科由以上三个例子可见，描述这类非数值计算问题的数学模型不 再是数学方程，而是诸如表、树、图之类的数据结构。因此， 可以说数据结构课程主要是研究非数值计算的程序设计问题中 所出现的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构的目的是为了了解计算机处理对象的特性，将实 际问题
4、中所涉及的处理对象在计算机中表示出来并对它们进行 处理。与此同时，通过算法训练来提高学生的思维能力，通过 程序设计的技能训练来促进学生的综合应用能力和专业素质的 提高。 1.2 基本概念和术语 数据（data)所有能输入到计算机中去的描述客 观事物的符号 数据元素（data element）数据的基本单位， 也称节点（node）或记录（record） 数据项（data item）有独立含义的数据最小单 位，也称域(field) 数据结构（data structure)数据元素和数据元 素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）数据元素间除“同属于一个集合”外，无其
5、它关系 线性结构一个对一个，如线性表、栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算 机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为： 顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3
6、元素41345 h存储地址 存储内容 指针1345 元素1 14001346 元素4 . . .1400 元素2 1536. . .1536 元素3 1346链式存储 h数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构顺序存储链式存储 线性表 栈 队树形结构 图形结构数据结构的三个方面：数据类型高级语言中指数据的取值范围及其上 可进行的操作的总称例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型typ
7、edef struct int num;char name20;float score; STUDENT; STUDENT stu1,stu2, *p; 1.3 算法的描述和算法分析简介 算法（algorithm）解决某一特定问题的具体步 骤的描述，是指令的有限序列 算法特性算法的描述采用C语言 算法的评价衡量算法优劣的标准 v正确性(correctness) v可读性(readability) v健壮性(robustness) v效率与低存储量算法效率用依据该算法编制的程序在计算机上执行所消耗 的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或 多组相同的统计数据区分缺
8、点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取 决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行， 效率均不同，所以使用绝对时间单位衡量算法效率不合适算法的时间复杂性（time complexity）算法的时间相当于程序时间中的运行时间部分。 同样，关键操作的次数对时间复杂性的影响最大。假 设, 算法中关键操作执行的次数是问题特征（规模） n 的某个函数f（n）。那么，算法的时间量度(复杂性 )记作： T (n) = O(f(n)在多数情况下, 算法中关键操作执行的次数和包含 它的语句的频度相同。 语句的频度（frequency count)指的是该语句重复执行的次数。所以，在实 际应用时，用算法中语句的最大频度作为算法的时 间复杂性。例1 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时 间复杂度为(1) 如果将s=0也看成是基本操作，则语句频度为， 其时间复杂度仍为(1)，即常量阶。 例2、for(I=1;I, , , , ，试画出其逻辑结构图，并说明它是什么类型 的逻辑结构。
