《数据结构》学习指导

《《数据结构》学习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。课程的特点，教学的要求，方法。明确数据结构所研究的问题以及有关基本概念。初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算

2、法设计的要求，算法的时间复杂度和算法的空间复杂度。3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。4、课程内容与基本要求(一)数据结构的引入(1)三个世界：现实世界，信息世界，机器世界。数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。(2)非数值问题(结合三个世界讲)：控制，管理，数据处理(3)数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。(二)课程的地

3、位，性质，作用。(1)地位:计算机专业的核心课程之一。(2)性质:算法理论基础和软件设计的技术基础课。(3)作用:程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三)数据结构的产生和发展(四)课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社200

4、2年25《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社2002年《数据结构》实验指导书唐开山自编讲义2002年(五)基本概念和术语(1)数据(2)数据元素(3)数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。数据结构综合三方面的内容：数据的逻辑结构，数据的存储结构及其运算。且不涉及元素本身的内容。(5)结构：数据元素相互之间的关系。a)四类基本结构；b)表示形式(6)逻辑结构(7)物理结构(存储结构)(8)元素或结

5、点(9)数据域(10)数据元素之间关系的两种表示方法：顺序映像—顺序存储结构；非顺序映像—链式存储结构。(11)存储结构的描述(12)数据类型(13)抽象数据类型(14)抽象数据类型按其值的不同特性分为三种类型(15)抽象数据类型可用三元组表示(16)多型数据类型(六)抽象数据类型的表示和实现(1)概述用伪码和类c语言作为描述工具(2)基本约定(3)抽象数据类型triplet的表示和实现①赋值参数和引用参数②部分基本操作及其实现：构造三元组(七)算法和算法分析(1)算法的概念(2)算法的五个特性①有穷性②确定性③可行性④输入⑤输出(3)算法设

6、计的要求①正确性②可读性③健壮性④效率与低存储量需求25(4)算法效率的度量①事后统计方法②事前分析估算的方法(5)时间复杂度：△时间复杂度的确定：算法中基本操作，重复执行的次数是问题规模n的基本函数f(n)，算法的时间量度记做T(n)=O(f(n))，则f(n)为该问题的渐进时间复杂，简称时间复杂度。△只需选择一种基本操作来讨论算法的时间复杂度。只需求出它关于n的增长率为何即可。△线性查找的平均时间复杂度和最坏时间复杂度。(6)空间复杂度：算法的存储空间需求。5、作业P71.3，1.5，P81.8中(1)、(3)、（5）、(7)、(8),P

7、101.12，1.14二、线性表1、学习目的：明确线性表的概念与基本运算；明确顺序表和链表的定义、组织形式、结构特征和类型说明；熟练掌握线性表的顺序存储结构和链接存储结构（单链表、循环链表、双向链表）及其基本运算的实现原理和方法。2、学习重点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结构特点；循环链表、双链表上删除与插入运算的实现。3、学习难点：指针操作；删除、插入运算中的指针操作顺序；双链表上指针

8、的操作顺序。 4、课程内容与基本要求(一)线性表类型的定义(1)线性表的四个特性(2)定义(3)抽象数据类型线性表的定义(二)线性表的顺序表示和实现(1)有关概念①