没有合适的资源?快使用搜索试试~ 我知道了~
汇编数据结构与算法大全.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 193 浏览量
2022-05-07
16:26:53
上传
评论
收藏 143KB DOC 举报
温馨提示
试读
18页
汇编数据结构与算法大全.doc
资源推荐
资源详情
资源评论
www.jie-ri.org
2.1 知识点
2.1.1 数据结构的基本概念
数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处
理的符号的集合。
数据对象是具有相同性质的数据元素的集合。通常,一个数据对象中的数据元素不是
孤立的,而是彼此之间存在着一定的联系,这种联系就是数据结构。数据对象中数据元素
之间的联系需要在对数据进行存储和加工中反映出来,因此,数据结构概念一般包括三方
面的内容:数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的
运算的集合。
数据的逻辑结构
数据的逻辑结构只抽象地反映数据元素之间的逻辑关系,它与数据的存储无关,是独
立于计算机的。
数据的存储结构
数据的存储结构是数据的逻辑结构在计算机存储器里的实现(亦称为映象)。它是依赖
于计算机的,并有四种基本的存储映象方法,分别为顺序存储方法、链接存储方法、索引
存储方法、散列存储方法。这四种基本的存储方法也可以组合起来对数据结构进行存储映
象。
数据的运算
数据的运算定义在数据的逻辑结构之上,每种逻辑结构都有一个运算的集合。常用的
运算有:查找、插入、删除、更新、排序等。显然,对数据运算的具体实现方法只有在确
定了存储结构之后才能加以考虑。
文本框: 考纲要求
1.数据结构、算法的基本概念
2.线性表的定义、存储和运算
3.树形结构的定义、存储和运算
4.排序的基本概念和排序算法
5.检索的基本概念和检索算法
2.1.2 算法的基本概念
算法及其特征
简单地说,一个算法就是一种解题方法,更严格地说,算法是由若干条指令组成的有
穷序列,它必须具有以下特征:
(1)有穷性:一个算法必须在执行有穷步后结束。
(2)确定性:算法的每一步必须是确切地定义的,无二义性。
(3)可行性:算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷
次运算后完成。
(4)输入:一个算法具有 0 个或多个输入的外界量,它们是算法开始前对算法最初给
出的量。
(5)输出:一个算法至少产生一个输出,它们是与输入有某种关系的量。
对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。
算法的分析
求解同一个问题可以有多种不同的算法,评价一个算法的优劣除了正确性和简明性外,
主要考虑两点:一是执行算法所耗费的时间,二是执行算法所耗费的存储空间,特别是辅
助存储空间的耗费。就这两者而言,前者显得比后者更为重要,在数据结构中往往更注重
www.jie-ri.org
www.jie-ri.org
对算法执行时间的分析。一个算法所耗费的时间是该算法中每条语句的执行时间之和,而
每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。
2.1.3 线性表
线性表是 n≥0 个元素的一个有限序列:(al,a2,a3,....an-1,an)
线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。
若 n≥0,则 a1 为第一个元素,an 为最后一个元素。元素 ai-l 先于 ai,我们称 ai-l 为 ai 的
前驱;ai 在 ai-1 之后,ai 为 ai-1 的后继。除第一个元素外,每个元素都有一个且仅有一个
直接前驱;除最后一个元素外,每个元素都有一个且仅有一个直接后继。
用顺序存储结构存储的线性表称做顺序表;用链式存储结构存储的线性表称做链表;
用散列方法存储的线性表称做散列表。如果对线性表插入和删除运算发生的位置加以限制,
则成为两种特殊的线性表——栈和队列。若线性表中的元素都是单个字符,则称做串。
文本框: $ 算法与程序的区别
算法的含义与程序十分相似,但二者又有区别。一个程序不一定满足有穷性,操作系统就
是如此,只要整个系统不被破坏、操作系统就永远不会停止,所以操作系统程序不是一个
算法。另外,程序中的指令必须是机器可以执行的,而算法中的指令则无此限制。但是,
一个算法如果用机器可执行的语言书写,则它就是一个程序。
2.1.4 线性表的存储
有多种存储方式能将线性表存储在计算机内,其中最常用的是顺序存储和链接存储。
线性表的顺序存储
线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组,从数组的第
一个元素开始,将线性表的结点依次存储在数组中。即线性表的第 i 个结点存储在数组的
第 i(0≤i≤n-1)个元素中,用数组元素的顺序存储来体现线性表中结点的先后次序关系。
用数组存储线性表的最大优点是能直接访问线性表中的任一结点。
用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的,可能会
与线性表的结点可以任意增加和减少的要求相矛盾;二是执行线性表的结点插入、删除操
作时要移动存于数组中的其他元素,使插入和删除操作不够简便。
线性表的链接存储
线性表链接存储是用链表存储线性表,最简单的用单链表。如从链表的第一个表元开
始,将线性表的结点依次存储在链表的各表元中。即线性表的第 i 个结点存储在链表的第
i(0<i<n-1)个表元中。链表的每个表元除要存储线性结点的信息外,还要有一个成分用
来存储其后继结点的指针。单链表就是通过链接指针来体现线性表中结点的先后次序关系。
每个链表还要有一个指向链表的第一个表元,链表的最末一个表元的后继指针值为空。用
链表存储线性表的优点是线性表的每个表元的后继指针就能完成插入或删除的操作,不需
移动任何表元。
其缺点也主要有两条:一是每个表元增加了一个后继指针成分,要花费更多的存储空
间;二是不便随机地直接访问线性表的任一结点。
2.1.5 线性表的运算
查找运算
查找线性表的第 i(0≤i≤n-l)个表元;
在线性表中查找具有给定键值的表元;
插入运算
把新表元插在线性表的第 i(0≤i≤n)个位置上;
把新表元插在具有给定键值的表元的前面或后面;
删除运算
www.jie-ri.org
www.jie-ri.org
删除线性表的第 i(0≤i≤n-1)个表元;
删除线性表中具有给定键值的表元;
其他运算
统计线性表元的个数;
输出线性表各表元的值;
复制线性表;
线性表分析;
线性表合并;
线性表排序;
按某种规则整理线性表。
2.1.6 数组
数组是有限个同类型数据元素组成的序列。一个二维数组(或称矩阵)可以看成是由
m 个行向量所组成的向量,也可以看成是由 n 个列向量所组成的向量。数组的运算主要有
查找或存取数组中某个元素。
由于计算机存储单元是一维的结构,而数组是多维的结构,因此就必须把多维结构映
射为一维的结构,即把多维结构按一定次序排列成一维的,常用的排列次序有行优先顺序
和列优先顺序两种。
给出任一数组元素的下标,可以直接计算数组元素的存放地址。二维数组元素地址的
计算公式是:
(l)行优先顺序下:
LOC(aij)=LOC(a11)+((i-1)×n+(j-l))×λ
(2)列优先顺序下:
LOC(aij)=LOC(a11)+((j-1)×m+(i-l))×λ
式中,n 和 m 分别为数组每行和每列的元素个数,λ 为每个数组元素占用的存储单元
个数。
2.1.7 稀疏矩阵
具有大量 0 元素的矩阵称做稀疏矩阵。对于稀疏矩阵可以进行压缩存储,只存储非 0
元素。若非 0 元素的分布有规律,则可以用顺序方法存储非 0 元素,仍可以用公式计算数
组元素的地址。一般的稀疏矩阵主要有两种存储方法。三元组法和十字链表法。
2.1.8 广义表
广义表(又称列表)是线性表的推广,是由零个或多个单元素或子表所组成的有限序
列。广义表和线性表的区别在于:线性表的成分都是结构上不可分的单元素,而广义表的
成分既可以是单元素,又可以是有结构的表。
广义表一般记做:
LS=(d1,d2,.,dn)
其中 LS 是广义表的名字,n 是长度,d 是广义表成分。
广义表有如下特征:
(1)广义表的元素可以是子表,而子表的元素还可以是子表。
(2)广义表可被其他广义表所共享(引用)。
(3)广义表可以是递归的表,即广义表也可以是本身的一个子表。
和线性表类似,可对广义表进行的运算有查找、插入和删除等。但广义表的两个非常
重要的基本运算是取广义表表头 HEAD(LS)和取广义表表尾 TAIL(LS)。
2.1.9 树
树的基本概念
www.jie-ri.org
剩余17页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 82
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功