数据结构-使用c语言 朱战立

《数据结构-使用c语言 朱战立》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教材：朱战立编著，数据结构——使用C语言（第3版），西安交通大学出版社，2003年数据结构2学时数：70（50学时授课＋20学时上机）教材：朱战立编著，数据结构（使用C语言）第3版，西安交通大学出版社，2003年参考书：[1]严蔚敏等，数据结构（C语言版），清华大学出版社[2]数据结构学习指导与典型题解，朱战立等编著，西安交通大学出版社，2002年3内容安排章内容学时章内容学时1绪论47树和二叉树102线性表48图103栈和队列89排序44串210查找45数组411上机（共10次）20合计7041、上课认真听讲，适当做好笔记。2、考试成绩分两部分：平时成绩（包括出勤和上机实验）

2、占20%，期末成绩占80%。3、课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。4、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。对学生的几点要求5第1章　绪　论讨论5个问题：1.1数据结构的基本概念1.2抽象数据类型和软件构造方法1.4算法和算法的时间复杂度1.5算法书写规范61.1数据结构的基本概念1、举例建立一个学生档案系统。学生表包括学号、姓名、性别、籍贯。要求：查找“王红”是否存在。解决的方法步骤：如何记录所有学生记录（及选择何种逻辑数据结构）？选择何种存储结构？若把所有记录依次存

3、储在一个数组中——采用顺序存储结构若采用指针链表——采用链式存储结构7为什么要学习数据结构？什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法→数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）8电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：

4、如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述10例1.1电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。非数值计算问题：11例1.2田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。非数值计算问题：12（1）设用如下六个不同的代号代表不同的项目：跳高

5、跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。非数值计算问题----田径赛的时间安排问题解法13姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BF比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛14非数值计算问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。15数据结构课程的

6、形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。1617数据结构课程的地位它是计算机专业及相关专业的核心课程之一，是计算机及相关专业的重要骨干基础课程。它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。18《数据结构课程》所处的地位：19数据结

7、构的核心研究内容数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。本书围绕数据结构的三种基本结构：线性结构（第2-5章）、树形结构（第7章）和图形结构（第8章）展开讨论，研究解决如下问题：一个具体问题的逻辑数据结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？202、基本术语(1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。(2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序