(02331)数据结构串讲资料(一)

《(02331)数据结构串讲资料(一)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构串讲资料（一）第一部分课程概述一、课程简介数据结构是高等教育臼学考试计算机及应用专业（独立本科段）考试计划中一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的冇关知识。本课程的n的和任务是使应考者较全而地掌握各种常用的数据结构，为学习后续软件课程捉供必要的基础，捉髙运用数据结构解决实际问题的能力。二、指定教材《数据结构》全国高等教育H学考试指导委员会组编，黄刘住主编，经济科学出版社2000版。第1章绪论•1.1数据结构•1.2基本概念和术语•1.3抽象数据类型•1.4算法和算法分析引论■对于一个课题，在计算机领域，一般遵循下面的解决原则：需

2、求分析、总体设计、模块分割、建立数学模型、解数学模型的算法、程序编制、调试、结果■数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。■数据结构的地位：数学、硕件、软件Z间。核心专业基础课.1.1数据结构的基本概念和术语1.基本术语•数据：是信息的载体，能够被计算机识别存储和加工处理。（数字、字符、声音、图形、图像等等）•数据元索：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。常常作为一个整体进行考虑和处理，如纪录/结构。•数据项：数据的不可分割的最小单位，如结构中的域。•数据对象：性质相同的数据元素的集合，是数据的一个

3、子集2.数据结构定义：是数据Z间的相互关系，及数据的组织形式，相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括以卞三方面内容：（1）数据元素之间的逻辑关系。也称为数据的逻辑结构（2）数据元素及其关系在计算机存储器2内的表示，称为数据的存储结构（3）数据的运算，即对数据施加的操作数据类型：所谓数据类型是一个值的集合及在这些值上定义的一组操作的总称。按“值”是否可以分解，可将数据类型划分为两类：①原子类型，其值不可分解；例如整形，字符型等标准类型及指针等标准的导出类型②结构类型，其值可分解为若干个成分（或称为分量）如数组，结构等类型，抽象数据类型——

4、ADT定义：抽象数据类型是指抽彖数据的组织和相关的操作，它可以看做是数据的逻辑结构及其在逻辑结构上定义的操作，每一个操作由它的输入和输出定义。ADT二（D,S,P）其中：D是数据对象，用结点的有限集合表示；S是D上的关系的集合，用结点间的序偶的集合来表示；P是对D的基本操作的集合。基本操作的定义格式为：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉数据的逻辑结构冇两种：（1）线性结构：若结构是非空集，则有且仅有一个开始节点和一个终端节点，并且所有节点都最多只有一个肓接前趋和一个肓接后续。例如线性表。（2）非线性结构：一个节点可能有有

5、多个直接前趋和直接后续。第5章到第7章讨论的数据结构都是非线性结构。数据的存储结构可分为四种：顺序存储方法——借助元素在存储器的相对位置來表示数据元素之间的逻辑关系。链式存储方法——借助指示元素存储地址的指针表示数据元素之间的逻辑关系。索引存储方法在存储结点的同时，还建立附加的索引表，索引表屮的每一项称为索引项。1.2学习数据结构的意义计算机科学家沃斯（N.Wirth）提出的:“算法+数据结构二程序”这里的数据结构指的是逻辑结构和存储结构，而算法则是对数据运算的描述。上述思想揭示了程序设计的木质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算

6、法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。例1:编写程序查询某城市某人的电话号码建立一张登记表，存放2个数据项：姓名+Tel好的算法取决于这张农的结构及存储方式：•将表中结点按照姓名顺序地存储在计算机中，依次查找，对能遍历整个表都找不到。•建立一张姓氏索引表：姓+表中的起始地址则不需杳找其他姓氐查找效率得到捉高。1.3算法和算法分析1.算法定义：指一系列确定的而且是在有限步骤内能完成的操作。算法的重要特性(1)有穷性:能执行结束(2)确定性:对于相同的输入执行相同的路径(3)0至多个输入(4)1至多个输出(5)冇效性(可

7、行性)(川于描述算法的操作都是足够基木的)例：问题：程序是不是算法？如操作系统，只要系统不遭破坏，它就永远不会停止，即使没冇作业要处理，仍处于一个等待循环屮，等待新作业的进入。因此操作系统程序不是一个算法。2.算法设计的要求(1)正确性(2)可读性(3)健壮性容错性(4)效率与低存储屋需求3.算法的效率定义：一个处法如果能在所要求的资源限制内将问题解决好，则称这个并法是冇效率的。例如，一个资源限制是：可川來存储数据的全部空间——町能是分离的内存空间限制和磁盘空间限制以及允许执行每一个子任务所需要的时间。4.算法的分析一一算法性能的评价评价标准：1)算法所需的

8、计算时间2)算法所需的存储空间3)算法的简单性度量算