ch1数据结构的概念数据类型算法10_10.ppt

本科课堂教学秩序若干规定 实行课堂点名制度。 学生迟到时要报告，经老师允许后，方可进入课堂。 学生因病因事请假时，必须在上课前报告老师。 凡发现学生在上课时吃早餐、吸烟、睡觉者，一律请出教室；在计算中心上机时玩游戏者，一律请出机房。 学生不准交头接耳，不准看报、看小说或阅读与本课程无关的其他书籍，未经讲课老师允许，课堂内不准使用随身所带的电子和通讯设备（如收录设备、通讯工具、电子存录与播放设备等），已带入教室的通讯工具必须关闭电源。 课前、课间休息时，班干应组织学生将黑板擦刷干净。 课程简介 计算机软件技术基础是一门专业基础课，是我院的一门必修课。该课程主要由三部分组成。 1) 数据结构：从抽象数据类型的角度讲述各基本类型的数据结构及其应用，以及讲述查找和排序的实现方法； 2) 操作系统：从资源管理的角度讲述操作系统的基本功能及其简单实现； 3) 软件工程方法：讲述软件项目工程化的开发过程。主要讲述软件工程的基本概念和原理，支持软件开发和维护的理论、方法和标准。 学习方式 ? 听课 （启发式、讨论式） ? 读书 （预习、复习） ? 课题开发报告 （实践） 考试成绩 §1 软件技术基础： 平时成绩30％ （书面作业） 期末卷面考试70 ％ §2 软件技术基础实践课考核： 提交软件课设文档报告 数据结构部分(Data Structure) 数据结构 要讲述的内容及课时分配 第1章 概述 (共1学时) 1.1 数据结构的概念 1.1.1 有关概念和术语 1.1.2 逻辑结构和数据结构 第2章 线性结构 (共8学时) 2.1 线性表 3学时 2.1.1 线性表的逻辑结构 2.1.2 线性表的顺序存储及运算 2.1.3 线性表的链式存储及运算 2.1.4 顺序表和链表的比较 2.2 栈和队列 3学时 2.2.1 栈 2.2.2 队列 2.3 串 0.5学时 2.3.1 串及其基本运算 2.3.2 串的定长顺序存储及基本运算 2.4 数组、特殊矩阵 1.5学时 2.4.1 多维数组 2.4.2 特殊矩阵的压缩存储 第3章 非线性结构 (共7学时) 3.1 树 4学时 3.1.1 树的定义和基本术语 3.1.2 树的基本操作 3.1.3 树的存储结构 3.2 二叉树 3.2.1 二叉树的概念 3.2.2 基本操作与存储实现 3.2.3 二叉树的遍历 3.2.4 树、森林和二叉树之间的转换 3.3 图 3学时 3.3.1 图的基本概念 3.3.2 图的存储表示 3.3.3 图的遍历 第4章 查找与排序 (共2学时) 4.1 查找 4.1.1 基本概念与术语 4.1.2 静态查找表 4.2 排序 4.2.1 排序的概念 4.2.2 三种简单排序算法 课程背景 数据结构是伴随计算机软件技术的发展而分化出的一个领域，产生于二十世纪60年代末期，在70年代得到极大的发展，形成了较为完善的研究内容和教学体系。 2001年美国把“算法与数据结构”列入计算机科学教学计划，将其作为计算机及信息技术相关学科专业的本科必修基础课程，并以此科目作为评估学生对计算机科学掌握、了解的重要指标。 ? 严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，1997.4 ? 严蔚敏，吴伟民，数据结构题集（C语言版），清华大学出版社，1999.2 ? 李春葆，数据结构习题与解析（C语言篇）修 订版，清华大学出版社，2002.4 丁宝康等，数据结构自学考试指导，清华大学 出版社， 2001年5月。 上机软件: C语言为主 数据结构课程的地位 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程 课程目标 学会如何有效地组织信息，以便支持高效的数据处理 掌握常用的基本数据结构及其应用 学会合理地组织数据，有效地表示数据，有效地处理数据 基本掌握算法的设计与分析技术 提高程序设计能力与程序的质量 提高使用计算机解决问题的能力 有关概念Q1：什么是数据结构？ 答: 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： 例如： 复数可以取如下的定义： 复数是一种数据结构