数据结构和算法.ppt

《数据结构和算法.ppt》由会员分享，可在线阅读，更多相关《数据结构和算法.ppt（72页珍藏版）》请在优知文库上搜索。

1、重要性：信息领域：先修课程：课程特点：课程学习要求：课程考核方法：课程考核方法：1 1、期末考试：、期末考试： 50%50%；2 2、实验：、实验： 30%30%；3 3、课堂笔记：、课堂笔记： 5%5%；4 4、平时表现（作业、考勤）：、平时表现（作业、考勤）： 5%5%；5 5、阶段测验、阶段测验 ： 5%5%；6 6、课程总结、课程总结 ： 5%5%；引言引言数据结构是一门数据结构是一门 讨论讨论怎样合理地组织数据、建立合适的数据怎样合理地组织数据、建立合适的数据结构，从而提高计算机执行程序时的时间效率和结构，从而提高计算机执行程序时的时间效率和空间效率空间效率问题问题的课程的课程。第1

2、章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析 在计算机科学中，是指。 数值数据、字符、声音、图像、图形等，在程序设计时通常作，在程序设计时通常作为一个整体进行考虑和处理为一个整体进行考虑和处理。 同义词：同义词： 元素、结点、顶点、记录、对象、元组等元素、结点、顶点、记录、对象、元组等。 具有独立含义的最小标识单位具有独立含义的最小标识单位 同义词：字段、域、属性等同义词：字段、域、属性等。10002数据结构陈英18.00书号书名作者价格10001计算机原理张明15.00 表中某一本书的相关数据表中某一

3、本书的相关数据( (表中每一行表中每一行) )都是一个数据元素，都是一个数据元素，每一个数据元素其具有独立意义。每一个数据元素由每一个数据元素其具有独立意义。每一个数据元素由4 4个简单个简单数据项数据项( (书号、书名、作者、价格书号、书名、作者、价格) )组成。组成。 是一个同类值的集合和定义在这个值集上的一组操作的总称。 当我们在高级程序语言中定义每一种数据类型，在程当我们在高级程序语言中定义每一种数据类型，在程序编译时计算机语言编译系统就知道了以下信息：序编译时计算机语言编译系统就知道了以下信息：(1) (1) 一组性质相同的值集合，一组性质相同的值集合，(2) (2) 一个预定的存储

4、体系，一个预定的存储体系，(3) (3) 定义在这个值集合上的一组操作。定义在这个值集合上的一组操作。 可分为两类：、 简单类型的数据是不可分解的整体，如整数、实数、字符、指针、枚举量等。 请解释整型数据类型。整型数据类型通常有整型数据类型通常有short(2short(2字节字节) )、int(2int(2字节字节) )、long(4long(4字节字节) )等形式，等形式，其值集为某个区间上的整数。其值集为某个区间上的整数。 如果整型是两个字节表示的，其值集范围是：如果整型是两个字节表示的，其值集范围是：-32768-327683276732767，定义在整，定义在整型数据上的操作为：单目

5、正型数据上的操作为：单目正(+)(+)操作、负操作、负(-)(-)操作，双目加操作，双目加(+)(+)操作、减操作、减(-)(-)操作、操作、乘乘( (* *) )操作、除操作、除(/)(/)操作和取模操作和取模(MOD)(MOD)操作等算术运算，双目关系操作等算术运算，双目关系(， =，=，等等) )操作运算以及赋值操作运算以及赋值(=)(=)操作等。操作等。 由简单数据类型按照一定的规则构造而成。 结构数据类型中还可包含结构数据类型，所以结构数据类型的数据可以分解成若干个简单数据类型的数据或子结构数据类型。也称作复合数据类型。 数据对象是数据类型的实例，简称对象。 数据对象举例。例如：例如

