当前位置: 首页 > >

一篇关于数据结构算法与数据结构基础论述

发布时间:



数据结构绪论总结
基础知识摘要(选择题、判断题易出现)数据结构的基本概念逻辑结构分类图:存储结构算法

算法复杂度例题典型实例与解析


基础知识摘要(选择题、判断题易出现)
数据结构的基本概念

数据:信息的载体,能够有效地输入到计算机中并且能够被计算机处理的符号的总称,也是计算机程序处理对象的集合。


数据元素:数据元素是数据中的一个“个体”,是数据的基本组织单位。(易考)


数据项:一个数据元素可由若干个数据项组成。数据项是构成数据元素的不可分割的最小单元,是对客观事物某一方面特性的数据描述。(易考)


数据对象:性质相同的数据元素的集合


逻辑结构分类图:


存储结构

1. 顺序存储(数据元素之间的逻辑关系通过单元之间的相邻关系来体现):
优点:便于随机存取,存储密度高。
缺点:容易造成存储空间的浪费。
所以不便于进行插入和删除操作,因为删除和插入操作可能会引起大量数据元素的移动。
2. 链式结构(数据元素可以存储在任意的物理位置上):
优点:存储空间的利用率高,容易实现插入和删除操作。
缺点:数据元素的存储密度不高,且只能实现顺序存取。

3. 索引存储:
优点:查找速度快。
缺点:增加了索引表而占用了较多的存储空间。
4. 散列存储(根据元素的关键字直接计算出改数据元素的存储地址):
优点:实现查找、插入和删除操作的速度较快。
缺点:可能会造成“冲突”现象的问题,增加了时间和空间的开销。


算法

1. 算法五特性:
有穷性、确定性、有效性(可行性)、输入和输出。

2.评价一个算法的好坏时需要考虑下列目标:正确性、可读性、健壮性和高效性。


算法复杂度例题

【例1.1】


1 for(i = n; i>=1;i - -){
2 x = x+1;
3 for(j = n; j >= i; j--)
4 y = y+1;
}

其中:
语句1重复执行的次数是__n+1__;
语句2重复执行的次数是__n____;
语句3重复执行的次数是__(3+n)*n/2____;
语句4重复执行的次数是__(1+n)*n/2____;


【补充】: 算法的时间复杂度:O(1)

【例1.2】


i = 1; j = 0;
while ( i + j < = n ) {
if ( i > j ) j++; // *
else i++;
}

计算 带 * 语句的执行次数:
T(n) = n
可举特殊值带入计算


【例题1.3】


x = n; y = 0; // n 是不小于 1 的常数
while(x >= ( y + 1) * ( y + 1)){
y ++; / / *
}

计算 带 * 语句的大O表示为多少?
= O(n^1/2)


【例题1.4】


x = 91; y = 100;
while ( y > 0 ) {
if ( x > 100) {x -= 10; y - - ; } // *
else x++;
}

计算 带 * 语句的执行次数:
T(n) = 1100
解析:当每一次x从91到101都会经行判断所以当经行了11次之后 进行y- - 所以每进行一次y- -就会有11次的判断,所以得到执行次数为1100次。
存在着判断语句时,我们进行计算的时候,要多计算一次判断的情况


典型实例与解析

【例1.1】 存储数据时,不仅要存储 各数据元素的值,而且还要存储(数据元素之间的关系)。
补充:
1.在顺序存储结构中,数据元素之间是通过物理存储位置来体现的;在链式存储结构中,数据元素之间的关系通过结点的指针来体现的。
2.链式存储结构中,各个结点的存储空间可以不连续,但是如果描述的是在一个结点内的存储单元地址必须连续的。


【例1.2】可以用(抽象数据类型)定义一个完整的数据结构。


【例1.3】一个算法应该是(程序和要满足五个基本特性


【例1.4】算法的时间复杂度取决于(问题的规模和待处理数据的初始状态)
补充:算法的时间复杂度不仅与问题规模有关,还依赖于输入数据集的状态
【例1.5】数据结构中评价算法的两个性能


【例1.5】空间复杂度也是一个算法好坏的标准之一,它所描述的时算法在运行过程中所占用辅助空间大小。


持续更新中,嘿嘿。



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网