数据结构第1章绪论

《数据结构第1章绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论课程背景计算机=软件+硬件软件=程序+文档（软件工程的观点）程序=算法+数据结构（NiklausWirth，图灵奖获得者)‘数据结构’=‘计算机程序设计技巧'(Kunth，图灵奖获得者)熟悉c语言≠写出‘好’的程序学习数据结构=编写高水平的程序《数据结构》：计算机类专业8大核心课程之一注：教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程图灵奖：1966年设置，每年奖励1-2名杰出的计算机科学家，被誉为计算机领域的诺贝尔奖基本学习方法课前预习、上

2、课认真听讲课后多做习题多上机编程（熟练掌握c、c++）勤学勤练教材和参考书教材数据结构（c语言版）秦锋编著中国科技大学出版社主要参考书《数据结构例题详解及课程设计指导》秦锋、袁志祥等中国科技大学出版社《数据结构C语言版》严蔚敏、吴伟民清华大学出版社《C程序设计》谭浩强清华大学出版社本章主要内容什么是数据结构基本概念和术语算法1.1什么是数据结构早期的计算机主要用于数值计算现在的计算机更多地是用于非数值数据处理（字符、表格、图像）对非数值数据的处理：分析数据的逻辑特征→抽象出合适的数学模型→合理地存储到计算机→设计出算法→编写出程

3、序请看例1～3例1学生信息查询系统首先要构造学生信息表，表1-1表达出学生数据的逻辑关系，它就是一个数学模型，这张表如何构造、在计算机内如何存储将直接影响查找算法的设计以及算法的效率表1-1学生信息表的特点每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构，现实中这类关系的数据有很多。。通常的操作插入某个学生的信息删除某个学生的信息更新某个学生的信息按条件查找某个学生的信息中国象棋、国际象棋的人机大战，核心技术是人编写的对弈程序。对弈步

4、骤和过程可以用树型结构表达出来（数学模型）例2人机对弈图1-1井子棋对弈树树形应用树型结构的特点所处理的数据之间具有层次关系，这是我们所说的树形结构,还有如：基因遗传关系等，它是一种非线性结构。对它的操作有：建立树形结构、存储树、访问树中的每个结点例3排课子系统排课系统中各门课程的先后关系可以用一个图表达出来，这个图表达了数据的逻辑关系（数学模型）在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。如何安排每学期的课程？计算机专业课程的开设情况如下表所示：计算机

5、专业学生的必修课程课程编号课程名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1课程先后关系的图型描述c1c9c4c2c12c10c11c5c3c6c7c8图结构的特点关系比较复杂，用例1和例2的结构表达不出来，必须用图结构描述（离散数学中的图论）通过实施创建图结构，存储图结构，可以对图结构中的顶点进行线性排序

6、，从而找出每学期应该上的课程。现实中，这类关系的数据非常多。如：网络规划、交通、通讯规划等，这里典型的非线性关系。操作对象的关系复杂多样操作不再是单纯的数值计算，更多的是非数值问题求解，需要对数据（不是数值）进行分析、组织及管理。必须对数据进行有效的组织、存储，才能对数据进行有效的操作返回结论1.2基本概念和术语数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位（记录、结构体）数据元素的分类简单型数据元素由一个数据

7、项组成，数据项就是数据中不可再分割的最小单位复杂型数据元素复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息数据结构是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构线性结构树形结构图形结构数据结构主要研究数据的逻辑结构数据的存储结构对数据的操作（运算算法）数据结构的定义数据结构的定义逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构存储结构（物理结构）是指数据结构在存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表

8、示清楚数据元素之间的逻辑结构数据运算对数据施加的操作。运算的定义依赖于逻辑结构，但运算的实现必依赖于存储结构（真正理解）顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的