6、：25，是整型数据对象。，是整型数据对象。 A，是字符数据对象。，是字符数据对象。 char *p ，定义，定义p为一个字符指针对象。为一个字符指针对象。 int a10，定义，定义a为一个含有为一个含有10个整型数的整型数组对象。个整型数的整型数组对象。 Rectangle r，定义，定义 r 为一个为一个Rectangle类型的对象。类型的对象。 RECtangle rec，定义，定义 rec 为一个为一个RECtangle 抽象数据类型的抽象数据类型的对象。对象。 第1章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.

7、5 算法性能分析(1) 数据的逻辑结构逻辑结构，即数据元素间的逻辑关系；(2) 数据的存储结构存储结构，数据元素在计算机存储器中的存储方式；(3) 数据的运算运算，对数据施加的操作。 没有统一的定义，通常指数据元素之间的相互关没有统一的定义，通常指数据元素之间的相互关系，即数据的组织形式；包括：系，即数据的组织形式；包括： 定义：定义： 数据元素之间的相互联系称为数据的逻辑结构。 根据数据元素之间关系的不同特性，通常有下列四类基本结构。 线性逻辑结构线性逻辑结构 树型逻辑结构树型逻辑结构 图型逻辑结构图型逻辑结构 集合逻辑结构集合逻辑结构 数据的逻辑结构可以用图形形象地表示。 用图形中的每一个

8、节点(或叫顶点)对应着一个数据元素，用两节点间的连线(称有向边或弧)对应着关系中的一个序偶，其中第一个元素为起始点，第二个元素为终止点，箭头指向终止点。 节点之间是一个对一个的关系，呈线性关系，是线性逻辑结构。节点之间是一个对一个的关系，呈线性关系，是线性逻辑结构。它的特征是：若结构为非空集，则该结构有且只有一个开始节点它的特征是：若结构为非空集，则该结构有且只有一个开始节点和一个终端节点，并且所有节点都最多只有一个直接前趋和一个和一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接后继。直接后继。它的特征是：节点之间是一个对多个的关系，一个节点可能有它的特征是：节点之间是一个对多个的关

9、系，一个节点可能有一个直接前趋和多个直接后继。呈树形关系，是树形数据结构一个直接前趋和多个直接后继。呈树形关系，是树形数据结构( (非线性结构非线性结构) )。 它的特征是：节点之间是多个对多个的关系，它的特征是：节点之间是多个对多个的关系，一个节点可能有多个直接前趋和多个直接后继。一个节点可能有多个直接前趋和多个直接后继。呈图形关系呈图形关系 ( (非线性结构非线性结构) )。 集合中数据元素之间的关系是松散的，实际运算时可以用其它结构来表示它。 数据的存储结构是 用计算机处理具体问题时，必须考虑由这个具体问题抽象出的数据在计算机中的存储方式，以便于运算。通常情况下，数据在计算机中存储方式有

10、以下四种： 顺序存储顺序存储 链接存储链接存储 索引存储索引存储 散列存储散列存储 将逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现 （3，5，6，8，23，12，54）= float an 逻辑上相邻的结点不一定存储在物理位置相邻的存储单元中，结点间的逻辑关系由附加的指针字段来体现。 一组数据元素的集合（3，5，6） 365 设有一组线性排列的数据元素(zhao，qian，sun，li，zhou，wu，zheng，wang)，其链接存储形式如图所示。 该方法在存储结点信息的同时，建立附加的索引表。索引表中的每一个索引项由唯一标识某结点的关键字以及该

11、结点的地址组成。赵1钱23孙56李891、赵文 2、赵五 23、钱四 24、钱进 56、孙军 89、李百 应用一个函数，将每一个结点的关键字作为该函数的自变量，得到相应的函数值作为该结点的存储地址。 有函数 y = 2x , 集合（3，5，6）的存储：1 2 3 4 5 6 7 8 9 10 11 12 13 356 正如整数和实数分别对应不同的运算一样，不同逻辑结构的数据有不同的运算。数据运算不仅仅是加、减、乘、除、矩阵、微分、积分、方程等等这些数值计算问题，还包括像在一张表格中，进行查找记录，增加记录，修改记录，删除记录等等操作运算，而怎样才能进行这样的运算呢? 在数据结构中，这些运算常常

12、涉及算法问题。 线性结构的数据数据可以非常方便地进行插入、线性结构的数据数据可以非常方便地进行插入、删除数据元素，而对于树和图这样的非线性结构的数据删除数据元素，而对于树和图这样的非线性结构的数据可以有查询数据元素之间的关系、遍历数据元素等运算可以有查询数据元素之间的关系、遍历数据元素等运算。 根据以上分析，我们可以看到数据结构的概念主根据以上分析，我们可以看到数据结构的概念主要包括如图所示的三个方面的主要内容：要包括如图所示的三个方面的主要内容：等等序、插入、删除、修改数据的运算：检索、排散列存储索引存储链式存储顺序存储数据的存储结构散列结构图形结构树形结构非线性结构串及数组队列栈顺序表线性

13、结构数据的逻辑结构数据结构 我们讨论两数据结构是否相同，主要看它们的逻辑我们讨论两数据结构是否相同，主要看它们的逻辑结构、存储结构和运算集合是否相同，这三者中只要结构、存储结构和运算集合是否相同，这三者中只要有一个不同，都不能称这两个数据结构相同。有一个不同，都不能称这两个数据结构相同。 设有两个呈线性排列的数据分别是设有两个呈线性排列的数据分别是1, 3, 5, 7, 9和和0.1, 0.2, 0.4, 0.6, 0.8（其中的每个数是数据元素），（其中的每个数是数据元素），现将它们分别存放在整型一维数组现将它们分别存放在整型一维数组A5和实型一维数和实型一维数组组B5中。现在，我们来分析这

14、两个数据的数据结构中。现在，我们来分析这两个数据的数据结构是否相同。是否相同。 首先，这两个数据都是呈线性排列，则它们的逻首先，这两个数据都是呈线性排列，则它们的逻辑结构均为线性逻辑结构；辑结构均为线性逻辑结构； 其次，它们分别存储在一维数组中，这使得逻辑其次，它们分别存储在一维数组中，这使得逻辑位置相邻的数据元素在物理存储位置上也相邻，这样位置相邻的数据元素在物理存储位置上也相邻，这样它们都属于顺序存储结构；它们都属于顺序存储结构； 另外，根据另外，根据C C语言语法规定，一维数组语言语法规定，一维数组A5A5中的数中的数据元素间可以进行加、减、乘、除和模运算，而一维据元素间可以进行加、减、

15、乘、除和模运算，而一维数组数组B5B5中的数据元素间只能进行加、减、乘、除运中的数据元素间只能进行加、减、乘、除运算；这样，数据算；这样，数据1, 3, 5, 7, 91, 3, 5, 7, 9和数据和数据0.1, 0.2, 0.1, 0.2, 0.4, 0.6, 0.80.4, 0.6, 0.8的运算集合不同。可以断定，这两个的运算集合不同。可以断定，这两个数据有着完全不同的数据结构。数据有着完全不同的数据结构。 数据类型数据类型 可看作是高级语言提供的可看作是高级语言提供的数据结构数据结构数据结构数据结构3 3方面的联系方面的联系 同一逻辑结构的不同存储结构，用不同的名字称谓同一逻辑结构的

16、不同存储结构，用不同的名字称谓 如：线性表如：线性表 顺序表、链表、散列表顺序表、链表、散列表 运算不同，称谓也不同运算不同，称谓也不同 如：线性表如：线性表 栈、队列栈、队列第1章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析 int float double char 数组数组 int5 char25 结构体结构体 struct 结构型名结构型名 数据类型名数据类型名 成员成员; ; struct student long number; char name20; char sex; float score3; ; struct student A50; int a, b, *p=&a, *q ; q = &b；ap110110 已知定义：int x，*k=&x； 试问：表达式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：答：对于*k，表示变量x。 对于&x，&是地址运算符，&x表示变示变量x的地址。 对于*&x，表示*k，即变量x。 对于&*k， *k表示变量x， &*k即表示变量